Corsi di Laurea Corsi di Laurea Magistrale Corsi di Laurea Magistrale
a Ciclo Unico
Scuola di Ingegneria
INGEGNERIA INFORMATICA
Insegnamento
AUTOMI, LINGUAGGI E COMPUTAZIONE
INP8084178, A.A. 2018/19

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

Principali informazioni sull'insegnamento
Corso di studio Corso di laurea magistrale in
INGEGNERIA INFORMATICA
IN0521, ordinamento 2009/10, A.A. 2018/19
N0
porta questa
pagina con te
Crediti formativi 9.0
Tipo di valutazione Voto
Denominazione inglese AUTOMATA, LANGUAGES AND COMPUTATION
Dipartimento di riferimento Dipartimento di Ingegneria dell'Informazione (DEI)
Sito E-Learning https://elearning.dei.unipd.it/course/view.php?idnumber=2018-IN0521-000ZZ-2018-INP8084178-N0
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 GIORGIO SATTA ING-INF/05

Dettaglio crediti formativi
Tipologia Ambito Disciplinare Settore Scientifico-Disciplinare Crediti
AFFINE/INTEGRATIVA Attività formative affini o integrative INF/01 2.0
CARATTERIZZANTE Ingegneria informatica ING-INF/05 7.0

Organizzazione dell'insegnamento
Periodo di erogazione Primo semestre
Anno di corso I Anno
Modalità di erogazione frontale

Tipo ore Crediti Ore di
didattica
assistita
Ore Studio
Individuale
LEZIONE 9.0 72 153.0

Calendario
Inizio attività didattiche 01/10/2018
Fine attività didattiche 18/01/2019

Commissioni d'esame
Commissione Dal Al Membri
1 A.A. 2018/2019 01/10/2018 15/03/2020 SATTA GIORGIO (Presidente)
PINI MARIA SILVIA (Membro Effettivo)
PIZZI CINZIA (Supplente)

Syllabus
Prerequisiti: Per poter seguire l'insegnamento con profitto sono necessarie una solida base matematica ed una approfondita conoscenza dei concetti e delle metodologie alla base dell’elaborazione automatica dell’informazione. Più specificatamente, si assume che lo studente abbia familiarità con le tecniche di dimostrazione più comuni, incluso la dimostrazione per induzione. Si assume inoltre la conoscenza della programmazione in generale, incluso la programmazione ricorsiva, e la conoscenza delle strutture dati più comuni, quali gli alberi ed i grafi.
Conoscenze e abilita' da acquisire: Il corso ha due obiettivi principali: (i) l’apprendimento di conoscenze che riguardano i modelli più diffusi per rappresentare formalmente la computazione; (ii) l’acquisizione dell’abilità di formalizzazione applicata alla analisi di una computazione.

Più specificatamente, le conoscenze da acquisire sono:
1. concetti di base dei modelli di calcolo, quali automi e grammatiche
2. concetti di base delle risorse di calcolo, quali tempo e spazio
3. il concetto di linguaggio formale come rappresentazione matematica di un problema
4. nozioni di computabilità, decidibilità e trattabilità di un problema

Le abilità che lo studente svilupperà durante il corso sono:
1. rappresentare in modo astratto la computazione
2. rappresentare un problema mediante un linguaggio formale, e studiare le sue proprietà matematiche
Modalita' di esame: La verifica delle conoscenze apprese e delle abilità attese è effettuata mediante una prova scritta obbligatoria, che prevede l’esposizione delle nozioni teoriche svolte nel corso e l’analisi di sistemi computazionali e di linguaggi formali.
Criteri di valutazione: I criteri di valutazione utilizzati all’esame finale per la verifica delle conoscenze apprese e delle abilità da acquisire sono i seguenti:
1. completezza delle conoscenze acquisite
2. livello di astrazione raggiunto nell’analisi di sistemi computazionali e linguaggi formali
3. proprietà di linguaggio nell’esposizione

Ai fini della valutazione complessiva verrà inoltre considerata la partecipazione attiva alle discussioni tecniche sul forum elettronico durante il periodo di svolgimento del corso, ed i meriti acquisiti nella soluzione dei contest proposti a lezione.
Contenuti: Tecniche base per le dimostrazioni matematiche. Definizione dei concetti di base dei linguaggi formali. Caratterizzazione di problemi computazionali in termini di linguaggi formali.

Automi a stati finiti deterministici, non-deterministici, e non-deterministici con epsilon-transizioni. Espressioni regolari e loro relazione con gli automi a stati finiti. Proprietà dei linguaggi regolari.

Grammatiche context-free, alberi di derivazione; semplificazione di grammatiche context-free e forme canoniche. Automi push-down e loro relazione con le grammatiche context-free. Proprietà dei linguaggi context-free.

Macchine di Turing, definizioni di base e tecniche di costruzione. Linguaggi (problemi) ricorsivamente enumerabili (computabili) e ricorsivi (decidibili). Tesi di Church-Turing. Dimostrazione dell'esistenza di linguaggi/funzioni non decidibili e non computabili. Problemi intrattabili e la nozione di NP-completezza. Altre classi di problemi.
Attivita' di apprendimento previste e metodologie di insegnamento: Il corso viene erogato mediante lezioni frontali che utilizzano materiale didattico su supporto digitale distribuito agli studenti in anticipo rispetto alle lezioni. Al fine di favorire la discussione, la collaborazione, e l'auto-verifica del processo di apprendimento da parte degli studenti durante il corso,
viene messo a disposizione degli studenti sulla piattaforma moodle un forum elettronico supervisionato dal docente in cui poter discutere la risoluzione di problemi di teoria e di esercizi applicativi proposti dal docente stesso. Infine, per incoraggiare la partecipazione attiva degli studenti allo svolgimento delle lezioni e motivare gli stessi a mantenere il passo con gli argomenti svolti, vengono proposti con continuità dal docente dei piccoli contest, premiati con dei bonus di cui si tiene conto nella valutazione finale.
Eventuali indicazioni sui materiali di studio: Gli argomenti del corso sono trattati nel libro di testo di riferimento. Viene inoltre fornito mediante la piattaforma moodle materiale didattico aggiuntivo a sostegno del corso, nella forma dei lucidi svolti a lezione e di dispense con esercizi svolti.
Testi di riferimento:
  • J.E. Hopcrpft, R.Motwani, J.D.Ullman, Automi, Linguaggi e Calcolabilità. --: Pearson, 2018. terza edizione Cerca nel catalogo

Didattica innovativa: Strategie di insegnamento e apprendimento previste
  • Lecturing
  • Interactive lecturing
  • Questioning
  • Active quiz per verifiche concettuali e discussioni in classe
  • Files e pagine caricati online (pagine web, Moodle, ...)

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

Obiettivi Agenda 2030 per lo sviluppo sostenibile
Istruzione di qualita'