algoritmai

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 nnutraukiama 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šą 331=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 rraktas 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; kk=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 q(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(nc)+f(n), kur a≥1, c≥1, f(n)-teigiama f-ja. 1) Jei f(n)= q(n(logca)-e) ,tai T(n)= q(nlogca). 2) Jei f(n)= q(nlogca) ,tai T(n)= q(nlogca . log n. 3) Jei f(n)= q(n(logca)+e) ,tai T(n)= q(f(n)), jei af(nc)≤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 q(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 q( 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 q[(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 ppaskutinę 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 ssukeič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

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 q(n2).

Iterpimo metodas.

Čia eilinis elementas yyra į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ų:

Pagal tai ir algoritmo sudėtingumas bus q(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 ppalyginimų 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:

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 q(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 t = 1/Kåi=1K (ti), vidurkis – atsitiktinis dydis.

Dirpersija bus : S2(t)= i-t)2= = ti2-2`t ti +`t2) = = ti2-2t ti+K`t2]= = ti2-2( ti)* * ti + K/K2 ( ti)2] = * *[ ti2 – ( ti)2]

Ši dispersijos ffomulė 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 [ ti] = 1/K2 D(ti) = 1/K*D(t); D – tikroji dispersija;S-įvertinimas.S2(`t)=S2(t)/K arba ištraukus šaknį: S(t) = S(t)/ ; |`t – m| 0, tai D`t = `t1- `t2, S2(Dt)»S2(`t1)+ S2(`t2)-2`M12 t.y. dispersija mažesnė nei nepriklausomų dydžių atvju. S2(D`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: D`t – tpS(D`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 ssurūšiuota. Tada seka suskaldoma į vieną elementą ir visą likusią. Gausis taip kaip ir kituose algoritmuose. Tuo atveju algoritmo sudė-tingumas q(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:

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 q(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 + e

e – 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, jjei bet kokia seka iš n elementų vienodai galima?

Hn=1 + P[ai > aj] × 1 = 1+ 1/2 × 1 = = ln n + g +1/2n + e

Ši eilutė diverguojanti, t.y. didėjant n, jos reikšmė didėja.(Eulerio formulė) čia g=0,577; e- 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 palyginimų. Paskutiniame lygyje pralai-mėjusį elementą reikės palyginti su ppra-laimėjusiais elementais, lyginant su mak-simaliu. Taip rasim kitą max elementą. Reikia 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 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 bblogiausio (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)=

Bendras šios srities sprendinys:

(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) = q( 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. AAPJUNGTI (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 S 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————–

w1 ir w2 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 q(eloge).e-briaunų sk.

Tuomet 3-čio operatoriaus sudetingumas proporcingas viršūnių sk. n q(n). Laikas reikalingas surasti aibei w1 ir w2 įkurias įeina viršūnes V ir w ir jų sujungimas, jei priklauso skirtingoms aibėms yra beveik tuščias: q(n) . O jei tiksliau t.y. q(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 q( MAX(e,n log n)). Todėl matom, kad visumoje Kraskalo algoritmo sudėtingumas yra q(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 q(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

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

V5 V4

V7 V8

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 q(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 i1 until n do c0ii0;

2. for 1£ i,j£ n ir ¹j do c0ijcij;

3. for k1 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 lijcnij

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 q(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

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;

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 q(n2) ( 3 operatorius atleikamas n kartų, todėl algoritmo sudėtingumui įtakos neturi ).