Presentazione

Organizzazione della Didattica

DM270
INFORMATICA ORD. 2014


12

Corsi comuni

 

Frontali Esercizi Laboratorio Studio Individuale
ORE: 64 32 0 102

Periodo

AnnoPeriodo
I annoannuale

Frequenza

Facoltativa

Erogazione

Convenzionale

Lingua

Italiano

Calendario Attività Didattiche

InizioFine
02/10/201701/06/2018

Tipologia

No results found

Responsabile Insegnamento

ResponsabileSSDStruttura
Prof. BALDAN PAOLOINF/01Dipartimento di Matematica

Altri Docenti

DocenteCoperturaSSDStruttura
Dott. BRESOLIN DAVIDEIstituzionaleINF/01Dipartimento di Matematica

Attività di Supporto alla Didattica

Non previste.

Bollettino

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.

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.

Il corso prevede lezioni frontali ed esercizi.

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.

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.

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.

Nigel Cutland, Computability. An Introduction to Recursive Function Theory. : Cambridge University Press, 1980 T.H. Cormen, C.E. Leiserson, R.L. Rivest, C. Stein, Introduzione agli Algoritmi e Strutture Dati (3a edizione). : McGraw-Hill Italia, 2010

Pagina web per la parte di Computabilità: http://www.math.unipd.it/~baldan/Computabilita Materiale aggiuntivo per la parte di algoritmi: http://www.math.unipd.it/~colussi/CompAlgoritmi_2014-15