ComunicazioniRisultati prova scritta 1 modulo del 20-9-201821-09-2018 12:45
Pubblicati i risultati della prova scritta di esame per il 1 modulo del corso, tenuta il 20-9-2018. Si ricorda che gli studenti che hanno ottenuto la sufficienza (almeno 18) possono, volendo, sostenere il colloquio orale previsto per il 26-9-18 alle ore 10 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.
| Risultati prova scritta 1 modulo del 6-9-201808-09-2018 16:12
Pubblicati i risultati della prova scritta di esame per il 1 modulo del corso, tenuta il 6-9-2018. Si ricorda che gli studenti che hanno ottenuto la sufficienza (almeno 18) possono, volendo, sostenere il colloquio orale previsto per il 12-9-18 alle ore 10 nello studio del docente o, in alternativa, mantenere il voto ottenuto. 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.
| Prova scritta modulo 1 del 6-9-201828-08-2018 16:38
La prova scritta di esame relativa al modulo 1 prevista il giorno 6-9-2018 avrà luogo alle ore 15 in aula T5. Si pregano gli studenti interessati a sostenere la prova di inviarne comunicazione all'indirizzo giorgio.gambosi@uniroma2.it
| Risultati prova scritta corso Fondamenti di Informatica (6 cfu) del 9-7-201810-07-2018 23:52
Pubblicati i risultati della prova scritta di esame per il corso di Fondamenti di Informatica (6 cfu), tenuta il 9-7-2018. Si ricorda che gli studenti che hanno ottenuto la sufficienza (almeno 18) possono, volendo, sostenere il colloquio orale previsto per il 12-7-18 alle ore 10 nello studio del docente o, in alternativa, presentarsi per la verbalizzazione del voto ottenuto.
| Risultati prova scritta 1 modulo del 9-7-201810-07-2018 23:50
Pubblicati i risultati della prova scritta di esame del primo modulo, tenuta il 9-7-2018. Si ricorda che gli studenti che hanno ottenuto la sufficienza (almeno 18) possono, volendo, sostenere il colloquio orale previsto per il 12-7-18 alle ore 10 nello studio del docente o, in alternativa, mantenere il voto ottenuto. 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.
| Prova scritta modulo 1 del 9-7-201803-07-2018 16:05
Si precisa che la prova scritta di esame relativa al modulo 1 prevista il giorno 9-7-2018 avrà luogo alle ore 15 in aula T5. Si pregano gli studenti interessati a sostenere la prova di inviarne comunicazione all'indirizzo giorgio.gambosi@uniroma2.it
| 20-06-2018 20:16
Pubblicati i risultati della prova scritta di esame del primo modulo, tenuta il 18-6-2018. Si ricorda che gli studenti che hanno ottenuto la sufficienza (almeno 18) possono, volendo, sostenere il colloquio orale previsto per il 22-6-18 alle ore 10 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.
| Prova scritta modulo 1 del 18-6-201817-06-2018 20:46
Si precisa che la prova scritta di esame relativa al modulo 1 prevista il giorno 18-6-2018 avrà luogo alle ore 15 in aula T5.
| Ricevimento mod.2 7/6/1806-06-2018 14:45
Si avvisano gli studenti che la docente sarà disponibile nel suo studio dalle ore 10:30 alle 13 per chiarire eventuali dubbi degli studenti in previsione dell'esame.
| 28-03-2018 12:02
La lezione del giorno mercoledì 4 aprile 2018 non avrà luogo.
| 25-02-2018 20:53
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 modulo24-02-2018 19:24
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-201815-02-2018 19:01
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
| 11-02-2018 15:12
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-201804-02-2018 15:16
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
| 16-01-2018 23:31
Una cartella condivisa contenente i testi di esami precedenti è accessibile a questo indirizzo
| 22-10-2017 11:55
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
| 06-10-2017 17:17
A partire da mercoledì 11 ottobre, le lezioni avranno luogo presso l'aula 6, edificio PP2.
| 06-10-2017 17:14
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. |
Lezioni24 | 31-05-2018
Prove di NP-completezza: problemi il cui predicato è disgiunzione o congiunzione di predicati di problemi noti, problemi di colorabilità. Il ruolo delle costanti. | 23 | 30-05-2018
Prove di NP-completezza: CAMMINO HAMILTONIANO, LONG PATH, TSP. NP-completezza in senso forte di TSP. Appartenenza a coNPC del complemento di COLORABILITY. Cenno alla prova di NP-completezza di DOMINATING SET. Enunciato del teorema di Ladner e struttura delle classe P, NP, coNP. | 22 | 24-05-2018
Algoritmo pseudo-polinomiale per il problema PARTIZIONE. Problemi numerici. NP-completezza in senso forte e in senso debole. | 21 | 23-05-2018
Prove di NP-completezza: 3SAT, VERTEX COVER, INDEPENDENT SET, CLIQUE. | 20 | 17-05-2018
Appartenenza del problema LONG PATH alla classe NP. | 19 | 16-05-2018
Il teorema di Cook-Levin. Esercizio: Vertex Cover è in NP. | 18 | 10-05-2018
Caratterizzazione alternativa della classe NP. Esercizio: dimostrazione che SAT è in NP | 17 | 09-05-2018
Dalla complessità dei linguaggi alla complessità dei problemi: tipi di problemi, problemi e codifiche, codifiche ragionevoli, complessità del linguaggio delle istanze. | 16 | 03-05-2018
La classe coNP. | 15 | 02-05-2018
PSPACE=NPSPACE. Riduzioni polinomiali, completezza, linguaggi separatori. | 14 | 26-04-2018
Inclusione stretta di P in EXPTIME. | 13 | 19-04-2018
Teorema di accelerazione. Defininizioe di P, NP, PSPACE, NPSPACE, EXPTIME, NEXPTIME e prime relazioni fra loro. | 12 | 18-04-2018
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. | 11 | 12-04-2018
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. | 10 | 11-04-2018
Halting problem: accettabilità e non decidibilità. Riducibilità many-to-one fra linguaggi ed applicazioni alle porve di accettabilità/decidibilità o non accettabilità/decidibilità | 9 | 05-04-2018
Prova dell'esistenza di linguaggi non accettabili. Esercitazione: programma in Pascal minimo che simula una computazione non deterministica. | 8 | 29-03-2018
Cardinalità di insiemi e numeri transfiniti. Insiemi numerabili: sottoinsiemi, unione, prodotto cartesiano. Insieme delle parti di un insieme numerabile: la diagonalizzazione di Cantor. | 7 | 28-03-2018
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 | 6 | 22-03-2018
Linguaggi e funzioni. Linguaggi complemento. Accettabilità e decidibilità di linguaggi. Calcolabilità di funzioni | 5 | 21-03-2018
La Macchina di Turing Universale. Esercitazione: macchina di Turing che, con input i due numeri binari x e y, decide se x=2y | 4 | 15-03-2018
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. | 3 | 14-03-2018
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 | 2 | 08-03-2018
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. | 1 | 07-03-2018
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. |
Materiale didatticoRisultati prova scritta d'esame 1 modulo, del 20-9-2018. | | Risultati prova scritta d'esame 1 modulo, del 6-9-2018. | | Testo prova scritta d'esame modulo 1 del 9-7-2018, con soluzioni. | | Risultati prova scritta d'esame primo modulo del 9-7-2018 | | Risultati prova scritta d'esame appello straordinario Fondamenti di Informatica (6cfu) del 9-7-2018 | | Risultati prova scritta di esame primo modulo del 18-6-018 | | Mod.2. Dispensa 9: La classe NP | | Mod.2. Dispensa 8: La classe P | | Mod. 2. Esercizi: Macchine di Turing | | Mod. 2. Esercizi: Linguaggi accettabili e decidibili | | Mod. 2. Esercizi: Cardinalità di insiemi | | Mod. 2. Esercizi: Linguaggi e complessità | | Mod. 2. Dispensa 7: Linguaggi e problemi | | 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 | | Esercizi sugli automi a stati finiti | | Esercizi sui linguaggi linguaggi regolari | | Quiz sui fondamenti matematici | |
| InformazioniAnno accademico | 2017-2018 |
---|
Crediti | 12 |
---|
Settore | INF/01 |
---|
Anno | 2 |
---|
Semestre | 1-2 |
---|
Propedeuticità | Matematica discreta. |
---|
ProgrammaPrimo 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. |
Testi di riferimentoModulo 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. |
Ricevimento studentiModulo 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. |
Modalità di esameL'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. |
|