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

PRESENTAZIONE

L'insegnamento 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 le nozioni di automa, riconoscimento di linguaggi, funzione calcolabile. Saper classificare i linguaggi a seconda degli automi in grado di riconoscerli. Essere in grado di valutare se un problema è decidibile/semi-decidibile.

OBIETTIVI FORMATIVI (DETTAGLIO) E RISULTATI DI APPRENDIMENTO

Al termine dell'insegnamento lo studente/la studentessa sarà in grado di:

  • Conoscere alcuni concetti e risultati fondamentali  nella cultura di un informatico (macchina astratta, riconoscimento di linguaggi, funzione calcolabile, decidibilità, halting problem).
  • Sviluppare semplici automi, anche attraverso l'utilizzo di simulatori. 

PREREQUISITI

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

MODALITA' DIDATTICHE

Lezioni frontali.

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

LEZIONI

INIZIO LEZIONI

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

https://corsi.unige.it/corsi/8759/studenti-orari

Orari delle lezioni

L'orario di questo insegnamento è consultabile all'indirizzo: Portale EasyAcademy

ESAMI

MODALITA' D'ESAME

L'esame consiste in una prova scritta e in una prova orale.Per poter
sostenere la prova oraleè necessario avere superato la prova scritta.

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.

ALTRE INFORMAZIONI

Rivolgersi al docente per ulteriori informazioni non comprese nella scheda insegnamento.