Algoritmi e strutture dati
Docente
Sabrina De Capitani di Vimercati
Crediti
12 cfu
Anno: II
Quadr: I
Programma
- Introduzione. Algoritmi e rappresentazione dei dati. Tempo di calcolo. Complessità computazionale. Strutture Dati Elementari e rappresentazione in memoria.
- Strutture di tipo lineare. Specifica e realizzazione di liste, pile e code.
- Strutture di tipo ad albero. Alberi: algoritmi di visita, realizzazioni. Heap ed HeapSort.
- Strutture di tipo reticolare. Grafi: specifica, realizzazioni, algoritmi di visita, componenti connesse.
- Strutture di tipo insieme. Insiemi: specifica e realizzazione, Mfset. Dizionari: specifica e realizzazioni, tabelle hash. Alberi bilanciati di Ricerca.
- Complessità di algoritmi. Relazioni per la complessità di algoritmi ricorsivi.
- Impatto delle strutture dati sulla complessità di un algoritmo. Il problema dei cammini minimi. Schema generale di algoritmo basato sul teorema di Bellman. Algoritmi: Dijkstra, Johnson, Bellman-Ford-Moore, con pila ed Pape-D’Esopo.
- Divide et impera. Descrizione del paradigma. Esempi: Mergesort, Quicksort.
- Backtrack. Descrizione del paradigma. Esempio: String matching.
- Programmazione Dinamica. Descrizione del paradigma. Esempio: String matching approssimato.
- Greedy. Descrizione del paradigma. Esempi: Minimo Albero di Copertura, Scheduling di Programmi.
- Non determinismo ed enumerazione. Certificati polinomiali. Non determinismo. Enumerazione.
- Problemi NP-completi. Classi P e NP. Riducibilità polinomiale.
Modalità d’esame
L’esame consiste di una prova scritta cartacea composta di più esercizi e domande di teoria.
Può essere sostenuto suddiviso in 2 compitini.
Ulteriore pagina di riferimento
http://sdecapitaniasd.ariel.ctu.unimi.it
E’ consentito l’accesso al sito solo agli studenti del Corso di Laurea.