PARTE QUARTA: Il Problema del
Dizionario
-
22/10/03:
-
Il problema del dizionario. Gestione di un dizionario mediante un
array non ordinato: operazioni di ricerca, inserimento e cancellazione
e relativi costi. Lower bound problema della ricerca in un insieme
non ordinato.
Gestione di un dizionario mediante un array ordinato. Lower bound al problema
della ricerca in un insieme non ordinato. La ricerca binaria. Ottimalità
della ricerca binaria. Operazione di inserimento e relativo costo.
-
Dispense: 49,
50,
51,
52,
53,
54.
-
23/10/03:
-
Alberi binari di ricerca (ABR): definizione, esempi. Visita anticipata,
posticipata e simmetrica di un ABR. Algoritmo ricorsivo di visita simmetrica.
-
Approfondimento: Algoritmo ricorsivo di visita anticipata e posticipata.
Algoritmo di inserimento in un array ordinato.
-
Dispense: 55,
56,
57,
58,
59,
60,
61.
-
28/10/03:
-
Algoritmo ricorsivo di ricerca e relativa complessità. Algoritmo
di ricerca del predecessore di un nodo: correttezza ed analisi della
complessità.
-
Approfondimento: Algoritmo iterativo di ricerca. Algoritmi di ricerca
del minimo e del massimo e relativa complessità. Algoritmo
di ricerca del successore di un nodo: correttezza ed analisi della complessità.
-
Dispense:
62,
63.
-
29/10/03:
-
Algoritmo di inserimento ed analisi della
correttezza e della complessità.
Algoritmo di cancellazione ed analisi della correttezza e della
complessità. Variazione del
rapporto tra numero di nodi nell'ABR e relativa altezza. ABR con altezza
logaritmica nel numero di nodi contenuti.
-
Dispense: 64,
65, 66,
67, 68.
-
30/10/03:
-
Approfondimento: Esercizi riepilogativi di preparazione alla prova intermedia.