Sillabo dell'insegnamento

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