III Anno -- 6 CFU

Obiettivi formativi: Scopo del corso è quello di fornire gli strumenti formali e le nozioni fondamentali per studiare problemi trattabili e non mediante calcolatore. Il corso è strutturato in 2 parti. Nella prima parte viene presentata la teoria degli automi e dei linguaggi formali, teoria a fondamento della descrizione e dell'implementazione dei linguaggi di programmazione. La seconda parte delinea i concetti e la natura dei problemi che ammettono soluzione effettiva, ovvero dei problemi risolvibili mediante calcolatore.

Propedeuticità consigliate: Il corso ha come prerequisiti i corsi del I e II anno. Esso è propedeutico per tutti i corsi di informatica teorica, in particolar modo per i corsi di complessità, analisi e verifica automatica di sistemi, sicurezza e crittografia, i corsi di linguaggi e compilatori, intelligenza artificiale, deduzione automatica, semantica, modelli di calcolo non convenzionali, etc.

Programma dettagliato

• Automi e linguaggi formali (I Parte: 25h):
  Linguaggi e grammatiche
  Automi a stati finiti e linguaggi regolari
  Linguaggi liberi da contesto, forme normali e automi a pila
  Classificazione di Chomsky (cenni)

• Calcolabilità (II Parte: 25h):
  Nozione intuitiva di algoritmo
  Modelli formali per il calcolo:
  Macchine di Turing/funzioni ricorsive/programmi While
  Tesi di Church
  Goedelizzazione, Universalità e Teorema s-m-n
  Problemi solubili e non: problema della terminazione
  Metaprogrammazione: compliazione, interpretazione e specializzazione
  Insiemi ricorsivi e r.e.
  Teoremi di Ricorsione e Teorema di Rice
  Riducibilità funzionale: Insiemi completi, creativi e produttivi

Modalità d'esame: Esame scritto ed orale (opzionale). Voto minimo di ammissione all'orale: 16/30. Coloro che non sostengono l'oarale non possono conseguire un voto superiore a 24/30 (incluso) anche se il voto dello scritto fosse superiore. Il voto dello scritto è valido per l'ammissione all'orale solo nell'arco dell'Anno Accademico di riferimento, ovvero una volta scaduto tale termine (ultimo appello di Settembre) lo scritto deve essere risostenuto al fine di essere ammesso all'orale.

In particolare si ricorda che:

• Per verbalizzare un voto è necessario essersi iscritti ad un appello
• Tutti gli esami scritti negli appelli hanno durata di 3h e saranno strutturati in due parti (I e II) separate, secondo la struttura del programma del corso
• È sempre possibile la consegna separata di una delle due parti allo scadere di 1h:30 dall'inizio dell'esame, al fine di migliorare la propria situazione relativamente ad una sola parte
• Tutti i voti sono in 30esimi ed il voto totale degli scritti conseguibile in un appello è una media arrotondata all'intero successivo dei voti in 30esimi ottenuti in ogni sua parte (I e II)
• Chi consegna una o entrambe le parti annulla il corrispondente voto per la corrispondente parte (anche se questo era di valore superiore)
• La situazione dei voti, aggiornata all'ultima consegna avvenuta, anche di una sola parte, è aggiornata di appello in appello e visualizzata negli avvisi relativi al corso
• Gli orali si possono svolgere su appuntamento con il docente dopo aver conseguito almeno 16/30 e comunque NON oltre il 1 Ottobre dell'anno solare corrente. Oltre tale data non sarà possibile svolgere l'esame orale
• Non vengono verbalizzati voti inferiori a 18/30
• Per avere un voto finale superiore a 24/30 è necessario l'orale
• I voti conseguiti nell'A.A. corrente sono validi fino e NON oltre il 1 Ottobre dello stesso anno. Chi avesse sostenuto l'esame e non avesse verbalizzato il voto entro tale data dovrà risostenere gli scritti nel successivo anno accademico

Testi di consultazione ad integrazione della dispensa:

• Hopcroft and Ullman, "Introduction to Automata Theory, languages and computation", Addison Wesley, 1979
• Jones, "Computability and Complexity", MIT Press, 1997
• Rogers, "Theory of recursive functions and effective computability", MIT Press, 1988
• Kleene, "Introduction to meta-mathematics", North Holland, 1952
• Odifreddi, "Classical recursion theory", Elsevier North-Holland, 1989