Corsi di Laurea Corsi di Laurea Magistrale Corsi di Laurea Magistrale
a Ciclo Unico
Scuola di Ingegneria
INGEGNERIA DELL'INFORMAZIONE
Insegnamento
INFORMATICA TEORICA (Ult. numero di matricola da 0 a 4)
IN01103926, A.A. 2015/16

Informazioni valide per gli studenti immatricolati nell'A.A. 2013/14

Principali informazioni sull'insegnamento
Corso di studio Corso di laurea in
INGEGNERIA DELL'INFORMAZIONE
IN0513, ordinamento 2011/12, A.A. 2015/16
Ult1001
porta questa
pagina con te
Crediti formativi 6.0
Tipo di valutazione Voto
Denominazione inglese THEORY OF COMPUTATION
Dipartimento di riferimento Dipartimento di Ingegneria dell'Informazione (DEI)
Sito E-Learning https://elearning.dei.unipd.it/course/view.php?idnumber=2015-IN0513-000ZZ-2013-IN01103926-ULT1001
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 CINZIA PIZZI ING-INF/05

Mutuazioni
Codice Insegnamento Responsabile Corso di studio
IN01103926 INFORMATICA TEORICA (Ult. numero di matricola da 0 a 4) CINZIA PIZZI IN0521

Dettaglio crediti formativi
Tipologia Ambito Disciplinare Settore Scientifico-Disciplinare Crediti
CARATTERIZZANTE Ingegneria informatica ING-INF/05 6.0

Organizzazione dell'insegnamento
Periodo di erogazione Secondo semestre
Anno di corso III 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 01/03/2016
Fine attività didattiche 15/06/2016
Visualizza il calendario delle lezioni Lezioni 2019/20 Ord.2011

Commissioni d'esame
Commissione Dal Al Membri
11 A.A. 2016/2017 01/10/2016 31/12/2019 PIZZI CINZIA (Presidente)
RODA' ANTONIO (Membro Effettivo)
COMIN MATTEO (Supplente)
PIETRACAPRINA ANDREA ALBERTO (Supplente)
PINI MARIA SILVIA (Supplente)
SATTA GIORGIO (Supplente)
SILVESTRI FRANCESCO (Supplente)
VANDIN FABIO (Supplente)
10 A.A. 2016/2017 01/10/2016 15/03/2018 PINI MARIA SILVIA (Presidente)
PIZZI CINZIA (Membro Effettivo)
COMIN MATTEO (Supplente)
FERRARI CARLO (Supplente)
SATTA GIORGIO (Supplente)
VANDIN FABIO (Supplente)
9 A.A. 2015/2016 01/10/2015 15/03/2017 PIZZI CINZIA (Presidente)
PINI MARIA SILVIA (Membro Effettivo)
COMIN MATTEO (Supplente)
FERRARI CARLO (Supplente)
SATTA GIORGIO (Supplente)
8 A.A. 2014/2015 01/10/2014 15/03/2016 PINI MARIA SILVIA (Presidente)
PIZZI CINZIA (Membro Effettivo)
BILARDI GIANFRANCO (Supplente)
COMIN MATTEO (Supplente)
SATTA GIORGIO (Supplente)
7 A.A. 2014/2015 01/10/2014 15/03/2016 PIZZI CINZIA (Presidente)
PINI MARIA SILVIA (Membro Effettivo)
BILARDI GIANFRANCO (Supplente)
COMIN MATTEO (Supplente)
SATTA GIORGIO (Supplente)

Syllabus
Prerequisiti: Per poter seguire l'insegnamento con profitto e' necessaria una solida base matematica.
Conoscenze e abilita' da acquisire: Acquisizione di concetti di base dei modelli di calcolo, delle nozioni di computabilita' e decidibilita' e delle correlate gerarchie di automi, linguaggi e grammatiche.
Sviluppo della capacita' di astrazione, di analisi, e di risoluzione di problemi.
Modalita' di esame: Una prova scritta obbligatoria.
Criteri di valutazione: La valutazione dello studente si basera' su una verifica dell'apprendimento dei concetti di base introdotti durante il corso e la loro applicazione alla risoluzione di problemi in termini di analisi di automi e linguaggi formali e delle loro proprieta'.
Contenuti: Caratterizzazione di problemi in termini di linguaggi formali.
Studio di linguaggi formali e dei limiti della computabilita' mediante gerarchie di modelli riconoscitivi (automi) e generativi (grammatiche). In particolare si studieranno i linguaggi regolari, liberi dal contesto, ricorsivi e ricorsivamente enumerabili.

Linguaggi Regolari (REG).
Automi a stati finiti deterministici, non-deterministici, non-deterministici con epsilon-transizioni. Espressioni regolari: definizioni, proprieta', relazione con gli automi. Proprieta' dei linguaggi regolari.

Linguaggi Liberi dal Contesto (CFL).
Grammatiche Libere dal Contesto: definizioni, alberi di derivazione, semplificazione di grammatiche libere dal contesto, forma normale di Chomsky. Automi push-down, definizioni e loro relazione con le grammatiche libere dal contesto. Proprieta' dei Linguaggi Liberi dal Contesto.

Macchine di Turing.
Definizioni di linguaggi (problemi) ricorsivamente enumerabili (computabili) e ricorsivi (decidibili). Tesi di Church-Turing. Definizioni di base delle macchine di Turing e tecniche di costruzione. Dimostrazione dell'esistenza di linguaggi/funzioni non decidibili e non computabili.
Attivita' di apprendimento previste e metodologie di insegnamento: Il corso viene erogato attraverso lezioni frontali. Viene inoltre messo a disposizione degli studenti un forum (supervisionato) in cui poter discutere la risoluzione di esercizi. Questo per favorire la discussione e l'auto-verifica del processo di apprendimento da parte degli studenti durante il corso.
Eventuali indicazioni sui materiali di studio: Gli argomenti del corso sono trattati nei primi 9 capitoli del libro di testo di riferimento (fino alla sezione 9.3 inclusa).

Viene inoltre fornito materiale aggiuntivo a sostegno del corso (dispense di esercizi, slides su alcuni argomenti piu' discorsivi).
Testi di riferimento:
  • J.E. Hopcrpft, R.Motwani, J.D.Ullman, Automi, Linguaggi e Calcolabilità. --: Pearson, Addison Wesley, --. Cerca nel catalogo