Diskrečioji matematika - algoritmai

Diskrečioji matematika 7 Algoritmų sudėtingumas Algoritmo sąvoka A. Algoritmu vadinama gerai apibrėžta skaičiavimo procedūra, kuri paima tam tikrą reikšmę įėjime (įėjimo duomenis) ir grąžina tos įėjimo reikšmės pilnai apibrėžtą reikšmę išėjime. Sąvoka “algoritmas” matematikoje dažnai priimama kaip pirminė, neapibrėžiama paprastesnėmis sąvokomis. Mes apibrėžėme, bet savo apibrėžime naudojome sąvoką “skaičiavimo procedūra”. Jei naudojame šią sąvoką apibrėždami “algoritmą”, tai tada pati “skaičiavimo procedūros” sąvoka lieka kaip pirminė. Žodžiu, bent vienos naujos pirminės sąvokos šitoje vietoje reikia. Sąvoka “skaičiavimo procedūra” čia buvo pavartota plačiąja prasme. Turime galvoje ne vien veiksmus su skaičiais. Skaičiavimo procedūrą gal labiau tiktų aiškinti, kaip tam tikrą veiksmų su simboliais seką. Įėjimo duomenys ir rezultatai skaičiavimo procedūrai gali būti bet kokie konstruktyvieji objektai (tokie objektai, kurie pasirinkti pirminiais arba kuriuos galima sukonstruoti gerai apibrėžtoje procedūroje), pvz., alfabeto simboliai, šių simbolių kombinacijos (pvz. eilutės), matricos, grafai ir t.t. Sąvoka “konstruktyvusis objektas” atstovauja tam tikrą požiūrį į matematiką – konstruktyviąją matematiką. Konstruktyviojoje matematikoje objekto egzistavimas siejamas su galimybe tą objektą sukonstruoti. Konstruktyvausiaus objekto ir konstruktyvausiaus proceso sąvokos algoritmų teorijai patogiame požiūryje į matematiką yra laikomos pirminėmis. Konstruktyvausiaus proceso įvaizdžiai: laikrodžio surinkimas iš dalių; teksto surinkimas iš raidžių, kt. Konstruktyvaus proceso esmė – gerai apibrėžtų veiksmų su nedalomais objektais vykdymas. Konstravimo procese iš pirminių objektų gaunami objektai ir vadinami konstruktyviaisiais. Pvz. teksto konstravime “dalyvauja” elementarūs objektai – simboliai ir elementarūs veiksmai: “įrašyti simbolį”, “ištrinti simbolį”, “perskaityti simbolį”, “palyginti du simbolius”. Algoritmas konstruktyviojoje matematikoje vaidina panašią rolę, kaip kad funkcija tradicinėje matematikoje. Žodis “algoritmas” yra kilęs iš 9 a. matematiko Al-Chorezmo pavardės (skaitant tą pavardę lotyniškai). Algoritmu viduramžių Europoje buvo vadinama dešimtainė pozicinė skaičiavimo sistema, o toks vardas prigijo dėl to, kad ta sistema į Europą atėjo su Al-Chorezmo darbais. Algoritminis procesas – toks procesas, kuriame palaipsniui (diskrečiaisiais žingsniais) pertvarkomi konstruktyvieji objektai. Algoritmas apibūdinamas: (1) aibe galimų įėjimo duomenų; (2) galimų rezultatų aibe; (3) galimų tarpinių rezultatų aibe; (4) algoritmo pradžios sąlyga; (5) algoritmo pabaigos sąlyga; (6) algoritmo vykdymo taisyklėmis (7) rezultato paėmimo taisyklėmis Algoritmui duodamas įėjimo duomenų rinkinys, algoritmas dirba su juo, ir jis gali po tam tikro žingsnių skaičiaus sustoti, arba niekada nesustoti. Algoritmo sustojimas/nesustojimas – labai svarbus klausimas algoritmų tyrime. Tą klausimą atidėsime, o dabar pereisime prie algoritmų analizės. Algoritmų sudėtingumo analizės pradmenys. Rūšiavimo algoritmų sudėtingumas A. Algoritmų analize priimat vadinti resursų, reikalingų algoritmui, kiekio nustatymą. Kiek atminties prireiks tam tikro algoritmo įvykdymui su tam tikrais duomenimis? Kiek laiko prireiks? Kaip pavyzdį paimkime rūšiavimo (kitaip, masyvų tvarkymo) uždavinį. Kas yra įėjimo duomenys rūšiavimo algoritmui? – Rūšiavimui teikiama skaičių seka. Ji gali būti trumpesnė arba ilgesnė; jau iš anksto labiau ar mažiau tvarkinga (surūšiuota). Algoritmų analizės sunkumas kaip tik ir yra tame, kad galimų įėjimo variantų paprastai būna labai daug. Reikia kažkaip apibendrinti tuos variantus. Pvz., nagrinėjami geriausias, blogiausias ir vidutinis atvejai. Kokiuos rūšiavimo algoritmus žinote? Iš “paprastų” (1) įterpimo; (2) išrinkimo; (3) pakeitimo (burbuliuko metodas). Pagal ką nustatomas rūšiavimo uždavinio dydis? • Pagal įėjimo sekos dydį. Pagal ką būtų nustatomas kurio nors grafų uždavinio dydis? • Pagal viršūnių skaičių; • lankų skaičių. Kaip išmatuoti uždavinio vykdymo laiką? • Galima matuoti tikrą laiką. Toks matavimas tiks lyginti vykdymo laiką panašiems uždaviniams, vykdomiems tame pačiame kompiuteryje, rašytiems ta pačia programavimo kalba. • Galima vykdymo laiką nusakyti mažiau nuo kompiuterio ir programinės įrangos priklausomais rodikliais. Pvz., galima skaičiuoti elementarių žingsnių, reikalingų algoritmui įvykdyti, skaičių. Grįžkime prie rūšiavimo uždavinio. Panagrinėsime rūšiavimo įterpimu algoritmą. Rūšiavimui įterpimu pradinis masyvas skaidomas į dvi dalis: jau surūšiuotą ir dar nesurūšiuotą. Imame pirmąjį elementą iš dar nesurūšiuotos dalies ir terpiame į surūšiuotąją dalį. Rūšiavimas_įterpimu(A) For j2 to length(A) C1 n length(A) Do keyA(j) C2 n–1 /* A(j) įterpsime į jau surūšiuotą seką A(1,2, …, j-1) */ ij–1 C3 n–1 while i>0 and A(i)>key C4 do A(i+1)A(i) C5 ii-1 C6 end A(i+1)key C7 n–1 end Bendras vykdymo laikas, pažymėkime jį T(n): tj priklausys nuo duomenų ir skirsis geriausiu, vidutiniu ir blogiausiu atvejais. Geriausią atvejį turėsime, aki masyvas A jau surūšiuotas. Tada tj1, kai j1,2,…,n. Tai yra, vykdymo laikas gali būti išreikštas kaip tiesinė funkcija: T(n)an+bn. Funkcijos argumentas – uždavinio dydis. Panagrinėkime tj blogiausiuoju atveju. Blogiausias atvejis nutinka tada, kai masyvas surūšiuotas atvirkščia tvarka. Kiekvieną A(j) tada turime lyginti su kiekvienu surūšiuotos masyvo dalies A(1,2, …, j-1) elementu. tjj, j2,3,…,n. Tada Pasiremta mokyklinio galvosūkio “Kaip greitai susumuoti skaičius nuo 1 iki 100” sprendimu. Pirmas sandaugos narys sudarytas, sumuojant pirmąjį ir paskutinįjį eilutės narį (arba antrą ir priešpaskutinį, ir t.t.). Vienam nariui vidutiniškai tenka ½ tokios sumos. O sumuojamų narių iš viso yra n–1. Analogiškai sumuojame Taigi, blogiausiuoju atveju Gavome funkciją, kurios pavidalas: T(n)an2+bn+c. Įvertinkime vidutinį vykdymo laiką. Tarkime skaičiai rūšiavimui pateiktame masyve išdėstyti atsitiktine tvarka. Vidutiniškai reikės peržiūrėti pusę iš A(1,2,…,j–1) elementų, kol rasime mažesnį už A(j). Taigi, tj/2. T(n) vėl bus kvadratinė funkcija. Paprastai algoritmo vykdymo laiko funkcija skaičiuojama blogiausiam atvejui. Tai yra ilgiausias vykdymo laikas iš visų dydžio n duomenų rinkinių. • Blogiausiuoju atveju vykdymo laikas yra viršutinė riba algoritmo vykdymui su bet kokiu įėjimu; • Neretai blogiausias atvejis įvyksta (pvz., paieška duomenų bazėje, kai reikiamos informacijos nėra); • Vidutinis atvejis, žiūrint apytiksliai, dažnai turi tą pačią vykdymo laiko funkciją, kaip blogiausiasis atvejis; • Kas yra vidutinis įėjimas dažniausiai neaišku; • Neretai vidutiniam įėjimui vykdymo laiko funkciją sunku įvertinti (mes nagrinėjome tuo klausimu palankų atvejį). Iš tikrųjų, vertinant algoritmo sudėtingumą, labai svarbus vykdymo laiko funkcijos augimo greitis, eilės tikslumu. Sakome, kad rūšiavimo įterpimu vykdymo laikas geriausiuoju atveju auga tiesiškai, žym. (n), blogiausiuoju atveju – kvadratiniu dėsniu, žym. (n2). A. Sakoma, kad vienas algoritmas yra efektyvesnis už kitą, jeigu pirmojo algoritmo vykdymo laiko augimo eilė blogiausiuoju atveju yra mažesnė, negu antrojo algoritmo. , 0 ir  žymėjimai Paruošta pagal T.H. Cormen, C.E. Leiserson, R.L. Rivest knyga "Introduction to Algorithms", MIT Press, 1990. Pilniau susipažinsime su žymėjimais, naudojamais algoritmų sudėtingumo teorijoje. Kai domimės vykdymo laiko funkcijos augimo pobūdžiu (tiesinis, kvadratinis ir pan.), tai sakome, kad tyrinėjame asimptotinį algoritmų efektyvumą. Mus domina, kaip algoritmų vykdymo laikas didėja, lyginant su uždavinio dydžiu, riboje, kai uždavinio dydis neribotai auga (artėja į begalybę). -žymėjimas. Sakome, kad funkcija f(n) priklauso sudėtingumo klasei (g(n)), jei egzistuoja teigiamos konstantos c1 ir c2, tokios, kad 00, tokie, kad 0n0}. Funkcijų f(n) ir g(n) santykį parodo paveikslas: Pvz., galime sakyti, kad rūšiavimo įterpimu vykdymo laiko funkcija blogiausiuoju atveju T(n)=(n2). Sakome, kad g(n) yra asimptotiškai griežta funkcijos f(n) riba. Kaip įrodyti, kad funkcija f(n) priklauso klasei g(n)? Reikia rasti konstantas c1 ir c2, ir n0 tokias, kad būtų tenkinama nelygybė: 0=1, pasirinkus c2>=1/2. Kairioji pusė bus patenkinta visiems n>=7, pasirinkus c1=n0. Funkcijų f(n) ir g(n) tarpusavio santykius rodo paveikslas: Iš f(n)=(g(n)) išplaukia f(n)=O(g(n)). -priklausomybė yra stipresnė, negu O- priklausomybė. Pvz., an2+bn=(n2); an2+bn=O(n2), Tačiau an+b(n2); an+bn=O(n2). Literatūroje kartais pasitaiko pasitaiko, kad O-žymėjimu žymimos asimptotiškai griežtos ribos. Viršutinę asimptotinę ribą dažnai galima rasti vien tik peržvelgus algoritmo struktūrą. Jei yra du ciklai, įdėti vienas į kitą, tai galima drąsiai sakyti, kad algoritmas turi viršutinę asimptotinę ribą O(n2). Viršutinė riba blogiausiajam atvejui bus ir viršutine riba bet kuriam kitam atvejui. -žymėjimas. Nurodo apatinę asimptotinę ribą funkcijos vykdymo laikui. Duotajai funkcijai g(n) žymime f(n)=(g(n)) tokį funkcijų rinkinį: (g(n)){f(n):c,n0>0 tokie, kad 0n0}. Funkcijų f(n) ir g(n) tarpusavio santykius parodo paveikslas: Kai apatinę asimptotinę ribą nustatome geriausiajam atvejui, tai kartu tą ribą nustatome ir visiems uždavinio atvejams. Pvz., apatinė asimptotinė riba rūšiavimui įterpimu yra (n). Teorema. Bet kurioms dviems funkcijoms f(n) ir g(n) galioja priklausomybė f(n)(g(n)) tada ir tik tada, kai f(n)O(g(n)) ir f(n)(g(n)). o-žymėjimas ir w-žymėjimas. Viršutinė asimptotinė riba O-žymėjime gali būti, bet gali ir nebūti asimptotiškai griežta. Pvz., abu užrašai teisingi: 2n2O(n2) ir 2nO(n2). Tačiau pirmoji riba yra asimptotiškai griežta. Antroji riba nėra asimptotiškai griežta. Mažosios raidės o ir w pabrėžia, kad viršutinė (apatinė) riba nėra asimptotiškai griežtos. o(g(n))) aprašo aibę funkcijų: o(g(n))){f(n):c>0 n0>0 toks, kad 0n0}. Tokiu atveju: T.y., riboje, kai n neaprėžtai auga, f(n) tampa nereikšmingai mažas, lyginant su g(n). w-žymėjimas aprašo apatinę ribą, kuri nėra asimptotiškai griežta. Jei f(n)w(g(n)), tai Pavyzdukas. Tarkime vykdymo laiko funkcija yra T(n)an2+bn+c (pvz., rūšiavimui įterpimu). Tuomet teisingi tokie asimptotiniai įverčiai: T(n) (n2); T(n)O(n2); T(n)O(n3); T(n)O(n4); T(n) (n2); T(n) (n); T(n)o(n2); T(n)o(n3); T(n)w(n2) T(n)w(n). Polinomiškai ir eksponentiškai augančios funkcijos A. Sakoma, kad funkcija T(n) yra polinominė (polinomiškai aprėžta), jei T(n)(nk) kažkokiam pastoviam realiajam skaičiui k. A. Sakoma, kad funkcija auga logaritmiškai, jei T(n)(loga(n)). Pagrindas – bet koks realusis skaičius. A. Sakoma, kad funkcija auga eksponentiškai, jei T(n)(an), a>1. Bet kuri eksponentinė funkcija, riboje kai n, auga žymiai greičiau už bet kurią polinominę funkciją. Formuluojant glaustai: Arba kitaip galime užrašyti nbo(an). Jei algoritmo vykdymo laiko funkcija auga eksponentiškai, uždavinys bent kiek didesniam n tampa sunkiai išsprendžiamas netgi ir greitu kompiuteriu. Laikoma, kad uždavinys yra išsprendžiamas kompiuteriu, jeigu jo algoritmo vykdymo laiko funkcija polinominė, ir laikoma, kad uždavinys yra kompiuteriu neišsprendžiamas, jei jo algoritmo vykdymo laiko funkcija auga eksponentiškai. Grafų algoritmų sudėtingumo tyrimas Patyrinėkime, kokio sudėtingumo buvo mūsų nagrinėtieji trumpiausiojo kelio (Dijkstra) ir trumpiausiojo jungiančiojo medžio (Kruskal) algoritmai. Tarkime, |V|n (viršūnių skaičius) ir |L|m (lankų skaičius). Dijkstra (G,w,s) Inicializacija (G,s) O(n) S   O(1) Q  V[G] O(n) Ciklas kol Q ne tuščia aibė U  minimalų atstumą nuo s turinti viršūnė iš Q O(n) S  S  {u} O(1) Q  Q – u O(1) O(n2) Ciklas visoms v, kurios gretimos u Relaksacija (u, v, w) O(1) O(n) Ciklo pabaiga Ciklo pabaiga Bendrai paėmus, Dijkstra algoritmo vykdymo laiko funkcija T(n)O(n2). Kruskal (G,w) M O(n) Ciklas kiekvienai grafo viršūnei vV(G) Sudaryti po atskirą aibę, į kurią ta viršūnė įeitų O(n) Ciklo pabaiga Surūšiuoti visus lankus L nedidėjimo tvarka O(mlog(m)) Ciklas visiems lankams (u,v)L iš eilės Jei viršūnė v priklauso kitai aibei, nei viršūnė u Tai MM(u,v) Sujungti aibę, kuriai priklauso viršūnė u O(m) su aibe, kuriai priklauso viršūnė v Pabaiga jei Ciklo pabaiga Bendrai paėmus, Kruskal algoritmo vykdymo laiko funkcija: T(n,m)O(n)+O(mlog(m))+O(m)O(mlog(m)). Algoritmų sudėtingumo klasės, P, NP, “NP-complete” Čia nagrinėsime kompiuteriu spręstinus ir kompiuteriu nespręstinus uždavinius. Uždavinys, kaip jau kalbėjome, laikomas išsprendžiamu (spręstinu) kompiuteriu, jei jam egzistuoja polinominio laiko algoritmas ir nespręstinu, jei polinominio laiko algoritmas jam neegzistuoja. Ar algoritmo sudėtingumas priklauso nuo to, kokiu būdu koduosime duomenis? (Ar gali sudėtingumas pereiti iš polinominio į nepolinominį ir atvirkščiai?) Yra tokių (kraštutinių) atvejų, kada priklauso. Tarkime, pradiniai duomenys algoritmui – sveikas skaičius. Pavadinkime jį k. Tarkime algoritmo sudėtingumas priklauso nuo skaičiaus dydžio – yra (k). Perduokime skaičių k algoritmui vienetainiu kodu (vienetainiame kode skaičius k – eilutė iš k vienetų). Tuomet algoritmo vykdymo laiko funkcija bus (n) n ilgio įėjimui. Jei panaudosime sveikajam skaičiui k dvejetainį vaizdavimą, tada įėjimo ilgis bus nlog2(k). Tada vykdymo laiko funkcija bus (k)(2n). Taigi, dvejetainės sistemos požiūriu, algoritmo vykdymo laiko funkcija bus eksponentinė. Tačiau jei ekstremalių ir brangių kodavimo sistemų (tokių, kaip vienetainė) nenaudosime, tai algoritmo vykdymo laiko funkcijos pobūdis, pereinant iš vienos sistemos į kita, nesikeis. T.y. negausime polinominio laiko perėjimo į nepolinominį, keisdami kodavimo sistemą iš 10-ainės į 2-ainę ar 3-ainę. A. Sakoma, kad funkcija f yra polinomiškai apskaičiuojama, jei egzistuoja polinominio laiko algoritmas A, kuris, davus bet kokį įėjimą x dvejetainiame kode, atiduoda atsakymą f(x). A. Sakoma, kad du kodavimo būdai: e1 ir e2 yra polinomiškai susiję, jei egzistuoja dvi polinomiškai apskaičiuojamos funkcijos f12 ir f21, tokios, kad kiekvienam i iš tam tikros uždavinių aibės I f12(e1(i))e2(i) ir f21(e2(i))e1(i). T.y., kodavimai yra polinomiškai susiję, jei duomenis iš vieno į kitą įmanoma pervesti per polinominį laiką. Tiriant algoritmus paprastai daroma taip: pasirenkamas įprastinis kodavimo būdas, pvz. dvejetainis, ir toliau kodavimu nebesirūpinama, dirbama su tuo pasirinktuoju “standartiniu” būdu. Abstraktieji uždaviniai Siekiant supaprastinti algoritmų sudėtingumo analizę, nagrinėsime tik sprendimo priėmimo (angl. decision) uždavinius, t.y. tokiuos, kurie įėjime gali turėti įvairias duomenų struktūras, tačiau išėjime gali turėti tik taip/ne (“0”/”1”). Taigi, įėjimas, kuris gali būti bet kokio sudėtingumo dvejetainė eilutė, o išėjime tik viena iš dviejų reikšmių “0” arba “1”. Sudėtingumo prasme, kiekvienas uždavinys su sudėtingesniu išėjimu turi atitikmenį sprendimo priėmimo uždavinių tarpe. Pvz. uždavinys: Duotas grafas su svoriais G(V,L,w) ir dvi viršūnės u,vV. Rasti trumpiausiąjį kelią tarp jų. Atitinkamas sprendimo priėmimo uždavinys: Duotas grafas su svoriais G(V,L,w) ir dvi viršūnės u,vV, ir, papildomai, skaičius k. Reikia rasti, ar egzistuoja kelias tarp u ir v ne ilgesnis už k. Sprendimo priėmimo uždaviniai patogūs analizuoti, nes jiems galima pritaikyti formaliųjų kalbų analizės metodus. A. Alfabetu  vadinsime simbolių rinkinį. Pvz. dvejetainiam kodavimui {0,1}. A. Kalba L iš alfabeto  vadinsime eilučių, sudarytų iš  simbolių, rinkinį. Pvz. L{10,11,101,111,1101,10001,...} – pirminių skaičių kalba dvejetainiame vaizdavime. Su kalbomis galima vykdyti visas aibių teorijos operacijas: sąjungą, sankirtą, papildymą. Papildymas imamas iki visų galimų dvejetainių eilučių rinkinio, vadinamojo *; *{,0,1,01,10,11,000,...}, kur  – tuščia eilutė. Kiekviena kalba yra * poaibis. Apibrėšime sąryšį tarp sprendimo priėmimo uždavinių ir kalbų. A. Sakoma, kad algoritmas A priima eilutę x iš dvejetainio alfabeto, jei, davus x, algoritmas išveda A(x)1 ir sustoja. A. Sakoma, kad algoritmas A atmeta eilutę x iš dvejetainio alfabeto, jei davus x, algoritmas išėjime išveda A(x)0 ir sustoja. A. Algoritmo A priimama kalba vadinamas eilučių rinkinys L{x:A(x)1}. Netgi tuo atveju, jeigu kalba L yra priimama algoritmo A, algoritmas ne būtinai atmes eilutę xL. Pvz., algoritmas gali patekti į amžiną ciklą ir nesustoti A. Kalba L vadinama apibrėžta (decided) algoritmu A, jei bet kuri dvejetainė eilutė yra arba priimama, arba atmetama algoritmo A. A. Sakoma, kad kalba L yra priimama polinominiu laiku algoritmo A, jeigu bet kuriai n ilgio eilutei xL algoritmas ją priima laiku O(nk), kur k – konstanta. A. Sakoma, kad kalba L polinominiu laiku apibrėžiama algoritmu A, jei bet kuriai n ilgio eilutei x algoritmas nusprendžia, ar x priklauso kalbai per laiką O(nk). A. Polinominio sudėtingumo klase vadinama aibė kalbų, kurių eilučių narystė nusprendžiama polinominiu laiku. Klasę vadinsime P. P{L:egzistuoja A, apibrėžiantis L per O(nk)} Pvz., panagrinėkime kalbą PATH. Šios kalbos eilutę sudarys grafas G (tam tikras grafo viršūnių ir lankų bei jų svorių aprašymas) ir dvi viršūnės u ir v, ir dar sveikasis skaičius k. Jei atstumas tarp viršūnių u ir v aprašytajame grafe G mažesnis už k, tada sakysime, kad eilutė kalbai priklauso (kalbos priėmimo/apibrėžimo algoritmas išves “1” ir sustos). Jei atstumas didesnis už k – eilutė nepriklausys kalbai. Kalbos priėmimo algoritmas įeis į amžiną ciklą; kalbos apibrėžimo algoritmas išves “0” ir sustos. Realiai, algoritmas, kuris darys sprendimą dėl eilučių priklausymo kalbai, bus trumpiausiojo kelio radimo algoritmas. Tarkime, sprendžiame PATH problemą. Tarkime, žinome kelią nuo k iki v. Ar sunku bus patikrinti, ar kelias p ne ilgesnis už k? (“Ar sunku”, reiškia “ar ilgai vykdomo algoritmo reikės patikrinimui”) Patikrinimo laikas PATH atveju yra O(m), m– lankų skaičius, eilės – tos pačios eilės, kaip ir pats kelio radimas. Norint patikrinti kelio ilgį reiks surasti lankų svorius, iš čia tas O(m). Imkime kitą uždavinį – Hamiltono ciklo radimą. Kaip galėtų algoritmas apibrėžti kalbą Hamiltono_ciklas? – Algoritmas turėtų perrinkti visas galimas kelių kombinacijas. Kiek tų visų galimų kelių yra? – Jei viršūnių yra n, tai galimų viršūnių perstatymų n! Taigi, uždavinio sudėtingumas O(n!), kas nėra O(nk) jokiam k. T.y. algoritmo neįmanoma įvykdyti polinominiu laiku. Ką reikštų patikrinti, ar duotasis ciklas yra Hamiltono ciklas? – Reikėtų patikrinti, ar duotoji viršūnių seka tikrai yra visų grafo viršūnių perstatinys, ir ar tikrai visi nurodyti sujungimai egzistuoja. Toks patikrinimas Hamiltono ciklui užimtų polinominį laiką O(n2), kur n – grafo viršūnių skaičius, O(m), jei m imtume grafo lankų skaičių (ar grafo kodo dydį). A. Verifikavimo algoritmu vadinsime dviejų argumentų algoritmą A, kuriame vienas argumentas – įprastinė įėjimo eilutė x, antras argumentas – dvejetainė eilutė y, vadinama sertifikatu. A(x,y)1, jei sertifikatas teisingas. Pvz., Hamiltono_ciklo atveju sertifikatu būtų viršūnių, sudarančių Hamiltono ciklą grafe sąrašas. A. Sudėtingumo klasė NP – tai kalbų, kurios gali būti verifikuotos (patikrintos) polinominio laiko algoritmais, klasė. Pvz., kalba PATH ir kalba Hamiltono_ciklas – abi priklauso klasei NP. Teorema. Jei LP, tai LNP. Egzistuoja polinominio laiko algoritmas, kuris apibrėžia L. Jį galima pertvarkyti į verifikavimo algoritmą su bet kokiu sertifikatu, kurį algoritmas ignoruos. Teorema. PNP. Priimkime be įrodymo. Nėra žinoma, ar PNP, bet dauguma algoritmų teorijos tyrinėtojų linkę manyti, kad PNP. P ir NP galima interpretuoti taip: • P – klasė uždavinių, kuriuos įmanoma priimtinu laiku išspręsti; • NP – klasė uždavinių, kurių sprendinio teisingumą įmanoma priimtinu laiku patikrinti. “NP-pilnoji” (NP-complete) uždavinių klasė. Pagrindinė priežastimi kodėl informatikos teoretikai tiki, kad PNP, tai NP-pilnosios uždavinių klasės egzistavimas. Klasė pasižymi tuo, kad iki šiol nerastas polinominio laiko algoritmas nei vienam jos uždaviniui. Tačiau įrodyta, kad jei bent vienas uždavinys iš NP pasirodytų išsprendžiamas polinominiu laiku, tada kiekvienas iš tos klasės turėtų polinominį sprendinį. Nežiūrint daug įdėto darbo, nė vienas iš NP-complete klasės uždavinių iki šiol nėra polinominiu laiku išspręstas. Kaip tik iš to ir kyla informatikos teoretikų įsitikinimas, kad polinominiai algoritmai šiems uždaviniams neegzistuoja. “NP-complete” (NPC) kalbos yra sunkiausios iš visų NP kalbų. Informatikos teoretikai mano, kad PNPC. Bendras, P, NP, NPC klasių išsidėstymas tada atrodytų taip, kaip parodyta toliau sekančiame paveikslėlyje. Teorema. (1) Jei bent vienas iš “NP-complete” uždavinių yra išsprendžiamas polinominiu laiku, tai PNP. (2) Jei bent vienas uždavinys iš NP uždavinių yra polinominiu laiku neišsprendžiamas, tai visi “NP-complete” uždaviniai yra polinominiu laiku neišsprendžiami. Įrodymas, kad NP-complete uždaviniai yra tarpusavyje vienodo sudėtingumo (lygiaverčiai) yra gautas, remiantis polinominiu pervedamumu (angl., reducability). Intuityviai suprantama, kad uždavinį Q būtų galima pavadinti pervedamu į Q’, jei kiekvienas Q atvejis būtų lengvai perfrazuojamas į Q’ atvejį (“lengvai, pvz., galėtų reikšti “polinominiu laiku”). Pakalbėsime apie pervedamumą formaliųjų kalbų terminais. A. Sakoma, kad kalba L1 yra polinominiu laiku pervedama į kalbą L2, jei egzistuoja polinomiu laiku apskaičiuojama funkcija f, tokia, kad xL1 perveda į f(x)L2. f vadinama pervedimo funkcija, o ją įgyvendinantis algoritmas – pervedimo algoritmu. Pervedimo funkcija f turi savybę, kad jei xL1, tai f(x)L2, ir jei xL1, tai f(x)L2. Atsakymas į klasuimą, ar f(x)/L2 teisingai duoda atsakymą į klausimą, ar xL1, ar xL1. Teorema. Jei kalbos L1 ir L2 yra tokios, kad L1 polinominiu laiku pervedama į L2, tai iš taiginio, kad L2P išplaukia L1P. Įrodymas. Tarkime A2 yra polinominiu laiku įvykdomas algoritmas, kuris apibrėžia kalbą L2, o F – polinominiu laiku įvykdomas algoritmas, kuris apskaičiuoja pervedimo funkcijos f reikšmę. Algoritmai F ir A2 jungiami nuosekliai, todėl bendras algoritmas A apibrėžia kalbą L1 polinominiu laiku. A. Kalba L vadinama “NP-pilnąja” (NP-complete), jei: (1) LNP; (2) L’ pervedama polinominiu laiku į L visoms L’NP. NP-pilnosios klasės uždavinių pavyzdžiai (1) Hamiltono ciklo (kelio) radimas grafe; (2) Bulinių schemų patenkinamumo (satisfability) uždavinys. Sakoma, kad schema Patenkinama, jei egzistuoja tokia vienetų ir nulių kombinacija įėjime, kuri išėjime duoda vienetą (patenkinamos schemutės paveikslas lapuose). Su schemų patenkinamumo problema dažnai susiduriama optimizuojant aparatūrinę įrangą. jei schema nepatenkinama, tai vietoje jos visos galima statyti nuliuką. Deja, schemų patenkinamumo uždavinį galima išspręsti tik įėjimo kombinacijų pilnu perrinkimu (2k kombinacijų, jei k įėjimo kintamųjų skaičius). (3) Loginių formulių patenkinamumo uždavinys Formulę apibrėžiame kaip sudėtą iš – bulinių (loginių) kintamųjų x1, x2,... – loginių jungtukų ,,,,; – skliaustukų. Formulė, kuri turi tokį įėjimą, kuris išėjime duotų 1-ą, vadinama patenkinama. Pvz., formulė (x1,x2,x3,x4)((x1x2) ((x1x3)x4)) x2 turi patenkinantį įėjimą: x10, x20, x31, x41. (4) Klikos radimas bekrypčiame grafe; (5) Grafo dengimo uždavinys. Bekrypčiame grafe reikia rasti minimalų skaičių viršūnių, tokių, kad visos grafo briaunos būtų tomis išrinktosioms viršūnėms gretimos. (6) Poaibio sumos uždavinys. Duota natūrinių skaičių aibė ir skaičius lN (natūrinių skaičių aibės). Reikia patikrinti, ar galima surasti tokį aibės poaibį, kurio suma būtų l. (7) Keliaujančio prekeivio uždavinys. Grafe su svoriais reikia rasti trumpiausią ciklą, praeinantį per visas viršūnes po vieną kartą.

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!