Sillabo dell'insegnamento

• A - Fondamenti
* CAL - Calcolabilita'
Algoritmi ed il concetto di procedimento effettivo. Macchine a registri (URM). Funzioni parziali ricorsive (sostituzione, ricorsione, minimalizzazione). Equivalenze tra modelli di calcolo. Universalità dei modelli di calcolo. Tesi di Church.
* CAL - Calcolabilita'
Insiemi ricorsivi e ricorsivamente enumerabili. Teoremi di Rice e di Rice-Shapiro.
* CAL - Calcolabilita'
Problemi decidibili, indecidibili e semidecidibili. Indecidibilità del problema della fermata. Metodo di riduzione. Esempi di altri problemi indecidibili.
* CAL - Calcolabilita'
Enumerazione delle funzioni calcolabili. Esistenza di funzioni non calcolabili: il metodo della diagonalizzazione. Il teorema del parametro. Programmi universali.
* CAL - Calcolabilita'
Funzionali. Definizioni ricorsive. Ordinamenti parziali, funzioni monotone e punti fissi. Funzionali ricorsivi. Relazione tra continuità e ricorsività. Il teorema di Myhill-Sheperdson. Primo teorema di ricorsione. Secondo teorema di ricorsione.
• B - Algoritmi
* ASC - Algoritmi su Strutture Combinatorie
Algoritmi su grafi. Visita in ampiezza e visita in profondità. Ordinamento topologico. Componenti fortemente connesse.
* ASC - Algoritmi su Strutture Combinatorie
Algoritmi su stringhe. Preelaborazione fondamentale. Algoritmi basati su confronti: di Knuth Morris e Pratt, di Boyer e Moore e di Yao Corasich. Algoritmi seminumerici: Algoritmo ShiftAnd e algoritmo Fingerprint di Rabin e Karp. Alberi dei suffissi e algoritmo di Ukonnen per la loro costruzione in tempo lineare.
* A - Algoritmi fondamentali
Algoritmi di Geomatria Computazionale. Rappresentazione degli oggetti geometrici e algoritmi di base. Algoritmo per il test di non intersezione tra segmenti. Involucro convesso: algoritmi di Graham e di Jarvis. Localizzazione di un punto in un piano suddiviso in regioni poligonali.
TAA - Tecniche Algoritmiche Avanzate
Esempi di algoritmi randomizzati. Algoritmo di rendering. Algoritmo di routing.
AP - Algoritmi Paralleli
Algoritmi Multithread.