Differenze tra le versioni di "Algoritmi e strutture dati T2/2008-2009"
(→03/12/2008 [MER]) |
|||
(53 versioni intermedie di 5 utenti non mostrate) | |||
Riga 37: | Riga 37: | ||
http://www.algoteam.dsi.unimi.it/ | http://www.algoteam.dsi.unimi.it/ | ||
− | http:// | + | http://vc.dsi.unimi.it/ [VideoLezioni] |
== Diario del corso == | == Diario del corso == | ||
Riga 48: | Riga 48: | ||
=== 01/10/2008 [MER] === | === 01/10/2008 [MER] === | ||
+ | *Performance dell'Algoritmo - Tempo | ||
*Insertion Sort | *Insertion Sort | ||
− | === 02/10/2008 [GIO] === | + | === 02/10/2008 [GIO][LAB] === |
+ | [http://homes.dsi.unimi.it/~aguzzoli/didattica/algo/l1.zip I Lezione] | ||
− | *Introduzione | + | === 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] === | ||
+ | [http://homes.dsi.unimi.it/~aguzzoli/didattica/algo/l2.zip II Lezione] | ||
+ | |||
+ | === 10/10/2008 [VEN] === | ||
+ | *Notazioni asintotiche (O, Ω, Θ, o piccolo) | ||
+ | *Introduzione Grafi | ||
+ | |||
+ | === 13/10/2008 [LUN] === | ||
+ | *[http://homes.dsi.unimi.it/~torelli/Grafi%20e%20alberi.pdf Grafi ed Alberi] | ||
+ | *[http://www.algoteam.dsi.unimi.it/pdf/AlberiBinariCompleti.pdf Albero Binario Completo] | ||
+ | *[http://www.algoteam.dsi.unimi.it/pdf/AlberiBinariQuasiCompleti.pdf Albero Binario Quasi Completo] | ||
+ | *[http://www.algoteam.dsi.unimi.it/pdf/SelectSort.pdf Selection Sort] | ||
+ | *Heap Sort - [http://homes.dsi.unimi.it/~torelli/Gli%20heap2e.pdf Gli Heap] | ||
+ | *[http://www.algoteam.dsi.unimi.it/pdf/HeapSort.pdf HeapSort] | ||
+ | *[http://www.algoteam.dsi.unimi.it/pdf/AlberiHeap.pdf Gli Alberi Heap] | ||
+ | *[http://www.algoteam.dsi.unimi.it/pdf/AlberiHeapOperazioneBuild.pdf 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] === | ||
+ | *[http://homes.dsi.unimi.it/~aguzzoli/didattica/algo/lucidi3.pdf III lezione] | ||
+ | |||
+ | === 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] === | ||
+ | *[http://homes.dsi.unimi.it/~aguzzoli/didattica/algo/lucidi4.pdf IV Lezione] | ||
+ | |||
+ | === 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] === | ||
+ | *[http://homes.dsi.unimi.it/~aguzzoli/didattica/algo/lucidi5.pdf V] | ||
+ | |||
+ | === 21/11/2008 [VEN] === | ||
+ | *Alberi binari | ||
+ | *[http://homes.dsi.unimi.it/~torelli/Grafi%20e%20alberi.pdf 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 | ||
+ | *[http://homes.dsi.unimi.it/~torelli/Codici%20e%20linguaggi2e.pdf 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). |
Versione attuale delle 20:41, 26 gen 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).