Algoritmi e Strutture Dati I Corso D

Programma di esame per l'anno accademico 1999/2000

[I libri di testo sono nelle pagine principali.]

Problemi, algoritmi e complessità

  1. Presentazione del corso e dei suoi prerequisiti. Analisi asintotica.
    1. Struttura e scopo, modalità di svolgimento delle lezioni, esercitazioni ed esami, pagine Web [Pagina Web].
    2. Prerequisiti matematici richiesti [Pagina Web].
    3. Crescita polinomiale ed esponenziale [LP, cap.1].
    4. Ordine di grandezza e comportamento asintotico. Notazione O, Omega e Teta [CLR, cap.2].
    5. Confronto asintotico tra funzioni [CLR, cap.2].
  2. Esercitazioni.
    1. Verifica dei prerequisiti.
    2. Ordini di grandezza, comportamento e confronto asintotico di funzioni.
  3. Formalizzazione di problemi, dati e algoritmi. Ordinamento e Insertion Sort.
    1. Cenni sulla rappresentazione dei dati elementari: bit, interi, puntatori, caratteri/stringhe (ASCII e Unicode), reali (IEEE 754) [Pagina Web].
    2. Formalizzazione di un problema mediante la notazione matematica. Esempio dell'ordinamento [CLR, cap.1].
    3. Formalizzazione dell'algoritmo di risoluzione mediante un linguaggio di programmazione. Pseudocodice adottato nel libro di testo [CLR, cap.1].
    4. Progettazione di un algoritmo e verifica della correttezza. Esempio dell'Insertion Sort [CLR, cap.1] [Animazione].
  4. Modello di calcolo RAM e analisi di complessità.
    1. Modello di computazione secondo von Neumann (Modello RAM = Random Access Machine). Operazioni elementari supportate e ipotesi di costo unitario [Pagina Web].
    2. Dimensione dei dati. Risorse computazionali. Complessità asintotica di un problema e di un algoritmo. Caso ottimo, caso medio e caso pessimo. Limite inferiore e superiore di complessità, complessità polinomiale e superpolinomiale [Lu, cap. 4 (solo le parti qui citate)].
    3. Analisi di complessità di un algoritmo al caso ottimo, medio e pessimo. Esempio dell'Insertion Sort [CLR, cap.1].
  5. Esercitazioni.
      Formalizzazione del problema, progetto dell'algoritmo risolutore, dimostrazione della correttezza e analisi della complessità al caso pessimo:
    1. Ricerca del massimo in un vettore.
    2. Ricerca sequenziale di un elemento in un vettore.
    3. Fusione di due sottovettori ordinati (merge).
  6. Algoritmi divide et impera (1). Ricerca binaria. MergeSort.
    1. Ricerca sequenziale e ricerca binaria in un vettore ordinato (``Scommettiamo che?'': esempio del vocabolario e dell'elenco telefonico) [Lu, cap.5 par.5.2.1] [Pagina Web].
    2. Schema generale di un algoritmo ricorsivo divide et impera e sua relazione con il principio di induzione [CLR, cap.1].
    3. Ordinamento con il MergeSort [CLR, cap.1] [Lu, cap.5 par.5.3.2] [Animazione].
  7. Algoritmi divide et impera (2). Moltiplicazione veloce. Coppia di punti più vicini.
    1. Moltiplicazione rapida di interi lunghi [Lu, cap.5 par.5.2.2] [Pagina Web].
    2. Un esempio impegnativo: ricerca della coppia di punti più vicini [CLR, cap.35 par.35.4].
  8. Esercitazioni.
      Progettazione di algoritmi divide et impera:
    1. Riformulazione del massimo in maniera ricorsiva.
    2. Trovare il primo e secondo elemento [Lu, cap.3].
    3. Generazione delle sequenze binarie in ordine lessicografico.
    4. Generazione di tutte le permutazioni di un insieme [Lu, cap.3].
  9. Equazioni di ricorrenza. Analisi degli algoritmi divide et impera con esempi.
    1. Equazioni di ricorrenza e connessione con gli algoritmi divide et impera con esempi:
      • MergeSort : T(n) = 2 T(n/2) +O(n);
      • coppia di punti più vicini: T(n) = 2 T(n/2) +O(n);
      • massimo e primo/secondo : T(n) = 2 T(n/2) +O(1);
      • ricerca binaria : T(n) = T(n/2) +O(1);
      • moltiplicazione rapida : T(n) = 3 T(n/2) +O(n);
      • Insertion Sort ricorsivo: T(n) = T(n-1) +O(n);
      • generazione delle sequenze binarie: T(n) = 2 T(n-1) +O(1);
      • generazione delle permutazioni : T(n) = n T(n-1) +O(n).
    2. Metodo principale e teorema principale [CLR, cap.4].
    3. Metodo di sostituzione (cenni) e iterativo [CLR, cap.4].
  10. Esercitazioni con la ricorsività e la risoluzione delle equazioni di ricorrenza.

Ordinamento e selezione

  1. Heap e HeapSort.
    1. Definizione di heap [CLR, cap.7 par 7.1].
    2. Mantenimento della proprietà di heap [CLR, cap.7 par 7.2].
    3. Costruzione di uno heap [CLR, cap.7 par 7.3].
    4. L'algoritmo HeapSort [CLR, cap.7 par 7.4].
    5. Cancellazione dallo heap (facoltativo) [Pagina Web].
  2. Esercitazioni.
    1. Animazione dei seguenti algoritmi [Animazione]:
    2. InsertionSort
    3. MergeSort
    4. HeapSort
  3. QuickSort.
    1. Animazione del QuickSort [Animazione].
    2. Descrizione del QuickSort [CLR, cap.8 par 8.1].
    3. Versione randomizzata del QuickSort [CLR, cap.8 par 8.3].
  4. Analisi di HeapSort e QuickSort.
    1. Prestazioni di HeapSort [CLR, cap.7 par 7.2--7.4].
    2. Prestazioni di QuickSort [CLR, cap.8 par 8.2].
    3. Prestazioni di QuickSort [CLR, cap.8 par 8.2].
    4. Analisi del caso medio QuickSort [Lu, cap.3 par 3.3].
  5. Limite inferiore all'ordinamento per confronti. Tecniche di base per i limiti inferiori.
    1. Limite inferiore all'ordinamento per confronti [CLR, cap.9 par 9.1].
    2. Tecniche di base per i limiti inferiori [Lu, cap.4 par 4.2].
  6. Mediano e k-esimo elemento. Counting Sort e Radix Sort. (Bucket Sort.)
    1. Selezione del mediano e del k-esimo elemento [CLR, cap.10 par 10.1-10.3].
    2. Animazione di Counting Sort e Radix Sort [Animazione].
    3. Descrizione e analisi di Counting Sort e Radix Sort [CLR, cap.9 par 9.2-9.3].
    4. Lettura consigliata di Bucket Sort [CLR, cap.9 par 9.4].
  7. Esercitazioni preparatorie alla prima verifica.
    1. Risoluzione di alcuni degli esercizi forniti nel materiale didattico [Pagina Web].
    2. Risoluzione di alcuni degli esercizi delle verifiche degli anni passati [Pagina Web].
  8. Esercitazioni preparatorie alla prima verifica.
    1. Risoluzione di alcuni degli esercizi forniti nel materiale didattico [Pagina Web].
    2. Risoluzione di alcuni degli esercizi delle verifiche degli anni passati [Pagina Web].

Strutture dati e algoritmi di ricerca

  1. Strutture informative di base: pile, code, liste e alberi radicati.
    1. Pile e code [CLR, cap.11 par 11.1].
    2. Liste concatenate e loro rappresentazione [CLR, cap.11 par 11.2].
    3. Alberi liberi, radicati e ordinati [CLR, cap.5 par 5.5].
    4. Rappresentazione di alberi [CLR, cap.11 par 11.4].
  2. Esercitazioni.
  3. Dizionari. Tabelle hash (1): liste concatenate.
    1. Il problema del dizionario [CLR, Parte III (introduzione)].
    2. Concetto di funzione hash con esempi [CLR, cap.12 par 12.3].
    3. Collisioni e loro gestione mediante liste concatenate [CLR, cap.12 par 12.2].
  4. Tabelle hash (2): indirizzamento aperto.
    1. Analisi della gestione mediante liste concatenate [CLR, cap.12 par 12.2] [Pagina Web].
    2. Indirizzamento aperto: scansione lineare, quadratica e doppio hash [CLR, cap.12 par 12.4 senza analisi].
  5. Esercitazioni
  6. Alberi binari di ricerca. Visite di alberi.
    1. Rappresentazione di alberi e loro visita [Lu, cap.6 par 6.2].
    2. Definizione di albero binario di ricerca con esempi [Lu, cap.5 par 5.2.1] [CLR, cap.13 par 13.1].
    3. Ricerca in un albero binario di ricerca e relazione con la ricerca binaria [Lu, cap.5 par 5.2.1] [CLR, cap.13 par 13.2].
    4. Inserzione e cancellazione in un albero binario di ricerca [CLR, cap.13 par 13.3].
  7. Alberi bilanciati (1): alberi AVL.
    1. Problema del ribilanciamento. Definizione di 1-bilanciamento e alberi AVL [Lu, cap.5 par 5.2.1] [Bi, cap.10 par 10.1].
    2. Altezza logaritmica degli AVL: alberi di Fibonacci [Lu, cap.5 par 5.1.2] [Bi, cap.10 par 10.1].
    3. Rotazioni (SS, DS, SD, DD) e inserimento in un AVL [Lu, cap.5 par 5.2.1] [Bi, cap.10 par 10.1].
  8. Esercitazioni.
  9. Alberi bilanciati (2): alberi 2-3 e B-alberi.
    1. B-Alberi e loro uso in memoria secondaria [CLR, cap.19 (introduzione)].
    2. Definizione di B-alberi [CLR, cap.19 par 19.1].
    3. Ricerca e inserimento in un B-albero [CLR, cap.19 par 19.2].
    4. Altezza logaritmica dei B-alberi [CLR, cap.19 par 19.1].
  10. Esercitazioni.
  11. Alberi digitali. Trie, Patricia e alberi dei suffissi.
    1. Note ausiliari alla lezione [PDF] [Postscript].
    2. Definizione di trie non compatti e compatti.
    3. Definizione di Patricia.
    4. Ricerca e inserimento.
    5. Suffix tree.
  12. Sospensione della didattica per elezioni (D.R. n. 01/319 del 21 febbraio 2000).
  13. Sospensione della didattica per elezioni (D.R. n. 01/319 del 21 febbraio 2000).
  14. Sospensione della didattica per vacanze.
  15. Sospensione della didattica per vacanze.
  16. Sospensione della didattica per visita CAMPUS.
  17. Ricerca testuale: algoritmo string matching di Karp-Rabin.
    1. Definizione del problema dello string matching [CLR, cap.34 (introduzione)].
    2. Algoritmo immediato per lo string matching [CLR, cap.34 par 34.1].
    3. Algoritmo di Karp-Rabin e sua relazione con le collisioni nelle funzioni hash [CLR, cap.34 par 34.2].

Algoritmi su grafi, tecniche ``greedy'' e di programmazione dinamica

  1. Grafi e visite in ampiezza (BFS) e profondità (DFS).
    1. Terminologia sui grafi [CLR, cap.5 par 5.4].
    2. Rappresentazione di grafi [CLR, cap.23 par 23.1].
    3. Visita in ampiezza (BFS) [CLR, cap.23 par 23.2].
    4. Visita in profondità (DFS) [CLR, cap.23 par 23.3].
  2. Esercitazioni.
  3. Greedy: Alberi di ricoprimento minimo.
    1. Costruzione di un albero di copertura minimo [CLR, cap.24 par 24.1].
    2. Algoritmi di Prim e Kruskal [CLR, cap.24 par 24.2].
  4. Esercitazioni.
  5. Programmazione dinamica. Sottosequenza più lunga e string matching con errori.
    1. Programmazione dinamica e ricorsione [CLR, cap.16 par 16.2].
    2. Sottosequenza comune più lunga e string matching approssimato [CLR, cap.16 par 16.3 e problema 16-3].
  6. Esercitazioni.

Intrattabilità e NP-completezza

  1. Nozione di NP-completezza.
    1. Problemi in P e NP [CLR, cap.36 par 36.1].
    2. Verifica in tempo polinomiale e certificati [CLR, cap.36 par 36.2].
    3. NP-completezza e riducibilità [CLR, cap.36 par 36.3].
  2. Esercitazioni

Approfondimenti facoltativi