Docente

• Prof. Carla Piazza

Indirizzo e-mail

carla.piazza@uniud.it

Indirizzo Pagina Web Personale

http://www.dimi.uniud.it/piazza

Crediti

12 CFU

Finalità e obbiettivi formativi

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 e' 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

Algoritmi 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.

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).

Prerequisiti

E’ utile che lo studente abbia buona padronanza con i contenuti dei corsi del I anno del corso di Laurea Triennale in Informatica/Tecnologie Web e Multimediali, con particolare riferimento ai corsi di Matematica Discreta, Analisi Matematica, Programmazione, Architettura degli Elaboratori.

Bibliografia

1.     Cormen T.H., Leiserson C.E., Rivest R.L, Stein C., Introduction to Algorithms, MIT Press, Third edition, 2009.

2.     Altri testi utili/Further useful textbooks:

1.     A. Bertossi, A. Montresor. Algoritmi e Strutture Dati, 2/ed, Città Studi Edizioni, 2010.

2.     C. Demetrescu, I. Finocchi, G. F. Italiano, Algoritmi e Strutture Dati, 2/ed, McGraw-Hill, 2007.

3.     P. Crescenzi, G. Gambosi, R. Grossi. Strutture di Dati e Algoritmi, Addison-Wesley Pearson, 2006.

4.     Aho A.V., Hopcroft J.E., Ullman J.D., Data Structures and Algorithms, Addison-Wesley, 1983.

5.     Aho A.V., Hopcroft J.E., Ullman J.D., The Design and Analysis of Computer Algorithms, Addison-Wesley, 1974.

Modalità d'esame

L’esame consta di una parte scritta e una orale.