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

• Avviso del 1 settembre 2009
  

  Esami di Informatica Teorica del 15/09/2009 Gli esami di Informatica Teorica del 15/09/2009 avranno luogo nelle aule N10 e N11 secondo i seguenti orari: 9:00 Informatica Teorica I (DM509) e primo modulo di Infomatica Teorica (DM270) 11:00 Informatica Teorica II (DM509) e secondo modulo di Infomatica Teorica (DM270)

Archivio avvisi

Il programma del corso di Informatica Teorica - 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.

Il programma di massima del corso di Informatica Teorica - Secondo Modulo è il seguente:

• Linguaggi non contestuali
• 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, 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.

Materiale didattico

• Il testo consigliato (non considerato indispensabile) è:
  
  G. Ausiello, F. d'Amore, G. Gambosi
  Linguaggi Modelli Complessità
  FrancoAngeli
• Il materiale del corso di Informatica Teorica - Primo Modulo di quest'anno accademico ha lievi variazioni rispetto al materiale dello scorso anno:
  • 00-presentazione-del-corso-v.1.0.pdf
  • 01-insiemi-relazioni-funzioni-v.1.5.pdf
  • 02-linguaggi-e-grammatiche-v.1.4.pdf
  • 03-linguaggi regolari-v.1.4.pdf
  • 04-proprieta-linguaggi regolari-v.1.0.pdf
• I lucidi delle esercitazioni di Informatica Teorica - Primo Modulo in formato pdf sono anche reperibili qui:
  • e01-concetti-base-v1.3.pdf
  • e02-grammatiche-formali-v1.1.pdf
  • e03-automi-a-stati-finiti-v1.3.pdf
  • e04-pumping-lemma-regolari-v1.3.pdf
  • e048-gramm-exp-reg-v1.0.pdf
  • e050-myhill-nerode-v1.3.pdf
• Materiale del corso di Informatica Teorica - Secondo Modulo:
  • linguaggi non contestuali-03.pdf
  • automi-a-pila-06.pdf
  • algoritmo-cyk-01.pdf
  • macchine-di-turing-13.pdf
  • decidibilita-05.pdf
  • riducibilita-08.pdf
  • macchine-di-turing-e-linguaggi-01.pdf
  • macchine-registri-04.pdf
  • complessita-temporale-03.pdf
  • complessita-spaziale-05.pdf
• I lucidi delle esercitazioni di Informatica Teorica II in formato pdf sono reperibili qui:
  • e060-linguaggi-cf-v1.1.pdf
  • e070-automi-a-pila-v1.2.pdf
  • e080-mturing-v1.2.pdf
  • e100-NP-completezza.pdf

  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)

  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)

   

  Informatica Teorica / A cura di Maurizio Patrignani / 4 ottobre 2008