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
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ù n – v(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
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
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.