Corsi di Laurea Corsi di Laurea Magistrale Corsi di Laurea Magistrale
a Ciclo Unico
Scuola di Scienze
INFORMATICA
Insegnamento
COMPUTABILITA' E ALGORITMI
SCP6076317, A.A. 2017/18

Informazioni valide per gli studenti immatricolati nell'A.A. 2017/18

Principali informazioni sull'insegnamento
Corso di studio Corso di laurea magistrale in
INFORMATICA
SC1176, ordinamento 2014/15, A.A. 2017/18
N0
porta questa
pagina con te
Crediti formativi 12.0
Tipo di valutazione Voto
Denominazione inglese COMPUTABILITY AND ALGORITHMS
Sito della struttura didattica http://informatica.scienze.unipd.it/2017/laurea_magistrale
Dipartimento di riferimento Dipartimento di Matematica
Obbligo di frequenza No
Lingua di erogazione ITALIANO
Sede PADOVA
Corso singolo È possibile iscriversi all'insegnamento come corso singolo
Corso a libera scelta È possibile utilizzare l'insegnamento come corso a libera scelta

Docenti
Responsabile DAVIDE BRESOLIN INF/01
Altri docenti PAOLO BALDAN INF/01

Dettaglio crediti formativi
Tipologia Ambito Disciplinare Settore Scientifico-Disciplinare Crediti
CARATTERIZZANTE Discipline Informatiche INF/01 12.0

Organizzazione dell'insegnamento
Periodo di erogazione Annuale
Anno di corso I Anno
Modalità di erogazione frontale

Tipo ore Crediti Ore di
didattica
assistita
Ore Studio
Individuale
ESERCITAZIONE 4.0 32 68.0
LEZIONE 8.0 64 136.0

Calendario
Inizio attività didattiche 02/10/2017
Fine attività didattiche 15/06/2018
Visualizza il calendario delle lezioni Lezioni 2018/19 Ord.2014

Commissioni d'esame
Commissione Dal Al Membri
2 a.a. 2017/2018 01/10/2017 28/02/2020 BALDAN PAOLO (Presidente)
BRESOLIN DAVIDE (Membro Effettivo)
CRAFA SILVIA (Membro Effettivo)
PALAZZI CLAUDIO ENRICO (Membro Effettivo)
RANZATO FRANCESCO (Membro Effettivo)

Syllabus
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 abilita' 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.
Modalita' 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.
Attivita' di apprendimento previste e metodologie di insegnamento: Il corso prevede lezioni frontali ed esercizi.
Eventuali indicazioni sui materiali di studio: 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
Testi di riferimento:
  • Nigel Cutland, Computability. An Introduction to Recursive Function Theory. --: Cambridge University Press, 1980. Testo per la parte di computabilità. Cerca nel catalogo
  • T.H. Cormen, C.E. Leiserson, R.L. Rivest, C. Stein, Introduzione agli Algoritmi e Strutture Dati (3a edizione). --: McGraw-Hill Italia, 2010. Cerca nel catalogo