Calcolabilita' e Complessita' (Laurea Specialistica) - a.a. 2004/05

Registro delle Lezioni

  1. 28/09/04 (3h). introduzione: differenza tra problemi e algoritmi; algoritmi e modelli di calcolo; classi di problemi "indipendenti" dal modello di calcolo; problemi decidibili e semi-decidibili (relazione con logica matematica); problemi trattabili. Prima formalizzazione: problemi P di input/output e automi A (deterministici) con stato, relazione di transizione, computazione, funzione calcolata f_A, funzione complessita' esatta T_A (numero di passi). Esempio: problema del sorting, automa per il selection sort. Correttezza parziale e totale. Tecniche per dimostrare correttezza parziale e terminazione di un automa con stato. Esempio: correttezza (invariante) e terminazione per il selection sort. Simulazione tra automi e sue proprieta'.
  2. 30/09/04 (2h). Il modello di calcolo delle TM (ad un nastro infinito) ed automa associato. Varianti delle TM con piu' nastri e/o nastri semi-infiniti. Linguaggio T-decidibile e T-semidecidibile. Le classi di linguaggi R e RE, inclusione di R in RE. Esempi informali di linguaggi appartenenti e non a R ed RE. Dimostrazione di equivalenza tra TM a nastro infinito e TM a nastro semi-infinito mediante l'uso di relazioni di simulazione.

    05/10/04 (3h). docente assente

  3. 07/10/04 (2h). La tesi di Church (invarianza di R ed RE al variare del modello di calcolo). Codifica di problemi (input-output) mediante stringhe. Altre varianti delle TM: input read-only, output write-only, traduttori.
    Le classi di complessita' tempo TIME_m(f), TIME^semi_m(f) e TIME(f). La classe P dei problemi trattabili. La tesi di Church estesa (invarianza di P al variare del modello di calcolo). Richiami su O-notazione. Inclusione di TIME_m(f) in TIME^semi_m(O(n+f)) e simulazione di una TM a m-nastri infiniti con una TM ad m nastri semi-infiniti a 2 tracce. Inclusione di TIME_m(f) in TIME_1(O(f^2)) e simulazione di una TM a m-nastri con una TM ad 1 nastro a 2*m tracce.
  4. 12/10/04 (3h). Le classi di complessita' spazio SPACE_m(f) e SPACE(f) e TM offline. Inclusione di SPACE_m(f) in SPACE_1(f) e SPACE^semi_m(f) usando le stesse costruzioni di TM viste usate per le inclusioni tra classi di complessita' tempo. Giustificazione della O-notazione: il teorema di tape-compression: inclusione di SPACE_m(f) in SPACE_m(g) se f e' in O(g); rappresentazione di un blocco di m caretteri con 1 carattere. Il teorema di linear speed-up: inclusione di TIME_m(f) in TIME_m(g) se f e' in O(g) [m>1, f lineare e g super-lineare]; simulazione di m passi (automa derivato A^m_M) con pochi passi.
  5. 14/10/04 (2h). Il modello di calcolo delle RAM e automa associato. Confronto con il modello delle TM. Simulazione di una TM mediante RAM in O(n+f).
  6. 19/10/04 (3h). Simulazione di una RAM mediante una TM off-line a piu' nastri con la tecnica del log file. Crescita lineare della dimensione degli interi e degli indirizzi di memoria modificati, simulazione di una RAM che lavora in tempo f con una TM che lavora in tempo O(f^3(n)). Impossibilita' di simulare una RAM con moltiplicazione che lavora in tempo polinomiale [e calcola 2^(2^(log n))] con una TM che lavora in tempo polinomiale [e quindi puo' produrre solo un output di dimensione polinomiale].
  7. 21/10/04 (2h). Le TM non-deterministiche (NDTM), definizione di linguaggio accettato/deciso e tempo/spazio di lavoro. Automa deterministico A' corrispondente ad un automa non-deterministico A per accettare/decidere un linguaggio. Le classi di complessita' non-deterministiche NTIME(f) e NSPACE(f), e la classe NP. Risultati di riduzione ad un nastro, speed-up e tape compression per le classi non-deterministiche. Esempio: problema della reachability (formulazione finitaria), algoritmo enumerativo esponenziale, algoritmo di visita polinomiale, algoritmo non deterministico. Simulazione di una TM non-deterministica mediante una TM deterministica mediante visita BFS dell'albero/grafo delle possibili computazioni

    26/10/04 (3h) - docente assente GPCE

    28/10/04 (2h) - docente assente GPCE

    02/11/04 (3h) - docente assente FMCO

    04/11/04 (2h) - docente assente FMCO

    09/11/04 (3h) - sospensione per compitini

    11/11/04 (2h) - sospensione per compitini

  8. 16/11/04 (3h). Relazione tra NTIME e SPACE, basata su visita BFS dell'albero delle computazioni. Relazione tra NSPACE e TIME o SPACE (teorema di Savitch), basata su esistenza di un cammino da configurazione iniziale ad accettante nel grafo delle configurazioni (raggiungibili da quella iniziale). Inclusione NSPACE in TIME e in SPACE (teorema di Savitch): ricerca di un cammino nel grafo delle ID di dimensione prefissata (con nodo target ausiliario). Sommario delle relazioni di inclusione tra classi di complessita'. Classi naturali e relazioni di derivate inclusione. La nozione di riduzione < tra problemi. Proprieta' della riduzione, proprieta' di chiusura per riduzione dei problemi (semi)decidibili. Classi di linguaggi chiusi per riduzione e linguaggi C-completi. Riduzione poly-time <_P e classi naturali chiuse per <_P. Riduzione log-space <_L e classi naturali chiuse per <_L (senza dimostrazione). Inclusione tra <_L, <_P e <.
  9. 18/11/04 (2h). Composizione in serie di TM offline con tecnica demand-driven: proprieta' transitiva di <_L e classi naturali chiuse per <_L. TM canoniche ed equivalenza tra TM e TM canoniche. Codifica TM canoniche (ad 1 nastro) come stringhe. La funzione universale U. La TM universale M_U, e relazione tra la complessita' tempo di M_U(< M >,x) e M(x): T_U(< M >,x) in O(|< M >| * T_M(x)).
  10. 23/11/04 (3h). I linguaggi H (halting problem, codifica delle coppie) e K, RE-completezza di H per <_L, Non decidibilita' di K e H. Funzioni calcolabili n-arie, e variante n-aria U_n della funzione universale. Teorema S-m-n e definizione implicita di codifiche di TM. Proprieta' estensionali dei programmi come linguaggi della forma , esempi e Teorema di Rice. Proprieta' di chiusura di classi di linguaggi: riduzione, operazioni insiemistiche, quantificazione illimitata, quantificazione limitata. Proprieta' di chiusura di R ed RE rispetto ad operazioni insiemistiche (e per quantificazione - solo enunciati).

    25/11/04 (2h) - docente impegnato in concorso

    30/11/04 (3h) - lezione sospesa per sciopero

  11. 02/12/04 (2h). Caratterizzazione di R in termini di RE (RE non e' chiuso per complementazione). Predicato di Kleene (codifica di computazioni come sequenze di quintuple), e Caratterizzazione di RE in termini di R. Proprieta' di chiusura di R per quantificazione limitata. Chiusura di RE per quantificazione esistenziale illimitata, e per quantificazione limitata. R e RE non sono chiusi per quantificazione universale illimitata. Caratterizzazione di R ed RE in termini di enumerazioni.
  12. 07/12/04 (3h). ESERCIZI su calcolabilita' del tipo "dire se un linguaggio appartiene ad R o RE". TOT ed EQ non sono in RE. Dimostrazione per assurdo che funzioni con certe proprieta' non sono calcolabili. Proprieta' di chiusura derivate per R ed RE: k(L) e k^*(L). Teorema di gerarchia spazio.
  13. 09/12/04 (2h). Teorema di gerarchia tempo. Inclusioni strette tra classi naturali di complessita'. Proprieta' di chiusura delle classi naturali rispetto ad operazioni insiemistiche, e quantificazione limitata (per L e NL si usa tecnica demand-driven). Problemi completi rispetto a <_L: varianti della TM universale, e problemi completi per NL, P, NP e PSPACE, EXP ottenuti da varianti dell'halting problem.
  14. 14/12/04 (3h). Caratterizzazione di NP in termini di P (sfruttando analisi di complessita' per la TM universale e per il predicato di Kleene). Esempi di problemi RE-completi di natura logica: {(Ax,eq) | eq e' derivabile da Ax nella logica equazionale}, {F| F tautologia della logica del primo ordine}. Formule booleane (BF), BF quantificate (QBF), forme normali congiuntive (CNF). Problemi logici correlati a SAT che risultano essere completi per qualche classe naturale: SAT (NP), k-SAT (NP se k>2), 2-SAT (NL), HORNSAT (P), QSAT (PSPACE). Metodo della tabella: corrispondenza riga descrizione istantanea, corrispondenza tabella computazione. NP-completezza di SAT: codifica di una tabella mediante variabili booleane; formula in CNF per esprimere che esiste una tabella che rappresenta una computazione accettante.
  15. 16/12/04 (2h). Problemi su circuiti booleani: CIRCUIT SAT (NP), CVP (P) [vedi libro per completezza], MONOTONE CVP (P). Reachability e' NL-completo: mappare x in un problema di reachability per il grafo delle ID di M con input x, con M NDTM con input read-only che lavora in spazio logaritmico. Problemi NP-completi su grafi: hamilton path, travelling salesman problem, clique (independent set, node cover), 3-colorability Problemi NP-completi numerici: integer programming (ma linear programming e' in P), knapsack
  16. 21/12/04 (3h). Chiusura per concatenazione di NP e P (usare quantificazione log-limitata). Chiusura per Kleene star di NP (usare quantificazione poly-limitata) e P (usare programmazione dinamica). Chiusura per coding di NP. P non e' chiuso per coding, se P non coincide con NP. NP e' diverso da SPACE(n) (quest'ultimo non e' chiuso per riduzione poly-time e per quantificazione esistenziale poly-limitata). Esercizi su COMPLESSITA'.