10 Exercitii
7.1 Demonstrati
ca procedura binsearch se termina intr-un
numar finit de pasi (nu cicleaza).
Indicatie: Aratati ca binrec(T[i .. j], x) este apelata intotdeauna cu i j si ca binrec(T[i .. j], x) apeleaza binrec(T[u .. v], x) intotdeauna astfel incat
v-u < j-i
7.2 Se poate inlocui
in algoritmul iterbin1:
i) k (i+j+1) div 2
cu k (i+j) div 2?
ii) i k
cu i k+1?
iii) j k-1
cu j k?
7.3 Observati ca bucla while din algoritmul insert (Sectiunea
1.3) foloseste o cautare secventiala (de la coada la cap). Sa inlocuim aceasta
cautare secventiala cu o cautare binara. Pentru cazul cel mai nefavorabil, ajungem
oare acum ca timpul pentru sortarea prin insertie sa fie in ordinul lui n log n?
7.4 Aratati ca timpul pentru iterbin2 este in Q(1), Q(log n),
Q(log n) pentru
cazurile cel mai favorabil, mediu si respectiv, cel mai nefavorabil.
7.5 Fie T[1 .. n] un
tablou ordonat crescator de intregi diferiti, unii putand fi negativi. Dati un
algoritm cu timpul in O(log n) pentru cazul cel mai
nefavorabil, care gaseste un index i,
1 i n, cu T[i] = i, presupunand ca acest index exista.
7.6 Radacina patrata intreaga a lui n N
este prin definitie acel p N pentru care p
src="http://www.cwu.edu/~andonie/Cartea%20de%20algoritmi/images/cap7/cap7_19.gif" v:shapes="_x0000_i1043"> < p+1.
Presupunand ca nu avem o functie radical, elaborati un algoritm care il gaseste
pe p intr-un timp in O(log n).
Solutie: Se apeleaza patrat(0, n+1, n), patrat fiind functia
function patrat(a, b,
n)
if
a = b-1 then return a
m
(a+b) div 2
if m2 n then
patrat(m, b, n)
else patrat(a, m, n)
7.7 Fie tablourile U[1 .. N]
si V[1 .. M], ordonate crescator. Elaborati un algoritm
cu timpul de executie in Q(N+M), care
sa interclaseze cele doua tablouri. Rezultatul va fi trecut in tabloul T[1 .. N+M].
Solutie: Iata o prima varianta a acestui algoritm:
i, j, k 1
while i N
and j M
do
if
U[i]
V[j] then T[k] U[i]
i
i+1
else T[k]
V[j]
j
j+1
k
k+1
if i > N then
for h j
to M do
T[k] V[h]
k k+1
else for h i
to N do
T[k] U[h]
k k+1
Se poate obtine un algoritm si mai simplu,
daca se presupune ca avem acces la locatiile U[N+1] si V[M+1], pe care le
vom initializa cu o valoare maximala si le vom folosi ca santinele:
i, j 1
U[N+1], V[M+1] +
for k 1 to
N+M do
if
U[i]
<V[j] then T[k] U[i]
i
i+1
else T[k]
V[j]
j j+1
Mai ramane sa analizati eficienta celor doi
algoritmi.
7.8 Modificati algoritmul mergesort astfel incat T sa fie separat nu in doua, ci in trei
parti de marimi cat mai apropiate. Analizati algoritmul obtinut.
7.9 Aratati ca, daca in algoritmul mergesort separam pe T in tabloul U, avand n-1 elemente, si
tabloul V, avand un singur element,
obtinem un algoritm de sortare cu timpul de executie in Q(n2). Acest nou
algoritm seamana cu unul dintre algoritmii deja cunoscuti. Cu care anume?
7.10 Iata si o alta procedura de pivotare:
procedure pivot1(T[i .. j], l)
p T[i]
l i
for k i+1
tojdo
if T[k] p
then l l+1
interschimba
T[k]
si T[l]
interschimba T[i] si T[l]
Argumentati de ce procedura este corecta si
analizati eficienta ei. Comparati numarul maxim de interschimbari din
procedurile pivot si pivot1. Este oare rentabil ca in
algoritmul quicksort sa inlocuim
procedura pivot cu procedura pivot1?
7.11 Argumentati de ce un apel funny-sort(T[1 ..n ]) al
urmatorului algoritm sorteaza corect elementele tabloului T[1 .. n].
procedure funny-sort(T[i .. j])
if
T[i]
> T[ j] then interschimba T[i]
si T[ j]
if
i < j-1 then k ( j-i+1) div 3
funny-sort(T[i .. j-k])
funny-sort(T[i+k .. j])
funny-sort(T[i .. j-k])
Este oare acest simpatic algoritm si
eficient?
7.12 Este un lucru elementar sa gasim un
algoritm care determina minimul dintre elementele unui tablou T[1 .. n] si utilizeaza pentru aceasta n-1 comparatii intre elemente ale tabloului. Mai mult, orice algoritm
care determina prin comparatii minimul elementelor din T efectueaza in mod necesar cel putin n-1 comparatii. In anumite aplicatii, este nevoie sa gasim atat
minimul cat si maximul dintr-o multime de n elemente. Iata un algoritm care determina minimul si maximul
dintre elementele tabloului T[1 .. n]:
procedure fmaxmin1(T[1 .. n], max, min)
max, min T[1]
for i 2 to n do
if max < T[i] then max
T[i]
if min > T[i] then min
T[i]
Acest algoritm efectueaza 2(n-1) comparatii intre
elemente ale lui T. Folosind tehnica
divide et impera, elaborati un algoritm care sa determine minimul si maximul
dintre elementele lui T prin mai
putin de 2(n-1) comparatii. Puteti
presupune ca n este o putere a lui 2.
Solutie: Un apel fmaxmin2(T[1 .. n], max, min) al urmatorului algoritm gaseste
minimul si maximul cerute
procedure fmaxmin2(T[i .. j], max,
min)
case i =
j: max, min T[i]
i = j-1 : if T[i]
< T[ j] then max
T[ j]
min
T[i]
else max
T[i]
min
T[ j]
otherwise : m (i+j)
div 2
fmaxmin2(T[i .. m], smax,
smin)
fmaxmin2(T[m+1 .. j], dmax,
dmin)
max maxim(smax,
dmax)
min minim(smin,
dmin)
Functiile maxim si minim determina,
prin cate o singura comparatie, maximul, respectiv minimul, a doua elemente.
Putem deduce ca atat fmaxmin1, cat si fmaxmin2
necesita un timp in Q(n) pentru a gasi minimul si maximul intr-un
tablou de n elemente. Constanta
multiplicativa asociata timpului in cele doua cazuri difera insa. Notand cu C(n)
numarul de comparatii intre elemente ale tabloului T efectuate de procedura fmaxmin2,
obtinem recurenta
src="http://www.cwu.edu/~andonie/Cartea%20de%20algoritmi/images/cap7/cap7_20.gif" v:shapes="_x0000_i1044">
Consideram n = 2k si folosim
metoda iteratiei:
src="http://www.cwu.edu/~andonie/Cartea%20de%20algoritmi/images/cap7/cap7_21.gif" v:shapes="_x0000_i1045">
Algoritmul fmaxmin2 necesita cu 25% mai putine comparatii decat fmaxmin1. Se poate arata ca nici un
algoritm bazat pe comparatii nu poate folosi mai putin de 3n/2-2 comparatii. In acest sens, fmaxmin2
este, deci, optim.
Este procedura fmaxmin2 mai eficienta si in practica? Nu in mod necesar. Analiza
ar trebui sa considere si numarul de comparatii asupra indicilor de tablou,
precum si timpul necesar pentru rezolvarea apelurilor recursive in fmaxmin2. De asemenea, ar trebui sa
cunoastem si cu cat este mai costisitoare o comparatie de elemente ale lui T, decat o comparatie de indici (adica,
de intregi).
7.13 In ce consta similaritatea algoritmului
selection cu algoritmul i) quicksort si ii) binsearch?
7.14 Generalizati procedura pivot, partitionand tabloul T in trei sectiuni T[1 .. i-1], T[i .. j], T[ j+1 .. n], continand elementele lui T mai mici decat p, egale cu p si
respectiv, mai mari decat p. Valorile
i si j vor fi calculate in procedura de pivotare si vor fi returnate
prin aceasta procedura.
7.15 Folosind ca model versiunea iterativa a
cautarii binare si rezultatul Exercitiului 7.14,
elaborati un algoritm nerecursiv pentru problema selectiei.
7.16 Analizati urmatoarea varianta a
algoritmului quicksort.
procedure quicksort-modificat(T[1 .. n])
if
n = 2 and T[2] < T[1]
then interschimba T[1] si
T[2]
else if n > 2 then
p selection(T, (n+1) div 2)
arrays U[1 .. (n+1) div 2 ], V[1 .. n div 2]
U elementele din T mai mici decat p
si, in
completare, elemente egale cu p
V elementele din T mai mari decat p
si, in
completare, elemente egale cu p
quicksort-modificat(U)
quicksort-modificat(V)
7.17 Daca presupunem ca gasirea medianei
este o operatie elementara, am vazut ca timpul pentru selection, in cazul cel mai nefavorabil, este
tm(n) O(n) + max{tm
(i) | i n/2}
Demonstrati ca tm O(n).
Solutie: Fie n0 si d doua constante astfel incat pentru n > n0 avem
tm (n) dn + max{tm
(i) | i n/2}
Putem considera ca exista constanta reala pozitiva c astfel incat tm(i) ci+c,
pentru 0 i n0.
Prin ipoteza inductiei specificate partial presupunem ca t(i) ci+c,
pentru orice 0 i < n.
Atunci
tm(n) dn+c+cn/2 = cn+c+dn-cn/2 cn+c
deoarece putem sa alegem constanta c suficient de mare, astfel incat
cn/2 dn.
Am aratat deci prin inductie ca, daca c este suficient de mare, atunci
tm(n) cn+c,
pentru orice n 0. Adica, tm O(n).
7.18 Aratati ca luand p T[1] in algoritmul selection si considerand cazul cel mai nefavorabil, determinarea
celui de-al k-lea cel mai
mic element al lui T[1 .. n] necesita un timp de executie in
O(n2).
7.19 Fie U[1 .. n] si V[1 .. n] doua
tablouri de elemente ordonate nedescrescator. Elaborati un algoritm care sa
gaseasca mediana celor 2n elemente intr-un
timp de executie in O(log n).
7.20 Un element x este majoritar in
tabloul T[1 .. n], daca #{i | T[i] = x} > n/2. Elaborati un algoritm liniar care sa determine elementul majoritar
in T (daca un astfel de element
exista).
7.21 Sa presupunem ca Eva a gasit un A‘ pentru care
a = gA‘ mod p = gA mod p
si ca exista un B, astfel incat b = gB mod p. Aratati ca
x‘ = bA‘ mod p = bA mod p = x
chiar daca A‘ A.
7.22 Aratati cum poate fi calculat x15 prin doar cinci inmultiri
(inclusiv ridicari la patrat).
Solutie: x15 = (((x2 )2 )2 )2x-1
7.23 Gasiti un algoritm divide et impera pentru a calcula un termen
oarecare din sirul lui Fibonacci. Folositi proprietatea din Exercitiul 1.7.
Va ajuta aceasta la intelegerea algoritmului fib3 din Sectiunea
1.6.4?
Indicatie: Din Exercitiul 1.7, deducem ca fn =
src="http://www.cwu.edu/~andonie/Cartea%20de%20algoritmi/images/cap7/cap7_22.gif" v:shapes="_x0000_i1046"> , unde
src="http://www.cwu.edu/~andonie/Cartea%20de%20algoritmi/images/cap7/cap7_23.gif" v:shapes="_x0000_i1047"> este elementul
de pe ultima linie si ultima coloana ale matricii M n-1.
Ramane sa elaborati un algoritm similar cu dexpo pentru a afla matricea
putere M n-1. Daca, in loc
de dexpo, folositi ca model algoritmul dexpoiter2, obtineti algoritmul
fib3.
7.24 Demonstrati ca algoritmul lui Strassen
necesita un timp in O(nlg 7), folosind de aceasta data
metoda iteratiei.
Solutie: Fie doua constante pozitive a
si c, astfel incat timpul pentru
algoritmul lui Strassen este
t(n) 7t(n/2) + cn2
pentru n > 2, iar t(n) a
pentru n 2. Obtinem
t(n) cn2(1+7/4+(7/4)2++(7/4)k-2) + a7k-1
cn2(7/4)lg n + a7lg n
= cnlg 4+lg 7-lg 4 + anlg 7 O(nlg 7)
7.25 Cum ati modifica algoritmul lui Strassen pentru a inmulti matrici
de n n elemente, unde n
nu este o putere a lui doi? Aratati ca timpul algoritmului rezultat este tot
in Q(nlg 7).
Indicatie: Il majoram pe n pana la
cea mai mica putere a lui 2, completand corespunzator matricile A si B
cu elemente nule.
7.26 Sa presupunem ca avem o primitiva grafica box(x, y, r),
care deseneaza un patrat 2r 2r
centrat in (x, y), stergand zona din interior. Care este
desenul realizat prin apelul star(a, b, c),
unde star este algoritmul
procedure star(x, y, r)
if r > 0 then star(x-r,
y+r, r div 2)
star(x+r, y+r, r div 2)
star(x-r, y-r, r div 2)
star(x+r, y-r, r div 2)
box(x,
y, r)
Care este rezultatul, daca box(x, y, r) apare inaintea celor patru apeluri recursive? Aratati ca timpul
de executie pentru un apel star(a, b, c) este in Q(c2).
7.27 Demonstrati ca
pentru orice intregi m si n sunt adevarate urmatoarele
proprietati:
i) daca m si n sunt pare, atunci
cmmdc(m, n) = 2cmmdc(m/2, n/2)
ii) daca m este impar si n este par,
atunci cmmdc(m, n) = cmmdc(m, n/2)
iii) daca m si n sunt impare, atunci cmmdc(m,
n) = cmmdc((m-n)/2,
n)
Pe majoritatea calculatoarelor, operatiile
de scadere, testare a paritatii unui intreg si impartire la doi sunt mai rapide
decat calcularea restului impartirii intregi. Elaborati un algoritm divide et
impera pentru a calcula cel mai mare divizor comun a doi intregi, evitand
calcularea restului impartirii intregi. Folositi proprietatile de mai sus.
7.28 Gasiti o structura de date adecvata, pentru a reprezenta numere
intregi mari pe calculator. Pentru un intreg cu n cifre zecimale, numarul
de biti folositi trebuie sa fie in ordinul lui n. Inmultirea si impartirea
cu o putere pozitiva a lui 10 (sau alta baza, daca preferati) trebuie sa poata
fi efectuate intr-un timp liniar. Adunarea si scaderea a doua numere de n,
respectiv m cifre trebuie sa poata fi efectuate intr-un timp in Q(n+m).
Permiteti numerelor sa fie si negative.
7.29 Fie u
si v doi intregi mari cu n, respectiv m cifre. Presupunand ca folositi structura de date din Exercitiul 7.28, aratati ca
algoritmul de inmultire clasica (si cel a la russe) a lui u cu v
necesita un timp in Q(nm).
