Algoritmi e strutture dati T2/2008-2009

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]

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]

II Lezione

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

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]

• 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
• Pile
• Stack
• Code
• Linked List

06/11/2008 [GIO][LAB]

• IV Lezione

07/11/2008 [VEN]

• teorema principale
• alberi di matula
• liste singolarmente linkate
• implementazione di puntatori e ogetti
• introduzione rapresentazione degli alberi binari

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]

• Risoluzione delle collisioni mediante liste
• Funzione hash: metodo della divisione, moltiplicazione e hashing universale
• Risoluzione delle collisioni con indirizzamento aperto: ispezione lineare, quadratica
• Analisi dell'hashing ad indirizzamento aperto