јлгоритмы


PAIE?KA PAPRASTAME S?RA?E
1.1. Nuosekli paie?ka
Tegu ?ra?ai i?d?styti atsitiktinai kaip buvo ?ra?yti. Reikia  surasti  duot?
?ra??  pagal  rakt?.  Nuosekliai  ie?kant  reikia  per?i?r?ti  visus  ?ra?us
nuosekliai.Vid.per?i?r?? ?ra?? sk. ie?kant yra  Lap  =L/2.  Jei  ?ra?o  n?ra
teks per?i?r?ti visus ?ra?us L. Tarkim ie?komo ?ra?o  su  tikimybe  p0  n?ra
s?ra?e, tada vid. per?i?r?t? ?ra?? sk. Lap=L*p0+(i(1L  (i*pi  );  pi=1-p0/L.
Ie?kant  ?ra?o  sutvarkytame  faile(?ra?ai  i?d?styti  pagal  rakt?)  reikia
per?i?r?ti i? eil?s, tod?l vid. per?i?r?t? ?ra?? sk. tas pats: Lsp=L/2.  Jei
ie?komo ?ra?o n?ra, tai paie?ka nutraukiama kai eilinis raktas bus  didesnis
u? u?duot?. Atliekant k ?ra?? paie?k? nesutvarkytame faile  vid.  per?i?r?t?
?ra?? sk. Lkap = k * L / 2.
1.2. Paie?ka interpoliavimas
Jei s?ra?ai sur??iuoti ir ?inomas pirmo  ?ra?o  raktas  K(1)  ir  paskutinio
K(n)   tai   galima   apskai?iuoti   p=X-K(1)/K(n)-K(1).   X-ie?komo   ?ra?o
raktas.Paie?k? pradedam nuo ?ra?o kurio numeris p*n.
1.3. Binarin? paie?ka
Naudojama sur??iuotame masyve.  Jis  dalinamas  pusiau  ir  ie?komas  raktas
lyginamas su vidurio raktu ir t.t.. Idealus masyvo dydis 2n-1.Jei 31  ?ra?as
reik?s 5 ?ingsni?, kad surasti ?ra?? 31(25-1. Bendru atveju 2n-1-1< N (  2n-
1. Kai ?ra?? sk. bet koks, tai naudojami tokie alg.:

1) Pos?ra?io rib? nustatymo metodas. I?kiriame 2  markerius:  V  vir?utiniam
adresui ir A apatiniam adresui. Vidurinio ?ra?o adresas F((  (V+A)  /  2  (.
Ie?komas ?ra?o raktas k palyginamas su F. Jei  k(Fk,  tai  ?ra?as  surastas,
jei k Fk, tai imam apatin? dal?, tada V(F+1, o A i?lieka  tas  pats  ir  t.t..
Toks dalinimas  atliekamas  tol,  kol  nepasidaro  A(V.  Rekurentin?  lygtis
apra?anti max palyginim? sk. binarin?je paie?koje yra:
 f(n)({1, n(1 f( ( n/2 ( )+1, n>1.  Sprend?iant  rekurentin?  formul?  galim
u?ra?yti: f(n) ( f( (n/2( ) + 1 (        f( (n/21( ) + 1(( f( (n/22( )+1)  +
1 ( f( (n/22( )+2 (...( f( (n/2i( ) + i, kol
( n/2i  ((1;  i((logn(.  f(n)((logn(+1  arba  f(n)  (  (log  (n+1)(  .  Vid.
palyginim? sk. ideliu atveju kai n ( 2k-1:
f(n)(1* 1/n + 2*2/n + 3*4/n +...+  ((log n( + 1)*2k-1/n  (  1/n  *  (i(1(log
n(+1 (i * 2i-1).  2k-1-1F1,  tai  ie?komas
?ra?as yra antroje dalyje, kuri ma?esn? u? pirm?j?.
2r-1-12.  Tas  dvi  dalis  galim  dalinti  dar
pusiau. T(n) ( T(2k) ( 2T(2k-1)+2 ( 2(2T(2k-2) + 2) +2 ( 22T(2k-2) +  22  +2
( 2k-1T(2) + 2k-1 +...+ 23 +22 +2 ( 2k-1 + 2k-1 + 2k-2 + ... + 23 +22  +2  (
n+2k-1-2 ( n+n/2-2 ( 3n/2-2. Atliekant toki? skaidymo  proced?r?,  algoritmo
sud?tingumas suma??ja.

Rekurentini? lyg?i? sprendimas
T(n) ( {b, n(1aT(n/c) + bi, n>1
 a,b,c-teigiamos const.n(ck; k(log cn.
T(1) ( b
T(c) ( aT(1) + bc ( ab + bc ( (1+a/c);
T(c2) ( aT(c) + bc2 ( a(ab + bc) + bc2 ( a2b + abc +  bc2  (  bc2(1+  a/c  +
a2/c2) ......
T(n) ( T(ck)  (  aT(ck-1)  +  bck  (  bck(1+a/c+a2/c2+...+ak/ck)  .  T(n)  (
bn(i(0logcn (a/c)i. Jei ac, turim  did?jan?i?  geometrin?  progresij?.  Tuomet  T(n)
greitai  did?ja  did?jant  n,  tai  eksponentinio  sud?tingumo   algoritmas.
U?davin? suskaid?ius ? 4 dalis  ir  toki?  dali?  pa?mus  4  Ц  ias:  a=c=4,
gauname ((nlog4n), log2n > log4n.  Kas  bus,  kai  n?ck?  I?vestos  formul?s
netinka, bet pa?mus atvej?, kai nТ=ck > n, i?vados galioja.  U?davinys  gali
b?ti sprend?iamas su rekursija arba be jos,  ta?iau  u?davinio  sud?tingumas
nepasikei?ia. Su rekursija algoritmas sprend?iamas ?iek tiek ilgiau.
T Apie rekurentin?s lygties tipo  T(n)=aT(n\c)+f(n),  kur  a?1,  c?1,  f(n)-
teigiama f-ja.  1) Jei f(n)= ((n(logca)-()  ,tai  T(n)=  ((nlogca).  2)  Jei
f(n)= ((nlogca) ,tai T(n)= ((nlogca . log  n.  3)  Jei  f(n)=  ((n(logca)+()
,tai T(n)= ((f(n)), jei af(n\c)?bf(n) (b>1 dideliems n).

Balansavimas (skaidymas ? vienodas dalis). Reikia sur??iuoti n ilgio  masyv?
did?jimo tvarka. 1.surandam min, kur? sukei?iam su pirmu,  po  to  i?  (n-1)
elemento surandam min ir sukei?iam su  antru  ir  t.t..  Rekursyvin?  lygtis
apra?anti palyginim? sk.: T(n) ( {0, n(1T(n-1)+n-1, n>1 ;
 T(n) ( n(n-1)/2, o  algoritmo  sud?tingumas  ((n2).  ?ia  skaldymas  ?  dvi
nelygias dalis: ? vieno elemento ir (n-1).2. Gaunamas  suskald?ius  u?davin?
? dvi lygias dalis ( n/2. Tarkim, kad n ( 2k. Viena dalis nuo x1 iki xn/2  ,
o kita nuo xn/2+1 iki xn. ?ias dalis  sur??iuojam  ir  sujungiam  palyginant
minimalius  elementus.  Sujungimui  reiks  maksimum  n-1  palyginim?.   Tok?
skaidym? galima rekursyviai t?sti toliau, kol lieka dalyse  po  1  element?.
Rekursyvin? lygtis apra?anti tok? algoritm? yra:
 T(n) ( {0, n(1 2T(n/2) + n - 1, n>1.
 ?io algoritmo sud?tingumas (( n log n).

Dinaminis programavimas.
Kartais galima efektyvius algoritmus gauti naudojant dinamin?  programavim?.
?iuo b?du reik?t? skai?iuoti visus dalinius u?davnius, bet  sprend?iami  nuo
ma?? prie dideli?. Atsakymai prisimenami lentel?je ir  u?daviniai  jungiami,
kad b?t? i?spr?stas visas u?davinys ir gautas optimumas. Pvz. sudauginant  n
matric? yra labai svarbus daugybos eili?kumas, kuris nulemia bendr?  veiksm?
skai?i?.  Pa?ymim  mi  j   minimalus   veiksm?   sk.   dauginant   matricas:
Mi*Mi+1*...*Mj, kur 1 ( i < j ( n. Kai M ( M1*M2*...*Mn, tai  j?  mati?kumas
yra r0*r1*r2*...*rn.
  mi  j  (  {0,   i(j   MIN(   mik   +   mk+1,   j   +   ri-1   rk   rj   ),
              j > i, i ( k < j (1).
 M` (Mi*Mi+1*...*Mk, [ri-1*rk]. Min vei-ksm? sk. mi,k.
 M``(Mk+1 *Mk+2 *... * Mj, [rk*rj].
 Atliekant ?i? daugyb? min veiksm? sk. mk+1, j, o  sudauginant  M`  su  M``,
min veiksm? sk.  ri-1 rk rj. Tai atliekam tol kol  negaunam  m1n.1-a  lygtis
ya dinaminio programavimo rekurentin? lygtis.  mi,j  reik?m?s  skai?iuojamos
tvarka, kai did?ja indeks? sk. I? prad?i? skai?iuojam mi,i(  0  (visiem  i),
toliau mi, i+1, po to mi, i+2, kol neprieinam m1n.


R??IAVIMO ALGORITMAI

K-ma?i? korte?? r??iavimas
Tegul mes turime sek? A1 A2 ... An k-ma?i?  korte??,  t.y.,  A  erdvinis  Ai
elementas, sudarytas i? ai1 ai2 ... aik.Reikia ?i? sek?  r??iuoti  taip:  B1
B2 ... Bn, kad visiem i Bi ( Bi+1. R??iavimas atliekamas k  kart?  pereinant
per duot? sek?. Pirm? kart? atliekamas r??iavimas  pagal  k-?j?  komponent?.
Antr? kart? pagal (k-1) komponent?  ir  t.t.  Pr?jus  pagal  i-?j?,  tur?sim
s?ru?iuot?  sek?.  Kiekviena  skiltis  ai  j  yra  nuo  0  iki  m-1.  Reikia
organizuoti m pagalbini? eili? Q(j), kur j ( 0,...,m-1,  kurios  i?  prad?i?
turi b?ti tu??ios. Duomenis A1 A2 ... An i? prad?i? sura?om ?  s?ra??  EIL?.
Paimam eilin? korte?? Ai i? EIL?S ir patalpinam ? pagalbin? eil? Q(j)  pagal
analizuojamos  komponent?s  reik?m?.  Taip  darom  tol,  kol   bendra   EIL?
i?tu?t?ja. Visi korte?ai atsiduria pagalbin?se eil?se. Po to jie  suduriami:
Q(0) Q(1)...Q(m-1) ir jie sudaro vien? bendr? eil? EIL?.  Kai  praeinam  pro
visas komponentes, tai  EIL?  bus  sur??iuota.  Algoritmo  sud?tingumas  yra
tiesinis ([(n+m)/k]. Naudoti ?? metod? neverta, kai n yra ma?as.

Nevienodo ilgio korte?? r??iavimas
Kad suvienodinti korte?? ilgius galima  priekyje  prira?yti  nulius,  ta?iau
tai ne efektyvu, nes bus bereikaling? daug per?i?r?jim?. Tuomet tegul  lmax-
korte?? maksimalus ilgis,  tai  reikia  i?  prad?i?  sur??iuoti  maksimalaus
ilgio korte?us pagal l max paskutin? komponent?. Reik?s lmax kart?  r??iuoti
visus korte?us.Antr? kart? reikia r??iuoti korte?us, kuri? ilgis lmax -1  ir
jau sur??iuotus pagal paskutin? komponent?, kuri? ilgis lmax.  Ir  paskutin?
kart? lmax per?jus per vis? s?ra??,  bendram  s?ra?e  bus  sur??iuota  seka.
Pastabos:  1.  Prie?  naudojant  ??  algoritm?,  visi  korte?ai  turi   b?ti
i?skirstyti  pagal  ilgius.  Tam  formuojami  s?ra?ai  ILGIS(l),  kur  l   (
1,...,lmax, kuriuose sura?yti atitinkamo ilgio korte?ai.  Pirmame  ?ingsnyje
r??iuojamas tik s?ra?as ILGIS(lmax) pagal paskutin?  komponent?.  2.  Be  to
matom, kad pra?jus kart? pro vien?  komponent?  gali  b?ti  daug  pagalbini?
eili? Q(i) (kur i ( 0,1,...,m-1) tu??ios.  Ne?i?rint  to  jas  visas  reikia
jungti ? bendr? s?ra??, tod?l naudinga  b?t?  i?  prad?i?  nustatyti  kurios
pagalbin?s eil?s bus netu??ios ir tik jas jungti ? vien? bendr? s?ra??.

R??iavimas lyginant elementus
УBurbuliukoФ metodas. Paprastai elementai r??iuojami pagal raktin? ?od?.
Tarkim turim K1..K16 element? ir lyginame K1 >K2. Jeigu  daugiau  sukei?iam
vietom. Jeigu ne nieko nedarom ir t.t. Paskutinis palyginimas bus Km >  Kn.
Po 1 iteracijos did?iausias skai?ius atsiranda pabaigoje. Sekanti iteracija
vyksta su n-1 elementu, nes paskutinio neimame ir t.t.
Pirmoje iteracijoje bus (n-1) palyginim?.  Antroje  iteracijoje  (n-2),  i-
tojoje iteracijoje (n-i).
Tuomet bendras palyginim? skai?ius bus
[pic]
Kadangi ne visuomet elementai sukei?iami, tuomet jeigu i?r??iuota seka  bus
0 pakitim?, o  atvirk??iai  i?r??iuota  seka  -  n(n-1)/2  pakeitim?.  Tada
vidutinis pakeitim? sk. bus n(n-1)/4.
Jeigu yra n element? seka, tai i? jos  gali  b?ti  padaryti  n!  sek?.  Mes
laikome kad bet kuri seka gali pasitaikyti su vienoda tikimybe 1/n!.
Kiekvienai sekai galima para?yti inversi?k? sek?.  Jeigu  turime  tokias  2
sekas, ir jas sur??iuosime,  tai  sumalinis  pakeitim?  sk.  bus  n(n-1)/4.
Algoritmo sud?tingumas ((n2).
Iterpimo metodas.
?ia eilinis elementas yra ?terpiamas ? jau sur??iuot? elemet?  sek?.  Tegul
turime n element? i? viso ir turime jau i sur??iuot? element?. Mums  reikia
?terpti i+1 element? Ki+1. Ki+1 atsidurs tarp Kj < Ki+1  <  Kj+1  element?.
?statant i+1  element?  mums  reik?s  max  palyginim?  (su  1,  su  2Е).Max
palyginim? sk. b?t?:
[pic]Pagal tai ir algoritmo sud?tingumas bus  ((n2).Vidutini?kai bus ma?iau
palyginim?.?iuo b?du r??iuojant masyvus (paprastus) patogiau prad?ti elemt?
lyginim? nuo sur??iuotos sekos pabaigos. Tai yra nuo i-tojo elemento.
Panagrin?kime koks ?iame  algoritme  yra  vidutinis  palyginim?  sk.  Tegul
turime i  sur??iuot?  elemt?  ir  reikia  ?statyti  I+1  element?.  Pirmiau
lyginsime su 1 elememtu. Yra i+1 pozicijos, ? kurias  galima  ?statyti  i+1
element? ir priekyje ir gale.  Laikome,  kad  i+1  elementas  ?  bet  kuri?
pozicij? gali patekti su vienoda tikimybe 1/(i + 1).  Vidutinis  palyginim?
sk. ?statant element? bus:
[pic]jei patenka                          ? paskutin?
prie? pirm?j?                           pozicij?
  element?                               (gale)
=1/(i+1)(1+2+Е+i+i) = 1/(i+1)*((i+1)/i ) /2 + i / ( i + 1 ) = i / 2 + i / (
i + 1 )
Tiek  pagal  max,tiek  pagal  vidutin?  palyginim?  skai?i?  ?io  algoritmo
sud?tingumas yra ((n2)

Ekspermentinis statistinis algoritm?  tyrima.s  ?iuo  metodu  pvz.  tiriant
r??iavimo algoritmus mums  reikia  para?yti  atitinkam?  program?,  paiimti
atsitiktin? sek? i? n duomen?  ir  atlikti  skai?iavimus,  pvz.:  fikstuoti
laik? t1, po to paimame kit? sek? ir gauname laik? t2 po  to  paimame  kit?
sek? taip pat i? n duomen? ir gauname laik? t3 ir tokius bandymus kartojame
k kart?. Gauname atsitiktini? dyd?i? imt? t1, t2, Е. tk. Vidurkis bus  (  =
1/K(i(1K (ti), vidurkis - atsitiktinis dydis.
Dirpersija bus : S2(t)=[pic]i-t)2= =[pic]ti2-2(t ti +(t2) = =[pic] ti2-
2t[pic]ti+K(t2]= =[pic][pic]ti2-2([pic][pic]ti)* *[pic]ti + K/K2
([pic]ti)2] = [pic]* *[ [pic]ti2 - [pic]( [pic]ti)2]
?i  dispersijos  fomul?  patogesn?  ma?ininiuose  skai?iavimuose,  nes   su
kiekvienu nauju atsitiktiniu dyd?iu ti mes kaupiame tik dvi sumas : (ti  ir
(ti2.(t - atvirk?tinis dydis ir jis vertina tam tikr?  matematin?  vilt?.(t
dispersija yra  tokia:  D((t  )=  D  [[pic][pic]ti]  =  1/K2[pic]  D(ti)  =
1/K*D(t);  D   -   tikroji   dispersija;S-?vertinimas.S2((t)=S2(t)/K   arba
i?traukus ?akn?:  S(t)  =  S(t)/[pic];  |(t  -  m|<(  -  t.y.  artiname  ir
reikalaujame, kad jos skirtus? (. Kad i?rai?ka tur?t? prasm?, mes para?ome:
P{|(t - m |<(}=p.Padalinkime abi puses  i? vidutin?s kvadratin?s paklaidos.
P {|(t - m |/S((t)<( / S((t)}=p. Pa?y-m?kime tp = (/ S((t) (2). m- vidurkio
matematin? viltis.(t - m ?vertinimas tada i? formul?s (2) i?eina, kad  (  =
tp*S((t) = tp[pic]. Galim para?yti : t-(< m< t+(, tada t - tp[pic]< m <(t +
tp[pic]t.y. tikroji matematin? viltis su tikimybe p rasis ?iame  intervale,
o su tikimybe 1 i?eis i? ?io intervalo. Turime  taip  vadinam?  intervalin?
?vertinim?.

Dviej? program? ekspermentinis-  statistinis  tyrimas.  Tegul  mes  atlikom
skai?iavimus pagal vien? program? ir fiksavom  laikus  t1i(i=1Е.K).  Galima
paskai?iuoti vidurk?  (t1  ,  dispersij?  S2(t1)  ir  t1+-  (1(intervalinis
?vertinimas). T? pat? atlie-kam su kita programa(t2, S2(t2), (t2 +- (2
Jei palyginsim tik (t1 ir (t2 tas dar nerodo, kad vienas i?  ?i?  algoritm?
yra geresnis, nes (t1 ir (t2  -  atsitiktiniai  dyd?iai,  tod?l  palyginim?
rezultatas taip pat gali b?ti atsitiktinis. Geriau lyginti (t1 ( (1 ir  (t2
( (2. Jei jie nepersidengia, tai yra pagrindo teigti,  kad  viena  programa
yra geresn? u? kit?.Arba galima lyginti ir taip:
1.paskai?iuojam (t=t1-t2 ; D(((t ) = D((t1)+D((t2); Jeigu ?ie  atsitiktiniai
dy-d?iai nepriklausomi.
S2(((t  )   =   S2((t1   )   +    S2((t2)   =   S2(t1)/K   +   S2(t2)/K   ;
S(((t)=(((S2(t1)+S2(t2))/K);
((t - tpS(((t ) 0,  tai   ((t  =  (t1-  (t2,  S2((t)(S2((t1)+  S2((t2)-2(M12  t.y.
dispersija  ma?esn?  nei  nepriklausom?  dyd?i?  atvju.  S2(((t)(  S2(t1)/K+
S2(t2)/K -  2K12S((t1)  *  S((t2)=  S2(t1)/K+  S2(t2)/K  -  2M12/S(t1)S(t2)*
S(t1)/(k  *  S(t2)/(K  =  S2(t1)/K+  S2(t2)/K  -  2M12/K  t.y.  ir  vidurkio
dispersija  yra  ma?esn?,  nes  atsiima  2M12/K.  Atitinkamai   intervalinis
?vertinimas: ((t - tpS(((t)  A(J) tai sukei?iame juos vietomis  ir  I(I+1
ir t.t.. Taip palyginus su visais elementais, gausime,  kad  kair?je  pus?je
elemento su kuriuo mes lyginome bus elementai  ma?esni  u?  j?,  o  de?in?je
didesni, t.y. suskald?m sek? jo at?vilgiu.  Elementas  pagal  kur?  atlikome
palyginimus  yra  pirmasis  ir  vadinamas   generaliniu.   ?ia   generalinis
elementas visada buvo pirmas, ta?iau tai neb?tina. Gaima  paimti  bet  kur?.
Generaliniai elementai gali b?ti parenkami ?vairiai:  pirmas,  atsitiktinis,
mediana  (vidurinis).  Skaidyti  pagal  median?  geriausia.  Galima   paimti
nedideli? imt? i? keli? sekos element?  ir  surasti  median?.  Imant  visada
pirm? element?, blogiausias atvejis gaunasi, kada seka yra sur??iuota.  Tada
seka suskaldoma ? vien? element?  ir  vis?  likusi?.  Gausis  taip  kaip  ir
kituose algoritmuose. Tuo atveju algoritmo  sud?-tingumas  ((n2),  o  visais
kitais atvejais ?ymiai geriau. ?is algoritmas gerai veikia didel?m sekom,  o
taip pat reikia tinkamai parinkti  generalin?  element?.  Vid.  veiksm?  sk.
yra:
[pic]
c-koef.,  cn-veiksm?  sk.  atliekant  pirm?  suskaldym?.  Generalinis  elem.
atsiranda i-ojoje vietoje ir gaunam dvi sekas (i-1) ir  (n-i).  Veiksm?  sk.
skaldant sek? (i-1) yra (i(1n f(i-1), o sek? (n-i) yra (i(1n  f(n-i).   1/n-
i su vienoda tikimybe gali atsirasti bet kurioje vietoje.
(i(1n [f(i-1)+ f(n-i)](f(0)+ f(n-1)+ f(1)+ f(n-2)+...+  f(n-2)+  f(1)+  f(n-
1)+f(0)( 2 f(0)+2f(1)+...+2f(n-2)+2f(n-1)(2(i(1nf(i)
f(n)(cn + 2/n(i(0n-1 f(i), kai n>1
f(0)(f(1)(b
f(2)(2c+2/2[f(0)+f(1)](2c+2b(k
f(3)(3c+2/3[f(0)+f(1)+f(2)](3c+2/3[2b+2c+2b](3c+8/3b+4/3c((8b+13c)/3.
?rodyta, kad  visada  galioja  lygyb?  f(n)  <  kn  ln  n.  Tod?l  QUICKSORT
algoritmo vidutinis sud?tingumas yra ((n ln n). ?ia  nevertinta,  kad  ma?os
sekos gali b?ti r??iuojamos kitu b?du, kas dar pagreitina ?? algoritm?.

Optimalus r??iavimas. Jei yra n element?, tai variant?  i?  viso  gali  b?ti
n!. n=3, 3!=6 Minimalus palyginim? sk. blogiausiu atveju  =  3.  Ir  laikom,
kad ?i schema optimali. Tegul S(n) -  minimalus  palyginim?  sk.  blogiausiu
atveju, r??iuojant n  element?:  S(3)=3  Pilname  k-tojo  lygio  binariniame
medyje, paskutiniame lygyje yra 2K mazg?. K=S(n).
n! =< 2 S(n), tada S(n) >= (log n!( =n log n - n/ln2+1/2 log n + (
  ( - paklaida. (Stirlingo formul?)
Minimalus palyginim? sk. blogiausiu atveju yra apie nlogn . Palyginus
(log n!( su f(n) = n (log n( -  2  (log  n(  +  1  pasirodo,  kad  suliejimo
metodas pagal minimal? palyginim? sk. n?ra minimalus.

I?RINKIMAS
Maksimalaus elemento i?rinkimas  i?  n  element?  sekosRadus  max  element?,
reikia atlikti  n-1  palyginim?.  O  kiek  reikia  priskyrim??  Jei  seka  -
ma??janti, tai reik?s 1 prisky-rimo. Jei seka  -  did?janti,  tai  reik?s  n
priskyrim?. O koks  vidutinis  priskyrim?  sk,  jei  bet  kokia  seka  i?  n
element? vienodai galima?
Hn=1 +[pic] P[ai > aj] ( 1 = 1+ [pic]1/2 ( 1 = [pic][pic] = ln n +  (  +1/2n
+ (
?i eilut?  diverguojanti,  t.y.  did?jant  n,  jos  reik?m?  did?ja.(Eulerio
formul?) ?ia ((0,577; (- paklaida.

Sekan?io did?iausio elemento radimas (2-? max radimas). Norint  surasti  max
element?, reikia n-1 palyginim?. Po to j? pa?alinam ir surandame  kit?  max.
Tam reikia n-2 palyginim?. Tod?l i? viso palyginim? sk: 2n-3.  ??  algoritm?
galima pagerinti suskald?ius n element? ? 2 dalis: (n/2(  ir  (n/2(  Ie?kome
max element?: I dalyje max el. surasti reik?s  (n/2(  -  1  palygini-m?,  II
dalyje - (n/2( palyginim?. Po to juos reik?s tarpusavyje palyginti. I? viso
reik?s [pic] palyginim?. Paskutiniame lygyje pralai-m?jus?  element?  reik?s
palyginti su pra-laim?jusiais  elementais,  lyginant  su  mak-simaliu.  Taip
rasim kit? max  element?.  Reikia  [pic]  palyginim?.  Toliau  galima  kelti
klausim?, ar negalima ??jimo sek? padalinti  ?  4,  8  ir  t.t.  dali?,  kol
neprieisim algoritmo, kuris atitinka  piramidin?  r??iavim?.  Lai  I  faz?je
lyginame po 2 elementus: n=8
                                     a1
                                  a1    a6
                  a1           a3           a6          a7
                a1    a2     a3   a4    a5    a6    a7    a8
Ie?kant kito max elemento, reikia a6 ly-ginti  su  pralaim?jusiais,  randant
a1

Jei a6 > a3, tai reikia palyginti ir ar a6 > a2
Jei a6 < a3, tai reikia palyginti ir ar a3 > a6
Radom max per 2 palyginimus. Pirami-d?je radom per n-1 palyginim?.  Tai  yra
sekantis randamas per (log n(  -1  palygi-nim?.  Gauname,  kad  ?iuo  metodu
palygi-nim? sk. yra optimalus: n + (log n( - 2 .

Geriausio (max) ir blogiausio (min) elemento i?rinkimas
Galima si?lyti suskaidyti sek? n ? 2 dalis ir sura?yti ?iose dalyse  max  ir
min elementus. Palyginus max-ius elementus gaunamas max-is  elementas,  min-
ius -min-is. Rekursyviai galima suskaidyti iki 1,2  element?.  Palyginant  2
elementus tarpusavyje i? karto gauname max  ir  min  elementus.  Rekurentin?
lygtis, apra?anti tok? akgoritm?:
f(n)=[pic]
Bendras ?ios srities sprendinys:
|[pic|(n-2(log  |
|]   |n()/2, kai|
|    |n =<3 *   |
|    |2(log n(-1|
|    |          |
|    |(2(log    |
|    |n(+1-n)/2,|
|    |kitais    |
|    |atvejais  |


k-ojo didesnio elem. I?rinkimas[be ru?iavimo]
1.Alg. - i?rinkimas su randomizacija: pa?mus ?-aj?  elem  ir  elementu  seka
suskaidoma ? 2  dalis:  (i-1)-  S1,  i,  (n-i)-S3.  Jeigu  pataikeme  paimti
skaidymui elem. k-uoju, tai jis atsiduria  savo  vietoje  ir  algor.  baigia
darba. Jei nepataikeme tai tolimesniam skaidymui imame poaib?,  kuriame  yra
ie?komas elem. ir j? skaidome toliau: Jei i>k, tai imame S1, kuriame yra (i-
1) ele-t?. Jei i( . i1 ,i2 ...ik = n. P(i1 ,i2 ..ik ).
Nagrin?jome ?io bendro u?davinio kelis atvejus:
1.ma?iausio elem, radimas P(1,n-1)=n-1. (palyginim? sk ie?kant min =n-1).
2.1-mo ir 2-ro ma?iausio elem, radimas  P(1,1,n-2)=n+(log n(-2.
3.ma?. ir did?. elem, radimas
  P(1, n-2, 1)=(3/2  n(-2
4.k-tojo didesnio elem, radimas
P(k-1, 1,n-k) = (( n)
5.Dviej? ma?iausi?: P(2,n-2)=n+(log(n-1)(-2
6. trij? ma?iausi?: P(3,n-3)=n+2(log n(-(3|2|1|
?vairiais atvejais priklausomai nuo n.
Galima kelti tokius u?davinius:
a.surasti k ma?iausi? elem, P(k,n-k).
b. surasti k-?j? element? P(k-1,1,n-k).
c. surasti k element? i? eil?s P(1,1,1,..,1,n-k)
P(1,1,1,..,1,n-k)> P(k-1,1,n-k)> P( k,n-k).

Veiksmai su aibemis(DS po?iuriu)
U?davinius galima suvesti ?  veiksmus  su  aib?mis.  I?analizuojam  ?vairias
Duomen? Strukt?ras ir pasirenkam labiausiai  tinkam?.  Gero  alg.  Suk?rimas
neatski-riamas nuo tinkamos DS pasirinkimo. Pagr. mat. veiksmai  su  aib?mis
b?dingi informacin?s paie?kos u?daviniams:
1:PRIKLAUSYTI (a, S). Nustato ar elem.a priklauso aibei S. Jei  a  priklauso
S, tada TAIP, prie?ingu atveju NE..
2:?STATYTI (a,S).?stato elem, a ? S. Gaunasi aib? S ir elem, a t.y. S({a}.
3:PA?ALINTI (a,S). Pa?alina a elem, i? aib?s S t.y. aib? S pakei?iama  ?  S-
{a}.
4. APJUNGTI (S1,S2,S3). Atlieka tok? veiksm?: S3= S1(S2.
5:RASTI (a). Reikia rasti aib?, kurioje duotu momentu randasi elem,  a.  Jei
rast? dvejose aib?se, tada veksmas nenustatytas.
6:SUSKALDYTI (a,S) ?ia aib?selem, u?duoti santykiu  <=.?is  veiksmas  atliks
aib?s S suskaldym? ? S1={b|b<=a, b(S} ir S2={b|b>a}
7:MIN (S) Suranda ma?iausi? aib?s S elem.
?iuos veiksmus reik atlikti tam tikra seka duomen? baz?je.Mus domina  laikas
atliekant veiksm? sek? priklausomai DB dyd?io ir nuo  veiksm?  sekos  ilgio.
?is  laikinas  sud?tingumas  paprastai  tikrinamas  blogiausiu   atveju   ir
vidutini?ku.
PVZ.
Kraskalo alogoritmas.
Surasti ekonomin? med? neorentuotam  grafe.  Yra  grafas  G  (V,  E).V-vir?.
aib?,E-briaun? aib. Kieikviena briauna i? E turi  svor?  c.  Reikia  surasti
graf?-med? G(V,T). T-E poaibis i?. Taip kad ( i (T ci =>min.
Medis grafas be ciklo. Jei medyje S(V,T) pridesime koki? nors  briaun?,  tai
susidarys vienas ciklas. Grafo G mi?ku  vadiname  neorentuot?  med?i?  aib?:
{V1.,T1}, {V2.,T2},...,{Vk.,Tk} . V1 ,V2,  ..  Vk-suskaldyta  aib?  V.  V=V1
(V2,(..(Vk; V  i  (Vj  =(.  Atitinkamai  T1,T2,ЕTk  yra  aib?s  E  poaibiai.
Kraskalo alg sako: reikia med?ius  jungti  minimalaus  ilgio  briaunomis  ir
apjungti sujungtus med?ius  ?  vien?.  Taip  atliekama  tol,  kol  nesigauna
vienas ekonominis medis.
////////// P R O G R A M A--------------
(1 ir (2 yra med?iai mi?ke.  ?iame  algo-me  E  -  grafo  briaun?  aib?.  T-
ekonominio med?io briaun? aib?. VS - grafo mi?ko med?iai kurie apjungiami  ?
ekonomin? med?:
I? prad?i? VS- atskiras  grafo  G  vir??nei  kaip  vieno  elem,  aibei(viena
vir??n?-vienas mi?ko medis).
Kadangi aib?je E yra  sura?ytos  briaunos,kurias  rekia  imti  su  minimaliu
svoriu. Tai galb?t naudinga atlikti j? sur??iavim?. Tai  gali  b?ti  paimtas
alg, kurio sudetingumas ((eloge).e-briaun? sk.
Tuomet 3-?io operatoriaus sudetingumas proporcingas  vir??ni?  sk.  n  ((n).
Laikas reikalingas surasti aibei (1 ir (2 ?kurias ?eina vir??nes V ir  (  ir
j? sujungimas, jei priklauso skirtingoms aib?ms yra beveik tu??ias:  ((n)  .
O jei tiksliau t.y. ((n G(n)), kur G(n) - atvirk?tin? f-jai F(n) =2F(n-1)
Jeigu naudosime s?ra?? strukt?r?, tai (7,8) ?ios  dalies  alg.  sudetingumas
((  MAX(e,n  log  n)).  Tod?l  matom,  kad   visumoje   Kraskalo   algoritmo
sud?tingumas yra ((e log e), kur? nulemia r??iavimas.

Paskirstymo metodas (he?iravimo)
Mes ?ia nagrin?sime  duomen?  strukt?r?  besikei?ian?ioje  aib?je  S.  Nauji
elementai bus ?statomi, seni pa?alinami ir karts nuo karto  reik?s  atsakyti
? klausim?: ar priklauso duotu momentu  konkretus  elementas  aibei  S.  Bus
reikalingi     tokie     veiksmai:     PRIKLAUSYTI(a,s),     ?STA-TYTI(a,s),
PA?ALINTI(a,s). O elemen-tai, kurie gali  b?ti  aib?je  S,  imami  i?  labai
didel?s  aib?s.  Panagrin?sime  paskirstymo  metod?,  kuris  leid?ia   gerai
atlikti ?iuos 3 veiksmus.  A
  0                                                h(a)=1
  1                                                h(a)=2

                                                    h(a)=
m-1                                                =m-1
A-nuorod? masyvas(kiekvienas elementas  -  nuoroda  ?  sara??).  Paskirstymo
funkcija h(a) atvaizduoja universalios aib?s elementus  ? sveik?  skai?i?  0
( m-1 aib?.
Pvz.: h(a)=a mod m, ji gera kai a yra tolygiai  pasiskirst?.  Vadinasi  mums
reikia h(a) pasirinkti  pagal  a  pasiskirstym?.  A(i)  -  nurodo  ?  sara?o
element? a ( S, kur h(a)=i. Tai operacijos  ?STATYTI(a,s)  atlikimui  reikia
paskai?iuoti h(a) ir po to per?i?r?ti s?ra??, ? kur? nurodo h  A[h(a)].  Jei
elem A  ten  n?ra,  tai  j?  reikia  ?statyti  sara?o  gale.  PA?ALINTI(a,s)
atliekama analogi?kai. Tas  pats  ir  PRIKLAU-SYTI(a,s).  Blogiausiu  atveju
gali  atsitikti, kad atliekant operacij? ?STATYTI visoms  h(a)  gaunasi  tas
pats skai?ius ir visi elementai  tada  rasis  viename  sara?e.  Tuo  atveju,
atliekant  i-taj?  operacij?  reik?s  laiko,  proporcingo  i.  Ir  atliekant
?statymu reik?s ((n2) laiko. ?iuo atveju tai yra tas pats kaip ir  paprastas
sara?as. Ta?iau vidutinis  laikas  bus  ?ymiai  geresnis.  Jei  h(a)  ?gauna
reik?m? su tikimyb?mis 1/m ir ?statant nan.  Vadinasi  yra
u?duotos  tikimyb?s   q0,q1,...,qn.   (pi+(qi(1.Reikia   sudaryti   optimal?
paie?kos med? ,kuriame vidutini?kai b?t?  atliekama  ma?iausiai  palyginim?,
ie?kant ?vair? element? su u?duotomis tikimyb?s.
                               a4                          0
                     a3                     a5            1
             a1               3      4           5      2
       0              a2                                  3
               1               2
Fiktyviai pa?ymime elemtus medyje ,kuri? n?ra bet tenka ie?koti. Tikimyb?  ,
kad reik?s ie?koti a,  kuris  a3=nlog  n,  tai  ?is  algoritmas  i?  tikr?j?  yra
optimalus, o kai m<w (w=T?VAS[v] ). Tod?l  kai
gr??tama prie nutr?kusios proced?ros  paimama  sekanti  briauna,  kuri  gali
vesti ? nauj? vir??n? arba ? sen?. Tada 12  ir  13  operacijos  pakuoreguoja
APAT[v] reik?m?. ?ita briauna taip pat patenka ? stek?.  12  op.  pataikrina
ar ?i briauna patekusi ? med?.10 op. tikrina ar APAT[w] >=VIRNR[v],  jei  ne
tai 11 op. pakuoreguoja APAT[v]. Jei taip  tai  rei?kia  aptikta  labiausiai
susijusi  komponent?,  o  i?  steko  i?stumia  briaunas  ?einan?ias   ?   j?
(komponent?) ir taip pat i?stumiama paskutin?.



Paie?ka ? gyl? orentuotame grafe
Naudojant paie?kos  ?  gyl?  grafuose  algoritm?  orentuotame  grafe  galima
i?skirti orentuot? med?i? mi?k?, jei kiekvienam mazgui v suskaupsime  s?ra??
L[v], t.y. pasiekiame vir??ni? v aib? per 1 ?ingsn?. PVZ
            V1                           V2
                             V3
             V5                          V4

             V7                          V8
                            V6
                V1                     V6
           V2         V5       V7        V8
   V4           V3
I?skirtas grafo mi?kas (med?i? linijos i?tisin?s, kitos punktyrin?s)
Paimam vir??n? v1. I? jos pasiekiam v2. PIE?KA(v2) i??aukia PIE?KA(v3).  ?ia
Stop, niekur negalim patekti. Gr??tam ? v2 ir  pereinam  ?  v4.  V?l  niekur
negalim patekti. Gr??tam ? v1. ?ia i??aukiama PAIE?KA(v5). I? ?ios  vir??n?s
niekur negalim patekti, tod?l paimama sekanti УnaujaФ  vir??n?  v6  ir  t.t.
Gauasi du med?iai.
Tokio algoritmo darbo rezultate gauname 4 tip? lankus:
1.  Med?io  lankai,  kurie  paie?kos  metu  veda  ?   naujas   vir??nes   2.
Tiesioginiai lankai vedantieji nuo prot?vi? ? tiesioginius  palikuonis  (jei
(v,w)  -  tiesioginis  lankas  vw).

Stipriai susijusi? dali? is?kyrimas orentuotame grafe
Stipriai susijusios dalys orentuotame grafe,  tai  i?  bet  kurios  vir??n?s
egzistuoja kelias ? bet kuri?  kit?.  Kiekvienai  orentuoto  grafo  vir??nei
skai?iuosime APATRY?YS[v](  MIN({v}U{w  |  kuri  priklauso  skersiniam  arba
atbuliniam lankui (v,w) }). ?ia vir??ni? numeracija  pagal  pai?k?  ?  gyl?,
surandant med?ius. Vir??n?  v  orentuoto  grafo  stipriai  susijusios  dalie
?aknis bus  tada,  kai  APATRY?YS[v](v.  Atliekant  paie?k?  ?  gyl?  galima
apskai?iuoti APATRY?YS[V], o taip pat i?skirti  stipriai  susijusias  dalis,
tam grafo vir??n?s  talpinamos  ?  stek?,  kai  apeinant  graf?  sutinkamos.
Kiekvien?  kart?,  kai  aptinkama  stip.  susijusios  dalies  ?aknis,  visos
vir??n?s  iki  ?ios  ?aknies  i?stumiamos  i?  steko  ir  jos  yra  stipriai
susijusios dalies vir??n?s. Modifikuotos  proc.  paai?kinimas:  APATRY?YS[v]
skai?iuojamas 4,9 ir 11 eilut?je 4 operacijoje  suteikiama  pradin?  reik?m?
(vir??n?s Nr.). 9op. Priskiriam APATRY?YS[v](MIN(APATRY?YS[v],  APATRY?YS[w]
)-tai lankams ?einantiems ? med?. 10 op.  i?ai?kina  ar  n?einantis  ?  med?
lankas (v,w) yra atbulinis ar skersinis, o tai pat i?ai?kinama ar w(  stekui
;priklauso stipriai susijusiai grafo  daliai.  11  op.  koreguojama  reik?m?
APATRY?YS[v] (MIN(VIRNR[w], APATRY?YS[v] ). ?io algoritmo sud?tin-gumas  yra
((MAX(n,e)) Ц tiesin?s, n-vir??ni? sk. e-lank? sk.


Graf? susietumo matrica.

G(V,E) V-vir??ni? aib?, E-lank? aib?.
Susietumo matrica:     |0 1 1 0|
                 ( C ) (     |0 0 0 0|
            |0 1 0 0|
            |1 1 0 0|
cij ( {0, jei n?ra lanko i? i ? j 1,jei yra lankas i j
Susietumo matric? daugyba. Tegul turime grafus G1(V,E 1 ) ir G2 (V,  E  2  )
su tom pa?iom vir??n?m, bet skirtingais lankais. Sudauginsime  j?  susietumo
matricas C(C1*C2 . Susietumo matrica C atitinka multigrafas sudarytas  taip:
i? vi ? vj eina tiek lank?, kiek yra keli? i? vi ? vj ,  susidedan?i?  i?  2
lank?: pirmas lankas (G1 , antras (G2.  ?rodymas:  ar  egzistuoja  vi  ?  vj
kelias vi  vk  vj per tarpin? vir??n? vk  .  Galima  patikrinti  tokiu  b?du
c1ik*c2kj(1; c1ik(G1 , o c2kj(G2 . Kei?iant k nuo  1  iki  n  patikrinam  ar
egzistuoja kelias per  visas  tarpines  vir??nes.  Sumuojant,  gaunam  toki?
keli? sk. cij((k(1 n c1ik* c2kj. O tai atitinka  matric?  daugyba,  cij  yra
matricos C  elementai.  Tegul  C  yra  graf?  susietumo  matrica.  Tada  C*C
elementai  parodo  kiek  yra  skirting?  keli?  i?  vir??n?s  vi  ?   vj   ,
susidedan?i? i? dviej? lank?.
      |0110| |0110|    |0100|
( C )*( C ) (    |0000| |0000| ( |0000|
      |0100| |0100|    |0000|
      |1100| |1100|    |0110|
c12(1 rodo keli? v1 v3 v2 .
( C )( C )( C ) Parodo kiek keli? yra vj ir vi susidedan?i? i? 3 lank?.
      |0100| |0110|    |0000|
(C)(C)(C)(  |0000| |0000| (  |0000|
      |0000| |0100|    |0000|
      |0110| |1100|    |0100|
1 rodo, kad tarp v4 ir v2 yra kelias susidedantis i? 3 lauk?, tai v4  v1  v3
v2 . (C)4 rodyt? keli? sk. susidedan?i? i? keturi?  lank?,  ?ia  n?ra  toki?
keli?. Kai n?ra cikl?, tai  gauname  nulin?  matric?.  (C)n  Ц  yra  tikslas
skai?iuoti iki (C). Toliau bus rodomi  tik  ciklai.  Jei  susumuosime  visas
(C)+(C)2+Е+(C)n+
      |10..0|
                 +     |01..0|
      Е
      |00..1|
matricas, tai gausime keli? sk. i?  vi  ?  vj  .  Jei  atitinkamas  elemntas
cij>0, tai tas rodo, kad yra kelias tarp vir??ni? vi  vj  .  Matricos  (n*n)
daugybai reikia atlikti n3 daugybos veiksm?.  Matricai  (C)n  gauti,  reikia
~n4daugybos  veiksm?.  Kartais  keliamas  u?davinys  surasti  ar  egzistuoja
kelias tarp vis? grafo vir??ni?. T.y. surasti matric? (L), kurios
lij({0, jei n?ra kelio tarp vi ir vj 1, jei yra toks kelias.
Matom, kad  toks  u?davynys  gali  b?ti  i?spr?stas  dauginant  ir  sudedant
matricas. Grafas atitinkantis susietumo matric?  (L)  vadinamas  refleksiniu
-tranzitiniu grafo u?darymu.
Paai?kinimas (L) matricos radimo  algoritmo:  ?ia  visada  ckij(1,  jei  yra
daugiau keli?. Tod?l 5 op. 1+1(1. T.y. atliekami veiksmai su 0 ir 1.  ?ia  5
op. atliekamas n3 kart?, nes kartu atliekamas sumavimas.

Trumpiausio kelio radimas

Min kelio tarp vir??ni? radimo algoritmas:
 begin
1. for i(1 until n do c0ii(0;
2. for 1( i,j( n ir (j do c0ij(cij;
3. for k(1 until n do
4.      for 1( i, j( n do
5.      ckij( MIN(ck-1ij , ck-1ik +ck-1kj);
6. for 1( i, j( n do lij(cnij
 end
               V2    1 ir 2 op. duos matric? Cij0
     V1         2                | 2 8 5|
          5    V3       (Cij)( |3 ( (|
                                   |( 2 (|
         | 0 8 5|         k(1    |0 8 5|
(C0 ij)(| 3 0 8|         (C1ij)(|3 0 8|
           |( 2 0|                   |( 2 0|
C112(MIN(C012 , C011+C012)(8
C123(MIN(C023 , C021+C013)(8  ?vertina mas kelias v2v1v3 per v1.
k(2      |0 8 5|   C231(MIN(C131 ,C132+
(C2 ij)(| 3 0 8|                        + C121)(5
            |5 2 0| ?vertinamas kelias v3v2v1   per  v2.
 k(3     |0 7 5|   C312(MIN(C212 ,C213+
(C2 ij)(| 3 0 8|                        + C232)(7
            |5 2 0| ?vertinamas kelias v1v3v2 ,
kuris trumpesnis negu tiesioginis v1v2.
?io algoritmo sud?tingumas ((n3),nes ? op. atliekamas n3 kart? , o ? op.  n2
kart?. 1,2 op.taip pat n2 kart?.



U?davinys su vienu ?altiniu (  Deiks-tros algoritmas)
Randami trumpiausi atstumai  nuo vienos vir??n?s iki kit? garfo vir??ni?.
Grafas G=(V,E), pradin? vir??n? v0(V. Duotos reik?m?s l(vi  ,vj  )  ir  l(vi
,vj )= +(, jei  n?ra  lanko  vi  vj  .  Sprend?iant  ??  u?davin?,  sudaroma
vir??ni? aib? S(V.Taip  trumpiausias  atstumas  nuo  v0  iki  v(S  eina  per
vir??nes (S.


     V0           2             V1
               7                            3
10                        6                V5
                                             4
    V4        5              V3


I_|   S_  |w|D[w]|D[v1]|D[v2]|D[v3]|D[v4]

Prad?.| {v0}          | -  | -  | 2 | +( | +( | 10
1. |{v0,v1}             | v1| 2 | 2  |  5  | +( |  9
2. |{v0,v1,v2}        | v2 | 5 | 2 |  5   |   9  |   9
3. |{v0,v1,v2,v3}    | v3 | 9 | 2 |   5  |   9  |   9
4. |{v0,v1,v2,v3,v4}| v4 | 9 | 2 |   5  |   9  |   9

begin
1. S({v};
2. D[v](0;
3. for v(V,kaiS={v}do D[v](l(v,v)
4. while S(V do
   begin
5. paimti vir??n? w(V, nepriklausan?i? S, kuriai D[w]-mminimali (w(V-S)
6. prid?ti vir?un? w prie aib?s S;
7. for v(V-S do
8.   D[v](MIN(D[v];D[w]+l(w,v));
   end;
end;
     5  op.  atliekamas  n  kart?  (n-vir??ni?  ksai?ius),  7,8  operatoriai
atliekami n kart? (max). 4 op. wile ciklas ?stato kiekivien?  vir??n?  ?  S.
Tod?l ciklas i?  4,5,6,7,8 operatori? atleikamas n2 kart?,  tod?l  algoritmo
sud?tingumas ((n2) ( 3  operatorius  atleikamas  n  kart?,  tod?l  algoritmo
sud?tingumui ?takos neturi ).

	

ѕреимущества заказа у 5rik.ru - это пр€мой контакт с авторм без диспетчеров и курьеров обеспечит наивысшее качество за приемлемую цену....

ѕримерные цены работ на заказ