Dettagli sull'Insegnamento per l'A.A. 2018/2019
Nome:
Fondamenti dell'informatica II / Foundations of Computer Science II
Informazioni
Crediti:
: Master Degree in Computer Science 6 CFU (b)
Erogazione:
Master Degree in Computer Science curriculum GSEEM Elective
Master Degree in Computer Science 2nd anno curriculum General Compulsory
Lingua:
Inglese
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.
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