13 02 2015

Pagina 1

Algoritmi e Principi dell'Informatica Seconda Prova in Itinere 13 Febbraio 2015 Avvisi importanti Il tempo a disposizione è di 1 ora e 45 minuti. Esercizio 1 (punti 5/15-esimi) Si calcoli la complessità del seguente frammento di codice ossatura di una funzione f applicata a un array A: f(A): n := A.length i := 1 altre eventuali inizializzazioni eseguite in tempo costante while i < n do_something_in_tempo_costante i := i*2 f(A[1..n/3]) f(A[n/3+1..(2/3)*n]) j := 2 while j < n*n do_something_in_tempo_costante j := j*j return result Esercizio 2 (punti 7/15-esimi) Si consideri un albero rosso-nero di altezza nera bh e costituito da soli nodi neri. 1. Quali sono, rispettivamente, il numero minimo e massimo di nodi contenuti lbero? (si precisi se nel conto viene incluso il nodo T.NIL o no). 2. -nero costituito da soli nodi neri applicandovi esclusivamente operazioni di inserimento di nuovi nodi? In caso positivo in che modo? (eventualmente illustrandolo mediante un semplice esempio). 3. Qual è il numero massimo di nuovi nodi che si possono inserire in esso senza effettuare cancellazioni e senza alterare bh? Si forniscano brevi ma chiare spiegazioni per le risposte date. Esercizio 3 (punti 7/15-esimi) Sia dato un grafo G e due sottoinsiemi dei suoi vertici, V1 e V2. La distanza tra V1 e V2, d(V1, V2), è la distanza minima tra un nodo appartenente a V1 e un nodo appartenente a V2. Se V1 e V2 non sono disgiunti allora la loro distanza è uguale 0. Si specifichi un algoritmo che, a partire da un grafo G e da due suoi sottoinsiemi V1 e V2, calcoli la distanza tra V1 e V2; se ne discuta quindi la complessità . La valutazione dell dipenderà ovviamente dalla sua complessità. N.B.: Si può assumere che esista una funzione che in tempo costante vertice a uno dei due insiemi. Tracce di…