Fondamenti di informatica

Pubblicati i risultati della prova scritta del primo modulo e dell'appello straordinario per l'esame a 6 cfu, 12-9-2016

La prova orale del primo modulo del corso, per la sessione autunnale, avrà luogo il 21-9-2016 a partire dalle ore 14, presso lo studio del Prof. Gambosi.

Prova scritta di esame del 12-09-2016

Le prove scritte dei due moduli di esame per l'appello della sessione autunnale del 12-9-2016 avranno luogo secondo il seguente orario:

- ore 10:00 per il secondo modulo

- ore 14:00 per il primo modulo

Pubblicati i risultati della prova scritta del primo modulo e dell'appello straordinario per l'esame a 6 cfu, 18-7-2016

Inserito testo prova di esame del 18-7-2016, con soluzioni

Le prove scritte dei due moduli di esame per il secondo appello della sessione estiva avranno luogo, come previsto, il 18-7-2016 secondo il seguente orario:

- ore 9.00 per il primo modulo

- ore 11.30 per il secondo modulo

Pubblicati i risultati della prova scritta del primo modulo e dell'appello straordinario per l'esame a 6 cfu, 4-7-2016

Inserito testo prova di esame del 4-7-2016, con correzione di una delle soluzioni

Si avvisano gli studenti che la lezione di Fondamenti di Informatica di domani, 19 maggio, è rinviata a venerdì 27 maggio, dalle 9 alle 11.

Inserito elenco risultati esonero 1 modulo del 4-3-2106

Il testo, con soluzioni, dell'esonero del 4-3-2016 è stato inserito nella cartella condivisa relativa alle prove precedenti

In relazione alle nuove modalità di esame, per quanto riguarda il 1 modulo del corso, si chiarisce che:

- la nuova disciplina si applica a partire dal primo appello della sessione estiva. A partire da esso gli studenti sosterrano la prova scritta e (se superato lo scritto) un colloquio orale nello stesso appello.

- nel transitorio, gli studenti che hanno già superato la prova scritta in precedenza e coloro che la supereranno nell'esonero del 4-3-2016 dovranno sostenere il relativo colloquio in corrispondenza alla prova orale prevista per il primo appello della sessione estiva (giugno). Si pregano gli studenti interessati ad inviare comunicazione via mail al docente, nei giorni precedenti l'appello stesso, dell'intenzione di sostenere l'orale.

- nulla cambia per gli studenti che devono sostenere l'esame del vecchio corso di Fondamenti di Informatica (6 cfu), per il quale è già prevista una prova scritta (il 4-3, in corrispondenza alla prova scritta di esonero per il corso da 12 cfu) e un colloquio orale (il 7-3).

Verificata la difficoltà di molti studenti a rispettare i vincoli relativi alla vicinanza temporale nel sostenere i due moduli, i docenti hanno convenuto sull'opportunità di permettere di sostenere le prove di esame relative ai due moduli indipendentemente secondo le modalità descritte nella sezione apposita. 

Inserito elenco risultati prova scritta 1 modulo 17-2-2106

