horizontal rule

Diario delle lezioni

In corsivo le esercitazioni in laboratorio

23/04/02 30/04/02 02/05/02 09/05/02 14/05/02 16/05/02
21/05/02 23/05/02 28/05/02 30/05/02 04/06/02 11/06/02
13/06/02 18/06/02 20/06/02 25/06/02 27/06/02

Risorse generali

bulletuna classe per la semplificazione delle operazioni di lettura da console
bulletConsoleReader: codice (download), documentazione

 

horizontal rule

 

data 23/4/2002
tipo lez
#ore 2.5
#ore tot 2.5
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
    bulletanalisi asintotica
    bulletconcetto di istruzione (o operazione) dominante
    bulletnotazione asintotica
  4. Esempio: analisi dell'Insertion Sort
listati  
riferimenti
bullet[1] Sez. 2.1, 2.2, 2.3, 2.4, 2.5 (cenni), 2.6, 2.7 (parte). 2.8,
bullettrasparenze "Introduzione e modello di analisi" (1-24)
siti web http://java.sun.com/ 
commenti  

torna all'elenco delle lezioni

horizontal rule

data 30/4/2002
tipo lez
#ore 2.5
#ore tot 5
argomenti
  1. Confronto sperimentale fra un algoritmo quadratico ed un lineare per lo stesso problema (Calcolo delle somme dei prefissi)
  2. Metodologia "divide et impera"
  3. Merge-sort
  4. Equazioni di ricorrenza ed analisi del merge-sort
  5. Liste
    bullettipo astratto e implementazione
esercizi svolti
esercizi proposti Soluzione dell'equazione di ricorrenza del merge-sort per trovare una minorazione del suo costo asintotico di caso peggiore (provare cnlg n)
listati
  1. Somma prefissi
    bulletcodice classe SommaPrefissi (download)
  2. Esempio Vector + Iterator
    bulletcodice classe EsVect (download)
commenti
riferimenti
bullet[1] Sez. 3.1, 3.2
bullettrasparenze "Introduzione e modello di analisi" (24-32)
bullettrasparenze "Liste, pile e code" (1-13)
siti web

torna all'elenco delle lezioni

horizontal rule

data 2/5/2002
tipo lez
#ore 2.5
#ore tot 7.5
argomenti
  1. Liste
    bullettipo astratto e implementazione
  2. Pile
    bullettipo astratto e implementazione
  3. Code
    bullettipo astratto e implementazione
  4. Cenno al deque
    bullettipo astratto con operazioni di push, pop, enqueue, dequeue
  5. Confronti su operazioni di inserimento, ricerca e cancellazione
    bulletv. esercizi proposti
