PRIMENE RAČUNARA - mart 2003.

1. Opisati algoritam za brisanje elementa sa zadatim ključem iz binarnog stabla pretrage; složenost algoritma treba da bude O(log n) za uravnoteženo binarno stablo sa n elemenata (npr. AVL stablo). Nije neophodno da stablo i nakon operacije brisanja i dalje bude uravnoteženo, ali mora da i dalje bude binarno stablo pretrage. REŠENJE:

1. situacija: uklanjanje čvora koji je list:

ukloni se list

2. situacija: uklanjanje unitrašnjeg čvora C koji ima tačno jednog sina:

ukloni se čvor C

podstablo čiji koren je jedini sin čvora C se podigne za jedan nivo, tako da mu koren bude na mestu uklonjenog čvora C

3. situacija: uklanjanje unutrašnjeg čvora C koji ima oba sina:

pronaći prethodnika čvora C u stablu (tj. pronaći u levom podstablu čvora C najdesniji čvor Cd - počev od korena stabla prelazi se u stablu dokle god je moguće iz tekućeg čvora u njegovog desnog sina, a na kraju tih prelaza je čvor Cd).

ključ čvora Cd se kopira u ključ C, a čvor Cd se uklanja kao što je opisano u situacijama 1 ili 2

Nakon opisanih koraka u sve tri situacije, polazno stablo ostaje binarno stablo pretrage. U prve dve situacije je jasno zašto, dok zaključak važi i u trećoj situcaji, jer ključ Cd na svojoj novoj poziciji je veći od svih čvorova u levom podstablu ispod. U sve tri situacije vreme izvršenja zavisi od položaja čvora koji se uklanja (u najgorem slučaju se traganje završava u listu uravnoteženog stabla pretrage - O(log n)). Sve ostale operacije (uklanjanje čvora, premeštaj podstabala na novu lokaciju) zahteva konstantan broj baznih operacija, pa je složenost u najgorem slučaju proporcionalna visini stabla. Kako polazno stablo je uravnoteženo binarno stablo sa n elemenata, onda je njegova visina proprcionalna sa log_{2} n.

2. Za element z kažemo da je preovladjujući u nizu E ako je broj njegovih pojavljivanja veći od n/2 (gde je n broj elemenata niza E). Konstruisati algoritam linearne složenosti koji za dati niz brojeva odredjuje preovladjujući element ili utvrdjuje da on ne postoji. REŠENJE:

Algoritam Preovlada(X,n)
ulaz: X (*niz od n  elemenata skupa E*)
izlaz: poruka: preovladjuju\'ci element (ako postoji) ili poruka da ne postoji
begin
 K:=X[1]; (* tekuci kandidat za preovladjujuci element*)
 P:=1; (*broj kopija preovladjujuceg *)
  (* 1. prolaz niza radi eliminisanja svih elemenata niza sem jednog
    kao kandidata za preovladjujeceg *)
 for i:=2 to n do
   if P=0 then     (* proglasavanje novog kandidata *)
   begin
      K:=X[i];   (* pamtimo novog kandidata *)
      P:=1;      (* i broj njegovih kopija *)
   end
   else
     if (K=X[i]) then P=P+1  (* uvecanje broja kopija kandidata *)
     else P=P-1;  (* smanjuje se broj kopija za svaki element razlicit od                         tekuceg kandidata *)
  (* provera kandidata *)
 if P=0 then write ('Ne postoji'); (* ako je broj kopija kandidata =0, onda                                       ne postoji preovladjuci element *)
   else

    begin
      brojac=0;  (* brojac pojava potencijalnog kandidata *)
     (* 2. prolaz i  provera da li potencijalni kandidat ima svojstvo         preovladjujuceg *)
       for i=1 to n do
          if (X[i]=K) then brojac=brojac+1;
       if brojac>n/2 then write ('Postoji preovladjujuci element', K);
       else write ('Ne postoji');
    end

end.

Na složenost rešenja utiču elementarne operacije u oba prolaza kroz niz (eliminacija potencijalnih kandidata sem jednog i provera da li kandidat ima svojstvo preovladjuceg elementa s obzirom na broj pojava). U oba prolaza se prelazi članovi niza radi ažuriranja vrednosti za P, K, brojac, pa je ukupna složenost O(n).

3. Dat je aciklički usmereni graf G = (V, E). Konstruisati algoritam linearne složenosti koji utvrdjuje da li graf G sadrži neki Hamiltonov put. Prost put je Hamiltonov ako sadrži sve čvorove grafa.

4. Dat je n-dimenzioni niz A (n = 2^{k}) i sistem sa n procesora koji funcionišu po modelu EREW. Opisati algoritam reda O(log n) koji u i-ti element niza (1 < i ≤ n) smešta vrednost A[1] + i. REŠENJE: U prvom koraku jedan procesor upisuje vrednost A[1] + 2 u lokaciju A[2]. U drugom koraku učestvuju dva procesora i prvi upisuje vrednost A[1] + 3 u lokaciju A[3], a drugi vrednost A[2] + 2 u A[4]. ... U k-tom koraku učestvuje 2^{k−1} procesora i prvi procesor upisuje vrednost A[1] + 2^{k−1} + 1 u lokaciju A[1 + 2^{k−1}], a j-ti procesor (2 ≤ j ≤ 2^{k−1}) upisuje vrednost A[j] + 2^{k−1} u lokaciju A[j + 2^{k−1}]. U opisanim koracima nikoja dva procesora ne pristupaju istoj memorijskoj lokaciji i algoritam se izvršava u modeli EREW. Za niz od n = 2^{k} elemenata ovakvih koraka ima k = log_{2} n, pa je složenost ovog algoritma O(log n).