-1-

PAIESKA PAPRASTAME SĄRASE

1.1. Nuosekli paieska

Tegu įrasai isdėstyti atsitiktinai kaip buvo įrasyti. Reikia surasti duotą įrasą pagal raktą. Nuosekliai ieskant reikia perziūrėti visus įrasus nuosekliai.Vid.perziūrėų įrasų sk. ieskant yra L_ap =L/2. Jei įraso nėra teks perziūrėti visus įrasus L. Tarkim ieskomo įraso su tikimybe p₀ nėra sąrase, tada vid. perziūrėtų įrasų sk. L_ap=L*p₀+ _{i 1}^L (i*p_i ); p_i=1-p₀/L. Ieskant įraso sutvarkytame faile(įrasai isdėstyti pagal raktą) reikia perziūrėti is eilės, todėl vid. perziūrėtų įrasų sk. tas pats: L_sp=L/2. Jei ieskomo įraso nėra, tai paieska nutraukiama kai eilinis raktas bus didesnis uz uzduotą. Atliekant k įrasų paieską nesutvarkytame faile vid. perziūrėtų įrasų sk. L_kap = k * L / 2.

1.2. Paieska interpoliavimas

Jei sąrasai surusiuoti ir zinomas pirmo iraso raktas K(1) ir paskutinio K(n) tai galima apskaičiuoti p=X-K(1)/K(n)-K(1). X-ieskomo įraso raktas.Paieską pradedam nuo įraso kurio numeris p*n.

1.3. Binarinė paieska

Naudojama surūsiuotame masyve. Jis dalinamas pusiau ir ieskomas raktas lyginamas su vidurio raktu ir t.t.. Idealus masyvo dydis 2ⁿ-1.Jei 31 įrasas reikės 5 zingsnių, kad surasti įrasą 31 2⁵-1. Bendru atveju 2^n-1-1< N 2^n-1. Kai įrasų sk. bet koks, tai naudojami tokie alg.:

-9-

RŪSIAVIMO ALGORITMAI

K-mačių kortezų rūsiavimas

Tegul mes turime seką A₁ A₂ ... A_n k-mačių kortezų, t.y., A erdvinis A_i elementas, sudarytas is a_i1 a_i2 ... a_ik.Reikia sią seką rusiuoti taip: B₁ B₂ ... B_n, kad visiem i B_i B_i+1. Rūsiavimas atliekamas k kartų pereinant per duotą seką. Pirmą kartą atliekamas rūsiavimas pagal k-ąją komponentę. Antrą kartą pagal (k-1) komponentę ir t.t. Prėjus pagal i-ąją, turėsim sūrusiuotą seką. Kiekviena skiltis a_{i j} yra nuo 0 iki m-1. Reikia organizuoti m pagalbinių eilių Q(j), kur j 0,...,m-1, kurios is pradziu turi buti tusčios. Duomenis A₁ A₂ ... A_n is pradziu surasom i sąrasą EILE. Paimam eilini kortezą A_i is EILĖS ir patalpinam į pagalbinę eilę Q(j) pagal analizuojamos komponentės reiksmę. Taip darom tol, kol bendra EILĖ istustėja. Visi kortezai 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ūsiuota. Algoritmo sudėtingumas yra tiesinis q[(n+m)/k]. Naudoti sį metodą neverta, kai n yra mazas.

-17-

t₂t_1i+ t₁ t₂)=[ t_1it_2i - t₁ t_2i - t₂ t_1i + K t₁ t₂] =[t_1it_2i-1/K t_1i t_2i] ; Dt_i= t_1i - t_2i ; D(Dt)=D(t₁)+ D(t₂)-2M₁₂ (1); Koreliacijos koef. K₁₂ = M₁₂ / s(t₁)s(t₂); Jis gali kisti nuo -1 iki +1. M₁₂=K₁₂s(t₁)s(t₂). Jei K₁₂=1, tai reiskia teisinę funkcinę priklausomybę. Jei K₁₂=1 ir s(t₁)=s(t₂), tai jei įstatysim į 1 -ają formulę, tai gausime D(Dt)=0. Tačiau tai idealus atvejis, o praktiskai K₁₂ < 1.

Jei K₁₂ > 0, tai D`t = t<sub>1</sub>- t<sub>2</sub>, S<sup>2</sup>(Dt) S<sup>2</sup>( t<sub>1</sub>)+ S<sup>2</sup>( t<sub>2</sub>)-2 M<sub>12</sub> t.y. dispersija mazesne nei nepriklausomu dydziu atvju. S<sup>2</sup>(D`t) S²(t₁)/K+ S²(t₂)/K - 2K₁₂S( t₁) * S( t₂)= S²(t₁)/K+ S²(t₂)/K - 2M₁₂/S(t₁)S(t₂)* S(t₁)/ k * S(t₂)/ K = S²(t₁)/K+ S²(t₂)/K - 2M₁₂/K t.y. ir vidurkio dispersija yra mazesne, nes atsiima 2M₁₂/K. Atitinkamai intervalinis įvertinimas: D`t - t<sub>p</sub>S(D`t) <m (Dt) < D`t + t<sub>p</sub>S(D`t) (1). Kadangi S²(Dt) esant priklausomų bandymų atvejais yra < nei nepriklausomų bandymų, tai intervalinis įvertinimas (1) yra siauresnis ir algoritmų vertinimas yra tikslesnis. Jei intervalas apima 0, tai algoritmų palyginti negalima. Arba galima sakyti ir taip:

-3-

2) Posąrasio dydzio nustatymo metodas.Pradedant paieską iseities posąrasio dydis S₁ N, tai pirmoji riba N₁ N/2 , o posąrasis S₂ S₁/2 . S_i+1 S_i/2 ; N_i+1 N_i S_i+1/2 . Jeigu įrasų nėra, tai paskutinėje iteracijoje S_i+1 1. Toliau dalinant pusiau ir imant sekantį posąrasį, jis tampa nuliniu ir tai rodo, kad įrasų nėra.

