FONDAMENTI DI INFORMATICA A - L

Conoscenza e capacità di comprensione (knowledge and understanding): L'obiettivo del corso e' quello di far entrare in contatto lo studente con le principali teorie formali che costituiscono i fondamenti dell'informatica. Lo studente imparera' a comprendere come tutti gli aspetti dell'Informatica applicata siano stati realizzati o influenzati da conoscenze sviluppate a livello teorico.

Capacità di applicare conoscenza e comprensione (applying knowledge and understanding):: Per ogni teoria fondamentale affrontata, allo studente verranno mostrati esempi di suo concreto utilizzo, come l'uso di espressioni regolari in tool di editing e ricerca; l'uso delle grammatiche per lo sviluppo di compilatori; l'uso degli automi per la descrizione del comportamento di circuiti sequenziali; l'uso della logica matematica per la descrizione di specifiche di programmi e l'uso di sistemi formali per la descrizione della semantica dei linguaggi e per le dimostrazioni di correttezza dei programmi. Inoltre, utilizzando elementi di lambda-calcolo e di logica proposizionale, verra' indirizzato alla comprensione della perfetta sovrapposizione esistente tra processi computazionali e processi logico-deduttivi. Questo allo scopo anche di stimolarlo allo studio di materie come analisi e matematica discreta, che potrebbero apparire ad uno studente del primo anno troppo distanti dall'informatica e dalla programmazione.

Autonomia di giudizio (making judgements): Lo studente verra' stimolato a cercare autonomamente quali aspetti dell'informatica teorica vengono utilizzati negli argomenti trattati in corsi piu' apllicativi da lui seguiti nello stesso anno, come Programmazione e Architettura degli elaboratori. Verra' inoltre stimolato a comprendere come gli argomenti di corsi come Elementi di analisi matematica e Matematica discreta potrebbero venire formalizzati nella logica matematica.

Abilità comunicative (communication skills): lo studente acquisira' la capacita' di esprimere in maniera formale e non ambigua argomentazioni di tipo scientifico.

Capacità di apprendimento (learning skills): Lo studente sara' messo in condizione di poter affrontare autonomamente lo studio di argomenti teorici descritti formalmente.

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

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

Scritto e orale

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