PALGprogramma2014 < Algoritmi2

Tags: view all tags

---+ Progettazione di Algoritmi a.a. 2024-2025

<!--
<H2>Obiettivi</H2>
<DIV style="margin-left:5%; margin-right:10%">
<DIV ALIGN="justify">
<p>
Introdurre idee e tecniche che aiutano la progettazione e l'implementazione 
di software efficiente ed elegante. In particolare, tali idee e tecniche sono sfruttate in 
quelle parti di importanti sistemi software (sistemi operativi, compilatori/interpreti, 
DBMS, ecc.) che devono fornire elevate prestazioni. Enfasi è posta nella definizione 
e nella dimostrazione rigorosa delle proprietà dei concetti presentati (algoritmi e 
strutture dati). Il corso si sviluppa in base alle principali tecniche 
algoritmiche (Greedy, Divide et Impera, Programmazione Dinamica e Backtracking) che sono 
esemplificate tramite numerosi esempi.
</p>
</DIV>
</DIV>
-->
---++ Programma

<div style="margin-left: 5%; margin-right: 10%;"> <div align="justify">

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]

---+++ *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]

</div>
---+++ 
</div>

---++ Testi consigliati

<span style="background-color: transparent;">1) S. Dasgupta, C. Papadimitriou, U. Vazirani </span> _Algorithms_ <span style="background-color: transparent;">. Disponibile anche [[http://algorithmics.lsi.upc.edu/docs/Dasgupta-Papadimitriou-Vazirani.pdf][online]].</span>

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_ MacGraw -Hill 2010

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

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

6) P. Crescenzi, G. Gambosi, R. Grossi, G. Rossi _Strutture di dati e algoritmi._ Pearson 2012
<div style="margin-left: 5%; margin-right: 10%;"> </div>