Fondamenti di informatica

Modalità d'esame, aggiornamento

In considerazione di richieste pervenute e al fine di facilitare per quanto possibile lo svolgimento dell'esame, è consentito sostenere le tre prove dell'esame stesso (due scritti e un orale) nell'arco di (al più) tre appelli di esame consecutivi. Prove scritte superate, in mancanza di superamento della prova orale (e quindi dell'esame) entro i due appelli successivi, dovranno essere quindi sostenute di nuovo. Gli scritti superati nelle prove di esonero saranno considerati come sostenuti nel primo appello estivo.

Pubblicato il testo della prova scritta, primo modulo, del 15-7-2015, con soluzioni.

Pubblicati i risultati della prova scritta, primo modulo, del 15-7-2015.

Pubblicati i risultati della prova scritta, primo modulo, del 15-6-2015.

Pubblicato il testo della prova scritta, primo modulo, del 15-6-2015, con soluzioni.

Lezione del 01/06 annullata

Si avvisano gli studenti che, contrariamente a quanto comunicato a lezione, la lezione di lunedì 1 giugno non avrà luogo. Detta lezione è rimandata al giorno 3 giugno.

Mdalità d'esame

1) ORARI. Si informano gli studenti che, salvo diversa comunicazione, le prove scritte dei due moduli avranno sempre luogo nella stessa data: la prova scritta del PRIMO modulo avrà inizio alle ore 14 e la prova scritta del SECONDO modulo avrà inizio alle ore 10.

2) PROVA ORALE. La prova orale avviene congiuntamente per i due moduli. In generale, la prova orale deve aver luogo nello stesso appello in cui si sostiene la prova scritta. Fanno eccezione i due appelli della sessione estiva.

Più precisamente:

• scritto nell'appello di giugno: orale nell'appello di giugno o in quello di luglio;
• scritto nell'appello di luglio: orale nell'appello di luglio o in quello di settembre;
• scritto nell'appello di settembre:  orale nell'appello di settembre;
• scritto nell'appello di febbraio:  orale nell'appello di febbraio.

Si avvisano gli studenti che, per motivi di salute della docente, la lezione del 16/03/2015 non avrà luogo.

Pubblicato i risultati dell'esonero del 25-2-2015.

Pubblicato il testo dell'esonero del 25-2-2015, con soluzioni.

Pubblicato i risultati dell'esonero del 10-2-2015.

Pubblicato il testo dell'esonero del 10-2-2015, con soluzioni.

La prova di esonero del 10-2-2015 è posticipata dalle ore 16 alle ore 16.30

Prove di esonero

Le due prove di esonero relative alla parte di corso svolta nel primo semestre si terranno il 10-2-2015 alle ore 16 e il 25-2-2015 alle ore 10, in aula T5 in entrambi i casi.

Si prega, per motivi organizzativi, di comunicare al docente via email, entro 2 giorni prima della data dell'esonero, la propria intenzione di sostenere la prova, specificando nome, cognome e numero di matricola.

IMPORTANTE. La prova di esonero è riservata agli studenti che dovranno sostenere, a partire dalla sessione estiva, l'esame per il corso di FO da 12 cfu: gli studenti che abbiano nel loro piano di studi il precedente insegnamento di FO da 6 cfu devono sostenere l'esame per tale corso nel relativo appello, con il Prof. Intrigila.

La lezione di oggi, 9-12, è rimandata a data da definire.

All'indirizzo http://www.idt.mdh.se/kurser/cd5560/14_11/examination/KOMPENDIER/Regular/kompendium_engl.pdf è disponibile un utile elenco di problemi e soluzioni sui linguaggi regolari e i diversi modelli ad essi associati (ASF, Grammatiche regolari, ER). In inglese.

Pubblicata una breve nota sull'algebra delle espressioni regolari.

Messo a disposizione documento pdf con problemi sulle conoscenze richieste per il corso (logica, teoria degli insiemi, relazioni e funzioni, dimostrazioni induttive e per assurdo, insiemi numerabili e non numerabili).

Il problema Dominating Set (definizione). Esercitazione.

Il problema Partizione: problemi numerici, algoritmi pseudo-polinomiali e NP-completezza in senso debole. Tsp e NP-completezza in senso forte. Restrizioni polinomiali e non: la questione delle costanti.

Prove di NP-completezza: problemi di colorabilità, Hamiltonoan Circuit (solo enunciato), Hamiltonian Path, Longest Path, TSP

Prove di NP-completezza: i problemi Vertex Cover, Independent set, Clique

