Docente

Prof. Carla Piazza carla.piazza@uniud.it

Crediti

12 CFU

Finalità

Il corso si propone di introdurre ai fondamenti della teoria degli algoritmi, delle strutture dati e all’analisi della complessità computazionale di programmi. Il principale obiettivo del corso è familiarizzare lo studente con le principali problematiche e tecniche relative al disegno e alla progettazione di algoritmi. Ci si propone inoltre di introdurre i metodi di base utilizzati per stabilire la complessità di programmi e i criteri utilizzati per scegliere e progettare strutture dati.
Dopo aver superato l’esame si ritiene che lo studente sia in grado di risolvere algoritmicamente problemi classici e scegliere motivatamente le strutture dati adatte ad ottenere soluzioni computazionalmente efficienti. Sia in grado di porre limiti superiori sufficientemente precisi e indipendenti dall’architettura alla complessità computazionale di programmi di media difficoltà. Conosca i più importanti problemi e algoritmi “classici” del campo nonché le più importanti e utilizzate tecniche di analisi della complessità e di strutturazione dei dati.

Programma

1. Introduzione e nozioni preliminari
Introduzione. Elementi di logica e teoria degli insiemi. Alberi e grafi. Matematica discreta e analisi asintotica. Modelli di calcolo per la determinazione della complessità degli algoritmi. Problemi ricorsivi e aspetti algoritmici.

2. Algoritmi di ricerca e ordinamento
Algorimi primitivi di ordinamento e ricerca: selection-sort, insertion-sort, bubble-sort, heap-sort. Algoritmi ricorsivi: quick-sort, merge-sort. Analisi della complessità e limiti inferiori. Algoritmi lineari non basati sul confronto: counting-sort, radix-sort, bucket-sort. Determinazione dell'elemento medio.

3. Strutture dati 
Strutture dati primitive: liste, pile, code, heap. Algoritmi e strutture dati per la gestione e manipolazione di insiemi: tabelle hash, alberi di ricerca, bilanciamento, red-black alberi e B-alberi. Algoritmi e strutture dati per il problema Union-Find. Cenni alle strutture dati self-adjusting.

4. Algoritmi sui grafi
Tecniche di rappresentazione di grafi orientati e e non orientati. Algoritmi di visita in ampiezza e profondità. Algoritmi di visita su alberi. Calcolo delle componenti fortemente connesse. Algoritmi per la determinazione di topological-sort, minimum spanning tree (Prim e Kruskal), cammino minimo da una sorgente (Dijkstra, Bellmann-Ford) cammini minimi da sorgenti multiple (Floyd-Warshall, Johnson).

Bibliografia

Testi utilizzati:
Appunti delle lezioni; 
Cormen T.H., Leiserson C.E., Rivest R.L Introduction to Algorithms MIT Press, 1990 (anche in italiano).

Altri testi utili:
Aho A.V., Hopcroft J.E., Ullman J.D. Data Structures and Algorithms Addison-Wesley, 1983. 
Aho A.V., Hopcroft J.E., Ullman J.D. The Design and Analysis of Computer Algorithms Addison-Wesley, 1974.
D. E. Knuth Selected Papers in Computer Science Cambridge University Press, 1996.
Tarjan R.E. Data Structures and Network Algorithms SIAM, 1983.