I Esonero di Fondamenti di Informatica II (secondo modulo)
27-5-1998
Compito B
Esercizio N. 1 Illustrare con esempi in che modo la randomizzazione può aiutare nella gestione di informazioni.

Esercizio N. 2 Supporre di avere un insieme S di record con chiavi appartenenti a un insieme ordinato (esempio i numeri di matricola da 0000 a 9999) e di dover leggere tutti i record con chiave k maggiore o uguale di k1, e minore o uguale di k2.

Determinare il costo di tale operazione se l'insieme è memorizzato su:

1. una lista ordinata,

2. un B-albero,

3. un B+-albero.

 Assumere che |S| = n e che la cardinalità dell'insieme di record con chiave compresa tra k1 e k2 sia m.

Esercizio N. 3 Mostrare come si può affrontare il problema della ricerca del massimo elemento di un array con il metodo divide et impera. Fornire la relazione di ricorrenza e mostrare che la soluzione è C(n) = n - l.