Esame di Algoritmi e Strutture Dati Corso di Laurea in Ingegneria Informatica

Canali A-L, M-Z

Anno Accademico 2002-2003 9 luglio 2002-03

Domanda 1, punti 6 Si consideri la seguente classe Java, in cui, per semplicità, sono indicate solo le segnature dei metodi pubblici. public class BSTree { public BSTree(); // costruttore: crea BST vuoto public BSTNode insert (int key); // return rif. a nodo inserito o null public BSTNode delete (int key); // return rif. a nodo elimin. o null public BSTNode search (int key); // return rif. a nodo trovato o null public int[] preOrder(); // return array con chiavi visitate public int[] inOrder(); // return array con chiavi visitate public int[] postOrder(); // return array con chiavi visitate public int[] bfs(); // return array con chiavi visitate }

Scrivere una metodo Java, con segnatura public static void sort(int[] data), che ordini un array di int sfruttando i servizi della classe BSTree. Si discuta il costo computazionale dell’algoritmo.

Possibile soluzione Assumiamo che nell’array data non ci siano elementi ripetuti. Si inseriscono gli elementi in un BST e si esegue una visita simmetrica, che restituisce l’array degli elementi del BST ordinati: public static void sort(int[] data) { BSTree aTree = new BSTree(); for(int i = 0; i < data.length; i++) aTree.insert(data[i]); int[] temp = aTree.inOrder(); for(int i = 0; i < data.length; i++) data[i] = temp[i]; } Sia CI(n) il costo dell’inserimento dell’n-esimo elemento. Si ha: costo = CI(0) + CI(1) + … + CI(n-1) (inserimenti) + O(n) (inOrder()) + O(n) (copia array)

= Σ CI(i) + O(n)

Se CI(n)=O(log n) (caso medio), allora costo=O(n log n); se CI(n)=O(n) (caso peggiore), allora costo=O(n2)

1/5

Domanda 2, punti 6 Si consideri la seguente equazione di ricorrenza.

>+−=

=1)1(1

)(ncnnFna

nF

a. Individuare un algoritmo di ordinamento la cui funzione di costo temporale è esprimibile tramite la F(n) definita.

b. Determinare una delimitazione superiore per la funzione F(n)

Possibile soluzione

Un algoritmo di ordinamento la cui funzione di costo è esprimibile tramite la F(n) è SelectionSort. Infatti SelectionSort di volta in volta cerca il massimo in un array di n, n-1, n-2, …, 1 elementi. In altri termini una descrizione ricorsiva di SelectionSort è la seguente (per n > 1):

cerca il massimo tra gli n elementi e ponilo in prima posizione (costo: cn) esegui ricorsivamente SelectionSort sul rimanente sottoarray di n-1

elementi (costo: F(n-1)) da cui si vede che il costo è proprio F(n) = F(n-1) + cn. Nel caso base naturalmente il costo è costante e pari a F(1) = a. Una delimitazione superiore al valore di F(n) è dunque O(n2).

2/5

Domanda 3, punti 6 Fornire un'istanza di albero AVL in cui esiste un nodo la cui cancellazione causa un numero di operazioni di ribilanciamento superiore a uno. Illustrare l'evoluzione dell'albero in seguito a tale cancellazione.

Possibile soluzione

E è sbilanciato Rotazione

Cancello C D è sbilanciato Rotazione

3/5

Domanda 4, punti 6 Scrivere un metodo Java, con segnatura public static AVLNode search_i(AVLNode root, int i), che restituisce l’i-esimo elemento memorizzato in un albero AVL con costo computazionale proporzionale all’altezza dell’albero. Si utilizzi la seguente definizione: class AVLNode { int element; AvlNode left; AvlNode right; int size; } dove size indica il numero di elementi memorizzati nel sottoalbero avente come radice il nodo.

Possibile soluzione L’idea è quella di visitare l’albero AVL scendendo direttamente verso il nodo i-esimo. Di volta in volta ci si chiede se bisogna scendere nel sottoalbero sinistro o nel sottoalbero destro. In particolare, se stiamo cercando il nodo j-esimo di un sottoalbero avente il nodo v come radice:

se il sottoalbero sinistro di v ha almeno j nodi, allora il nodo j-esimo si trova nel sottoalbero sinistro;

se il sottoalbero sinistro di v ha j-1 nodi, il nodo j-esimo è proprio v; altrimenti il nodo j-esimo (se esiste) si trova nel sottoalbero destro di v.

L’algoritmo è il seguente: public static AVLNode search_i(AVLNode root, int i) { if(root == null) return null; if(root.left == null) if(i == 1) return root; else return search_i(root.right, i - 1); else if(root.left.size >= i) return search_i(root.left, i); else if(i == root.left.size + 1) return root; else return search_i(root.right, i – 1 - root.left.size); } Poiché in ogni chiamata ricorsiva si effettua un numero costante di operazioni e si scende di un livello, il costo è proporzionale all’altezza dell’albero.

4/5

5/5

Domanda 5, punti 6 Descrivere un algoritmo che, dato un grafo diretto G, verifichi se G è aciclico. Si discuta il costo computazionale dell’algoritmo.

Possibile soluzione Si può impiegare l’algoritmo di ordinamento topologico: l’algoritmo ha successo se e soltanto se G è un grafo aciclico.

boolean acyclicityTest(Graph G = (V, E)) { i = j = 1; for(v ε V) { num(v) = 0; fin(v) = 0; } while(∃v ε V con num(v) == 0) if(!TS(v)) return false; return true; } boolean TS(Node v) { num(v) = i++; for(ogni nodo w adiacente a v) if(num(w) == 0) { if(!TS(w)) return false; } else if(fin(w) == 0) return false; //scoperto un ciclo fin(v) = j++; return true; } Il costo è quello della DFS, ossia O(m + n) con m=|E|, n=|V|.