3) Ribos numeris visada 2 laipsnyje

Idealus atvejis binarinei paieskai N 2^k-1 ir riba bus N₁ 2^k-1.Tegu 2^k-1<N<2^k-1, tai pirma riba N₁ 2^k-1. Gaunam 2 ne vienodas dalis. Jei K<F₁, tai imam pirmą dali ir elgiames kaip idealiu atveju. Jei K>F_1, tai ieskomas įrasas yra antroje dalyje, kuri mazesnę uz pirmąją.

2^r-1-1<N-2^k-1<2^r-1 ir vėl viskas tas pats. Panagrinėsime algoritmo sudėtingumą, įstatant n elementų į medį pagal atliekamų palyginimų sk.. Blogiausias atvejis, kai elementai isrikiuoti, nes gaunamas paprastas sąrasas ir kiekvieną elementą pastatyti į sąraso galą. T(n)-bendras palyginimų sk. įstatant n elementų į sąrasą. T(n-1) - bendras palyginimų sk. įstatant n-1 elementą. Įstatant n-tąjį elementą reikia n-1 palyginimų. T(n) T(n-1) + (n-1). T(n) T(n-1) + (n-1) T(n-2) + (n-2) + (n-1) T(1) + 1 +...+ (n-1) _{i 1}^n-1 ( i ) n * (n-1)/2. Vidutinis atvejis, kai iseities seka a₁,a₂,...,a_n yra bet kokia, tai sio algoritmo sudėtingumas q(n log n ).

-11-

Rūsiavimas lyginant elementus

"Burbuliuko" metodas. Paprastai elementai rūsiuojami pagal raktinį zodį.

Tarkim turim K₁..K₁₆ elementų ir lyginame K₁ >K₂. Jeigu daugiau sukeičiam vietom. Jeigu ne nieko nedarom ir t.t. Paskutinis palyginimas bus K_m > K_n. Po 1 iteracijos didziausias 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 isrūsiuota seka bus 0 pakitimų, o atvirksčiai isrūsiuota seka - n(n-1)/2 pakeitimų. Tada vidutinis pakeitimų sk. bus n(n-1)/4.

Jeigu yra n elementų seka, tai is jos gali būti padaryti n! sekų. Mes laikome kad bet kuri seka gali pasitaikyti su vienoda tikimybe 1/n!.

Kiekvienai sekai galima parasyti inversiską seką. Jeigu turime tokias 2 sekas, ir jas surusiuosime, tai sumalinis pakeitimu sk. bus n(n-1)/4. Algoritmo sudetingumas q(n²).

-19-

Binarinis įterpimo algoritmas

Ieskant elementui vietos jau surūsiuotoje sekoje mes galima naudoti binarinį paieskos metodą.

Iterpiant i+1 elementą i i-tojo dydzio surusiuotą sąrasą reikia atlikti log i + 1 = log(i+1) palyginimą. Visada reiks atlikti max palyginimu, nes iterpiamo dydzio tame sąrase nera. Rusiuojant n-tojo dydzio sąrasą mums reikes atlikti log(i+1) palyginimų.

log(i+1) = log(i) = n log(n)]-2 ^logn + 1 tokio algoritmo sudėtingumas q(nlogn).

Rūsiavimas isrinkimu

Is pradziu isrenkame didziausią elementą. Ji sukeičiame su paskutiniu. Paskui is likusios dalies isrenkame didziausią ir sukeičiame su priespaskutiniu ir t.t.

Palyginimų sk. tokiam algoritmui yra (n-i)=i=n(n-1)/2, tai sio algo-ritmo sudėtingumas: q(n²).Sis alg. gali būti geriausias vienu metu ieskant max ir min.

-5-

1) Principas - 'Skaldyk ir valdyk'

Sprendziant koki nors uzdavini kartais jie suskaldomi i du. Rasti ju sprendimai apjungiami ir gaunamas uzdavinio sprendimas. Savo ruoztu suskaidyti uzdaviniai gali buti toliau skaidomi. Visiems uzdaviniams spręsti naudojama ta pati rekursyvi procedura. Pavyzdziui, reikia rasti aibeje is N elementu max ir min elementą. Surandant max elementą reikia (n-1) palyginimu. Taip pat ir ieskant min reikia (n-2) palyginimu (su max nelyginam). Ieskant min ir max elementu reikia 2n -3. Tarkim n 2^k. Visą aibę suskaldom i 2 dalis. Kiekvienoje is ju randam min ir max ir juos palyginam. T(n) =p. Pazy-mekime t_p = e/ S( t) (2). m- vidurkio matematinė viltis. t - m įvertinimas tada is formulės (2) iseina, kad e = t_p*S( t) = t_p. Galim parasyti : t-e< m< t+e, tada t - t_p< m < t + t_pt.y. tikroji matematinė viltis su tikimybe p rasis siame intervale, o su tikimybe 1 iseis is sio intervalo. Turime taip vadinamą intervalinį įvertinimą.

Dviejų programų ekspermentinis- statistinis tyrimas. Tegul mes atlikom skaičiavimus pagal vieną programą ir fiksavom laikus t_1i(i=1..K). Galima paskaičiuoti vidurkį t₁ , dispersiją S²(t₁) ir t₁+- e₁(intervalinis įvertinimas). Tą patį atlie-kam su kita programa t₂, S²(t₂), t₂ +- e₂

Jei palyginsim tik t₁ ir t₂ tas dar nerodo, kad vienas is sių algoritmų yra geresnis, nes t₁ ir t₂ - atsitiktiniai dydziai, todel palyginimu rezultatas taip pat gali buti atsitiktinis. Geriau lyginti t₁ e₁ ir t₂ e₂. Jei jie nepersidengia, tai yra pagrindo teigti, kad viena programa yra geresnė uz kitą.Arba galima lyginti ir taip:

