Fondamenti di informatica

La lezione del giorno mercoledì 4 aprile 2018 non avrà luogo.

Pubblicati i risultati della prova scritta di esonero del primo modulo e di esame del corso di 6 cfu. Si ricorda che gli studenti che hanno ottenuto la sufficienza (almeno 18) possono, volendo, sostenere il colloquio orale previsto per il 6-3-18 alle ore 15 nello studio del docente o, in alternativa, mantenere il voto ottenuto. Gli studenti che hanno ottenuto un voto compreso tra 15 e 17 devono, per superare l'esame, sostenere il colloquo orale. Si pregano gli studenti che intendono sostenere il colloquo orale di comunicarlo al docente via email. In assenza di comunicazione, si manterrà traccia del voto ottenuto, se sufficiente.

Colloqui orali primo modulo

I colloqui orali relativi al secondo esonero della del primo modulo, del 21-2-2018, sono rimandati a martedì 6 marzo alle 15.00 presso lo studio del docente. I risultati della relativa prova scritta saranno pubblicati nei prossimi giorni.

Prove scritte del 21-2-2018

Le prove scritte relative al corso di Fondamenti di Informatica del 21-2-2018 avranno luogo con il seguente orario:

- ore 10.00 in aula T5 per il secondo modulo

- ore 14.00 in aula T5 per il primo modulo

Pubblicati i risultati della prova scritta di esonero del primo modulo e di esame del corso di 6 cfu. Si ricorda che gli studenti che hanno ottenuto la sufficienza (almeno 18) possono, volendo, sostenere il colloquio orale previsto per il 14-2-18 o, in alternativa, mantenere il voto ottenuto. Gli studenti che hanno ottenuto un voto compreso tra 15 e 17 devono, per superare l'esame, sostenere il colloquo orale. Si pregano gli studenti che intendono sostenere il colloquo orale di comunicarlo al docente via email. In assenza di comunicazione, si manterrà traccia del voto ottenuto, se sufficiente.

Prove scritte del 9-2-2018

Le prove scritte relative al corso di Fondamenti di Informatica del 9-2-2018 avranno luogo con il seguente orario:

- ore 10.00 in aula T5 per il secondo modulo

- ore 15.00 in aula T5 per il primo modulo

Una cartella condivisa contenente i testi di esami precedenti è accessibile a questo indirizzo

Le lezioni del primo modulo del corso riprenderanno Lunedì 30 ottobre 2017 alle ore 9 in aula 6PP2, con una prima lezione di recupero delle lezioni perse per causa di forza maggiore

A partire da mercoledì 11 ottobre, le lezioni avranno luogo presso l'aula 6, edificio PP2.

Le lezioni di martedì 10, martedì 17 e mercoledì 18 ottobre non avranno luogo. Saranno recuperate in seguito, in date da definire. La lezione di mercoledì 11 avrà regolarmente luogo.

Funzioni time-constructible (definizione). Relazione fra le classi NTIME e le classi DTIME. Classi complemento. Gerarchie di complessità relativamente alla funzione limite: enunciato del Gap-theorem. Teorema di compressione lineare.

Introduzione alla teoria della complessità. Misure di complessità e assiomi di Blum. Le misure dtime, dspace, ntime, nspace: definizioni, loro relazioni e indipendenza dal modello di calcolo. Classi di complessità DTIME[f(n)], DSPACE[f(n)], NTIME[f(n)], NSPACE[f(n)]: definizioni e relazioni fra classi detereministiche e fra classi non detreministiche.

Halting problem: accettabilità e non decidibilità. Riducibilità many-to-one fra linguaggi ed applicazioni alle porve di accettabilità/decidibilità o non accettabilità/decidibilità

Prova dell'esistenza di linguaggi non accettabili. Esercitazione: programma in Pascal minimo che simula una computazione non deterministica.

Cardinalità di insiemi e numeri transfiniti. Insiemi numerabili: sottoinsiemi, unione, prodotto cartesiano. Insieme delle parti di un insieme numerabile: la diagonalizzazione di Cantor.

La tesi di Church-Turing. Il linguaggio Pascal minimo e sua equivalenza con il modello di calcolo Macchina di Turing. Descrizione della Macchina di Turing Universale in Pascal minimo

Linguaggi e funzioni. Linguaggi complemento. Accettabilità e decidibilità di linguaggi. Calcolabilità di funzioni

La Macchina di Turing Universale. Esercitazione: macchina di Turing che, con input i due numeri binari x e y, decide se x=2y

Equivalenza fra macchine deterministiche e macchine non deterministiche. Rappresentazione di una macchina di Turing mediante una parola di un opportuno alfabeto. Introduzione alla Macchina di Turing Universale.

Equivalenza fra macchine definite su un alfabeto generico e macchine definite sull'alfabeto binario. Completezza dell'insieme delle quintuple. Macchine di Turing non deterministiche (di tipo riconoscitore): grado di non determinismo, albero delle computazioni, accettazione e rigetto

Macchine di Turing di tipo trasduttore e macchine di tipo riconoscitore. Equivalenza fra macchine a k nastri e macchine ad un nastro. Stato globale, computazione e esito di una computazione di una macchina di Turing.