Dimostrazioni di NP-completezza. NP-completezza di 3SAT. Esistenza di problemi NP-intermedi: il teorema di Ladner (solo enunciato)

Il teorema di Cook-Levin

La classe NP: algoritmi non deterministici e definizione alternativa della classe NP

Problemi decisionali complemento. Complessità dell'insieme delle istanze. La classe P.

Tipi di problemi. Problemi decisionali. Codifiche, codifiche ragionevoli. Problemi decisionali e linguaggi: decisione dell'insieme delle istanze.

Classi complemento. P=coP e congettura NP diverso da coNP. Ciusura di NP e coNP rispetto alla riducibilità polinomiale. Linguaggi coNP-completi.

Pricipali classi di complessità e loro relazioni di inclusione debole. Separazione di P e EXPTIME. Congettura "P diverso da NP". Riduzioni polinomiali, chiusura di P e linguaggi NP-completi.

Esempi di funzioni time-constructible. Teoremi di compressione e di accelerazione

Classi di complessità non deterministiche. Relazioni fra classi di complessità. Gap theorem e funzioni space- e time-constructible

Misure di complessità e loro relazioni. Relazione fra i diversi modelli di calcolo rispetto alle misure di complessità spazio e tempo. Classi di complessità deterministiche

Accettabilità, decidibilità e riduzioni. Esercitazione: simulazione di una macchina di Turing non deterministica mediante un programma scritto in linguaggio PacalMinimo

L'Halting Problem

Insiemi numerabili e non numerabili e il Teorema di Cantor

La tesi di Church Turing. Il modello di calcolo PascalMinimo e la sua equivalenza con il modello macchina di Turing

Linguaggi accettabili, linguaggi decidibili, funzioni calcolabili

La Macchina di Turing Universale.

Modelli equivalenti di macchine di Turing: macchine deterministiche e non deterministiche, macchine a k nastri e ad un solo nastro, macchine definite su un alfabeto qualsiasi e macchine definite su un alfabeto binario.

Stati globali, transizioni, computazioni di una macchina di Turing. Struttura dell'insieme delle quintuple: totalità e non determinismo.

Introduzione alla calcolabilità: relazione fra calcolabilità e linguaggio formale. Dal concetto di operazione elementare alla macchina di Turing: una macchina che decide se una parola è palindroma.

Macchine di Turing non deterministiche. Equivalenza tra MdT e NMdT. Equivalenza tra linguaggi accettati da MdT e linguaggi di tipo 0.

Macchine di Turing multitraccia e multinastro. Simulazione mediante MdT ad un nastro e una traccia.

Definizione di macchina di Turing. Esempi di MdT. Accettazione e decisione su MdT.

Analisi sintattica. Parsing a discesa ricorsiva (cenni). L'algoritmo Cocke- Yunger-Kasami.

Analisi sintattica. Grammatiche e linguaggi ambigui. XML come esempio di formalismo basato su grammatiche CF

Forma normale di Greibach. Equivalenza tra grammatiche CF e automi a pila non deterministici. Esistenza di linguaggi accettati da NPDA e non accettati da DPDA.

Pumping lemma per i linguaggi CF. Proprietà di chiusura dei linguaggi CF.

Automi a pila (PDA) deterministici e non deterministici. Accettazione per pila vuota e per stato finale: equivalenza.

Grammatiche CF in forma ridotta. Eliminazione di produzioni unitarie e di simboli inutili. Forma normale di Chomsky.

Esempio di minimizzazione di un ASF. Linguaggi context-free. Alberi sintattici. Grammatiche in forma ridotta.

Minimizzazione di automi a stati finiti. Il teorema di Myhill-Nerode.

Esempio di derivazione di ER da ASF. Predicati decidibili su linguaggi regolari.

Esempi di uso del pumping lemma per linguaggi regolari. Equivalenza tra ASF ed espressioni regolari.

Pumping lemma per linguaggi regolari. Proprietà di chiusura dei linguaggi regolari

Esempi di riduzione ASFND-ASFD. Equivalenza tra ASF e grammatiche di tipo 3.

Esempi di ASFD e ASFND. Equivalenza tra ASFD e ASFND.

Esempi di ASFD. Automi a stati finiti non deterministici. Configurazioni di un ASFND. Stringhe accettate da un ASFND. Linguaggi accettati da ASFND.

Automi a stati finiti deterministici. Stato interno. Configurazioni di un ASFD. Computazioni di un ASFD. 

Gerarchia di Chomsky. Automi: definizioni generali. Stato interno, configurazioni di un automa, funzione di transizione.

Grammatiche e linguaggi. Simboli terminali e non terminali. Produzioni. Derivazioni. Tipi di grammatiche.

