FONDAMENTI DI INFORMATICA

Conoscenza di base delle teorie fondamentali dell'informatica.

Capacita' di comprensione del significato degli aspetti teorici dell'informatica.

Capacita' di utilizzare nozioni teoriche in contesti applicativi.

Capacita' di valutare, giudicare e comunicare metodologie e tecniche informatiche nel contesto piu' generale ed astratto delle teorie fondazionali.

Nessuno.

No.

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 della teoria dei modelli.
• Introduzione formale ai risultati limitativi della logica: Goedel, Tarski, Church.
• Induzione, induzione completa, induzione ben fondata e suo utilizzo nelle dimostrazioni di correttezza
• Corrispondenza tra Induzione e Ricorsione: un cenno
• Un frammento decidibile della logica del primo ordine: clausole di Horn e cenni di Prolog

Semantica dei linguaggi di programmazione:

• Semantica Operazionale Strutturata

Scritto e orale

http://www.dmi.unict.it/~barba/FONDAMENTI/ESERCIZI/index.html