Differenze tra le versioni di "Algoritmi e strutture dati T2/2008-2009"

Da WikiDsy.
(→‎Diario del corso)
(→‎03/12/2008 [MER])
 
(47 versioni intermedie di 4 utenti non mostrate)
Riga 52: Riga 52:
  
 
=== 02/10/2008 [GIO][LAB] ===
 
=== 02/10/2008 [GIO][LAB] ===
−
 
+
[http://homes.dsi.unimi.it/~aguzzoli/didattica/algo/l1.zip I Lezione]
−
*Introduzione al Linguaggio C
 
−
*Esempi vari
 
−
*Slides fino a pag.56
 
  
 
=== 03/10/2008 [VEN] ===
 
=== 03/10/2008 [VEN] ===
Riga 67: Riga 64:
 
*Merge Sort
 
*Merge Sort
  
−
=== 09/10/2008 [MER] ===
+
=== 08/10/2008 [MER] ===
  
 
*Complessità di un algoritmo e di un problema
 
*Complessità di un algoritmo e di un problema
 
*Notazioni asintotiche (O, Ω, Θ, o piccolo)
 
*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


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]

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]

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]

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).
Estratto da "https://wiki.dsy.it/index.php?title=Algoritmi_e_strutture_dati_T2/2008-2009&oldid=19132"