Algoritmi e strutture dati - Esercizi

Vero. E’ facile dimostrare che n +

√ 2 3

3

(c) 5n n + O(n ) = O(n ) √ √

3 3

3 3

≤ ∀n ≥

Vero. E’ facile vedere che 5n n n , 25, quindi 5n n = O(n ). Il risultato segue dal fatto che la

3 2 3

somma di una funzione in O(n ) ed una in O(n ) è nella classe O(n ).

2

(d) Falso. E’ facile vedere che 4n + lg(n ) = 4n + 2lg(n) = Θ(n). Dovrebbe quindi essere 4n lg(n) = O(n). Assurdo

≤ ≥

perchè non possono esistere c, n > 0 tali che 4n lg(n) cn per ogni n n

0 0

Esercizio 4

Si vuole dimostrare la correttezza del programma seguente:

1 n, s)

esercizio(A,

←

2 i 1

←

3 k 0 ≤

4 while i n

←

5 do k s, A, k)

insert(A[i],

←

6 i i +1

rispetto alla specifica:

Input (Pre-condizione): A[1..n] è un array di interi; s è un intero.

Output (Post-condizione): A[1..k] è un array ordinato che contiene tutti gli elementi inizialmente in A[1..n] che

sono maggiori di s.

Si proponga una specifica per la procedura s, A, m) che permetta di dimostrare la correttezza del programma

insert(x,

esercizio.

Soluzione

La procedura s, A, m) deve essere corretta rispetto la seguente specifica:

