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
- 2019/2020
- 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.
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.
(4 ore): Le classi LOGSPACE, NLOGSPACE, PSPACE e NPSPACE. Il concetto di transduttore. Riduzioni. Teorema di Satvich.
(4 ore): Le classi EXPTIME, NEXPTIME, EXPSPACE, NEXPSPACE. Teoremi di separazione. Metodi didattici
- Lezioni frontali. Si tratta di un corso altamente teorico che viene affrontato in classe con lezioni partecipative e soluzione di problemi di complessitá crescente.
Modalità di verifica dell'apprendimento
- Esame orale. Durante l'esame si faranno 4/5 domande (valutate da 4 a 8 trentesimi ciascuna) di carattere teorico/pratico. Si chiederà, in un colloquio della durata di circa 30 minuti, la soluzione a qualche esercizio visto in classe, con particolare attenzione alla verifica delle conoscenze di carattere generale e concettuale.
Testi di riferimento
- *************** ATTENZIONE
Le slide el corso saranno pubblicate su ClassRoom. COdice corso: 2sehia
***************
1) M. Sispser, "Introduction to the Theory of Computation"
2) H. Lewis, C. Papadimitriou, "Elements Of The Theory Of Computation", 2Nd Edition
