Fondamenti dell'Informatica 2, A.A. 2008/2009

Orario del corso:

Argomenti trattati a lezione

  1. 2 Marzo 2010. Presentazione del corso.
    Parte 1: Linguaggi Formali
    Alfabeti e linguaggi. Automi a stati finiti deterministici. Definizione di linguaggio regolare. Esempi.
  2. 5 Marzo 2010. Esempi di DFA (linguaggi con ultimo, penultimo, terzultimo carattere "0". Automi a stati finiti non deterministici. Teoremi di equivalenza tra formalismi DFA e NFA. Esempio di trasformazione da NFA e DFA evitando di analizzare troppi stati inutili.
  3. 9 Marzo 2010. (1 ora) Automi con ε-transizioni. Definizioni e esempi. Teoremi di equivalenza tra formalismi NFA e ε-NFA.
  4. 12 Marzo 2010. Espressioni regolari. Costruzione di ε-NFA per una e.r. Calcolo dell'espressioni regolari associate ad un DFA.
  5. 16 Marzo 2010. Pumping Lemma per i linguaggi regolari. Applicazioni. Proprietà di chiusura dei linguaggi regolari e applicazioni. Risultati di decidibilità.
  6. 19 Marzo 2010. Le relazioni RM e RL. Il teorema di Myhill-Nerode. Unicità dell'automa minimo.
  7. 23 Marzo 2010. Algoritmi di minimizzazione di automi. Esempi ed esercizi. Grammatiche libere dal contesto (CF). Linguaggio generato. Esempio. Alberi di derivazione e derivazioni.
  8. 26 Marzo 2010. Relazioni tra alberi e derivazioni. Ambiguità. Eliminazione di simboli inutili. Eliminazione di ε-produzioni e di produzioni unitarie.
  9. 30 Marzo 2010. Le forme normali di Chomsky (dettagliatamente) e di Greibach. Il pumping lemma per i linguaggi liberi dal contesto. Applicazioni del pumping lemma ed esercizi.
  10. 9 Aprile 2010. Proprietà di chiusura dei linguaggi liberi. Proprietà di decidibilità degli stessi. Grammatiche lineari destre e equivalenza con i linguaggi regolari. Grammatiche di tipo 1. Grammatiche di tipo 0 e gerarchia di Chomsky. Calcolare con le grammatiche.
  11. 13 Aprile 2010. Esercizi su linguaggi dipendenti dal contesto. Risultati di decidibilità. Esistenza di insieme ricorsivo non generabile da grammatiche dipendenti dal contesto.
  12. 16 Aprile 2010. Parte II: Tesi di Church e Computabilità
    Richiamo del formalismo delle funzioni primitive ricorsive e ricorsive parziali e della Tesi di Church. Il formalismo delle Macchine di Turing. Descrizione istantanea e computazione. Esempi ed esercizi. (Dove acquistarla :) La nozione di funzione Turing calcolabile. Le funzioni di base.
  13. 20 Aprile 2010. Teorema di equivalenza tra le funzioni ricorsive parziali e le funzioni Turing-calcolabili.
  14. 23 Aprile 2010. (1 ora) Calcolabilità e Linguaggi di Programmazione. Sintassi del linguaggio While mediante grammatica CF e concetto di stato.
  15. 27 Aprile 2010. Semantica formale del linguaggio While. Turing completezza del linguaggio While (solo traccia della dim). Programmi for ed equivalenza con il formalismo delle funzioni primitive ricorsive (senza dimostrazione). Dimostrazione dell'indecidibilità dell'halting problem senza aritmetizzazione. 30 Aprile 2010. Interpreti e Teorema s-m-n senza aritmetizzazione. Il primo teorema di ricorsione. Dimostrazioni ed esempi. Proprietà dei programmi estensionali e non.
  16. 7 Maggio 2010. Il secondo Teorema di Ricorsione. I Teoremi di Rice e Rice-Shapiro (senza dim) ed il loro significato. Riducibilità funzionale. Studio della relazione di riducibilità. Esempi di riduzione. Insiemi minimali per la relazione.
  17. 11 Maggio 2010. Insiemi ricorsivi e completi. Relazioni tra insiemi e loro complementari. Esercizi.
  18. 14 Maggio 2010. Insiemi creativi e produttivi. Riducibilità tra questi. Proprieta' dei produttivi. Teorema di Myhill.
  19. 18 Maggio 2010. Insiemi semplici. Proprieta' ed esistenza di un insieme semplice. Esercizi. Valutazione del corso.
  20. 21 Maggio 2010. Parte III: Complessità Computazionale
    Problemi e linguaggi. Problemi decisionali e funzionali e relazioni.
  21. 25 maggio 2010. 10 Marzo 2008. Classi di Complessità in tempo deterministiche. Alcuni cenni a simulazioni e alla tesi di Church computazionale. La classe P. La classe EXPTIME.
  22. 28 Maggio 2010. La MdT non deterministica. La classe NP. Collocazione di NP tra P e EXPTIME. Caratterizzazione di NP come GUESS+VERIFY, riduzioni e completezza.
  23. 1 Giugno 2010. Complessità in spazio. Riduzioni in spazio logaritmico. NP completezza. Teoremi di Cook (breve cenno alla dimostrazione). SAT, 3SAT, 2SAT, e NAESAT.
  24. 4 Giugno 2010. Esercitazione.
  25. 8 Giugno 2010. Esercitazione.


Home page del corso