Source: http://homes.dsi.unimi.it/~torelli/argomenti03.html
Timestamp: 2017-09-20 21:58:00+00:00

Document:
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/)
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).
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).
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).
Aggiornato il 4/2/2004.

References: §1
 §1
 §2
 §2
 §2
 §3
 §7
 §7
 §3
 §3
 §7
 §1
 §1
 §33
 §1
 §1
 §1
 §1
 §1
 § 2
 §2
 § 2
 §5
 §6
 §2
 §2
 §4
 §4
 §3
 §4
 §8
 §8
 §8
 § 8
 §9
 §9
 §9
 §9
 §10
 §31
 §10
 §10
 §10
 §11
 §11
 §11
 §2
 §2
 §11
 §12
 §12
 §12
 §6
 §12
 §12
 §12
 § 13
 § 13
 § 13
 § 14
 §19
 §23
 § 22
 § 22
 §22
 § 22
 § 22
 §16
 §16
 §17
 §17
 §17
 §17
 §24
 §3
 §18
 §37