Tags:
create new tag
view all tags

Progettazione di Algoritmi a.a. 2016-2017

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]

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. 27. ]

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, 21, 23, 24. 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]

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]

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

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






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