Corso di Algoritmi e strutture dati   Edizione 2/serale

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

 

Le indicazioni dei paragrafi si riferiscono al libro di testo (T.H. Cormen, C.E. Leiserson, R.L. Rivest, C. Stein, Introduzione agli algoritmi e strutture dati, McGraw-Hill, II edizione 2005), altre indicazioni agli appunti disponibili alla pagina http://homes.dsi.unimi.it/~torelli/note2e.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.

 

3 ottobre:       Informazioni generali sul corso.      

La compressione di testi e l'algoritmo di Huffman (testo §16.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).

 

4 ottobre:       Ancora generalità sul corso.

                      Riepilogo sui codici.

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

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

                     

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

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

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

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

                  

10 ottobre:     Nozioni di base sui grafi. Un albero libero è un grafo connesso aciclico (appunti: "Grafi e alberi" §2.1, testo §§B.4 e B.5.1).

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

                      Alberi radicati e linguaggi ereditari (appunti: "Grafi e alberi" §§2.2).

 

11 ottobre:     Alberi binari, k-ari e ordinati (appunti: "Grafi e alberi" §§2.2 e 2.3, testo §§B.5.2 e B.5.3).

                      Alberi binari completi e completi a sinistra. La struttura dati heap (testo §6.1).

 

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

                      Mantenimento delle proprietà di uno heap (Heapify: testo §6.2).

                      Costruzione efficiente di uno heap (testo §6.3).

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

 

17 ottobre:     Riepilogo sugli heap. Cenno all’analisi ammortizzata e suo uso nella dimostrazione della linearità della costruzione degli heap (appunti "Gli heap" §3.4).

                      Heapsort (testo §6.4).

                     

18 ottobre:     Code a priorità come strutture di dati astratte (dati + operazioni) e realizzazione con heap (testo §6.5).

                      L’uso di uno heap consente di realizzare in modo efficiente l’algoritmo di Huffman (testo §16.3).

                      Origine del termine “algoritmo” (si veda eventualmente il riferimento Knuth [182] citato nelle note al termine del capitolo 2 del testo) e caratteristiche fondamentali degli algoritmi (testo §1.1, dispense Bertoni-Goldwurm §1.1). Cenno agli algoritmi probabilistici (testo §31.8). Problemi di ordinamento (testo §1.1).

 

21 ottobre:     Ordinamento per inserimento, ordinamento in loco (sul posto), pseudocodice (testo §2.1). 

                      Sintesi, analisi e classificazione di algoritmi (dispense §§1.1-1.3).

                      Cenno alle classi P e NP e ai problemi NP-completi (testo pagine 8-9 e capitolo 34).

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

Microanalisi di insertion sort: caso migliore, peggiore e medio.

 

24 ottobre:     Somma di Gauss (la somma dei primi n numeri interi positivi: appunti note informali.pdf e testo appendice A, passim).

                      Ricerca lineare (o sequenziale) (testo esercizio 2.1-3) e binaria (o dicotomica) (testo esercizio 2.3-5).

                      Tecniche di progetto: approccio incrementale e dìvide-et-ìmpera. Mergesort (testo §2.3).

                     

25 ottobre:     Complessità di MergeSort. Introduzione alle relazioni di ricorrenza (testo §2.3).

                      Introduzione alle notazioni asintotiche, in particolare O (testo §3.1).

 

28 ottobre:     Notazioni asintotiche. Le notazioni O( ) e o( ): le altre notazioni (da conoscere e usare: Θ e Ω) si possono esprimere in funzione di queste (testo § 3.1).

                      Funzioni monotòne. Floor e ceiling (testo § 3.2).

 

