Fondamenti di informatica

Docenti: Giorgio Gambosi, Miriam Di Ianni

Comunicazioni

22-10-2017 11:55

Le lezioni del primo modulo del corso riprenderanno Lunedì 30 ottobre 2017 alle ore 9 in aula 6PP2, con una prima lezione di recupero delle lezioni perse per causa di forza maggiore


06-10-2017 17:17

A partire da mercoledì 11 ottobre, le lezioni avranno luogo presso l'aula 6, edificio PP2.


06-10-2017 17:14

Le lezioni di martedì 10, martedì 17 e mercoledì 18 ottobre non avranno luogo. Saranno recuperate in seguito, in date da definire. La lezione di mercoledì 11 avrà regolarmente luogo.


Lezioni


Materiale didattico

Esercizi sugli automi a stati finiti

Esercizi sui linguaggi linguaggi regolari

Quiz sui fondamenti matematici

Slide sugli automi

Slide sugli automi a stati finiti

Slide sui linguaggi

Slide di richiami matematici

Slide di introduzione al corso

Informazioni

Anno accademico2017-2018
Crediti12
SettoreINF/01
Anno2
Semestre1-2
PropedeuticitàMatematica discreta.

Programma

Primo modulo

- 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


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.


Ricevimento studenti

Modulo 1

Al termine delle lezioni. E' possibile inoltre richiedere un appuntamento 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

 

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.