Home Introduzione Programma Orario Laboratorio Nettuno Esame Diario 02-03 Materiale Challenge News Link Forum Esoneri

horizontal rule

Diario delle lezioni 2002-03

Lezioni del 2001-02

In corsivo le esercitazioni in laboratorio

28/04/03 29/04/03 05/05/03 06/05/03 08/05/03 12/05/03
13/05/03 15/05/03 19/05/03 20/05/03 22/05/03 26/05/03
27/05/03 29/05/03 03/06/03 05/06/03 09/06/03 10/06/03
12/06/03 16/06/03 17/06/03 23/06/03

 

horizontal rule

 

data 28/4/2003
tipo lez
#ore 2
#ore tot 2
argomenti
  1. Introduzione al corso
  2. Definizione di algoritmo e di struttura dati
  3. Modello di analisi dei costi
    bulletcosti uniformi
    bulletdimensione dell'input
    bulletanalisi di caso peggiore
listati  
riferimenti
bullet[1] Sez. 2.8
bullettrasparenze "Introduzione e modello di analisi" (1-18)
siti web  
commenti  

torna all'elenco delle lezioni

horizontal rule

data 29/4/2003
tipo lez
#ore 2
#ore tot 4
argomenti
  1. Modello di analisi dei costi
    bulletriepilogo
    bulletanalisi asintotica
    bulletoperazione dominante
    bulletnotazione asintotica
  2. Analisi dell'InsertionSort
esercizi svolti
esercizi proposti
listati
commenti
riferimenti
bullet[1] Sez. 2.1, 2.2, 2.3, 2.4, 2.5, 2.6, 2.7, 9.1.1
bullettrasparenze "Analisi asintotica" (1-6)
siti web

torna all'elenco delle lezioni

horizontal rule

data 5/5/2003
tipo lez
#ore 2
#ore tot 6
argomenti
  1. Esempi di analisi asintotica di caso peggiore in funzione della dimensione dell'input
  2. Discussione sulla dimensione dell'input
  3. Metodologia di progetto di algoritmi "divide et impera"
  4. Merge-sort: algoritmo ed analisi
  5. Equazioni di ricorrenza
  6. GeneralitÓ sui tipi astratta di dati (ADT)
  7. Specifica Java attraverso interfacce degli ADT
esercizi svolti
esercizi proposti
listati
commenti
riferimenti
bullet[1] Sez. 2.8, 9.3.4
bullettrasparenze "Analisi asintotica" (7-8)
bullettrasparenze "Divide et impera" (1-6)
bullettrasparenze "Liste, pile e code" (1-2)
siti web

torna all'elenco delle lezioni

horizontal rule

data 6/5/2003
tipo lez
#ore 2
#ore tot 8
argomenti
  1. Array e Vector
  2. Cenno agli iteratori (interfaccia Iterator)
  3. Cenno al concetto di collezione
  4. Interfacce Collection, Set, List
  5. Liste e loro implementazioni
    bulletliste collegate, array, Vector
  6. Discussione operazioni su liste
  7. Confronto costi operazioni su liste collegate, array, array ordinati
  8. ADT Pila: generalitÓ ed operazioni
esercizi svolti
esercizi proposti
  1. ricerca binaria: codice e costo
  2. algoritmo per riconoscimento di stringhe parenteticamente corrette
listati
commenti
riferimenti
bullet[1] Sez. 3.1, 3.1.1, 3.1.2, 3.1.3, 3.2, 3.7, 4.1
bullettrasparenze "Liste, pile e code" (3-20, 24)
siti web

torna all'elenco delle lezioni

horizontal rule

data 8/5/2003
tipo lez
#ore 2
#ore tot 10
argomenti
  1. ADT Pila: implementazioni
    bullettramite Vector e tramite LinkedList
  2. Algoritmo per riconoscimento di stringhe parenteticamente corrette
  3. ADT Coda: generalitÓ ed operazioni
  4. ADT Coda: implementazioni
    bullettramite array circolare e LinkedList
esercizi svolti
esercizi proposti
listati
commenti
riferimenti
bullet[1] Sez. 4.1, 4.1.1, 4.2
bullettrasparenze "Liste, pile e code" (21-36)
siti web

torna all'elenco delle lezioni

horizontal rule

data 12/5/2003
tipo lez
#ore 2
#ore tot 12
argomenti
  1. Presentazione classi Stack e Queue della "asd_library"
  2. Definizione ADT albero
  3. Terminologia di riferimento
  4. Rappresentazione con liste collegate
  5. Operazioni
  6. Rappresentazione del singolo nodo
  7. interfaccia Tree
  8. Algoritmi su alberi e loro analisi
    bulletlivello di un nodo
    bulletaltezza di un albero
esercizi svolti
esercizi proposti
listati
  1. ADT Stack
    bulletfile Stack.java
    bulletfile Stack_adt.java
    bulletfile StackDemo.java
  2. ADT Queue
    bulletfile Queue.java
    bulletfile Queue_adt.java
    bulletfile QueueDemo.java
