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

Registro delle Lezioni

Le lezioni sono tenute da Moggi se non altrimenti specificato.
  1. 05/11/01 (2h). Formalizzazione delle nozioni di problema (di input-output) e di algoritmo (sequenziale e deterministico) mediante automi e nozioni derivate. Correttezza parziale e totale. Simulazione tra automi e sue proprieta'. Esempio: problema del sorting di una lista, formalizzazione del selection-sort a diversi livelli di astrazione, e relazione di simulazione.
  2. 07/11/01 (2h). Automi con transizioni pesate (a valori in un monoide ordinato) e rivitazione delle nozioni correlate. Esempi di monoidi per complessita' tempo e spazio. Dimostrazioni di correttezza parziale mediante invarianti. Esempi: selection-sort. Tecniche per dimostrare la terminazione di un automa.
  3. 08/11/01 (1h). Esempi di applicazione delle tecniche per correttezza parziale e terminazione: bubble-sort, correttezza del raffinamento dell'automa per insertion-sort (relazione di simulazione) Maggiorazione della complessita' in funzione della dimensione dell'input.
  4. 12/11/01 (2h). Schema divide-et-impera (a decomposizione variabile e fissa) per la definizione ricorsiva di funzioni parziali. Tecniche per dimostrare la terminazione e la correttezza parziale (albero delle chiamate ricorsive). Esempi: selection-sort (e insertion-sort).
  5. 14/11/01 (2h). Algoritmi divide-et-impera per insertion-sort, merge-sort e quick-sort: terminazione e correttezza parziale. dimostrazione di correttezza parziale. (Esempio di algoritmo divide-et-impera a decomposizione variabile: calcolo ottimale della moltiplicazione di una sequenza di matrici rettangolari.)
  6. 15/11/01 (1h). Calcolo ottimale della moltiplicazione di una sequenza di matrici rettangolari. Definizione ricorsiva della complessita' esatta di algoritmi divide-et-impera. Condizioni sufficienti per una maggiorazione della complessita' esatta.
    19/11/01 (2h). DOCENTE ASSENTE
    21/11/01 (2h). DOCENTE ASSENTE
  7. 22/11/01 (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. Moltiplicazione di grandi numeri.
  8. 26/11/01 (2h). Complessita'spazio (e tempo parallelo) di algoritmi divide-et-impera. Tipi di dato come algebre parziali eterogenee: segnature, termini, algebre, interpretazione dei termini. Definizione di simulazione e simulazione parziale.
  9. 28/11/01 (2h). Proprieta' di simulazioni e simulazioni parziale, relazione tra omomorfismi (tra algebre totali) e simulazioni. Composizione di simulazioni. 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).
  10. 29/11/01 (2h). Specifica della complessita' in termini del modello canonico esempi (insiemi finite e liste). Estensioni del tipo di dato set: complementazione, intervalli con ordine lineare discreto (unione di intervalli chiusi e limitati non adiacenti). Restrizioni del tipo di dato set: dizionari e alberi di ricerca binari (o tabelle hash).
  11. 03/12/01 (2h). Estensioni del tipo di dato set: intervalli con ordine lineare denso (unione di intervalli limitati non adiacenti), intervalli e complementazione (unione di intervalli non adiacenti, funzione caratteristica con un numero finito di punti di discontinuita').
  12. 05/12/01 (2h). Esercizi: implementazione della union per la rappresentazione ad unione di intervalli, implementazione della insert per la rappresentazione della funzione caratteristica. Rappresentazione degli insiemi usando B-tree (caso B-tree con 2-3 figli): rappresenta l'insieme delle foglie, e' un albero di ricerca, ed e' perfettamente bilanciato.
  13. 06/12/01 (2h). Implementazione dei dizionari con B-tree: le operazioni member, insert (overflow e suddivisione) e delete (underflow e concatenazione o bilanciamento).
  14. 10/12/01 (2h). 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. Implementazione ad heap (alberi binari quasi perfettamente bilanciati).
  15. 12/12/01 (2h). Implementazione di una heap usando un array e struttura ausiliaria analoga a bit-vector per implementare le operazioni di inserimento e cancellazione. Variazioni sul tipo set: il tipo delle funzioni parziali (a dominio finito) da U a V.
  16. 13/12/01 (2h). Grafi diretti (etichettati): definizioni generali, ed esempi. Rappresentazione di grafi: matrice di adiacenza e liste di adiacenza, altre rappresentazioni.
  17. 17/12/01 (2h). Algoritmi su grafi per calcolo in-degree e topological sorting: correttezza ed implementazione con complessita tempo O(V+E).
  18. 19/12/01 (2h). Algoritmo per il calcolo della tempistica ottimale (adattando il topological sorting). 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.
  19. 20/12/01 (1h). 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).

    VACANZE DI NATALE

  20. 07/01/02 (2h). 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.
  21. 09/01/02 (2h). Correttezza dell'algoritmo di Dijkstra mediante invariante. Costruzione dell'albero dei cammini minimi a partire dall'output dell'algoritmo di Dijkstra. Generalizzazione dell'algoritmo di Dijkstra ad un monoide ordinato linearmente.
  22. 10/01/02 (1h). 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. 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).
  23. 14/01/02 (2h). 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).
  24. 16/01/02 (2h). 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).
  25. 17/01/02 (1h). Esempi: cammino di lunghezza minima con capacita' massima, numero di cammini di lunghezza minima, cammino di capacita' massima con lunghezza minima (ACCENNO). La programmazione dinamica come ottimizzazione del divide-et-impera, grafo (DAG) delle chiamate ricorsive: cammini e chiamate ricorsive nel divide-et-impera.
  26. 21/01/02 (2h). 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, moltiplicazione ottimale di matrici.
  27. 23/01/02 (2h). Esempi di programmazione dinamica: coefficenti binomiali, problema dello zaino.
  28. 24/01/02 (1h). Esercizio: rappresentazione di fogli elettronici (con numero prefissato di celle) , approccio lazy al calcolo del valore delle celle usando visita di un grafo e topological sorting.

    SOSPENSIONE DELLE LEZIONI

  29. 04/03/02 (2h). Esercizi: algoritmi (di visita e topological sorting) per grafi rappresentati con liste di liste di adiacenza e nodi con informazione ausiliaria. Implementazione del semianello dei polinomi A[x] con liste ordinate di monomi (con coefficienti non nulli).
  30. 06/03/02 (1h). Esercizi: operazioni (somma, prodotto, chiusura transitiva) su matrici NxN a valori in A quasi ovunque nulle.
  31. 06/03/02 (2h). Conversione tra rappresentazioni (a lista ordinata degli elementi non nulli, e ad array nxn) di matrici q.o. nulle. Esercizi: output di un circuito booleano, approssimazione di funzioni reali mediante coperture di rettangoli.
  32. 11/03/02 (2h). Esercizi: test di inclusione per approssimazione di funzioni reali. Il modello di calcolo delle TM (ad un nastro), motivazione informale e automa associato. Linguaggio T-decidibile e T-semidecidibile.
  33. 13/03/02 (1h). Le classi di linguaggi R e RE, la tesi di Church (invarianza di R ed RE al variare del modello di calcolo). Inclusione di R in RE, TM canoniche e cardinalita' delle funzioni T-calcolabili.
  34. 14/03/02 (2h). COMPITINO
  35. 18/03/02 (2h). Esempi di problema decidibile (correttezza sintattica), semi-decidibile ma non decidibile (terminazione), e non semi-decidibile (correttezza semantica). Varianti delle TM: TM a m-nastri, input read-only, output write-only. Le classi di complessita' tempo TIME_m(f) e TIME(f). Simulazione di una TM a m-nastri con una TM ad 1 nastro.
  36. 20/03/02 (1h). Inclusione di TIME_m(f) in TIME_1(O(f^2)). La classe P dei problemi trattabili.
  37. 21/03/02 (2h). 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. Il teorema di linear speed-up: simulazione di m passi con pochi passi.
  38. 25/03/02 (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).
  39. 27/03/02 (1h). Simulazione di una RAM mediante una TM con la tecnica del log file.

    VACANZE PASQUALI

  40. 04/04/02 (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), automa non-deterministico associato, definizione di linguaggio deciso e tempo di lavoro. Le classi di complessita' non-deterministiche NTIME(f) e NSPACE(f). Risultati di speed-up e tape compression per le classi non-deterministiche.
  41. 08/04/02 (2h). 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. Complessita' spazio, numero di configurazioni raggiungibili, e loop detection tramite contatore. 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'.
  42. 10/04/02 (1h). Classi di linguaggi e linguaggi C-completi (rispetto ad una riduzione). TM canoniche e loro codifica come stringhe.
  43. 10/04/02 (2h). 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). RE-completezza di H. Non decidibilita' di K (e H). Caratterizzazione di R in termini di RE. Proprieta' di chiusura di R ed RE rispetto ai connettivi logici (RE non e' chiuso per complementazione).
  44. 15/04/02 (2h). Teorema S-m-n e definizione implicita di codifiche di TM. Non decidibilita' delle proprieta' estensionali dei programmi (Teorema di Rice). Esempi di proprieta' estensionali. Quantificazione esistenziale (illimitata), Caratterizzazione di RE in termini di R (predicato di Kleene). Chiusura di RE per quantificazione esistenziale illimitata.
  45. 17/04/02 (1h). Caratterizzazione di R ed RE in termini di enumerazioni.
  46. 18/04/02 (2h). Riassunto proprieta' di chiusura di R ed RE rispetto a: riduzione, connettivi logici, quantificazione (limitata ed illimitata). Tecniche per dimostrare/refutare l'appartenenza ad R/RE. Esempi: TOT, EQ, etc.
  47. 22/04/02 (2h). 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).
  48. 24/04/02 (1h). Inclusione di NSPACE in SPACE (teorema di Savitch).
  49. 29/04/02 (2h). Riduzione poly-time e/o log-space. Classi naturali: relazioni di inclusione, proprieta' di chiusura delle classi naturali rispetto ad operazioni insiemistiche, quantificazione limitata, e riduzione.
  50. 02/05/02 (2h). Problemi completi, varianti dell'halting problem, della TM universale, e problemi completi per P, NP e PSPACE. Teorema di gerarchia spazio.
  51. 06/05/02 (2h). Teorema di gerarchia tempo. Inclusioni strette tra classi naturali di complessita'. Caratterizzazione di NP in termini di P. Problemi logici che risultano essere completi per qualche classe naturale: CVP (P), monotone CVP (P), SAT (NP), circuit SAT (NP), HORNSAT (P), 2-SAT (NL), k-SAT (NP se k>2), QBF (PSPACE).
  52. 08/05/02 (1h). 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.
  53. 09/05/02 (2h). P-completezza di CVP: generazione mediante cicli for del circuito booleano 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. Riduzioni log-space per dimostrare completezza: CVP < monotone CVP (P); SAT < 3-SAT (NP).
  54. 13/05/02 (2h). Problemi completi (con accenno dimostrazione): Reachability NL-completo (mappare x in un problema di reachability per il grafo delle ID di M con input x); QBF PSPACE-completo (formula compatta, ma non in CNF, per esprimere P(u,v,n) esiste un cammino di lunghezza <= 2^n da x ad y nel grafo delle ID di M con input x). HORNSAT P-completo: costruzione del modello iniziale e verifica dei goal; riduzione di CVP a HORSAT (simile a riduzione a monotone CVP). 2-SAT NL-completo (senaza dimostrazione): grafo associato ad una 2-CNF. Problemi NP-completi su grafi non-orientati: 3_SAT < independent set < node cover, clique; 3-colorability (senza dimostrazione).
  55. 15/05/02 (1h). Problemi NP-completi su grafi orientati: hamilton path, travelling salesman problem. Problemi NP-completi numerici: integer programming, problema dello zaino.
  56. 16/05/02 (2h). Altri tipi di algoritmi: algoritmi paralleli (motiplicazione di matrici) con lavoro polinomiale eseguito in tempo poli-logaritmico; algoritmi probabilistici (test A*B=C) che rispondono correttamente quasi sempre e lavorano in tempo polinomiale. Il modello di calcolo delle RTM, la classe RP, il powering lemma. Il modello di calcolo dei circuiti (booleani), la nozione di lavoro e tempo, le classi NC^k. Posizionamento dell classi di complessita' RP e NC^k. L'ipotesi P=/=NP. Esercizi: chiusura per concatenazione di P e NP. chiusura per Kleene star di NP.
  57. 20/05/02 (2h). Esercizi: chiusura per Kleene star di P, chiusura per coding di NP (ed in parte di P), proprieta' di chiusura non soddisfatte da SPACE(n) ma valide per NP.
  58. 22/05/02 (1h). Esercizi: proprieta' di chiusura di classi di complessita' rispetto operazioni su linguaggi, appartenenza di linguaggi a classi di complessita'.
  59. 23/05/02 (2h). Esercizi: appartenenza di linguaggi a classi di complessita'. Controesempio a chiusura di R (ed altre classi) rispetto all'operazione prefix(L), contreesempio a chiusura di L e NL rispetto all'operazione k(L), se P=/=NP.
  60. 27/05/02 (2h) Esercizi: appartenenza di linguaggi a classi di complessita'. Relazioni di inclusione tra classi di di linguaqgi.
  61. 29/05/02 (1h) Esercizi su prima parte.