1 - 01/03 | | Introduzione al corso. Modello RAM di von Neumann. |
2 - 03/03 | | Segmento di somma massima. |
3 - 08/03 | | Complessità dell'ordinamento mediante confronti. Limite inferiore e alcuni limiti superiori (Insertion sort, selection sort). Caso pessimo e caso medio. |
4 - 13/03 | | Quicksort e sua complessità al caso pessimo. |
5 - 15/03 | | Quicksort randomizzato e analisi probabilistica con variabili indicatrici. |
6 - 20/03 | | Indecidibilità della fermata di Turing. Indecidibilità della complessità di Kolmogorov. |
7 - 24/03 | | laboratorio: modifica del mergesort per trovare le inversioni in un array |
8 - 27/03 | | Ricerca binaria, limite inferiore, paradigma divide et impera. |
9 - 29/03 | | Teorema principale per la risoluzione di relazioni di ricorrenza per la complessità di algoritmi divide et impera. |
10 - 03/04 | | Algoritmi divide et impera. Moltiplicazione veloce di matrici. Coppia di punti più vicina nel piano cartesiano. |
11 - 05/04 | | Alberi binari: definizione induttiva, visite e problemi decomponibili, con esempi. |
12 - 19/04 | | Alberi binari di ricerca e operazioni per dizionari (ricerca, inserimento, cancellazione, range query). |
13 - 26/04 | | Alberi AVL di ricerca (1-bilanciati). |
14 - 03/05 | | Grafi e loro rappresentazione in memoria. Implementazione in C++ della lettura di grafi da file e loro costruzione in memoria mediante liste di adiacenza. |
15 - 05/05 | | Grafi: cammini. Visita in profondità: albero DFS, classificazione degli archi, connettività, ciclicità. Visita in ampiezza (BFS) e distanze nei grafi non pesati. |
16 - 08/05 | | laboratorio: descrizione progetto (con difficoltà di registrazione) |
17 - 10/05 | | Funzioni hash e tabelle hash: gestione delle collisioni mediante liste di trabocco e indirizzamento aperto. |
18 - 12/05 | | Grafi pesati e cammini pesati. Algoritmo di Dijkstra per i cammini minimi. |
19 - 17/05 | | Classi di complessità P e NP: esempio dei cicli euleriani e hamiltoniani (HAM) nei grafi, colorazione di mappe (grafi) planari. Nozione di certificato polinomiale. Definizione della classe NP. |
20 - 19/05 | | Riduzione polinomiale. Esempio da HAM a commesso viaggiatore (TSP). Definizione della classe NPC (problemi NP-completi). Problema della soddisfacibilità (SAT) e Teorema di Cook-Levin. Colorazione di mappe. Riduzione a la Karp. |