Algoritmi e Strutture Dati: Algoritmi, Calcolabilita' e Complessita' (III anno) - a.a. 2002/03

Registro delle Lezioni

Le lezioni sono tenute da Moggi se non altrimenti specificato.
  1. 28/10/02 (1h). Formalizzazione delle nozioni di problema (di input-output) e di algoritmo (sequenziale e deterministico) mediante automi e nozioni derivate. Correttezza parziale e totale. Automi con transizioni pesate (a valori in un monoide ordinato) e rivitazione delle nozioni correlate. Esempi di monoidi per complessita' tempo e spazio.
  2. 29/10/02 (2h). Dimostrazioni di correttezza parziale mediante invarianti. Tecnica per dimostrare la terminazione di un automa. Esempi: problema del sorting di una sequenza (di reali), formalizzazione del selection-sort e bubble-sort, dimostrazione di correttezza parziale e terminazione.
  3. 31/10/02 (2h). Automi con transizioni pesate, complessita' e maggiorazione in funzione della dimensione dell'input. Simulazione tra automi e sue proprieta'. Esempi di raffinamenti e simulazioni: selection-sort e bubble sort. Applicazione delle tecniche per correttezza parziale e terminazione per dimostrare che una relazione tra automi e' una simulazione.
  4. 05/11/02 (3h). Schema divide-et-impera per la definizione ricorsiva di funzioni parziali. Tecniche per dimostrare la terminazione e la correttezza parziale (albero delle chiamate ricorsive). Esempi: selection-sort, insertion-sort, merge-sort e quick-sort. Non-esempi: bubble-sort. Definizione ricorsiva della complessita' esatta per un algoritmo divide-et-impera.
  5. 08/11/02 (2h). Maggiorazioni della complessita' esatta (in funzione della dimensione del problema), il master method. Applicazioni delle tecniche di maggiorazione agli esempi visti, inadeguatezza della maggiorazione nel caso del quick-sort. Altri esempi di algoritmi divide-et-impera: Moltiplicazione di grandi numeri, calcolo ottimale della moltiplicazione di una sequenza di matrici rettangolari.
  6. 12/11/02 (3h). Tipi di dato come algebre parziali eterogenee: segnature, termini, algebre, interpretazione dei termini. Esempi: stack e insiemi (finiti). Definizione di simulazione e simulazione parziale. Metodologia di implementazione di un tipo di dato (a partire da un modello canonico). Esempi: naturali e sequenze binarie, insiemi finiti e liste (o bit-vector). Proprieta' di simulazioni e simulazioni parziale. Composizione di simulazioni. Relazione tra omomorfismi e simulazioni.
  7. 15/11/02 (2h). Implementazioni del tipo di dato set: a bit-vector, a liste o porzione di array (senza ripetizioni, ordinate). Possibili implementazioni delle operazioni per la rappresentazione a liste, discussione della loro correttezza e complessita'. Specifica della complessita' in termini del modello canonico, invece che dell'algebra che descrive l'implementazione.
  8. 19/11/02 (3h). Estensione del tipo di dato set con complementazione (U infinito): modo generico di definirsi una implementazione con complementazione avendo una senza complementazione (ma e' necessaria la differenza). Estensione del tipo di dato set con ordine lineare (denso) su U e operazione intervallo: unione di intervalli limitati e non adiacenti (in ordine crescente), funzione caratteristica con un numero finito di punti di discontinuita'.
  9. 22/11/02 (2h). DOCENTE ASSENTE
  10. 26/11/02 (3h). Restrizioni del tipo di dato set: dizionari e code di priorita'. Implementazione naive (a liste ordinate); alberi di ricerca binari (problema a stimare la complessita'); B-trees = albero di ricerca perfettamente bilanciato che rappresenta l'insieme delle foglie (caso con 2-3 figli). B-trees: relazione tra altezza e cardinalita' dell'insieme rappresentato, dimostrazione di correttezza di member per induzione sulla struttura dell'albero. Insert (overflow e suddivisione), proprieta' di correttezza per la funzione ausiliaria.
  11. 29/11/02 (2h). B-trees: delete (underflow e concatenazione o bilanciamento). Funzioni di conversione da B-tree a lista ordinata e viceversa calcolabili in tempo lineare, ed implementazione delle operazioni union, intersect, difference mediante conversione. Il tipo di dato code di priorita' (min e deletemin). Implementazione usando liste ordinate o B-tree. Modifica del modello canonico per liste di priorita' usando multi-insiemi.
  12. 03/12/02 (3h). Code di priorita: implementazione ad heap con albero quasi perfettamente bilanciato rappresentato mediante un array (costo logaritmico di insert e delmin). Grafi orientati (etichettati): definizioni generali, varianti. Rappresentazione di grafi: matrice di adiacenza e liste di adiacenza, altre rappresentazioni. Algoritmi su grafi (rappresentati con liste di adiacenza) per calcolo in-degree e topological sorting: correttezza ed implementazione con complessita tempo O(V+E).
  13. 06/12/02 (2h). DOCENTE ASSENTE
  14. 10/12/02 (3h). Correttezza del topological sorting mediante invariante. Test di aciclicita'. Tempistiche ottimali. Definizione di visita di un grafo, e sue proprieta' (nodi visitati=nodi raggiungibili, albero di visita). Schema generale per visite di grafi, usando un insieme di nodi esaminati e di nodi frontiera.
  15. 13/12/02 (2h). La visita BFS e DFS come istanze dello schema generale implementando la frontiera come coda e stack. Algoritmo per BFS in O(V+E), Algoritmo ricorsivo per DFS in O(V+E). Rappresentazione di grafi etichettati con reali positivi con matrici a valori reali positivi estesi. Lunghezza di un cammino e distanza tra nodi. L'algoritmo di Dijkstra per calcolare le distanze da un nodo in tempo O(V^2). Correttezza dell'algoritmo di Dijkstra mediante invariante.
  16. 17/12/02 (3h). Risultato di decomposizione di un cammino da u a v con nodi intermedi in U+w. Algoritmo di Floyd per il calcolo delle distanze. Semianelli (chiusi): definizione, esempi e costruzioni di semianelli (chiusi). Relazione tra matrici quadrate a valori in semianelli chiusi e grafi etichettati. Operazioni su matrici e loro interpretazione in termini di grafi: prodotto, chiusura transitiva (e riflessiva). Adattamento dell'algoritmo di Floyd per calcolare la chiusura transitiva in un semianello chiuso A: decomposizione univoca di un cammino proprio da u a v con nodi intermedi in U+w; ruolo della operazione a^*. Esempi di problemi su grafi che si possono ridurre ad un problema di chiusura transitiva mediante una opportuna scelta del semianello: esistenza di un cammino, cammino di lunghezza minima (con etichette a valori in R).

    20/12/02 LEZIONE CANCELLATA

    VACANZE DI NATALE

  17. 07/01/03 (3h). Esempi di problemi su grafi che si possono ridurre ad un problema di chiusura transitiva mediante una opportuna scelta del semianello: cammino di capacita' massima, cammino di lunghezza massima, insieme di stringhe (insiemi di caratteri) associato ai cammini da x ad y (archi etichettati con caratteri di un alfabeto). Esempio con semi-anello composito: numero di cammini di lunghezza minima. Contro-esempio (non soddisfa le proprieta' di un semi-anello): cammino di lunghezza minima tra quelli di capacita' massima. Variante dell'algoritmo di Floyd per costruirsi un cammino di lunghezza minima (se esiste): matrice con nodi intermedi.

    10/01/03 LEZIONE CANCELLATA

  18. 14/01/03 (3h). La programmazione dinamica come ottimizzazione del divide-et-impera. Analisi della complessita' tempo e spazio tra divide-et-impera e programmazione dinamica sulla base del grafo delle chiamate ricorsive: cammini e chiamate ricorsive (divide-et-impera), nodi raggiungibili e soluzioni da memorizzare (programmazione dinamica). Tecniche associate alla programmazione dinamica: approccio demand-driven, approccio bottom-up (e riduzione della complessita' spazio). Esempi di applicazione della programmazione dinamica: numeri di fibonacci, coefficenti binomiali, moltiplicazione ottimale di matrici, problema dello zaino (tecnica demand-driven preferibile).
  19. 17/01/03 (2h - inizio ore 15.30). Esercizi
  20. 21/01/03 (3h).RECUPERO Esercizi

    SOSPENSIONE DELLE LEZIONI

  21. 25/02/03 (1h). 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); classi naturali di complessita' ("problemi trattabili").
  22. 26/02/03 (1h). Richiami su automi deterministici: relazione di transizione, computazione, funzione calcolata, complessita' tempo, correttezza parziale e totale, simulazione tra automi e sue proprieta'. Esempio: sorting di una sequenza (di reali), formalizzazione del selection-sort.
  23. 28/02/03 (2h). Il modello di calcolo delle TM (ad un nastro) e automa associato. Linguaggio T-decidibile e T-semidecidibile. Le classi di linguaggi R e RE, inclusione di R in RE. La tesi di Church (invarianza di R ed RE al variare del modello di calcolo). Altri modelli di calcolo: RAM e automa associato, TM a m-nastri.

    03/03/03 DOCENTE IMPEGNATO CON ESAME DOTTORATO

  24. 05/03/03 (1h). Richiami su automi deterministici (solo per studenti del nuovo ordinamento): tecniche per dimostrare correttezza parziale e terminazione, esempi di invariante e simulazione.
  25. 07/03/03 (2h). Varianti delle TM: input read-only, output write-only, traduttori. Le classi di complessita' tempo TIME_m(f) e TIME(f). La classe P dei problemi trattabili. 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. Il teorema di linear speed-up: simulazione di molti passi con pochi passi.
  26. 10/03/03 (2h). COMPITINO 1a PARTE
  27. 12/03/03 (1h). Le classi di complessita' spazio SPACE_m(f) e SPACE(f) e TM offline. Simulazione di una TM a m-nastri di lavoro con una TM ad 1 nastro lavoro, inclusione di SPACE_m(f) in SPACE_1(f). Il teorema di tape-compression: rappresentazione di m caratteri con un carattere.
  28. 14/03/03 (2h). Il modello di calcolo delle RAM, automa associato, e relative classi di complessita' tempo. Confronto con il modello delle TM. Simulazione di una TM mediante RAM in O(f). Simulazione di una RAM mediante una TM con la tecnica del log file.
  29. 17/03/03 (2h). Crescita lineare della dimensione degli interi, e 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 f con una TM che lavora in tempo O(f^k(n)). Le TM non-deterministiche (NDTM), definizione di linguaggio deciso e tempo/spazio di lavoro. Le classi di complessita' non-deterministiche NTIME(f) e NSPACE(f).
  30. 19/03/03 (1h). Simulazione di una TM non-deterministica mediante una TM deterministica mediante visita BFS dell'albero delle possibili computazioni, e relazione tra NTIME e TIME. Esempi di algoritmi non-deterministici per SAT e Reachability.
  31. 21/03/03 (2h). Risultati di riduzione ad un nastro, speed-up e tape compression per le classi non-deterministiche. Relazione tra complessita' spazio e numero di configurazioni raggiungibili (tecnica di loop detection tramite contatore). Classi di complessita' tempo-spazio e deterministiche e non: risultati di inclusione ovvi. Inclusione NTIME in SPACE (visita per livelli dell'albero delle computazioni) e NSPACE in TIME (ricerca di un cammino nel grafo dell ID). Inclusione di NSPACE in SPACE (teorema di Savitch).
  32. 24/03/03 (2h). Classi naturali: relazioni di inclusione. La nozione di riduzione tra problemi. Proprieta' della riduzione, proprieta' di chiusura per riduzione dei problemi (semi)decidibili. Uso della riduzione per dimostrare la non (semi)decidibilita'. Riduzione poly-time e/o log-space. Proprieta' di chiusura delle classi naturali rispetto riduzione. Classi di linguaggi e linguaggi C-completi (rispetto ad una riduzione). TM canoniche ed equivalenza tra TM e TM canoniche.

    26/03/03 LEZIONE CANCELLATA

    28/03/03 LEZIONE CANCELLATA

  33. 31/03/03 (2h). Codifica TM canoniche come stringhe. La funzione universale (per riconoscitori e traduttori). La TM universale. I linguaggi H (halting problem, codifica delle coppie) e K, semidecidibilita' di H (usando la TM universale) e K (riducibile ad H). Non decidibilita' di K (e H). RE-completezza di H.
  34. 02/04/03 (1h). La TM universale per traduttori (con input read-only e output write-only). Teorema S-m-n e definizione implicita di codifiche di TM. Non decidibilita' delle proprieta' estensionali dei programmi (Teorema di Rice).
  35. 04/04/03 (2h). Esempi di proprieta' estensionali. Proprieta' di chiusura di R ed RE rispetto ai connettivi logici. Caratterizzazione di R in termini di RE (RE non e' chiuso per complementazione). Proprieta' di chiusura di R per` quantificazione limitata Predicato di Kleene. Chiusura di RE per quantificazione esistenziale illimitata, e per quantificazione limitata.

    07/04/03 LEZIONE CANCELLATA

    09/04/03 LEZIONE CANCELLATA

    11/04/03 LEZIONE CANCELLATA

  36. 14/04/03 (2h). Caratterizzazione di RE in termini di R (predicato di Kleene). Dimostrazioni alternative delle proprieta' di chiusura di RE usando il predicato di Kleene. Caratterizzazione di R ed RE in termini di enumerazioni.
  37. 16/04/03 (1h). Riassunto proprieta' di chiusura di R ed RE rispetto a: riduzione, connettivi logici, quantificazione (limitata ed illimitata). ESERCIZI: TOT, etc.

    vacanze pasquali

  38. 28/04/03 (2h). ESERCIZI su calcolabilita' del tipo "dire se un linguaggio appartiene ad R o RE". Dimostrazioni (per assurdo) che TOT non e' riducibile al complementare di K, e che funzioni con certe proprieta' non possono essere calcolabili.
  39. 30/04/03 (1h). proprieta' di chiusura delle classi naturali rispetto ad operazioni insiemistiche, quantificazione limitata (N, NL)
  40. 02/05/03 (3h recupero). proprieta' di chiusura delle classi naturali rispetto a quantificazione limitata (P, NP, PSPACE). Caratterizzazione di NP in termini di P. Analisi di complessita' per la TM universale e per il predicato di Kleene. Problemi completi: varianti della TM universale, e problemi completi per NL, P, NP e PSPACE ottenuti da varianti dell'halting problem.
  41. 05/05/03 (2h). Teoremi di gerarchia spazio e tempo. Inclusioni strette tra classi naturali di complessita'.
  42. 07/05/03 (1h). Problemi logici che risultano essere completi per qualche classe naturale: CVP (P), monotone CVP (P), SAT (NP), k-SAT (NP se k>2), 2-SAT (NL), HORNSAT (P), QBF (PSPACE). Verifica che SAT appartiene ad NP.
  43. 09/05/03 (2h). P-completezza di CVP. Metodo della tabella: corrispondenza riga descrizione istantanea, corrispondenza tabella computazione. Codifica booleana di una tabella, Circuito buoleano per calcolare la tabella corrispondente ad una 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.
  44. 12/05/03 (2h). NP-completezza di (riduzione di SAT a) 3-SAT e CIRCUIT SAT. P-completezza di (riduzione di CVP a) MONOTONE CVP. HORNSAT P-completo: costruzione del modello minimo e verifica dei goal; riduzione di CVP a HORSAT (simile a riduzione a monotone CVP). 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).
  45. 14/05/03 (1h). QBF PSPACE-completo: completamento della dimostrazione. Reachability e' ML-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.
  46. 16/05/03 (2h). Problemi NP-completi su grafi non-orientati: 3_SAT < independent set < node cover, clique; 3-colorability (senza dimostrazione). Problemi NP-completi su grafi orientati: hamilton path, travelling salesman problem. Problemi NP-completi numerici: integer programming, problema dello zaino.
  47. 19/05/03 (2h). Chiusura per concatenazione di P e NP. Chiusura per Kleene star di NP e P. Chiusura per coding di NP. P non e' chiuso per coding, se P non coincide con NP. NL-completezza di una variante di Reachability.
  48. 21/05/03 (1h). ESERCIZI su complessita'..
  49. 23/05/03 (2h). ESERCIZI su I parte.
  50. 26/05/03 (2h). ESERCIZI su complessita'.
  51. 28/05/03 (1h). ESERCIZI su calcolabilita'.
  52. 30/05/03 (2h). ESERCIZI su I parte.

    fine lezioni