Corso di Algoritmi e strutture dati   Turno 2/serale

I principali argomenti svolti a lezione (a. a. 2003-2004)

Le indicazioni dei paragrafi si riferiscono al libro di testo ([2] Cormen et al.), altre indicazioni agli appunti disponibili alla pagina http://homes.dsi.unimi.it/~torelli/note.html o alle dispense di Bertoni e Goldwurm scaricabili dalla pagina http://homes.dsi.unimi.it/~goldwurm/algo/. Le indicazioni non possono essere sempre esaurienti e dettagliate e rimandare a riferimenti specifici, comunque i rimandi ad altri testi o siti sono in genere utili solo per approfondimenti (non indispensabili). Si raccomanda di leggere sempre (dovrebbe essere ovvio!) anche le introduzioni dei capitoli (senza numero di paragrafo) e le introduzioni alle diverse parti del testo, che costituiscono spesso una sorta di compendio (leggi “bigino”) assai utile.

30 settembre:       Informazioni generali sul corso.

                           Esempi introduttivi (potenze di 2, logaritmi e “somma di Gauss” sono indispensabili nella valutazione della complessità degli algoritmi).

                           La compressione di testi e l'algoritmo di Huffman (§17.3).

                           La legge di Zipf (http://linkage.rockefeller.edu/wli/zipf/)

                           Codici e in particolare codici prefissi (appunti: "Codici e linguaggi").

 

2 ottobre:            Ancora generalità sul corso e raccolta informazioni.

                           Alberi binari e alberi di Huffman (§5.5.3 e 17.3).

                           Il programma per il codice di Huffman (§17.3).

                           Code a priorità “astratte” (§7.5).

                          

3 ottobre:            Complessità e correttezza dell’algoritmo di Huffman (§17.3).

                           Introduzione ai linguaggi formali e alle operazioni su linguaggi (appunti: "Codici e linguaggi" §1.3).

                       

7 ottobre:            Nuova dimostrazione della correttezza dell’algoritmo di Huffman (appunti: "Codici e linguaggi" §1.4).

                           Grafi e alberi come linguaggi (vedi appunti omonimi).

                           Un albero libero è un grafo connesso aciclico (appunti: "Grafi e alberi" §2.1).

                                  

9 ottobre:            Alberi radicati e linguaggi ereditari (appunti: “Grafi e alberi” §2.2).

                           Alberi binari, k-ari e ordinati (appunti: "Grafi e alberi" §2.3).

                          

10 ottobre:          Code a priorità (§7.5) e loro realizzazione con heap (§7.1).

                           Alberi binari completi a sinistra e heap (appunti "Gli heap" §3.1 e testo §7.1).

                           Rappresentazione con array: dove sono padri e figli?

                           La procedura Heapify (testo §7.2).

 

14 ottobre:          Proprietà degli heap (altezza, numero di foglie,…) (appunti "Gli heap" §3.2).

                           Costruzione degli heap in tempo lineare (appunti "Gli heap" §3.3 e testo §7.3).

 

16 ottobre:          Riepilogo sugli heap. Heapsort (§ 7.4).

                           Origine del termine algoritmo (si veda nel testo la prefazione italiana ed eventualmente il riferimento Knuth [121]) e caratteristiche fondamentali degli algoritmi (testo §1.1, dispense Goldwurm §1.1).

                           Il problema della terminazione. Esempi: frazioni egizie (http://www.ics.uci.edu/~eppstein/numth/egypt/) e problema di Collatz (3x + 1) (http://www.cecm.sfu.ca/organics/papers/lagarias/).

 

17 ottobre:          Cenno agli algoritmi probabilistici (testo §33.8).

                           Ordinamento per inserimento, ordinamento in loco, pseudocodice (testo §1.1).

                                  

21 ottobre:          I modelli di macchine RAM e RASP (testo §1.2 e dispense Goldwurm cap. 3, senza il linguaggio di programmazione).

                           Analisi degli algoritmi, in particolare insertion sort: caso migliore, peggiore e medio (testo §1.2).

 

23 ottobre:          Tecniche di progetto degli algoritmi (testo §1.3).

                           Mergesort e sua analisi in spazio e tempo, versione ricorsiva e non ricorsiva (testo §1.3).

                           Ricerca binaria (o dicotomica) (testo esercizio 1.3-5).

 

28 ottobre:          Perché usare le notazioni asintotiche (testo §§1.4 e 2.1).

                           Le notazioni O( ) e o( ): le altre notazioni (da sapere e usare: Θ e Ω) si possono esprimere in funzione di queste (testo § 2.1).

                           Funzioni monotòne. Base e tetto (testo §2.2).

                           Richiami sulle notazioni che useremo (testo § 2.2, si può saltare il logaritmo iterato lg*, NON il logaritmo in generale!).

                          

30 ottobre:          Iterazione e ricorsione. Definizioni e calcoli ricorsivi. L’esempio del calcolo del numero delle parti in cui n rette dividono il piano (dispense Goldwurm §5.1).

Osservazioni sul calcolo di e: attenzione agli errori di approssimazione!

                           Fattoriali e binomiali (testo §6.1); formula di Stirling e calcolo di lg(n!) (testo §2.2).

Osservazioni sul tempo di calcolo del fattoriale (criterio di costo logaritmico).

 

31 ottobre:          Crescita polinomiale, esponenziale, (poli)logaritmica (testo §2.2).

                           Risoluzione di ricorrenze: il metodo di sostituzione (testo §4.1).

                           Introduzione alla parte II del testo: ordinamento e selezione, statistiche d’ordine (testo pagine129-131).

 

4 novembre:        Il metodo iterativo per risolvere le ricorrenze e l’albero di ricorsione (testo §4.2).

                           Richiami sulla serie geometrica (testo §3.1).

                           Il teorema principale (testo §4.3).

 

 6 novembre:       Cenno alla dimostrazione del teorema principale tramite l'albero di ricorsione (testo fig. 4.3).

Gli esercizi 4.4-2 e 4.4-3 del testo.

Introduzione a quicksort (testo capitolo 8).

 

7 novembre:        Quicksort: la procedura di partizionamento (testo §8.1).

                           Prestazioni di quicksort: caso migliore e peggiore (testo §8.2).

                           Considerazioni sul caso medio Q(n lg n) (testo §8.2).

 

11 novembre:      Quicksort randomizzato (testo § 8.3).

Generazione di numeri e permutazioni pseudo-casuali (generatore lineare congruente: vedere eventualmente Knuth, riferimento [122] nel testo, oppure, per esempio, http://www.math.utah.edu/~alfeld/Random/Random.html).

                           Profondità della pila e mediano fra tre elementi (testo, problemi 8-4 e 8-5).

 

13 novembre:      Il modello ad albero di decisione e il limite inferiore per gli ordinamenti (testo §9.1).

                           Counting sort (testo §9.2).

 

14 novembre:      Radix sort (testo §9.3).

Considerazioni storiche sulle schede perforate e le prestazioni degli elaboratori.

                           Bucket sort (testo §9.4).

 

18 novembre:      Statistiche d'ordine. Determinazione del minimo e del massimo e minimo simultaneamente (testo §10.1).

                           Prodotto di matrici e algoritmo di Strassen (testo §31.2, solo la presentazione e le conclusioni; si confrontino anche le dispense Bertoni-Goldwurm §10.5).

                           Selezione con tempo medio lineare (testo §10.2).

                           Selezione in tempo lineare nel caso peggiore (testo §10.3, solo il risultato).

 

20 novembre:      Introduzione alle strutture di dati (testo pagg. 185-187).

                           Pile, code e deque (testo §11.1 ed esercizio 11.1-5).

                          

21 novembre:      Liste concatenate, con e senza sentinelle (testo §11.2).

Liste auto-organizzate (si porta in testa l'elemento cercato).

Realizzazione di puntatori e oggetti con array (testo §11.3).

                                  

25 novembre:      Rappresentazione unaria di alberi ordinati: ogni albero ordinato può essere rappresentato come un albero binario (appunti: "Grafi e alberi" §2.4).

Rappresentazione di alberi mediante un'unica parola binaria (appunti: "Grafi e alberi" §2.5).

Rappresentazioni di alberi radicati (testo §11.4).

                                  

27 novembre:      Un esempio di rappresentazione "esotica" degli alberi: i numeri di Matula (si veda, per esempio, l'articolo accessibile dall'indirizzo http://www.math.ethz.ch/EMIS/journals/PIMB/067/3.html)

                           Tabelle hash. Indirizzamento diretto (testo §12.1).

                           Hash per concatenazione (testo §12.2).

 

28 novembre:      Riepilogo dell'hash con concatenazione: la complessità media è sempre Q(1 + alfa) (testo §12.2).

Nota: si può saltare la dimostrazione del teorema 12.2 (basta pensare che mediamente si percorre mezza lista, dunque di lunghezza alfa/2). Contrariamente a quel che dice il libro, conviene pensare alfa come una variabile che può crescere all'infinito (se continuo a inserire dati in una tabella di dimensione fissa...), e interpretare theta di 1 + alfa come: il tempo o è costante (theta di 1) o cresce come alfa.

                           Le collisioni cominciano presto: si veda il paradosso del compleanno (testo §6.6.1).

                           Funzioni hash (testo §12.3: non è richiesta la procedura descritta nella figura 2.4, si rifletta piuttosto su quante cifre decimali deve avere la costante A. Solo un cenno all'hash universale: pagina 216).

 

2 dicembre:         Indirizzamento aperto (testo §12.4).

Scansione lineare, quadratica e hash doppio (testo §12.4 e problema 12-4).

                           Analisi dell'hash a indirizzamento aperto (teorema 12.5 del testo).

 

4 dicembre          Analisi dell'hash a indirizzamento aperto (teoremi 12.6 e 12.7 del testo).

Algoritmi di visita degli alberi (senza dimenticare la visita per livelli: testo § 13.1).

Alberi binari di ricerca: un albero in cui ogni figlio sinistro è minore del padre e ogni figlio destro è maggiore NON è necessariamente di ricerca! (testo § 13.1).

 

5 dicembre          Operazioni sugli alberi binari di ricerca (inclusa la cancellazione: § 13.2 e 13.3).

Alberi di ricerca casuali: solo pag. 238 e l'enunciato del teorema 13.6.

Fatto l'esercizio 13.4-2 e, a grandi linee, risolto il problema 13-4 (sui numeri di Catalan si può consultare per esempio http://www.geometer.org/mathcircles/catalan.pdf oppure http://www.maths.usyd.edu.au:8000/u/kooc/catalan.html)

 

9 dicembre          Alberi lessicografici (problema 13-2).

Gli RB-alberi, anche come estensioni di strutture dati (introduzione cap. 15 + § 14.1 del testo; si vedano gli appunti “A proposito degli RB-alberi”).

 

11 dicembre        Operazioni sugli RB-alberi (§§14.2 e 14.3 del testo: le cancellazioni (§14.4) si possono saltare; si deve invece sapere quando basta una rotazione e quando ne occorrono due)

 

12 dicembre        I B-alberi e le operazioni su di essi (testo cap.19: introduzione, §§ 19.1 e19.2. Saltare §19.3. Perché nella figura 19.7(d) si spezza la radice?).

 

16 dicembre        Rappresentazioni dei grafi (testo §23.1 ed esercizio 23.1-6 = il problema della celebrità:  un link dallo Utah).

Operazioni su insiemi disgiunti. Applicazione alla determinazione delle componenti connesse di un grafo (testo § 22.1).

 

18 dicembre        Uso delle foreste per rappresentare insiemi disgiunti (testo § 22.3. Solo cenni al §22.2).

                           Unione per rango (cos’è il rango?) e compressione dei cammini (testo § 22.3).

 

19 dicembre        Le funzioni ricorsive, la funzione di Ackermann e la sua inversa (testo § 22.4, solo la prima sezione: saltare da "Proprietà dei ranghi" in poi. Per le funzioni ricorsive si può consultare il libro di G. Ausiello et al. http://www.dis.uniroma1.it/~ausiello/InfoTeoRMvo/main.pdf al paragrafo 6.5 oppure  http://vigna.dsi.unimi.it/InformaticaTeorica.pdf ).

 

8 gennaio 2004    Tecniche algoritmiche evolute (introduzione alla parte IV del testo).

                           Questionario di valutazione della didattica.

                           Esempio: il problema del resto (vedere anche il problema 17-1 sul testo).

                           Programmazione dinamica e problemi di ottimizzazione: il prodotto di matrici (testo §16.1).

 

9 gennaio             Quiz di autovalutazione: 30 domande sul corso (è il quiz disponibile online).

                           Domande e risposte. Approfondimenti sull'altezza degli RB-alberi (lezione di riepilogo: nessun argomento nuovo per tener conto dello sciopero dei mezzi pubblici).

 

13 gennaio           La tecnica della memorizzazione (testo §16.2 – saltare i dettagli dei conti e dei programmi. Saltare i §§16.3 e 16.4).

                           Algoritmi greedy: il problema della selezione di attività (testo §17.1).

 

15 gennaio           Dimostrazione della correttezza dell'algoritmo greedy per la selezione di attività (testo §17.1).

                           Strategia greedy o programmazione dinamica? I problemi dello zaino (testo §17.2).

                           I matroidi: esempi e motivazioni (testo §17.4; per la dimostrazione del teorema 17.5 si può vedere la breve nota Problemi su insiemi, matroidi e algoritmi ingordi).

 

16 gennaio           Il teorema di Rado (o di Borůvka: teorema 17.10 del testo, ma meglio le dispense di Goldwurm, teorema 12.2).

                           Visita di grafi in ampiezza e in profondità e ordinamento topologico (solo i concetti principali dei §§ 23.2 (saltare dal lemma 23.1 a fine §), 23.3 (saltare da "Proprietà della visita in profondità" a fine §) e 23.4 (saltare da pag. 467 a fine capitolo). Per tutti gli algoritmi sui grafi fare riferimento alla nota Una guida alla visita di grafi e vedere gli esempi nelle figure del testo.        

 

20 gennaio           Alberi ricoprenti minimi (testo cap. 24, introduzione).

                           Gli algoritmi di Kruskal e Prim (testo §24.2: si possono tralasciare i dettagli dei programmi). L'algoritmo di Dijkstra per la determinazione dei cammini minimi (figura 25.5 del testo).

 

22 gennaio           Analisi ammortizzata: il metodo degli aggregati e quello degli accantonamenti

(aula 200)            (si può saltare quello del potenziale) (testo §§18.1 e 18.2).

                           Esempi: pile con multipop e contatore, per quest'ultimo vedere il §3.4 degli appunti sugli heap.

                           Tabelle dinamiche (testo §18.4, saltando da pag. 351 alla fine).

 

23 gennaio           Cenni ai problemi P, NP e NP-completi (si veda l'introduzione al capitolo 36 del testo).

                           Algoritmi approssimati: rapporto limite (testo pagina 907).

                           Coperture approssimate di vertici (testo §37.1).

                           Cenni al problema del commesso viaggiatore e della copertura di un insieme (§§37.2 e 37.3, solo i risultati).

                           Commiato.

 

 

Aggiornato il 4/2/2004.