Home » Archivo » Archvio 2011 » Computabilità e algoritmi - 2011/2012

Laurea Magistrale

Salta il menu di secondo livello

Computabilità e algoritmi - 10 CFU - A.A. 2011/2012

Insegnante

Prof. Paolo Baldan

Periodo

I anno - 2 trimestre | 16/01/2012 - 17/03/2012

Curriculum:

Ore: 64 Frontali, 0 Laboratorio, 16 Esercizi

Torna su ▲

Programma del Corso

Il corso si articola in due parti, la prima si concentra sulla teoria della computabilità, mentre la seconda approfondisce aspetti legati alle tecniche algoritmiche.

Per quanto riguarda la teoria della computabilità saranno sviluppati i seguenti temi:
- 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.
- Enumerazione delle funzioni calcolabili. Esistenza di funzioni non calcolabili: il metodo della diagonalizzazione. Il teorema del parametro. Programmi universali.
- Problemi decidibili, indecidibili e semidecidibili. Indecidibilità del problema della fermata. Metodo di riduzione. Esempi di altri problemi indecidibili.
- Insiemi ricorsivi e ricorsivamente enumerabili. Teoremi di Rice e di Rice-Shapiro.
- 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.

L'approfondimento delle tecniche algoritmiche si concentrerà su:
- Algoritmi su grafi (Capitolo 6 del testo di riferimento). Visita in ampiezza e visita in profondità. Ordinamento topologico. Componenti fortemente connesse.
- 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.
- Algoritmi Multithread. Tutto il Capitolo 27 del testo di riferimento.
- 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.
- Esempi di algoritmi randomizzati. Algoritmo di rendering. Algoritmo di routing.

Prerequisiti: - -

Propedeuticità:

Ausili Didattici: - -

Testi di Riferimento: Nigel Cutland "Computability. An Introduction to Recursive Function Theory." Cambridge University Press.

Introduzione agli Algoritmi e Strutture Dati. (terza edizione). T.H.Cormen, C.E.Leiserson, R.L.Rivest, C.Stein. Editore McGraw-Hill Italia.

Torna su ▲