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

Registro delle Lezioni

Le lezioni sono tenute da Moggi se non altrimenti specificato.
  1. 03/11/98 (Moggi). Introduzione al corso. Formalizzazione mediante automi (con transizioni pesate) delle nozioni di problema, algoritmo, correttezza parziale e totale, complessita', dimensione dell'input e stime di complessita'. Simulazione tra automi e raffinamento di algoritmi. Invarianti e correttezza parziale.
  2. 05/11/98 (Moggi). Esempi di algoritmi descritti mediante automi: selection-sort, bubble-sort. Esempi di dimostrazione di correttezza mediante invariante. Esempio di simulazione tra due automi per selection-sort.
  3. 10/11/98 (Moggi). La tecnica divide-et-impera. Schema generico in ML e pseudo-Pascal. Schema specifico quando il numero di sotto-problemi non varia. Esempi di algoritmi divide-et-impera: selection-sort, merge-sort, torre di Hanoi, moltiplicazione tra grandi numeri. Esempio di algoritmo dividi-et-impera con numero di sotto-problemi variabili: moltiplicazione ottimale di n matrici rettangolari.
  4. 12/11/98 (Moggi). Criteri sufficienti per dimostrare terminazione e correttezza parziale di un algoritmo ricorsivo divide-et-impera. La funzione complessita' esatta di un algoritmo divide-et-impera definita in funzione del costo esatto di decomposizione e composizione. Criteri sufficienti per maggiorare la complessita' esatta di un algoritmo divide-et-impera.
  5. 17/11/98 (Moggi). Metodi per definire implicitamente una maggiorazione la complessita' esatta di un algoritmo divide-et-impera. Il Master Method ed significato intuitivo della casistica. Applicazioni del Master Method: esempi. Tipi di dato e segnature many sorted. Algebre parziali, modelli canonici e modelli implementativi.
  6. 19/11/98 (Moggi). Relazioni di simulazione e simulazione parziale tra algebre parziali, e correttezza (parziale) di una implementazione rispetto al modello canonico relativamente ad una relazione di simulazione. Estensione delle proprieta' delle simulazioni e simulazioni parziali alle interpretazione dei termini. Esempi di implementazioni e simulazioni per il tipo di dato set. Esercizio, il tipo di dato "insiemi ereditari".
  7. 24/11/98 (Catania). I dizionari: motivazione, segnatura, modello canonico, implementazioni di base, relazione di simulazione rispetto al modello canonico. Le tabelle hash a concatenazione e ad indirizzamento aperto: funzioni hash, struttura dati, implementazione delle operazioni, cenni alla complessita' delle operazioni.
  8. 26/11/98 (Catania). Esempio generale sulle tabelle hash ad indirizzamento aperto. Le code di priorita': motivazione, segnatura, modello canonico, limitazioni delle implementazioni di base. Implementazione ad albero: proprieta' dell'albero, implementazione delle operazioni, complessita'. Uso di heap per la rappresentazione dell'albero e relazione di simulazione rispetto al modello canonico. Introduzione ad Heapsort.
  9. 01/12/98 (Catania). Heapsort: relazione con selezione diretta, algoritmo, esempi, complessita'. Esercizio proposto: heapsort come simulazione selezione diretta. Introduzione a Quicksort: algoritmo, interpretazione algoritmo in base allo schema del divide et impera, schema generale prova di correttezza, terminazione dell'algoritmo.
  10. 03/12/98 (Catania). Quicksort: note aggiuntive sulla correttezza, complessita' caso peggiore, caso migliore, idea complessita' caso medio. Confronto Heapsort, Quicksort e metodi di ordinamento diretti. Astrazione degli algoritmi proposti ai tipi di dato astratti.
  11. 10/12/98 (Moggi). Grafi diretti (etichettati): definizioni generali, ed esempi. Rappresentazione di grafi: matrice di adiacenza e liste di adiacenza, altre rappresentazioni. Il problema del calcolo della distanza tra nodi. L'algoritmo di Dijkstra.
  12. 15/12/98 (Catania). Gli alberi di ricerca binari: definizione, operazioni, complessita' caso migliore e caso peggiore, idea complessita' caso medio. Ottimizzazione degli alberi di ricerca binari: motivazioni, giustificazione, definizione e complessita' di alberi 2-3 e alberi AVL.
  13. 17/12/98 (Moggi). Correttezza (invariante) dell'algoritmo di Dijkstra, analisi di complessita' per due possibili implementazioni: O(V^2) e O((E+V)*log V). (Da fare come ottenere i cammini minimi, da spiegare come implementare l'operazione di modifica della priorita' e/o cancellazione di un elemento in una coda di priorita').
  14. 22/12/98 (Catania). Concetti di base algoritmi per dati residenti su memoria di massa: unita' di misura della complessita', generalizzazione alberi di ricerca. I B-alberi: relazione con strutture dati viste in precedenza, definizione, operazioni, complessita' delle operazioni.
  15. 07/01/99 (Moggi). Algoritmo di Floyd per il calcolo delle distanze: correttezza e complessita'. Confronto con l'algoritmo di Dijkstra. Varianti degli algoritmi di Dijkstra e Floyd per ottenere anche i cammini di lunghezza minima (mantenendo complessita' tempo e dimensione dell'input invariata a meno di fattori costanti). Generalizzazione dell'algoritmo di Floyd al caso di archi con lunghezze anche negative.
  16. 12/01/99 (Moggi). Implementazione di operazione di cancellazione di un elemento da una coda di priorita' in tempo O(log n). Necessita' di mantenere informazione aggiuntiva per risalire in tempo constante da un elemento alla sua posizione nella coda di priorita'. Implementazione di insiemi ereditariamente finiti mediante liste ordinate. Ordine lessicigrafico sulle liste, versione semplice e versione ricorsiva. Corrispondenza grafi etichettati e matrici quadrate a valori in un semi-anello. Interpretazione delle matrici M^n e M^* in termini di cammini, esempi con varie scelte di semi-anello.
  17. 14/01/99 (Moggi). Variante dell'algoritmo di Floyd per il calcolo della chiusura transitiva di una matrice quadrata a coefficenti in un semi-anello COMPLETO A (non necessariamente idempotente), supponendo che di saper calcolare la chiusura riflessiva e transitiva a^* in A. Esempi di a^* per varie scelte di semi-anello completo. Schema generale per visite di grafi, usando un insieme di nodi esaminati e di nodi frontiera. DFS e BFS come istanze dello schema generale implementando la frontiera rispettivamente con una pila ed una coda. Indegree di un grafo, grafi aciclici per rappresentare ordini parziali, test di aciclicita' e topological sorting. Algoritmi in O(V+E) per indegree, test di aciclicita' e topological sorting.
  18. 19/01/99 (Moggi). Programmazione dinamica: DAG delle dipendenze, confronto con divide-et-impera, complessita' stazio e complessita' tempo. Esempi di algoritmi che usano la tecnica della programmazione dinamica: numeri di fibonacci, coefficenti binomiali, il problema dello zaino. Risoluzione bottom-up e riduzione della complessita' spazio.
  19. 21/01/99 (Moggi). Ricerca di una soluzione ammissibile mediante enumerazione delle soluzioni possibili. Ricerca di una/tutte le soluzioni ammissibili mediante visita di un albero con tecniche di pruning: criterio di espansione della frontiera, criteri di terminazione della visita. Ricerca di una soluzione ottima mediante visita di un albero con tecniche di branch-and-bound: criterio di espansione della frontiera, criterio di terminazione della visita.
  20. 26/01/99 (Moggi). Esercizi.
  21. 28/01/99 (Moggi). Esercizi.

    INIZIO SECONDA PARTE: CALCOLABILITA' e COMPLESSITA'

  22. 08/03/99 (Moggi). Il modello di calcolo delle Macchine di Turing (TM): configurazioni istantanee, relazione di transizione, automo con stato associato ad una TM. Linguaggio, codifica di problemi di decisione in linguaggi, funzione caratteristica e semicaratteristica, linguaggi decidibili e semidecidibili, Le classi di complessita' TIME(f).
  23. 08/03/99 (Moggi, 3 ore). TM a piu' nastri. Proprieta' di elementari delle classi di complessita' TIME(f) dimostrate usando la tecnica della simulazione: riduzione ad un nastro, speed-up lineare. TM con nastro di input read-only (e nastro di output write-only) e le classi di complessita' SPACE(f). Proprieta' di elementari delle classi di complessita' SPACE(f) dimostrate usando la tecnica della simulazione: riduzione ad un nastro, compressione del nastro. Le classi naturali P (polytime) ed L (logspace).
  24. 15/03/99 (Moggi). Il modello di calcolo delle RAM. Confronto con le TM. Simulazione di una TM mediante RAM in O(f). Tecnica del log file.
  25. 18/03/99 (Moggi). Simulazione di una RAM mediante TM in O(f^3). Tesi di Curch estesa. Impossibilita' di simulazione polinomiale per RAM con operazione di moltiplicazione. Esempi di TM: contatore, addizionatore, operazione di fetch da log file.

    il 22 e 25 Marzo non vi sono lezioni, poiche' il docente e' in missione

  26. 29/03/99 (Moggi). il modello di calcolo delle TM non-deterministiche: criterio di accettazione, classi di complessita' tempo e spazio, lemmi di speed-up lineare e compressione, la classe NP, esempi di algoritmi non deterministici. Simulazione di una NDTM mediante una TM in O(c^f), visita BFS dell'albero delle computazioni. Codifica di TM canoniche, e funzione universale.
  27. 08/04/99 (Moggi). TM universale e variante per traduttori. I problemi H (halting problem) e K, semidecidibilita' di H e K, non decidibilita' di H e K (tecnica della diagonalizzazione). 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'. Proprieta' di chiusura di R, caratterizzazione di R in termini di RE, non semidecidibilita' del complementare di K.
  28. 12/04/99 (Moggi). Esempi di riduzione per dimostrare non decidibilita' ne' semidecidibilita' (TOT, EQ). Predicati/funzioni m-arie calcolati da una TM, variante m-aria della funzione universale. Teorema S-m-n, predicato di Kleene. Proprieta' estensionali dei programmi e teorema di Rice. Accenni al programma di Hilbert e al teorema di incompletezza di Goedel.
  29. 15/04/99 (Moggi). Proprieta' di chiusura di RE, caratterizzazione di RE in termini di R tramite il predicato di Kleene. Caratterizzazioni alternative di R ed RE in termini di enumerazioni.
  30. 19/04/99 (Moggi). Esercizi su tecniche per stabilire decidibilita' e/o semidecidibilita' di linguaggi/problemi.
  31. 22/04/99 (Moggi). Esercizi su tecniche per stabilire decidibilita' e/o semidecidibilita' di linguaggi/problemi.
  32. 26/04/99 (Moggi). Accenni alla struttura di R ed RE rispetto alla riducibilita'. Classi di complessita' naturali, relazioni di inclusioni non strette tra classi di complessita'.
  33. 29/04/99 (Moggi). Teoremi di gerarchia per TIME e SPACE. Inclusioni strette tra classi naturali.
  34. 03/05/99 (Moggi). Riducibilita' poly-time e log-space. Proprieta' transitiva della riducibilita'. Chiusura delle classi naturali per riducibilita'. Esistenza di problemi completi (varianti dell'Halting problem). [Non esistenza di problemi R-completi per riducibilita' poly-time].
  35. 06/05/99 (Moggi). Chiusura delle classi di complessita' naturali per operazioni insiemistiche e per quantificazione esistenziale limitata. Caratterizzazione di NP in termini di P. Appartenenza di SAT ad NP, sfruttando la caratterizzazione di NP in termini di P.
  36. 10/05/99 (Moggi). NP-completezza di SAT rispetto a riduzioni log-space (metodo della tabella). P-completezza di CVP (circuit value problem) rispetto a riduzioni log-space. NL-completezza di REACHABILITY (solo enunciato).
  37. 13/05/99 (Moggi). Varianti di SAT complete per classi naturali: QFB PSPACE-completa, 3-SAT NP-completa, HORNSAT P-completa, 2-SAT NL-completa. Esempi di problemi NP-completi: CIRCUIT SAT; CLIQUE, NODE COVER, INDEPENDENT SET, HAMILTON PATH, 3-COLORABILITY; KNAPSACK, INTEGER PROGRAMMING.
  38. 17/05/99 (Moggi). Algoritmi probabilistici: test A*B=C per matrici quadrate, test di primalita', test di nullita' per espressioni simboliche. RTM (Monte-Carlo e Las Vegas), le classe RP e ZPP, riduzione della probabilita' di errore e powering lemma.
  39. 20/05/99 (Moggi). Algoritmi paralleli: moltiplicazione di matrici, somme dei prefissi, REACHABILITY (chiusura riflessiva e transitiva di una matrice booleana). La nozione di tempo parallelo e lavoro. Il modello di calcolo delle famiglie uniformi di circuiti booleani. Le classi di complessita' parallele NC_j, relazione con le altre classi di complessita', e chiusura per riduzione log-space. Il problema del costo di comunicazione, accenno al modello BSP.
  40. 24/05/99 (Moggi). Esercizi su Complessita' Computazionale: chiusura di NP e P rispetto alla Kleene's star; NP e' diverso da SPACE(n) [dimostrando che SPACE(n) non e' chiuso per quantificazione esistenziale poly-bound, facendo uso del teorema di gerarchia spazio]; P-completezza di MONOTONE CVP.
  41. 27/05/99 (Moggi). Esercizi su Complessita' Computazionale.