Teoria della Computabilita'

Teoria della Computabilità (A.A. 2011/12)

N. crediti: 9
Orario delle lezioni: Lunedì e Mercoledì dalle 8:00 alle 11:00 (Aula 24)
Orario di ricevimento
Testi consigliati

N.J. Cutland. Computability: an introduction to recursive function theory, Cambridge University Press, Cambridge - UK, 1986. [Testo principale]
M.D. Davis, R. Sigal, E.J. Weyuker. Computability, Complexity, and Languages: Fundamentals of Theoretical Computer Science, Academic Press, New York, 1994.
M. Sipser. Introduction to the Theory of Computation, PWS Publishing Company (2nd ed.), 2005. [Lettura consigliata]
M. Garey, D. Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman and Co., 1979. [Lettura consigliata]

MATERIALE DIDATTICO ON-LINE

MODULO DI COMPUTABILITÀ

Programma del corso, introduzione, macchine URM, computazioni, funzioni calcolabili, parziale e totale correttezza di programmi URM
(Agg. 06/03/12)

Decidibilità di predicati, calcolabilità su altri domini, funzioni di base, composizione di funzioni
(Agg. 26/03/12)

Ricorsione, definizione per casi, somme e prodotti limitati, minimalizzazione limitata, funzioni primitive ricorsive
(Agg. 31/03/12)

Notazione "uparrow" di Knuth, funzione di Ackermann, calcolabilità della funzione di Ackermann, Loop Programs, Bounding Theorem, dimostrazione che la funzione di Ackermann non è primitiva ricorsiva
(Agg. 31/03/12)

Minimalizzazione
(Agg. 5/04/11)

Altri approcci alla calcolabilità, funzioni parziali ricorsive, funzioni μ-ricorsive, equivalenza tra funzioni URM-calcolabili e funzioni parziali ricorsive, relazione tra funzioni μ-ricorsive e funzioni parziali ricorsive, tesi di Church
(Agg. 5/04/11)

Enumerazione delle funzioni calcolabili, metodo diagonale di Cantor, teorema di parametrizzazione (s-m-n)
(Agg. 7/04/11)

Funzioni "busy beaver" (o del "castoro indaffarato") e loro non calcolabilità
(Agg. 13/04/12)

Programmi universali, forma normale di Kleene, indecidibilità del problema "φ_x è totale", esistenza di una funzione calcolabile totale non primitiva ricorsiva mediante diagonalizzazione, operazioni effettive su funzioni calcolabili e loro domini e codomini
(Agg. 16/04/12)

Definizione per casi con funzioni calcolabili (anche parziali)
(Agg. 24/04/12)

Problemi indecidibili, tecnica della riduzione, teorema di Rice, indecidibilità in altri domini, predicati parzialmente decidibili
(Agg. 28/04/10)

Insiemi ricorsivamente enumerabili, varie caratterizzazioni, teorema di Rice-Shapiro
(Agg. 12/05/11)

MODULO DI COMPLESSITÀ (a cura del Dott. Salvatore Cristofaro)

Notazioni asintotiche
Macchine di Turing e loro formalizzazione
Funzioni numeriche (Turing) computabili
Macchine di Turing multi-nastro
Relazioni tra macchine di Turing e macchine di Turing multi-nastro
Classi di complessità temporale
La classe NP
NP-completezza
Il problema della soddisfacibilità proposizionale (SAT)
Teorema di Cook
Catalogo di problemi NP-completi (3-SAT, n-SAT, VertexCover, CLIQUE, IndependentSet,
HamiltonianPath, HamiltonianCircuit, LongestSimplePath, SetCover, HittingSet,
SubgraphIsomorphism, TravelingSalesman, 3-DimensionalMatching, Partition, SubsetSum, Knapsack)
Complessità spaziale delle macchine di Turing

link alla dispensa
(Agg. 05/11/12)