Algoritmi e Strutture Dati 2

CdL Informatica - Univ. Roma Tor Vergata
AA 2021/2022

• Diario
• Testi
• Contatti

Homework

• Primo homework: Consegna entro le ore 19:00 di venerdì 26 novembre 2021.
  Risultati: 0268333, 0270316, 0280714, 0281010, 0281111, 0284291, 0285619, 0286706.
• Secondo homework: Consegna entro le ore 19:00 di venerdì 21 gennaio 2022.
  Errata Corrige.
  Risultati: 0268333, 0270316, 0280714, 0281010, 0281111, 0284291, 0285619, 0286706.

Informazioni

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 su questa pagina web.

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.

Programma provvisorio

Orario lezioni

Mercoledì: 09:00 - 11:00 e Giovedì: 14:00 - 16:00

• In Aula 16, Edificio SoGeNe
• In videoconferenza qui: https://tvalgoteam.site/asd2

Diario delle lezioni

• 6 ottobre 2021: 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] o anche il Capitolo 13 in [7]).
  Video. Esercizi.
• 7 ottobre 2021: 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] o anche i Capitoli 3 e 4 in [8]).
  Video. Esercizi.
• 13 ottobre 2021: 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] o anche i Capitoli 16 e 17 in [7]).
  Video. Esercizi.
• 14 ottobre 2021: 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 - per approfondire si veda anche [9] - e inizio Cap. 7.2).
  Esercizi.
• 20 ottobre 2021: Esercitazione.
• 21 ottobre 2021: Reti di flusso e "grafo residuo". L'algoritmo di Ford e Fulkerson per il problema Max-Flow: correttezza e terminazione. ([1]: Cap. 7.2. Si veda anche [4]: Cap. 7.1 e 7.2).
  Video. Esercizi.
• 27 ottobre 2021: Ottimalità e running time dell'algoritmo di Ford e Fulkerson. La variante con capacity scaling per rendere l'algoritmo polinomiale. ([4]: Cap. 7.2 e 7.3).
  Video. Esercizi.
• 28 ottobre 2021: Problemi computazionalmente difficili e come affrontarli: 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).
  Video. 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)
• 3 novembre 2021: 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, [4]: Cap. 11.8).
  Video. Esercizi.
  
• 4 novembre 2021: Esercitazione.
• 10 novembre 2021: Euristiche di ricerca locale. Ricerca locale con fattore di approssimazione garantito. Esempio: Un algoritmo approssimante per Max-Cut. ([1]: Cap. 9.3, e [4]: Cap. 12.4).
  Video. Esercizi.
• 11 novembre 2021: 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).
  Video. Esercizi.
• 17 novembre 2021: 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]).
  Video. Esercizi.
• 18 novembre 2021: Valore atteso di una variabile aleatoria e linearità. Esempi: Analisi di un semplice algoritmo 2-apx in valore atteso per Max-Cut. Analisi del numero atteso di confronti dell'algoritmo Random Quick Sort. ([2]: Cap. 2.5).
  Video. Esercizi.
• 24 novembre 2021: Esercitazione.
• 25 novembre 2021: Test di primalità probabilistici polinomiali. Il test di Fermat. Richiami di teoria elementare dei numeri: numeri di Carmichael, radici non-banali dell'unità, cenni al Teorema dei numeri primi. Il test di Miller-Rabin. ([1]: Cap. 1.3. Per approfondire si veda [5]: Cap. 13.8).
  Video. Codice. Esercizi.
• 1 dicembre 2021: 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).
  Video. Esercizi.
• 2 dicembre 2021: Il Metodo Probabilistico: il conteggio di base e il metodo del valore atteso. Esempi. ([2]: Cap. 6.1, 6.2, 6.4).
  Video. Esercizi.
• 9 dicembre 2021: Introduzione alle Catene di Markov. Analisi di un algoritmo probabilistico per 2-SAT. ([2]: Cap. 7.1).
  Video. Esercizi.
• 15 dicembre 2021: Esercitazione.
• 16 dicembre 2021: Analisi di un algoritmo probabilistico per 3-SAT con running time O((4/3)ⁿpoly(n)). ([2]: Cap. 7.1).
  Video. Esercizi.
• 22 dicembre 2021: Metodi Monte Carlo per la stima di parametri. Campionamento casuale (sampling) e conteggio. 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).
  Video. Esercizi.
• 23 dicembre 2021: Introduzione alle Cryptocurrencies: le funzioni hash crittografiche e le loro proprietà. Collision resistance e il paradosso dei compleanni. Cenni alla costruzione di Merkle-Damgård. ([3]: Cap. 1 e [2]: Cap 5.1).
  Video. Esercizi.
• 12 gennaio 2022: La Blockchain come registro distribuito. La rete P2P dei full node. Le transazioni. Esempi su Bitcoin testnet ([3]: Cap. 2 e 3. Si veda anche [9]).
  Video. Esercizi.
• 13 gennaio 2022: Esercitazione.

Testi di riferimento

[1] Algorithms
Sanjoy Dasgupta, Christos Papadimitriou, Umesh Vazirani.
McGraw Hill, 2006

[2] Probability and Computing (2nd edition)
Michael Mitzenmacher, Eli Upfal
Cambridge University Press, 2017

[3]: Bitcoin and Cryptocurrency Technologies
Arvind Narayanan, Joseph Bonneau, Edward W. Felten, Andrew Miller, and Steven Goldfeder
Princeton University Press, 2016

(Una versione preliminare di questo libro e altro materiale collegato è liberamente scaricabili qui: http://bitcoinbook.cs.princeton.edu/)

Testi di supporto

[4] Algorithm Design
Jon Kleinberg, Eva Tardos
Addison Wesley, 2005

[5] Introduction to Algorithms
Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein
The MIT press, 2001

[6] Algorithms Illuminated. Part 4: Algorithms for NP-Hard Problems
Tim Rougharden
Soundlikeyourself Publishing, 2020

Altri riferimenti

[7] Algorithms Illuminated. Part 3: Greedy Algorithms and Dynamic Programming
Tim Rougharden
Soundlikeyourself Publishing, 2019

[8] Algorithms Illuminated. Part 1: The Basics
Tim Rougharden
Soundlikeyourself Publishing, 2017

[9] Bengt Aspvall, Michael F. Plass and Robert Endre Tarjan.
A linear-time algorithm for testing the truth of certain quantified Boolean formulas.
Information Processing Letters, 8(3):121--123, 1979.

Modalità d'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.

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.

Contatti

Francesco Pasquale
Dipartimento di Ingegneria dell'Impresa "M. Lucertini" - Università di Roma "Tor Vergata"
Via del Politecnico, 1 - 00133 Roma - Italy
Tel.: +39 06 7259 7803
pasquale@mat.uniroma2.it (OpenPGP: 0xBF979C2A)