Algoritmi e strutture dati 2

Docente: Francesco Pasquale

Comunicazioni

Informazioni

04-10-2021 22:41

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.

 

Le lezioni si svolgono, di norma, in Aula 16 al SoGeNe. Per venire in aula è necessario prenotare un posto tramite il Delphi. Si ricorda inoltre che chi entra nei locali dell'Ateneo è tenuto a rispettare il protocollo di sicurezza, reperibile qui: infostudenticovid.uniroma2.it.

 

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 didattico relativo a questo corso sarà reso disponibile sulla pagina web del corso:
https://www.mat.uniroma2.it/~pasquale/dida/aa2122/asd2/

 

Gli studenti che non possono partecipare alle lezioni in presenza, potranno partecipare da remoto collegandosi a questo link: 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). Cercherò inoltre di registrare tutte le lezioni e renderle disponibili.

 

Per qualunque altra informazione non esitate a contattarmi per email.

 

F.P.


Lezioni


Materiale didattico

Informazioni

Anno accademico2021-2022
Crediti6
SettoreINF/01
Anno3
Semestre1
PropedeuticitàAlgoritmi e strutture dati.

Programma

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

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.


Ricevimento studenti

Durante il periodo delle lezioni (Ottobre 2021 - Gennaio 2022):
Giovedì 16:00 - 18:00 oppure su appuntamento.

Al di fuori del periodo delle lezioni:
Su appuntamento.


Modalità di esame

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.