Algoritmai

InformacijaInformacija – žinios, vienų asmenų perduodamos kitiems raštu, žodžiu, masinės komunikacijos priemonėmis. Informacijos klasifikacija: elementarioji, genetinė, biologinė, semantinė, kompiuterinė (semantinės dalis skaitmeniniu pavidalu). Dėsniai: pokyčiai laike, nėra adityvumo (A+A= A), nėra komutatyvumo, turinys nepriklauso nuo saugojimo ir pateikimo (nebent skirsis suvokimo greitis).Informacijos kiekis auga eksponentiškai lyginant su gamybos apimtimi. Informacija perduodama pranešimu, pranešimas siunčiamas signalu (kalba, raštas, šviesa, srovė, …). Signalas turės prasmę tik tada, jei jį sugeba priimti gavėjas. Signalas – priemonė pranešimams perduoti. Tokiu atveju priimantysis ką nors sužino. Vadinasi, informacija yra nežinojimo priešingybė. Informatyvumo daugiaprasmybės (mat. analizė). Nevienoda žmogaus jutimo organų priėmimo galia.Kadangi informacija – neapibrėžtumo priešingybė, apie jos dydį būtų galima spręsti iš neapibrėžtumo sumažėjimo. Tarkime, informacijos šaltinis gali siųsti vieną iš vienodai svarbių ir vienodai tikėtinų pranešimų. Žinoma pranešimų aibė (gyvenimiškai – bus suprastas), bei žinoma, kad pranešimas siunčiamas. Tada neapibrėžtumo funkcija E (ji priklauso tik nuo N) yra monotoniškai didėjanti. Imtuvas priims pranešimą, neapibrėžtumas išnyks. Gauta informacija gali būti prilyginta buvusiam neapibrėžtumui. Jei galimas tik vienas pranešimas, tai jo turinys žinomas iki atsiuntimo ir nieko naujo neatneša. E(1) = 0.Tegul siunčia du šaltiniai, kiekvienas turi po N skirtingų. Galimų porų skaičius N2. Du vienodi šaltiniai turi sukurti dvigubai didesnį neapibrėžtumą, tada E(N2) = 2E(N). Sprendinys – log. Jei pagrindas 2, gausime neapibrėžtumo matą log2N bitais. Natūriniu logaritmu išreikštas matas yra natas. Logaritminį matą nagrinėjo Hartley 19a trečiam dešimtmetyje, vėliau, po II pasaulinio karo bendresnį, entropiją, nagrinėjo Shanon savo ryšio teorijoje. Gautų žinių kiekis priklauso nuo skaitytojo (patirtis, suvokimas), informacijos matas turi būti objektyvus. Pradinis matas – raidė, jos kodavimas kompiuteriu. Baitas, 2 baitai (Unicode). Analoginė ir diskrečioji informacija (8000*8000 taškų – žmogaus akis). Laidais efektyviau perduodama analoginė informaciją.EntropijaVienodai tikėtinų pranešimų atveju neapibrėžtumas buvo nusakytas E(N). Priimtas pranešimas panaikina neapibrėžtumą I(p) = E (1/p) = -log(p), (1) čia p=1/n yra pranešimo tikimybė. Kuo mažiau tikėtinas pranešimas, tuo didesnė informacija. Tarkime, vieno pranešimo tikimybė p, kito – q. tikimybė juos gauti paeiliui lygi pq, informacijos kiekis: I(pq) = – log(pq) = I(p) + I(q), o tai atitinka intuityvų reikalavimą, kad nepriklausomų šaltinių informaciją reikia sumuoti. Kadangi pranešimas priėmėjo požiūriu atsitiktinai išrinktas, tai gaunamos informacijos kiekis taip pat atsitiktinis, su tikimybe pi gaunam –log(pi) informacijos. Gaunamos informacijos kiekis, išreiškiantis šaltinio neapibrėžtumą (vadinamą entropija) išreiškiamas formuleE(P) = , P = (p1, … pN)Panašiai ir statistinėje fizikoje. Yra ir kitų apibrėžimų. Atskiru atveju, kai visos tikimybės 1/N, gauname entropiją išreiškiamą log(N). Intuityviai didžiausia – kai tikimybės lygios – entropija maksimali. Vadinasi, entropija intuityviai sutampa su neapibrėžtumu.Dviejų pranešimų su tikimybe ½ entropija lygi 1. Vadinasi, vienas bitas – iš semaforo. Šviesoforo (049 002 049) lygus 1,12 bito (skaičiuojama dvejetainių logaritmų suma) – įrodykite.Max = 3, kai tikimybės vienodos. Perdavimo trikdžiai. Statistinis nagrinėjimas. Iš statistikos – informacijos suspaudimo būdai.Algoritmai783-850 metais (dabartinė Chiva Uzbekijoje) gyveno Abu Jafar Mohamed ibn Musa al Chorezmi (Iš Chorezmo). Jis parašė veikalą Kitab Al Džebr val Mukabala – atstatymų ir perstatymų knyga, iš čia algebra.O dar parašė traktatą apie indiškąją (arabiškąją) skaičiavimo sistemą, veiksmus stulpeliu.Al Chorizmi – algorism – algoritmas. Pradžioje – veiksmai su dešimtainiais skaičiais, vėliau ir bet kurie.

