Programma

1. Introduzione. Algoritmi e rappresentazione dei dati. Tempo di calcolo. Complessità computazionale. Strutture Dati Elementari e rappresentazione in memoria.
2. Strutture di tipo lineare. Specifica e realizzazione di liste, pile e code.
3. Strutture di tipo ad albero. Alberi: algoritmi di visita, realizzazioni. Heap ed HeapSort.
4. Strutture di tipo reticolare. Grafi: specifica, realizzazioni, algoritmi di visita, componenti connesse.
5. Strutture di tipo insieme. Insiemi: specifica e realizzazione, Mfset. Dizionari: specifica e realizzazioni, tabelle hash. Alberi bilanciati di Ricerca.
6. Complessità di algoritmi. Relazioni per la complessità di algoritmi ricorsivi.
7. 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.
8. Divide et impera. Descrizione del paradigma. Esempi: Mergesort, Quicksort.
9. Backtrack. Descrizione del paradigma. Esempio: String matching.
10. Programmazione Dinamica. Descrizione del paradigma. Esempio: String matching approssimato.
11. Greedy. Descrizione del paradigma. Esempi: Minimo Albero di Copertura, Scheduling di Programmi.
12. Non determinismo ed enumerazione. Certificati polinomiali. Non determinismo. Enumerazione.
13. 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.