Visualizza wikitesto di Algoritmi e strutture dati T2/2008-2009

[[Categoria:Corsi 2008-2009]]
<!-- non cancellare le righe precedenti -->

=== 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] ===
[http://homes.dsi.unimi.it/~aguzzoli/didattica/algo/l1.zip I Lezione]

=== 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).