Espressioni regolari. Esempi ed esercizi.

Linguaggi formali. Operazioni sui linguaggi formali (unione, intersezione, complemento, concatenazione, potenza, stella di Kleene). Espressioni regolari.

Richiami di teoria degli insiemi. Dimostrazioni per induzione. Insiemi infiniti, numerabili e non numerabili. Diagonalizzazione. Definizione di linguaggio formale.

Introduzione al corso. Richiami di calcolo proposizionale.

Il programma enunciato di seguito è solo approssimativo. Argomenti ulteriori potrebbero essere inseriti durante il corso e/o, corrispondentemente, argomenti di minor rilevanza, elencati sotto, potrebbero essere omessi.

Modulo 1

- Fondamenti matematici: logica, insiemi, relazioni, funzioni, strutture algebriche fondamentali

- Insiemi finiti e infiniti; numerabilità e non numerabilità di insiemi

- Caratteristiche elementari dei linguaggi

- Grammatiche di Chomsky e loro gerarchia

- Generazione ed accettazione di linguaggi

- Riconoscimento di linguaggi: automi

- Automi a stati finiti determinitici e non deterministici; equivalenza tra essi

- Relazioni tra automi a stati finiti e grammatiche di tipo 3 (regolari)

- Pumping lemma per i linguaggi regolari

- Proprietà di chiusura dei linguaggi regolari

- Predicati decidibili sui linguaggi regolari

- Espressioni regolari e loro equivalenza con gli automi a stati finiti e con le grammatiche regolari

- Minimizzazione di automi a stati finiti

- Linguaggi context free

- Grammatiche di tipo 2: forme ridotte e forme normali (Chomsky, Greibach)

- Pumping lemma per i linguaggi context free

- Automi a pila e linguaggi context free

- Automi a pila deterministici 

- Ambiguità

- Analisi lessicale e sintattica

- Introduzione alle Macchine di Turing

- Linguaggi di tipo 1 e automi lineari

- Linguaggi di tipo 0 (ricorsivamente enumerabili) e Macchine di Turing

Modulo 2

Parte 1, calcolabilità:

- Ancora sulle Macchine di Turing: trasduttori e riconoscitori, Macchine ad un nastro e a k nastri, Macchine  deterministiche e non deterministiche. Macchina di Turing universale.
- Linguaggi e funzioni. Linguaggi e linguaggi complemento. Accettabilità e decidibilità di linguaggi. Calcolabilità di funzioni. La tesi di Church-Turing e modello di calcolo equivalenti alla macchina di Turing.

- Cardinalità di insiemi. Insiemi numerabili e non numerabili. Diagonalizzazione.
- Linguaggi non decidibili. 

- Riducibilità tra linguaggi

Parte 2, complessità:

- Misure di complessità: DTIME, DSPACE, NTIME, NSPACE.
- Classi di linguaggi. Gap theorem e funzioni time-constructible. Teoremi di compressione e di accelerazione. Definizione delle classi di complessità spaziale e temporale: P, NP, PSPACE, NPSPACE, EXP, coNP. Inclusione, inclusione propria, coincidenza. Completezza.

- Problemi e codifiche. Problemi decisionali e loro complemento.
- La classe P. Riducibilità polinomiale e chiusura di P rispetto alla riducibilità polinomiale. Problemi in P: 2-SAT, 2-COLORABILITA'. Funzioni in FP: trasformazione di una funzione booleana in forma congiuntiva normale.
- La classe NP. Linguaggi NP-completi e Teorema di Cook. Chiusura rispetto alla riduzione polinomiale. Esempi di dimostrazioni di NP-completezza: 3-SAT, Vertex Cover, 3-Colorability, Colorability, Independent Set, Clique, Hamiltonian Circuit/Path, Longest Path, Commesso Viaggiatore. Problemi NP-intermedi: il teorema di Ladner.

- Algoritmi pseudo-polinomiali, problemi numerici e NP-completezza in senso forte; il problema PARTIZIONE.

G. Ausiello, F. D'Amore, G. Gambosi, L. Laura "Linguaggi, Modelli, Complessità" nuova edizione. Franco Angeli, 2014. ISBN 978-88-917-0553-2.

Materiale a cura del docente.

Per il secondo modulo: materiale didattico a cura del docente.

Al termine delle lezioni. E' possibile inoltre richiedere un appuntamento via mail.

Scritto e orale. E' prevista una prova di esonero (opzionale) scritto relativo alla prima parte del corso. Per l'iscrizione all'esame è richiesta la prenotazione sul sito delphi.uniroma2.it