LINGUAGGI FORMALI, CALCOLABILITA' E COMPLESSITA'
Anno accademico e docente
Non hai trovato la Scheda dell'insegnamento riferita a un anno accademico precedente?
Ecco come fare >>
- English course description
- Anno accademico
- 2022/2023
- Docente
- GUIDO SCIAVICCO
- Crediti formativi
- 6
- Periodo didattico
- Secondo Semestre
- SSD
- INF/01
Obiettivi formativi
- Il corso introduce le principali metodologie per l'analisi della calcolabilitá e della complessitá di un problema decisionale.
Argomenti trattati (Conoscenze):
- introduzione ai problemi decisionali e relazione con i problemi funzionali e di ottimizzazione.
- linguaggi regolari, Pumping Lemma, esistenza di linguaggi non regolari, automi a stati finiti
- linguaggi liberi dal contesto, Pumping Lemma, esistenza di linguaggi non liberi dal contesto, automi a pila
- modello della macchina di Turing e tesi di Church-Turing
- riduzioni many one e riduzioni di Turing; esistenza di problemi non decidibil, esempi di problemi noti non decidibili, teorema di Rice
- concetto di classe di complessitá
- la classe P e la classe NP, e relazione tra P ed NP
- problemi NP-completi
- approssimazione a problemi NP-completi
- le classi NLOGSPACE, PSPACE, e NPSPACE, e teorema di Satvich
- altre classi importanti e teoremi di separazione.
- accenno alla relazione che sussiste tra la teoria della computabilitá e l'intelligenza artificiale moderna
Al termine del corso lo studente sará capace di (Abilitá)
- riconoscere un problema decisionale calcolabile da uno non calcolabile (in certi casi semplici)
- riconoscere la classe di complessitá di un problema calcolabile (in certi casi semplici)
- comprendere la matematica alla base di un problema e le questioni relative alla sua classificazione
- comprendere il ruolo giocato da certi problemi classici, soprattutto di tipo logico Prerequisiti
- Conoscenze basiche di logica e di programmazione in qualsiasi linguaggio. Aver superato con successo l'esame di Algoritmi e Strutture Dati.
Contenuti del corso
- (4 ore): Introduzione. Problemi decisionali. Problemi non decisionali e relazioni tra problemi.
(8 ore): Logica proposizionale, del primo ordine, soddisfacilibilità, validità, metodi automatici per il ragionamento, logiche sub-proposizionali, loigiche super-proposizionali, concetto di complessità descrittiva.
(4 ore): Tesi di Church-Turing attraverso modelli alternativi della macchina di Turing e loro essenziale equivalenza. Definizione di problema decisionale calcolable e semi-calcolabile. Esistenza di un problema non calcolabile.
(4 ore): Modello e concetto di riduzione many one e Turing. Le classi DEC, RE, e CO-RE, esempi classici di problemi non calcolabili e semi-calcolabili. Il concetto di problema RE-completo e CO-RE-completo.
(4 ore): Il problema della soddisfacibilitá di formule della logica del primo ordine (il caso della logica del primo ordine dei numeri naturali).
(4 ore): Definizione di classe di complessitá. La classe P e la classe NP. Il concetto di problema NP-completo.
(4 ore): Problemi classici NP-completi e relative riduzioni. Approssimazione a problemi NP-completi.
(3 ore): Le classi LOGSPACE, NLOGSPACE, PSPACE e NPSPACE. Il concetto di transduttore. Riduzioni. Teorema di Satvich.
(3 ore): Le classi EXPTIME, NEXPTIME, EXPSPACE, NEXPSPACE. Teoremi di separazione.
(2 ore): IA moderna e relazione con la teoria della computabilitá Metodi didattici
- Lezioni frontali. Lo studente può usufruire delle lezioni precedentemente registrate disponibili sulla pagina YouTube del docente.
Modalità di verifica dell'apprendimento
- Esame orale.
Testi di riferimento
- *************** ATTENZIONE
Le slide el corso saranno pubblicate su ClassRoom.
***************
1) M. Sispser, "Introduction to the Theory of Computation"
2) H. Lewis, C. Papadimitriou, "Elements Of The Theory Of Computation", 2Nd Edition
