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.

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.