Algoritmų teorija

Algoritmų teorija Algoritmų teorija yra natūrali procedūrinio programavimo tąsa. Kūrėte algoritmus, šiame kurse bandysim aiškintis, ką galima buvo padaryti geriau, ką – blogiau, t.y., nagrinėsim informacijos (pradinių duomenų?) sąvoką, labai nedaug duomenų struktūrų (teisingi aprašai padeda kurti efektyvesnes procedūras) – yra atskiras duomenų struktūrų kursas, bei vertinsim ir kursim (ir atvirkščiai) kai kurių gyvenimiškų uždavinių algoritmus. Tolesnė dalis abstrakcijos augimo prasme galėtų būti sudėtingumo ir apskaičiuojamumo teorijos bei programų sistemų inžinerijos kursai. Atsiskaitymas: kaupiamasis pažymys, todėl reiks lankomumo ir kontrolinių ar koliokviumų (1-2). Literatūra: Iain T. Adamson, Data structures and algorithms: the first course, Springer-Verlag, 1996. A.Žilinskas ir kt. Informatika, Vilnius, Aldorija, 2000. B.Burgis (ats. red.), Kompiuterija, Kaunas, Naujasis lankas, 2000. K. Plukas;Skaičiavimo metodai ir algoritmai, I-II dalys, Kaunas, Technologija, 1995-1997 A. Juozapavičius, Duomenų struktūros ir algoritmai, Vilnius, VU leidykla, 1997. R. Sedgewick et al., An Introduction to the Analysis of Algorithms, Addison-Wesley Pub Co, 2001. T. H. Cormen et al., Introduction to Algorithms, MIT Press, 2001. Mūsų kalba turi begalę perteklinių ir daugiaprasmių žodžių, dažniausiai mintį supranta tik sakantysis. Tai yra minusas ir pliusas kartu. Minusas – neaiški prasmė, pliusas – mažiau jautri iškraipymams (sugedusio telefono žaidime gal tik po trečios ar ketvirtos grandies prasmė iškraipoma). Artėjant link kompiuterio ta kalba turi tapti vienareikšmė, tačiau žmonės sugeba ir tais vienareikšmiais žodžiais (netgi programuodamas mašinine kalba) sukurti begalinius ciklus ir pan… Informacija – tai žinios, perduodamos… Skirtumai tarp informacijos ir žinių:– informacija pradinė, objektyvi, o žinias kuria žmogus iš gaunamos informacijos, jos subjektyvios. Informatika – mokslo ir technikos sritis, nagrinėjanti informacijos kūrimo, kaupimo, perdavimo ir apdorojimo dėsnius, metodus ir technines priemones. Terminas atsirado 7-8 dešimtmetyje, angliškai computer science. Užuomazgos (mechaninis mastymas) F.Bacon, Leibnicas, Paskalis, Lullius (XIII). Technika pagrįstas informatikos metodų taikymas praktikoje vadinamas informacinėmis technologijomis. Tai metodai ir būdai informacijai ieškoti, rinkti, tvarkyti ir pateikti. Pateikimo būdai, vartotojų pasiruošimas. Svarbiausia informacinių technologijų dalis – kompiuteris. Tačiau tai tik priemonė veiksmų su informacija algoritmams realizuoti. Algoritmai užrašomi programavimo kalba, tada jie vadinami kompiuterių programomis. Programinės įrangos klasifikacija. Informatikos objektas – informacija, algoritmai, programavimas, kompiuterinė technika, informacinės technologijos. Informacija Informacija – ž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ą. Entropija Vienodai 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 formule E(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. Algoritmai 783-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: 2 sveikų skaičių daugyba: Duomenys – 2 natūriniai skaičiai, rezultatas sveikas skaičius, šių dviejų sandauga. 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 . 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 pro­gra­ma­vi­mo kal­ba. Ta­čiau toks al­go­rit­mo api­brė­ži­mas ne visai ko­rek­tiš­kas, ka­dan­gi griež­tu­mo ir vie­na­reikš­miš­ku­mo rei­ka­la­vi­mai pa­tys sa­vai­me nė­ra vie­na­reikš­miai. Ki­ta ver­tus, pro­gra­ma­vi­mo kal­ba už­ra­šy­ta ‘pro­gra­ma’ ati­tin­ka griež­tu­mo ir vie­na­reikš­miš­ku­mo rei­ka­la­vi­mus, ke­lia­mus al­go­rit­mui. Pro­gra­ma­vi­mo kal­bos – vie­nas iš bū­dų al­go­rit­mams už­ra­šy­ti. Nors kai ku­riais at­ve­jais al­go­rit­mą leng­va su­for­mu­luo­ti ir ben­dri­ne kal­ba, ta­čiau te­ori­niams ty­ri­mams rei­kia spe­cia­lių al­go­rit­mų už­ra­šy­mo for­ma­liz­mų, kaip pa­vyz­džiui: RAM, Tu­ring’o ir Pos­t’o ma­ši­nos, Mar­ko­vo al­go­rit­mai, lamb­da 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. Te­ori­niam ty­ri­mui svar­bu, kad mi­ni­ma­liu ele­men­ta­rių veiks­mų kie­kiu bū­tų re­a­li­zuo­ja­mos arit­me­ti­nės ir lo­gi­nės ope­ra­ci­jos. Ku­riant pro­gra­ma­vi­mo kal­bas sie­kia­ma, kad pro­gra­muo­ti bū­tų pa­to­gu, to­dėl jo­se gau­su per­tek­liš­kų ele­men­tų. Tai ap­sun­ki­na jo­mis už­ra­šy­tų al­go­rit­mų te­ori­nius ty­ri­mus. Ga­li iš­kil­ti klau­si­mas, ko­dėl al­go­rit­mams for­mu­luo­ti ne­pa­si­nau­do­jus ge­rai ži­no­mo­mis ma­te­ma­ti­kos for­mu­lė­mis. Skir­tin­gai nuo įpras­tų ma­te­ma­ti­kos ob­jektų, al­go­rit­mas tu­ri se­man­ti­nę pa­lie­pi­mo pras­mę: al­go­rit­mas tu­ri bū­ti įvyk­dy­tas, ir ‘... al­go­rit­mų te­ori­ja ga­lė­tų bū­ti trak­tuo­ja­ma kaip lie­pia­mų­jų sa­ki­nių ling­vis­ti­ka’ [29]. Ma­te­ma­ti­nė­je for­mu­lė­je jo­kių dvi­pras­my­bių ne­su­kel­tų skai­čius , pa­kel­tas laips­niu e, nes toks ira­cio­na­lu­sis skai­čius eg­zis­tuo­ja. Bet, no­rint kom­piu­te­riu ap­skai­čiuo­ti šios for­mu­lės reikš­mę, iš­kil­tų klau­si­mas, kaip tai pa­da­ry­ti. Vi­sų pir­ma, kaip kom­piu­te­ry­je tu­ri bū­ti at­vaiz­duo­ti skai­čiai  ir e, ypač tuo at­ve­ju, kai rei­ka­lau­ja­mas žen­klų skai­čius di­des­nis už kom­piu­te­rio žo­džio il­gį. Veiks­mų su apy­tiks­liais skai­čiais re­zul­ta­tai kar­tais ga­li ap­skri­tai ne­tu­rė­ti pras­mės, nes la­bai daug kar­tų pa­kar­to­jus veiks­mą, pa­klai­da ga­li ne­pri­im­ti­nai iš­aug­ti, net jei­gu vie­no veiks­mo pa­klai­da yra la­bai ma­ža. Ži­no­ma at­ve­jų (pa­vyz­džiui, at­mo­sfe­rinius reiš­ki­nius ap­ra­šant ne­tie­si­nė­mis di­fe­ren­cia­li­nė­mis lyg­ti­mis), kai re­zul­ta­tą ne­pa­pras­tai vei­kia duo­me­nys. Pa­ki­tus duo­me­nims tik tūks­tan­tų­jų pro­cen­to da­lių dy­džiu, re­zul­ta­tas ga­li pa­si­keis­ti daug kar­tų. Tai va­di­na­ma­sis pe­te­liš­kės efek­tas, ku­rį ga­li­ma nu­sa­ky­ti taip: kaž­kur Eu­ro­po­je pe­te­liš­kė mos­te­lė­jo spar­ne­liu, o re­zul­ta­tas – tai­fū­nas Ra­mia­ja­me van­de­ny­ne. Šis pa­vyz­dys ro­do, kad net griež­tai ma­te­ma­tiš­kai su­for­mu­luo­to už­da­vi­nio, tu­rin­čio vie­nin­te­lį spren­di­nį, al­go­rit­mi­nio spren­di­mo ga­li­my­bės ne vi­sa­da aiš­kios. Va­di­na­si, rei­kia ma­te­ma­ti­nių ty­ri­mų, kol už­da­vi­nio sprendimas ga­lės bū­ti at­vaiz­duo­tas kom­piu­te­ry­je leis­ti­nais veiks­mais 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. Re­ziu­muo­da­mi, kas bu­vo pa­sa­ky­ta, al­go­rit­mą ga­li­me api­bū­din­ti kaip vienareikšmiškai api­brėž­tą baig­ti­nę veiks­mų se­ką, ku­ria bet ko­kiems duo­me­nims (iš leis­ti­nos duo­me­nų ai­bės) gau­na­mas pra­smin­gas re­zul­ta­tas. Al­go­rit­mas yra (kom­piu­te­riu at­lie­ka­mi) veiks­mai, ku­riais duo­me­nys trans­for­muo­ja­mi į re­zul­ta­tą, o ne bet ko­kia baig­ti­nė, kad ir vie­na­reikš­miš­kai api­brėž­ta, veiks­mų se­ka. 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: begalinė į abi puses Tiuringo mašinos juosta; neapibrėžtai plečiama mašina; 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ų) projektavimas Užsakovas (sponsorius), užduoties paruošėjas (algoritmo kūrėjas), programuotojas (gali būti tas pats). Užduoties dekompozicija pagal duomenis, pageidaujamus rezultatus. Formalios specifikacijos (reikalavimų formulavimas). Kiekviena funkcija turi turėti aiškias pradines sąlygas ir aiškų rezultatą. Funkcinis rišlumas: vienintelis tikslas, išreiškiamas paprastu sakiniu. Funkcija daranti darbus A, B, C – nebus panaudojama, jei reiks tik A. Sąsajos aiškumas: duomenys ir rezultatas tik argumentų sąraše. Laisvas jungimas (kaip 4) – be globalių kintamųjų. Informacijos slėpimas. Vidinės detalės nežinomos (a. sąsaja, b. pre ir post conditions) Algoritmų sudėtingumas Kaina = (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: jei programuojame paiešką, bazinėmis operacijomis galime laikyti ieškomojo objekto palyginimus su kolekcijoje esamais objektais; jei dauginam dvi skaitines matricas, bazinė operacija bus dviejų skaičių daugyba; 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: Kiekvienam n nagrinėjame visus n dydžio užduoties atvejus. Kiekvienam atvejui i (instance) randame darbo, atliekamo algoritmu, kiekį T(i). Apibrėžiame W(n) = max T(i) visiems n dydžio atvejams i. Funkciją W(n) vadinsime blogiausio atvejo sudėtingumu. 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ėžiame A(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 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 tempai Tegul f ir g yra dvi teigiamos realios f-jos, apibrėžtos visiems n>0. Sakysime 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. 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. 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 0 arba = , tada g yra  (f). 1/2c 1/2f jei lim g/f = , galime matyti, kad g/f>1, g>f. 3. Jei lim g/f = c, 0 n0, k>0. Tada g/f ≥ 1/K, kai n>n0; vadinasi lim g/f ≠ 0. Kelios formulės: = 0; 0; 0 jei p

Daugiau informacijos...

★ Klientai rekomenduoja

Šį rašto darbą rekomenduoja mūsų klientai. Ką tai reiškia?

Mūsų svetainėje pateikiama dešimtys tūkstančių skirtingų rašto darbų, kuriuos įkėlė daugybė moksleivių ir studentų su skirtingais gabumais. Būtent šis rašto darbas yra patikrintas specialistų ir rekomenduojamas kitų klientų, kurie po atsisiuntimo įvertino šį mokslo darbą teigiamai. Todėl galite būti tikri, kad šis pasirinkimas geriausias!