Sillabo dell'insegnamento

• A - Fondamenti
COM - Complessita'
Ordine di grandezza. Limite superiore ed inferiore. Strumenti matematici: principio di induzione,
COM - Complessita'
Complessità  intrinseca di un problema.
* CAL - Calcolabilita'
Cenni sui problemi decisionali. La classe P e NP. Soluzioni enumerative.
• B - Algoritmi
* A - Algoritmi fondamentali
InsertionSort: analisi della complessità in tempo e spazio nel caso pessimo e nel caso medio.
* A - Algoritmi fondamentali
Quicksort con analisi della complessita' in tempo nel caso pessimo e nel caso medio.
* A - Algoritmi fondamentali
Visite dei grafi: visita in ampiezza (BFS), visita in profondità  (DFS) e loro proprietà  (classificazione degli archi).
* SDF - Strutture di Dati Fondamentali
Code, Pile: operazioni di base
* SDF - Strutture di Dati Fondamentali
Generalità  sugli alberi ordinati, realizzazione.C omplessità  delle operazioni di visita e di ordinamento utilizzando alberi binari di ricerca. Grafi:generalità  e rappresentazione in memoria. Schema generale di visita di grafi. Alberi di copertura e componenti connesse.
TAPA - Tecniche fondamentali di Analisi e Progetto di Algoritmi
Divide-et-Impera: Mergesort, Ricerca Binaria, Selezione. Mediana e statistiche d'ordine.
TAPA - Tecniche fondamentali di Analisi e Progetto di Algoritmi
Greedy: Alberi di copertura di costo minimo: algoritmo di Kruskal, algoritmo di Prim,
TAPA - Tecniche fondamentali di Analisi e Progetto di Algoritmi
Programmazione dinamica: moltiplicazione di matrici con il minimo numero di prodotti, problema dello zaino intero con/senza
SDA - Strutture di Dati Avanzate
Cenni su heap binomiali, heap di Fibonacci e strutture dati per UnionFind.
* ASC - Algoritmi su Strutture Combinatorie
Grafi aciclici e ordine topologico (algoritmo con la cancellazione di sorgenti, algoritmo con i tempi di fine-visita DFS).
* ASC - Algoritmi su Strutture Combinatorie
Cammini minimi da sorgente singola: Bellman Ford, metodo anologo alla moltiplicazione matrice-vettore
* ASC - Algoritmi su Strutture Combinatorie
Cammini minimi fra tutte le coppie: algoritmo di Floyd-Warshall, algoritmo analogo alla moltiplicazione di matrici, algoritmo di Johnson per grafi sparsi. Longest Common Subsequence.