Calcolabilita' e Complessita' (Laurea Specialistica) - a.a. 2006/07

Registro delle Lezioni

  1. 02/10/2006 (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. Correttezza parziale e totale. Esempio: problema del sorting, automa per il selection sort ed insertion sort. Esercizio: descrivere un automa per bubble sort. Tecnica dell'invariante per dimostrare la correttezza parziale.
  2. 05/10/2006 (2h). Tecnica per dimostrare la terminazione di un automa con stato (f_A e' una funzione totale). Se A risolve parzialmente P e f_A e' totale, allora A risolve totalmente P. Esempio: correttezza (invariante) e terminazione per il selection sort. Esercizio: dimostrare la correttezza degli automi per insertion sort e bubble sort. Simulazione tra automi e sue proprieta'. Esempio: raffinamento dell'automa 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,<). Accenni al raffinamento delle definizioni (problema, automa, correttezza, simulazione) per tenere conto dei costi.
  3. 09/10/2006 (2h). Il modello di calcolo delle TM (deterministiche ad un nastro infinito) per problemi di decisione ed automa associato. 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). Varianti delle TM con piu' nastri (o nastro semi-infinito). Nastri read-only, nastri write-only (scrivono solo caratteri dell'alfabeto di input, e la testina non puo' tornare indietro). Altre varianti delle TM: TM off-line (per complessita' spazio), traduttori (per calcolare funzioni da stringhe a stringhe),

    12/10/2006 (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). Richiami su O-notazione. La classe P dei problemi trattabili. La tesi di Church estesa (invarianza di P al variare del modello di calcolo). 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. Rappresentazione di dati mediante stringhe. Esempi: rappresentazione binaria di numeri, rappresentazion di matrici booleane (bit vector a liste).

  4. 16/10/2006 (2h). Codifica di problemi (input-output) mediante stringhe. Cambio di rappresentazione, rappresentazioni ragionevoli e irragionevoli (p.e. numeri in formato unario). Problemi logici (codifica formule), Problemi su grafi (codifica grafi). Stabilita' di P rispetto a cambi di rappresentazione polytime, e cambi di modelli di calcolo con costo di simulazione polytime p(n,t(n)). Varianti delle TM per la complessita' spazio: nastri read-only, nastri di lavoro 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). Le classi di complessita' spazio SPACE_m(f) e SPACE(f) e TM offline. Inclusione di SPACE(f) in SPACE_1(O(f)). Giustificazione della O-notazione per la complessita' spazio (teorema di tape-compression): inclusione di SPACE_m(f) in SPACE_m(g) se f e' in O(g). Riformulazione in termini di TM: per ogni TM off-line che lavora in spazio f e C>0 esiste una TM off-line che calcola la stessa funzione di M e lavora in spazio f/C.
  5. 19/10/2006 (2h). Dimostrazione del teorema di tape-compression: 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. Codifica (iniettiva) dell'input/output di una TM in quelli per una RAM, e cosa significa simulare una TM (decisore) con una RAM.
  6. 23/10/2006 (2h) Dimensione dell'input di una RAM (codifica binaria degli interi). 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 read, fetch e write che opera su nastri di input e di log. 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 [producendo output di dimensione esponenziale] con una TM che lavora in tempo polinomiale [e quindi puo' produrre solo un output di dimensione polinomiale].
  7. 26/10/2006 (2h). Le TM non-deterministiche (NDTM), automa non-deterministico e albero delle computazioni, definizione di linguaggio accettato/deciso da una NDTM. Le TM non-deterministiche (NDTM), definizione di tempo/spazio di lavoro. 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.

    30/10/2006 DOCENTE ASSENTE

  8. 02/11/2006 (2h). NDTM, proof-search e programmazione logica. Esempio: problema della reachability (formulazione finitaria), algoritmo non deterministico, algoritmo enumerativo esponenziale, algoritmo di visita polinomiale. Automa deterministico A' corrispondente ad un automa non-deterministico A per accettare/decidere un linguaggio: ad ogni passo visita un livello dell'albero delle computazione di A con input x. Relazione tra NTIME e TIME. Simulazione di una TM non-deterministica mediante una TM deterministica mediante visita BFS dell'albero delle possibili computazioni (istanza della Tesi di Church, ma non di quella estesa).
  9. 06/11/2006 (2h). Relazioni tra classi di complessita' spazio/tempo e determistiche/non-deterministiche: Relazione tra NTIME e SPACE, basata sull'algoritmo 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 ausiliario per accettazione). Sommario delle relazioni di inclusione tra classi di complessita'. Classi naturali e relazioni di inclusione derivate.
  10. 09/11/2006 (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, composizione in serie di TM offline con tecnica demand-driven, proprieta' transitiva di <_L, classi naturali chiuse per <_L. Inclusione tra <_L, <_P e <.
  11. 13/11/2006 (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)). Semidecidibilita' dei linguaggi H (halting problem, codifica delle coppie) e K, non decidibilita' di K e H.

    16/11/2006 (2h). DOCENTE ASSENTE

  12. 20/11/2006 (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. Riduzione di H a K (usando s-m-n), ed RE-completa di K per <. Proprieta' estensionali dei programmi come linguaggi della forma , esempi e non esempi di proprieta' estensionali, Teorema di Rice (riduzione di K a usando s-m-n).
  13. 23/11/2006 (2h). Proprieta' di chiusura di classi di linguaggi: riduzione, operazioni insiemistiche, quantificazione illimitata, quantificazione limitata. Proprieta' di chiusura derivate. 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 ed RE e controesempi.
  14. 27/11/2006 (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.
  15. 30/11/2006 (2h) Proprieta' di chiusura derivate per R ed RE: concanenazione L L', chiusura riflessiva e transitiva L^*, k(L) e k^*(L). 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.
  16. 04/12/2006 (2h) Teorema di gerarchia spazio. Teorema di gerarchia tempo. Inclusioni strette tra classi naturali di complessita'. Inesistenza di linguaggi R_completi per <_P.
  17. 07/12/2006 (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.
  18. 11/12/2006 (2h) 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). M |= F e' in P se F e' in BF, ed e' in PSPACE se F e' una QBF. Problemi logici correlati a SAT={F CNF|F e' soddisfacibile} che risultano essere completi per qualche classe naturale: SAT (NP), k-SAT (NP se k>2, SAT <_L 3-SAT), 2-SAT (NL), HORNSAT (P, usando modello minimo), QSAT (PSPACE).
  19. 14/12/2006 (1h) Esercizi: selezione di esercizi dati negli appelli Gen-Set 2006. NP e' diverso da SPACE(n) (perche' quest'ultimo non e' chiuso per riduzione poly-time).
  20. 18/12/2006 (2h) Problemi su circuiti booleani: CIRCUIT-SAT (NP), CVP (P), MONOTONE CVP (P). Riduzione di CIRCUIT-SAT a SAT. Metodo della tabella: corrispondenza riga descrizione istantanea, corrispondenza tabella computazione. P-completezza di CVP: circuito per calcolare una riga della tabella a partire dalla precedente, replicando una componente con 3 caratteri di input ed 1 in output (+ casi limite), e per calcolare se una riga e' una configurazione accettante. NP-completezza di SAT: NDTM normalizzate (con grado di non-determinismo 2), variabili booleane per rappresentare le scelte non deterministiche Problemi NP-completi su grafi: clique (node cover), hamilton path, 3-colorability. Problemi NP-completi numerici: integer programming (ma linear programming e' in P
  21. 21/12/2006 (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. Proprieta' di chiusura rispetto ad operazioni sui linguaggi di classi naturali di complessita' (analogie e differenze con i casi R ed RE): Chiusura per Kleene star di P (usare programmazione dinamica) e di NL (sfruttare il non-determinismo), P non e' chiuso per coding se P e' diverso da NP. Esercizi su calcolabilita': selezione di esercizi dati negli appelli Gen-Set 2006.