31 ottobre:     Richiami sulle notazioni che useremo; crescita polinomiale, esponenziale, (poli)logaritmica (testo §3.2, si può saltare il logaritmo iterato lg*, NON il logaritmo in generale! Attenzione alla relazione 3.15).

                      Fattoriali e binomiali (testo §C.1); formula di Stirling e calcolo di lg(n!) (testo §3.2).

                      Il classico (1202!) problema dei conigli (testo latino – con traduzione – al sito http://utenti.quipo.it/base5/fibonacci/fibonacci.htm, gentilmente segnalato da uno studente).

                     

2 novembre:   Sistemi di riscrittura D0L per il problema dei conigli (si veda per esempio http://www.biologie.uni-hamburg.de/b-online/e28_3/lsys.html).

I numeri di Fibonacci, vari metodi di calcolo e la formula di Eulero-Binet (vedi appunti La formula di Eulero-Binet e testo §3.2 e problemi 4-5 e 31-3).

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

 

7 novembre:   Iterazione e ricorsione. Definizioni e calcoli ricorsivi (cfr. dispense §§5.1 e 5.2).

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

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

                     

8 novembre:   Il teorema “dell’esperto” (o teorema principale: testo §4.3).

                      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.

 

11 novembre: Quicksort: la procedura di partizionamento (testo §7.1).

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

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

 

14 novembre: Uso di insertion sort al termine di quicksort (esercizio 7.4-5 del testo).

                      Quicksort randomizzato (testo § 7.3).

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

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

 

15 novembre: Il modello ad albero di decisione e il limite inferiore per gli ordinamenti (testo §8.1). Counting sort (testo §8.2).

                      Radix sort (testo §8.3). Considerazioni storiche sulle schede perforate e le prestazioni degli elaboratori.

                      Bucket sort (testo §8.4).

 

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

                      L’algoritmo di Strassen (testo §28.2 – solo la presentazione e le conclusioni e dispense Bertoni-Goldwurm §10.5).

                      Selezione con tempo medio lineare (testo §9.2).

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

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

                     

21 novembre: Introduzione alle strutture di dati (testo pagg. 165-167).

                      Pile (testo §10.1).

                      Code e deque (testo §10.1 ed esercizio 10.1-5).

                      Liste concatenate, con e senza sentinelle (testo §10.2).

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

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

 

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

Rappresentazioni di alberi radicati (testo §10.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)

 

25 novembre: Tabelle hash. Indirizzamento diretto (testo §11.1).

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

                      Nota: si può saltare la dimostrazione del teorema 11.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 §11.3: non è richiesta la procedura descritta nella figura 11.4, si rifletta piuttosto su quante cifre decimali deve avere la costante A. Solo un cenno all'hash universale: l’inizio del §11.3.3).

 

28 novembre: Indirizzamento aperto (testo §11.4). 

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

                      Scansione lineare, quadratica e hash doppio (testo §11.4 e problema 11-3).

                     

29 novembre: Analisi dell'hash a indirizzamento aperto (teoremi 11.6 e 11.8 del testo).

Algoritmi di visita degli alberi (senza dimenticare la visita per livelli: testo §12.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 §12.1).

 

2 dicembre:    Operazioni sugli alberi binari di ricerca (inclusa la cancellazione: §12.2 e 12.3).

Alberi di ricerca casuali: solo l’inizio del §12.4 e l'enunciato del teorema 12.4; fare l’esercizio 12.4-3.

Alberi lessicografici o radix tree (problema 12-2).

 

5 dicembre:    Conteggio degli alberi e linguaggio di Dyck: il problema 12-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).

                          

6 dicembre:    Ricerche nella memoria secondaria: §18.1.

                      I B-alberi e le operazioni su di essi (testo §§18.2 e 18.3. Saltare §18.4. Perché nella figura 18.7(d) si spezza la radice?).

 

12 dicembre:  Gli alberi rosso-neri come realizzazione efficiente di B-alberi con t = 2 (alberi 2-3-4, cfr. Sedgewick [269]) e come estensioni degli alberi di ricerca (introduzione cap. 14 + §13.1 del testo; si vedano le note Alberi rosso-neri).

 

13 dicembre:  Operazioni sugli alberi rosso-neri (§§13.2 e 13.3 del testo: le cancellazioni (§13.4) si possono saltare; si deve invece sapere quando basta una rotazione e quando ne occorrono due).

 

16 dicembre:  Tecniche avanzate di progetto e analisi: introduzione alla parte IV del testo.

Problemi di ottimizzazione e programmazione dinamica. Il problema delle catene di montaggio (§15.1).

Il problema del prodotto di matrici e il numero di parentesizzazioni (§15.2).

 

19 dicembre:  Sottostruttura ottima oppure no? L’esempio dei cammini minimi o massimi e la tecnica dell’annotazione o memorizzazione (testo §15.3 – saltare i dettagli dei conti e dei programmi. Saltare i §§15.4 e 15.5).

                      Algoritmi golosi: il problema della selezione di attività (testo §16.1): per ordinare i tempi di fine, come stabilire se conviene usare counting sort?

 

20 dicembre:  I problemi dello zaino: quando funzionano i golosi e quando no? 16.2. Ricordiamo che l’algoritmo di Huffman – §16.3 – è stato visto nelle prime lezioni del corso).

                      I matroidi forniscono una risposta globale (testo §16.4, si vedano gli appunti Problemi su insiemi, matroidi e algoritmi golosi).

 

