Docente
|
RODOLA' EMANUELE
(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: albero della ricorsione, iterazione, sostituzione, 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 di interi (descrizione, implementazione e analisi): IntegerSort, BucketSort, RadixSort.
- Tipo di dato Dizionario. Alberi di ricerca binari. Alberi AVL.
- Tavole Hash.
- Grafi e loro rappresentazione. Algoritmi di visita (descrizione, implementazione e costo).
- Tecnica algoritmica 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.
Il materiale di studio viene fornito completamente sul sito di riferimento del corso.
Come materiale integrativo vengono suggeriti di volta in volta capitoli selezionati dai seguenti testi:
T.H. Cormen, C.Papadimitriou, U. Vazirani. Introduzione agli algoritmi
J. Kleinberg, E. Tardos Algorithm Design
S. Dasgupta, C. Papadimitriou, U. Vazirani Algorithms
C. Demetrescu, I. Finocchi, G.F. Italiano Algoritmi e strutture dati
|