Algoritmi e strutture dati 2

Informazioni

In accordo con le decisioni del Consiglio del Corso di Laurea, per l'AA 2020/21 il corso verrà erogato in modalità on-line. Durante il corso valuteremo la possibilità di svolgere alcune attività (in particolare le esercitazioni) in presenza, in base alla disponibilità delle aule e alle opinioni/preferenze degli studenti frequentanti.

Gli studenti interessati a partecipare alle lezioni sono invitati a iscriversi al corso tramite il Delphi. Questo non è né obbligatorio né vincolante (potete seguire il corso anche senza registrarvi e potete abbandonarlo in ogni momento anche se vi siete registrati), ma è utile a me per avere l'elenco degli indirizzi email degli studenti interessati, nel caso avessi necessità di inviare comunicazioni urgenti relative al corso.

Io non uso Microsoft Teams per la gestione dei corsi e personalmente disapprovo l'utilizzo in ambito accademico di qualunque piattaforma basata su software proprietario. Tutto il materiale relativo a questo corso sarà reso disponibile sulla pagina web del corso
https://www.mat.uniroma2.it/~pasquale/dida/aa2021/asd2/
Le lezioni si svolgeranno di norma qui:

https://tvalgoteam.site/asd2

(si tratta di un'istanza di Jitsi installata su un pc che si trova nel mio ufficio). Chi volesse fare delle prove indipendenti con questo sistema di videoconferenza può usare il server messo a disposizione dagli sviluppatori di jitsi qui, oppure uno dei numerosi server italiani messi a disposizione da volontari in questo periodo di emergenza, di cui trovate un elenco qui (o, volendo, può anche installarsi un proprio server: istruzioni dettagliate si trovano qui).

Per qualunque altra informazione non esitate a contattarmi per email.

F.P.

Le firme digitali e il loro utilizzo in Bitcoin. La rete P2P dei full node. La Proof of Work per validare le transazioni e la Blockchain come registro distribuito. ([3]: Cap. 1 e 2).
Lavagna. Esercizi.

Introduzione alle Cryptocurrencies: le funzioni hash crittografiche e le loro proprietà. Collision resistance e il paradosso dei compleanni. Cenni alla costruzione di Merkle-Damgård. ([3]: Cap. 1 e [2]: Cap 5.1).
Lavagna. Esercizi.

Esercitazione.

Metodi Monte Carlo per la stima di parametri. Campionamento casuale (sampling) e conteggio, cenni alla classe #P. Esempio: Un FPRAS (Fully Polynomial-time Randomized Approximation Scheme) per il problema del conteggio delle assegnazioni che soddisfano una formula in DNF. ([2]: Cap. 11.1, 11.2).
Lavagna. Esercizi.

Il Metodo Probabilistico: il conteggio di base e il metodo del valore atteso. Cenni alla tecnica di derandomizzazione tramite medie condizionate ([2]: Cap. 6.1, 6.2, 6.3).
Lavagna. Esercizi.

[Guest Lecture by Isabella Ziccardi]: Pseudorandomness e pseudorandom generators, i primi tentativi: middle-square e linear congruential. Periodo massimo e potency. Cenni alle implicazioni dell'esistenza dei pseudorandom generator in teoria della complessità. Cenni ai Cryptographically-secure pseudo random generators.
Lavagna. Note. Esercizi.

Stime del discostamento di una variabile aleatoria dal suo valore atteso. La disuguaglianza di Markov. La varianza di una variabile aleatoria e la disuguaglianza di Chebyshev. Somme di variabili aleatorie indipendenti e le disuguaglianze di Chernoff ([2]: Cap. 3.1, 3.2, 3.3, 4.1, 4.2).
Lavagna. Esercizi.

Test di primalità probabilistici polinomiali. Il test di Fermat. Richiami di teoria elementare dei numeri: numeri di Carmichael, radici non-banali dell'unità, cenni al Teorema dei numeri primi. Il test di Miller-Rabin. ([1]: Cap. 1.3. Per approfondire si veda [5]: Cap. 13.8).
Lavagna. Codice. Esercizi.

Esercitazione.

Valore atteso di una variabile aleatoria e linearità. Esempi: Analisi di un semplice algoritmo 2-apx in valore atteso per Max-Cut. Analisi del numero atteso di confronti dell'algoritmo Random Quick Sort. ([2]: Cap. 2.5).
Lavagna. Esercizi.

Introduzione agli algoritmi probabilistici. Esempio: un algoritmo probabilistico per verificare il prodotto di matrici. Variabili aleatorie e valore atteso: la distribuzione geometrica. ([2]: Cap. 1.3, 2.4. Per un ripasso di probabilità dicreta si vedano, per esempio, i primi due capitoli in [2]).
Lavagna. Esercizi.

I problemi computazionalmente difficili come risorsa: I fondamenti della crittografia a chiave pubblica, il protocollo di Diffie-Hellman per la generazione di una chiave condivisa e il sistema di cifratura RSA. Cenni a One-time pad, cifrari a blocchi, AES. ([1]: Cap. 1.2 e 1.4).
Lavagna. Esercizi.

Euristiche di ricerca locale. Ricerca locale con fattore di approssimazione garantito. Esempio: Un algoritmo approssimante per Max-Cut. Cenni a Gradient descent e Simulated annealing. ([1]: Cap. 9.3, e [4]: Cap. 12.4).
Lavagna. Esercizi.

Esercitazione.

Affrontare i problemi computazionalmente difficili: 2. Algoritmi Approssimanti. Esempio: un algoritmo 2-approssimante per il problema k-clustering. Approssimazioni arbitrariamente buone. Esempio: un FPTAS (Fully Polynomial-Time Approximation Scheme) per il problema Knapsack ([1]: Cap. 9.2, [4]: Cap. 11.8).
Lavagna. Esercizi.

Problemi computazionalmente difficili e come affrontarli: 1. Ricerca esaustiva intelligente. Le tecniche: Backtracking e Branch-and-bound. Esempi: Un algoritmo per SAT e un algoritmo per TSP ([1]: Cap. 9.1).
Lavagna. Esercizi.

Ottimalità e running time dell'algoritmo di Ford e Fulkerson. La variante con capacity scaling per rendere l'algoritmo polinomiale. ([4]: Cap. 7.2 e 7.3).
Lavagna. Esercizi.

Reti di flusso e "grafo residuo". L'algoritmo di Ford e Fulkerson per il problema Max-Flow: correttezza e terminazione. ([1]: Cap. 7.2. Si veda anche [4]: Cap. 7.1 e 7.2).
Lavagna. Esercizi.

Esercitazione.

La tecnica della Riduzione. Esempi: Un algoritmo lineare per 2-SAT ottenuto tramite riduzione al problema di scomporre un grafo diretto in componenti fortemente connesse e DAG delle componenti. Richiami su grafi diretti, DAGs e topological sorting. Introduzione al problema Max Flow ([1]: Esercizio 3.28 e inizio Cap. 7.2).
Lavagna. Esercizi.

La tecnica della Programmazione Dinamica. Esempi: Un algoritmo per Chain matrix multiplication e un algoritmo per Independent set su alberi. ([1]: Cap. 6.5, 6.7. Per un ripasso sulla tecnica della Programmazione Dinamica si veda il Capitolo 6 in [4]).
Lavagna. Esercizi.

La tecnica Divide et Impera. Esempio: l'algoritmo di Karatsuba per moltiplicare due interi. Cenni all'algoritmo di Strassen per la moltiplicazione di matrici. Richiami sulle relazioni di ricorrenza e sul Teorema Master. ([1]: Cap. 1.1, 2.1, 2.2, 2.5. Per un ripasso sulla tecnica Divide et Impera si veda il Capitolo 5 in [4]).
Lavagna. Esercizi.

Introduzione al corso, descrizione del programma di massima. La tecnica Greedy. Esempio: Un algoritmo greedy per decidere la soddisfacibilità delle formule di Horn ([1]: Cap. 5.3. Per un ripasso sulla tecnica greedy si veda il Capitolo 4 in [4]).
Lavagna. Esercizi.

Si veda la pagina del corso sul sito del docente:
https://www.mat.uniroma2.it/~pasquale/dida/aa2021/asd2/

1. Progettare algoritmi efficienti. Riepilogo delle tecniche più efficaci per progettare algoritmi efficienti: Greedy, Divide-et-Impera, Programmazione Dinamica, Riduzioni. Il problema Max-Flow e l'algoritmo di Ford e Fulkerson. Linear programming e duality.
2. Problemi computazionalmente difficili. Richiami di NP-completezza da un punto di vista algoritmico. Le tecniche per affrontare i problemi computazionalmente difficili: ricerca esaustiva intelligente, algoritmi approssimanti, euristiche. I problemi computazionalmente difficili come risorsa: il protocollo di Diffie-Hellman, il sistema RSA e i fondamenti della crittografia a chiave pubblica. La matematica dietro le scene: Teoria dei numeri.
3. Algoritmi probabilistici. Il ruolo della randomness negli algoritmi. Quando scegliere a caso semplifica l'implementazione: Test di primalità di Miller-Rabin. Quando scegliere a caso rende gli algoritmi più efficienti: Packet Routing. Quando poter scegliere a caso è indispensabile: Protocolli interattivi e zero-knowledge proofs. Le tecniche per analizzare gli algoritmi probabilistici, la concentrazione della misura. Metodi Monte Carlo. Cenni alla classe #P. Campionamento e conteggio approssimato. Catene di Markov a stati finiti e tempo discreto. Cenni a FPRAS (Fully Polynomial-time Radomized Approximation Scheme) e ai metodi MCMC (Markov Chain Monte Carlo).
4. Cryptocurrencies.Le idee algoritmiche che hanno dato vita a Bitcoin. Gli ingredienti: reti Peer-to-Peer, funzioni hash crittografiche e firme digitali. La Blockchain e il problema del consenso distribuito. Transazioni, blocchi, alberi di Merkle.

Testi di riferimento

[1] S. Dasgupta, C. Papadimitriou, and U. Vazirani. Algorithms. McGraw-Hill, 2006.
[2] M. Mitzenmacher and E. Upfal. Probability and Computing (2nd edition). Cambridge University Press, 2017.
[3] A. Narayanan, J. Bonneau, E. Felten, A. Miller, and S. Goldfeder. Bitcoin and Cryptocurrency Technologies. Princeton University Press, 2016.

Testi di supporto

[4] J. Kleinberg and E. Tardos. Algorithm Design. Addison-Wesley, 2005.
[5] T.H. Cormen, C.E. Leiserson, R.L. Rivest, C. Stein. Introduction to Algorithms. The MIT press, 2001.
[6] T. Roughgarden. Algorithms Illuminated: Part 4: Algorithms for NP-Hard Problems. Soundlikeyourself Publishing LLC, 2020.

Durante il periodo delle lezioni (Ottobre 2020 - Gennaio 2021):
Lunedì 15:30 - 17:30 oppure su appuntamento.

Al di fuori del periodo delle lezioni:
Su appuntamento.

L'esame consiste in una prova scritta e in un colloquio orale.

Durante il corso gli studenti potranno svolgere due test intermedi sotto forma di homework. Chi ottiene una valutazione positiva a entrambi gli homework è esonerato dalla prova scritta.