Corsi di Laurea Corsi di Laurea Magistrale Corsi di Laurea Magistrale
a Ciclo Unico
Scuola di Scienze
INFORMATICA
Insegnamento
COMPUTABILITA'
SCP8084818, A.A. 2019/20

Informazioni valide per gli studenti immatricolati nell'A.A. 2019/20

Principali informazioni sull'insegnamento
Corso di studio Corso di laurea magistrale in
INFORMATICA
SC1176, ordinamento 2014/15, A.A. 2019/20
N0
porta questa
pagina con te
Crediti formativi 6.0
Tipo di valutazione Voto
Denominazione inglese COMPUTABILITY
Sito della struttura didattica http://informatica.scienze.unipd.it/2019/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 PAOLO BALDAN INF/01

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

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

Tipo ore Crediti Ore di
didattica
assistita
Ore Studio
Individuale
LEZIONE 6.0 48 102.0

Calendario
Inizio attività didattiche 30/09/2019
Fine attività didattiche 18/01/2020
Visualizza il calendario delle lezioni Lezioni 2019/20 Ord.2014

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

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à, completando e approfondendo alcune conoscenze algoritmiche acquisite nella laurea di primo livello. 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.
Modalita' di esame: Esame scritto e prova orale.
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.
Contenuti: 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.
Attivita' 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:
  • Nigel Cutland, Computabiliy: An Introduction to Recursive Function Theory. --: Cambridge University Press, 1980. Cerca nel catalogo

Didattica innovativa: Strategie di insegnamento e apprendimento previste
  • Lecturing
  • Problem based learning
  • Story telling
  • Problem solving

Didattica innovativa: Software o applicazioni utilizzati
  • Moodle (files, quiz, workshop, ...)
  • Latex

Obiettivi Agenda 2030 per lo sviluppo sostenibile
Istruzione di qualita'