Fondamenti di informatica

Collegamento Teams appello modulo 1 del 22-9-2020

Collegamento Teams appello modulo 1 dell'8-9-2020

Prove di esame modulo 1 - sessione autunnale 2020

Le prove di valutazione per il primo modulo del corso si terranno, in considerazione della situazione epidemiologica, sotto forma di orale, in via telematica. Le date previste sono l'8-9-2020 e il 22-9-2020, in entrambi i casi a partire dalle ore 15. Gli studenti che intendono sostenere le prove possono comunicare il loro interesse utilizzando i form all'indirizzo https://forms.gle/BHjX5fWDxLPUDPsGA (per l'8-9) e https://forms.gle/3ijQqzoAnvofovLe9 (per il 22-9). Per ognuna delle due date, verrà creata una sessione Teams dedicata, cui gli studenti prenotati (e altri che volessero assistere all'esame) saranno invitati.

Collegamento Teams appello modulo 1 del 20-7-2020

Collegamento Teams appello modulo 1 del 26-6-2020

Prove di esame modulo 1 - sessione estiva 2020

Le prove di valutazione per il primo modulo del corso si terranno, in considerazione della situazione epidemiologica, sotto forma di orale, in via telematica. Le date previste sono il 26-6-2020 e il 20-7-2020, in entrambi i casi a partire dalle ore 15. Gli studenti che intendono sostenere le prove possono comunicare il loro interesse utilizzando i form all'indirizzo https://forms.gle/fTMNA31rmJPvgBkB7 (per il 26-6) e https://forms.gle/N6UnJDTr3rjFdT6c9 (per il 20-7). Per ognuna delle due date, verrà creata una sessione Teams dedicata, cui gli studenti prenotati (e altri che volessero assistere all'esame) saranno invitati.

Lezioni a distanza modulo 2

Cari ragazzi, a partire dalla prossima settimana inizieremo con le lezioni a distanza. Le terremo su Teams (spero vi siate iscritti tutti) il mercoledì e il giovedì, come da calendario, però varierò l’orario: ci incontreremo (su Teams) alle 18. Questo perché la mattina potrei avere problemi di connessione – e anche alcuni di voi, che hanno fratelli che seguono lezioni a distanza o genitori in smart working. Spero non vi crei problemi: in caso contrario, fatemelo sapere al più presto.

Le lezioni che prevedo saranno di tipo proattivo: questo significa che, nella lezione online (che trovate su Teams)  vi indicherò il materiale delle dispense che dovrete guardare prima dell’incontro su Teams. Pertanto, durante il nostro incontro su Teams (il mercoledì e il giovedì alle 18) io mi metterò in ascolto e mi porrete domande, chiederete chiarimenti, ecc. Insomma, questi incontri saranno un momento di discussione collettiva.

Cercherò di fornirvi materiale che sia il più possibile simile alle lezioni che ascoltereste in aula. Sto preparando del materiale (un power point per ciascuna lezione) e le prime due lezioni sono già state caricate su Teams.

Ricapitolando. Il lavoro sarà organizzato come segue: ad ogni lezione power point sarà associata una data, e la lezione sarà *sempre* disponibile qualche giorno prima di quella data. *Prima* di quella data, dovrete guardare sia la lezione power point che le dispense pdf su questo sito (in ogni lezione indico numero dispensa, paragrafi e pagine da considerare) in modo che alla data della lezione (un mercoledì o un giovedì alle 18) apro una sessione teams e *voi* mi fate domande sul materiale che avete guardato.

Spero di essere stata chiara. Sono sempre disponibile a mezzo posta elettronica.

Lezioni 5-11-12 marzo 2020

In conseguenza del decreto del CdM che sospende le attività didattiche in tutti gli Atenei fino al 15-3-2020, le lezioni previste per i giorni 5-3, 11-3 e 12-3 sono annullate.

Esame orale 1 modulo del 18-2-2020

L'esame è rimandato alle ore 15 dello stesso giorno, 18-2-2020.

Risultati prova scritta 1 modulo del 13-2-2020

