PARTE QUARTA: Il Problema del Dizionario

23/10/02:

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.

 

24/10/02:

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.

 

29/10/02:

Algoritmo ricorsivo di ricerca e relativa complessità. Algoritmo di ricerca del predecessore di un nodo: correttezza ed analisi della complessità.

Approfondimento: Operazione 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: 60, 61, 62, 63.

 

30/10/02:

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.

 

31/10/02:

Approfondimento: Esercizi riepilogativi di preparazione alla prova intermedia.