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

Registro delle Lezioni

Le lezioni sono tenute da Moggi se non altrimenti specificato.
  1. 07/11/00 (1h). Formalizzazione delle nozioni di problema (di input-output) e di algoritmo (sequenziale e deterministico) mediante automi.
  2. 08/11/00 (2h). Automi con transizioni pesate (a valori in un monoide ordinato) e nozioni derivate. Esempi di monoidi per complessita' tempo e spazio. Correttezza parziale e totale. Dimostrazioni di correttezza parziale mediante invarianti. Esempi: selection-sort, bubble-sort.
  3. 10/11/00 (2h). Simulazione tra automi e sue proprieta'. Raffinamento dell'algoritmo per il selection-sort. Tecniche per dimostrare la terminazione di un automa. Maggiorazione della complessita' in funzione della dimensione dell'input.
    14/11/00 (1h). NON C'E' LEZIONE
  4. 15/11/00 (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. Esempi: selection-sort, insertion-sort.
  5. 17/11/00 (2h). Algoritmi divide-et-impera per merge-sort e quick-sort. Esempi di dimostrazione di correttezza parziale. Esempio di algoritmo divide-et-impera a decomposizione variabile: calcolo ottimale della moltiplicazione di una sequenza di matrici rettangolari.
  6. 21/11/00 (1h). Definizione ricorsiva della complessita' esatta di algoritmi divide-et-impera, maggiorazioni della complessita' esatta (in funzione della dimenzione del problema), il master method.
  7. 22/11/00 (2h). Esempi di analisi di complessita' tempo (spazio e tempo parallelo) di algoritmi divide-et-impera, e bonta' delle maggiorazioni trovate.
  8. 24/11/00 (2h). Altri esempi di algoritmi divide-et-impera: moltiplicazione di grandi numeri, torre di Hanoi. Tipi di dato come algebre parziali eterogenee (richiami).
  9. 28/11/00 (1h). Definizione di simulazione e simulazione parziale, relazione tra omomorfismi (tra algebre totali) e simulazioni. Esempi di simulazioni: naturali e sequenze binarie, insiemi finiti e bit-vector.
  10. 29/11/00 (2h). Esempi di simulazioni: implementazioni di insiemi finiti mediante liste e array, implementazione di dizionari mediante array ordinati e tabelle hash aperte. Specifica della complessita' in termini del modello canonico.
    01/12/00 (2h). NON C'E' LEZIONE
  11. 05/12/00 (3h). Code di priorita': motivazione, segnatura, modello canonico, limitazioni delle implementazioni di base. Implementazione ad albero binario: proprieta' dell'albero, implementazione delle operazioni, complessita'. Uso di heap per la rappresentazione dell'albero e relazione di simulazione rispetto al modello canonico. Grafi diretti (etichettati): definizioni generali, ed esempi. Rappresentazione di grafi: matrice di adiacenza e liste di adiacenza, altre rappresentazioni.
  12. 06/12/00 (2h). Algoritmi su grafi: calcolo in-degree e topological sorting O(V+E). Accenno a visite di un grafo.
    08/12/00 (2h). VACANZA
  13. 12/12/00 (1h). Schema generale per visite di grafi, usando un insieme di nodi esaminati e di nodi frontiera. La visita BFS come istanze dello schema generale implementando la frontiera come una coda.
  14. 13/12/00 (2h). Correttezza e terminazione per gli algoritmi di visita generale e visita BSF (riformulandoli come automi). Algoritmo per il calcolo della tempistica ottimale (adattando il topological sorting).
  15. 15/12/00 (2h). Visita DFS: implementazione a stack e ricorsiva. 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.
  16. 19/12/00 (1h). Adattamento dell'algoritmo di Dijkstra per calcolare i cammini minimi, e rappresentazione dei cammini minimi mediante un albero.
  17. 20/12/00 (2h). Risultato di decomposizione di un cammino da u a v con nodi intermedi in U+w. Algoritmo di Floyd per il calcolo delle distanze: addattamento al caso di archi con pesi negativi e chiusura di un numero reale, variante che lavora in spazio O(V^2), variante per ricostruire i cammini minimi.
  18. 22/12/00 (2h). Semianelli chiusi: definizione, esempi, costruzioni su semianelli (semianello prodotto, semianello delle matrici quadrate). 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).
  19. 09/01/01 (1h). Adattamento dell'algoritmo di Floyd per calcolare la chiusura transitiva di una matrice quadrata a valori in un semianello chiuso. 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, cammino di lunghezza massima, cammino di capacita' massima, numero dei cammini.
  20. 10/01/01 (2h). Implementazione del tipo di dato set con alberi binari di ricerca, complessita' tempo ed il problema del bilanciamento degli alberi. Implementazione del tipo di dato set con alberi 2-3.
  21. 12/01/01 (2h). Implementazione del tipo di dato set con alberi 2-3: operazioni di inserimento e cancellazione con ribilanciamento. La struttura dati B-tree per rappresentare associazioni chiave-dati in memoria secondaria.
  22. 16/01/01 (2h). B-tree: operazione di inserimento.
  23. 17/01/01 (1h). B-tree: operazione di cancellazione. Esercizi: applicazioni della chiusura riflessiva e transitiva per calcolare il numero di cammini minimi, l'esistenza di cammini con vincoli sul colore degli archi.
  24. 19/01/01 (2h). Esercizi: implementazioni di semianelli, estensioni del tipo di dato set con complemento e/o intervallo.
  25. 23/01/01 (1h). Tipo di dato set ereditario: definizione induttiva del modello canonico e della implementazione.
  26. 24/01/01 (2h). Programmazione dinamica: DAG delle chiamate ricorsive, confronto con divide-et-impera, complessita' spazio e complessita' tempo. Esempi di algoritmi che usano la tecnica della programmazione dinamica: numeri di fibonacci, moltiplicazione ottimale di matrici (inclusa risoluzione bottom-up).
  27. 26/01/01 (2h). Esempi di programmazione dinamica: coefficenti binomiali, problema dello zaino.
  28. 06/03/01 (2h). Esercizi: algoritmi su grafi rappresentati con lista di liste di adiacenza (e con informazione ausiliaria associata ai nodi); calcolo della chiusura transitiva di una matrice sparsa (quasi ovunque nulla) rappresentata con una lista di terne.
  29. 08/03/01 (1h). Esercizi: rappresentazione di fogli elettronici, approccio lazy al calcolo del valore delle celle usando visita di un grafo e topological sorting.
  30. 09/03/01 (2h). Esercizi: fogli elettronici approccio eager al calcolo del valore delle celle. Problemi di decisione e linguaggi. Macchine di Turing (TM) ad un nastro ed automa associato: configurazioni istantanee, relazione di transizione.
  31. 13/03/01 (2h). Linguaggi decidibili e semidecidibili, le classi R e RE, la tesi di Church (invarianza di R ed RE al variare del modello di calcolo). 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, inclusione di TIME_m(f) in TIME_1(O(f^2)). La classe P dei problemi trattabili.

    15/03/01 lezione sospesa per seminario

  32. 16/03/01 (2h). COMPITINO
  33. 20/03/01 (2h). Le classi di complessita' spazio SPACE_m(f) e SPACE(f) e TM con nastro read-only. 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). Le classi L e PSPACE. Il teorema di tape-compression e linear speed-up: rappresentazione di m caratteri con un carattere, simulazione di m passi con pochi passi.
  34. 22/03/01 (1h). Il modello di calcolo delle RAM, e relative classi di complessita'. Confronto con le TM.
  35. 23/03/01 (2h). Simulazione di una TM mediante RAM in O(f). Simulazione di una RAM mediante una TM con la tecnica del log file. Esercizi: TM per addizione, TM per fetch da log file.
  36. 27/03/01 (2h). Costo polinomiale della simulazione di una RAM mediante una TM con la tecnica del log file, e assenza della moltiplicazione dalle operazioni aritmentiche di base. La tesi di Church (estesa). Il modello di calcolo delle TM non-deterministiche: criterio di accettazione di un linguaggio, valutazione della complessita' tempo e spazio. Le classi di complessita' non deterministiche. Simulazione di una TM non-deterministica mediante una TM deterministica mediante visita dell'albero delle possibili computazioni.
  37. 29/03/01 (1h). Esempi di descrizioni di TM: addizione, fetch da logfile.
  38. 30/03/01 (2h). Codifica di TM canoniche, e funzione universale. TM universale e variante per traduttori. I problemi H (halting problem) e K, semidecidibilita' di H e K. 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'.

    03/04/01 sospensione per ETAPS

    05/04/01 sospensione per ETAPS

    06/04/01 sospensione per ETAPS

  39. 10/04/01 (2h). Non decidibilita' di H (tecnica della diagonalizzazione). Non decidibilita' delle proprieta' estensionali dei programmi (Teorema di Rice). Teorema S-m-n e definizione implicita di codifiche di TM. Proprieta' di chiusura di R (quantificazione limitata), caratterizzazione di R in termini di RE. Proprieta' di chiusura di RE (quantificazione illimitata), caratterizzazione di RE in termini di R (predicato di Kleene).
  40. 20/04/01 (2h). Caratterizzazione di R ed RE in termini di enumerazioni. Esempi di problemi non semidecidibili: complementari di H e K, TOT, EQ. Esercizi: tecniche per stabilire o refutare decidibilta' o semidecidibilita' di linguaggi.
  41. 24/04/01 (2h). Esercizi: tecniche per stabilire o refutare decidibilta' o semidecidibilita' di linguaggi. Classi di complessita' tempo-spazio e deterministiche e non: risultati di inclusione. Inclusione di NSPACE in TIME (metodo della reachability).
  42. 27/04/01 (2h). Inclusione di NSPACE in SPACE (teorema di Savitch). Relazioni di inclusione tra classi naturali. Proprieta' di chiusura delle classi naturali rispetto ad operazioni insiemistiche e quantificazione limitata.
  43. 02/05/01 (1h). Chiusura delle classi naturali rispetto alla riduzione poly-time e/o log-space. Problemi completi, varianti dell'halting problem e problemi completi per P, NP e PSPACE.
  44. 04/05/01 (2h). Teoremi di gerarchia spazio e tempo. Inclusioni strette tra classi naturali di complessita'. Caratterizzazione di NP in termini di P.
  45. 08/05/01 (2h). I problemi CVP e SAT. P-completezza di CVP e metodo della tabella.
  46. 09/05/01 (1h). NP-completezza di SAT.
  47. 11/05/01 (2h). NL-completezza di Reachability e PSPACE-completezza di QBF (senza dimostrazione). Varianti di CVP e SAT: riduzione di SAT a Circuit SAT e 3-SAT, algoritmo polinomiali per 2-SAT (NL-completo) ed HORN-SAT (P-completo).
  48. 15/05/01 (2h). Riduzione di CVP a MONOTONE CVP (P-completo): introduzione di nodi duali. Esercizi: proprieta' di chiusura derivate per P e NP.
  49. 16/05/01 (1h). Riduzione di CVP a HORN-SAT (P-completo). Esercizi: proprieta' di chiusura derivate per P e NP, chiusura di NP rispetto alla chiusura transitiva.
  50. 18/05/01 (2h). Problemi P-completi su grafi: independent set, node cover, clique, 3-colorability, hamilton path, travelling salesman problem.
  51. 22/05/01 (2h). Problemi P-completi numerici: integer programming e knapsack. Esercizi.
  52. 23/05/01 (1h). Esercizi
  53. 25/05/01 (2h). Esercizi
  54. 29/05/01 (2h). Esercizi (P e chiusura per coding, Hamilton cycle), Accenni (algoritmi e classi di complessita' probabilistiche)

    FINE LEZIONI