Pubblicazione dei risultati della prova scritta relativa al 1 modulo del corso, tenuta il 13-2-2020. Si ricorda che la prova orale si terrà il 18-2-2020 alle ore 10 nello studio del docente. Si ricorda inoltre che gli studenti che hanno ottenuto la sufficienza (18 o più) allo scritto possono sostenere l’orale o, se preferiscono, mantenere la valutazione ottenuta. Coloro che hanno ottenuto un voto compreso tra 15 e 17 hanno la possibilità, se lo desiderano, di sostenere l’orale per tentare di raggiungere la sufficienza. Si pregano gli studenti interessati a sostenere l’orale di comunicarlo inviando una mail al docente all’indirizzo giorgio.gambosi@uniroma2.it. In assenza di indicazioni, il voto ottenuto sarà comunque memorizzato per tutti gli studenti che hanno ottenuto la sufficienza, al fine della valutazione finale mediante media con il voto ottenuto nel 2 modulo. E’ possibile, in appelli successivi e fino alla verbalizzazione finale, sostenere nuovamente la prova scritta, tenendo presente che ciò comporta, in caso di valutazione del relativo elaborato, la perdita del voto già acquisito.

Risultati prova scritta 1 modulo del 30-1-2020

Pubblicazione dei risultati della prova scritta relativa al 1 modulo del corso, tenuta il 30-1-2020. Si ricorda che la prova orale si terrà il 4-2-2020 alle ore 10 nello studio del docente. Si ricorda inoltre che gli studenti che hanno ottenuto la sufficienza (18 o più) allo scritto possono sostenere l’orale o, se preferiscono, mantenere la valutazione ottenuta. Coloro che hanno ottenuto un voto compreso tra 15 e 17 hanno la possibilità, se lo desiderano, di sostenere l’orale per tentare di raggiungere la sufficienza. Si pregano gli studenti interessati a sostenere l’orale di comunicarlo inviando una mail al docente all’indirizzo giorgio.gambosi@uniroma2.it. In assenza di indicazioni, il voto ottenuto sarà comunque memorizzato per tutti gli studenti che hanno ottenuto la sufficienza, al fine della valutazione finale mediante media con il voto ottenuto nel 2 modulo. E’ possibile, in appelli successivi e fino alla verbalizzazione finale, sostenere nuovamente la prova scritta, tenendo presente che ciò comporta, in caso di valutazione del relativo elaborato, la perdita del voto già acquisito.

Esonero 1 modulo del 13-2-2020

A correzione della comunicazione precedente, la prova scritta per l'esonero relativo al 1 modulo del corso del 13-2-2020 si svolgerà in aula G2C alle ore 15.00. 

Si invitano gli studenti interessati a sostenere le prove di esonero a comunicarlo all'indirizzo https://forms.gle/w3t2x4ki3RpxEFHU7

Esonero 1 modulo

Le prove scritte per l'esonero relativo al 1 modulo del corso si terranno il 30-1-2020 e il 13-2-2020 in aula 4PP2 alle ore 15.00. I corrispondenti colloqui orali si svolgeranno il 4-4-2020 e il 18-2-2020 nello studio del docente.

Si invitano gli studenti interessati a sostenere le prove di esonero ad inviare comunicazione in tal senso via mail all'indirizzo giorgio.gambosi@uniroma2.it

Lezione rimandata

Per problemi di salute del docente, la lezione prevista per il 28 novembre è rimandata a data da definire.

Aula

A partire da oggi, 17-10, le lezioni del primo modulo del corso si terranno in aula G2C, con il medesimo orario

Lucidi

Copie dei lucidi utilizzati a lezione sono disponibili a questo indirizzo (aprire link in una nuova finestra del browser)

Raccolta esercizi

A questo indirizzo è disponibile una raccolta di esercizi e di testi di prove di esame (aprire link in una nuova finestra del browser)

Introduzione al corso. Introduzione alla calcolabilità: problemi e istanze, risoluzione automatica di problemi, procedimenti risolutivi, il concetto di "passo elementare di calcolo". Introduzione alle macchine di Turing: una macchina di Turing per addizionare due numeri.

Modulo 2: lezione del 04/06/2020

Modulo 2, Dispensa 6: linguaggi e complessità

Modulo 2: lezione del 28/05/2020

Modulo 2: lezione del 27/05/2020

Modulo 2: lezione del 21/05/2020

Modulo 2: lezione del 20/05/2020

Modulo 2: lezione del 14/05/2020

Modulo 2, Esercizi: la classe P

Modulo 2, Esercizi: la classe NP

Modulo 2: lezione del 13/05/2020

Modulo 2, Dispensa 9: la classe NP

Modulo 2, Dispensa 8: la classe P

Modulo 2: lezione del 07/05/2020

Modulo 2: lezione del 06/05/2020

Modulo 2, Dispensa 7: linguaggi e problemi