commenti Il libro di testo non contiene dettagli su alberi generici
riferimenti
bullet[1] Sez. 6.1
bullettrasparenze "Alberi" (1-15)
siti web

torna all'elenco delle lezioni

horizontal rule

data 13/5/2003
tipo lez
#ore 2
#ore tot 14
argomenti
  1. visite di alberi
  2. visite in profonditÓ (algoritmi ricorsivi)
    bulletpreordine
    bulletinordine
    bulletpostordine
  3. visita in ampiezza
  4. analisi degli algoritmi di visita
  5. alberi binari
  6. rappresentazione di alberi binari
  7. ADT in Java
  8. visite di alberi binari
    bulletpreordone
    bulletinordine
    bulletpostordine
    bulletampiezza
  9. analisi degli algoritmi di visita
  10. alberi binari rappresentati tramite array
    bulletvantaggi
    bulletsvantaggi
esercizi svolti
esercizi proposti algoritmo per la visita di un labirinto
listati
commenti
riferimenti
bullet[1] Sez. 6.2, 6.4, 6.4.1, 6.4.2, 
bullettrasparenze "Alberi" (16-30)
siti web

torna all'elenco delle lezioni

horizontal rule

data 15/5/2003
tipo lab
#ore 2
#ore tot 2
argomenti
esercizi svolti
esercizi proposti
listati
commenti
riferimenti vedi pagina laboratorio
siti web

torna all'elenco delle lezioni

horizontal rule

data 19/5/2003
tipo lez
#ore 2
#ore tot 16
argomenti
  1. considerazioni su eliminazione della ricorsione
  2. eliminazione ricorsione sull'algoritmo di visita in preordine di un albero
  3. considerazioni di costo
  4. concetto di chiave
  5. chiavi in Java e interface Comparable
  6. alberi binari di ricerca (BST)
  7. rappresentazione dei nodi
  8. operazioni sui BST
  9. ricerca iterativa e ricorsiva nei BST
  10. costo della ricerca nei BST (caso peggiore)
esercizi svolti
esercizi proposti
listati
commenti
riferimenti
bullet[1] Sez. 5.2, 5.3, 5.4, 5.5, 6.2, 6.3, 6.4.2
bullettrasparenze "Eliminazione della ricorsione" (1-7)
bulletalberi binari di ricerca (1-16)
siti web

torna all'elenco delle lezioni

horizontal rule

data 20/5/2003
tipo lez
#ore 2
#ore tot 18
argomenti
  1. ricerca nei BST: analisi di caso medio (distribuzione uniforme)
  2. ricerca predecessore e successore nei BST: algoritmi e costi
  3. inserimento in un BST: algoritmo e costo
esercizi svolti
esercizi proposti
listati
commenti
riferimenti
bullet[1] Sez. 6.3, 6.5
bulletalberi binari di ricerca (17-29)
siti web

torna all'elenco delle lezioni

horizontal rule

data 22/5/2003
tipo lab
#ore 2
#ore tot 4
argomenti
esercizi svolti
esercizi proposti
listati
commenti
riferimenti vedi pagina laboratorio
siti web

torna all'elenco delle lezioni

horizontal rule

data 26/5/2003
tipo lez
#ore 2
#ore tot 20
argomenti
  1. eliminazione da un BST
  2. algoritmi e costi
  3. ADT dizionario
  4. operazioni sul dizionario
  5. alberi perfettamente bilanciati
esercizi svolti
esercizi proposti
listati
commenti
riferimenti
bullet[1] Sez. 6.7
bulletalberi binari di ricerca (30-37)
bulletalberi AVL (1-5)
siti web

torna all'elenco delle lezioni

horizontal rule

data 27/5/2003
tipo lez
#ore 2
#ore tot 22
argomenti
  1. alberi perfettamente bilanciati: prestazioni e limiti
  2. bilanciamento in altezza e alberi AVL
  3. alberi di Fibonacci
  4. altezza di un albero di Fibonacci
  5. altezza di un albero AVL
  6. discussione sui requisiti degli algoritmi di inserimento/eliminazione
esercizi svolti
esercizi proposti
listati
commenti
riferimenti
bullet[1] Sez. 6.7.2
bulletalberi AVL (5-12)
siti web

torna all'elenco delle lezioni

horizontal rule

data 29/5/2003
tipo lez
#ore 2
#ore tot 24
argomenti
  1. algoritmo di inserimento in AVL
  2. rotazione semplice, rotazione doppia
  3. costo inserimento in AVL
  4. algoritmo di eliminazione da AVL
  5. costo eliminazione da AVL
esercizi svolti
esercizi proposti
listati
commenti
riferimenti
bullet[1] Sez. 6.7.2
bulletalberi AVL (13-28)
siti web
http://www.seanet.com/users/arsen/avltree.html (animazione AVL)

