Elementi di Teoria dei linguaggi formali:


Alfabeto, stringa, linguaggio. Operazioni tra linguaggi. Espressioni regolari. Cardinalita' dei linguaggi.
Grammatiche di Chomsky. Grammatiche ti tipo 0, 1, 2 e 3. Gerarchia di Chomsky. Forma normale di Bakus.
Cosa vuol dire computare
Accettazione e riconoscimento di linguaggi. Automi.
Automi a stati finiti deterministici e non deterministici.
Nota sugli Automi a Stati Finiti
Pumping Lemma per Automi a stati finiti.
Cenni di linguaggi non contestuali.



Modelli computazionali e teoria della calcolabilita':


Macchine di Turing. Maccchina di Turing Universale.
Introduzione alla programmazione funzionale ed al Lambda-calcolo
variabili libere e legate,alfa-equivalenza, sostituzione, beta-riduzione. Definizione di sistema formale. Numerali di Church, funzioni lambda-definibili.
Lambda-definibilita' di funzioni ricorsive. Il teorema di Church-Rosser; unicita' della forma normale, consistenza della teoria della beta-equivalenza.
Il formalismo delle funzioni primitive ricorsive e parziali ricorsive
Introduzione informale alla teoria della ricorsivita' e ad alcuni risultati fondamentali.
Un modello computazionale basato sulla logica: un cenno alla programmazione logica.



Codici e rappresentazione informazione numerica:


Codici e rappresentazione in complemento a due.
Strings vs Numbers



Macchine astratte


Macchine astratte
Realizzazione di macchine astratte; organizzazione a livelli dei sistemi di calcolo.




Logica:


Sistemi formali. Regole derivabili ed amissibili. Alcune proprieta' dei sistemi formali. Consistenza.
La Logica Proposizionale. Principali definizioni e proprieta'. Teorema di deduzione.
Semantica della Logica Proposizionale. Correttezza e completezza.
La Deduzione Naturale per la logica proposizionale.
La corrispondenza dimostrazioni-programmi
La logica dei predicati: linguaggio e semantica.
La logica dei predicati: sostituzioni, deduzione naturale, sistema assiomatico.
Enunciati di alcuni teoremi fondamentali.
Formalizzazione dell'aritmetica e della teoria dei gruppi.
Enunciati di alcuni teoremi fondamentali
Corrispondenza tra Induzione e Ricorsione: un cenno



Semantica dei linguaggi di programmazione:


Semantica Operazionale Strutturata


Fondamenti generali


Il lavoro dell'informatico nel mondo globalizzato. L'importanza di acquisirne una visione non "localistica" e di cogliere tutte le opportunita' per aprire i propri orizzonti nel mondo del lavoro (Erasmus, tirocini all'estero ecc.)

La grande maggioranza dei testi sono in formato elettronico e scaricabili dalla seguente pagina web

programma e materiale didattico

Elementi di Teoria dei linguaggi formali:


Alfabeto, stringa, linguaggio. Operazioni tra linguaggi. Espressioni regolari. Cardinalita' dei linguaggi.
Grammatiche di Chomsky. Grammatiche ti tipo 0, 1, 2 e 3. Gerarchia di Chomsky. Forma normale di Bakus.
Cosa vuol dire computare
Accettazione e riconoscimento di linguaggi. Automi.
Automi a stati finiti deterministici e non deterministici.
Nota sugli Automi a Stati Finiti
Pumping Lemma per Automi a stati finiti.
Cenni di linguaggi non contestuali.



Modelli computazionali e teoria della calcolabilita':


Macchine di Turing. Maccchina di Turing Universale.
Introduzione alla programmazione funzionale ed al Lambda-calcolo
variabili libere e legate,alfa-equivalenza, sostituzione, beta-riduzione. Definizione di sistema formale. Numerali di Church, funzioni lambda-definibili.
Lambda-definibilita' di funzioni ricorsive. Il teorema di Church-Rosser; unicita' della forma normale, consistenza della teoria della beta-equivalenza.
Il formalismo delle funzioni primitive ricorsive e parziali ricorsive
Introduzione informale alla teoria della ricorsivita' e ad alcuni risultati fondamentali.
Un modello computazionale basato sulla logica: un cenno alla programmazione logica.



Codici e rappresentazione informazione numerica:


Codici e rappresentazione in complemento a due.
Strings vs Numbers



Macchine astratte


Macchine astratte
Realizzazione di macchine astratte; organizzazione a livelli dei sistemi di calcolo.




Logica:


Sistemi formali. Regole derivabili ed amissibili. Alcune proprieta' dei sistemi formali. Consistenza.
La Logica Proposizionale. Principali definizioni e proprieta'. Teorema di deduzione.
Semantica della Logica Proposizionale. Correttezza e completezza.
La Deduzione Naturale per la logica proposizionale.
La corrispondenza dimostrazioni-programmi
La logica dei predicati: linguaggio e semantica.
La logica dei predicati: sostituzioni, deduzione naturale, sistema assiomatico.
Enunciati di alcuni teoremi fondamentali.
Formalizzazione dell'aritmetica e della teoria dei gruppi.
Enunciati di alcuni teoremi fondamentali
Corrispondenza tra Induzione e Ricorsione: un cenno



Semantica dei linguaggi di programmazione:


Semantica Operazionale Strutturata


Il lavoro dell'informatico nel mondo globalizzato. L'importanza di acquisirne una visione non "localistica" e di cogliere tutte le opportunita' per aprire i propri orizzonti nel mondo del lavoro (Erasmus, tirocini all'estero ecc.)

La grande maggioranza dei testi sono in formato elettronico e scaricabili dalla seguente pagina web

http://www.dmi.unict.it/barba/FONDAMENTI/PROGRAMMI-TESTI/programmaAAcorrente.html