9 gennaio ’06: Riepilogo sugli algoritmi golosi e i matroidi.

                      Matroidi grafici e matriciali. Il teorema di Rado (o di Borůvka: teorema 16.11 del testo. Per la dimostrazione meglio gli appunti Problemi su insiemi, matroidi e algoritmi golosi e le dispense Bertoni-Goldwurm).

 

10 gennaio:     L’esempio della programmazione di lavori con scadenze e penalità (testo § 16.5).

                      Introduzione all’analisi ammortizzata (testo capitolo 17. Si può saltare il metodo del potenziale).

 

13 gennaio:     Il metodo dell’aggregazione per l’analisi ammortizzata (testo §17.1) e quello degli accantonamenti (§17.2).

                      L’esempio della pila con MULTIPOP (l’esempio del contatore binario è sostanzialmente già stato visto nelle note sugli heap, §§3.3 e 3.4).

                      Tabelle dinamiche (solo l’espansione, testo §17.4. In particolare il metodo degli accantonamenti ci consente di determinare facilmente i costi anche per espansioni diverse: qual è il costo ammortizzato triplicando la tabella quando è piena?)

                     

16 gennaio:     Rappresentazioni dei grafi (testo §22.1 ed esercizio 22.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 §21.1).

                      Uso delle foreste per rappresentare insiemi disgiunti (testo §21.3. Solo cenni al §21.2).

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

 

17 gennaio:     Le funzioni ricorsive, la funzione di Ackermann e la sua inversa (testo § 21.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 o le voci rilevanti nell’enciclopedia online http://en.wikipedia.org).

                      Visita di grafi in ampiezza e in profondità e ordinamento topologico (solo i concetti principali dei §§ 22.2 (saltare dal lemma 22.1 a fine §), 22.3 (guardare la “classificazione degli archi”) e 22.4. Per tutti gli algoritmi sui grafi fare riferimento agli appunti Una guida alla visita di grafi e vedere gli esempi nelle figure del testo. Gli algoritmi sui grafi possono essere utili in particolare per il progetto di Laboratorio: nelle pagine del sito http://www.algoteam.dsi.unimi.it/ vi sono ulteriori esempi dettagliati e anche molti programmi in C.

 

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

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

                     

23 gennaio:     Cenni ai problemi P, NP e NP-completi (§34.1 del testo).

                      Due esempi: il problema della cricca e quello della copertura di vertici (§§34.6.1 e 34.6.2 del testo)

                     

24 gennaio:     Algoritmi approssimati: rapporto di approssimazione (testo pagina 873).

                      Coperture approssimate di vertici (testo §35.1).  

                      Risoluzioni approssimate dei problemi del commesso viaggiatore e della copertura di un insieme (§§35.2 e 35.3, solo i risultati).

 

 

 

 

 

 

 

Aggiornato il 6/2/2006 e 2/10/2009.