Informatica Teorica
(Laurea Magistrale in Ing. Informatica, Ord. D.M. 270/04 - 1° anno)
Anno Accademico 2009-2010
Anno Accademico 2008-2009
Informatica Teorica per gli studenti della Laurea Magistrale in Ingegneria Informatica (12 CFU) è suddiviso in due moduli, che costituiscono un'introduzione alla teoria dei linguaggi e, parallelamente, alla teoria degli automi e della computabilità.
Informazioni sugli obiettivi formativi, sui docenti, sull'orario delle lezioni e sul calendario
degli esami saranno disponibili nella pagina del corso di Informatica Teorica del Collegio Didattico di Ingegneria Informatica.
In questa pagina potrete trovare:
- Avviso del 18 febbraio 2010
Risultati e verbalizzazioni Informatica Teorica (DM 270/04)
- I risultati della prova dell'11/02/2010 relativa a Informatica Teorica (solo DM 270/04) sono
disponibili qui: voti-IT-270-11-02-2010-01.pdf.
- Gli studenti possono verbalizzare il voto di questa prova nelle seguenti date:
- Lunedì 22 febbraio ore 17:00, ufficio Di Battista
- Mercoledì 24 febbraio ore 9:00, ufficio Di Battista
- Venerdì 26 febbraio ore 17:00, ufficio Di Battista
|
- Avviso del 15 febbraio 2010
Risultati e verbalizzazioni Informatica Teorica II (DM 509/99)
- I risultati della prova dell'11/02/2010 relativa a Informatica Teorica II (solo DM 509/99) sono
disponibili qui: voti-IT2-509-11-02-2010-01.pdf.
- Gli studenti possono verbalizzare il voto di questa prova nelle seguenti date:
- Martedì 16 febbraio ore 16:00, ufficio Di Battista
- Venerdì 19 febbraio ore 12:00, ufficio Di Battista
- Venerdì 26 febbraio ore 17:00, ufficio Di Battista
- Gli studenti di Informatica Teorica D.M. 270/04 dovranno attendere le valutazioni ancora un po'.
|
- Avviso del 14 febbraio 2010
Risultati e verbalizzazioni Informatica Teorica - I Modulo
- I risultati della prova dell'11/02/2010 relativa al primo modulo di Informatica Teorica sono
disponibili qui: IT1-2010-02-11.pdf.
- Gli studenti D.M. 509/99 che devono verbalizzare l'esame di "Informatica Teorica I"
possono verbalizzare il voto di questa prova o il voto della prova intermedia nelle seguenti date:
- Martedì 16 febbraio ore 16:00, ufficio di Patrignani
- Venerdì 19 febbraio ore 16:00, ufficio di Patrignani
- Gli studenti D.M. 270/04 dovranno attendere per la verbalizzazione l'esito della prova relativa al secondo modulo
(e verbalizzeranno la media delle due prove con il prof. Di Battista).
|
Archivio avvisi
Il programma del corso di Informatica Teorica (D.M. 270/04) - Primo Modulo è il seguente:
- Proprietà elementari dei linguaggi: operazioni su linguaggi, operatore
di Kleene, espressioni regolari, cardinalità dei linguaggi
- Grammatiche formali: grammatiche di Chomsky, produzioni, 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.
- Linguaggi non contestuali
Il programma di massima del corso di Informatica Teorica (D.M. 270/04) - Secondo Modulo è il seguente:
- Cardinalità di insiemi infiniti.
- Macchine di Turing (MT) e Turing calcolabilità: funzionamento delle MT, MT multinastro,
MT non deterministiche, descrizione linearizzata delle MT, MT universale, il problema della fermata,
calcolabilità secondo Turing, teorema di Rice, linguaggi di tipo 0 e MT.
- Macchine a registri (RAM): modelli di costo per RAM, modello a costi uniformi, modello a costi
logaritimici, RAM e MT.
- Teoria della complessità: tipologie di problemi, problemi di decisione, complessità
e problemi di decisione su linguaggi, teoremi di compressione, classi di complessità, relazioni
elementari tra classi di complessità, riducibilità, completezza, la classe NP, NP-completezza,
esempi di problemi NP-completi.
Il programma del corso di Informatica Teorica I (D.M. 509/99) è reperibile dalla
pagina del corso dell'A.A. 2008-2009.
Il programma del corso di Informatica Teorica II (D.M. 509/99) è reperibile dalla
pagina del corso dell'A.A. 2008-2009.
