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:

• Avvisi
• Programma dei corsi
• Materiale didattico
• Prove d'esame

• Annuncio del 5 febbraio 2012
  

  Quinta prova intermedia di Informatica Teorica I risultati della quinta prova intermedia sono disponibili qui: IT-270-2012-01-27-esonero-5.pdf

• Annuncio del 26 gennaio 2012
  

  Quinta prova intermedia La quinta prova intermedia di Informatica Teorica si terrà Venerdì 27 gennaio 2012 - ore 17:30 - Aule N10, N14. Non sarà necessario prenotarsi alla prova.

• Annuncio del 26 gennaio 2012
  

  Quarta prova intermedia di Informatica Teorica I risultati della quarta prova intermedia sono disponibili qui: IT-270-2012-01-11-esonero-4.pdf

• Annuncio del 9 gennaio 2012
  

  Quarta prova intermedia La quarta prova intermedia di Informatica Teorica si terrà Mercoledì 11 gennaio 2012 - ore 15:45 - Aule N1, DS1. Non sarà necessario prenotarsi alla prova.

• Annuncio dell'8 gennaio 2012
  

  Terza prova intermedia di Informatica Teorica I risultati della terza prova intermedia sono disponibili qui: IT-270-2011-12-07-esonero-3.pdf

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.

• Il materiale del corso di Informatica Teorica - Primo Modulo:
  • 01-presentazione-del-corso-v.1.4.pdf
  • 02-linguaggi-e-grammatiche-v.1.8.pdf
    • 01-espressioni-regolari-01.pdf
    • 02-grammatiche-formali-01.pdf
  • 03-linguaggi regolari-v.1.9.pdf
    • 03-automi-a-stati-finiti-01.pdf
  • 04-proprieta-linguaggi-regolari-v.1.2.pdf
    • 04-pumping-lemma-regolari-01.pdf
    • 05-gramm-exp-reg-01.pdf
    • 06-myhill-nerode-01.pdf
  • 05-linguaggi-non-contestuali-06.pdf
    • 07-linguaggi-cf-01.pdf
  • 06-automi-a-pila-09.pdf
    • 08-automi-a-pila-01.pdf
  • 07-algoritmo-cyk-03.pdf
• Materiale del corso di Informatica Teorica - Secondo Modulo:
  • 08-cardinalita-transfinite-01.pdf
  • 09-macchine-di-turing-16.pdf
    • 09-mturing-01.pdf
  • 10-decidibilita-07.pdf
  • 11-riducibilita-11.pdf
  • 12-rice-03.pdf
  • 13-macchine-di-turing-e-linguaggi-03.pdf
  • 14-macchine-registri-06.pdf
  • 15-complessita-temporale-06.pdf
  • 16-complessita-spaziale-10.pdf
  • 17-complessita-sublineari-01.pdf

Prova scritta

L'esame è costituito da una prova scritta

• Per sola comodità di erogazione, tale prova è suddivisa in due parti relative al primo e al secondo modulo
• Gli studenti D.M 509/99 avranno compiti appositi
• Gli studenti che devono sostenere un compito integrativo da 7 CFU avranno compiti appositi (si prega di contattare il docente in anticipo)

Valutazione in itinere

Alternativamente all'esame ci si può avvalere della valutazione in itinere (prove intermedie)

• Solo gli studenti D.M. 270/04 di "Informatica Teorica" possono fruire della valutazione in intinere. Per gli studenti D.M. 509/99 (che hanno un diverso programma) non è prevista.
• La valutazione in itinere non è mutualmente esclusiva rispetto a quella tradizionale, tuttavia, lo studente che si presenta all'esame in un regolare appello rifiuta implicitamente il voto della valutazione in itinere.
• Il risultato della valutazione in itinere, qualora accettato dallo studente, sarà verbalizzato nella prima sessione d'esame di febbraio 2012.
• Si prevedono 5 prove intermedie in tutto, distribuite nel primo semestre. Il voto finale si otterrà facendo la media dei voti delle singole prove dopo aver scartato il voto peggiore (oppure, non considerando una prova a cui lo studente è stato assente).
• Le date delle prove intermedie sono le seguenti:
  1. Mercoledì 2 novembre 2011 - ore 17:30 - Aula N10
  2. Mercoledì 23 novembre 2011 - ore 15:45 - Aule N1/N3/DS1
  3. Mercoledì 7 dicembre 2011 - ore 15:45 - Aule N1, DS1
  4. Mercoledì 11 gennaio 2012 - ore 17:30 - Aula N10
  5. Venerdì 27 gennaio 2012 - ore 17:30 - Aula N10

Esempi di prove d'esame

Le seguenti prove d'esame si riferiscono al corso di Informatica Teorica I (Ord. D.M. 509/99), corrispondente grosso modo al Primo Modulo del corso attuale, e sono fornite a titolo d'esempio.

• Prove d'esame di Informatica Teorica I (Ord. D.M. 509/99):
  
  • Prova del 20 novembre 2002 (file pdf)
    
    Soluzioni della precedente (file pdf)
  • Prova del 31 gennaio 2003 (file pdf)
    
    Soluzioni della precedente (file pdf)
  • Prova del 13 novembre 2003 (file pdf)
    
    Soluzioni della precedente (file pdf)
  • Prova del 28 gennaio 2004 (file pdf)
  • Prova del 27 settembre 2004 (file pdf)
  • Prova del 22 novembre 2004 (file pdf)
    
    Soluzioni della precedente (file pdf)
  • Prova del 5 luglio 2005 (file pdf)
  • Prova del 15 settembre 2005 (file pdf)
  • Prova del 28 novembre 2005 (file pdf)
  • Prova del 3 luglio 2006 (file pdf)
  • Prova del 26 settembre 2006 (file pdf)
  • Prova del 19 luglio 2007 (file pdf)
    
    Soluzioni della precedente (file pdf)
  • Prova del 27 novembre 2007 (file pdf)
  • Prova del 15 settembre 2009 (file pdf)
  • Prova del 2 febbraio 2009 (file pdf)
    
    Soluzioni della precedente (file pdf)
  • Prova del 21 giugno 2010 (file pdf)

Le seguenti prove d'esame si riferiscono al corso di Informatica Teorica II (Ord. D.M. 509/99), corrispondente grosso modo al Secondo Modulo del corso attuale, e sono fornite a titolo d'esempio.

• Prove d'esame di Informatica Teorica II (Ord. D.M. 509/99):
  
  • Prova del 9 febbraio 2007 (file pdf)
  • Prova del 7 febbraio 2008 (file pdf)