Dettagli sull'Insegnamento per l'A.A. 2018/2019

Le informazioni che state leggendo si riferiscono all'anno accademico 2018/2019. Per questo molti collegamenti non sono disponibili e i dati potrebbero essere incompleti. Per leggere le informazioni correnti sul corso, se ancora erogato, consulta il catalogo corsi di ateneo. Per consultare le informazioni relative ad altri anni accademici, usa la lista in fondo a questa pagina.

A. Accademico:

2018/2019

Nome:

Fondamenti dell'informatica II / Foundations of Computer Science II

Tipo:

Corso singolo

Informazioni

Codice:

F0196

SSD:

INF/01

Crediti:

: Master Degree in Computer Science 6 CFU (b)

Periodo:

1^st semester

Erogazione:

Master Degree in Computer Science curriculum GSEEM Elective
Master Degree in Computer Science 2^nd anno curriculum General Compulsory

Lingua:

Inglese

Docenti:

Sergio Orefice

Prerequisiti

Conoscenza degli argomenti trattati nei corsi base di programmazione, familiarità con strutture dati fondamentali, ricorsione e nozioni base della compilazione

Obiettivi

Profonda conoscenza della teoria degli automi e dei linguaggi formali, introduzione ai linguaggi non lineari

Sillabo

1. Nozioni centrali della teoria dei linguaggi formali. Gerarchia di Chomsky
2. Automi a stati finiti deterministici. Automi a stati finiti non deterministici. epsilon-chiusura
3. Espressioni regolari. Teorema di Kleene . Pumping Lemma per linguaggi regolari. Proprietà dei inguaggi regolari
4. Grammatiche context-free. Automi a pila. Linguaggi liberi dal contesto e proprietà. Forma Normale di Chomsky. Pumping Lemma per linguaggi liberi dal contesto. Algoritmo CYK
5. Linguaggi formali multidimensionali e visuali. Modelli sintattici
6. Grammatiche posizionali context-free

Descrittori di Dublino

Alla fine del corso, lo studente dovrebbe

conoscere i principali formalismi utilizzati nella teoria degli automi e dei linguaggi formali, comprendere le diverse caratterizzazioni dei linguaggi regolari e dei linguaggi context free
conoscere e capire le proprietà dei linguaggi regolari e dei linguaggi context free, essere capace di estendere concetti e formalismi della tradizionale teoria dei linguaggi formali alla specifica della sintassi di linguaggi non lineari
avere capacità nel ragionamento formale e abilità nello sviluppare una dimostrazione
capire e saper spiegare specifiche di linguaggi usando notazioni formali (espressioni regolari, automi, grammatiche)
essere capace di leggere e comprendere testi e articoli scientifici che usano le nozioni apprese per altre applicazioni

Testi di riferimento

Hopcroft, Motwani, Ullman, Automi, Linguaggi e calcolabilità , Addison-Wesley. Reference for points 1-4
Hopcroft, Motwani, Ullman, Introduction to Automata Theory, Languages and Computation , Addison-Wesley. Reference for points 1-4
Papers provided by the lecturer Reference for points 5-6

Modalità d'esame

Gli studenti sono incoraggiati a partecipare attivamente alle lezioni facendo domande e discutendo le soluzioni adottate negli esempi sviluppati in aula. L'esame consiste in una prova scritta sugli argomenti trattati nel corso. E' prevista anche una prova intermedia scritta che copre la prima parte del programma del corso in modo che gli studenti possano dividere il carico di studio. L'esame scritto (durata 2 ore) è costituito da un insieme di domande per la verifica delle competenze teoriche/formali e per la verifica della capacità di comprendere e risolvere esercizi significativi. Criteri di valutazione saranno: la padronanza delle nozioni e dei formalismi presentati nel corso, nonché la capacità di applicarli; la chiarezza e la completezza delle spiegazioni.

Risorse Internet

Homepage:

http://www.di.univaq.it/orefice/fond.html

Aggiornamenti alla pagina del corso

Le informazioni sulle editioni passate di questo corso sono disponibili per i seguenti anni accademici:

Per leggere le informazioni correnti sul corso, se ancora erogato, consulta il catalogo corsi di ateneo.

Ultimo aggiornamento delle informazioni sul corso: 14 febbraio 2018, 09:39