Sillabo dell'insegnamento

• A - Fondamenti
COM - Complessita'
- Algoritmi: correttezza, terminazione, costo computazionale (caso pessimo, caso medio). Analisi di InsertionSort. Fondamenti di Matematica. Principio di Induzione (prova di terminazione e correttezza di programmi). Ordine di grandezza di funzioni: O, ??, ??, o, ??. Base, tetto, esponenziali, Logaritmi. Sommatorie e serie. Limitazioni di ordine di grandezza con l'uso degli integrali. Soluzioni di ricorrenze, verifiche di soluzioni. Il Teorema dell'esperto.
SLP - Semantica dei Linguaggi di Programmazione
Tipi di dati astratti. Rappresentazione dei tipi di dati astratti.
* CAL - Calcolabilita'
Problemi di decisione. Complessita' dei problemi. La classe P e la classe NP. La riduzione polinomiale. Enunciato del Teorema di Cook e i problemi NP-completi
• B - Algoritmi
TAPA - Tecniche fondamentali di Analisi e Progetto di Algoritmi
Riconoscimento di pattern in un testo: la soluzione ingenua e l'algoritmo di Knuth-Morris-Pratt. (Inviluppo convesso: algoritmo di Graham).
* A - Algoritmi fondamentali
Problema del flusso massimo nelle reti. Capacita' minima di tagli, cammini aumentanti.
TAPA - Tecniche fondamentali di Analisi e Progetto di Algoritmi
Soluzioni ottime e soluzioni esatte del problema dello zaino 0-1. Coefficienti binomiali. Ottimizzazione del prodotto di una sequenza di matrici. Cammini minimi tra tutte le coppie di vertici. Chiusura transitiva di grafi orientati
* ASC - Algoritmi su Strutture Combinatorie
Rappresentazione in memoria. Visite di grafi e algoritmi basati su visite. - Condizioni
TAPA - Tecniche fondamentali di Analisi e Progetto di Algoritmi
Stampa di stringhe e di insiemi. Il problema delle n regine. Accoppiamento stabile. Scelta ottima e metodo branch and bound per il problema dello zaino.
* ASC - Algoritmi su Strutture Combinatorie
Grafi - Generalita' e rappresentazione in memoria. Schema generale di visita di grafi. Alberi di copertura e componenti connesse.Visita in ampiezza (BFS), visita in profondit? (DFS) e loro proprieta' (classificazione degli archi). Grafi aciclici e ordine topologico (algoritmo con la cancellazione di sorgenti, algoritmo con i tempi di fine-visita DFS). Componenti fortemente connesse (algoritmo con i tempi di fine-visita DFS).
* SDF - Strutture di Dati Fondamentali
Strutture di dati: dati statici e dinamici. Il tipo di dato lista: realizzazione del tipo lista con puntatori e con cursori. Liste lineari, liste bidirezionali, liste circolari. Liste composite. Pile: realizzazione con puntatori e con arrays. Code: realizzazione con puntatori e con arrays. Memorizzazione su tabelle con indirizzamento diretto. Collisioni. Tabelle hash. Criteri per funzioni hash. Gestione delle collisioni. Scansione esterna (liste di trabocco). Scansione interna (lineare, quadratica, doppio hashing, pseudocasuale). Cancellazione di dati. Costo medio della scansione esterna ed interna senza agglomerati primari.
* SDF - Strutture di Dati Fondamentali
Generalita' sugli alberi ordinati, realizzazione. Alberi binari di ricerca. Ricerca di chiavi, minimo, massimo, successore e predecessore. Inserimento e cancellazione. Costo computazionale delle operazioni di ricerca e problema del bilanciamento. Alberi AVL (cenno alle operazioni di rotazione). Alberi Red-Black. B-alberi, ricerca di chiavi, inserimento, cancellazione. Costo computazionale delle operazioni sui B-alberi. Alberi bilanciati per realizzare insiemi disgiunti (union, find).
* SDF - Strutture di Dati Fondamentali
Rappresentazione con arrays. Heap: procedura di mantenimento dalla proprieta' di heap e calcolo del costo computazionale. Costruzione di un heap: metodo dal basso e dall'alto, calcolo dei costi computazionali. HeapSort e suo costo computazionale. Code di priorit?. Inserimento e cancellazione su un heap, confronto di efficienza tra le varie realizzazioni. Heaps d-ary.
* A - Algoritmi fondamentali
Metodi di progetto: Divide et Impera. Analisi di Ricerca binaria e MergeSort. Procedure di partizione (3 versioni). Analisi del costo di Partizione e di QuickSort (caso peggiore, caso migliore, caso medio medio). Limiti teorici della complessit? del problema di ordinamento per confronto. CountingSort.
TAPA - Tecniche fondamentali di Analisi e Progetto di Algoritmi
Algoritmi Greedy: selezione delle attivita', colorazione di un grafo di intervalli, codici di Huffman.
* A - Algoritmi fondamentali
Calcolo del minimo e del massimo in una sequenza. La mediana e la selezione dell'i-esimo elemento: algoritmo di costo computazionale medio O(n); algoritmo di costo pessimo O(n).