In breve:
Paradigmi di sintesi di algoritmi.
Fondamenti matematici per l'analisi di complessità degli algoritmi.
Algoritmi di ordinamento e selezione.
Strutture dati fondamentali, tabelle hash, alberi binari di ricerca, grafi.
Teoria della computabilità e NP-completezza.
Per esteso:
*Analisi di algoritmi e complessità*
Dimensione dei dati di un problema. Caso pessimo, ottimo e medio.
*Progettazione di algoritmi*
Paradigma iterativo (Insertionsort). Paradigma divide et impera (Mergesort).
*Ordine di grandezza delle funzioni*
Notazione asintotica.
*Ricorrenze*
Metodi risolutivi. Alberi di ricorsione. Metodo principale.
*Algoritmi di ordinamento: Heapsort*
Heap. Mantenimento delle proprietà dello heap. Costruzione di uno heap.
Algoritmo Heapsort. Code con priorità.
*Algoritmi di ordinamento: Quicksort*
Algoritmo Quicksort. Prestazioni di Quicksort. Versione randomizzata di Quicksort. Analisi.
*Ordinamento in tempo lineare*
Limiti inferiori per l'ordinamento. Counting Sort. Radix Sort. Bucket Sort.
*Mediano e selezione*
Minimo e massimo. Selezione con tempo medio lineare.
*Strutture dati fondamentali*
Strutture di base. Realizzazione di puntatori e oggetti. Rappresentazione di alberi radicati.
*Tabelle hash*
Tabelle a indirizzamento diretto. Funzioni hash. Indirizzamento aperto.
*Alberi binari di ricerca*
Operazioni di visita, ricerca, inserimento e cancellazione.
*Grafi*
Rappresentazioni. Visita in ampiezza e in profondità. Ordinamento topologico. Cammini minimi da sorgente unica. Cammini minimi tra tutte le coppie di vertici.
*Programmazione dinamica*
Fasi dello sviluppo di algoritmi. Esempio: ottimizzazione della parentesizzazione per il prodotto di una sequenza di matrici.
*Computabilità*
Macchina di Turing deterministica, multi-nastro, non-deterministica. Tesi di Church-Turing. Macchina di Turing universale. Problema della terminazione. Indecidibilità.
*Problemi NP e oltre NP*
Problemi decisionali, di ricerca, di enumerazione e di ottimizzazione. Classi di complessità P, NP e coNP. NP-Completezza. Riducibilità. Classe PSPACE.