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. 2019/20

Informazioni valide per gli studenti immatricolati nell'A.A. 2018/19

Principali informazioni sull'insegnamento
Corso di studio Corso di laurea in
INFORMATICA
SC1167, ordinamento 2011/12, A.A. 2019/20
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/2019/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 Responsabile non ancora definito.
Altri docenti GILBERTO FILE' INF/01

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

Organizzazione dell'insegnamento
Periodo di erogazione Secondo semestre
Anno di corso II Anno
Modalità di erogazione frontale

Tipo ore Crediti Ore di
didattica
assistita
Ore Studio
Individuale
ESERCITAZIONE 2.0 16 34.0
LEZIONE 6.0 48 102.0

Calendario
Inizio attività didattiche 02/03/2020
Fine attività didattiche 12/06/2020
Visualizza il calendario delle lezioni Lezioni 2019/20 Ord.2011

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
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: I principali contenuti del corso sono i seguenti:
Parte 1: regular languages and lexical analysis (3 cfu)
-- automi a stati finiti
-- espressioni e linguaggi regolari
-- pumpling lemma
-- proprietà dei linguaggi regolari
-- analisi lessicale.
Parte 2: linguaggi liberi da contesto e analisi sintattica (3 cfu)
-- grammatiche e linguaggi liberi da contesto
-- automi a pila
-- pumping lemma
-- proprietà dei linguaggi liberi da contesto
-- analisi sintattica.

Parte 3: indecidibilità e intrattabilità (2 cfu)
-- macchine di Turing
-- indecidibilità
-- 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: Un sito moodle con tutto il materiale del corso. Sono disponibili anche e le registrazioni delle lezioni
Testi di riferimento:
  • Alfred V. Aho, Monica S. Lam, Ravi Sethi, Jeffrey D. Ullman, Compilers: Principles, Techniques, and Tools. --: Addison-Wesley, 2006. Cerca nel catalogo
  • Hopcroft, John E.; Motwani, Rajeev; Ullman, Jeffrey D., Automi, linguaggi e calcolabilità. Milano: Addison-Wesley Pearson Italia, 2009. Cerca nel catalogo