SABRINA DE CAPITANI DI VIMERCATI | |
Contact Information | Short Biography | Publications | Curriculum (Pdf) | Teaching | Other Links | |
INSEGNAMENTI
Programma di Algoritmi e strutture dati
Obiettivo del Corso Il corso ha lo scopo di introdurre i concetti fondamentali riguardanti l'analisi ed il progetto di algoritmi e strutture dati e l'analisi della complessità computazionale degli algoritmi. Contenuti del Corso 1. Introduzione Nozione di problema e algoritmo. Analisi di algoritmi, complessità in spazio e tempo di algoritmi ricorsivi e non. Notazioni asintotiche. Calcolo dei tempi di esecuzione di un programma. 2. Tipi di dati astratti di base Liste, Stack, Code: definizione ed operazioni. Implementazione (array, puntatori) con esecuzione delle operazioni e vantaggi/svantaggi. 3. Alberi Concetto di albero e definizioni. Tecniche di attraversamento (inorder, preorder, postorder). Operazioni su ADT albero. Tecniche di rappresentazione. Alberi binari di ricerca: definizione, rappresentazione, operazioni. Alberi binari rosso neri: definizione, rappresentazione, operazioni. 4. Insiemi Definizione, operazioni e tecniche di rappresentazione. Dizionari: definizione e operazioni. Code di priorità: concetti, esempi di utilizzo e tecniche di rappresentazione. Heap: realizzazione e esecuzione delle operazioni. 5. Hashing Tavole ad indirizzamento diretto. Tavole hash. Funzioni hash. Indirizzamento aperto. 6. Tecniche avanzate di progettazione ed analisi. Programmazione dinamica. Algoritmi greedy. 7. Grafi Grafi orientati e non orientati: definizioni e concetti principali. Tecniche di rappresentazione. Cammino minimo in grafi pesati: problema e soluzioni. Algoritmi di visita in ampiezza (BFS) e profondità (DFS). Esempi di applicazioni della DFS: test di aciclicità, ordinamento topologico, ritrovamento di componenti fortemente connesse. Esempi di applicazioni della BFS: calcolo cammino minimo in grafi non pesati. Minimo albero ricoprente: problema e soluzioni. Punti di articolazione: definizione e ritrovamento. Graph matching. 8. Ordinamento Problema. Limite inferiore di complessità per gli algoritmi di ordinamento. Insertion sort, heapsort, quicksort, mergesort: descrizione ed analisi della complessità. 9. Gestione dei dati su memoria esterna Problemi. B-alberi: definizione, proprietà e vantaggi. Esecuzione delle operazioni di ricerca, inserimento e cancellazione. Operazioni di concatenazione e bilanciamento nella cancellazione. Operazioni di divisione e promozione nell'inserimento. Modalità di esame L'esame consiste in una prova scritta della durata di 2:30 ore circa. |