insert(x,

Input (Pre-condizione): x, s sono interi; A[1..m] è un array ordinato di interi maggiori di s.

≤

Output (Post-condizione): se x s ritorna k = m e lascia inalterata A[1..m]; altrimenti ritorna k = m + 1 e un array

ordinato A[1..k] che contiene anche x oltre a tutti gli elementi inizialmente in A[1..m].

Con questa specifica la correttezza di segue dall’invariante:

esercizio −

A[1..k] è un array ordinato che contiene tutti gli elementi inizialmente in A[1..i 1] che sono maggiori di s.

Esercizio 5

Scrivere un algoritmo ricorsivo che, data una sequenza di n > 0 numeri positivi contenuta in un array A[1 .. n], utilizzi

la tecnica divide-et-impera per determinare se la sequenza contiene un numero pari di 2.

Descrivere la complessità dell’algoritmo proposto.

Soluzione

Sviluppiamo un algoritmo PariDispari(A,p,r) che restituisce true se la sequenza in A[p .. r ] contiene un numero dispari

di 2, false altrimenti. La chiamata iniziale sarà PariDispari(A,1,n). Assumiamo che == denoti un test di uguaglianza

applicabile sia a numeri interi che a valori booleani.

PariDispari(A,p,r)::=

if p=r then return (A[p]==2)

else if p<r then q = (p+r) div 2;

firstpart = PariDispari(A,p,q);

secondpart = PariDispari(A,q+1,r);

return (firstpart==secondpart)

Correttezza

Terminazione: L’algoritmo termina perchè le chiamate ricorsive vengono effettuate su parti sempre piu’ piccole del-

l’array iniziale.

Possiamo quindi utilizzare un ragionamento induttivo.

Base. Il caso di base si verifica quando l’array contiene un solo elemento e la risposta è corretta.

Passo induttivo. Se assumiamo che firstpart sia true se e solo se l’array A[p..q] contiene un numero pari di 2 e sec-

ondpart sia true se e solo se l’array A[q + 1..r] contiene un numero pari di 2, allora A[p..r] contiene un numero pari

di 2 se e solo se firstpart e secondpart sono entrambi true oppure false. La risposta è quindi corretta.

Esercizio 6 ≤ ≤

Diciamo che x è un massimo locale in una sequenza di interi (x , . . . , x ) se 1 < i < n e x x e x x .

i 1 n i−1 i i+1 i

Esempio: nella sequenza (7, 5, 2, 8, 8, 4, 9, 4, 5) vi sono 3 massimi locali: 8,8,9.

• ≥

Si scriva lo pseudocodice di un algoritmo che data una array A[1..n], di interi, con n 2, restituisce il numero

m dei massimi locali di A.

• Si dimostri la correttezza dell’algoritmo e se ne discuta la complessità.

Soluzione

max_loc(A,n)

m <- 0

i <- 2

while i < n

do if (A[i-1] <= A[i]) and (A[i+1] <= A[i])

then m <- m+1

i <- i+1

return m

La correttezza si dimostra utilizzando il seguente invariante per il ciclo while:

m e’ il numero di massimi locali di A[1 .. i-1]

Inizializzazione: Prima della prima esecuzione del ciclo i = 2 e, per la definizione data, non ci sono massimi locali in

A[1..2]; pertanto l’invariante è verificato.

Mantenimento: Il test verifica se A[i] è un massimo locale e in caso di risposta affermativa incrementa il valore di m.

Pertanto l’invariante viene preservato con l’incremento di i.

Terminazione: Il ciclo termina con i = n. L’invariante assicura che sono stati conteggiati tutti i massimi locali di

A[1..n-1]. Poichè, per la definizione data, A[n] non può essere un massimo locale, tutti i massimi locali di A sono già

stati conteggiati.

La complessità e’ chiaramente lineare.

Esercizio 7 ∈

Date le seguenti procedure A e B, si determini la complessità asintotica della procedura A(n) su input n N .

A(n) ←

1 S 0

←

2 for i 1 to n

←

3 do S S + B(i)

4 return S

B(m) ←

1 S 0

←

2 for i 1 to m

←

3 do S S + i

4 return S

Soluzione

Poichè A richiama B dobbiamo calcolare la complessità T (m) di B su input m. E’ facile vedere che tale complessià è

B

uguale a cm per una qualche costante c > 0 in quanto la procedura consiste di un ciclo for da 1 ad m. La complessità

T (n) di A su input n è quindi determinata dalla sommatoria:

A

n n n c 2

P P P

T (i) = (n + 1)n = Θ(n )

ci = c i =

B

i=1 i=1 i=1 2

Esercizio 8 ∈

Date le seguenti procedure e si determini la complessità asintotica della procedura su input n N .

A B, A(n)

A(n) ←

1 s 0

←

2 for i 1 to n

←

3 do s s + B(n)

4 return s

B(m)

1 if m = 1

2 then return 0

3 else return B(m/2) + m

Soluzione

La complessità di può essere espressa tramite la ricorrenza T (n) = T (n/2) + Θ(1) che si risolve facilmente con il

B B B

master method ottenendo T (n) = Θ(logn). Per la complessità di abbiamo

A

B

A(n) ←

1 s 0 1

←

2 for i 1 to n n + 1

n

P

←

3 do s s + T (n) = nT (n)

B(n) B B

i=1

4 return s 1

n n

P P

e quindi: T (n) = T (n) = Θ(logn) = Θ(nlogn)

A B

i=1 i=1

Esercizio 9 √

Nell’ipotesi che = Θ( m), determinare la complessità asintotica (caso peggiore) della seguente procedura

Proc(m) ∈

n) al crescere di n N .

Fun(A, n)

Fun(A,

1 if n < 1

2 then return 1

←

3 t n/2)

Fun(A,

2

4 if t > n 12 ·

← − n/2)

5 then t t Fun(A,

←

6 for j 1 to n

←

7 do t t + A[j] + Proc(n)

8 return t

Soluzione

n)

Fun(A,

1 if n < 1 return 1

←

2 t n/2) T (n/2)

Fun(A, Fun

2

3 if t > n 12

← − ·

4 then t t n/2) T (n/2)

Fun(A, Fun

←

5 for j 1 to n √

←

6 do t t + A[j] + n n

Proc(n)

7 return t

Nel caso peggiore vengono effettuate entrambe le chiamate ricorsive e quindi T (n) soddisfa la ricorrenza T (n) =

√ Fun Fun

·

2 T (n/2) + Θ(n n) e la complessità asintotica della procedura si trova risolvendo tale ricorrenza. Questo si

Fun √ √

Fun 1+

ottiene facilmente utilizzando il Master Method. Si ha a = 2, b = 2, log 2 = 1, n n = Ω(n ), e n n soddisfa la

2 √ 3

proprietà di regolarità. Quindi siamo nel caso 3 ed abbiamo T (n) = Θ(n n) = Θ(n ).

2

Fun

Esercizio 10

Considerata la ricorrenza: n 2

) + 3n + n

