119553 - LINGUAGGI FORMALI, COMPUTABILITA' E COMPLESSITA'

insegnamento
ID:
119553
Tipo Insegnamento:
Obbligatorio
Durata (ore):
48
CFU:
6
SSD:
INFORMATICA
Sede:
Ferrara - Università degli Studi
Url:
INTELLIGENZA ARTIFICIALE, DATA SCIENCE E BIG DATA/INTELLIGENZA ARTIFICIALE: DATA SCIENCE Anno: 1
Anno:
2024

Dati Generali

Periodo di attività

Primo Semestre (19/09/2024 - 17/12/2024)

Syllabus

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 problemi classici come la soddifacibilità di formule logiche, proposizionali, sub-proposizionali, e al primo ordine

Prerequisiti

Conoscenze basiche di logica e di programmazione in qualsiasi linguaggio.

Metodi didattici

Lezioni frontali. Lo studente può usufruire delle lezioni precedentemente registrate disponibili sulla pagina YouTube del docente.

Verifica Apprendimento

Esame orale. Durante il corso, verranno proposti degli esercizi scritti la cui valutazione potrà dispensare, in tutto o in parte, l'esame orale.

Testi

*************** ATTENZIONE
Le slide del corso saranno pubblicate su ClassRoom.

CODICE: tiakzjs
***************

1) M. Sispser, "Introduction to the Theory of Computation"

2) H. Lewis, C. Papadimitriou, "Elements Of The Theory Of Computation", 2Nd Edition

Contenuti

(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á

Lingua Insegnamento

ITALIANO

Corsi

Corsi

No Results Found

Persone