Corso di Algoritmi e strutture dati   Turno 2/serale

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

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.

g 30 settembre: Informazioni generali sul corso.

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

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

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

v 1 ottobre: Ancora generalità sul corso.

Riepilogo sui codici.

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

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

m 5 ottobre: Riepilogo sulla costruzione dell’albero di Huffman.

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

Somma di Gauss (la somma dei primi n numeri interi positivi: appunti note informali.pdf e testo capitolo 3, passim).

Complessità dell’algoritmo di Huffman (§17.3).

Dimostrazione della correttezza dell’algoritmo di Huffman (appunti: "Codici e linguaggi" §1.4).

g 7 ottobre: 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/).

Sintesi, analisi e classificazione di algoritmi (dispense §1.1) Problemi di ordinamento; insertion sort (testo §1.1).

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

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

Analisi di algoritmi: modelli RAM e RASP. Criteri di costo uniforme e logaritmico; calcolabilità. (dispense §§3.1 - 3.3, senza le operazioni).

Microanalisi di insertion sort: caso migliore, peggiore e medio. Ordini di grandezza (§1.2).

Leggere §1.4 e fare problema 1.1 (cfr. dispense §1.3).

m 12 ottobre: Tecniche di progetto: approccio incrementale e dìvide-et-ìmpera. 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).

Introduzione alle notazioni asintotiche.

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

v 15 ottobre: Funzioni monotòne. Base e tetto (testo §2.2).

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

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

m 19 ottobre: Iterazione e ricorsione. Definizioni e calcoli ricorsivi (cfr. dispense §§5.1 e 5.2).

Il classico (1202!) problema dei conigli.

Ricorrenze tipiche dell'approccio dìvide-et-ìmpera: il metodo di sostituzione (testo §4.1).

g 21 ottobre: Il metodo iterativo per risolvere le ricorrenze; l’albero di ricorsione (testo §4.2).

Richiami sulla serie geometrica (testo §3.1).

Il teorema principale (testo §4.3).

v 22 ottobre: Lezione non svolta a causa dello sciopero dei mezzi pubblici.

m 26 ottobre: Esempi d'uso del teorema principale (§4.3) e cenno alla sua dimostrazione tramite l'albero di ricorsione (testo §4.4, essenzialmente la figura 4.3).

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

g 28 ottobre: Risoluzione di una ricorrenza di tipo diverso dal dìvide-et-ìmpera: i numeri di Fibonacci e la formula di Eulero-Binet (vedi appunti la formula di Eulero-Binet.pdf).

Il calcolo efficiente delle potenze, con un cenno alle catene di addizioni (per approfondimenti Knuth, riferimento [122] nel testo, §4.6.3).

v 29 ottobre: Richiami sui linguaggi formali (appunti: "Codici e linguaggi" §1.3).

Nozioni di base sui grafi. Un albero libero è un grafo connesso aciclico (appunti: "Grafi e alberi" §2.1, testo §§5.4 e 5.5.1).

m 2 novembre: Grafi e alberi come linguaggi (appunti: "Grafi e alberi" §2.1).

Alberi radicati, binari, k-ari e ordinati (appunti: "Grafi e alberi" §§2.2 e 2.3, testo §§5.5.2 e 5.5.3).

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

Introduzione agli algoritmi di ordinamento e selezione. Statistiche d’ordine (introduzione alla parte II del testo).

La struttura dati heap (testo §7.1).

v 5 novembre: Mantenimento delle proprietà dello heap (Heapify: testo §7.2).

Costruzione di uno heap e heapsort (testo §§7.3 e 7.4).

m 9 novembre: Gli heap come linguaggi; altezza, numero di foglie, altezza dei nodi (appunti sugli heap §§3.1 e 3.2).

Dimostrazione che Buildheap richiede al più n – v(n) scambi (appunti sugli heap §3.3).

Code a priorità come strutture di dati astratte e realizzazione con heap (testo §7.5).

g 11 novembre: Cenno all’analisi ammortizzata e al suo uso nella dimostrazione della linearità della costruzione degli heap (appunti "Gli heap" §3.4).

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).

v 12 novembre: Uso di insertion sort al termine di quicksort (esercizio 8.4-4 del testo).

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).

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

Counting sort (testo §9.2).

g 18 novembre: Radix sort (testo §9.3).

Considerazioni storiche sulle schede perforate e le prestazioni degli elaboratori.

Bucket sort (testo §9.4).

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

v 19 novembre: Selezione con tempo medio lineare (testo §10.2).

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

Selezione usando gli heap: estrazione iterata del massimo o del minimo.

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

Pile (testo §11.1).

m 23 novembre: Code e deque (testo §11.1 ed esercizio 11.1-5).

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).

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

Rappresentazioni di alberi radicati (testo §11.4).

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)

v 26 novembre: Tabelle hash. Indirizzamento diretto (testo §12.1).

Hash per concatenazione: la complessità media è sempre Q(1 + a) (testo §12.2).

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

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).

m 30 novembre: Lezione non tenuta per concomitanza dello sciopero generale.

g 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).

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

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

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).

g 9 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.

Alberi lessicografici (problema 13-2).

v 10 dicembre Svolto l'esercizio 13.4-2 e 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 oltre alle note Grafi e alberi, §2.6).

Ricerche nella memoria secondaria: introduzione del capitolo 19.

m 14 dicembre I B-alberi e le operazioni su di essi (testo §§ 19.1 e 19.2. Saltare §19.3. Perché nella figura 19.7(d) si spezza la radice?).

g 16 dicembre Gli RB-alberi come realizzazione efficiente di B-alberi con t = 2 (alberi 2-3-4, cfr. Sedgewick [175]) e come estensioni degli alberi di ricerca (introduzione cap. 15 + § 14.1 del testo; si vedano le note “A proposito degli RB-alberi”).

v 17 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).

m 21 dicembre Tecniche evolute di progetto e analisi: introduzione alla parte IV del testo.

Problemi di ottimizzazione. Esempi: il problema del resto e il problema dello zaino (vedere alla fine del §17.2 e il problema 17-1 del testo).

Programmazione dinamica (introduzione capitolo 16). Il problema del prodotto di matrici e il numero di parentesizzazioni (§16.1).

m 11 gennaio 2005

Questionario di valutazione della didattica.

Il prodotto di matrici (testo §16.1) e l’algoritmo di Strassen (testo §31.2 – solo la presentazione e le conclusioni e dispense Bertoni-Goldwurm §10.5).

La ricorsione con 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).

g 13 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. Ricordiamo che l’algoritmo di Huffman – §17.3 – è stato visto nelle prime lezioni del corso. Il §17.5 si può saltare).

I matroidi: esempi e motivazioni (appunti Problemi su insiemi, matroidi e algoritmi ingordi e testo §17.4; per la dimostrazione del teorema 17.5 si possono vedere gli appunti citati, al §6).

v 14 gennaio Il teorema di Rado (o di Borůvka: teorema 17.10 del testo, ma meglio le dispense Bertoni-Goldwurm, teorema 12.2 e gli appunti sopra citati).

Analisi ammortizzata: il metodo degli aggregati e quello degli accantonamenti (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.

m 18 gennaio Tabelle dinamiche (testo §18.4, saltando da pag. 351 alla fine del capitolo).

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

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

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

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

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 ).

v 21 gennaio 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 agli appunti Una guida alla visita di grafi e vedere gli esempi nelle figure del testo.

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).

Questi ultimi algoritmi non saranno chiesti all’orale ma possono essere utili per il progetto di Laboratorio.

Aggiornato il 1/2/2005.