Tags:
create new tag
view all tags

Progettazione di Algoritmi a.a. 2017-2018

Programma

Per ogni algoritmo nel programma Ŕ data una dimostrazione di correttezza e valutata la complessitÓ di possibili implementazioni. Alla fine di ogni argomento sono elencati i testi consigliati in ordine di rilevanza. Gli appunti saranno pubblicati durante lo svolgimento del corso.

Grafi

Rappresentazione tramite matrici di adiacenza e liste di adiacenza. Visite in ampiezza (BFS) e in profonditÓ (DFS). Albero di visita e classificazione degli archi di una visita. Componenti connesse e fortemente connesse, algoritmo di Tarjan. Ordinamento topologico. Distanze in un grafo.

[Appunti del corso. Testo 1: Cap. 3, 4. Testo 3: Cap. 22, 23. Testo 5: Cap. 11. Testo 6: Cap.7]

Reti di flusso

Il problema della ricerca del flusso massimo. L'algoritmo greedy e l'algoritmo di Ford-Fulkerson (correttezza e complessiÓ). Il teorema del massimo flusso-minimo taglio. Esempi di applicazioni del massimo flusso: abbinamento massimo, cammini arco disgiunti su grafi, il grado di connettivitÓ di un grafo. (DFS).

[Appunti del corso. Testo 3: Cap. 26. ]

Greedy

Descrizione della tecnica e schema generale per dimostrare la correttezza di un algoritmo Greedy. Algoritmi per Selezione AttivitÓ. Cammini minimi in grafi pesati: algoritmo di Dijkstra. Minimo albero di copertura: algoritmi di Prim e di Kruskal, strutture dati per insiemi disgiunti. Algoritmi di approssimazione e quantificazione dell'errore. Il problema del ricoprimento tramite nodi (Vertex Cover). Codici di Huffman.

[Appunti del corso. Testo 1: Cap. 4, 5. Testo 3: Cap. 16, 23, 24, 25. Testo 4: Cap. 4, 11]

Divide et Impera

Descrizione della tecnica. Il problema del massimo sottovettore. Algoritmo per la ricerca della coppia di punti pi¨ vicini (Closest Pair). Il problema della mediana.

[Appunti del corso. Testo 1: Cap. 2. Testo 4: Cap. 5. Testo 5: Cap. 5, 10. Testo 6: Cap. 3]

Programmazione Dinamica

Descrizione della tecnica e confronto con Divide et Impera. Ricerca esaustiva e memoizzazione. Dal calcolo del valore ottimo al trovare una soluzione ottima. Il problema dello Zaino (Knapsack). Cammino pi¨ lungo in grafi aciclici (Longest Path in DAG). Pianificazione AttivitÓ (CPM). Sistemi con vincoli di differenza e cammini minimi in grafi con pesi anche negativi. Algoritmi di Bellman-Ford e di Floyd-Warshall. Il problema della massima sottosequenza comune (LCS). Distanza tra stringhe (Edit Distance). Prodotto di una sequenza di matrici (Matrix Chaining).

[Appunti del corso. Testo 1: Cap. 6. Testo 2: Cap. 5. Testo 3: Cap. 15, 24, 25. Testo 4: Cap. 6. Testo 5: Cap. 10. Testo 6: Cap. 6]

Backtracking

Descrizione della tecnica. Enumerazione di strutture semplici: sottoinsiemi, sequenze, permutazioni. Esplorazione dello spazio di ricerca, ovvero generazione delle possibili soluzioni di un problema: 3-colorazione, ciclo Hamiltoniano. Euristiche di taglio: Zaino.

[Appunti del corso. Test 1: Cap. 9. Testo 2: Cap. 7]

Testi consigliati

1) S. Dasgupta, C. Papadimitriou, U. Vazirani Algorithms . Disponibile online su github.

2) E. Horowitz, S. Sahni Fundamentals of Computer Algorithms Computer Science Press.

3) T.H. Cormen, C.E. Leiserson, R.L. Rivest, C. Stein Introduzione agli algoritmi e strutture dati</a> MacGraw -Hill 2010

4) J. Kleimberg, E. Tardos Algorithm Design Addison Wesley, 2005

5) C. Demetrescu, I. Finocchi, G.F. Italiano Algoritmi e Strutture di Dati. MacGraw-Hill 2010

6) P. Crescenzi, G. Gambosi, R. Grossi, G. Rossi Strutture di dati e algoritmi. Pearson 2012

Edit | Attach | Watch | Print version | History: r6 < r5 < r4 < r3 < r2 | Backlinks | Raw View | Raw edit | More topic actions
Topic revision: r6 - 2018-02-22 - AngeloMonti






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