-23-

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 1}ⁿ f(i-1), o seką (n-i) yra _{i 1}ⁿ f(n-i). 1/n- i su vienoda tikimybe gali atsirasti bet kurioje vietoje.

_{i 1}ⁿ [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 1}ⁿf(i)

f(n) cn + 2/n _{i 0}^n-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 mazos sekos gali buti rusiuojamos kitu budu, kas dar pagreitina si algoritmą.

Optimalus rūsiavimas. Jei yra n elementų, tai variantų is viso gali būti n!. n=3, 3!=6 Minimalus palyginimų sk. blogiausiu atveju = 3. Ir laikom, kad si schema optimali. Tegul S(n) - minimalus palyginimų sk. blogiausiu atveju, rūsiuojant n elementų: S(3)=3 Pilname k-tojo lygio binariniame medyje, paskutiniame lygyje yra 2^K 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ė)

-8-

Dinaminis programavimas.

Kartais galima efektyvius algoritmus gauti naudojant dinaminį programavimą. Siuo būdu reikėtų skaičiuoti visus dalinius uzdavnius, bet sprendziami nuo mazu prie dideliu. Atsakymai prisimenami lenteleje ir uzdaviniai jungiami, kad butu isspręstas visas uzdavinys ir gautas optimumas. Pvz. sudauginant n matricu yra labai svarbus daugybos eiliskumas, kuris nulemia bendrą veiksmu skaičių. Pazymim m_{i j} minimalus veiksmų sk. dauginant matricas: M_i*M_i+1*...*M_j, kur 1 i < j n. Kai M M₁*M₂*...*M_n, tai jų matiskumas yra r₀*r₁*r₂*...*r_n.

m_{i j} =p.Padalinkime abi puses is vidutinės kvadratinės paklaidos.

-22-

Rūsiavimas suskaldymu (quick sort).

Turime seką is n elementu. I 1, o J n. Lyginame A(I) su A(J). Jei A(I) < A(J), tai J J-1, bet jei A(I) > 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 mazesni uz jį, o desinėje didesni, t.y. suskaldėm seką jo atzvilgiu. Elementas pagal kurį atlikome palyginimus yra pirmasis ir vadinamas generaliniu. Čia generalinis elementas visada buvo pirmas, tačiau tai nebztina. Gaima paimti bet kuri. Generaliniai elementai gali buti parenkami ivairiai: pirmas, atsitiktinis, mediana (vidurinis). Skaidyti pagal medianą geriausia. Galima paimti nedidelią imti is keliu sekos elementu ir surasti medianą. Imant visada pirmą elementą, blogiausias atvejis gaunasi, kada seka yra surusiuota. Tada seka suskaldoma i vieną elementą ir visą likusią. Gausis taip kaip ir kituose algoritmuose. Tuo atveju algoritmo sude-tingumas q(n²), o visais kitais atvejais zymiai geriau. Sis algoritmas gerai veikia didelem sekom, o taip pat reikia tinkamai parinkti generalini elementą. Vid. veiksmu sk. yra:

-4-

Lygių sk. binariniame medyje - log n. Tegu T(n) yra palyginimų sk. įstatant elementus a₁,a₂,...,a_n į binarinį medį. Tegu b₁,b₂,...,b_n yra ta pati seka, tačiau jau isrūsiuota didėjimo tvarka. Kadangi a₁,a₂,..,a_n yra atsitiktinai isdėstyti, tai bet kuris is jų gali atsidurti bent kurioje vietoje su vienoda tikimybe. Tuomet a₁ su tikimybe 1/n gali atsirasti j vietoje (j 1...n). a₁ faktiskai tampa medzio saknim ir jis yra j-tasis. Tai (j-1) elementu yra kaireje puseje, o (n-j) desineje. Istatant (j-1) elementu i kairi pomedi, reikia (j-1) palyginimu su saknimi plius T(j-1) ((j-1)+T(j-1)). Analogiskai desiniam pomedziui reikia (n-j) palyginimu su saknimi plius T(n-j). (j-1) + T(j-1) + (n-j) + T(n-j) (n-1) + T(j-1) + T(n-j). Tiek palyginimų reikėtų jei būtų j-tasis elementas (medzio saknimi),bet a₁ gali būti bet kuris, tuomet palyginimų sk.: T(n) 1/n _{j 1}ⁿ ((n-1)+T(j-1)+T(n-j)) n-1+ 1/n _{j 1}ⁿ (T(j-1) + T(n-j)) n-1 + 2/n _{j 0}^n-1 ( T(j) ).

Toliau pertvarkant galima parodyti, kad T(n) k n log n, kur k ln 4 1.39.

-12-

Iterpimo metodas.

Čia eilinis elementas yra įterpiamas į jau surūsiuotą elemetų seką. Tegul turime n elementų is viso ir turime jau i surūsiuotų elementų. Mums reikia įterpti i+1 elementą K_i+1. K_i+1 atsidurs tarp K_j < K_i+1 < K_j+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(n²).Vidutiniskai bus maziau palyginimu.Siuo budu rusiuojant masyvus (paprastus) patogiau pradeti elemtu lyginimą nuo surusiuotos sekos pabaigos. Tai yra nuo i-tojo elemento.

Panagrinėkime koks siame algoritme yra vidutinis palyginimų sk. Tegul turime i surūsiuotų 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:

je

-20-

Rūsiavimas piramide