Modulo 2: lezione del 30/04/2020

Modulo 2: lezione del 29/04/2020

Modulo 2: lezione del 23/04/2020

Modulo 2: lezione del 22/04/2020

Modulo 2: lezione del 15/04/2020

Modulo 2: lezione del 16/04/2020

Modulo 2, Esercizi: linguaggi e complessità

Modulo 2: lezione del 09/04/2020

Modulo 2: lezione del 08/04/2020

Modulo 2, Dispensa 5:l'Halting Problem

Modulo 2, Dispensa 4: cardinalità del numerabile e numeri transfiniti

Modulo 2: Lezione del 01/04/2020

Modulo 2, Esercizi: decidibilità, accettabilità, calcolabilità

Modulo 2, Esercizi: macchine di Turing

Modulo 2, Dispensa 3: decidibilità, accettabilità, calcolabilità e la Tesi di Church-Turing

Modulo 2: lezione del 02/04/2020

Modulo 2: lezione del 26/03/2020

Modulo 2: Lezione del 25/03/2020

Modulo 2: Lezione del 19/03/2020

Modulo 2: Lezione del 18/03/2020

Modulo 2, Dispensa 2: Introduzione alla calcolabilità Macchine di Turing e macchina di Turing Universale

Modulo 2, Dispensa 1: Introduzione alla calcolabilità

Risultati prova scritta 1 modulo del 13-2-2020

Risultati prova scritta 1 modulo del 30-1-2020

Primo modulo

- Introduzione al corso: algoritmi, problemi, modelli di calcolo

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

- Proprietà di chiusura dei linguaggi CF

- Decidibilità di predicati su linguaggi CF

- Pumping lemma per i linguaggi context free

- Automi a pila e linguaggi context free

- Automi a pila deterministici

- Ambiguità e sua indecidibilità

- L'algoritmo CYK

- Analisi sintattica in un compilatore, linguaggi LL(k) e LR(k) (cenni)

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.

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.

Modulo 2

Dispense a cura del docente, disponibili in questa pagina.

Per consultazione: il testo utilizzato nel modulo 1.

Modulo 1

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

Modulo 2

Al termine della lezione del mercoledì. E' possibile (e preferibile) richiedere un appuntamento via mail.

Nuove modalità di esame adottate per il modulo 2 a seguito dell’emergenza COVID-19.

A causa della nota emergenza coronavirus, gli esami verranno svolti in modalità telematica a  mezzo Teams.

Per partecipare ad un appello, è assolutamente necessario prenotarsi su delphi.

Ciascun appello consisterà di una prova scritta seguita da una prova orale e sarà strutturato come di seguito descritto:

1)    PROVA SCRITTA: si tratta di una serie di domande a risposte multiple; la durata della prova sarà di 10/15 minuti (può variare da appello ad appello, dipendentemente dal numero e dalla complessità delle domande). Gli studenti che non conseguiranno un punteggio sufficiente (che sarà comunicato prima dell’inizio della prova) non saranno ammessi alla prova orale.

2)    PROVA ORALE: obbligatoria per poter superare l’esame corrispondente al modulo 2.

PRIMA DELL’INIZIO DELLA PROVA SCRITTA E DELLA PROVA ORALE: alla data e all’ora prevista per l’esame, gli studenti che intendono partecipare alla prova dovranno collegarsi su Teams (ove verrà predisposto un canale della classe Fondamenti di Informatica), attivare videocamera e microfono e, quando richiesto dal docente, mostrare il proprio documento di riconoscimento.

 Videocamera e microfono dovranno rimanere attivi per tutta la durata della prova scritta, e il viso dello studente dovrà essere inquadrato per tutta la durata della prova.

LA PROVA ORALE AVRA' INIZIO NON APPENA TERMINATA LA PROVA SCRITTA. Dipendentemente dal numero di studenti, potrà proseguire anche nei giorni successivi.

Modalità di esame in vigore prima dell'emergenza COVID-19

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

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. Si invitano gli studenti a prenotarsi per l'esame inviando una mail cono Nome, Cognome e Matricola al docente, all'indirizzo giorgio.gambosi@uniroma2.it ; inoltre, se è già stato superato l'esame relativo al secondo modulo, si invita a prenotarsi sul sito delphi.uniroma2.it, per l'eventuale verbalizzazione finale.

Informazioni specifiche alla prova di esame per il 2 modulo

Per sostenere l'esame è necessario prenotarsi sul sito delphi.uniroma2.it.

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