Tags:
create new tag
view all tags

Progettazione di Algoritmi a.a. 2021-2022

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)

Le prenotazioni di un appello si apriranno solo dopo il termine dell'appello precedente.

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.
Libro di testo:

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 - Canale I (Lauria)

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

Esercitatore: Matteo Cinelli

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



Topic attachments
I Attachment History Action Size Date Who Comment
PDFpdf 000_ProgrammaEsameDettagliato.pdf r2 r1 manage 50.1 K 2022-05-25 - 13:31 MassimoLauria  
PDFpdf 001_Introduzione.pdf r1 manage 483.1 K 2022-03-02 - 12:12 MassimoLauria  
PDFpdf 002_Strassen.pdf r1 manage 799.2 K 2022-03-02 - 12:12 MassimoLauria  
PDFpdf 003_SAT.pdf r1 manage 719.1 K 2022-03-02 - 12:12 MassimoLauria  
JPEGjpg 004_Complessit_dei_Problemi.jpg r1 manage 1875.8 K 2022-03-02 - 12:13 MassimoLauria  
PDFpdf 005_BFS.pdf r1 manage 2928.1 K 2022-03-02 - 12:12 MassimoLauria  
PDFpdf 006_ExampleBFS1.pdf r1 manage 170.3 K 2022-03-02 - 12:12 MassimoLauria  
PDFpdf 007_ExampleBFS2.pdf r1 manage 148.2 K 2022-03-02 - 12:12 MassimoLauria  
PDFpdf 008_ExampleBFS3.pdf r1 manage 150.9 K 2022-03-02 - 12:12 MassimoLauria  
PDFpdf 009_Esercizi_2022.02.28.pdf r1 manage 2196.6 K 2022-03-02 - 12:12 MassimoLauria  
PDFpdf 010_DFS.pdf r3 r2 r1 manage 3302.5 K 2022-03-10 - 18:09 MassimoLauria  
PDFpdf 011_ExampleDFS1.pdf r1 manage 139.9 K 2022-03-02 - 12:13 MassimoLauria  
PDFpdf 012_ExampleDFS2.pdf r1 manage 214.1 K 2022-03-02 - 12:13 MassimoLauria  
PDFpdf 013_TSORT.pdf r2 r1 manage 1919.0 K 2022-03-10 - 18:09 MassimoLauria  
PDFpdf 014_ExampleTSORT.pdf r1 manage 359.2 K 2022-03-03 - 23:15 MassimoLauria  
PDFpdf 015_Esercizi_2022.03.07.pdf r1 manage 1687.2 K 2022-03-07 - 15:56 MassimoLauria  
PDFpdf 016_SCOMP.pdf r3 r2 r1 manage 3468.6 K 2022-03-11 - 15:41 MassimoLauria  
PDFpdf 017_ExampleSCOMP.pdf r1 manage 257.1 K 2022-03-07 - 20:23 MassimoLauria  
PDFpdf 018_Lavagna_2022.03.10.pdf r1 manage 3141.8 K 2022-03-10 - 18:09 MassimoLauria  
PDFpdf 019_Lavagna_2022.03.11.pdf r1 manage 1194.6 K 2022-03-11 - 15:46 MassimoLauria  
PDFpdf 020_Esercizi_2022.03.14.pdf r1 manage 2316.8 K 2022-03-14 - 17:16 MassimoLauria  
PDFpdf 021_GREEDY.pdf r1 manage 2593.0 K 2022-03-14 - 23:01 MassimoLauria  
PDFpdf 022_SPTREE.pdf r1 manage 3282.3 K 2022-03-14 - 23:01 MassimoLauria  
PDFpdf 023_KRUSKAL.pdf r1 manage 2055.0 K 2022-03-14 - 23:01 MassimoLauria  
PDFpdf 024_ExampleKRUSKAL.pdf r1 manage 240.7 K 2022-03-14 - 23:01 MassimoLauria  
PDFpdf 025_Esercizi_2022.03.21.pdf r1 manage 1512.8 K 2022-03-22 - 14:49 MassimoLauria  
PDFpdf 026_Esercizi_2022.03.28.pdf r1 manage 3413.5 K 2022-03-30 - 15:47 MassimoLauria  
PDFpdf 027_UNIONFIND.pdf r2 r1 manage 3994.5 K 2022-04-01 - 18:06 MassimoLauria  
PDFpdf 028_PRIM_PQUEUE.pdf r2 r1 manage 3883.1 K 2022-04-01 - 18:06 MassimoLauria  
PDFpdf 029_ExamplePRIM.pdf r2 r1 manage 165.5 K 2022-04-01 - 18:06 MassimoLauria  
PDFpdf 030_ExampleUNIONFIND1.pdf r1 manage 146.2 K 2022-03-27 - 10:30 MassimoLauria  
PDFpdf 031_ExampleUNIONFIND2.pdf r1 manage 162.9 K 2022-03-27 - 10:30 MassimoLauria  
PDFpdf 032_Esercizi_2022.04.04.pdf r1 manage 3506.8 K 2022-04-04 - 21:35 MassimoLauria  
PDFpdf 033_CAMMINIMINIMI.pdf r1 manage 5035.7 K 2022-04-04 - 21:35 MassimoLauria  
PDFpdf 034_CAMMININEGATIVI.pdf r2 r1 manage 2816.6 K 2022-04-21 - 17:49 MassimoLauria  
PDFpdf 035_ExampleDijkstra1.pdf r1 manage 139.5 K 2022-04-04 - 21:35 MassimoLauria  
PDFpdf 036_ExampleDijkstra2.pdf r1 manage 139.5 K 2022-04-04 - 21:35 MassimoLauria  
PDFpdf 037_ExampleSPDAG.pdf r1 manage 147.3 K 2022-04-04 - 21:35 MassimoLauria  
PDFpdf 038_ExampleBF.pdf r1 manage 176.8 K 2022-04-04 - 21:35 MassimoLauria  
PDFpdf 039_ESERCIZIGREEDY.pdf r1 manage 1578.6 K 2022-04-06 - 11:58 MassimoLauria  
PDFpdf 040_ExampleRELAX.pdf r1 manage 198.0 K 2022-04-07 - 17:41 MassimoLauria  
PDFpdf 041_Esercizi_2022.04.11.pdf r1 manage 6099.4 K 2022-04-12 - 15:02 MassimoLauria  
PDFpdf 042_FLOYDWARSHALL.pdf r1 manage 2558.3 K 2022-04-19 - 18:49 MassimoLauria  
PDFpdf 043_ExampleFW.pdf r1 manage 240.4 K 2022-04-19 - 18:49 MassimoLauria  
PDFpdf 044_APPROX.pdf r3 r2 r1 manage 5234.0 K 2022-04-28 - 18:33 MassimoLauria  
PDFpdf 045_SETCOVER.pdf r2 r1 manage 3457.0 K 2022-04-28 - 18:33 MassimoLauria  
PDFpdf 046_ExampleVC1.pdf r1 manage 94.5 K 2022-04-24 - 19:06 MassimoLauria  
PDFpdf 047_ExampleVC2.pdf r1 manage 99.5 K 2022-04-24 - 19:06 MassimoLauria  
PDFpdf 048_ExampleVC3.pdf r1 manage 100.1 K 2022-04-24 - 19:06 MassimoLauria  
PDFpdf 049_ExampleVC4.pdf r1 manage 96.3 K 2022-04-24 - 19:06 MassimoLauria  
PDFpdf 050_Esercizi_2022.05.02.pdf r1 manage 3902.9 K 2022-05-03 - 13:35 MassimoLauria  
PDFpdf 051_DIVIDEETIMPERA.pdf r1 manage 4706.9 K 2022-05-02 - 15:35 MassimoLauria  
PDFpdf 052_SELECTION.pdf r1 manage 2101.0 K 2022-05-02 - 15:35 MassimoLauria  
PDFpdf 053_Esercizi_2022.05.09.pdf r1 manage 5157.2 K 2022-05-09 - 17:03 MassimoLauria  
PDFpdf 054_PD1.pdf r1 manage 5325.7 K 2022-05-09 - 17:09 MassimoLauria  
PDFpdf 055_PD2.pdf r1 manage 3951.3 K 2022-05-09 - 17:09 MassimoLauria  
PDFpdf 056_PD3.pdf r1 manage 4376.0 K 2022-05-12 - 17:13 MassimoLauria  
PDFpdf 057_PD4.pdf r1 manage 2265.0 K 2022-05-12 - 17:13 MassimoLauria  
PDFpdf 058_BT1.pdf r2 r1 manage 3622.0 K 2022-05-27 - 17:47 MassimoLauria  
PDFpdf 059_BT2HARD.pdf r2 r1 manage 3642.4 K 2022-05-27 - 17:47 MassimoLauria  
PDFpdf 060_BT3PERM.pdf r2 r1 manage 4936.7 K 2022-05-27 - 17:47 MassimoLauria  
PDFpdf 061_Esercizi_2022.05.22.pdf r1 manage 5290.0 K 2022-05-24 - 08:45 MassimoLauria  
PDFpdf 062_Esercizi_2022.05.23.pdf r1 manage 4440.9 K 2022-05-24 - 08:45 MassimoLauria  
Edit | Attach | Watch | Print version | History: r106 < r105 < r104 < r103 < r102 | Backlinks | Raw View | Raw edit | More topic actions
Topic revision: r106 - 2022-05-27 - MassimoLauria






 
Questo sito usa cookies, usandolo ne accettate la presenza. (CookiePolicy)
Torna al Dipartimento di Informatica
This site is powered by the TWiki collaboration platform Powered by PerlCopyright © 2008-2022 by the contributing authors. All material on this collaboration platform is the property of the contributing authors.
Ideas, requests, problems regarding TWiki? Send feedback