Algoritmi e strutture dati 2

Esami sessione estiva - Modalità on-line

In ottemperanza al D.R. 888/2020 del 11/05/2020 gli esami della sessione estiva si svolgeranno "con modalità a distanza".

Io non uso Microsoft Office 365 per la gestione dei corsi e personalmente disapprovo l'utilizzo in ambito accademico di qualunque piattaforma basata su software proprietario.

Gli esami di ASD2 si svolgeranno qui:
https://tvalgoteam.site/asd2
(si tratta di un'istanza locale di Jitsi installata su un pc che si trova nella nostra Università).

Esercitazione.

Introduzione alle Cryptocurrencies: cenni alle funzioni hash crittografiche e il loro ruolo nei sistemi di criptovalute. Cenni alle reti peer-to-peer. Il sistema Bitcoin e la sua Blockchain. (Il codice sorgente di Bitcoin è liberamente scaricabile qui: https://github.com/bitcoin/bitcoin). Esercizi.

[Guest lecture by Sara Rizzo] Cascate informative: un esperimento di herding, modello generale e analisi del processo sequenziale. Processi di diffusione nelle reti: modello di un processo di diffusione, caratterizzazione cascate complete e cluster. Esercizi.

Cenni al World Wide Web e al funzionamento di un motore di ricerca: Crawling, Indexing e il problema del Ranking. Il PageRank e sua formulazione come Random Walk. Introduzione alle catene di Markov e al loro utilizzo nell'analisi di algoritmi probabilistici. Esempio: analisi di un semplice algoritmo probabilistico per 2-SAT. ([2]: Cap 7.1). Esercizi.

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). Esercizi.

Esercitazione.

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.4). Esercizi.

Permutation Routing sugli ipercubi: lower bound per la procedura BitFix e analisi dell'algoritmo probabilistico ([2]: Cap. 4.6). 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). Esercizi.

Test di primalità probabilistici polinomiali. Il test di Fermat. Richiami di teoria elementare dei numeri: radici non-banali dell'unità. Il test di Miller-Rabin. Il codice scritto in aula (primes.py) corretto e commentato. ([1]: Cap. 1.3. Per approfondire si veda [4]: Cap. 13.8). Esercizi.

Esercitazione.

Valore atteso di una variabile aleatoria e linearità. Esempio: Analisi del numero atteso di confronti dell'algoritmo Random Quick Sort. Il problema Contention Resolution ([2]: Cap. 2.5 e [3]: Cap. 13.1). 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]). 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). Esercizi.

Euristiche di ricerca locale. Esempio: Ricerca locale per Min Vertex Cover. Cenni a Simulated annealing. Ricerca locale con fattore di approssimazione garantito. Esempio: Un algoritmo approssimante per Max-Cut ([1]: Cap. 9.3, e [3]: Cap. 12.4). 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, [3]: Cap. 11.8). Esercizi.

Affrontare i problemi computazionalmente difficili: 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). Esercizi.
(Se vi dovesse venire in mente un'idea promettente per risolvere istanze di SAT, considerate la possibilità di partecipare alla prossima edizione di questo evento)

Il running time dell'algoritmo di Ford e Fulkerson. La variante con capacity scaling per rendere l'algoritmo polinomiale. ([3]: Cap. 7.3). Esercizi.

L'algoritmo di Ford e Fulkerson per Max-Flow: correttezza, running time e ottimalità. ([1]: Cap. 7.2. Si veda anche [3]: Cap. 7.1 e 7.2). Esercizi.

Esercitazione. (Il codice scritto in aula per l'Esercizio 5: travasi.py)

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). 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). 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). 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, per esempio, il Capitolo 4 su [3]). Esercizi.

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

Programma provvisorio

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. La teoria dell'NP-completezza da un punto di vista algoritmico e come 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).

La rapida evoluzione tecnologica degli ultimi decenni ha portato all'ordine del giorno nuove sfide algoritmiche. Nell'ultima parte del corso ne studieremo alcune e vedremo come sono state affrontate.

• Ranking. Le idee algoritmiche che hanno rivoluzionato i motori di ricerca: PageRank e HITS. La matematica dietro le scene: Algebra lineare e catene di Markov.
• Algoritmi che imparano. Expert selection e il meta-algoritmo dei multiplicative updates
• Cryptocurrencies.Le idee algoritmiche che hanno dato vita a Bitcoin e alla Blockchain. Gli ingredienti: reti Peer-to-Peer, funzioni hash crittografiche e crittografia a chiave pubblica.

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.

Testi di supporto

[3] J. Kleinberg and E. Tardos. Algorithm Design. Addison-Wesley, 2005.

[4] T.H. Cormen, C.E. Leiserson, R.L. Rivest, C. Stein. Introduction to Algorithms. The MIT press, 2001.

Durante il periodo delle lezioni (Ottobre 2019 - Gennaio 2020):
Giovedì 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 si effettueranno due prove intermedie sotto forma di homework. Gli studenti che ricevono una valutazione positiva agli homework sono esonerati dalla prova scritta.