Salta al contenuto principale
CODICE 80303
ANNO ACCADEMICO 2023/2024
CFU
SETTORE SCIENTIFICO DISCIPLINARE INF/01
LINGUA Italiano
SEDE
  • GENOVA
PERIODO 1° Semestre
MATERIALE DIDATTICO AULAWEB

PRESENTAZIONE

Il corso presenta concetti e risultati della Teoria degli Automi e della Teoria della Calcolabilità di importanza fondamentale nel bagaglio culturale di un informatico.

 

OBIETTIVI E CONTENUTI

OBIETTIVI FORMATIVI

Apprendere i concetti e i risultati fondamentali della teoria degli automi e della teoria della calcolabilità.

OBIETTIVI FORMATIVI (DETTAGLIO) E RISULTATI DI APPRENDIMENTO

Al termine dell'insegnamento gli studenti avranno acquisito  alcuni concetti e risultati fondamentali  nella cultura di un informatico (macchina astratta, riconoscimento di linguaggi, funzione calcolabile, decidibilità, halting problem) e saranno in grado di sviluppare semplici automi, anche attraverso l'utilizzo di simulatori. 

PREREQUISITI

Nozioni base su insiemi e funzioni; esperienza di programmazione in qualche linguaggio.

MODALITA' DIDATTICHE

Tradizionale

PROGRAMMA/CONTENUTO

Automi e Linguaggi
Alfabeti, stringhe, linguaggi
Automi a stati finiti deterministici (DFA) e  non deterministici (NFA)
Minimizzazione di DFA, espressioni regolari
Proprietà di chiusura dei linguaggi regolari, pumping lemma
Grammatiche context-free, automi push-down deterministici e non deterministici
Equivalenza di PDA e grammatiche CF
Proprietà di chiusura dei linguaggi CF, pumping lemma
 

Calcolabilità
Nozione di algoritmo e funzioni ricorsive primitive
Macchine di Turing e funzioni ricorsive
Tesi di Church-Turing, numerazione algoritmica delle funzioni ricorsive
Macchina di Turing universale e calcolatore
Problema dell'arresto, insiemi ricorsivi e ricorsivamente enumerabili, problemi decidibili e indecidibili
Riducibilità e teorema di Rice
Altri modelli di calcolo: funzioni mu-ricorsive, varianti delle macchine di Turing

TESTI/BIBLIOGRAFIA

Note a cura del docente.

 

DOCENTI E COMMISSIONI

Commissione d'esame

ELENA ZUCCA SCHILLANI (Presidente)

DAVIDE ANCONA

RICCARDO BIANCHINI (Supplente)

FRANCESCO DAGNINO (Supplente)

GIORGIO DELZANNO (Supplente)

LEZIONI

INIZIO LEZIONI

In accordo con il calendario didattico approvato dal Consiglio dei Corsi di Studio in Informatica

Orari delle lezioni

L'orario di tutti gli insegnamenti è consultabile all'indirizzo EasyAcademy.

ESAMI

MODALITA' D'ESAME

Scritto e orale

MODALITA' DI ACCERTAMENTO

La prova scritta verifica la capacità dello studente di mettere in pratica le nozioni viste a lezione. La prova orale verifica la comprensione dei concetti e la capacità di illustrarli in modo appropriato.

Calendario appelli

Dati Ora Luogo Tipologia Note
15/01/2024 14:00 GENOVA Scritto
09/02/2024 14:00 GENOVA Scritto
12/06/2024 14:00 GENOVA Scritto
15/07/2024 09:00 GENOVA Scritto
10/09/2024 14:00 GENOVA Scritto