Sis algoritmas susideda is dviejų dalių:1. Is duotos sekos sudaryti rūsiavimo medį. 2. Sukeisti pirmą elementą su paskutiniu ir atstatyti rūsiavimo medį. Rūsiavimo medį pradedame sudarinėti nuo n/2 , o kiekviena narys A(i) A(2i) ir A(i) 2i+1, ir [1 i n/2] arba [1 i n/2]. Didziausias elementas tampa medzio saknis. Pastatome didziausią elementą i sekos galą ir kadangi jis jau savo vietoje, todel jis daugiau nenagrinejamas, o seką sumaziname 1 ir turime jau ne rusiavimo medi. Mums vel reikia atstatyti rusiavimo medi, kad pirmasis elementas butu didziausias t.y. pradedant nuo n/2 eiti link pirmo ir kiekvieną elementą reikia sukeisti vietomis su didesniu sunumi. Taigi mums reikia tam tikrą elementą perstumti per kazkiek lygiu. Perstumiant elementą per 1 lygi reikia atlikti 2 palyginimus: (2i) ir (2i+1) tarpusavyje ir didziausią is ju su palyginamu elementu. Perstumiant elementą per n lygiu reikia atlikti 2n palyginimu, todel blogiausiu atveju, perstumiant n elementu, palyginimu sk. nevirsins 2nm.(m-lygiu sk. , be pirmos virsunes). Kai reikiia perstumti 1 elementą, maksimaliai reikia f(n) 2 log n palyginimų. Tiksliau: f(n) log n + log (n-1) . Perstumiant n virsūnių maksimaliai turėtume 2n log n palyginimų. Algoritmo sudėtingumas bus q(n log n). Tačiau įrodyta, kad pirmoje dalyje reikės ne daugiau kaip 2n-4 palyginimų, todėl pirmos dalies algoritmo sudėtingumas yra tiesinis, nes čia reikia perziureti tik n/2 elementu, o visumoje sio algoritmo sudetingumas q(n log n).

-2-

1) Posąrasio ribu nustatymo metodas. Iskiriame 2 markerius: V virsutiniam adresui ir A apatiniam adresui. Vidurinio įraso adresas F (V+A) / 2 . Ieskomas įraso raktas k palyginamas su F. Jei k F_k, tai įrasas surastas, jei k<F_k, tai imama virsutinė pusė, tada V pasilieka tas pats, o A F-1.Jei k > F_k, tai imam apatinę dali, tada V F+1, o A islieka tas pats ir t.t.. Toks dalinimas atliekamas tol, kol nepasidaro A V. Rekurentinė lygtis aprasanti max palyginimų sk. binarinėje paieskoje yra:

f(n) U) w-virsūnė is labiausiai susijusios komponentės. Jeigu surasime visų virsūnių APAT[v], tai automatiskai isskirsim susijusias dalis. Kiekvienos virsūnės v skaičių APAT[v] kai bus perziūrėtos visos zemesnės virsūnės, gausime taip:

APAT[v] = MIN (UU (1).

Čia virsūnės sunumeruotos pagal paieskos į gylį algoritmą.

Algoritmas t.y. faktiskai skaičiavimas pagal (1) formulę arba pakoreguota paieskos i gyli procedura. Procedūros paaiskinimas čia atliekamas virsūnių pernumeravimas. v<w jeigu v yra w protėvis. 4 eil. dydziui APAT[v] suteikiama pradinė reiksmė max gailma (jos Nr.) taip iki 9 operando.

-27-

k-ojo didesnio elem. Isrinkimas[be rusiavimo]

1.Alg. - isrinkimas su randomizacija: paėmus į-ajį elem ir elementu seka suskaidoma į 2 dalis: (i-1)- S₁, i, (n-i)-S₃. 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 ieskomas elem. ir jį skaidome toliau: Jei i>k, tai imame S₁, kuriame yra (i-1) ele-tų. Jei i<k, tai imame S₃ kuriame yra (n-i) elem. Antru atveju imamas poabis S₃ , taciau ieskomas elem., kuris yra(k-i), o skaidymui naudojamas tas pats alg. Kadangi skaidydami gali buti parinktas bet kuris elem.i, kuris gali būti lygus i =1,2..n su vienoda tikimybe 1/n, tai vid. palyginimų sk. bus

f(n)=n-1+1/n [S_i=1^k-1 f(n-i)+Sⁿ_i=k+1 f(i -1)]=n-1+1/n [S^n-1_i=n-k+1 f(i)+ [S_i=k^n-1 f(i )]

Čia įrodyta, kad f(n)<= 4n , t.y vidutiniskai sis alg, yra tiesinis q(n).

Jeigu nevykusiai pasirenkame skaidymui elem, tokio alg, sudėtingumas q(n²).

Isrinkimas be randomizacijos.

Naudojan 1-mą alg geriau butu zinoti medianą ir pagal ją suskaidyti aibę, bet reik surasti medianą.Siulomas apytikslis budas rasti medianą-padalinsime aibę po 5 elem. Surandame kiekveinos dalies medianą ir pagal si elem, skaidome visą aibę.

-35-

Fiktyviai pazymime elemtus medyje ,kuriu nera bet tenka ieskoti. Tikimybe , kad reikes ieskoti a, kuris a₃<a<a₄ yra q₃.Jei mums reikės iskoti a_i elemento , tai mums rekės atlikti GYLIS(a_i)+1 palyginima. Jei mums reikės ieskoti i-tojo elemento ,kurio nėra , tai mums reikės atlikti GYLIS( i ) palyginimų . Tai vid. palyginimų sk. C bus:

C _{i 1}ⁿ p_i [GYLIS(a_i)+1]+ _{i 0}ⁿ q_i GYLIS( i )

Nubraizome visus galimus medzio variantus ir kurio C maziausias ,tai ir bus optimalus binarines paieskos medis . Tai nesunku atlikti kai elementu sk. nedidelis.Tačiau sį uzdavinį galima spręsti naudojant dinaminį programavimą. Pirmiausia reikia nuspręsti kurį elementa padaryti saknimi. O po to lieka dar du medziai. Faktiskai galime padaryti bet kurį a_i elementą is n elementu. Taigi gali buti n variantu. Gaunasi labai kompli-kuotas uzdavinys , nes dar 2n pomedziu su kuriais darom vel tą pati. Todel faktiskai si uzdavini reikia spręsti is apačios. Pazymesime T_ij optimalų pomedį , kur 0 i j n.Tai dabar siame pomedyje yra elementai: (a_i+1 , a_i+2 , ...,a_j ). a_i nėra, nes pomedis prasideda nuo fiktyvaus elemento, baigiasi tai pat fiktyviu a_j. Pazymim C_ij jo vidutinį palyginimų sk. (kainą) . Sio pomedzio saknis yra r_ij . Pazymesim dar kiekvienam pomedziui T_ij svorį w_ij , kuris yra lygus:

-43-

PVZ

V₁ V₂

V₃

V₅ V₄

V₇ V₈

V₆

V₁ V₆

V₂ V₅ V₇ V₈

V₄ V₃

Isskirtas grafo miskas (medziu linijos istisines, kitos punktyrines)

Paimam virsūnę v₁. Is jos pasiekiam v₂. PIESKA(v₂) issaukia PIESKA(v₃). Čia Stop, niekur negalim patekti. Grįztam į v₂ ir pereinam į v₄. Vėl niekur negalim patekti. Grįztam į v₁. Čia issaukiama PAIESKA(v₅). Is sios virsūnės niekur negalim patekti, todėl paimama sekanti "nauja" virsūnė v₆ ir t.t. Gauasi du medziai.

Tokio algoritmo darbo rezultate gauname 4 tipų lankus:

1. Medzio lankai, kurie paieskos metu veda i naujas virsunes 2. Tiesioginiai lankai vedantieji nuo proteviu i tiesioginius palikuonis (jei (v,w) - tiesioginis lankas v<w) 3. Atbuliniai lankai vedantieji nuo palikuoniu i protevius 4. Skersiniai lankai, jungiantieji virsunes, kurios nera nei proteviai nei palikuonys viena kitai (jei (v,w) - skersinis lankas, tai v>w).

-29-

5.Dviejų maziausių: P(2,n-2)=n+ log(n-1) -2

6. trijų maziausių: P(3,n-3)=n+2 log n - 3|2|1|

įvairiais atvejais priklausomai nuo n.

Galima kelti tokius uzdavinius:

a.surasti k maziausiu elem, P(k,n-k).

b. surasti k-ąji elementą P(k-1,1,n-k).

c. surasti k elementų is 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 poziuriu)

Uzdavinius galima suvesti i veiksmus su aibemis. Isanalizuojam ivairias Duomenu Strukturas ir pasirenkam labiausiai tinkamą. Gero alg. Sukurimas neatski-riamas nuo tinkamos DS pasirinkimo. Pagr. mat. veiksmai su aibemis budingi informacines paieskos uzdaviniams:

1:PRIKLAUSYTI (a, S). Nustato ar elem.a priklauso aibei S. Jei a priklauso S, tada TAIP, priesingu atveju NE..

2:ĮSTATYTI (a,S).Įstato elem, a į S. Gaunasi aibė S ir elem, a t.y. S .

3:PASALINTI (a,S). Pasalina a elem, is aibės S t.y. aibė S pakeičiama į S-.

4. APJUNGTI (S₁,S₂,S₃). Atlieka tokį veiksmą: S₃= S₁ S₂.

5:RASTI (a). Reikia rasti aibę, kurioje duotu momentu randasi elem, a. Jei rastu dvejose aibese, tada veksmas nenustatytas.

-37-

Optimalaus binarinės paieskos medzio algoritmo sudėtingumas yra q(n³) .Procedūros MEDIS(i, j) sudėtingumas yra tiesinis , nes ji issaukiama n kartų.

8-tame operatoriuje ieskant m reikia palyginti sumas C_{i, k-1}+C_{k, j} . Tokių sumų yra j-1. todėl sios dalies sudėtingumas yra q(j-i). j įgija reiksmę n , o i-nulį. tai maksimalu atveju. Isorinis ciklas 4-10 atliekamas n kartų , o vidinis ciklas 5-10 nedaugiau n kartų kiekvienai isorinio ciklo iteracijai . Todėl algoritmo sudėtingumas su gera atsarga yra q(n³).

OPERACIJŲ APJUNGTI IR RASTI ATLIKIMO ALGORITMAS

Kruskalo algoritmų ypatumai:

1.Apjungiamos visada nepersikertančios aibės.

2.Aibių elementai tai virsūnių numeriai nuo 1 iki n.

Čia uzdavinio sprendimui yra papras-čiausiai duomenų struktūra - masyvas is n elementų. R(i), (i=1,2,.,n).

Čia kiekvienas elementas R(i) yra i-ta virsūnė. Is pradzių kiekvienas elementas sudaro atskirą aibę, todėl surasoma R(i)=i ir tai reiskia aibės numerį, kuriai priklauso sis elementas. Operacija RASTI(i) atliekama tiesioginiu kreipimosi į R(i). ir gaunamas aibės numeris, kuriai priklauso sis elementas. Kreipimosi laikas pastovus, todėl atliekant n tokių operacijų, sudėtingumas yra tiesinis q(n). čia yra geriausias atvejis. Norint atlikti operaciją APJUNGTI(A,B,C) reikia perziureti visą masyvą

-45-

Grafų susietumo matrica.

G(V,E) V-virsūnių aibė, E-lankų aibė.

Susietumo matrica: |0 1 1 0|

( C ) |0 0 0 0|

|0 1 0 0|

|1 1 0 0|

c_ij | - | - | 2 | + | + | 10

1. | | v₁| 2 | 2 | 5 | + | 9

2. | | v₂ | 5 | 2 | 5 | 9 | 9

3. | | v₃ | 9 | 2 | 5 | 9 | 9

4. || v₄ | 9 | 2 | 5 | 9 | 9

begin

S ; 2. D[v] 0;

3. for v V,kaiS=do D[v] l(v,v)

4. while S V do

begin

5. paimti virsūnę w V, nepriklausančią S, kuriai D[w]-mminimali (w V-S)

6. pridėti virsunę 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-virsūnių ksaičius), 7,8 operatoriai atliekami n kartų (max). 4 op. wile ciklas įstato kiekivieną virsūnę į S. Todėl ciklas is 4,5,6,7,8 operatorių atleikamas n² kartų, todėl algoritmo sudėtingumas q(n²) ( 3 operatorius atleikamas n kartų, todėl algoritmo sudėtingumui įtakos neturi ).

