Comunicazioni
Risultati 1 modulo 5-7-201707-07-2017 18:40Pubblicati 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:36Per 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:23Pubblicati 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:18Gli 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:16Per 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:16Al 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:
- Modulo 2:
|
Lezione del 31-03-201731-03-2017 08:14Si avvisano gli studenti che la lezione di oggi non avrà luogo. |
Esami orali del 7-3-2017, anticipo orario02-03-2017 19:41I 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:21La 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:20Le prove parziali relative al primo modulo del corso saranno distribuite durante l’anno 2017 nel seguente modo.
|
Prove scritte di esame del 15-2-201729-01-2017 17:35Le 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 |
Lezioni
| 46 | 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 didattico
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 | |
Informazioni
| Anno accademico | 2016-2017 |
|---|---|
| Crediti | 12 |
| Settore | INF/01 |
| Anno | 2 |
| Semestre | 1-2 |
| Propedeuticità | Matematica discreta. |
Programma
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à - 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.
- Cardinalità di insiemi. Insiemi numerabili e non numerabili. Diagonalizzazione.
- Riducibilità tra linguaggi
Parte 2, complessità:
- Misure di complessità: DTIME, DSPACE, NTIME, NSPACE.
- Problemi e codifiche. Problemi decisionali e loro complemento. - Algoritmi pseudo-polinomiali, problemi numerici e NP-completezza in senso forte; il problema PARTIZIONE.
|
Testi di riferimento
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.
Materiale a cura del docente.
Modulo 2
Materiale a cura del docente |
Ricevimento studenti
Modulo 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 esame
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
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:
- Modulo 2:
|