esercizi svolti Algoritmo per il riconoscimento delle stringhe parenteticamente corrette
esercizi proposti Completare la tabella con i costi asintotici di caso peggiore delle operazioni su lista (implementazione collegata e basata su array):
  1. inserimento elemento
    bulletin testa
    bulletin coda
    bulletin posizione i-esima assegnata
    bulletin posizione sconosciuta (è nota solo una proprietà dell'elemento da cancellare)
  2. cancellazione elemento
    bulletin testa
    bulletin coda
    bulletin posizione i-esima assegnata
    bulletin posizione sconosciuta (è nota solo una proprietà dell'elemento da cancellare)
  3. ricerca elemento
    bulleti-esimo 
    bulletin posizione sconosciuta (è nota solo una proprietà dell'elemento desiderato)
listati
  1. Code (implementazione con array)
    bulletcodice classe ArrayQueue (download)
  2. Code (implementazione collegata)
    bulletcodice classe QueueNode (download)
    bulletcodice classe Queue (download)
commenti deque: erroneamente indicato con deck
riferimenti
bullet[1] Sez. 3.7, 3.8, 4.1, 4.2
bullettrasparenze "Liste, pile e code" (13-35)
siti web

torna all'elenco delle lezioni

horizontal rule

data 7/5/2002
tipo lez
#ore 2.5
#ore tot 10
argomenti
  1. tipo astratto albero
  2. definizioni e concetti base
  3. rappresentazione con liste collegate
  4. operazioni sugli alberi
  5. rappresentazione in Java
  6. algoritmi
    bulletlivello di un nodo
    bulletaltezza di un (sotto)albero
  7. attraversamento di un albero
    bulletvisite in profondità
    bulletpreordine
    bulletinordine
    bulletpostordine
    bulletvisita in ampiezza
esercizi svolti completamento tabella complessità delle operazioni di inserimento e cancellazione su lista concatenata e su lista realizzata tramite array
esercizi proposti progettare un algoritmo per calcolare il livello di un nodo dato, assumendo una rappresentazione dei nodi priva del riferimento al genitore
listati
commenti
riferimenti
bullet[1] Sez. 6.1, 6.2, 6.4, 
bullettrasparenze "Alberi" (1-21)
siti web

torna all'elenco delle lezioni

horizontal rule

data 9/5/2002
tipo lez
#ore 2.5
#ore tot 12.5
argomenti
  1. alberi binari
  2. rappresentazione in Java
  3. visite di alberi binari
    bulletpreordine, inordine, postordine, ampiezza
  4. strutture dati per alberi binari
    bulletrappresentazione tramite array
    bulletrappresentazione tramite strutture collegate
  5. alberi binari di ricerca (BST)
  6. rappresentazione collegata
  7. richiami sull'interface Comparable
  8. operazioni sui BST
  9. ricerca e costo della ricerca
  10. inserimento in un BST e suo costo
  11. esempio di inserimento di 700000 chiavi casuali in un BST
    bulletvalutazioni empiriche sull'altezza di un BST nel caso medio
esercizi svolti
esercizi proposti realizzazione di un albero binario per il gioco "Indovina l'animale"
listati
commenti Lo spazio richiesto nel caso peggiore per la rappresentazione tramite array di un albero binario è esponenziale nel numero dei nodi
riferimenti
bullet[1] Sez. 6.3, 6.4, 6.5 
bullettrasparenze "Alberi" (22-32)
bullettrasparenze "Alberi binari di ricerca" (1-15 e 18-22)
siti web

torna all'elenco delle lezioni

horizontal rule

data 14/5/2002
tipo lez
#ore 2.5
#ore tot 15
argomenti
  1. cancellazione da un BST
  2. costo della cancellazione in un BST
  3. concetto di dizionario
  4. alberi bilanciati e bilanciamento perfetto
  5. bilanciamento in altezza ed alberi AVL
  6. fattore di bilanciamento
  7. alberi di Fibonacci
  8. altezza di un AVL
esercizi svolti
esercizi proposti
listati
commenti
riferimenti
bullet[1] Sez. 6.6, (no 6.6.1), 6.6.2, 6.7, (no 6.7.1), 6.7.2
bullettrasparenze "Alberi binari di ricerca" (23-30)
bullettrasparenze "Alberi AVL" (1-12)
siti web http://www.seanet.com/users/arsen/avltree.html (applet che mostra l'animazione degli algoritmi di gestione di un AVL)

torna all'elenco delle lezioni

horizontal rule

data 16/5/2002
tipo lab
#ore 2
#ore tot 2
argomenti
  1. uso della classe ConsoleReader
  2. esercizio di progettazione di due classi per il gioco "Indovina l'animale"
  3. discussione di una soluzione (classi ANode, ATree e TestAnimali)
esercizi svolti
esercizi proposti
listati
bulletClasse ANode download
bulletClasse ATree   (J2SDK 1.4) download
bulletClasse TestAnimali (con main) download
commenti la classe ATree necessita di J2SDK 1.4 a causa del metodo matches (classe String)
riferimenti Documento guida
siti web

torna all'elenco delle lezioni

horizontal rule

data 21/5/2002
tipo lez
#ore 2.5
#ore tot 17.5
argomenti
  1. inserimento negli AVL
    bulletalgoritmi di bilanciamento
    bulletcosto dell'inserimento
  2. cancellazione negli AVL
    bulletalgoritmi di bilanciamento
    bulletcosto della cancellazione
  3. valutazioni complessive e confronto con array ordinati
esercizi svolti
esercizi proposti
listati
commenti
riferimenti
bullet[1] Sez. 6.7.2
bullettrasparenze "Alberi AVL" (13 - 25)
siti web http://www.seanet.com/users/arsen/avltree.html (applet che mostra l'animazione degli algoritmi di gestione di un AVL)

torna all'elenco delle lezioni

horizontal rule

data 23/5/2002
tipo lez
#ore 2.5
#ore tot 20
argomenti
  1. concetto di heap
  2. max- e min-heap
  3. operazioni sugli heap
  4. rappresentazione degli heap
  5. algoritmi 
    bulletgetMax
    bulletinsert
    bulletdelMax e heapify
    bulletArray2Heap
  6. analisi degli algoritmi
  7. code di priorità
esercizi svolti
esercizi proposti estendere la classe Heap per realizzare un min-heap
listati classe Heap (download)
commenti
riferimenti
bullet[1] Sez. 6.9, 6.9.1, 6.9.2
bullettrasparenze "Heap" (1 - 34)
siti web

torna all'elenco delle lezioni

horizontal rule

data 28/5/2002
tipo lez
#ore 2.5
#ore tot 22.5
argomenti
  1. generalità su algoritmi di ordinamento
  2. SelectionSort
  3. QuickSort
  4. Upper bound e lower bound
  5. Alberi di decisione
  6. Lower bound dell'ordinamento
  7. HeapSort
esercizi svolti
esercizi proposti
listati classe Heap (download)
commenti
riferimenti
bullet[1] Sez. 9.1.2, 9.2, 9.3.2, 9.3.3
bullettrasparenze "Heap" (35 - 36)
bullettrasparenze "Algoritmi di ordinamento" (1 - 26)
siti web

torna all'elenco delle lezioni

horizontal rule

data 30/5/2002
tipo lab
#ore 2.5
#ore tot 4.5
argomenti sperimentazione algoritmi di ordinamento
esercizi svolti
esercizi proposti
listati
commenti
riferimenti
bulletDocumento guida
bulletclassi
siti web

torna all'elenco delle lezioni

horizontal rule

data 4/6/2002
tipo lez
#ore 2.5
#ore tot 25
argomenti
bulletdizionari in memoria secondaria
bulletmodello dei costi in memoria secondaria
bulletdefinizione di B-tree e principali proprietà
bulletaltezza di un B-tree
esercizi svolti
esercizi proposti
listati
commenti
riferimenti
bullettrasparenze "B-tree" (1 - 22)
bullet[1] Sez. 7, 7.1, 7.1.1 (fino p. 209)
siti web animazioni per la visualizzazione di B-tree
bullethttp://shell.uriel.net/~mozart/File/btree.html
bullethttp://www.cs.tcd.ie/Jeremy.Jones/vivio/B-tree.htm
(richiede l'installazione di un controllo Active-X)

torna all'elenco delle lezioni

horizontal rule

data 11/6/2002
tipo lez
#ore 2.5
#ore tot 27.5
argomenti
  1. ricerca in un B-tree
  2. inserimento in un B-tree
  3. eliminazione da un B-tree
esercizi svolti Impostazione soluzione interrogazione di range su un B-tree attraverso una visita appropriata dell'albero.
esercizi proposti Completare l'algoritmo per svolgere l'interrogazione di range.
listati
commenti Il giorno 6/6/2002 il docente non ha tenuto la lezione a causa di una indisposizione.
riferimenti
bullettrasparenze "B-tree" (23 - 38)
bullet[1] Sez. 7.1.1
siti web animazioni per la visualizzazione di B-tree
bullethttp://shell.uriel.net/~mozart/File/btree.html
bullethttp://www.cs.tcd.ie/Jeremy.Jones/vivio/B-tree.htm
(richiede l'installazione di un controllo Active-X)

torna all'elenco delle lezioni

horizontal rule

data 13/6/2002
tipo lab
#ore 2.5
#ore tot 7
argomenti
  1. estensione di Heap per definire MinHeap
  2. struttura dati Clessidra, con operazioni:
    bulletinserisci chiave
    bulletget mediano
    bulletdel mediano
esercizi svolti
esercizi proposti
listati

 

commenti
riferimenti
  1. documento guida

siti web

torna all'elenco delle lezioni

horizontal rule

data 18/6/2002
tipo lez
#ore 2
#ore tot 29.5
argomenti
  1. tavole hash
  2. funzioni hash
  3. qualità delle funzioni hash
  4. paradosso del compleanno
  5. tecniche di gestione delle collisioni
    bulletconcatenazione
    bulletopen addressing
  6. hashing estendibile
esercizi svolti
esercizi proposti
listati
commenti
riferimenti
bullettrasparenze "Hashing"
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.5, 10.5.1
siti web

torna all'elenco delle lezioni

horizontal rule

data 20/6/2002
tipo lez
#ore 2.5
#ore tot 32
argomenti
  1. grafi: definizioni e proprietà
  2. rappresentazioni
    bulletliste di adiacenza
    bulletmatrice di adiacenza
    bulletmatrice di incidenza
  3. visita di un grafo
    bulletin profondità (DFS)
    bulletin ampiezza (BFS)
esercizi svolti
esercizi proposti adattare gli algoritmi di visita dei grafi per rilevare cicli
listati
commenti
riferimenti
bullettrasparenze "Grafi" (1-24)
bullet[1] Sez. 8.1, 8.2
siti web

torna all'elenco delle lezioni

horizontal rule

data 25/6/2002
tipo lez
#ore 2
#ore tot 31.5
argomenti
  1. ordinamento topologico
  2. individuazione cicli in un grafo (risolve problema proposto il 20/6/2002)
  3. cammini minimi (Dijkstra)
esercizi svolti
esercizi proposti
listati
commenti
riferimenti
bullettrasparenze "Grafi" (25-32, 37-46)
bullet[1] Sez. 8.3, 8.4, 8.7
siti web

torna all'elenco delle lezioni

horizontal rule

data 27/6/2002
tipo lab
#ore 2.5
#ore tot 9.5
argomenti
  1. algoritmo di ricerca su vettore semi-infinito
  2. generalizzazione di Dijkstra per APSP
esercizi svolti
esercizi proposti
listati
commenti termine didattica faccia a faccia per il 2001-2002
riferimenti
  1. documento guida

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