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.