|
Insegnamento
INFORMATICA TEORICA (Ult. numero di matricola da 5 a 9)
IN01103926, A.A. 2015/16
Informazioni valide per gli studenti immatricolati nell'A.A. 2013/14
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 |
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)
|
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. |
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, 2009.
|
|
|