Алгоритмы

Алгоритмы

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| 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 =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 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 mw (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}Uw ). ?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 ).