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: Maurizio Patrignani

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-29.pdf
  • 020-linguaggi-e-grammatiche-23.pdf
    • 015-espressioni-regolari-05.pdf
      • 015-espressioni-regolari-2020-10-06-es-1-4.txt
      • 015-espressioni-regolari-2020-10-08-es-5-6.txt
    • 025-grammatiche-formali-02.pdf
      • 025-grammatiche-formali-2020-10-09-es-1-4.txt
      • 025-grammatiche-formali-2020-10-12-es-5-11.txt
      • 025-grammatiche-formali-2020-10-13-es-12-13.txt
      • 037-esercizi-aggiuntivi-2020-10-20.pdf
  • 030-linguaggi regolari-25.pdf
    • 035-automi-a-stati-finiti-01.pdf
      • 035-automi-a-stati-finiti-2020-10-15.pdf
      • 035-automi-a-stati-finiti-2020-10-16.pdf
      • 035-automi-a-stati-finiti-2020-10-19.pdf
      • 035-automi-a-stati-finiti-2020-10-20.pdf
  • 040-proprieta-linguaggi-regolari-21.pdf
    • 045-pumping-lemma-regolari-01.pdf
      • 045-pumping-lemma-regolari-2020-10-22.pdf
      • 045-pumping-lemma-regolari-2020-10-23.pdf
      • 045-pumping-lemma-regolari-2020-10-26.pdf
      • 045-pumping-lemma-regolari-2020-10-27.pdf
      • 045-pumping-lemma-regolari-2020-10-30.pdf
      • 2020-10-29-lavagna.jpeg
    • 055-gramm-exp-reg-01.pdf
      • 055-gramm-exp-reg-2020-11-03.pdf
    • 065-myhill-nerode-01.pdf
      • 065-myhill-nerode-2020-10-30.pdf
      • 065-myhill-nerode-2020-11-02.pdf
      • 065-myhill-nerode-2020-11-03.pdf
  • 050-linguaggi-non-contestuali-12.pdf
    • 075-linguaggi-cf-01.pdf
      • 075-linguaggi-cf-2020-11-09.pdf
      • 075-linguaggi-cf-2020-11-10.pdf
  • 060-automi-a-pila-15.pdf
    • 085-automi-a-pila-02.pdf
      • 085-automi-a-pila-2020-11-13.pdf
      • 085-automi-a-pila-2020-11-16.pdf
      • 085-automi-a-pila-2020-11-17.pdf
      • 085-automi-a-pila-2020-11-19.pdf
      • 085-automi-a-pila-2020-11-23.pdf
      • 085-automi-a-pila-2020-11-26.pdf
      • 085-automi-a-pila-2020-11-27.pdf
  • 070-algoritmo-cyk-06.pdf
  • 080-cardinalita-transfinite-05.pdf
  • 090-macchine-di-turing-21.pdf
    • 095-mturing-01.pdf
      • 095-mturing-2020-11-24.pdf
      • 095-mturing-2020-11-26.pdf
      • 095-mturing-2020-11-30.pdf
      • 095-mturing-2020-12-01.pdf
  • 100-decidibilita-09.pdf
  • 110-riducibilita-15.pdf
  • 120-rice-06.pdf
  • 130-macchine-di-turing-e-linguaggi-07.pdf
  • 140-macchine-registri-09.pdf
  • 150-complessita-temporale-11.pdf
    • 105-esercizi-classe-np-01.pdf
    • 115-np-completezza-01.pdf
    • 150-complessita-temporale-2021-01-07.pdf
  • 160-complessita-spaziale-14.pdf
  • 170-complessita-sublineari-08.pdf
  • 180-nl-e-conl-04.pdf
  • 190-incompletezza-03.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

• 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 2021.
• Si prevedono sette prove intermedie in tutto, distribuite nel primo semestre ed erogate tramite moodle ed il lockdown browser respondus. 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 i due voti più bassi (oppure, non considerando le due prove a cui lo studente è stato assente).
• Le date (preliminari e soggette a conferma) delle prove intermedie sono le seguenti:
1. Martedì 20 ottobre 2020 dalle 18:00 alle 18:30
   
2. Martedì 3 novembre 2020 dalle 18:00 alle 18:30
   
3. Martedì 17 novembre 2020 dalle 18:00 alle 18:30
   
4. Martedì 1 dicembre 2020 dalle 18:00 alle 18:30
   
5. Martedì 15 dicembre 2020 dalle 18:00 alle 18:30
   
6. Martedì 12 gennaio 2021 dalle 18:00 alle 18:30
   
7. Venerdì 22 gennaio 2021 dalle 18:00 alle 18:30
   

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)