Home » Archivo » Archvio 2013 » COMPUTABILITA' E ALGORITMI - 2013/2014

Laurea Magistrale

Salta il menu di secondo livello

COMPUTABILITA' E ALGORITMI - 10 CFU - A.A. 2013/2014

Insegnante

Prof. Paolo Baldan

Periodo

I Anno - 2 Trimestre | 13/01/2014 - 15/03/2014

Ore: 80 (16 esercitazione, 64 lezione)

Torna su ▲

Prerequisiti

Il corso richiede familiarità con alcuni concetti matematici di base, quali relazioni, funzioni, insiemi, cardinalità, ordini parziali, principi di induzione.
Non ci sono corsi propedeutici.

Conoscenze e abilità da acquisire

Obiettivo del corso è quello di avvicinare lo studente ai temi classici della teoria della calcolabilità e di completare e approfondire le conoscenze algoritmiche fondamentali acquisite nella laurea di primo livello. Per la prima parte, partendo dall'esame matematico del concetto di procedimento effettivo, si studiano i limiti che tale nozione impone sulla classe delle funzioni effettivamente calcolabili da un algoritmo, con lo sviluppo di una teoria dell'indecidibilità e della ricorsione. Per la seconda parte si approfondiscono alcune tecniche algoritmiche per l'elaborazione di strutture fondamentali quali grafi, stringhe e oggetti geometrici, si studiano algoritmi multithread e randomizzati. A livello più generale, il corso mira ad implementare le capacità di formalizzazione, ragionamento e problem solving dello studente.

Modalità di esame

L'esame si articola in una prova scritta, principalmente focalizzata sullo svolgimento di esercizi di teoria della computabilità, e in una discussione orale sulle tecniche algoritmiche.

Criteri di valutazione

La prova scritta contiene esercizi atti a verificare la capacità dello studente di utilizzare nozioni e tecniche dimostrative apprese durante il corso, per la soluzione di problemi nuovi. La prova orale verifica la conoscenza ed il livello di approfondimento dei temi trattati a lezione, con la descrizione di nozioni e la riproduzione di dimostrazioni note.

contenuti

Il corso si articola in due parti, la prima focalizzata sulla teoria della computabilità, e la seconda che approfondisce tematiche di natura prettamente algoritmica.

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. 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. Il teorema di Myhill-Sheperdson. Primo teorema di ricorsione. Secondo teorema di ricorsione.

L'approfondimento delle tecniche algoritmiche si concentrerà su:

- Algoritmi su grafi. Visita in ampiezza e visita in profondità. Ordinamento topologico. Componenti fortemente connesse.

- Algoritmi su stringhe. Algoritmi basati su confronti (Knuth,Morris e Pratt, di Boyer, Moore e Yao,Corasich). Algoritmi seminumerici (ShiftAnd e Fingerprint di Rabin,Karp). Alberi dei suffissi e algoritmo di Ukonnen per la loro costruzione in tempo lineare.

- Algoritmi Multithread.

- Algoritmi di Geometria Computazionale. Rappresentazione degli oggetti geometrici e algoritmi di base. 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.

- Algoritmi randomizzati. Algoritmo di rendering. Algoritmo di routing.

Attività di apprendimento previste e metodologie di insegnamento

Il corso prevede lezioni frontali ed esercizi.

Eventuali indicazioni sui materiali di studio

Pagina web: http://www.math.unipd.it/~baldan/Computabilita

Testi di riferimento

Torna su ▲