Fondamenti di informatica

Docenti: Giorgio Gambosi, Miriam Di Ianni

Comunicazioni

Risultati 1 modulo 20-9-2017

21-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/2017

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.


Risultati 1 modulo 5-7-2017

07-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-2017

03-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-2017

22-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 modulo

12-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-2017

12-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'esame

12-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-2017

31-03-2017 08:14

Si avvisano gli studenti che la lezione di oggi non avrà luogo.


Esami orali del 7-3-2017, anticipo orario

02-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-2017

02-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-2017

19-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 modulo

13-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 modulo

13-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-2017

29-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


Lezioni

4614-06-2017

Modulo 2. Dimostrazioni di NP-completezza e di coNP-completezza. Esercitazione.

4531-05-2017

Modulo 2. Dimostrazioni di NP-completezza: problemi di colorabilità, dominating set. Problemi coNP-completi

4426-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

4324-05-2017

Modulo 2. Dimostrazioni di NP-completezza: Vertex Cover, Independent Set, Clique, Circuito Hamiltoniano (solo enunciato)

4219-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.

4117-05-2017

Modulo 2. Il teorema di Cook-Levin

4012-05-2017

Modulo 2. La classe NP, algoritmi non deterministici, caratterizzazione della classe NP come classe dei problemi efficientemente verificabili.

3910-05-2017

Modulo 2. Codifiche ragionevoli. Problemi e complessità, linguaggi associati ad un problema e al suo complemento, il ruolo del linguaggio delle istanze.

3805-05-2017

Modulo 2. Linguaggi coNP-completi. Problemi: problemi di ricerca, ottimizzazione, enumerazione, decisione. Problemi e codifiche.

3703-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.

3628-04-2017

Modulo 2. Inclusione stretta di P in EXPTIME, uguaglianza di PSPACE e NPSPACE

3526-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.

3421-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).

 

3319-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.

3212-04-2017

Modulo 2. Riducibilità fra linguaggi. Misure di complessità: dtime, dspace, ntime, nspace, e loro relazioni. Correlazione polinomiale fra modelli di calcolo.

3107-04-2017

Linguaggi non accettabili, linguaggi non decidibili. L'Halting problem

3005-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.

2929-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.

2824-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.

2722-03-2017

La macchina di Turing Universale

2617-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.

2515-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.

2410-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.

2308-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.

2218-01-2017

Cenni sul parsing

2117-01-2017

Esercitazione

2011-01-2017

L’algoritmo CYK

1910-01-2017

Ambiguità, PDA deterministici

1821-12-2016

Equivalenza tra NPDA e CFG

1720-12-2016

Forma normale di Greibach

1614-12-2016

Automi a pila: accettazione per stato finale e per pila vuota. Equivalenza.

1513-12-2016

Decidibilità di predicati su linguaggi CF. Automi a pila.

1407-12-2016

Pumping lemma per i linguaggi context-free. Proprietà di chiusura dei linguaggi CF

1306-12-2016

Forme ridotte. Forma normale di Chomsky.

1230-11-2016

Linguaggi e grammatiche context free. Alberi sintattici. Forme ridotte.

1129-11-2016

Esercitazione sui linguaggi regolari

1023-11-2016

Equivalenza tra grammatiche di tipo 3 ed espressioni regolari. Minimizzazione di automi a stati finiti.

922-11-2016

DEcidibilità di predicati sui linguaggi regolari. Equivalenza tra espressioni regolari e automi a stati finiti

816-11-2016

Pumping lemma per i linguaggi regolari. Proprietà di chusura dei linguaggi regolari.

715-11-2016

Equivalenza tra grammatiche regolari e automi a stati finiti

609-11-2016

Equivalenza tra asf con epsilon transizioni,  asfnd e asfd

508-11-2016

Automi a stati finiti deterministici e non deterministici, definizione ed esempi, asf con epsilon transizioni

402-11-2016

Automi, configurazioni e computazioni. riconoscimento di linguaggi

326-10-2016

Grammatiche e linguaggi di tipo 0,1,2,3. Gerarchia di Chomsky. Forma normale di Backus.

225-10-2016

Esempi di espressioni regolari. Grammatiche. Derivazioni.

119-10-2016

Richiami matematici. Insiemi infiniti, numerabilità e non numerabilità. Diagonalizzazione. Esistenza di problemi non risolubili algoritmicamente.

Alfabeti e linguaggi. Espressioni regolari: definizione.

018-10-2016

Introduzione al corso. Questioni fondamentali nell'elaborazione dell'informazione. Richiami logico-matematici.


Materiale didattico

Risultati 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

Informazioni

Anno accademico2016-2017
Crediti12
SettoreINF/01
Anno2
Semestre1-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. 
- 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 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:

  • 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