-30-

6:SUSKALDYTI (a,S) Čia aibėselem, uzduoti santykiu <=.Sis veiksmas atliks aibės S suskaldymą į S₁= ir S₂=

7:MIN (S) Suranda maziausią aibes S elem.

Siuos veiksmus reik atlikti tam tikra seka duomenų bazėje.Mus domina laikas atliekant veiksmų seką priklausomai DB dydzio ir nuo veiksmų sekos ilgio. Sis laikinas sudėtingumas paprastai tikrinamas blogiausiu atveju ir vidutinisku.

PVZ.

Kraskalo alogoritmas.

Surasti ekonominį medį neorentuotam grafe. Yra grafas G (V, E).V-virs. aibė,E-briaunų aib. Kieikviena briauna is E turi svorį c. Reikia surasti grafą-medį G(V,T). T-E poaibis is. Taip kad S _{i T} c_i =>min.

Medis grafas be ciklo. Jei medyje S(V,T) pridesime kokią nors briauną, tai susidarys vienas ciklas. Grafo G misku vadiname neorentuotu medziu aibe: , ,..., . V₁ ,V₂, .. V_k-suskaldyta aibė V. V=V₁ V₂, .. V_k; V _i V_j = . Atitinkamai T₁,T₂,.T_k yra aibės E poaibiai. Kraskalo alg sako: reikia medzius jungti minimalaus ilgio briaunomis ir apjungti sujungtus medzius į vieną. Taip atliekama tol, kol nesigauna vienas ekonominis medis.

-38-

R(i). suradus reiksmes A arba B jas pakeisti reiksme C. atliekant sią operaciją vieną kartą , laikas proporcingas masyvo dydziui n, o atliekant n kartu sią operaciją, sudetingumas yra q(n²). Sią duomenu strukturą galima pagerinti naudojant susijusius sąrasus ir apjungiant aibes - mazesnę prijungiant prie didesnes. Čia reikia skirti vidinius aibių vardus nuo isorinių, kurie figūruoja operacijoje APJUNGTI. Sio algoritmo sudėtingumas:

perkeliant elementą is mazesnio sąraso i didesni, jis atsiduria galutiniame sąrase, maziausiai 2 kartus didesniame negu buvo. Todel jokio elemento negalime perkelti daugiau kaip log n kartu, todel laikinai sudetingumas vienam elementui q(log n), o visiems n elementams q(nlog n). Jei atliekama m operacijų RASTI n iki n-1 karto apjungti, tai laikinai sudėtingumas yra q(MASK m,n(log n)), jei m >=nlog n, tai sis algoritmas is tikrųjų yra optimalus, o kai m<<nlog n, tada yra geresni algoritmai.

Aibes galima vaizduoti medziais:

aibė A atvaizudojama neorntuotu medziu T_A , kurio virsūnės - aibės elementai. Sio medzio saknies vardas yra aibės vardas. Tuo atveju operacija APJUNGTI(A,B,C) atliekama sujungiant medzius. Jai A<B , T_A saknį reikia padaryti medzio T_B saknies sūnumi. Be to T_B saknies vardą pakesti i C. Operacija RASTI(i) atliekama einat nuo i- tosios virsunes i medzio sakni, kur yra patalpintas aibes vardas.Čia

-46-

( C )( C )( C ) Parodo kiek kelių yra v_j ir v_i susidedančių is 3 lankų.

|0100| |0110| |0000|

(C)(C)(C) |0000| |0000| |0000|

|0000| |0100| |0000|

|0110| |1100| |0100|

1 rodo, kad tarp v₄ ir v₂ yra kelias susidedantis is 3 laukų, tai v₄ v₁ v₃ v₂ . (C)⁴ rodytų kelių sk. susidedančių is keturių lankų, čia nėra tokių kelių. Kai nėra ciklų, tai gauname nulinę matricą. (C)ⁿ - yra tikslas skaičiuoti iki (C). Toliau bus rodomi tik ciklai. Jei susumuosime visas (C)+(C)²+.+(C)ⁿ+

|10..0|

+ |01..0|

.

|00..1|

matricas, tai gausime kelių sk. is v_i į v_j . Jei atitinkamas elemntas c_ij>0, tai tas rodo, kad yra kelias tarp virsūnių v_i v_j . Matricos (n*n) daugybai reikia atlikti n³ daugybos veiksmų. Matricai (C)ⁿ gauti, reikia ~n⁴daugybos veiksmų. Kartais keliamas uzdavinys surasti ar egzistuoja kelias tarp visų grafo virsūnių. T.y. surasti matricą (L), kurios

