Calcolabilita' e Complessita' (Laurea Specialistica) - a.a. 2005/06

Registro delle Lezioni

  1. 03/10/05 (2h). 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. Esempio: problema del sorting, automa per il selection sort. Correttezza parziale e totale.
  2. 06/10/05 (2h). 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'. Esempio: raffinamento dell'auto per il selection sort con stati intermedi per la ricerca dell'elemento da selezionare. Monoidi ordinati e costi. Esempio di monoidi ordinati: (N,0,+,<) e (N,0,max,<).
  3. 10/10/05 (2h). Raffinamento delle definizioni (problema, automa, correttezza, simulazione) per tenere conto dei costi. Il modello di calcolo delle TM (deterministiche ad un nastro infinito) per problemi di decisione ed automa associato. Varianti delle TM con piu' nastri (o nastro semi-infinito). Definizione di 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 (i programmi C sintatticamente corretti, i programmi C senza I/O che terminano, i programmi C senza I/O che non terminano).

    13/10/05 (2h). docente assente

  4. 17/10/05 (2h). La tesi di Church (invarianza di R ed RE al variare del modello di calcolo). Dimostrazione di equivalenza tra TM ad 1 nastro e TM a piu' nastri mediante simulazione di una TM a m-nastri con una TM ad 1 nastro a 2*m tracce. Le classi di complessita' tempo TIME_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.
  5. 20/10/05 (2h). Inclusione di TIME(f) in TIME_1(O(f^2)) con f almeno lineare, mediante analisi di complessita' della simulazione di una TM a m-nastri con una TM ad 1 nastro a 2*m tracce. Nastri read-only, nastri marcati (si scrivono solo caratteri diversi da blank), nastri write-only (scrivono solo caratteri dell'alfabeto di input, e la testina non puo' tornare indietro). Altre varianti delle TM: traduttori (per calcolare funzioni da stringhe a stringhe) e TM off-line (per complessita' spazio). Codifica di problemi (input-output) mediante stringhe. Esempi: ordinamento (codifica numeri e sequenze), problemi logici (codifica formule), bproblemi su grafi (codifica grafi). Le classi di complessita' spazio SPACE_m(f) e SPACE(f) e TM offline. Inclusione di SPACE(f) in SPACE_1(O(f)).
  6. 24/10/2005 (2h) 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. Il modello di calcolo delle RAM e automa associato. Confronto con il modello delle TM, dimensione dell'input di una RAM (codifica binaria degli interi) Codifica (iniettiva) dell'input/output di una TM in quelli per una RAM, e cosa significa simulare una TM con una RAM.
  7. 27/10/05 (2h). Simulazione di una TM mediante RAM in O(n+f). Simulazione di una RAM mediante una TM off-line a piu' nastri con la tecnica del logfile, decompisizone delle istruzioni RAM in termini di fetch e write che opera su nastri di input e di log.
  8. 31/10/05 (2h). 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(n)^3). 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]. Le TM non-deterministiche (NDTM), definizione di linguaggio accettato/deciso da una NDTM.
  9. 04/11/05 (2h). NDTM, proof-search e programmazione logica. Esempio: problema della reachability (formulazione finitaria), algoritmo enumerativo esponenziale, algoritmo di visita polinomiale, algoritmo non deterministico. Le TM non-deterministiche (NDTM), definizione di tempo/spazio di lavoro. Le classi di complessita' non-deterministiche NTIME(f) e NSPACE(f), e le classi naturali NP, PSPACE e NPSPACE. Risultati di riduzione ad un nastro, speed-up e tape compression per le classi non-deterministiche. Automa deterministico A' corrispondente ad un automa non-deterministico A per accettare/decidere un linguaggio. Relazione tra NTIME e TIME. Simulazione di una TM non-deterministica mediante una TM deterministica mediante visita BFS dell'albero/grafo delle possibili computazioni (istanza della Tesi di Church, ma non di quella estesa).
  10. 07/11/05 (2h). Relazioni tra classi di complessita' spazio/tempo e determistiche/non-deterministiche: Relazione tra NTIME e SPACE, basata su algoritmo che usa poco spazio per effettuare la BFS dell'albero delle computazioni. Relazione tra NSPACE e TIME o SPACE (teorema di Savitch), basata su 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 inclusione derivate.
  11. 10/11/05 (2h). 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, classi naturali chiuse per <_P. Riduzione log-space <_L (algoritmi log-space e programmi con for loop), composizione in serie di TM offline con tecnica demand-driven, proprieta' transitiva di <_L, classi naturali chiuse per <_L. Inclusione tra <_L, <_P e <.
  12. 14/11/05 (2h). 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)). I linguaggi H (halting problem, codifica delle coppie) e K, non decidibilita' di K e H.
  13. 17/11/2005 (2h). RE-completezza di H per <_L (e le altre riduzioni). 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).
  14. 21/11/05 (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.
  15. 24/11/2005 (2h) Caratterizzazione di R ed RE in termini di enumerazioni. ESERCIZI su calcolabilita' del tipo "dire se un linguaggio appartiene ad R o RE". TOT e <{f}> non sono in RE. Proprieta' di chiusura derivate per R ed RE: concanenazione L L', chiusura riflessiva e transitiva L^*, k(L) e k^*(L).
  16. 28/11/2005 (2h) SOLUZIONI agli esercizi. Esempi di linguaggi decidibili/semi-decidibili di natura logica: derivazioni e teoremi nella logica dei predicati (FOL), RE-completezza per i teoremi nella logica equazionale dei predicati.
  17. 01/12/2005 (2h) Teorema di gerarchia spazio. Teorema di gerarchia tempo. Inclusioni strette tra classi naturali di complessita'. Inesistenza di linguaggi R_completi per <_P.
  18. 05/12/2005 (2h) 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.
  19. 12/12/2005 (2h) Chiusura per Kleene star di P (usare programmazione dinamica) e di NL (sfruttare il non-determinismo). Caratterizzazione di NP in termini di P (sfruttando analisi di complessita' per la TM universale e per il predicato di Kleene). 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).
  20. 15/12/2005 (2h) 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. Problemi su circuiti booleani: CIRCUIT SAT (NP), CVP (P) [vedi libro per completezza], MONOTONE CVP (P).
  21. 19/12/2005 (2h) 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: clique (independent set, node cover), hamilton path, travelling salesman problem, 3-colorability. Alcuni esempi di riduzione. Problemi NP-completi numerici: integer programming (ma linear programming e' in P), knapsack QBF PSPACE-completo (formula compatta, ma non in CNF, per esprimere P(u,v,n) esiste un cammino di lunghezza <= 2^n da u a v nel grafo delle ID di M con input x).
  22. 22/12/2005 (2h) Esercizi su COMPLESSITA' (dati negli appelli Gen-Set 2005). NP e' diverso da SPACE(n) (perche' quest'ultimo non e' chiuso per riduzione poly-time). P non e' chiuso per coding se P e' diverso da NP (esiste L in P t.c. k(L) e' NP-completo).