T (n) = 10T ( 3

si richiede di:

• risolverla utilizzando il teorema principale;

2

• ), giustificando la risposta.

dire se T (n) = O(n

Soluzione 2 2

• E’ facile vedere che f (n) = 3n + n = Θ(n ). Possiamo quindi valutare lg 10 per verificare quale dei tre casi è

3 2 lg 10−

applicabile. Notiamo che 2 < lg 10 e che pertanto esiste una costante positiva tale che n = n . Quindi

3

3

lg 10− lg 10

f (n) = O(n ). Siamo nel caso 1 del metodo principale e quindi T (n) = Θ(n ).

3 3

lg 10 2

• ≥

No. Dovrebbero esistere c, n tali che n < cn per ogni n n , assurdo in quanto si avrebbe c > n , per

3

0 0

≥

ogni n n .

0

Esercizio 11

Considerata la ricorrenza: √

n 2

T (n) = 3T ( ) + 4n n

2

• la si risolva utilizzando il teorema principale;

3

• si dica se T (n) = O(n ), giustificando la risposta.

Soluzione

• Dobbiamo innanzitutto valutare lg 3 per verificare quale dei tre casi è applicabile. Otteniamo 1 < lg 3 < 2.

√

2 2

2 n) e quindi scartare subito i primi due casi. La prima condizione di

Possiamo poi notare che f (n) = Θ(n 2

applicabilità del terzo caso si verifica facilmente osservando che f (n) = Ω(n ) e che esiste un > 0 tale che

√

n n

2 2

lg 3+ p ≤

∗ ) c 4n

lg 3 + = 2, ovvero che f (n) = Ω(n ). La condizione di regolarità (3 4( n) si verifica

2

2 2 2

√ √

3

n n

2 2 2

p ≤ ∗

∗ ) 4n n. Pertanto T (n) = Θ(f (n)) = Θ(n n)

facilmente scegliendo c = 3/4: 3 4( 2 2 4

√

2 3 2 3

• ≤

E’ facile verificare che n n n , per ogni n > 1, e quindi che n lg n = O(n ). Dalla risposta precedente e

3

dala proprietà transitiva per la classe O si ottiene T (n) = O(n ).

Esercizio 12

Considerata la ricorrenza: n 2

T (n) = 8T ( ) + 2n lg n

3

• la si risolva utilizzando il teorema principale;

3

• si dica se T (n) = O(n ), giustificando la risposta.

Soluzione

• Dobbiamo innanzitutto valutare lg 8 per verificare quale dei tre casi è applicabile. Otteniamo 1 < lg 8 < 2.

3 3

2

Possiamo poi notare che f (n) = Θ(n lg n) e quindi scartare subito i primi due casi. La prima condizione di

2

applicabilità del terzo caso si verifica facilmente osservando che f (n) = Ω(n ) e che esiste un > 0 tale che

n n

2 2

lg 8+ ≤

∗ ) lg c2n lg n) si verifica

lg 8 + = 2, ovvero che f (n) = Ω(n ). La condizione di regolarità (8 2(

3

3 3 3

n n 8

2 2 2

∗ ≤ ∗

facilmente scegliendo c = 8/9: 8 2( ) lg 2n lg n. Pertanto T (n) = Θ(f (n)) = Θ(n lg n)

3 3 9

2 3 2 3

• ≤

E’ facile verificare che n lg n n e quindi che n lg n = O(n ). Dalla risposta precedente e dala proprietà

3

transitiva per la classe O si ottiene T (n) = O(n ).

Esercizio 13

Si consideri la ricorrenza: n

n ) + T ( ) + 4n

T (n) = T ( 4 8

e si dimostri la verità o falsità delle seguenti affermazioni, utilizzando il metodo di sostituzione o le proprietà delle

classi di complessità