Fondamenti di informatica

Docenti: Giorgio Gambosi, Miriam Di Ianni

Comunicazioni

14-09-2016 12:41

Pubblicati i risultati della prova scritta del primo modulo e dell'appello straordinario per l'esame a 6 cfu, 12-9-2016


12-09-2016 14:34

La prova orale del primo modulo del corso, per la sessione autunnale, avrà luogo il 21-9-2016 a partire dalle ore 14, presso lo studio del Prof. Gambosi.


Prova scritta di esame del 12-09-2016

07-09-2016 17:52

Le prove scritte dei due moduli di esame per l'appello della sessione autunnale del 12-9-2016 avranno luogo secondo il seguente orario:

- ore 10:00 per il secondo modulo

- ore 14:00 per il primo modulo

 


19-07-2016 13:31

Pubblicati i risultati della prova scritta del primo modulo e dell'appello straordinario per l'esame a 6 cfu, 18-7-2016


19-07-2016 13:31

Inserito testo prova di esame del 18-7-2016, con soluzioni


07-07-2016 16:38

Le prove scritte dei due moduli di esame per il secondo appello della sessione estiva avranno luogo, come previsto, il 18-7-2016 secondo il seguente orario:

- ore 9.00 per il primo modulo

- ore 11.30 per il secondo modulo


05-07-2016 23:25

Pubblicati i risultati della prova scritta del primo modulo e dell'appello straordinario per l'esame a 6 cfu, 4-7-2016


04-07-2016 19:16

Inserito testo prova di esame del 4-7-2016, con correzione di una delle soluzioni


18-05-2016 15:41

Si avvisano gli studenti che la lezione di Fondamenti di Informatica di domani, 19 maggio, è rinviata a venerdì 27 maggio, dalle 9 alle 11.


12-03-2016 15:09

Inserito elenco risultati esonero 1 modulo del 4-3-2106


04-03-2016 12:51

Il testo, con soluzioni, dell'esonero del 4-3-2016 è stato inserito nella cartella condivisa relativa alle prove precedenti


23-02-2016 15:01

In relazione alle nuove modalità di esame, per quanto riguarda il 1 modulo del corso, si chiarisce che:

- la nuova disciplina si applica a partire dal primo appello della sessione estiva. A partire da esso gli studenti sosterrano la prova scritta e (se superato lo scritto) un colloquio orale nello stesso appello.

- nel transitorio, gli studenti che hanno già superato la prova scritta in precedenza e coloro che la supereranno nell'esonero del 4-3-2016 dovranno sostenere il relativo colloquio in corrispondenza alla prova orale prevista per il primo appello della sessione estiva (giugno). Si pregano gli studenti interessati ad inviare comunicazione via mail al docente, nei giorni precedenti l'appello stesso, dell'intenzione di sostenere l'orale.

- nulla cambia per gli studenti che devono sostenere l'esame del vecchio corso di Fondamenti di Informatica (6 cfu), per il quale è già prevista una prova scritta (il 4-3, in corrispondenza alla prova scritta di esonero per il corso da 12 cfu) e un colloquio orale (il 7-3).


22-02-2016 12:48

Verificata la difficoltà di molti studenti a rispettare i vincoli relativi alla vicinanza temporale nel sostenere i due moduli, i docenti hanno convenuto sull'opportunità di permettere di sostenere le prove di esame relative ai due moduli indipendentemente secondo le modalità descritte nella sezione apposita. 


18-02-2016 13:03

Inserito elenco risultati prova scritta 1 modulo 17-2-2106


18-02-2016 11:44