IMPORTANTE. Su richiesta di alcuni studenti, la prova scritta parziale relativa al primo modulo del corso (e la contemporanea prova scritta relativa all'appello straordinario del corso di Fondamenti di Informatica da 6 CFU) è rimandata ulteriormente al 4-3-2016, alle ore 10, in aula T4. La prova orale per il corso di Fondamenti di Informatica da 6 CFU avrà luogo il 7-3-2016 alle ore 10, nello studio del Prof. Gambosi.

IMPORTANTE. La prova scritta parziale relativa al primo modulo del corso (e la contemporanea prova scritta relativa all'appello straordinario del corso di Fondamenti di Informatica da 6 CFU) è rimandata dal 26-2-2016 al 2-3-2016, alle ore 10, in aula T4. La prova orale per il corso di Fondamenti di Informatica da 6 CFU avrà luogo il 4-3-2016 alle ore 10, nello studio del Prof. Gambosi.

Il testo, con soluzioni, dell'esonero del 9-2-2016 è stato inserito nella cartella condivisa relativa alle prove precedenti

Inserito elenco risultati esonero 9-2-2106

Si comunica che è stato attivato un appello straordinario di esame per il corso di Fondamenti di Informatica (6 cfu). Le date previste sono il 26/2 h 10.00 aula T7 (in corrispondenza al secondo parziale del corso da 12 cfu) per lo scritto e il 29/2 h 10.00 nell'ufficio del Prof. Gambosi per l'orale. Resta inteso che gli studenti che hanno partecipato all'esonero tenuto il 9/2 possono, se vogliono, mantenere il risultato di tale prova e sostenere la sola prova orale, prenotandosi comunque per l'esame su Delphi.

Le prove parziali (scritte) per la prima parte del corso avranno luogo il 9-2-2016 e il 26-2-2016 in aula T7, alle ore 10. Si pregano gli interessati a sostenerle di informare il docente via mail entro il giorno precedente alla data della prova, all'indirizzo giorgio.gambosi@uniroma2.it

Inserita nella relativa cartella raccolta di quiz sui linguaggi CF.

Inserito nella cartella condivisa documento su algebra delle espressioni regolari.

Inserito nella cartella condivisa documento dimostrazioni.

Inserito nella cartella condivisa documento su ASF con epsilon-produzioni.

Creata cartella condivisa per altro materiale, raggiungibile a questo link.

Inserita nella relativa cartella raccolta di quiz sugi automi a stati finiti.

Inserita nella relativa cartella raccolta di quiz sui linguaggi regolari.

Inserita nella relativa cartella raccolta di quiz sui fondamenti matematici del corso.

Creata cartella condivisa per raccolte di esercizi, raggiungibile a questo link.

I testi delle prove scritte relative allo scorso a.a., con le relative soluzioni, sono disponibili nella cartella condivisa raggiungibile attraverso questo link.

Modulo 2. Esercitazione

Modulo 2. Esercitazione sulle prove di NP-completezza: Hamiltonian Path, Longest Path, Colorability e k-Colorability (k > 3), problemi di soddisfacibilità

Modulo 2. Problemi NP-intermedi: enunciato del teorema di Lader. Il problema Partizione. Problemi numerici, algoritmi pseudo-polinomiali e NP-completezza in senso forte o debole. NP-completezza in senso forte del problema Commesso Viaggiatore (TSP)

Modulo 2. Prove di NP-completezza: Insieme Indipendente, Clique, Dominating Set, 3-Colorabilità

Modulo 2. Prove di NP-completezza: i problemi 3SAT e Vertex Cover.

Il teorema di Cook-Levin.

Modulo 2. La classe NP: esempi di problemi in NP e definizione alternativa di NP.

Modulo 2. Complessità dei problemi: il linguaggio delle istanze. Problemi complemento. La classe P: esempi (2SAT e 2COL), riduzione polinomiale da 2COL a 2SAT.

Modulo 2. Linguaggi e problemi, tipi di problemi (di ricerca, ottimizzazione, enumerazione, decisione), problemi decisionali e linguaggi, problemi e codifiche

Modulo 2.  Riducibilità polinomiale e classe dei linguaggi NP-completi. La classe coNP, la congettura NP diverso da coNP, linguaggi coNP-completi.

Modulo 2. PSPACE=NPSPACE. Chiusura di una classe rispetto ad una riduzione, completezza di un liguaggio per una classe rispetto ad una riduzione.

Modulo 2. Classi di complessità complemento. Le classi P, NP, PSPACE, NPSPACE, EXPTIME, NEXPTIME e loro relazioni. Inclusione stretta di P in EXPTIME

I teoremi di compressione e di accelerazione.

Ancora sulle relazioni fra classi di complessità. Funzioni time- e space constructible: definizioni ed esempi (polinomio, esponenziale)

Misure di complessità: assiomi di Blum, dtime, dspace, ntime, nspace, relazioni. Correlazione polinomiale fra i modelli di calcolo. Classi di complessità di linguaggi: DTIME, DSPACE, NTIME, NSPACE e loro relazioni.

Non numerabilità dell'insieme dei linguaggi e numerabilità dell'insieme delle macchine di Turing. Halting Problem: accettabilità e non decidibilità. Riduzioni fra linguaggi.

Modulo 2. Numerabilità dell'unione di una infinità numerabile di insiemi numerabili. Insiemi non numerabili: la tecnica di diagonalizzazione di Cantor e la cardinalità del continuo.

Modulo 2. Esercitazione: simulazione della macchina di Turing Universale e di una macchina non deterministica mediante un programma in linguaggio PascalMinimo. Cardinalità di insiemi: insiemi numerabili, N, Z, Q, sottoinsiemi infiniti di insiemi numerabili, unione e prodotto cartesiano di insiemi numerabili.

Modulo 2. Relazioni fra accettabilità/decidibilità di linguaggi e calcolabilità di funzioni. La tesi di Churcg-Turing e il liguaggio PascalMinimo.

Modulo 2. La macchina di Turing Universale: implementazione. Linguaggi, linguaggi complemento, linguaggi accettabili, linguaggi decidibili. Funzioni (parziali e totali) calcolabili.

Modulo 2. Equivalenza fra non determinismo e determinismo. Introduzione alla macchina di Turing Universale.

Modulo 2. Equivalenza fra macchine di Turing che operano su un alfabeto generico e macchine di Turing che operano su un alfabeto binario. Stato globale di una macchina di Turing. Computazione di una macchina di Turing. Riconoscitori e trasduttori. Completezza dell'insieme delle quintuple. Macchine deterministiche e non deterministiche.

Modulo 2. Equivalenza fra macchine di Turing a k nastri e macchine di Turing ad un nastro.

Modulo 2. Macchina di Turing (ad un nastro) che calcola la somma di due numeri. Introduzione alle macchine a più nastri e macchina a 3 nastri che calcola la somma di due numeri.

Modulo 2. Cenni storici alla calcolabilità. Problemi e algoritmi. Il concetto di operazione elementare. Introduzione alla Macchina di Turing: macchina che verifica se una parola è palindroma.

Esempi di ASF. Automi a stati finiti non deterministici.

Automi a stati finiti. 

Riconoscimento di linguaggi e automi.

Gerarchia di Chomsky. epsilon-produzioni.

Espressioni regolari. Grammatiche generative. Derivazioni. Linguaggio generato da una grammatica.

Numerabilità dell'insieme degli algoritmi. Non numerabilità dell'insieme dei linguaggi: diagonalizzazione. Espressioni regolari.

Introduzione al corso. Linguaggi, problemi, algoritmi, modelli di calcolo.

Programma svolto.

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à

- Cenni sul parsing

- L'algoritmo CYK

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.

Modulo 2. Materiale a cura del docente.

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

L'esame prevede una coppia di prove (scritta e orale) relative al primo modulo e una coppia di prove (scritta e orale) relative al secondo modulo. Ciascuna coppia di prove può essere sostenuta indipendentemente dall'altra. Si richiede però che scritto e orale di ciascun modulo siano sostenuti nello stesso appello.

Il voto finale verrà calcolato come media dei voti conseguiti nelle prove relative ai due moduli.

E' prevista una prova di esonero (opzionale) scritto relativo alla prima parte del corso il cui orale potrà essere sostenuto nell'appello di giugno.

Per l'iscrizione all'esame è richiesta la prenotazione sul sito delphi.uniroma2.it