Algoritmi e strutture dati 2

Per il diario delle lezioni e il materiale didattico si veda la pagina web del corso sul sito del docente:
https://www.mat.uniroma2.it/~pasquale/dida/aa2223/asd2

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.
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 2022 - Gennaio 2023):
Giovedì 16:00 - 18:00 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.