l_ij {^{0, jei nėra kelio tarp vi ir vj} _{1, jei yra toks kelias}.

Matom, kad toks uzdavynys gali buti isspręstas dauginant ir sudedant matricas. Grafas atitinkantis susietumo matricą (L) vadinamas refleksiniu -tranzitiniu grafo uzdarymu.

Paaiskinimas (L) matricos radimo algoritmo: Čia visada c^k_ij 1, jei yra daugiau kelių. Todėl 5 op. 1+1 1. T.y. atliekami veiksmai su 0 ir 1. Čia 5 op. atliekamas n³ kartų, nes kartu atliekamas sumavimas.

-28-

Tačiau čia matom, kad generalinio elem. suradimui naudojamas masininis laikas, tai reiskia kad sunaudotas laikas būtų mazas palyginti su tuo, ką islosėm is geresnio aibes skaidymo.Čia -panasu į bin. Paeiską, tik skaidome per pusę. Aibei is 5 medianos rekia 6 palyginimų.

Medianos n/5 grupių radimui reikia 6* n/5 palyginimų.

Medianai is medianų radimui reikia f( n/5 ) palyginimų.

Suskaidymui reikia n-1 palyginimų. Atlikus suskaidymą ir atmetus maziausiai (3n+5)/10 elem, lieka (7n+5)/10 elem, kuriems tolimesniam skaidymui reikia is atitinkaami f( (7n+5)/10 ) palyginimų. Todel uzrasome rekurentinę lygį:

f(n)<f( (7n+5)/10 )+f( n/5 )+6* n/5 +(n-1)

Gavome sudėtingą rekurentinę lygtį, kurią sunku isspresti, tačiau įrodyta, kad : f(n)<=20n. Čia blogiausiaa atvejis ir sudė-tingumas q(n). n elementai uzduoti san-tykiu > . i₁ ,i₂ ...i_k = n. P(i₁ ,i₂ ..i_k ).

Nagrinėjome sio bendro uzdavinio kelis atvejus:

1.maziausio elem, radimas P(1,n-1)=n-1. (palyginimų sk ieskant min =n-1).

2.1-mo ir 2-ro maziausio elem, radimas P(1,1,n-2)=n+ log n -2.

3.maz. ir didz. 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)

-36-

w_ij q_i + (p_i+1 + q_i+1) +(p_i+2 +q_i+2) +...+(p_j+q_j). T_ij turi saknį a_k tada jis turi kairį pomedį T_{i, k-1} į kurį įeina (a_i+1, a_i+2 ,...,a_k-1) ir desinį pomedį T_kj į kurį įeina elementai (a_k+1, a_k+2, ...a_j ) . Faktiskai yra taip :

Gali būti taip ,kad i k-1, tada kairys pomedis tusčias ir gali būti k j, tada desinys pomedis tusčias. Tusčio pomedzio kurio indeksai sutampa T_ii , kaina C_ii 0, o svoris w_ii q_i. Tada galima parasyti taip: C_{i j} w_{i , k-1}+p_k + w_{k j}+C_{i , k-1}+C_{k j} w_{i j}+C_{i, k-1}+C_kj .Faktiskai mums reikia rasti reiksmę , kuri minimizuoja C_{i j} .Kadangi čia figūruoja w_ij , kuri nuo k nepriklauso, tai faktiskai reikia minimizuoti sumą C_{i, k-1}+C_{k, j} . Tai, ieskant optiamlaus medzio T_ij reikia skaičiuoti kiekvienam k , kuris i< k j medzio kainą su saknimi a_k ir pomedziu T_{i, k-1} ir T_{k ,j} .

Sio skaičiavimo algoritmas (1) yra: .....(patys surasit)

Optimalų binarinės paieskos medį sudaro procedura (2) MEDIS( i, j) .... (patys surasit)

Pirmas (1) algoritmas paskaičiuoja visus C_{i j} ir r_{i j} visiem 0 j i n vis didėjant skirtumui j-i . Po to (2) algoritmas prasideda procedūra MEDIS(0,n) ir rekursyviai sudaro optimalų binarinės paieskos medį.

-44-

Stipriai susijusių dalių isskyrimas orentuotame grafe

Stipriai susijusios dalys orentuotame grafe, tai is bet kurios virsūnės egzistuoja kelias į bet kurią kitą. Kiekvienai orentuoto grafo virsūnei skaičiuosime APATRYSYS[v] MIN(U). Čia virsūnių numeracija pagal paiską į gylį, surandant medzius. Virsūnė v orentuoto grafo stipriai susijusios dalie saknis bus tada, kai APATRYSYS[v] v. Atliekant paieską i gyli galima apskaičiuoti APATRYSYS[V], o taip pat isskirti stipriai susijusias dalis, tam grafo virsūnės talpinamos į steką, kai apeinant grafą sutinkamos. Kiekvieną kartą, kai aptinkama stip. susijusios dalies saknis, visos virsūnės iki sios saknies isstumiamos is steko ir jos yra stipriai susijusios dalies virsūnės. Modifikuotos proc. paaiskinimas: APATRYSYS[v] skaičiuojamas 4,9 ir 11 eilutėje 4 operacijoje suteikiama pradinė reiksmė (virsūnės Nr.). 9op. Priskiriam APATRYSYS[v] MIN(APATRYSYS[v], APATRYSYS[w] )-tai lankams įeinantiems į medį. 10 op. isaiskina ar nįeinantis į medį lankas (v,w) yra atbulinis ar skersinis, o tai pat isaiskinama ar w stekui ;priklauso stipriai susijusiai grafo daliai. 11 op. koreguojama reiksmė APATRYSYS[v] MIN(VIRNR[w], APATRYSYS[v] ). Sio algoritmo sudėtin-gumas yra q(MAX(n,e)) - tiesinės, n-virsūnių sk. e-lankų sk.

-26-

Ieskant kito max elemento, reikia a₆ ly-ginti su pralaimėjusiais, randant a₁
Jei a₆ > a₃, tai reikia palyginti ir ar a₆ > a₂

Jei a₆ < a₃, tai reikia palyginti ir ar a₃ > a₆

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 siuo metodu palygi-nimu sk. yra optimalus: n + log n - 2 .

