Sillabo dell'insegnamento

• A - Fondamenti
COM - Complessita'
Dipendenza dall'input: casi migliore, peggiore, medio (esempi con InsertSort). Tecnica Divide et Impera (esempio con MergeSort). Notazione asintotica.
COM - Complessita'
Concetti di algoritmo, complessita` in spazio e tempo. Oggetto e metodi dell'analisi. Modello computazionale RAM.
• B - Algoritmi
TAPA - Tecniche fondamentali di Analisi e Progetto di Algoritmi
Equazioni di ricorrenza e metodi di soluzione.
* A - Algoritmi fondamentali
Ottimizzazione: Elementi di programmazione dinamica. Problema della moltiplicazione di matrici. Problema della sottosequenza comune massimale.
* SDF - Strutture di Dati Fondamentali
Alberi binari: Alberi di ricerca binari. Proprieta`, operazioni. Alberi di ricerca Red-Black. Proprieta`, operazioni.
* SDF - Strutture di Dati Fondamentali
La struttura Heap, proprieta`, operazioni e loro complessita`.
* A - Algoritmi fondamentali
Ordinamento: L'algoritmo HeapSort. Definizione e analisi nei casi peggiore, migliore. L'algoritmo QuickSort. Definizione e analisi nai casi peggiore, migliore, medio. QuickSort random.
* A - Algoritmi fondamentali
Ordinamento: Limite inferiore per l'ordinamento. Alberi di decisione, limiti inferiori per il caso peggiore e medio. Counting sort.
* SDF - Strutture di Dati Fondamentali
Strutture dati elementari: Insiemi dinamici, operazioni fondamentali. Stack, code, liste semplici, doppie, circolari.
SDA - Strutture di Dati Avanzate
Grafi: Componenti connesse e fortemente connesse. Cammini minimi a sorgente singola: in grafi diretti aciclici, in grafi diretti con pesi non negativi (Dijkstra).
SDA - Strutture di Dati Avanzate
Grafi: Proprieta` e rappresentazione di grafi. Ricerca Breadth-first. Ricerca Depth-first. Ordinamento topologico di grafi diretti aciclici.
* A - Algoritmi fondamentali
Ottimizzazione: Elementi di strategia greedy. Problema della selezione delle attivita`. Problema del cambio di denaro. Problema dello zaino.