IMPORTANTE. Su richiesta di alcuni studenti, la prova scritta parziale relativa al primo modulo del corso (e la contemporanea prova scritta relativa all'appello straordinario del corso di Fondamenti di Informatica da 6 CFU) è rimandata ulteriormente al 4-3-2016, alle ore 10, in aula T4. La prova orale per il corso di Fondamenti di Informatica da 6 CFU avrà luogo il 7-3-2016 alle ore 10, nello studio del Prof. Gambosi.


17-02-2016 12:10

IMPORTANTE. La prova scritta parziale relativa al primo modulo del corso (e la contemporanea prova scritta relativa all'appello straordinario del corso di Fondamenti di Informatica da 6 CFU) è rimandata dal 26-2-2016 al 2-3-2016, alle ore 10, in aula T4. La prova orale per il corso di Fondamenti di Informatica da 6 CFU avrà luogo il 4-3-2016 alle ore 10, nello studio del Prof. Gambosi.


12-02-2016 21:59

Il testo, con soluzioni, dell'esonero del 9-2-2016 è stato inserito nella cartella condivisa relativa alle prove precedenti


12-02-2016 21:54

Inserito elenco risultati esonero 9-2-2106


12-02-2016 13:37

Si comunica che è stato attivato un appello straordinario di esame per il corso di Fondamenti di Informatica (6 cfu). Le date previste sono il 26/2 h 10.00 aula T7 (in corrispondenza al secondo parziale del corso da 12 cfu) per lo scritto e il 29/2 h 10.00 nell'ufficio del Prof. Gambosi per l'orale. Resta inteso che gli studenti che hanno partecipato all'esonero tenuto il 9/2 possono, se vogliono, mantenere il risultato di tale prova e sostenere la sola prova orale, prenotandosi comunque per l'esame su Delphi.


21-01-2016 10:46

Le prove parziali (scritte) per la prima parte del corso avranno luogo il 9-2-2016 e il 26-2-2016 in aula T7, alle ore 10. Si pregano gli interessati a sostenerle di informare il docente via mail entro il giorno precedente alla data della prova, all'indirizzo giorgio.gambosi@uniroma2.it


26-11-2015 08:37

Inserita nella relativa cartella raccolta di quiz sui linguaggi CF.


10-11-2015 10:45

Inserito nella cartella condivisa documento su algebra delle espressioni regolari.


10-11-2015 10:45

Inserito nella cartella condivisa documento dimostrazioni.


09-11-2015 20:03

Inserito nella cartella condivisa documento su ASF con epsilon-produzioni.


09-11-2015 20:01

 

 

Creata cartella condivisa per altro materiale, raggiungibile a questo link.


09-11-2015 19:49

Inserita nella relativa cartella raccolta di quiz sugi automi a stati finiti.


09-11-2015 19:49

Inserita nella relativa cartella raccolta di quiz sui linguaggi regolari.


20-10-2015 18:50

Inserita nella relativa cartella raccolta di quiz sui fondamenti matematici del corso.


20-10-2015 18:48

Creata cartella condivisa per raccolte di esercizi, raggiungibile a questo link.


20-10-2015 18:45

I testi delle prove scritte relative allo scorso a.a., con le relative soluzioni, sono disponibili nella cartella condivisa raggiungibile attraverso questo link.


Lezioni

3106-06-2016

Modulo 2. Esercitazione

3030-05-2016

Modulo 2. Esercitazione sulle prove di NP-completezza: Hamiltonian Path, Longest Path, Colorability e k-Colorability (k > 3), problemi di soddisfacibilità

2927-05-2016

Modulo 2. Problemi NP-intermedi: enunciato del teorema di Lader. Il problema Partizione. Problemi numerici, algoritmi pseudo-polinomiali e NP-completezza in senso forte o debole. NP-completezza in senso forte del problema Commesso Viaggiatore (TSP)

2826-05-2016

Modulo 2. Prove di NP-completezza: Insieme Indipendente, Clique, Dominating Set, 3-Colorabilità

2723-05-2016

Modulo 2. Prove di NP-completezza: i problemi 3SAT e Vertex Cover.

2616-05-2016

Il teorema di Cook-Levin.

2512-05-2016

Modulo 2. La classe NP: esempi di problemi in NP e definizione alternativa di NP.

2409-05-2016

Modulo 2. Complessità dei problemi: il linguaggio delle istanze. Problemi complemento. La classe P: esempi (2SAT e 2COL), riduzione polinomiale da 2COL a 2SAT.

2305-05-2016

Modulo 2. Linguaggi e problemi, tipi di problemi (di ricerca, ottimizzazione, enumerazione, decisione), problemi decisionali e linguaggi, problemi e codifiche

2202-05-2016

Modulo 2.  Riducibilità polinomiale e classe dei linguaggi NP-completi. La classe coNP, la congettura NP diverso da coNP, linguaggi coNP-completi.

2128-04-2016

Modulo 2. PSPACE=NPSPACE. Chiusura di una classe rispetto ad una riduzione, completezza di un liguaggio per una classe rispetto ad una riduzione.

2021-04-2016

Modulo 2. Classi di complessità complemento. Le classi P, NP, PSPACE, NPSPACE, EXPTIME, NEXPTIME e loro relazioni. Inclusione stretta di P in EXPTIME

1918-04-2016

I teoremi di compressione e di accelerazione.

1814-04-2016

Ancora sulle relazioni fra classi di complessità. Funzioni time- e space constructible: definizioni ed esempi (polinomio, esponenziale)

1711-04-2016

Misure di complessità: assiomi di Blum, dtime, dspace, ntime, nspace, relazioni. Correlazione polinomiale fra i modelli di calcolo. Classi di complessità di linguaggi: DTIME, DSPACE, NTIME, NSPACE e loro relazioni.

1607-04-2016

Non numerabilità dell'insieme dei linguaggi e numerabilità dell'insieme delle macchine di Turing. Halting Problem: accettabilità e non decidibilità. Riduzioni fra linguaggi.

1504-04-2016

Modulo 2. Numerabilità dell'unione di una infinità numerabile di insiemi numerabili. Insiemi non numerabili: la tecnica di diagonalizzazione di Cantor e la cardinalità del continuo.

1431-03-2016

Modulo 2. Esercitazione: simulazione della macchina di Turing Universale e di una macchina non deterministica mediante un programma in linguaggio PascalMinimo. Cardinalità di insiemi: insiemi numerabili, N, Z, Q, sottoinsiemi infiniti di insiemi numerabili, unione e prodotto cartesiano di insiemi numerabili.

 

1321-03-2016

Modulo 2. Relazioni fra accettabilità/decidibilità di linguaggi e calcolabilità di funzioni. La tesi di Churcg-Turing e il liguaggio PascalMinimo.

1217-03-2016

Modulo 2. La macchina di Turing Universale: implementazione. Linguaggi, linguaggi complemento, linguaggi accettabili, linguaggi decidibili. Funzioni (parziali e totali) calcolabili.

1114-03-2016

Modulo 2. Equivalenza fra non determinismo e determinismo. Introduzione alla macchina di Turing Universale.

1010-03-2016

Modulo 2. Equivalenza fra macchine di Turing che operano su un alfabeto generico e macchine di Turing che operano su un alfabeto binario. Stato globale di una macchina di Turing. Computazione di una macchina di Turing. Riconoscitori e trasduttori. Completezza dell'insieme delle quintuple. Macchine deterministiche e non deterministiche.

907-03-2016

Modulo 2. Equivalenza fra macchine di Turing a k nastri e macchine di Turing ad un nastro.

803-03-2016

Modulo 2. Macchina di Turing (ad un nastro) che calcola la somma di due numeri. Introduzione alle macchine a più nastri e macchina a 3 nastri che calcola la somma di due numeri.

729-02-2016

Modulo 2. Cenni storici alla calcolabilità. Problemi e algoritmi. Il concetto di operazione elementare. Introduzione alla Macchina di Turing: macchina che verifica se una parola è palindroma.

605-11-2015

Esempi di ASF. Automi a stati finiti non deterministici.

503-11-2015

Automi a stati finiti. 

429-10-2015

Riconoscimento di linguaggi e automi.

327-10-2015

 

Gerarchia di Chomsky. epsilon-produzioni.

215-10-2015

Espressioni regolari. Grammatiche generative. Derivazioni. Linguaggio generato da una grammatica.

113-10-2015

Numerabilità dell'insieme degli algoritmi. Non numerabilità dell'insieme dei linguaggi: diagonalizzazione. Espressioni regolari.

008-10-2015

Introduzione al corso. Linguaggi, problemi, algoritmi, modelli di calcolo.


Materiale didattico

Modulo 2, testo e soluzione della prova scritta dell'appello del 17/02/2017

Modulo 2, testo e soluzione dell'appello del 12/09/2016

Risultati prova scritta appello straordinario FO 6cfu, 12-9-2016

Risultati prova scritta primo modulo, 12-9-2016

Inserito testo prova di esame primo modulo del 12-9-2016, con soluzioni

Modulo 2, testo e soluzione della prova scritta dell'appello del 18/07/2016

Risultati prova scritta primo modulo, 4-7-2016

Risultati prova scritta appello straordinario FO 6cfu, 18-7-2016

Testo prova di esame primo modulo, 18-7-2016

Modulo 2, testo e soluzione della prova scritta dell'appello del 4/07/2016

Risultati prova scritta appello straordinario FO 6cfu, 4-7-2016

Risultati prova scritta primo modulo, 4-7-2016

Testo prova di esame primo modulo, 4-7-2016

Modulo 2, Testi di esame e soluzioni

Modulo 2, Dispensa 9: La classe NP

Modulo 2, Dispensa 8: La classe P

Modulo 2, Dispensa 7: Linguaggi e problemi

Modulo 2, Dispensa 6: Linguaggi e complessità

Modulo 2, Dispensa 5: L'Halting Problem

Modulo 2, Dispensa 4: Cardinalità di insiemi

Modulo2, Dispensa 3: Funzioni calcolabili e linguaggi decidibili

Risultati esonero 4-3-2016

Modulo 2, Dispensa 2: Macchine di Turing e Macchina di Turing Universale

Modulo 2, Dispensa 1: Introduzione

Risultati scritto 1 modulo 17-2-2016

Risultati esonero 9-2-2016

Informazioni

Anno accademico2015-2016
Crediti12
SettoreINF/01
Anno2
Semestre1-2
PropedeuticitàMatematica discreta.

Programma

Programma svolto.

 

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à

- Cenni sul parsing

- 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

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

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


Modalità di esame

L'esame prevede una coppia di prove (scritta e orale) relative al primo modulo e una coppia di prove (scritta e 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.

 

E' prevista una prova di esonero (opzionale) scritto relativo alla prima parte del corso il cui orale potrà essere sostenuto nell'appello di giugno.

 

Per l'iscrizione all'esame è richiesta la prenotazione sul sito delphi.uniroma2.it