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. 2018/19

Informazioni valide per gli studenti immatricolati nell'A.A. 2017/18

Principali informazioni sull'insegnamento
Corso di studio Corso di laurea in
INFORMATICA
SC1167, ordinamento 2011/12, A.A. 2018/19
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/2018/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

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 25/02/2019
Fine attività didattiche 14/06/2019

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:
  • Hopcroft, John E.; Motwani, Rajeev; Ullman, Jeffrey D., Automi, linguaggi e calcolabilità. Milano: Addison-Wesley Pearson Education Italia, 2009. 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

Didattica innovativa: Strategie di insegnamento e apprendimento previste
  • Lecturing
  • Problem based learning
  • Interactive lecturing
  • Problem solving
  • Quiz o test a correzione automatica per feedback periodico o per esami
  • Active quiz per verifiche concettuali e discussioni in classe
  • Videoriprese realizzate dal docente o dagli studenti

Didattica innovativa: Software o applicazioni utilizzati
  • Moodle (files, quiz, workshop, ...)
  • Camtasia (montaggio video)

Obiettivi Agenda 2030 per lo sviluppo sostenibile
Industria, innovazione e infrastrutture