Grįžkim prie informatikos problemų. Apytiksliai kalbant, spręsti tokias problemas mes pradedame nuo duotos informacijos, duomenų (duotų ar įvestų) ir stengiamės iš jų sukurti rezultatą, kuris pageidaujamu būdu susijęs su pradiniais duomenimis. Panagrinėkime paprastus pavyzdžius:1. 2 sveikų skaičių daugyba: Duomenys – 2 natūriniai skaičiai, rezultatas sveikas skaičius, šių dviejų sandauga.2. 2 lygčių sistema. Duomenys 6 realūs, a11, a12, a21, a22, b1, b2, sąlyga– diskriminantas ≠0. Rez 2 skaičiai x1 ir x2 tokie, kad a11x1+ a12x2=b1 ir a21x1+ a22x2=b2 . 3. Rūšiavimas. Duomenys simbolių eilučių masyvas, rezultatas- irgi tik žodyno tvarka.Matosi, kad iš duomenų gaunam rezultatą. Atidžiau, pastebim, kad sprendžiam ne vieną problemą, o jų klasę, mes ieškom tokių sprendimo metodų, kurie veiks vienodai su visais šios klasės uždaviniais. Yra daugybė atskirų uždavinių, kuriuos galima būtų išspręsti daug gražiau, protingiau, jei nagrinėtume tik specialius duomenų atvejus. Beje, dažnai tokie atvejai būna įdomūs, naudingi mąstymo treniruotei. Tačiau kartu svarbu yra rasti bendrus sisteminius sprendimo metodus, kurie duos pageidaujamą rezultatą visiems teisingiems duomenims. Tokį bendrą sisteminį metodą dažnai vadiname algoritmu.Mes (jūs), būdami kompiuterių specialistais algoritmą dažnai tapatiname su programos sąvoka, tačiau terminas plačiau pradėtas naudoti 1930 metais, prieš kompiuterį. Prieš pradedant nagrinėti kokį nors objektą, jį reikia apibrėžti. Kalbant apie algoritmus, dažnai vartojama artima programos sąvoka. Kai kurie vadovėliai šias sąvokas interpretuoja kaip abstraktaus ir konkretaus priešybę: algoritmas – griežtai ir vienareikšmiškai apibrėžta veiksmų seka, o programa – algoritmo realizavimas kuria nors programavimo kalba. Tačiau toks algoritmo apibrėžimas ne visai korektiškas, kadangi griežtumo ir vienareikšmiškumo reikalavimai patys savaime nėra vienareikšmiai. Kita vertus, programavimo kalba užrašyta ‘programa’ atitinka griežtumo ir vienareikšmiškumo reikalavimus, keliamus algoritmui. Programavimo kalbos – vienas iš būdų algoritmams užrašyti. Nors kai kuriais atvejais algoritmą lengva suformuluoti ir bendrine kalba, tačiau teoriniams tyrimams reikia specialių algoritmų užrašymo formalizmų, kaip pavyzdžiui: RAM, Turing’o ir Post’o mašinos, Markovo algoritmai, lambda skaičiavimas.Bandykim pradžiai intuityviai aptarti algoritmo sąvoką. Turbūt galvojam, kad algoritmas turėtų būti trumpas ir aiškus problemos sprendimo metodo aprašymas, o pasąmonėje dar jaučiam, kad jis turėtų būti tinkamas mechaniniams įrenginiams (ką reiškia – griežtumas, minimalus pasirinkimų sk.). Tada plačiau galėtume sakyti, kad algoritmas turėtų būti aiškių suprantamai aprašytų žingsnių seka, reikalinga problemai išspręsti, o pasąmonėje vėl jusime, kad ta seka turi būti baigtinė (o dar baigtinė – lyginant su žmogaus gyvenimo trukmės matavimo vienetais). Kadangi įsivaizdavome, kad ta seka galėtų kažkokiu būdu būti vykdoma mechaniškai, galėtume reikalauti, kad nei vienas žingsnis nepriklausytų nuo subjektyvių sprendimų, intuicijos, kūrybiškumo.Teoriniam tyrimui svarbu, kad minimaliu elementarių veiksmų kiekiu būtų realizuojamos aritmetinės ir loginės operacijos. Kuriant programavimo kalbas siekiama, kad programuoti būtų patogu, todėl jose gausu pertekliškų elementų. Tai apsunkina jomis užrašytų algoritmų teorinius tyrimus.Gali iškilti klausimas, kodėl algoritmams formuluoti nepasinaudojus gerai žinomomis matematikos formulėmis. Skirtingai nuo įprastų matematikos objektų, algoritmas turi semantinę paliepimo prasmę: algoritmas turi būti įvykdytas, ir ‘… algoritmų teorija galėtų būti traktuojama kaip liepiamųjų sakinių lingvistika’ [29]. Matematinėje formulėje jokių dviprasmybių nesukeltų skaičius , pakeltas laipsniu e, nes toks iracionalusis skaičius egzistuoja. Bet, norint kompiuteriu apskaičiuoti šios formulės reikšmę, iškiltų klausimas, kaip tai padaryti. Visų pirma, kaip kompiuteryje turi būti atvaizduoti skaičiai  ir e, ypač tuo atveju, kai reikalaujamas ženklų skaičius didesnis už kompiuterio žodžio ilgį.Veiksmų su apytiksliais skaičiais rezultatai kartais gali apskritai neturėti prasmės, nes labai daug kartų pakartojus veiksmą, paklaida gali nepriimtinai išaugti, net jeigu vieno veiksmo paklaida yra labai maža. Žinoma atvejų (pavyzdžiui, atmosferinius reiškinius aprašant netiesinėmis diferencialinėmis lygtimis), kai rezultatą nepaprastai veikia duomenys. Pakitus duomenims tik tūkstantųjų procento dalių dydžiu, rezultatas gali pasikeisti daug kartų. Tai vadinamasis peteliškės efektas, kurį galima nusakyti taip: kažkur Europoje peteliškė mostelėjo sparneliu, o rezultatas – taifūnas Ramiajame vandenyne. Šis pavyzdys rodo, kad net griežtai matematiškai suformuluoto uždavinio, turinčio vienintelį sprendinį, algoritminio sprendimo galimybės ne visada aiškios. Vadinasi, reikia matematinių tyrimų, kol uždavinio sprendimas galės būti atvaizduotas kompiuteryje leistinais veiksmais ir skaičiais.Pusiau formalus apibrėžimas: algoritmas yra baigtinė seka instrukcijų, reikalingų užduoties sprendimui; instrukcijas turi vykdyti skaičiavimo agentas, kuris veikia diskretiniu žingsniniu būdu, nenaudodamas tolydinių metodų ar analoginių įrenginių; instrukcijos turi vykdomos griežtai apibrėžta tvarka, o ne tikimybiškai. Kartais į tokį apibrėžimą įtraukiame reikalavimą, kad agentas turi turėti galimybę išrinkti, įvykdyti, išsaugoti sprendimo žingsnius.Tam, kad šis apibrėžimas būtų formalus, reiktų apibrėžti skaičiavimo agento sąvoką. Nors tai ir padaryta, bet laikoma, kad apsieisim be jo – būtu perdaug didelis abstrakcijų lygis.Nors visas šis apibrėžimas apsieina be kompiuterio sąvokos, tačiau bus lengviau galvoti, kai bent jau jausim kompiuterį fone. Tada “baigtinė instrukcijų seka” galėtų reikšti kompiuterinę programą, agentas – kompiuterį, “išrinkimas, padėjimas” – atmintį, diskretiniai duomenys ir žingsniai gali būti vykdomi skaitmeniniu (ne analoginiu) kompiuteriu.Reziumuodami, kas buvo pasakyta, algoritmą galime apibūdinti kaip vienareikšmiškai apibrėžtą baigtinę veiksmų seką, kuria bet kokiems duomenims (iš leistinos duomenų aibės) gaunamas prasmingas rezultatas. Algoritmas yra (kompiuteriu atliekami) veiksmai, kuriais duomenys transformuojami į rezultatą, o ne bet kokia baigtinė, kad ir vienareikšmiškai apibrėžta, veiksmų seka.Iš apibrėžimo seka algoritmo savybės:1. Baigtinumas: žingsnių seka turi baigtis po baigtinio žingsnių skaičiaus.2. Apibrėžtumas. Nepriklausomai nuo nusakymo būdų duomenys ir rezultatai turi būti vienareikšmiai (gali būti aibė, bet negali būti atsakymas “taip arba kitaip”3. Duomenys. Kokie nors (geriau, kad juos būtų įmanoma atvaizduoti kompiuteriu) duomenys iš leistinosios aibės, pvz.: masyvas, riboto dydžio, ribotų skaičių dydžio. Atskiru atveju duomenų gali nebūti.4. Rezultatai. Objektai (geriau, kad juos būtų galima atvaizduoti kompiuteriu), priklausantys nuo pradinių duomenų. Rezultatai turi būti perduodami vartotojui (geriau kompiuteriniu būdu).5. Efektyvumas. Kiekvienas žingsnis turi būti įvykdytas per baigtinį laiką. Negali būti žingsnis “išspręsti netiesinę lygtį”, gali būti “sudauginti”.Užduotis n.d.: paimti kokį kulinarinį receptą, įrodyti, kad tai algoritmas arba priešingai.Didelei daliai algoritmavimo uždavinių užtenka veiksmų su sveikaisiais skaičiais (tikslu, nesikaupia paklaidos), ir baigtinėmis aibėmis. Ta algoritmų teorijos dalis daugiausiai ištyrinėta, t.y., diskrečiosios matematikos užduoties nagrinėjimas. Algoritmų užrašymui naudojami formalizmai, kad galima būtų lengviau nagrinėti, vertinti. Blokinės schemos, specialios kalbos. Neimsim blokinių schemų (sunku didžiuliams uždaviniams), neimsim kalbos WHILE, kuri atmeta kint aprašus, begin, end, rašysim fragmentus Paskaliu.Ar algoritmas yra įrenginys (hardware), ar programa (software)?Nors šis klausimas panašus į klausimą apie viščiuką ir kiaušinį, reiktų jį aptarti, nes dalyje literatūros dominuoja tik kuris nors vienas aspektas. Pvz.: sakoma “Tiuringo mašina”, nors tokia gamtoje neegzistuoja, Tiuringo argumentai atitinka realių mašinų būvius.“Mašininis” supratimas sako, kad algoritmas yra mechanizmas pageidaujamiems veiksmams (skaičiavimams) realizuoti. “Instrukcijų aibė” yra šios mašinos architektūros specifikacija. Bet kuriuo laiko momentu mašinos būvis sutampa su vykdoma instrukcija. Didesni algoritmai sutampa su didesnėmis mašinomis. Begalinė atmintis (reikalinga, norint supaprastinti teorinius tyrimus) realizuojama keliais būdai:a) begalinė į abi puses Tiuringo mašinos juosta;b) neapibrėžtai plečiama mašina;c) nelimituotai jungiamos baigtinės mašinos.Programinis supratimas sako, kad algoritmas yra veiksmų seka (pvz.: programa kuria nors programavimo kalba). Skaičiavimo agentas ją vykdo pažingsniui (interpretuoja); savo ruožtu agentas gali būti ir mechanizmas ir programa (pvz.: Basic interpretatorius). Interpretatorius perkėlinėja žymeklį į vykdomą instrukciją iš duoto algoritmo instrukcijų rinkinio, tuo pačiu pakeisdamas atmintyje esančią informaciją pagal vykdomą komandą. Didesni algoritmai suprantami kaip didesnė instrukcijų aibė, bet tas pats interpretatorius.Pirmasis automatinis kompiuteris buvo fon Noimano mašina su atmintyje esančia programa. CPU, atskirta atmintis, jungiamieji įrenginiai. Kaip ir daug kur dabar.Tačiau mikroschemos daro tai mažiau suprantama, nes sukuriama mažytė mikroschema, kuriam nors specifiniam uždaviniui spręsti, t.y. algoritmas.Galvosim apie programinį modelį.Algoritmų (programų ir jų sistemų) projektavimasUžsakovas (sponsorius), užduoties paruošėjas (algoritmo kūrėjas), programuotojas (gali būti tas pats).1. Užduoties dekompozicija pagal duomenis, pageidaujamus rezultatus.2. Formalios specifikacijos (reikalavimų formulavimas). Kiekviena funkcija turi turėti aiškias pradines sąlygas ir aiškų rezultatą.3. Funkcinis rišlumas: vienintelis tikslas, išreiškiamas paprastu sakiniu. Funkcija daranti darbus A, B, C – nebus panaudojama, jei reiks tik A.4. Sąsajos aiškumas: duomenys ir rezultatas tik argumentų sąraše.5. Laisvas jungimas (kaip 4) – be globalių kintamųjų.6. Informacijos slėpimas. Vidinės detalės nežinomos (a. sąsaja, b. pre ir post conditions)Algoritmų sudėtingumasKaina = (sukūrimo, t.y., supratimo ir programavimo kaina) + (vykdymo kaina) = (programa, software) + (įrenginys, hardware)Įrenginio (hardware) kaina = (vieno vykdymo kaina) * (planuojamas vykdymų skaičius).Iš šių formulių seka, kad vienkartiniame kūrinyje dominuoja pirmoji kainos dalis. Matyt, tokiu atveju geriausia naudoti suprantamą, lengvai programuojamą algoritmą, netgi jei jis naudoja daug kompiuterio resursų. Tačiau, jei algoritmas bus naudojamas daug kartų, tada geriausia įdėti kiek daugiau pastangų ir užprogramuoti sudėtingesnį algoritmą, jei matosi, kad jis efektyvesnis kompiuterio resursų atžvilgiu.Galų gale mums kyla klausimas: Kaip palyginti dviejų algoritmų efektyvumą?Galima būtų galvoti apie programų vykdymo laiko matavimą. Bet tai priklauso nuo pasirinkto kompiuterio, ir, žinoma, reikalauja, kad abu algoritmai būtų įdiegti.Galima būtų galvoti apie algoritmą realizuojančios programos dydį (eilučių ar komandų kiekį), bet šis matas priklauso nuo programuotojo kvalifikacijos, pasirinktos programavimo kalbos, ir dar reikalauja abiejų algoritmų realizavimo.Vadinasi, reikia turėti algoritmų efektyvumo matavimo būdą, kuris nepriklausytų nuo kompiuterio, programavimo kalbos ar programuotojo, o tik nuo paties algoritmo.Viena galimybė – turėti formaliai apibrėžtą abstraktų įrenginį, kuris atsiribotų nuo kompiuterių architektūros ypatumų bei programavimo kalbų. Pavyzdys – Tiuringo mašina (TM), naudojama daugelyje informatikos mokslo darbų. TM atmintis – į abi puses begalinė juosta, padalinta į sekcijas, numeruojamas sveikais skaičiais. Kiekvienoje sekcijoje gali būti užrašytas vienas iš TM abėcėlės simbolių. Rašyti/skaityti galima tik į ar iš apžvelgiamos sekcijos, t.y., sekcijos, virš kurios TM galvutė. Galvutė gali būti vienoje iš kelių būsenų iš aibės Q. Priklausomai nuo galvutės būvio ir skaitomo simbolio galvutė pereina į naują būvį ir pasislenka kairėn, dešinėn arba lieka vietoje. TM programos sudarytos iš komandų, kiekviena komanda iš 5 elementų: Esamas būvis| apžvelgiamas simbolis| naujas būvis| naujas simbolis| judesio kryptis.Programa sustoja, kai galvutės būvis sutampa su vienu iš finalinės aibės būvių.Q0,1,q1,1,K.Garsi Church-Turing tezė skelbia, kad teorija, pagrįsta TM ir panašiais modeliais sprendžia tą pačią uždavinių klasę.Pagrindinė problema – tokiems užrašymams nagrinėti reikalingas vos ne atskiras mokslas, algoritmus sunku užrašyti ir skaityti.Savo analizei pasirinksim tarpinį variantą: rašysim programas, po to jose ieškosim kažkokių bazinių operacijų, susijusių su sprendžiama problema. Bazinėmis operacijomis gali būti:a) jei programuojame paiešką, bazinėmis operacijomis galime laikyti ieškomojo objekto palyginimus su kolekcijoje esamais objektais;b) jei dauginam dvi skaitines matricas, bazinė operacija bus dviejų skaičių daugyba;c) jei dėliojame kokį nors įrašų rinkinį pagal sutvarkytą raktų rinkinį (rūšiuojame), galime galvoti arba apie dviejų raktų palyginimo operaciją (kuris pirmesnis pagal eilę) arba apie dviejų įrašų sukeitimą vietomis.Jei turime užduotį, kurios sprendimui egzistuoja keli algoritmai, galime juos vertinti pagal bazinių operacijų skaičių, galim tikėti, kad didesnio operacijų skaičiaus algoritmui reiks daugiau darbo (programavimo, kompiuterio). Pakeliui pažymėkime, kad gali būti kiek kitaip, atsižvelgiant į operacijų specifiką. Pvz.: nors ir daug daugybų, bet greičiau dauginama iš 0 ir 1.Problemos realizacijai matavimo vienetas gali būti įvairus: pvz.: paieškos problemai galime imti rinkinio elementų skaičių, kvadratinių matricų daugyboje – dydį, lygčių sistemoje – lygčių kiekį.Rimtoji dalis. Sakykime, kad turim užduočių klasę, kiekvienos iš jų dydį galime vertinti sveikuoju n≥0. Galimi du algoritmo sudėtingumo apibrėžimo būdai:1) Kiekvienam n nagrinėjame visus n dydžio užduoties atvejus. Kiekvienam atvejui i (instance) randame darbo, atliekamo algoritmu, kiekį T(i). ApibrėžiameW(n) = max T(i) visiems n dydžio atvejams i.Funkciją W(n) vadinsime blogiausio atvejo sudėtingumu.2) Kiekvienam n nagrinėjame visus n dydžio užduoties atvejus. Sakykime, kad iš patirties, ar iš kokios specialios informacijos, ar patys begalvodami nustatėme kiekvieno atvejo tikimybę p(I). ApibrėžiameA(n) = ∑ p(i)•T(i) visiems n dydžio atvejams i.Funkciją A(n) vadinsime vidutiniu sudėtingumu.Galimas ir geriausio atvejo sudėtingumo matavimas, bet jis mažai parodo apie patį algoritmą.Tegul turime algoritmus P1 ir P2 tai pačiai problemų klasei su blogiausio atvejo sudėtingumais W1 = 100n ir W2 = 4n2. Kai n< 25 W1(n) > W2(n), n>25 W2(n) > W1(n) – elgesys priklauso nuo pradinių duomenų.Tegul suradom dar trečią algoritmą P3 su W3(n) = 10000n. Aišku, jei P1 veiks tame pat kompiuteryje, kur ir P3, P3 ilgiausias laikas (priklausantis nuo pradinių duomenų) visada bus ilgesnis, nei P1. Tačiau jei P3 veiks 1000 kartų greitesniame kompiuteryje, jo laikas bus mažesnis. Matosi, kad sunkiau nagrinėti funkcijas, kurių kitimo tempai nevienodi.Kelių funkcijų augimo tempaiTegul f ir g yra dvi teigiamos realios f-jos, apibrėžtos visiems n>0. Sakysime1. g yra O(f) arba g(n) yra O(f(n)), jei g nuo kažkurios vietos bus mažesnė nei konstanta padauginta iš f(n), t.y., jei egzistuoja realusis K>0 ir sveikasis n0 tokie, kad g(n) ≤ K*f(n) visiems n≥ n0. 2. g yra (f) arba g(n) yra (f(n)), jei g nuo kažkurios vietos bus didesnė nei konstanta padauginta iš f(n), t.y., jei egzistuoja realusis K1>0 ir sveikasis n1 tokie, kad g(n)≥ K1*f(n) visiems n≥ n1.3. g yra (f) arba g(n) yra (f(n)), jei g nuo kažkurios vietos bus tarp dviejų konstantų padaugintų iš f(n), t.y., jei egzistuoja realieji K, K1>0 ir sveikasis n0 tokie, kad K f(n) ≤ g(n) ≤ K1*f(n) visiems n≥ n0.Jei g yra O(f), bet f nėra O(g) sakysime, kad O(g) yra geriau nei O(f). Šiuo atveju algoritmas su blogiausio atvejo sudėtingumu g pakankamai dideliam matui veiks greičiau, nei f. Sakoma, kad algoritmas yra efektyvus, jei jo blogiausio atvejo sudėtingumas yra O (nk) teigiamiems k.Keli palyginimo metodai (suprantantiems ribas):1. Jei lim g(n)/f(n) = c ≥ 0, tada g yra O(f). c-1 < g/f < c+1 g<(c+1)f.2. Jei lim g(n)/f(n) = c > 0 arba = , tada g yra  (f).1/2c < g/f < 3/2c g > 1/2f jei lim g/f = , galime matyti, kad g/f>1, g>f.3. Jei lim g/f = c, 0 < c < , tada g yra  (f)Įrodymas iš 1 ir 2. Jei lim g/f = c, tai lim f/g = 1/c. g yra O(f) ir f yra O(g). Bet jei lim g/f = 0, g yra O(f), bet f nėra O(g). Šiuo atveju g yra geriau, nei f.(Įrodymas iš atvirkščio teiginio: tegul f yra O(g). tada f ≤ Kg visiems n>n0, k>0. Tada g/f ≥ 1/K, kai n>n0; vadinasi lim g/f ≠ 0.Kelios formulės: = 0; 0; 0 jei p0.TadaO(log2n) geriau negu O(n)O(n) geriau nei O(nlog2n)O(nlog2n) geriau negu O(n2)O(np) geriau nei O(ng), p0Tegul turime algoritmą su blogiausio atvejo sudėtingumu W(n); jo bazinių operacijų vykdymo laikas . Jei turime laiką T, uždavinio, išsprendžiamo per laiką T dydį (pradinių duomenų matą) galime rasti iš lygties W(n)  =T.= 1ms, W(n) = n2, T = 1 valn2*10-3=60*60 (sek)n2 = 6*105, n = …Tegul mašina k greitesnė, tada bazinės operacijos laikas yra /k. Jei laikui T max matai yra n1 ir n2, tada W(n1)  = T = W(n2) /k reiškia W(n2) = k W(n1).Pvz.: jei W(n) = 2n, 2n2=k2n1, n2 = n1 log2k.Kuriant algoritmus svarbu analizuoti jų sudėtingumą W, A ar abu. Techniniu požiūriu aiškėja, kad efektyvūs algoritmai turi turėti sudėtingumą O(nk), geriau, kai k mažesnis – tik tokiems algoritmams uždaviniai išsprendžiami praktiškai, jei n didelis.Ne viską lemia sudėtingumas – prisiminkim skyriaus pradžią. Dar reiktų pagalvoti, kad efektyvias, bet didžiules programas sunku prižiūrėti, ypač, jei tą daro ne autorius.n.d. f(n) = 4n3-3n2+2n-1, natūriniams n>0.Kokiems k galima sakyti, kad:F yra O(nk)F yra (nk)F yra (nk)Matricų n*n daugybaFor I = 1 to n do For j=1 to n do Begin C[I,j]:=0; For k=1 to n do C[I,j] = c[I,j] + A[I,k]*B[k,j] End W(n) = O(n3)Vienetukų uždavinysSakysim, duomenys yra n dvejetainių vienetų eilutė B = bn,…,b1. Uždavinys: apskaičiuoti, kiek yra vienetukų eilutėje. Nesigilinsime į tai, kokia duomenų struktūra taikyta eilutei užrašyti, ir sakysim, kad galime tiesiogiai skaityti bet kurio eilutės elemento reikšmę. Labai akivaizdus algoritmas vienetukams suskaičiuoti būtų toks:c:=0i:=nwhile i > 0 do i:=i – 1 if bi = 1 then c:=c+1 endAkivaizdu, kad tokio algoritmo vykdomų operacijų skaičius proporcingas n. Galima nesunkiai sumažinti algoritmo vykdomų ciklų kiekį, praplečiant galimų operacijų aibę:c:=0A:=Bwhile A<>0 do A:=(A – 1)  A c:=c+1 endčia su dvejetaine eilute atliekama aritmetinė atimties operacija kaip su sveikuoju skaičiumi ir loginė operacija ir () kaip su dvejetainiu kodu. Jei pirmojoje algoritmo versijoje operuojama tik su atskirais eilutės elementais, tai antruoju atveju atliekamos operacijos lygiagrečiai su visomis eilutės kaip dvejetainio kodo skiltimis. Įsitikinkite, kad algoritme vartojama loginė operacija pakeičia patį dešinįjį vienetuką nuliu. Suprantama, kad aritmetinis įrenginys, atliekantis tokias operacijas, turi būti sudėtingesnis negu tas, kuris atlieka tik pirmajai algoritmo versijai reikalingas operacijas. Antrosios algoritmo versijos atliekamas ciklo kartojimų skaičius priklauso nuo duomenų. Blogiausiu atveju, kai eilutėje yra tik vienetukai, ciklas kartojamas n kartų. Bet ciklo operacijos būtų vykdomos tik kelis kartus, jei toks būtų vienetukų skaičius duomenų eilutėje.

Trečiąją algoritmo versiją lengviau paaiškinti pavyzdžiu negu formaliai užrašyti. Jai realizuoti reikalingos tam tikrų kodo skilčių išskyrimo ir kodo postūmio 1, 2, 4,… skiltimis operacijos. Panagrinėkime pavyzdį: B=11010001, t.y. eilutė susideda iš 8 skilčių. Pirmoji operacija tokia: sudarykime eilutę N, neliesdami nelyginių eilutės B skilčių ir pakeisdami lygines eilutės B skiltis nuliais: N=01010001. Sudarykime eilutę L, paimdami lygines eilutės B skiltis, prirašydami joms iš kairės 0 ir jas pastumdami per vieną skiltį į dešinę: L = 01000000. Dabar sudėkime gautas eilutes pagal dvejetainių skaičių sudėties taisykles; gausime 10010001. Duomenis ir rezultatą užrašykime skilčių poras atskirdami tarpais:B = 11 01 00 01N+L = 10 01 00 01,Nesunku pastebėti, kad rezultato skilčių pora yra dvejetainis skaičius, lygus vienetukų skaičiui (dvejetaine forma) atitinkamoje eilutės B skilčių poroje. Dabar pakartokime operaciją, išskirdami lygines ir nelygines eilutės N+L poras: N = 00010001, L = 00100000 (imamos poros, pridedami 2 nuliukai). Sudėję N ir L ir užrašę eilutės B ir gauto rezultato skilčių ketvertukus su tarpais matysime,1101 00010011 0001,kad antrosios eilutės skilčių ketvertukai reiškia eilutės B skilčių ketvertukuose esančių vienetukų skaičių. Paėmę lyginius ir nelyginius rezultato ketvertukus, sudarysime eilutes N = 00000001, L = 00000011, kurias sudėję, gausime uždavinio atsakymą – dvejetainę skaičiaus 4 išraišką 00000100. Iš tikrųjų, eilutėje B yra 4 vienetukai. Esant eilutės ilgiui n=2K, tokių ciklų reikia K, taigi algoritmo vykdymo laikas proporcingas log n.Pirmosios algoritmo versijos cikliškai kartojami veiksmai labai paprasti. Antrosios versijos jau sudėtingesni, o trečiąją versiją programuojant tektų ir galvą pasukti. Akivaizdu, kad šių algoritmų vieno ciklo vykdymo laikai skirtingi. Tačiau lyginant algoritmų vykdymo laiką dideliems n ir nulems tas faktas, kad log n auga daug lėčiau, nei tiesinė n funkcija. Jeigu antrosios algoritmo versijos realizavimas ir nesukeltų ypatingų problemų standartinei kompiuterio komandų sistemai, kai dvejetainė eilutė telpa į mašininį žodį, tai trečiosios versijos realizavimui, matyt, reikėtų projektuoti specialią mikroschemą. Ar galima sudaryti dar greitesnį algoritmą? Jei uždavinys turi būti sprendžiamas labai daug kartų ir svarbus jo greitis, tada paruošiamųjų darbų laiką galima ignoruoti. Todėl visus galimus atsakymus galima apskaičiuoti iš anksto ir surašyti į atmintį adresais, sutampančiais su atitinkančia dvejetaine eilute, pvz.:Adresas Reikšmė000001010011100101110111 01121223

Prireikus sužinoti, kiek yra vienetukų kurioje nors dvejetainėje eilutėje, rezultatas tiesiog skaitomas iš atminties adresu, sutampančiu su ta eilute. Algoritmo sudėtingumas skaičiavimo laiko prasme nebepriklauso nuo duomenų dydžio! Atsakymas gaunamas per laiką, reikalingą skaičiui iš operatyviosios atminties nuskaityti. Tačiau paskutinysis algoritmas reikalauja labai didelės atminties.Šiuo paprastu pavyzdžiu iliustruojami svarbūs algoritmo sudėtingumą apsprendžiantys faktoriai: 1. Uždavinio sprendimo laikas priklauso nuo to, kokios leistinos operacijos algoritmui sudaryti. 2. Skaičiavimo resursai – laikas ir atmintis, dažnai pakeičiami, t.y., aukojant laiką, galima sutaupyti atminties, ir atvirkščiai. 3. Lygiagretus duomenų apdorojimas gali gerokai pagreitinti uždavinio sprendimą.Rūšiavimo algoritmaiTegul turime duomenų rinkinį E. Kiekvienas jo narys gali būti sudarytas iš kelių informacijos porcijų. Tegul kiekvienas narys turį raktą, priklausantį sutvarkytai aibei K. (Sutvarkytos aibės reikalavimai: santykis <, nariai susiję šiuo ženklu). Rakto prasmė nebūtinai turi būti žinoma, pagrindinė paskirtis – pagreitinti pasiekimą. Daug lengviau ieškoti sutvarkytoje aibėje. Išvada: dažnai naudojamus duomenis reikia saugoti tvarkingai.Artėkim prie Paskalio:Type K = (* tvarkingas tipas vardinis?*) T= record Key: K;. … (kiti laukai); E: kolekcija of T.Kolekcija E gali būti nedidelė. Tada galvotume apie jos saugojimą operatyviojoje atmintyje: masyvas. Jei viršija OA galimybes, tada galvotume apie failą, o jį saugotume išorinėje atmintyje: diskas, CDROM, juosta…

Masyvuose saugojamų rinkinių rūšiavimo algoritmai vadinami vidiniais, failuose: išoriniais.Matuodami rūšiavimo algoritmų sudėtingumą, užduoties dydžio matu laikysim E elementų skaičių. Bazinėmis operacijomis galime vadinti raktų palyginimus arba elementų sukeitimus.Nagrinėkime tuos rūšiavimo metodus, kurie naudoja raktų palyginimus. Tokį algoritmą galim pavaizduoti dvejetainiu medžiu, kurį galime vadinti alternatyvų medžiu (decision tree). Kiekvienas mazgas (ne lapas) atitinka dviejų raktų k1 ir k2 palyginimą. Susitariam, kad kai k1<= k2, pereisim į kairįjį “vaiką”. Schema

Blogiausio atvejo sudėtingumas šiuo atveju yra maksimalus palyginimų skaičius, t.y., medžio aukštis. Jei rinkinyje E yra N elementų, gali būti N! galimų variantų (medžio lapų). Nagrinėdami medžius (vėliau) matome, kad h aukščio medyje gali būti max 2h lapų. Jei h yra mūsų alternatyvų medžio aukštis, 2h ≥ N! ir W(n) =h ≥ log 2 (N!).Jei n>0 – lyginis n=2k,n! ≥ (2k)*(2k-1)…(k+1)*k >kk+1 ≥ kk =

Kai n=2k+1n! ≥ …(k+1) > > = Vadinasi, kiekvienam n>0 n! > ir log2(n!) > Kai n≥4, ≥1, log2 = log2(n)-1≥ log2(n)Kai n≥4:W(N)≥ log2(N!)≥ N log2NBlogiausio atvejo sudėtingumas yra (N log2N).Algoritmų sudarymasLengviausia sudaryti algoritmą, kai uždavinys užrašytas aritmetinėmis ar algebrinėmis formulėmis. Tačiau ir šiuo atveju reikia įvertinti skaičių atvaizdavimo kompiuteryje galimybes, kadangi kompiuteriu negalima atlikti aritmetinių operacijų su didesniais negu numatyta sveikaisiais, taip pat nei su didesniais, nei su mažesniais negu numatyta slankaus kablelio skaičiais. Pavyzdžiui, natūrinio skaičiaus kėlimas natūriniu laipsniu gali būti pakeistas pakartotinai atliekama daugyba. Algoritmiškai realizuojant tokį metodą, reikia numatyti, kad rezultatas neviršytų naudojamajam kompiuteriui maksimaliai leistino sveiko skaičiaus. Duomenys uždaviniui mn spręsti būtų m, n ir max; čia max maksimalus leistinas naudojamojo kompiuterio sveikasis skaičius, o užrašytas pseudokodu algoritmas atrodytų taip:read m, n, maxmax1INT(max/m) {INT( ) reiškia sveikąją dalį}m1mn1n-1 while (n1>0 and m10 and A[i]>m) do A[i+1]A[i] ii-1 end A[i+1]m endprogram iterpimas;uses dos;var a:array[1..20000] of integer;var i,j,n,m:integer;var val, min, sek, sek100:word;begin writeln (‘Kokio dydzio (<20000) masyvas?’); readln (n); (* Pradiniu duomenu generavimas *) randomize; for i:=1 to n do a[i]:=random(1000); writeln (‘Pradiniai duomenys:’); for i:=1 to n do write (a[i]:5); writeln; (* laiko atskaita *) gettime (val, min, sek, sek100); writeln (‘Rusiavimas pradetas:’, val, min, sek, sek100); for j:=2 to n do begin m:=a[j]; i:=j-1; while ((i>0) and (a[i] > m)) do begin a[i+1]:=a[i]; a[I]:=m; i:=i-1; end; a[i+1]:=m; nėra end; gettime (val, min, sek, sek100); writeln; writeln (‘Rusiavimas baigtas:’, val, min, sek, sek100); readln; writeln (‘Rezultatas:’); for i:=1 to n do write (a[i]:5); writeln; readln;end.Nesunku įvertinti persiuntimo operacijų skaičių (vertinamas tik masyvo elementų persiuntimas), kai šiuo algoritmu tvarkomas masyvas, kurio ilgis lygus n. Cikle for atliekami du persiuntimai, plius persiuntimai cikle while, kurių palankiausiu atveju (jei tvarkomasis masyvas jau buvo sutvarkytas) gali ir nebūti. Nepalankiausiu atveju (jei masyvas sutvarkytas priešinga tvarka) cikle while bus atliktas j-1 persiuntimas. Bendras persiuntimų skaičius gali būti apskaičiuotas kaip aritmetinės progresijos suma, kai bendras narys lygus 2+j-1=j+1, o j kinta nuo 2 iki n, T(n)=(3+n+1)(n-1)/2Išrinkimo algoritmasPanaudokime šio uždavinio algoritmo konstravimui bendrą metodą, vadinamą kompozicija. Taikant šį metodą, rezultatas sukomponuojamas iš dalių, gaunamų sprendžiant paprastesnius (pagalbinius) uždavinius. Pastebėję, kad minimalus tvarkomojo masyvo elementas tampa pirmuoju sutvarkyto masyvo elementu, jį galime gauti, išrinkdami minimalų tvarkomojo masyvo elementą. Antrą rezultato (sutvarkyto masyvo) elementą gausime suradę mažiausią likusios masyvo dalies elementą. Komponuodami surastus elementus, pirmajame žingsnyje gauname sutvarkytą masyvą, teturintį vieną elementą, paskui du, ir t.t. Išrinkimo algoritmas, realizuojantis kompozicijos metodą, gali būti toks:

read n, Afor j1 to n-1 do mA[j] ij for kj+1 to n do if A[k] arba lygybė, reiktų generuoti klaidos pranešimą.Slenkstis:1) rasti atsitiktinį skaičių k iš intervalo (I,j), slenksčiu imti k-tojo elemento raktą;2) imti “vidurinį” elementą a[(I+j) div 2];3) imti nedidelį poaibį, tarp raktų rasti medianą.Raktas negali būti mažiausiu, reiktų įdėti tikrinimą: bėgama masyvu nuo I iki j kol randami du skirtingi raktai, imamas didesnis. Jei visi vienodi – jau sutvarkytas.Ar blogai, jei didžiausias? – namie.Suskaidymas: Galvojam apie kairįjį ir dešinįjį žymeklius, pradžioje a[I] ir a[j]. Kairysis važiuoja dešinėn, kol pasiekia raktą, didesnį arba lygų slenkstiniam. Dešinysis važiuoja kairėn, kol pasiekia mažesnį už slenkstį. Jei žymekliai sustoja nesusikirsdami, rasti elementai sukeičiami. Procedūra kartojama, kol žymekliai susiliečia.Procedure skelk(I,j: index; p:K; Var k: index);Var kaire, desine: index;Begin kaire:=I; desine:=j; Repeat While a[kaire].key < p do kaire := kaire +1; While a[desine].key >= p do desine := desine – 1; If kaire < desine then swap (a[kaire], a[desine]) Until kaire >=??? desine; K: = kaireEnd;Beg car sup and the bee sum pieTegul slenksčio kriterijus: didesnysis iš pirmųjų skirtingų: car.Beg car desine –1, andcar stopSup ≥ car desine-1, and1p1 – tikimybė, kad kairioji dalis turi 1 elementą, p2 – 2 elementus, …A(N) = N-1 + p1(A(1)+A(N-1))+p2(A(2)+A(N-2))+ …++ pN-1 (A(N-1)+A(1))Tikimybės vienodos, lygios 1/(N-1).A(N)= (N-1) + (2(A(1)+…+A(N-1))/(N-1) (1)Kai N-1A(N-1)=… (2)Dauginam iš vardiklio, atimam:(N-1)A(N)-(N-2)A(N-1) = (N-1)2-(N-2)2+2A(N-1)(N-1)A(N)-NA(N-1)=2N-3Dalijam

Pažymim B(k) = A(k)/kB(N)-B(N-1)=3/N – 1/(N-1)Paeiliui keičiam į N-1, N-2, …, 2 (B(1)=0):B(N)= 3(1/2+ 1/3 + … + 1/N) – (1+1/2+1/3+…+1/(N-1)) = 2(1+1/2+…+1/N)+1/(N-3)Euler (1707-1783): kai N didelis, suma apytiksliai lygi lnN, apytiksliai 0,693log2N.Tada A(N) apytiksliai 1,4Nlog2N, => O(Nlog2N).Padalinus masyvą į dvi dalis ir jas abi sutvarkius didėjimo tvarka, jas būtų nesunku sulieti į vieną sutvarkytą masyvą, t.y. suformuoti rezultatą imant minimalų elementą iš dviejų sutvarkytų dalių. Pažymėję persiuntimų skaičių, reikalingą n ilgio masyvui sutvarkyti T(n), gautume sąryšį: T(n)=T(m)+T(n-m)+n; čia m vienos iš masyvo dalių elementų skaičius, ir paskutinysis dėmuo reiškia suliejimo persiuntimų skaičių. Jei kartotume dekompoziciją ir dalintume masyvą pusiau, tai m būtų n/2, ir gautąją lygtį būtų galima perrašyti taip: T(n)=2T(n/2)+n. Nesunku patikrinti, kad funkcija nlog(n) patenkina paskutiniąją lygtį. Deja, ši idėja masyvams tvarkyti netinka, kadangi suliejimas reikalauja palyginamos su tvarkomuoju masyvu papildomos atminties, o masyvų tvarkymo algoritmams keliamas reikalavimas, kad papildoma atmintis nebūtų naudojama. Tačiau ši idėja sėkmingai panaudojama failams tvarkyti.Tiek kompozicija, tiek dekompozicija yra labai bendri metodai. Norint juos įvaldyti, reikia nagrinėti žinomus efektyvius algoritmus, teoriškai analizuojant sudaromo algoritmo sudėtingumą.Procedure QuickSort(var X: masyvas; k1, k2: integer);Var I,j,a,y: integerBegin I:=k1; j:=k2; Y:=x[I+j] div 2]; Repeat While y>x[I] do I:=I+1; While yj; If k1