Progettazione di Algoritmi a.a. 2021-2022 (canale 1)

Docente: Massimo Lauria (https://massimolauria.net/)

Esercitatore: Matteo Cinelli

Informazioni sugli esami e sul programma di esame

Appelli

• Giugno: 14/6/2022 - Ore 14.00 (Aula I, edificio CU32 V.Caglioti)
• Luglio: 12/7/2022 - Ore 14:00 (Aula Cabibbo, edificio CU33 E.Fermi)
• Settembre: 13/9/2022 - Ore 14:00 (Aula T1, CU045-E01PTEL001)
  • Traccia: Appello3_Settembre2022_Traccia.pdf
  • Soluzione: Appello3_Settembre2022_Soluzione.pdf
  • Voti: Appello3_Settembre2022_Voti.pdf
• Sessione straordinaria di Ottobre: 21/10/2023 - Ore 14:00 (Aula Cabibbo, edificio CU33 E.Fermi)
  • Traccia: AppelloStraordinario_Ottobre2022_Traccia.pdf
  • Soluzione: AppelloStraordinario_Ottobre2022_Soluzione.pdf
  • Voti: AppelloStraordinario_Ottobre2022_Voti.pdf
• Gennaio: 24/1/2023 - Ore 14:00 (Aula T1, CU045-E01PTEL001)
  • Traccia: Appello4_Gennaio2023_Traccia.pdf (la scritta "Canale 2" è errata)
  • Soluzione: Appello4_Gennaio2023_Soluzione.pdf
  • Voti: Appello4_Gennaio2023_Voti.pdf
• Febbraio: 9/2/2023 - Ore 14:00 (Aula T1, CU045-E01PTEL001)
  • Traccia: Appello5_Febbraio2023_Traccia.pdf
  • Soluzione: Appello5_Febbraio2023_Soluzione.pdf
  • Voti: Appello5_Febbraio2023_Voti.pdf

• Sessione straordinaria di Marzo: 21/3/2023

  • Traccia: Appello5s_Marzo2023_Traccia.pdf

  • Soluzione: Appello5s_Marzo2023_Soluzione.pdf
  • Voti: Appello5s_Marzo2023_Voti.pdf

Modalità d'esame: l'esame è costituito da una singola prova scritta che dura circa due ore. Il docente ha la facoltà di richiedere un orale di chiarimenti in casi eccezionali.

La prova scritta è fatta da 3-4 esercizi che possono richiedere

• l'applicazione di definizioni e di algoritmi noti a degli input dati;
• la richiesta di progettare algoritmi con tecniche note (e.g. greedy, backtracking, programmazione dinamica) per risolvere un dato problema nuovo, spiegando bene il loro funzionamento e la loro complessità computazionale;
• la modifica di algoritmi noti per risolvere variazioni di problemi visti e risolti a lezione.

Le descrizioni, le spiegazioni degli algoritmi e della loro complessità devono essere chiare, precise e puntuali. Scrivere tanto non vuol dire cose corrette.

Programma d'esame

Indichiamo il programma del corso con tutto il materiale didattico incluso. Nella programma dettagliato lo stesso elemento potrebbe essere
indicato o elencato più volte. Qualunque cosa sia indicata come inclusa nel riassunto ma non sia presente nella lista dettagliata è comunque inclusa nel programma (fatemi sapere se ne manca qualcosa, in ogni caso).

Di tutti gli algoritmi visti a lezione, è necessario essere in grado di dimostrarne la correttezza e la complessità computazionale.

Programma di esame dettagliato: scarica il documento

Riassunto del programma di esame: Il programma di esame include tutto il materiale delle dispense
e dei documenti allegati i questa pagina. Include oltrettutto:

• tutti gli esercizi presentati nelle dispense (risolti o non risolti nelle stesse);
• tutte le sezioni del libro di testo indicate nelle dispense;
• tutti gli esercizi del libro indicati nelle dispense;
• tutti gli esercizi svolti alle esercitazioni.

T.H. Cormen, C.E. Leiserson, R.L. Rivest, C. Stein
Introduzione agli algoritmi e strutture dati 3/ed
McGraw Hill 2010

Diario delle lezioni e delle esercitazioni

Il corso prevede 36 lezioni, 24 di teoria e 12 di esercitazione. Dovremmo potercela fare entro 13 settimane, anche considerando eventuali feste nazionali, occasionali indisponibilità del docente, o altri eventi imprevisti. Il diario seguente copre tutto il periodo della didattica del semestre, dal 21 Febbraio al 27 Maggio. Tuttavia è molto probabile che il corso termini prima del 27 Maggio.

L'orario di ricevimento è Giovedì 11:00-13:00, ma il ricevimento dovrà essere concordato via email e può essere in presenza oppure online a seconda delle esigenze del caso.

La pagina web del docente con tutti i suoi contatti è:

Esiste un gruppo di discussione del corso che conterrà avvisi, informazioni, e che può essere usato anche tra voi per discutere e confrontarvi. Dovrebbe essere automaticamente accessibile a chi si iscrive con l'indirizzo email della sapienza ...@studenti.uniroma1.it

Gruppo di discusisone: https://groups.google.com/a/uniroma1.it/g/progettazione_algoritmi2022_canale1

Lezione remota: link zoom (accessibile solo a studenti sapienza, le lezioni non saranno registrate)

Settimana 01 - 21 Febbraio

21 Febbraio 2022 (Lunedì): Presentazione del corso

Introduzione al pensiero computazionale, e alla definizione di algoritmo. L'interesse per lo studio della correttezza e dell'efficienza degli algoritmi.

Abbiamo dato le informazioni di base riguardo i libri di testo, la modalità di esame e i contenuti del corso.

Come caso di studio abbiamo visto il problema della moltiplicazione di due matrice quadrate, e abbiamo discusso l'algoritmo standard e l'algoritmo di Strassen (vedi sezione 4.2 del libro di testo).

24 Febbraio 2022 (Giovedì): SAT, complessità dei problemi e intrattabilità

Vediamo un altro caso di studio, il problema della soddisfacibilità delle formule CNF (vedi allegato alla lezione)

Discutiamo poi altri preliminari come le notazioni asintotiche, la complessità degli algoritmi e dei problemi. In questo contesto vediamo i pochi metodi noti per dimostrare che un problema non può avere algoritmi di una certa complessità. Questo ci porta a discutere d'intrattabilità, e a menzionare la testi di Church-Turing (standard ed estesa). Precisiamo poi il modello di calcolo che usiamo per valutare la complessità degli algoritmi.

25 Febbraio 2022 (Venerdì): Grafi, la loro rappresentazione e l'algoritmo BFS (visita in ampiezza)

Introduciamo nozioni standard sui grafi (vedi Appendici B.4 e B.5 sul libro di testo) e discutiamo di come possano essere rappresentati i grafi in modo da poter essere elaborati in algoritmi (capitolo 22.1 del libro di testo).

Discutiamo poi la visita di grafi (semplici o diretti) per ampiezza (vedi capitolo 22.2 del libro di testo e allegati alla lezione)

Settimana 02 - 28 Febbraio

28 Febbraio 2022 (Lunedì): Esercitazione

3 Marzo 2022 (Giovedì): Complessità e Correttezza della BFS, descrizione di DFS

Completiamo la discussione sulla BFS, analizzando la complessità e dimostrando la correttezza dell'algoritmo. Introduciamo poi un altro algoritmo di visita, quello della visita in profondità.

4 Marzo 2022 (Venerdì): Complessità e Caratteristiche della DFS, ordinamento topologico

Riprendiamo la discussione della DFS (visita in profondità). Dimostriamo che la complessità è O(|V|+|E|), e poi dimostriamo alcune importanti proprietà (ad esempio il Teorema delle Parentesi e il Teorema del Cammino Bianco). Discutiamo la classificazione degli archi del grafo in base all'esito della DFS. Vediamo che la DFS può verificare la presenza di cicli in un grafo orientato e, nel caso di grafi aciclici, può calcolarne un ordinamento topologico.

Settimana 03 - 7 Marzo

7 Marzo 2022 (Lunedì): Esercitazione

10 Marzo 2022 (Giovedì): Applicazione della DFS, ordinamento topologico di grafi aciclici

Introduciamo i grafi aciclici e discutiamo un algoritmo per calcolare l'ordinamento topologico di questi grafi, utilizzando la DFS.

11 Marzo 2022 (Venerdì):Applicazione della DFS, calcolo delle componenti fortemente connesse

Introduzione del concetto di componente fortemente connessa. Discutiamo un algoritmo che calcola le componenti fortemente connesse di un grafo orientato. L'algoritmo è basato su DFS.

Settimana 04 - 14 Marzo

14 Marzo 2022 (Lunedì): Esercitazione

17 Marzo 2022 (Giovedì): Lezione cancellata

18 Marzo 2022 (Venerdì): Lezione cancellata

Settimana 05 - 21 Marzo

21 Marzo 2022 (Lunedì): Esercitazione

24 Marzo 2022 (Giovedì): Introduzione agli algoritmi greedy, ed al problema dell'albero di copertura minimo.

Introduciamo gli algoritmi Greedy, utilizzando come caso di studio il problema di Selezione di Attività. Le soluzioni ottime del problema hanno una sottostruttura ottima che discutiamo con attenzione, per poi far vedere che una strategia di algoritmo greedy è sufficiente per risolvere il problema. Introduciamo il problema dell'albero di copertura minimo.

25 Marzo 2022 (Venerdì): Alberi di copertura minimi. Il teorema del Taglio. Algoritmo di Kruskal.

Introduciamo gli alberi di copertura di un grafo non orientato. Nel caso di grafi pesati (ogni arco ha un valore numerico di peso) possiamo cercare un albero di costo minimo. Per farlo possiamo adottare delle strategie Greedy, realizzate ad esempio dagli algoritmi di Kruskal e Prim. La correttezza di entrambi gli algoritmi è basata sul Teorema del Taglio. Cominciamo poi la descrizione dell'algoritmo di Kruskal.

Settimana 06 - 28 Marzo

28 Marzo 2022 (Lunedì): Esercitazione

31 Marzo 2022 (Giovedì): Union-Find, gestione delle componenti connesse nell'algoritmo di Kruskal

Completiamo la trattazione dell'algoritmo di Kruskal discutendo la gestione delle componenti connesse in modo efficiente. Per farlo vediamo una struttura dati per la gestione di insiemi disgiunti, detta Union-Find.

1 Aprile 2022 (Venerdì): Algoritmo di Prim e Code di Priorità

Vediamo i dettagli dell'algoritmo di Prim per il calcolo di alberi di copertura minimi. Una componente importante dell'algoritmo è la struttura dati per la gestione delle code di priorità, che discutiamo.

Settimana 07 - 4 Aprile

4 Aprile 2022 (Lunedì): Esercitazione

7 Aprile 2022 (Giovedì): Cammini minimi in un grafo orientato pesato. Algoritmo di Dijkstra

Descriviamo il problema di trovare i cammini minimi in un grafo. Le varie tipologie (sorgente singola o multipla, destinazione singola o multipla). Poi descriviamo l'algoritmo di Dijkstra mettendolo in relazione con la BFS, e con l'algoritmo di Prim. Ne dimostriamo la correttezza per grafi orientati pesati con pesi non negativi.

8 Aprile 2022 (Venerdì): Cammini minimi con pesi negativi. DAG e Bellman-Ford

Consideriamo il caso di grafi pesati con archi di peso negativo. Questo comporta il problema dei cicli negativi. Vediamo un algoritmo per il calcolo dei cammini minimi in un DAG, che quindi non ha cicli negativi. In generale trattiamo diverse proprietà degli algoritmi basati sul rilassamento di archi.

Settimana 08 - 11 Aprile

11 Aprile 2022 (Lunedì): Esercitazione

14 Aprile 2022 (Giovedì): Nessuna lezione, vacanze pasquali

15 Aprile 2022 (Venerdì): Nessuna lezione, vacanze pasquali

Settimana 09 - 18 Aprile

18 Aprile 2022 (Lunedì): Nessuna lezione

21 Aprile 2022 (Giovedì): Cammini minimi Bellman-Ford e Floyd-Warshall

Discutiamo l'algoritmo di Bellman-Ford che riconosce la presenza di cicli negativi. Vediamo poi un altro algoritmo che calcola i cammini minimi tra tutte le coppie di vertici di un grafo, l'algoritmo di Flyod-Warshall.

22 Aprile 2022 (Venerdì): Esercizi sugli algoritmi Greedy

Facciamo un po' di esercizi sugli algoritmi Greedy.

Settimana 10 - 25 Aprile

25 Aprile 2022 (Lunedì): Nessuna lezione

28 Aprile 2022 (Giovedì): Algoritmi di Approssimazione - Vertex Cover

Ci sono problemi per cui calcolare la soluzione ottima è intrattabile. In questi casi si può optare per degli algoritmi che si avvicinino alla soluzione ottima entro una soglia nota a priori. Definiamo cos'è il fattore di approssimazione di un algoritmo. Vedremo il caso di studio di Vertex Cover per il quale l'algoritmo greedy banale non garantisce una buona approssimazione, e poi vedremo un algoritmi che garantisce un fattore di approssimazione 2.

29 Aprile 2022 (Venerdì): Algoritmi di Approssimazione - Set Cover

Consideriamo il problema del set cover, che è una versione più generale del vertex cover. E vediamo un algoritmo di approssimazione che garantisce O(log n).

Settimana 11 - 2 Maggio

2 Maggio 2022 (Lunedì): Esercitazione

5 Maggio 2022 (Giovedì): Divide et Impera

Discutiamo la tecnica, probabilmente già nota, del Divide et Impera: la tecnica di soluzione dei problemi basata sulla divisione degli stessi in sottoproblemi indipendenti che possono essere risolti separatamente. Poi la soluzione completa viene ottenuta dalla combinazione delle sotto-soluzioni. Vediamo come caso di studio il problema del sottovettore di somma massima. Vediamo algoritmi via via sempre più efficienti fino ad arrivare ad uno ottimo di complessità O(n). Concludiamo affrontando degli esercizi.

6 Maggio 2022 (Venerdì): Algoritmi per la selezione

Il problema della selezione consiste nel cercare in una sequenza di valori distinti, non necessariamente ordinati, quello che nella sequenza ha esattamente k elementi minori o uguali a lui. Vediamo prima un algoritmo randomizzato di complessità O(n) basato su tecniche simili a quelle del quicksort. Poi vediamo un algoritmo deterministico che ha asintoticamente la stessa complessità, anche se in pratica è meno veloce.

Settimana 12 - 9 Maggio

9 Maggio 2022 (Lunedì): Esercitazione

12 Maggio 2022 (Giovedì): Programmazione dinamica (1)

Vediamo il problema del tagli del bastone, usato come esempio introduttivo alla programmazione dinamica. Illustriamo poi formalmente le fasi della programmazione dinamica e vediamo un esempio di applicazione al problema della parentesizzazione ottima. Rivediamo gli algoritmi di Bellman-Ford e di Floyd-Warshall dal pundo di vista dello schema della programmazione dinamica.

13 Maggio 2022 (Venerdì): Programmazione dinamica (2)

DIscutiamo più precisamente la memoizzazione e vediamo esempi di applicazione. Poi introduciamo tecniche di programmazione dinamica su problemi per stringhe, come LCS e edit distance.

Settimana 13 - 16 Maggio

16 Maggio 2022 (Lunedì): Programmazione dinamica (3)

Completiamo la trattazione dell'edit distance e poi iniziamo a fare vari esercizi riguardo la programmazione dinamica. (video della lezione)

19 Maggio 2022 (Giovedì): Ricerca esaustiva e backtracking (1)

Cominciamo con la trattazione del backtracking. La generazione di insiemi di stringhe binarie con vincoli che richiedono il taglio dell'albero di ricerca. Ampliamo ad esempi che riguardano matrici binarie. Vediamo come usare il backtracking per risolvere problemi NP-completi: 3-coloring e il problema dello zaino.

20 Maggio 2022 (Venerdì): Esercitazione

Settimana 14 - 23 Maggio

23 Maggio 2022 (Lunedì): Esercitazione

26 Maggio 2022 (Giovedì): Ricerca esaustiva e backtracking (2)

Proseguiamo con la trattazione del problema dello zaino. Poi consideriamo la generazione di permutazioni. Vediamo variazioni di questo generatore, e in particolare vediamo una strategia basata su backtraking per il problema di trovare un ciclo Hamiltoniano in un grafo, e per il problema delle regine. Proponiamo come esercizio aperto la scrittura di un solutore per il sudoku.

27 Maggio 2022 (Venerdì): Conclusione del corso