Informazioni sugli obiettivi formativi, sui docenti, sull'orario delle lezioni e sul calendario degli esami sono disponibili nella pagina del Collegio Didattico di Ingegneria Informatica.

Docente: Giuseppe Di Battista

In questa pagina potrete trovare:

• Avvisi
• Programma del corso
• Materiale didattico
• Prove d'esame

Archivio avvisi

Il programma di massima del corso di Informatica Teorica è 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.
• 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, classi di complessità, relazioni elementari tra classi di complessità, riducibilità, completezza, la classe NP, NP-completezza, esempi di problemi NP-completi, la classe Pspazio, Pspazio-completezza, teorema di Savitch, le classi L e NL, NL-completezza, NL e co-NL, la classe BPP.

Materiale didattico (i link inattivi corrispondono a materiale in corso di revisione)

• I testi consigliati (non considerati indispensabili) sono:
  
  • G. Ausiello, F. d'Amore, G. Gambosi
    Linguaggi Modelli Complessità
    FrancoAngeli (i primi dieci capitoli sono distribuiti dagli autori qui)
  • Michael Sipser
    Introduction to the Theory of Computation
    Second Edition
    Thompson
  
   
  
• Slide del corso di Informatica Teorica:
  • 010-presentazione-del-corso-28.pdf
  • 020-linguaggi-e-grammatiche-23.pdf
    • 015-espressioni-regolari-05.pdf
    • 025-grammatiche-formali-02.pdf
  • 030-linguaggi regolari-25.pdf
    • 035-automi-a-stati-finiti-01.pdf
  • 040-proprieta-linguaggi-regolari-21.pdf
    • 045-pumping-lemma-regolari-01.pdf
    • 055-gramm-exp-reg-01.pdf
    • 065-myhill-nerode-01.pdf
  • 050-linguaggi-non-contestuali-12.pdf
    • 075-linguaggi-cf-01.pdf
  • 060-automi-a-pila-15.pdf
    • 085-automi-a-pila-02.pdf
  • 070-algoritmo-cyk-06.pdf
  • 080-cardinalita-transfinite-05.pdf
  • 090-macchine-di-turing-21.pdf
    • 095-mturing-01.pdf
  • 100-decidibilita-09.pdf
  • 110-riducibilita-15.pdf
  • 120-rice-05.pdf
  • 130-macchine-di-turing-e-linguaggi-07.pdf
  • 140-macchine-registri-09.pdf
  • 150-complessita-temporale-10.pdf
    • 105-esercizi-classe-np-01.pdf
    • 115-np-completezza-01.pdf
  • 160-complessita-spaziale-14.pdf
  • 170-complessita-sublineari-08.pdf
  • 180-nl-e-conl-03.pdf
  • 185-random-04.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__ 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 esclusivamente nella prima sessione d'esame di febbraio 2020.
• Si prevedono 5 prove intermedie in tutto, distribuite nel primo semestre. Il programma di ciascuna prova comprende tutto il programma svolto dal primo giorno di lezione fino alla lezione immediatamente precedente la prova. Il voto finale si otterrà facendo la media dei voti delle singole prove dopo aver scartato il voto più basso (oppure, non considerando una prova a cui lo studente è stato assente).
• Le date (preliminari e soggette a conferma) delle prove intermedie sono le seguenti:
  1. Lunedì 28 ottobre 2019 dalle 8:00 alle 10:00 aule N13, N14 e N11
     Programma della prima prova: tutto il programma dall'inizio del corso fino al teorema di Myhill-Nerode escluso. Risultati
  2. Venerdì 15 novembre 2019 dalle 8:00 alle 10:00 aule N13, N14 e N1
     Programma della seconda prova: tutto il programma dall'inizio del corso fino all'algoritmo CYK incluso. Risultati
  3. Venerdì 6 dicembre 2019 dalle 8:00 alle 10:00 aule N13, N14 e N1
     Programma della terza prova: tutto il programma dall'inizio del corso fino al teorema di Rice incluso. Risultati
  4. Venerdì 17 gennaio 2020 dalle 8:00 alle 10:00 aule N13, N14 e N1
     Programma della quarta prova: tutto il programma dall'inizio del corso fino alla complessita' temporale inclusa. Risultati
  5. Venerdì 24 gennaio 2020 dalle 8:00 alle 10:00 aule N13, N14 e N1
     Programma della quinta prova: tutto il programma dall'inizio del corso. Risultati

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 alla prima parte 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 alla seconda parte 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)