Geriausio (max) ir blogiausio (min) elemento isrinkimas

Galima siūlyti suskaidyti seką n į 2 dalis ir surasyti siose 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 is karto gauname max ir min elementus. Rekurentinė lygtis, aprasanti tokį akgoritmą:

_f(n)=

Bendras sios srities sprendinys:

-34-

parinkus h(a) daznai paskirstymo metodas duoda geresnius rezultatus. Tegul mums reikia atlikti aibeje veiksmus ĮSTATYTI(a,s), PASALINTI(a,s), PRI-KLAUSYTI(a,s) ir MIN(s). pirmiems trims veiksmams gerai tinka paskirstymo metodas, bet jame negalime atlikti MIN(s).Tai visiems siems vieksmams atlikti gerai tinka binarinės paieskos medziai.

Optimalūs binarinės paieskos medziai

Tegul mums reikia daug kartų atlikti tik 1 operacija PRIKLAUSYTI(a,S).a S ir a S. Tegul yra a₁ , a₂ ... a_n S.Uzduotos tikimybes su kuriomis reikes ieskoti atitinkamo elemento p₁, p₂ ,... p_n. q₀-tikimybė ,kad ieskomas elementas a<a₁.

Tikimybė q₁ -tikimybė ,kad reikės ieskoti elemento a, kuris a₁< a < a₂. Ir q_i , kur a_i < a < a_i+1. q_n ,kad reikės ieskoti a, kuris a>a_n. Vadinasi yra uzduotos tikimybes q₀,q₁,...,q_n. p_i+ q_i 1.Reikia sudaryti optimalų paieskos medį ,kuriame vidutiniskai būtų atliekama maziausiai palyginimų, ieskant įvairų elementų su uzduotomis tikimybės.

a₄ 0

a₃ a₅ 1

a₁ 3 4 5 2

0 a₂ 3

1 2

-42-

Toliau rekursyviniai issaukiama ta pati procedūra, kol nepasiekiama grafo lapo. Tada L(v) tusčia ir pereinam prie ankstesnės virsūnės (paskutinės nutrūkusios procedūros). Kai 5 eilutėje paimama virsūnė w, briauna (v,w) talpinam į steką, jei jos ten dar nėra. (v,w) briauna sutinkama 2 kartus, 1 kartą einant į virsūnę v, kur w L(v). 2 kartą, kai einam i virsunę w, nes v L(w). Nustatyti ar briauna (v,w) pateko į steką galima sitaip: jei v<w (w-"sena") arba v>w (w=TĖVAS[v] ). Todėl kai grįztama prie nutrūkusios procedūros paimama sekanti briauna, kuri gali vesti į naują virsūnę arba į seną. Tada 12 ir 13 operacijos pakuoreguoja APAT[v] reiksmę. Sita briauna taip pat patenka į steką. 12 op. pataikrina ar si briauna patekusi į medį.10 op. tikrina ar APAT[w] >=VIRNR[v], jei ne tai 11 op. pakuoreguoja APAT[v]. Jei taip tai reiskia aptikta labiausiai susijusi komponentė, o is steko isstumia briaunas įeinančias į ją (komponentę) ir taip pat isstumiama paskutinė.

Paieska į gylį orentuotame grafe

Naudojant paieskos į gylį grafuose algoritmą orentuotame grafe galima isskirti orentuotų medzių miską, jei kiekvienam mazgui v suskaupsime sąrasą L[v], t.y. pasiekiame virsūnių v aibę per 1 zingsnį.

PAIESKA PAPRASTAME SĄRASE  

1.1. Nuosekli paieska 1

1.2. Paieska interpoliavimas 1

1.3. Binarinė paieska 1

1) Posąrasio ribu nustatymo metodas. 2

2) Posąrasio dydzio nustatymo metodas 3

3) Ribos numeris visada 2 laipsnyje 3

1) Principas - 'Skaldyk ir valdyk' 5

Rekurentinių lygčių sprendimas 6

T Apie rekurentinės lygties tipo 6

Balansavimas (skaidymas į vienodas dalis). 7

Dinaminis programavimas. 8

RŪSIAVIMO ALGORITMAI

K-mačių kortezų rūsiavimas 9

Nevienodo ilgio kortezu rusiavimas 10

Rūsiavimas lyginant elementus "Burb" 11

Iterpimo metodas. 12

Eksper. statistinis algoritm tyrimas 13

Dviejų programų eksperm.- statist. tyrimas 15

Binarinis įterpimo algoritmas 19

Rūsiavimas isrinkimu 19

Rūsiavimas piramide 20

Rūsiavimas suliejimu (sujungimu) 21

Rūsiavimas suskaldymu (quick sort). 22

Optimalus rūsiavimas. 23

ISRINKIMAS

Max element isrinkim is n elementų sekos 24

Sekanč did. element rad. (2-ų max radimas). 25

Ger. (max) ir blog. (min) element isrink 26

k-ojo didesn elem. Isrink[be rusiavimo] 27

Isrinkimas be randomizacijos. 27

Veiksmai su aibemis(DS poziuriu) 29

Kraskalo alogoritmas. 30

Paskirstymo metodas (hesiravimo) 32

Optimalūs binarinės paieskos medziai 34

Operacijų apjungt ir rast atlikimo algoritm 37

Aibes galima vaizduoti medziais: 38

ALGORITMAI GRAFUOSE

Paieska į gylį 40

Grafo labiausiai susijusių dalių isskyrimo algoritmas 41

Paieska į gylį orentuotame grafe 42

Stipriai susijusių dalių isskyrimas orentuotame grafe 44

Grafų susietumo matrica. 45 Trumpiausio kelio radimas 47

Uzdavinys su vienu saltiniu ( Deiks-tros algoritmas) 48