Docente
|
PATRIZI FABIO
(programma)
Algoritmi e strutture dati: generalità ed esempi. Introduzione alla nozione di costo (tempo e spazio di memoria).
Notazioni asintotiche per le funzioni di costo e metodi di analisi (caso peggiore, medio, migliore).
Metodi di analisi di algoritmi ricorsivi: iterativo, sostituzione, relazione di ricorrenza, Master Theorem.
Tipi di dato astratto (pile, code, alberi) e loro implementazioni. Algoritmi di visita di un albero.
Algoritmi di ordinamento incrementali (descrizione, implementazione e analisi): SelectionSort, InsertionSort, BubbleSort, HeapSort, MergeSort, QuickSort. Lower bound sul costo dell'ordinamento per modello basato su confronti.
Algoritmi di ordinamento lineari (descrizione, implementazione e analisi): IntegerSort, BucketSort, RadixSort.
Tipo di dato Dizionario. Alberi di ricerca binari. Alberi AVL.
Tabelle di Hash.
Grafi e loro rappresentazione. Algoritmi di visita (descrizione, implementazione e costo).
Tecnica algoritmica golosa (greedy). Minimo albero ricoprente e rispettivo calcolo basato su algoritmo greedy. Algoritmi di Kruskal, di Prim e di Boruvka.
Cammini minimi su grafi e relativi algoritmi (descrizione, implementazione e analisi): calcolo delle distanze, algoritmo di Bellman e Ford, calcolo dei cammini minimi a sorgente singola su grafi aciclici, algoritmo di Dijkstra.
Esercizi su tutti gli argomenti in programma.
C. Demetrescu, I. Finocchi, G. F. Italiano: Algoritmi e strutture dati, McGraw-Hill, seconda edizione
|