| INFORMATICA TEORICA
(obiettivi)
Presentare la teoria dei linguaggi e, parallelamente, la teoria degli automi. Introdurre i paradigmi della computabilità e della complessità. Al termine del corso gli studenti dovrebbero conoscere nuove metodologie formali, dovrebbero riuscire a rivisitare in modo critico, dal punto di vista del potere espressivo, metodologie già introdotte in modo pragmatico e dovrebbero essere in grado di classificare i problemi dal punto di vista delle risorse richieste per la loro risoluzione.
|
|
Codice
|
20801728 |
|
Lingua
|
ITA |
|
Tipo di attestato
|
Attestato di profitto |
| Modulo: INFORMATICA TEORICA MODULO I
(obiettivi)
Presentare la teoria dei linguaggi e, parallelamente, la teoria degli automi. Introdurre i paradigmi della computabilità e della complessità. Al termine del corso gli studenti dovrebbero conoscere nuove metodologie formali, dovrebbero riuscire a rivisitare in modo critico, dal punto di vista del potere espressivo, metodologie già introdotte in modo pragmatico e dovrebbero essere in grado di classificare i problemi dal punto di vista delle risorse richieste per la loro risoluzione.
|
|
Codice
|
20801728-1 |
|
Lingua
|
ITA |
|
Tipo di attestato
|
Attestato di profitto |
|
Crediti
|
6
|
|
Settore scientifico disciplinare
|
ING-INF/05
|
|
Ore Aula
|
54
|
|
Attività formativa
|
Attività formative caratterizzanti
|
Canale Unico
|
Docente
|
PATRIGNANI MAURIZIO
(programma)
Proprietà elementari dei linguaggi: operazioni su linguaggi, operatore di Kleene, espressioni regolari, cardinalità dei linguaggi
Grammatiche formali: grammatiche di Chomsky, produzioni, generazione e riconoscimento di linguaggi.
Linguaggi regolari: automi a stati finiti, relazioni tra automi e linguaggi regolari, pumping lemma, chiusura dei linguaggi regolari, espressioni regolari e linguaggi regolari, decidibilità e linguaggi regolari, teorema di Myhill-Nerode.
(testi)
G. Ausiello, F. d'Amore, G. Gambosi, "Linguaggi Modelli Complessità", FrancoAngeli.
|
|
Date di inizio e termine delle attività didattiche
|
Dal al |
|
Modalità di erogazione
|
Tradizionale
|
|
Modalità di frequenza
|
Non obbligatoria
|
|
Metodi di valutazione
|
Prova scritta
|
|
|
| Modulo: INFORMATICA TEORICA MODULO II
(obiettivi)
Presentare la teoria dei linguaggi e, parallelamente, la teoria degli automi. Introdurre i paradigmi della computabilità e della complessità. Al termine del corso gli studenti dovrebbero conoscere nuove metodologie formali, dovrebbero riuscire a rivisitare in modo critico, dal punto di vista del potere espressivo, metodologie già introdotte in modo pragmatico e dovrebbero essere in grado di classificare i problemi dal punto di vista delle risorse richieste per la loro risoluzione.
|
|
Codice
|
20801728-2 |
|
Lingua
|
ITA |
|
Tipo di attestato
|
Attestato di profitto |
|
Crediti
|
6
|
|
Settore scientifico disciplinare
|
ING-INF/05
|
|
Ore Aula
|
54
|
|
Attività formativa
|
Attività formative caratterizzanti
|
Canale Unico
|
Docente
|
PATRIGNANI MAURIZIO
(programma)
Presentare la teoria dei linguaggi e, parallelamente, la teoria degli automi. Introdurre i paradigmi della computabilità e della complessità. Al termine del corso gli studenti dovrebbero conoscere nuove metodologie formali, dovrebbero riuscire a rivisitare in modo critico, dal punto di vista del potere espressivo, metodologie già introdotte in modo pragmatico e dovrebbero essere in grado di classificare i problemi dal punto di vista delle risorse richieste per la loro risoluzione.
(testi)
Michael Sipser, "Introduction to the Theory of Computation", Second Edition, Thompson.
|
|
Date di inizio e termine delle attività didattiche
|
Dal al |
|
Modalità di erogazione
|
Tradizionale
|
|
Modalità di frequenza
|
Non obbligatoria
|
|
Metodi di valutazione
|
Prova scritta
|
|
|
|
Università Roma Tre