| 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 5 a 9)
IN01103926, A.A. 2015/16
Informazioni valide per gli studenti immatricolati nell'A.A. 2013/14
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
Principali informazioni sull'insegnamento
| Corso di studio |
Corso di laurea in INGEGNERIA DELL'INFORMAZIONE IN0513, ordinamento 2011/12, A.A. 2015/16 |
 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-ULT1002 | |
| 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 | MARIA SILVIA PINI | ING-INF/05 |
|---|
Mutuazioni
| Codice | Insegnamento | Responsabile | Corso di studio |
|---|---|---|---|
| IN01103926 | INFORMATICA TEORICA (Ult. numero di matricola da 5 a 9) | MARIA SILVIA PINI | 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 |
| 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: |
|