Modulo 2. Introduzione alla calcolabilità: dai sillogismi al concetto di calcolo automatico. Introduzione alle macchine di Turing: macchine a 3 nastri e a 1 nastro per il calcolo della somma di due numeri.

Mod. 2. Dispensa 6: Linguaggi e complessità

Mod. 2. Dispensa 5: l'Halting Problem.

Mod. 2. Dispensa 4: cardinalità di insiemi

Mod. 2. Dispensa 2: macchine di Turing e Macchina di Turing Universale

Mod. 2. Dispensa 1: introduzione alla calcolabilità

Mod. 2. Dispensa 3: Funzioni calcolabili e linguaggi decidibili

Risultati prova scritta d'esonero, primo modulo Fondamenti di Informatica (12 cfu), del 21-2-2018.

Testo prova scritta primo modulo del 21-2-2018, con soluzioni corrette

Risultati prova scritta d'esame, Fondamenti di Informatica (6 cfu), del 21-2-2018

Testo prova di esame del 9-2-2018, con soluzioni

Risultati prova scritta d'esame, Fondamenti di Informatica (6 cfu), del 9-2-2018.

Risultati prova scritta d'esonero, primo modulo Fondamenti di Informatica (12 cfu), del 9-2-2018.

Esercizi sui linguaggi context free

Slide sui linguaggi context free

Esercizi sugli automi a stati finiti

Esercizi sui linguaggi linguaggi regolari

Quiz sui fondamenti matematici

Slide sugli automi

Slide sugli automi a stati finiti

Slide sui linguaggi

Slide di richiami matematici

Slide di introduzione al corso

Primo modulo

- 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 

Secondo modulo

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.

Modulo 1

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

Modulo 2

Dispense a cura del docente, disponibili in questa pagina.

Per consultazione: il testo utilizzato nel modulo 1.

Modulo 1

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

Modulo 2

Al termine della lezione del mercoledì. E' possibile inoltre richiedere un appuntamento via mail.

L'esame prevede una coppia di prove (scritto e colloquio orale) relative al primo modulo e una coppia di prove (scritto e colloquio 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. Per l'iscrizione all'esame è richiesta la prenotazione sul sito delphi.uniroma2.it

Sono previsti per il corso di Fondamenti di Informatica due appelli di esame per ciascuna sessione. Tuttavia, per ognuno dei due moduli ciascuno studente potrà sostenere un numero massimo di quattro prove di esame nel corso di un anno accademico. In particolare, potrà sostenere l'esame relativo ad un modulo in entrambi gli appelli della sessione immediatamente successiva al termine delle lezioni del modulo stesso. Per quanto riguarda le altre sessioni, le date a disposizione saranno due, ma lo studente potrà sostenere l'esame in una sola delle due date.

Nel dettaglio:

Modulo 1:

• due appelli di esame a disposizione nella sessione estiva anticipata (febbraio) - ciascuno studente può sostenere l'esame in entrambi gli appelli
• due appelli di esame a disposizione nella sessione estiva (giugno) - ciascuno studente può sostenere l'esame in un solo appello a sua scelta
• due appelli di esame a disposizione nella sessione autunnale (settembre) - ciascuno studente può sostenere l'esame in un solo appello a sua scelta

Modulo 2:

• due appelli di esame a disposizione nella sessione estiva (giugno) - ciascuno studente può sostenere l'esame in entrambi gli appelli
• due appelli di esame a disposizione nella sessione autunnale (settembre) - ciascuno studente può sostenere l'esame in un solo appello a sua scelta
• due appelli di esame a disposizione nella sessione invernale (febbraio) - ciascuno studente può sostenere l'esame in un solo appello a sua scelta

Informazioni specifiche alla prova di esame per il 1 modulo

La prova scritta di esame prevede l'assegnazione di un punteggio compreso tra 0 e 33. Gli studenti che otterranno un punteggio maggiore o uguale a 18 potranno, se vorranno, mantenere tale punteggio come voto per il modulo (30 e lode se il punteggio è maggiore di 30), non sostenendo la prova orale. Gli studenti con punteggio della prova scritta pari a 15, 16 o 17 dovranno necessariamente, per superare l'esame, sostenere la prova orale e raggiungere, nella valutazione scritto+orale, la sufficienza.

Informazioni specifiche alla prova di esame per il 2 modulo

La prova scritta di esame prevede l'assegnazione di un punteggio compreso tra 0 e 30. Gli studenti che otterranno un punteggio compreso fra 18 e 24 potranno, se vorranno, mantenere tale punteggio come voto per il modulo, non sostenendo la prova orale. Gli studenti che otterranno un punteggio compreso fra 25 e 30 potranno, se vorranno, avere riconosciuto il voto 24, non sostenendo la prova orale. In entrambi i casi, gli studenti hanno facoltà di sostenere la prova orale se intendo provare ad incrementare il voto.

Infine, gli studenti con punteggio della prova scritta pari a 15, 16 o 17 dovranno necessariamente, per superare l'esame, sostenere la prova orale e raggiungere, nella valutazione scritto+orale, la sufficienza.