Informatica Teorica 2012/2013

1) Calcolabilita'.

Concetti preliminari: Cardinalità di insiemi, Insiemi numerabili e non numerabili, Diagonalizzazione,

Macchine di Turing: Definizioni ed esempi, Macchine ad un nastro e a k nastri, Macchine di Turing deterministiche e non deterministiche e loro equivalenza, Macchina di Turing universale, Macchine di Turing con oracolo.

Linguaggi e funzioni: Linguaggi e linguaggi complemento, Accettabilità e decidibilità di linguaggi, Calcolabilità di funzioni, Tesi di Church-Turing, Linguaggi non decidibili, Riducibilità tra linguaggi.

2) Complessità.

Problemi e codifiche: Problemi decisionali, Problemi complementari, Problemi di ottimizzazione.

Misure di complessità: Misure statiche e dinamiche, Assiomi di Blum, DTIME, DSPACE, NTIME, NSPACE.

Classi di linguaggi: Inclusione, Completezza, Funzioni time-constructible, Definizione delle classi di complessità spaziale e temporale, Teorema di accelerazione.

Classi di complessità temporale: classi complemento, chiusura rispetto a variazioni finite.

La classe P: Definizione, Riducibilità polinomiale e chiusura di P rispetto alla riducibilità polinomiale, Esempi di problemi in P (2-SAT, 2-COLORABILITA'), Funzioni in FP, Trasformazione di una funzione booleana in forma congiuntiva normale.

La classe NP: Definizione, Linguaggi NP-completi e Teorema di Cook, Chiusura rispetto alla riduzione polinomiale, Esempi di dimostrazioni di NP-completezza (3-SAT, Vertex Cover, 3-COLORABILITA', COLORABILITA', Independent Set, Clique, Hamiltonian Circuit/Path, Longest Path, Commesso Viaggiatore).

Algoritmi pseudo-polinomiali, problemi numerici e NP-completezza in senso forte: il problema Knapsack.

Oltre NP: La classe coNP, Definizione della gerarchia polinomiale, Complessità esponenziale: classi LEXP e PEXP (definizione).

Problemi di ottimizzazione: Le classi PO e NPO, Linguaggi soggiacenti, La questione "PO = NPO?", La classe APX, Appartenenza ad APX di min-Vertex Cover, non Appartenenza ad AXP di min-TSP (se P diverso da NP), Appartenenza ad AXP di min-TSP con disuguaglianza triangolare e algoritmo di Christofiedes.