(classi Java rilevanti, da scaricare a partire dalla URL base http://www.seanet.com/users/arsen: BTApplet, BTData, BTNode, BTPanel, BTSprite, BTTool, BTTree, MODE, MSG, SOUND; inoltre occorre scaricare le cartelle http://www.seanet.com/users/arsen/images/ e http://www.seanet.com/users/arsen/sounds/)

(non ci sei riuscito? clicca qui)

torna all'elenco delle lezioni

horizontal rule

data 3/6/2003
tipo lez
#ore 2
#ore tot 26
argomenti
  1. coda di prioritÓ
  2. heap
  3. rappresentazione degli heap
  4. operazioni sugli heap: inserimento, eliminazione e getFirst
  5. operazione heapify
  6. array2heap
esercizi svolti
esercizi proposti
listati
commenti
riferimenti
bullet[1] Sez. 6.9, 6.9.1, 6.9.2
bulletheap (1-27)
siti web

torna all'elenco delle lezioni

horizontal rule

data 5/6/2003
tipo lab
#ore 2
#ore tot 6
argomenti
esercizi svolti
esercizi proposti
listati
commenti
riferimenti vedi pagina laboratorio
siti web

torna all'elenco delle lezioni

horizontal rule

data 9/6/2003
tipo lez
#ore 2
#ore tot 28
argomenti
  1. algoritmo di Floyd
  2. analisi algoritmo di Floyd
  3. HeapSort e sua analisi
  4. SelectionSort e sua analisi
  5. sorting di elementi Comparable
esercizi svolti
esercizi proposti
listati
commenti
riferimenti
bullet[1] Sez. 6.9.2, 9.1.2
bulletheap (28-41)
bulletsorting (1-10)
siti web

torna all'elenco delle lezioni

horizontal rule

data 10/6/2003
tipo lez
#ore 2
#ore tot 30
argomenti
  1. quicksort e sua analisi
  2. lower bound
  3. alberi di decisione e lower bound del sorting
esercizi svolti
esercizi proposti
listati
commenti
riferimenti
bullet[1] Sez. 9.2, 9.3.3
bulletsorting (11-26)
siti web

torna all'elenco delle lezioni

horizontal rule

data 12/6/2003
tipo lab
#ore 2
#ore tot 8
argomenti
esercizi svolti
esercizi proposti
listati
commenti
riferimenti vedi pagina laboratorio
siti web

torna all'elenco delle lezioni

horizontal rule

data 16/6/2003
tipo lez
#ore 2
#ore tot 32
argomenti
  1. indirizzamento diretto
  2. tabelle hash
  3. funzioni hash
  4. paradosso del compleanno
  5. funzioni hash su interi e su stringhe
  6. tecniche di risoluzione delle collisioni
  7. concatenazione
  8. open addressing
  9. clustering primario e secondario
esercizi svolti
esercizi proposti
listati
commenti
riferimenti
bullet[1] Sez. 10.1, 10.1.1, 10.1.2, 10.1.3, 10.1.4, 10.2, 10.2.1, 10.2.2, 10.4
bullethashing (1-29)
siti web http://www.engin.umd.umich.edu/CIS/course.des/cis350/hashing/WEB/HashApplet.htm (animazione hashing; si pu˛ scaricare uno jar file dalla URL http://www.engin.umd.umich.edu/CIS/course.des/cis350/hashing/WEB/HashApplet.jar

torna all'elenco delle lezioni

horizontal rule

data 17/6/2003
tipo lez
#ore 2
#ore tot 34
argomenti
  1. cancellazione nelle tavole hash
  2. considerazioni sul fattore di carico delle tavole hash
  3. introduzione ai grafi
  4. definizioni e proprietÓ
  5. rappresentazioni dei grafi e loro proprietÓ
esercizi svolti
esercizi proposti
listati
commenti
riferimenti
bullet[1] Sez. 10.3, 8.1
bulletgrafi (1-10)
siti web

torna all'elenco delle lezioni

horizontal rule

data 23/6/2003
tipo lez
#ore 2
#ore tot 36
argomenti
  1. Visita DFS ricorsiva
  2. DFS iterativa
  3. significato delle marcature
  4. proprietÓ della DFS
  5. costo DFS
  6. DAG e ordini parziali
  7. definizione topological sort
esercizi svolti
esercizi proposti
listati
commenti
riferimenti
bullet[1] Sez. 8.2, 8.7
bulletgrafi (11-25)
siti web

torna all'elenco delle lezioni

horizontal rule

data 24/6/2003
tipo
#ore
#ore tot
argomenti
esercizi svolti
esercizi proposti
listati
commenti
riferimenti
siti web

torna all'elenco delle lezioni

horizontal rule

data 26/6/2003
tipo
#ore
#ore tot
argomenti
esercizi svolti
esercizi proposti
listati
commenti
riferimenti
siti web

torna all'elenco delle lezioni

 

horizontal rule

Bacheca di Algoritmi e Strutture Dati a.a. 2007-08 - canale A - L

forum del corso

ultima modifica: 03/04/2008 23.36
by FdA