Corsi di Laurea Corsi di Laurea Magistrale Corsi di Laurea Magistrale
a Ciclo Unico
Scuola di Scienze
INFORMATICA
Insegnamento
AUTOMI E LINGUAGGI FORMALI
SC03100756, A.A. 2017/18

Informazioni valide per gli studenti immatricolati nell'A.A. 2016/17

Principali informazioni sull'insegnamento
Corso di studio Corso di laurea in
INFORMATICA
SC1167, ordinamento 2011/12, A.A. 2017/18
N0
porta questa
pagina con te
Crediti formativi 8.0
Tipo di valutazione Voto
Denominazione inglese AUTOMATA AND FORMAL LANGUAGES
Sito della struttura didattica http://informatica.scienze.unipd.it/2017/laurea
Dipartimento di riferimento Dipartimento di Matematica
Obbligo di frequenza No
Lingua di erogazione ITALIANO
Sede PADOVA
Corso singolo È possibile iscriversi all'insegnamento come corso singolo
Corso a libera scelta È possibile utilizzare l'insegnamento come corso a libera scelta

Docenti
Responsabile GILBERTO FILE' INF/01
Altri docenti DAVIDE BRESOLIN INF/01

Dettaglio crediti formativi
Tipologia Ambito Disciplinare Settore Scientifico-Disciplinare Crediti
CARATTERIZZANTE Discipline Informatiche INF/01 8.0

Modalità di erogazione
Periodo di erogazione Secondo semestre
Anno di corso II Anno
Modalità di erogazione frontale

Organizzazione della didattica
Tipo ore Crediti Ore di
Corso
Ore Studio
Individuale
Turni
ESERCITAZIONE 2.0 16 34.0 Nessun turno
LEZIONE 6.0 48 102.0 Nessun turno

Calendario
Inizio attività didattiche 26/02/2018
Fine attività didattiche 01/06/2018

Commissioni d'esame
Nessuna commissione d'esame definita

Syllabus
Prerequisiti: Nozioni di logica.
Conoscenze e abilita' da acquisire: Questo corso fornisce i concetti fondamentali della teoria degli
automi e dei linguaggi formali, mostrando la loro applicazione ai compilatori.
Inoltre, introduce le nozioni di indecidibilita' e intrattabilita'.
Modalita' di esame: Scritto e orale.
Criteri di valutazione: Lo scritto contiene alcune domande che consentono di valutare il livello di apprendimento delle nozioni impartite durante il corso. Sono poi presenti esercizi di costruzione di automi e di grammatiche formali.
Contenuti: Gli argomenti principali del corso sono:

Parte 1: linguaggi regolari e analisi lessicale (3 cfu)
-- automi a stati finiti
-- espressioni e linguaggi regolari
-- analisi lessicale

Parte 2: linguaggi liberi da contesto e analisi sintattica (3 cfu)
-- grammatiche e linguaggi liberi dal contesto
-- automi a pila
-- analisi sintattica: parsers top-down (LL) e bottom-up (LR)

Parte 3: indecidibilita' e intrattabilita' (2 cfu)
-- macchine di Turing
-- concetto di indecidibilita'
-- problemi intrattabili
-- classi P e NP
Attivita' di apprendimento previste e metodologie di insegnamento: Lezioni frontali ed esercizi in classe.
Eventuali indicazioni sui materiali di studio: Vengono rese disponibili le trasparenze usate a lezione.
Testi di riferimento:
  • Hopcroft, John E.; Motwani, Rajeev; Ullman, Jeffrey D., Automi, linguaggi e calcolabilità. Milano: Addison-Wesley Pearson Education Italia, 2003. Cerca nel catalogo
  • Alfred V. Aho, Monica S. Lam, Ravi Sethi, Jeffrey D. Ullman, Compilers: Principles, Techniques, and Tools. --: Addison-Wesley, 2006. Cerca nel catalogo