Sillabo dell'insegnamento

• A - Fondamenti
* ALF - Automi e Linguaggi Formali
Scopo del corso: approfondire alcuni concetti di informatica teorica svolti nei corsi della laurea triennale.Linguaggi e grammatiche. La Gerarchia di Chomsky. Varianti della nozione di automa finito e di linguaggio formale. Cenni agli automi probabilistici e ai linguaggi fuzzy. Cenni a sottoclassi dei linguaggi regolari.
* CAL - Calcolabilita'
Centralità della nozione di calcolabilità. Enunciato e discussione della tesi di Church-Turing alla luce della distinzione tra explicandum ed explicatum di Rudolf Carnap. Il problema del Busy Beaver e sua indecidibilità. Ruolo e significato dei teoremi centrali della teoria della calcolabilità. I teoremi limitativi. I teoremi di ?universalità?.
COM - Complessita'
Cenni al decimo problema di Hilbert e agli insiemi diofantei. Il teorema di Matjasievic. Il problema della complessità in generale. La complessità strutturale di Kolmogorov, Solomonov e Chaitin. Possibili applicazioni. Impostazioni innovative per la riduzione della complessità.
COM - Complessita'
La complessità astratta. Gli assiomi di Blum. Significato di alcuni teoremi centrali. Teorema del collegamento ricorsivo tra misure di complessità. Teorema della lacuna. Teorema dell'accelerazione. La complessità concreta. Il teorema di Cook e la tesi di Cook-Karp come ?analogo? della Tesi di Church-Turing. Limiti di tale paragone. I sette Problemi del Millennio come riproposizione dei problemi di Hilbert al Convegno del 1900.
COM - Complessita'
Il linguaggio di programmazione LOOP di Meyer e Ritchie, come caso di studio per il problema della complessità. Proprietà significative di tale linguaggio. Teoremi di limitazione alla crescita delle variabili. Profondità di nidificazione dei cicli LOOP. Conseguenze teoriche di alcuni di questi risultati.
* CAL - Calcolabilita'
Equivalenze tra diversi modelli di computo e significato di tale equivalenza. Il teorema di ricorsione. Il teorema di Rice. Il teorema della forma normale di Kleene. Sulle tecniche e gli strumenti utilizzati per dimostrare le equivalenze. Analisi del rapporto tra le nozioni di ?ricorsivo? e ?ricorsivamente enumerabile?