Comunicazioni
Lezioni
Materiale didattico | InformazioniAnno accademico | 2022-2023 |
---|
Crediti | 6 |
---|
Settore | INF/01 |
---|
Anno | 3 |
---|
Semestre | 1 |
---|
Propedeuticità | Algoritmi e strutture dati. |
---|
ProgrammaProgramma provvisorio
- 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.
- 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.
- 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).
- 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 riferimentoTesti 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. |
Ricevimento studentiDurante 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. |
Modalità di esameL'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. |
|