ComunicazioniRisultati 1 modulo 20-9-201721-09-2017 21:47
Pubblicati i risultati della prova scritta di esame del 20-9-2017, relativa al 1 modulo e al corso da 6 cfu. Si ricorda che gli studenti che hanno conseguito la sufficienza (almeno 18) possono sostenere l'esame orale previsto per il 25-9 o mantenere il voto conseguito, dandone comunicazione via email al docente. Gli studenti che hanno conseguito un voto pari a 15, 16 o 17 devono sostenere l'esame orale del 25 per raggiungere la sufficienza.
| 02-09-2017 17:07
I Prof. Gambosi e Di Ianni aderiscono allo sciopero proclamato dal Movimento per la Dignità della Docenza Universitaria. L’agitazione consiste nell’astensione dallo svolgimento degli esami di profitto per un appello (il primo nel periodo dal 28-8 al 31-10-2017). Questo corrisponde, per entambi i docenti, all’appello del corso di Fondamenti di Informatica del 4-9-2017 (e, corrispondentemente, all'appello del corso di Informatica Teorica ad esso collegato). Quindi, a meno di revoca dello sciopero stesso, il suddetto appello non avrà luogo. Resta inteso che l’appello successivo del 20-9 si terrà regolarmente e che gli studenti che si sono prenotati per l’appello del 4-9 possono partecipare a quello del 20-9.
| Appello del 04/09/201702-09-2017 17:07
I Prof. Gambosi e Di Ianni aderiscono allo sciopero proclamato dal Movimento per la Dignità della Docenza Universitaria. L’agitazione consiste nell’astensione dallo svolgimento degli esami di profitto per un appello (il primo nel periodo dal 28-8 al 31-10-2017). Questo corrisponde, per entambi i docenti, all’appello del corso di Fondamenti di Informatica del 4-9-2017 (e, corrispondentemente, all'appello del corso di Informatica Teorica ad esso collegato). Quindi, a meno di revoca dello sciopero stesso, il suddetto appello non avrà luogo. Resta inteso che l’appello successivo del 20-9 si terrà regolarmente e che gli studenti che si sono prenotati per l’appello del 4-9 possono partecipare a quello del 20-9.
| Risultati 1 modulo 5-7-201707-07-2017 18:40
Pubblicati i risultati della prova scritta di esame del 5-7-2017, relativa al 1 modulo. Si ricorda che gli studenti che hanno conseguito la sufficienza (almeno 18) possono sostenere l'esame orale previsto per il 12-7 o mantenere il voto conseguito, dandone comunicazione via email al docente. Gli studenti che hanno conseguito un voto pari a 15, 16 o 17 devono sostenere l'esame orale del 12 per raggiungere la sufficienza.
| Prove scritte 5-7-201703-07-2017 00:36
Per il secondo appello della sessione estiva 2016/17, la prova scritta del primo modulo avrà luogo alle ore 14 in aula 4 PP2, mentre la prova scritta del secondo modulo avrà luogo alle ore 10.00, nella stessa aula.
| Risultati 1 modulo 21-6-201722-06-2017 19:23
Pubblicati i risultati della prova scritta di esame del 21-6-2017, relativa al 1 modulo e al corso da 6 cfu. Si ricorda che gli studenti che hanno conseguito la sufficienza (almeno 18) possono sostenere l'esame orale previsto per il 26-6 o mantenere il voto conseguito, dandone comunicazione via email al docente. Gli studenti che hanno conseguito un voto pari a 15, 16 o 17 devono sostenere l'esame orale del 26 per raggiungere la sufficienza.
| Prenotazioni prova 1 modulo12-06-2017 14:18
Gli studenti che intendano sostenere la prova di esame relativamente al primo modulo del corso sono pregati di inviarne comunicazione via mail al docente, all'indirizzo giorgio.gambosi@uniroma2.it
| Prove scritte 21-6-201712-06-2017 14:16
Per il primo appello della sessione estiva 2016/17, la prova scritta del primo modulo avrà luogo alle ore 14 in aula T5, mentre la prova scritta del secondo modulo avrà luogo alle ore 10.00, nella stessa aula.
| Nuove regole in merito agli appelli d'esame12-06-2017 12:16
Al fine di facilitare gli studenti incrementando il numero di possibili date di esame,
a partire dalla sessione estiva 2016/17 sono previsti per il corso di Fondamenti di Informatica due appelli di esame per ciascuna sessione. Tuttavia, ciascuno studente continuerà a poter 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 (esattamente come avveniva fino ad ora). Per quanto riguarda le altre sessioni, per le quali sino ad ora gli studenti avevano a disposizione una sola data di esame, da ora in poi 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
| Lezione del 31-03-201731-03-2017 08:14
Si avvisano gli studenti che la lezione di oggi non avrà luogo.
| Esami orali del 7-3-2017, anticipo orario02-03-2017 19:41
I colloqui orali relativi all'esonero, previsit per il 7-3 alle 14 nello studio del docente, sono anticipati alle ore 11.
| Esami orali del 7-3-201702-03-2017 19:39
- Per gli studenti che hanno ottenuto la sufficienza piena (almeno 18) alla prova scritta, la prova orale è facoltativa: possono, se preferiscono, mantenere il voto ottenuto allo scritto come valutazione complessiva. In alternativa, possono presentarsi il 7-3 per sostenere il colloquio orale. Si pregano gli studenti che intendono sostenere il colloquio il 7 di darne comunicazione al docente via email.
- Gli studenti che hanno ottenuto un voto compreso tra 15 e 17 (inclusi) devono invece sostenere il colloquio orale il 7-3 al fine di raggiungere una piena sufficienza.
| Esami orali del 22-2-201719-02-2017 11:33
- Per gli studenti che hanno ottenuto la sufficienza piena (almeno 18) alla prova scritta, la prova orale è facoltativa: possono, se preferiscono, mantenere il voto ottenuto allo scritto come valutazione complessiva (del primo modulo per l'esame da 12 cfu, dell'intero esame per l'esame da 6 cfu). In alternativa, possono presentarsi il 22-2 per sostenere il colloquio orale. Si pregano gli studenti che intendono sostenere il colloquio il 22 di darne comunicazione al docente via email.
- Gli studenti che hanno ottenuto un voto compreso tra 15 e 17 (inclusi) devono invece sostenere il colloquio orale il 22-2 al fine di raggiungere una piena sufficienza.
| Seconda prova parziale primo modulo13-02-2017 12:21
La seconda prova parziale per il primo modulo del corso avrà luogo il 28-2-2017 alle ore 10 in aula G2C, per quanto riguarda lo scritto, e il successivo 7-3-2017 alle ore 14 nello studio del docente, per quanto riguarda l’orale. Gli studenti interessati sono invitati a darne comunicazione via mail al docente, Prof. Gambosi.
| Prove parziali per il primo modulo13-02-2017 12:20
Le prove parziali relative al primo modulo del corso saranno distribuite durante l’anno 2017 nel seguente modo.
- Febbraio: una prova in corrispondenza alle date fissate per la sessione invernale 2015-2016 + una ulteriore prova ad hoc, le cui date sono comunicate sulla pagina del corso
- Giugno-Luglio: una sola prova, tenuta in corrispondenza del secondo appello della sessione estiva del corso
- Settembre: una prova, tenuta in corrispondenza dell’appello della sessione autunnale del corso
| Prove scritte di esame del 15-2-201729-01-2017 17:35
Le prove scritte dei due moduli di esame avranno luogo secondo il seguente orario:
- ore 10:00 per il secondo modulo
- ore 14:00 per il primo modulo e per il vecchio esame di FI da 6 cfu
| 18-10-2016 09:12
Una cartella condivisa contenente il materiale didattico messo a disposizione è accessibile a questo link (aprire in una finestra diversa)
| 08-10-2016 17:38
L'inizio delle lezioni è rimandato a martedì 18 ottobre alle ore 14, in aula 3A |
Lezioni46 | 14-06-2017
Modulo 2. Dimostrazioni di NP-completezza e di coNP-completezza. Esercitazione. | 45 | 31-05-2017
Modulo 2. Dimostrazioni di NP-completezza: problemi di colorabilità, dominating set. Problemi coNP-completi | 44 | 26-05-2017
Modulo 2. Dimostrazioni di NP-completezza: TSP. Il problema Partizione. Problemi numerici: algoritmi pseudo-polinomiali, NP-completezza in senso debole e in senso forte | 43 | 24-05-2017
Modulo 2. Dimostrazioni di NP-completezza: Vertex Cover, Independent Set, Clique, Circuito Hamiltoniano (solo enunciato) | 42 | 19-05-2017
Modulo 2. Dimostrazioni di NP.completezza. NP-completezza di 3SAT. La struttura di NP: il terorema di Ladner (solo enunciato). Utilizzo delle riduzioni polinomiali per mostrare l'appartenenza a P di un problema: il problema 2COL. | 41 | 17-05-2017
Modulo 2. Il teorema di Cook-Levin | 40 | 12-05-2017
Modulo 2. La classe NP, algoritmi non deterministici, caratterizzazione della classe NP come classe dei problemi efficientemente verificabili. | 39 | 10-05-2017
Modulo 2. Codifiche ragionevoli. Problemi e complessità, linguaggi associati ad un problema e al suo complemento, il ruolo del linguaggio delle istanze. | 38 | 05-05-2017
Modulo 2. Linguaggi coNP-completi. Problemi: problemi di ricerca, ottimizzazione, enumerazione, decisione. Problemi e codifiche. | 37 | 03-05-2017
Modulo 2. Riducibilità, chiusura, completezza. Riducibilità polinomiale, NP-completezza e congettura "P diverso da NP". La classe coNP: relazione fra le prime due congetture della complessità computazionale, linguaggi coNP completi, chiusura di coNP rispetto alla riducibilità polinomiale. | 36 | 28-04-2017
Modulo 2. Inclusione stretta di P in EXPTIME, uguaglianza di PSPACE e NPSPACE | 35 | 26-04-2017
Modulo 2. Teorema di accelerazione lineare (schema della dimostrazione). Principali classi di complessità: P, NP, PSPACE, NPSPACE, EXPTIME, NEXPTIME e loro relazione. La classe coP. La classe FP. | 34 | 21-04-2017
Modulo 2. Relazioni fra classi di complessità temporali deterministiche e non deterministiche. Classi di complessità complemento. Il Gap-Theorem (solo enunciato). Teorema di compressione lineare (schema della dimostrazione).
| 33 | 19-04-2017
Modulo 2. Funzioni time- e space-contructible; la funzione n^k. Classi di complessità: DTIME, DSPACE, NTIME, NSPACE. Prime relazioni fra tali classi. | 32 | 12-04-2017
Modulo 2. Riducibilità fra linguaggi. Misure di complessità: dtime, dspace, ntime, nspace, e loro relazioni. Correlazione polinomiale fra modelli di calcolo. | 31 | 07-04-2017
Linguaggi non accettabili, linguaggi non decidibili. L'Halting problem | 30 | 05-04-2017
Simulazione di una macchina di Turing non deterministrica mediante un programma in Pascal minimo. Insiemi numerabili: sottoinsiemi di insiemi numerabili, unione e prodotto cartesiano di insiemi numerabili. Non numerabilità dell'nsieme delle parti di N. | 29 | 29-03-2017
La tesi di Church-Turing. Un nuovo modello di calcolo: li linguaggio Pascal minimo. Equivalenza de. modelli Pascal minimo e macchina di Turing. Simulazione della macchina di Turing Universale mediante un programma scritto in linguaggio Pascal minimo. | 28 | 24-03-2017
Linguaggi e linguaggi complemento, linguaggi accettabili e linguaggi decidibili. Funzioni, funzioni totali, funzioni calcolabili. Relazioni fra accettabilità e decidibilità di linguaggi e calcolabilità di funzioni. | 27 | 22-03-2017
La macchina di Turing Universale | 26 | 17-03-2017
Equivalenza fra macchine di Turing a k nastri e macchine di Turing a 1 nastro. Equivalenza fra macchine di Turing ad alfabeto qualsiasi e macchine di Turing ad alfabeto binario. Introduzione alla macchina di Turing Universale. | 25 | 15-03-2017
Macchine di Turing di tipo trasduttore e di tipo riconoscitore. Macchine di Turing deterministiche e non deterministiche e loro equivalenza. Macchine a k>1 nastri a testine indipendenti e solidali e loro equivalenza. | 24 | 10-03-2017
Modulo 2. Esercitazione: macchina di Turing ad un nastro che calcola la somma di due numeri interi. Cosiderazioni: memoria lineare delle macchine di Turing. Macchine di Turing: stati globali, transizioni, computazioni. | 23 | 08-03-2017
Modulo 2. Introduzione alla calcolabilità. Descrizione informale di una macchina di Turing a 3 nastri che calcola la somma di due interi. Definizione formale di una macchina di Turing. | 22 | 18-01-2017
Cenni sul parsing | 21 | 17-01-2017
Esercitazione | 20 | 11-01-2017
L’algoritmo CYK | 19 | 10-01-2017
Ambiguità, PDA deterministici | 18 | 21-12-2016
Equivalenza tra NPDA e CFG | 17 | 20-12-2016
Forma normale di Greibach | 16 | 14-12-2016
Automi a pila: accettazione per stato finale e per pila vuota. Equivalenza. | 15 | 13-12-2016
Decidibilità di predicati su linguaggi CF. Automi a pila. | 14 | 07-12-2016
Pumping lemma per i linguaggi context-free. Proprietà di chiusura dei linguaggi CF | 13 | 06-12-2016
Forme ridotte. Forma normale di Chomsky. | 12 | 30-11-2016
Linguaggi e grammatiche context free. Alberi sintattici. Forme ridotte. | 11 | 29-11-2016
Esercitazione sui linguaggi regolari | 10 | 23-11-2016
Equivalenza tra grammatiche di tipo 3 ed espressioni regolari. Minimizzazione di automi a stati finiti. | 9 | 22-11-2016
DEcidibilità di predicati sui linguaggi regolari. Equivalenza tra espressioni regolari e automi a stati finiti | 8 | 16-11-2016
Pumping lemma per i linguaggi regolari. Proprietà di chusura dei linguaggi regolari. | 7 | 15-11-2016
Equivalenza tra grammatiche regolari e automi a stati finiti | 6 | 09-11-2016
Equivalenza tra asf con epsilon transizioni, asfnd e asfd | 5 | 08-11-2016
Automi a stati finiti deterministici e non deterministici, definizione ed esempi, asf con epsilon transizioni | 4 | 02-11-2016
Automi, configurazioni e computazioni. riconoscimento di linguaggi | 3 | 26-10-2016
Grammatiche e linguaggi di tipo 0,1,2,3. Gerarchia di Chomsky. Forma normale di Backus. | 2 | 25-10-2016
Esempi di espressioni regolari. Grammatiche. Derivazioni. | 1 | 19-10-2016
Richiami matematici. Insiemi infiniti, numerabilità e non numerabilità. Diagonalizzazione. Esistenza di problemi non risolubili algoritmicamente.
Alfabeti e linguaggi. Espressioni regolari: definizione. | 0 | 18-10-2016
Introduzione al corso. Questioni fondamentali nell'elaborazione dell'informazione. Richiami logico-matematici. |
Materiale didatticoRisultati prova scritta appello di esame del 20-9-2017, corso da 6 cfu | | Risultati prova scritta appello di esame del 20-9-2017 | | Testo esame scritto primo modulo del 5-7-2017 | | Risultati prova scritta 1 modulo del 5-7-2017 | | Testo e soluzione della prova scritta per il 1 modulo, del 21-6-2017 | | Risultati prova scritta esame da 6cfu del 21-6-2017 | | Risultati prova scritta 1 modulo del 21-6-2017 | | Modulo 2. Dispensa 9: La classe NP | | Modulo 2. Dispensa 8: La classe P | | Modulo 2. Esercizi: La classe P | | Modulo 2. Esercizi: La classe NP | | Modulo 2. Esercizi: Linguaggi e Complessità | | Modulo 2. Dispensa 7: Linguaggi e Problemi | | Modulo 2. Dispensa 6: Linguaggi e Complessità | | Modulo 2. Dispensa 5: Linguaggi non accettabili e non decidibili e l'Halting Problem | | Modulo 2. Esercizi: Cardinalità di insiemi | | Modulo 2. Dispensa 4: Cardinalità di insiemi | | Modulo 2. Esercizi: Accettabilità e decidibilità di linguaggi | | Modulo 2. Dispensa 3: Funzioni calcolabili e linguaggi decidibili | | Modulo 2. Dispensa 2: Macchine di Turing e Macchina di Turing Universale | | Modulo 2. Esercizi: Macchine di Turing | | Modulo 2. Dispensa 1: Introduzione alla calcolabilità. | | Testo prova scritta di esonero del 28-2-17, con soluzioni | | Risultati prova scritta di esonero del 28-2-17. | | Risultati prova scritta di esame del 15-2-17, corso da 6cfu | | Risultati prova scritta di esonero del 15-2-17. | | Testo prova scritta di esonero del 15-2-17, con soluzioni | |
| InformazioniAnno accademico | 2016-2017 |
---|
Crediti | 12 |
---|
Settore | INF/01 |
---|
Anno | 2 |
---|
Semestre | 1-2 |
---|
Propedeuticità | Matematica discreta. |
---|
ProgrammaModulo 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à
- Applicazione alla compilazione: analisi lessicale
- Applicazione alla compilazione: analisi sintattica (parsing). Parsing top-down e bottom-up.
- Parsing LL e LR
- 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.
|
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.
Materiale a cura del docente.
Modulo 2
Materiale a cura del docente |
Ricevimento studentiModulo 1. Al termine delle lezioni. E' possibile inoltre richiedere un appuntamento via mail.
Modulo 2. Al termine della lezione del mercoledì per chiarimenti brevi. Previo appuntamento da richiedersi 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
Nuove regole a partire dall'anno accademico 2016/17.
Al fine di facilitare gli studenti incrementando il numero di possibili date di esame,
a partire dalla sessione estiva 2016/17 sono previsti per il corso di Fondamenti di Informatica due appelli di esame per ciascuna sessione. Tuttavia, ciascuno studente continuerà a poter 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 (esattamente come avveniva fino ad ora). Per quanto riguarda le altre sessioni, per le quali sino ad ora gli studenti avevano a disposizione una sola data di esame, da ora in poi 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
|
|