Algoritmi e strutture dati T2/2008-2009
Indice
- 1 Docenti
- 2 Orari delle lezioni
- 3 Sito del Corso
- 4 Materiale didattico
- 5 Compilatori
- 6 Links utili
- 7 Diario del corso
- 7.1 29/09/2008 [LUN]
- 7.2 01/10/2008 [MER]
- 7.3 02/10/2008 [GIO][LAB]
- 7.4 03/10/2008 [VEN]
- 7.5 06/10/2008 [LUN]
- 7.6 08/10/2008 [MER]
- 7.7 09/10/2008 [GIO][LAB]
- 7.8 10/10/2008 [VEN]
- 7.9 13/10/2008 [LUN]
- 7.10 15/10/2008 [MER]
- 7.11 17/10/2008 [VEN]
- 7.12 20/10/2008 [LUN]
- 7.13 22/10/2008 [MER]
- 7.14 23/10/2008 [GIO][LAB]
- 7.15 24/10/2008 [VEN]
- 7.16 27/10/2008 [LUN]
- 7.17 29/10/2008 [MER]
- 7.18 31/10/2008 [VEN]
- 7.19 03/11/2008 [LUN]
- 7.20 05/11/2008 [MER]
- 7.21 06/11/2008 [GIO][LAB]
- 7.22 07/11/2008 [VEN]
- 7.23 10/11/2008 [LUN]
- 7.24 12/11/2008 [MER]
- 7.25 14/11/2008 [VEN]
- 7.26 17/11/2008 [LUN]
- 7.27 19/11/2008 [MER]
- 7.28 20/11/2008 [GIO][LAB]
- 7.29 21/11/2008 [VEN]
- 7.30 24/11/2008 [LUN]
- 7.31 26/11/2008 [MER]
- 7.32 28/11/2008 [VEN]
- 7.33 01/12/2008 [LUN]
- 7.34 03/12/2008 [MER]
- 7.35 argomenti svolti
Docenti
Mauro Torelli e Stefano Aguzzoli
Orari delle lezioni
- Lun 18.30 - 20.30 - AULA 208
- Mer 20.00 - 21.30 - AULA 208
- Gio 18.30 - 21.30 - AULA 309 [LAB]
- Ven 18.30 - 20.00 - AULA 208
Sito del Corso
http://homes.dsi.unimi.it/~torelli/algoritmi.html
http://homes.dsi.unimi.it/~aguzzoli/algo.htm
Materiale didattico
"Introduzione agli algoritmi e strutture dati" Seconda edizione McGraw-Hill (Cormen, Leiserson, Rivest, Stein)
"C Didattica e programmazione" 4° edizione
"Il linguaggio C. Principi di programmazione e manuale di riferimento." 2° Edizione
Compilatori
Linux: GCC
Windows: MinGW - cs1300
Links utili
http://www.algoteam.dsi.unimi.it/
http://vc.dsi.unimi.it/ [VideoLezioni]
Diario del corso
29/09/2008 [LUN]
- Concetto di Algoritmo
- Counting Sort
01/10/2008 [MER]
- Performance dell'Algoritmo - Tempo
- Insertion Sort
02/10/2008 [GIO][LAB]
03/10/2008 [VEN]
- RAM (Random Access Machine)
- Divide et Impera
- Introduzione Merge Sort
06/10/2008 [LUN]
- Merge Sort
08/10/2008 [MER]
- Complessità di un algoritmo e di un problema
- Notazioni asintotiche (O, Ω, Θ, o piccolo)
09/10/2008 [GIO][LAB]
10/10/2008 [VEN]
- Notazioni asintotiche (O, Ω, Θ, o piccolo)
- Introduzione Grafi
13/10/2008 [LUN]
- Grafi ed Alberi
- Albero Binario Completo
- Albero Binario Quasi Completo
- Selection Sort
- Heap Sort - Gli Heap
- HeapSort
- Gli Alberi Heap
- Costruzione Heap
- Linguaggi, Codici Binari
15/10/2008 [MER]
- linguaggi e codici binari
17/10/2008 [VEN]
20/10/2008 [LUN]
- Heapsort
- catena di addizioni
- Quicksort
22/10/2008 [MER]
- sequenze pseudocasuali
- costo del quicksort
- algoritmi di ordinamento con le chiavi
- Counting Sort
- Radix Sort
23/10/2008 [GIO][LAB]
24/10/2008 [VEN]
- Bucket Sort
- Procedure ricorsive
- Statistiche d'ordine: minimo, massimo, mediano
- complessita delle statistiche d'ordine
27/10/2008 [LUN]
- Zenone
- I conigli di fibonacci
- calcolo di fibonacci con linguaggi e automi
29/10/2008 [MER]
- fibonacci in notazione matriciale
- Alberi AVL
- calcolo del minimo e del massimo
31/10/2008 [VEN]
- algoritmo di Strassen
- calcolo della complessita di un algoritmo
- metodo di sostituzione
- teorema principale
03/11/2008 [LUN]
- teorema pricipale
- metodo di sostituzione
05/11/2008 [MER]
- Introduzione a strutture di dati
- Stack
- Code
- Liste Concatenate
06/11/2008 [GIO][LAB]
07/11/2008 [VEN]
- Implementare puntatori e oggetti
- Rappresentazione di alberi con radice
- Teorema principale
- Alberi di matula
- Liste singolarmente linkate
10/11/2008 [LUN]
12/11/2008 [MER]
- Hashing
- Tabelle a indirizzamento diretto
- Tabelle Hash
- Funzioni Hash
- Il metodo della divisione
- Il metodo della moltiplicazione
14/11/2008 [VEN]
- lezione non svolta
17/11/2008 [LUN]
- Tavole Hash
- Funzione hash: metodo della divisione, moltiplicazione e hashing universale
- indirizzamento aperto: ispezione lineare, quadratica, doppio hashing
- Analisi dell'hashing ad indirizzamento aperto
19/11/2008 [MER]
- alberi binari di ricerca
- ricerca, massimo, minimo
- sucessore
- inserimento, cancellazione
20/11/2008 [GIO][LAB]
21/11/2008 [VEN]
- Alberi binari
- Alberi e linguaggi
24/11/2008 [LUN]
- B-alberi
- definizione di un b-albero
- altezza di un b-albero
- inserimento di una chiave (solo funzionamento)
- lucidi alberi 2-3-4
- introduzione alberi rosso-neri
26/11/2008 [MER]
- alberi 2-3-4
- alberi rosso-neri
- dimostrazione dell'altezza degli alberi rosso-neri
- rotazione e inserimento (solo funzionamento)
28/11/2008 [VEN]
- programmazione dimanica
01/12/2008 [LUN]
- algoritmi greedy
03/12/2008 [MER]
- algoritmi greedy
- codici di huffman
- Huffman e Linguaggi
argomenti svolti
- programmazione dinamica:
- algoritmi golosi
- analisi ammortizzata:metodo dell'aggregazione, degli accantonamenti, del potenziale
- algoritmi per grafi:
- rappresentazione dei grafi
- visita in ampiezza e profondita
- alberi di connesioni minimi
- algoritmi di Prim e Kruscal
- algoritmo di Dijkstra
- algoritmi di ordine P
- algoritmi di ordine NP e NP completi
- esempi di problemi NP completi: soddisfattibilità dei circuiti, soddisfattibilità delle formule, soddisfattibilità delle formule 3-CNF, problema della cricca, problema della copertura massima dei vertici, ciclo hamiltoniano, somma di sottoinsiemi e problema del commesso viaggiatore.(sapere che cosa risolvono questi problemi)
- algoritmi di approssimazione: introduzione, probelma della copertura di vertici, del commesso viaggiatoree della copertura di insiemi(non chiede questi algoritmi).
