82.Algoritmai
82.Algoritmai
Algoritmai – efektyvios procedūros (EP), aprašančios veiksmų seką ir vienareikšmiškai duodančios tam tikrą rezultatą.
Mokykliniai daugybos “stulpeliu” ir dalybos “kampu” metodai, sudėtingos funkcijos diferencijavimo taisyklės ir t.t. – algoritmai.
Pagrindiniai reikalavimai
1.Algoritmas naudojamas su pradiniais duomenimis ir duoda rezultatus. Be to, algoritmo vykdymo metu pasirodo tarpiniai rezultatai.
Taigi, algoritmas operuoja su objektais -duomenimis – pradiniais, tarpiniais ir galutiniais
Algoritmų teorijoje nenaudojamas žodinis objektų apibrėžimas, vietoje to fiksuojami:
• konkretūs baigtiniai pradinių objektų rinkiniai ,
• baigtinis kitų objektų sudarymo būdų iš elementariųjų objektų rinkinys. <
Elementariųjų objektų rinkinys sudaro
baigtinį pradinių simbolių alfabetą.
Tipinis kitų objektų sudarymo būdas – indukcija.
Paprasčiausias indukcinis apibrėžimas – klasikinis identifikatoriaus apibrėžimas, naudotas jau ALGOLe: identifikatorius yra raidė arba identifikatorius, kuriam iš dešinės pridėta raidė arba skaičius.
::=::= ½::= 0½1½2½3½4½5 ½6 ½7 ½8 ½9
2.Duomenys talpinami atmintyje.
3.Algoritmas susideda iš elementarių žingsnių arba veiksmų, skirtingų žingsnių aibė baigtinė.
4.Algoritmo žingsnių seka determinuota.
5.Natūralu iš algoritmo reikalauti rezultatyvumo.
Reikia skirti:
• algoritmo aprašą (instrukcijas/programą),
• algoritmo realizacijos mechanizmą (kompiuterį),
• algoritmo vykdymo procesą (veiksmų seką, gaunamą pritaikant aalgoritmą konkretiems duomenims).
3.Algoritmų modeliai
Algoritmų teorijoje:
• parenkamas baigtinis pradinių objektų rinkinys, tie objektai laikomi elementariais,
• parenkamas baigtinis naujų objektų sudarymo būdų rinkinys.
Algoritminiai modeliai, pretenduojantys į sąvokos “algoritmas” formalizavimą, turi būti universalūs.
Universalumas:
• įrodoma, kad vieną modelį galima pakeisti kitu,
• sukurta iinvariantiška modelių atžvilgiu sąvokų sistema, įgalinanti aptarti algoritmų savybes nepriklausomai nuo parinktos formalizacijos.
Yra trys pagrindiniai universalių algoritminių modelių tipai:
• rekursyviosios funkcijos – istoriškai pirmoji algoritmo sąvokos formalizacija,
• algoritmo vaizdavimas determinuotu įtaisu, gebančiu atlikti labai primityvias operacijas,
• bet kokių alfabetų žodžių perdirbimas; Posto sistemos, normaliniai Markovo algoritmai.
4.Tiuringo tezė
• Viskas, kas gali būti padaryta su skaičiavimo mašina, gali būti atitinkamai aprašyta
• Bet kuri procedūra, kurią galima tiksliai aprašyti, gali būti suprogramuota skaičiavimo mašinai.
Alanas Matisonas Tiuringas
A.M.Turing, 1912.06.23 – 1954.06.08
Turing A.M. On computable numbers, with an application to the entsheidungsproblem. Proc. London Math. Soc., Ser 2, 42, 1936)
Nagrinėtini tokie klausimai:
• kokie procesai gali būti aprašyti?
• ar galima viena kalba aprašyti visus galimus aprašyti procesus?
• ar egzistuoja kokiu nors būdu visiškai aapibrėžti procesai, kurių negalima aprašyti?
• ar galima tvirtinti, kad egzistuoja kažkokie procesai, kuriuose yra tam tikras emocinio pobūdžio ryšys ir juos galima tik intuityviai apibūdinti, o negalima aprašyti baigtiniu žodžių kiekiu?
Algoritmo ar efektyvios procedūros sąvoka sutinkama, kai tik turime reikalų su keliomis elgseną reglamentuojančiomis instrukcijomis;
tai įvyksta, kai spręsdami kokį nors uždavinį aptinkame, kad kuri nors procedūra,
jei ją teisingai atliksime,
visada baigsis,
duodama tam tikrą atsakymą.
Jeigu yra duotas instrukcijų rinkinys, kyla tokie klausimai:
– ar mums tiksliai pranešta, ką ddaryti?
– ar galėsime elgtis pagal instrukcijas?
Algoritmas – efektyvi procedūra – aibė nuosekliai laike atliekamų instrukcijų/taisyklių, tiksliai reglamentuojančių mūsų/kieno nors elgesį.
Interpretuojančio subjekto intelekto lygis:
• per žemas – gali instrukcijų nesuprasti;
• per aukštas ar instrukcijos jam nepriimtinos – gali jas savaip interpretuoti;
Patogu būtų turėti:
• kalbą, kuria aprašoma elgesio taisyklų aibė,
• vieną – vienintelę mašiną, kuri interpretuotų tos kalbos nurodymus ir žingsnis po žingsnio atliktų tiksliai nurodytus procesus.
Pagrindinė tos mašinos idėja – kokybinis mašinos sudėtingumo didinimas pakeičiamas paprastu kiekybiniu atminties didinimu.
Tiuringo mašina – tai mašina su baigtiniu būsenų skaičiumi, sujungta su ypatingu įtaisu – juosta, ant kurios ji gali užrašyti, o po to perskaityti simbolių sekas.
Tiuringas aptiko, kad šios mašinos gali atlikti labai sudėtingus skaičiavimus ir iškėlė teiginį, dažnai vadinamą Tiuringo teze:
bet kuris procesas, kurį natūraliai būtų galima pavadinti efektyvia procedūra, gali būti realizuotas Tiuringo mašina.
5.Tiuringo mašinos
Tiuringo mašina – tai baigtinis automatas, sujungtas su išorine atmintimi – juosta, kuri suskirstyta į ląsteles.
Galvutė atlieka tris funkcijas:
• skaito ląstelės turinį,
• įrašo į ląstelę,
• pasislenka prie gretimos ląstelės.
Baigtinis automatas aprašomas:
– įėjimo simbolių alfabetu (s0, . , sm),
– išėjimo simbolių alfabetu (r0, . ,rn),
– vidinių būsenų aibe (q0, . , qp),
– funkcijomis
Q(t+1) = G(Q(t),S(t)),
R(t+1) = F(Q(t),S(t)).
Tiuringo mašina aprašoma trimis lygtimis:
Q(t+1) = G(Q(t),S(t)),
R(t+1) = F(Q(t),S(t)),
D(t+1) == D(Q(t),S(t)),
o naujoji funkcija D nurodo galvutės judėjimo kryptį .
Baigtinis automatas – aprašomas tokiu penketu:
sena skaitomas nauja įrašomas judėjimo
būsena simbolis būsena simbolis kryptis
qi sj G(qi, sj) F(qi, sj) D(qi, sj)
arba
qi sj qij sij dij
Kokią nors Tiuringo mašiną, pavyzdžiui, galima aprašyti taip:
q0 0 q0 0 D arba 0 0 0 0 1
q0 1 q1 0 D 0 1 1 0 1
q0 P S 0 – 0 P S 0 –
čia raide S pažymėta sustojimo būsena, raide P – simbolių eilutės pabaiga.
Tiuringo mašinose skaičiavimus galima atlikti nurodžius:
• pradinę mašinos (baigtinio automato) būseną,
• juostoje įrašytą informaciją,
• ląstelę, ties kuria yra skaitanti galvutė.
5.1. TM pavyzdžiai
1.Lygiškumo indikatorius
Duota vienetų ir nulių eilutė, pabaigos simbolis P; vietoje jo reikia įrašyti 1, jei vienetų skaičius nelyginis, arba 0, jei vienetų skaičius lyginis.
qi sj qij sij dij
0 0 0 0 D
0 1 1 0 D
0 P S 0 – lyginis vienetų skaičius
1 0 1 0 D
1 1 0 0 D
1 P S 1 – nelyginis vienetų skaičius
qi sj qij sij dij
0 0 0 0 D
0 1 1 1 D
0 P S 0 – lyginis vienetų skaičius
1 0 1 0 D
1 1 0 1 D
1 P S 1 – nelyginis vienetų skaičius
Išsaugoma pradinė informacija
2.Išraiškų su skliaustais tikrinimas
( ( ( ( ) ( ) ) ( ) ) ) – teisinga išraiška,
( ( ) ) ), ) ) – neteisingos išraiškos.
Tikrinimo procedūra:
– einant iš kairės į dešinę randamas pirmas “)”, einant į
kairę randamas jam porinis “(“ ir abu skliaustai braukiami;
– procesas kartojamas, kol išbraukiamos visos poros.
Jei lieka neišbrauktų neporinių skliaustų – išraiška neteisinga, jei nelieka – teisinga.
5.2.Tiuringo mašinų diagramos
Būsenos atvaizduojamos apskritimais; būsena qi užrašoma po apskritimu.
Galvutės judesio kryptis nurodoma apskritimo viduje (pvz., K – kairėn, D – dešinėn).
Rodyklė atvaizduoja penkiukę (qi,sj,qij,sij,dij).
Rodyklės pabaigoje užrašomas skaitomas simbolis sj, viduryje – įrašomas simbolis sij (jei sutampa su sj – galima praleisti).
Dažnai pasitaikančios penkiukės (qi,sj,qi,sj,dij) praleidžiamos (nesikeičia nei būsena, nei simbolis).
4. Daugybos įtaisas
Darbo algoritmas
5. Kartoja 3 p., kol randa B
6. Kartoja 1 p., kol randa kairįjį A ir sustoja.
Juosta po daugybos
Užduotis. Suprojektuoti Tiuringo mašiną, apskaičiuojančią skaičiaus n kvadratą.Skaičius atvaizduotas taip:
5.Dvejetainių skaičių sumatorius
Užduotis. Duota Tiuringo mašina:
Mašina pradeda darbą tuščioje juostoje. Koks bus jos darbo
rezultatas?
6. Tiuringo mašinos atminties valdymas
Yra žodžių Ui aibė, kiekvienas žodis turi požymį Ni.
Žodžiai ir jų požymiai atvaizduoti dvejetaine forma, išdėstyti juostoje poromis NiUi ir atskirti simboliais X.
Simboliai Y žymi aibės pradžią ir pabaigą.
Visi požymiai vienodo ilgio.
6.1. Paieška
1 – simboliai 1/0, esantys į kairę nuo galvutės iki kairiojo Y, pakeičiami simboliais A/B;
2 – požymio N skiltys iš kairės pusės po vieną keičiamos į A/B:
3,4 – galvutė pereina į dešinę iki pirmo skaitmens 1/0 ((tai bus tikrinamojo požymio skiltis), pakeičia į A/B ir patikrina sutapimą:
Į 6 būseną patenkama, jeigu skiltys nesutapo, pereinama dešinėn iki pirmojo X ir grįžtama į 1 būseną
Į 5 būseną patenkama, jeigu skiltys sutapo ir grįžtama iki kairiojo Y kitos požymio N skilties išrinkimui:
.
Kai 2 būsenoje aptinkamas X, tai reiškia, kad visos N skiltys patikrintos, sutapo ir pirmas skaitmeninis žodis į dešinę nuo A/B yra ieškomasis žodis;
Tiuringo mašinos juosta suradus požymį atrodo taip:
Jei 6 būsenoje aptinkamas dešinysis Y, ttai reiškia, kad žodžio su tokiu požymiu informacijos masyve nėra:
6.2. Perrašymas
1-randama pirma skaitmeninė žodžio skiltis, atsimenama, 0/1 pakeičiama į A/B:
2,3 – grįžtama kairėn iki Y:
4,5 – judama dešinėn iki pirmo skaitmens, įrašoma atsiminta žodžio skiltis raidine forma A/B; darbas bbaigiamas perskaičius simbolį X:
6 – galvutė gražinama į pradinę padėtį ir valdymas perduodamas pirmai būsenai – kitos žodžio skilties paieškai:
Po perrašymo gaunama tokia juosta:
Labai paprasta Tiuringo mašinai pridėti perkodavimo iš A/B į 0/1 būsenas.
Po darbo baigtinio automato vidinė būsena parodo kito žodžio požymio vyriausiąją skiltį.
7. Tiuringo mašinų modifikacijos
Susipažinus su Tiuringo mašinos darbo principais, galima pastebėti dvi tų mašinų ypatybes:
– Tiuringo mašina gali daryti daug ką, ko negali daryti mašinos su baigtiniu būsenų skaičiumi, ir, nors jų struktūra labai paprasta, gali vykdyti ir labai sudėtingus skaičiavimus;
– Tiuringo mašinoms būdingas neefektyvumas, nes net elementariuose skaičiavimuose galvutė turi daug kartų slankioti išilgai ilgų juostos atkarpų.
Galima apsiriboti dviejų simbolių alfabetu. Jei Tiuringo mašina T naudoja k skirtingų simbolių, juos galima koduoti nn skilčių dvejetainiu kodu, čia n = ]log2k[.
Tiuringo mašiną T galima pakeisti kita, T*, kuri su juosta dirba taip, tarsi jos ląstelės būtų sugrupuotos n ilgio blokais.
Šenonas 1956 m. įrodė, kad bet kuri Tiuringo mašina ekvivalentiška Tiuringo mašinai tik su dviem būsenomis.
Ekvivalentiškumas pasiekiamas Tiuringo mašinoje su daugeliu būsenų žymiai padidinus alfabeto simbolių skaičių.
Tiuringo mašina, dirbanti su begaline į abi puses juosta, ekvivalentiška Tiuringo mašinai, dirbančiai su juosta, begaline į vieną pusę.
Literatūroje aprašomi daugiajuosčių Tiuringo mašina variantai, nurodoma, kkad dargi gaunamas n-matės Tiuringo mašinos efektas.
Daugelio juostų TM
Viena juosta – daug galvučių
Dviejų dimensijų juosta
Tiesioginio kreipimosi TM
Nedeterminuota TM
8. Universali Tiuringo mašina
Nagrinėdami įvairias Tiuringo mašinas matėme, kad pradžioje juostoje būdavo kažkokia informacija, o mašinai sustojus juostoje likdavo skaičiavimų rezultatas, priklausantis
nuo pradinės informacijos ir
nuo Tiuringo mašinos tipo.
Tiuringas įrodė, kad galima padaryti vieną – vienintelę fiksuotos struktūros mašiną U, turinčią tokią savybę:
kiekvienai Tiuringo mašinai T egzistuoja tokia simbolių dT seka ir jeigu juostoje vienetiniame kode duotas skaičius x,
po jo yra seka dT ir mašina U būsenoje q0 pradeda darbą nuo kairiojo kraštinio dT simbolio, tai mašinai sustojus juostoje atsiranda skaičius f(x).
Mašina U modeliuoja mašinos T darbą nepriklausomai nuo pastarosios sudėtingumo. Mašina T gali turėti žymiai daugiau būsenų, naudoti daugiau simbolių ar naudoti skirtingus simbolius. Viskas, ko reikia mašinai U – tai simbolių sekos dT, ir ji apskaičiuos tą pačią funkciją, kaip ir mašina T.
Kas yra dT?
Matyt, tai kažkoks būdas, kuriuo mašinoje U aprašoma mašina T.
Jeigu turime Tiuringo mašinos T aprašą, pasiėmę popieriaus lapą ir pieštuką žingsnis po žingsnio galime modeliuoti Tiuringo mašinos darbą ir rasti f(x). Tą mes jau ne kartą ir darėme.
Universaliai Tiuringo mašinai reikia:
– mašinos T aprašo (juostoje),
– simbolių sekos Sx aprašo,
– darbinės zonos jjuostoje,
– sugebėjimo teisingai interpretuoti mašinos T darbo taisykles.
Universalios Tiuringo mašinos darbas turėtų būti labai paprastas:
– pagal žymę M nustatyti, kurioje juostos vietoje mašina T pradeda dirbti,
– atsiminti mašinos būsenas,
– skaityti iš imituojamos juostos,
– penkiukių lentelėje surasti naują būseną, įrašomą simbolį ir judėjimo kryptį.
Tarkime, kad mašinos T juosta begalinė tik į kairę pusę ir kad T – tik dviejų simbolių mašina. Tie apribojimai neesminiai, tik žymiai supaprastina aiškinimą. Juostoje yra tokios keturios zonos:
Aprašas: penkiukės vaizduojamos dvejetainiu kodu, atskirtos simboliais X.
Modeliuojama mašina gali turėti labai daug būsenų. Jos koduojamos dvejetainiais skaičiais ( k skilčių, k=]log2n[).
Padarius prielaidą, kad mašina T yra dviejų simbolių, sj,sij, dij kodavimui pakanka paskirti po vieną dvejetainę skiltį. Jei k=2, penkiukė atrodo taip:
Mašinos T aprašas universalios Tiuringo mašinos juostoje atrodo taip:
Darbo pradžioje zonoje "režimas” yra pradinė mašinos būsena ir simbolis, kurį mašina skaito pirmuoju, skaitanti galvutė yra ties pirmu iš kairės pusės simboliu X.
Mašinos darbo ciklą galima suskaidyti į keturias fazes:
1.Dirba paieškos mašina – dešiniojoje juostos pusėje (mašinos T apraše) ieško pirmos poros “būsena – simbolis”, sutampančios su informacija zonoje “režimas”. Po šio etapo juosta atrodo taip:
2.Dirba perrašymo mašina:
galvutė juda į dešinę, praleidžia visas raides A/B, po jų esančius skaičius qqij, sij perrašo į zoną “režimas”, o dij nespausdina, bet atsimena viena iš dviejų galimų išėjimo būsenų.
Po to juosta atrodo taip:
3.Trečioje fazėje:
– mašina juda kairėn iki žymės M, ištrina ją ir vietoje jos laikinai įrašo dij (raidėmis A/B);
– mašina juda dešinėn iki kairiojo X ir pakeliui visus A/B keičia 0/1 (atstato mašinos režimo zoną), juda dešinėn iki pirmojo 0/1 ir atgal kairėn, keisdama visus A/B į 0/1 (atstato aprašo zoną);
– skaito simbolį sij, atsimena jį (viena iš dviejų išėjimo rodyklių) ir vietoje jo įrašo specialų simbolį S.
Juosta po trečiosios fazės atrodo taip:
4.Baigiamojoje fazėje mašina:
– juda kairėn iki A/B (rodančių dij),
– spausdina toje vietoje sij (skaitmeninėje formoje 0/1),
– juda kairėn arba dešinėn (pagal kryptį, nurodytą dij),
– skaito ląstelės turinį, atsimena,
– vietoje jos spausdina M,
– juda dešinėn iki S ir spausdina perskaitytą simbolį raidine forma A/B,
– vėl grįžta į pirmą darbo ciklo fazę.
Kas įvyko atlikus vieną mašinos darbo ciklą?
Universali Tiuringo mašina pradėjo nuo poros “būsena-simbolis” qi – sj, rado penkiukę, atliko jos komandas.
Po to mašina vietoje senosios poros „būsena
– simbolis“ atspausdino naują porą, t.y., atliko vienos penkiukės komandą ir pasiruošė naujai.
Universalios Tiuringo mašinos egzistavimas reiškia, kad bet kokios Tiuringo mašinos komandų sistemą galima interpretuoti dviem būdais:
– kaip konkretaus įrenginio T aprašą,
– kaip universalios mašinos programą.
Nurodyta dvejopa abstraktaus lygio interpretacija išsaugo pagrindinius inžinerinės realizacijos pliusus ir minusus:
– konkreti mašina T dirba žymiai greičiau;
– universali mašina U sudėtingesnė, tačiau vieną kartą sukurta tinka kiek norima sudėtingiems algoritmams realizuoti;be to keičiant algoritmus nereikia kurti naujų įrenginių, pakanka pparašyti naujas programas.
9.Išsprendžiamumo problemos
• 9.1. Sustojimo problema
Radikaliausias reikalavimas– bet kuriam algoritmui A ir duomenims α nustatyti, ar bus gautas rezultatas.
Kitais žodžiais kalbant: reikia sudaryti tokį algoritmą D, kad
D(A,α)=Taip, jei A(α) duoda rezultatą,
ir D(A,α)=Ne, jei A(α) – nerezultatyvus.
Pagal Tiuringo tezę uždavinio formuluotė būtų tokia: sudaryti mašiną T0, kuri bet kuriai Tiuringo mašinai T ir bet kokiems duomenims α pereitų į būseną
T0(T, α)=Taip, jei T(α) sustoja
ir į būseną T0(T, α)=Ne, jei T(α) nesustoja.
Būtų naudinga turėti procedūrą, kuri nustatytų, ar bet kkuri TM T su juosta t kada nors sustos.
UTM problemos sprendimą supaprastina.
Pagrindinis klausimas – ar sustos bet kuri mašina T su juosta t keičiamas labiau apibrėžtu – ar sustos konkreti UTM su juosta (t)(dT).
Kita problemos sprendimo kryptis – rrasti viršutinę skaičiavimų trukmės ribą.
Šis požiūris gali pasirodyti visiškai logišku, nes:
– mašina T turi žinomą būsenų skaičių Q,
– alfabete žinomas simbolių skaičius S,
– juostoje – žinomas netuščių ląstelių skaičius N.
Būtų galima apskaičiuoti tam tikrą Q, S, N funkciją ir daryti prielaidą, kad jeigu mašina per laiką f(Q,S,N) nesustoja, tai ji niekada ir nesustos.
9.2.Sustojimo problemos neišsprendžiamumas
Jei mašina gali išspręsti sustojimo problemą visoms (T,t) poroms, tai gali tą padaryti ir daliniam atvejui
(T, dT), kai juostoje t yra pačios mašinos T aprašas dT.
Mašinai D reikia TM T aprašo ir juostos t. Dabar abu aprašai sutampa, dT = t ir mašinos D pradinė juosta būtų (dT) (dT).
Taigi, galima padaryti mašiną E, kuriai reikia tik aprašo ddT, o visa kita – kaip ir mašinoje D.
Mašina E* su dT sustoja, jei mašina T su dT nesustoja ir atvirkščiai.
O dabar “žudantis” klausimas: kas atsitiks, jei mašinai E* duosime juostą dE*?
Ji sustoja, jei mašina E*, kuriai duota juosta dE nesustoja ir atvirkščiai.
To negali būti, todėl darome išvadą, kad mašina E*, taigi ir E, ir D negali egzistuoti.
Visa tai įrodo, kad negali būti mašinos, atsakančios į bendrą klausimą
“ar sustoja mašina T su juosta t”,
nes tai apima iir klausimą
“ar sustoja mašina T su juosta dT”.
Sustojimo problemos neišsprendžiamumas reiškia, kad negalima sudaryti bendros procedūros ar programos, kuri peržiūrėtų bet kurią mašininę programą ir nuspręstų, ar ji kada nors sustos, ar ne.
Tai reiškia, kad programuotojams neverta stengtis sukurti universalią “derinimo programą”, apsaugančią programas nuo tokio tipo klaidų.
Tai taip pat reiškia, kad nėra prasmės stengtis surasti rinkinį taisyklių, kurios nuspręstų, kada bet kuris iš siūlomų algoritmų teisingas “sustojimo” prasme.
Savaime aišku, mes galime surasti taisykles, tinkančias plačioms uždavinių klasėms.
10. Raiso teorema
Apibendrinimai
Bet kuri netriviali apskaičiuojamų funkcijų savybė algoritmiškai neišsprendžiama.
Tikslesnė šios teoremos formuluotė:
tegul C – bet kokia vieno kintamojo apskaičiuojamų funkcijų klasė, netriviali ta prasme, kad egzistuoja funkcijos ir priklausančios, ir nepriklausančios C; tuomet neegzistuoja algoritmas, kuris pagal funkcijos fx numerį x nustatytų fx priklausomumą klasei C. Kitaip formuluojant – aibė {x| fx ĪC} neišsprendžiama.
Apie algoritmų numeravimą
Visų algoritmų aibė suskaičiuojama: bet kurį algoritmą galima apibrėžti baigtiniu aprašu, o fiksuoto alfabeto baigtinio ilgio žodžių aibė suskaičiuojama.
Tai reiškia, kad egzistuoja abipusis vienareikšmis atitikimo ryšys tarp algoritmų ir natūrinių skaičių, t.y., funkcija
j : Al* ® N.
Ta funkcija vadinama algoritmų numeracija, o jos reikšmės j(A) – algoritmo A numeriu numeracijoje j.
Taip pat egzistuoja atvirkštinė funkcija j-1(n)=An, pagal numerį n aatkurianti algoritmo An aprašą. Funkciją
j-1 galima vadinti algoritmų aibės išvardinimu.
Taip apibrėžus j , funkcija j-1 kai kuriuos natūrinius skaičius dekoduos į žodžius, kurie neaprašo jokio algoritmo. Tuos skaičius galima laikyti niekur neapibrėžtų algoritmų numeriais.
Iš Raiso teoremos daroma išvada, kad pagal apskaičiuojamos funkcijos numerį negalima sužinoti, ar ši funkcija pastovi, periodinė, ribota, ar jos reikšmėse yra tam tikras duotas skaičius.
Tačiau Raiso teoremoje kalbama ir apie funkcijas, ir apie algoritmus, o juos reikia skirti.
Raiso teoremos prasmė ta, kad pagal algoritmo aprašą negalima spręsti apie juo apskaičiuojamos funkcijos savybes.
Patyrusio programuotojo Raiso teorema nestebina: jis žino, kad pagal kokios nors sudėtingesnės programos tekstą, sunku suprasti, ką ji daro.
Jei tai ir suprantama, tai kiekvieną kartą – savaip; sisteminio metodo čia nėra.
Programos tekste algoritminiu būdu galima aptikti sintaksines klaidas.
Sintaksinės algoritmo savybės – tai algoritmą aprašančio teksto savybės.
Semantinės algoritmo savybės susiję su tuo, ką jis daro.
Programų derinimo metu sintaksines klaidas lengva surasti, o visos problemos susiję su derinamos programos semantika.
Truputį laisvai ir neformaliai interpretuojama Raiso teorema skamba taip:
pagal algoritmo sintaksę nieko negalima sužinoti apie jo semantiką.
Žodžiai “nieko negalima sužinoti” griežtai kalbant perdėti.
Tiksliau – “nėra vieno algoritmo, įgalinančio sužinoti”.
Negalima atpažinti visų apskaičiuojamų funkcijų, aprašytų universaliomis algoritminėmis kalbomis (Tiuringo mmašinomis ir pan.).
Apskaičiuojamų funkcijų poklasių, aprašytų specialiomis kalbomis, savybės gali būti nustatomos.
Teoriniu požiūriu neišsprendžiamumas ne nesėkmė, o mokslinis faktas.
Informatikos specialistui pagrindinių algoritmų teorijos neišsprendžiamumų žinojimas – toks pat mokslinės kultūros elementas, kaip fizikui – žinojimas, kad negalima sukurti amžinojo variklio.
Jeigu turime reikalą su neišsprendžiamu uždaviniu, tai reikia gerai žinoti du dalykus:
pirma – algoritmo, išsprendžiančio tą problemą, nebuvimas nereiškia, kad daliniu atveju tos problemos negalima išspręsti;
antra – neišsprendžiamumo pasirodymas – tai dažniausiai pernelyg plačios uždavinio formuluotės rezultatas.
11. Skaičiavimų sudėtingumas
Algoritmiškai išsprendžiamų problemų klasė.
Turint universalų algoritmo modelį – TM, galima formaliai nagrinėti efektyvumo problemą.
Kaip galima išmatuoti skaičiavimo proceso efektyvumą, kaip nustatyti, kuris skaičiavimo procesas efektyvesnis. Formaliai vykdymo trukmę galima nustatyti naudojant matematinį algoritmo modelį – standartinę (vienos juostos, vienos galvutės) TM. Konkrečiai TM M ir įėjimui w algoritmo vykdymo (skaičiavimo) trukmė tM(w) yra žingsnių skaičius, atliekamas nuo pradinės būsenos iki sustojimo.
Tiuringo mašina M, atpažįstanti palindromus
w = wR
onaano
Pirmoje fazėje M atlieka |w| +2 komandų;
antroje fazėje – (|w|+2)-2 komandų;
trečioje fazėje – (|w|+2)-4 komandų ir t.t.
Bendras fazių skaičius yra |w|/2
([|[|w|/2] nelyginiam w).
Taigi, vykdymo trukmė
tM(w) = c*|w|2.
Nagrinėsime Tiuringo mašinos M vykdymo trukmę kaip funkciją
f : N → N,
čia f(n) maksimalus Tiuringo mašinos
žingsnių kiekis bet kokiai n simbolių ilgio įėjimo sekai.
Kaip algoritmai (realizuojami Tiuringo mašina) elgiasi ilginant įėjimo sekas. Tokio tipo analizė vadinama asimptotine.Tarkime, kad
f(n) = 2*n3+2*n+5 ir
g(n) = 10*n2+3.
Kai n ≤ 4, f(n) ≤ g(n), tačiau, didinant n, f augs žymiai greičiau už g;
f augimo greitį nulemia aukščiausio laipsnio dedamoji n3.
Fakto, kad g augimo greitis nedidesnis už f augimo greitį parodymui naudojamas taip vadinamas didžiosios O pažymėjimas (big-O notation):
g(n)=O(f(n)).
Pati f(n) yra O(n3).
Kiek mes ggalime sužinoti apie realų sprendžiamo uždavinio sudėtingumą iš ką tik pasiūlyto skaičiavimų sudėtingumo įvertinimo modelio?
Dviejų galvučių vienos juostos Tiuringo mašina gali atpažinti palindromus greičiau. Ši mašina (K) turi tik perstumti antrą galvutę į dešinįjį eilutės galą ir stumti galvutes vieną link kitos palyginant jų skaitomus simbolius. Tokios mašinos K vykdymo laikas
tK(n) yra c*n.
Tai reiškia, kad
vykdymo laikas priklauso nuo naudojamo modelio ir betarpiška išvada būtų ta, kad apie realų sprendžiamos problemos sudėtingumą mes labai mažai sužinome mmatuodami vykdymo laiką.
Atidžiau išnagrinėjus vieno algoritmo modelio modeliavimą kitu, galima padaryti tokią išvadą:
jeigu K yra kokia nors determinuota Tiuringo mašina, kurios vykdymo laikas tK(n), o M – kokia nors kita Tiuringo mašina, kuri modeliuoja K per laiką tM(n) , ttai tK(n) yra
O(p(tM(n))),
čia p(x) – koks nors polinomas.
Pavyzdys. Dviejų galvučių Tiuringo mašina K atpažįsta palindromus per laiką
tK(n)=c*n.
Modeliuodami šį uždavinį standartine vienos galvutės mašina M gauname laiką
tM(n)=c’*n2.
Šiuo atveju polinomas p(x) yra d*x2, čia d – kokia tai konstanta.
Kada mes keičiame algoritmo formalizavimą, jo vykdymo laikas gali išaugti, bet augimo greitis polinomiškai apribotas.
Ar šis faktas svarbus praktiškai? Norėdami atsakyti į šį klausimą, apibrėžkime tokią Tiuringo mašinų klasę:
Tiuringo mašina M yra polinomiškai apribota, jei egzistuoja toks polinomas p(x), kuriam galioja
tM(n)≤p(n),
čia n – bet koks teigiamas skaičius.
Kalba vadinama polinomiškai išsprendžiama, jei egzistuoja ją išsprendžianti polinomiškai apribota Tiuringo mašina.
Visų polinomiškai išsprendžiamų kalbų klasė žymima simboliu P. P kalbų pavyzdžiai – visos reguliarios kalbos, palindromų kalbos.
Yra paprastas ššios problemos sprendimo algoritmas – kiekvienai viršūnių sekai ai1, ai2, ., aik, k≤n nustatyti, ar egzistuoja kelias, apeinantis visas viršūnes ir tada rasti minimalaus ilgio kelią.
Algoritmo problema – reikia išnagrinėti pernelyg daug kelių. Bendrasis sekų ai1, ai2, ., aik, k≤n kiekis yra (n-1)! ir net nedideliems n, pvz., n=11, reikia patikrinti
10!=3 628 800 kelių.
Šis pavyzdys paaiškina klasės P prasmę, plačiai pripažintą kompiuterių mokslo bendruomenėje:
klasei P priklauso problemos, kurios turi praktiškai įvykdomus algoritminius sprendimus.
Tam tikra prasme ššis tvirtinimas gali būti interpretuojamas kaip kiekybinė Čerčo-Tiuringo tezės versija.
Kai visos Tiuringo mašinos sprendžia visas potencialiai išsprendžiamas skaičiavimų problemas, tai polinomiškai ribotos Tiuringo mašinos sprendžia visas praktiškai įvykdomas skaičiavimų problemas.
Kaip vertinti šią naują Čerčo-Tiuringo tezės versiją?
Tarkime, algoritmo vykdymo laikas x1000.
Galima sutikti, kad šis algoritmas praktiškai neįvykdomas. Netgi algoritmas, kurio vykdymo laikas 100100×2 vargu ar gali būti laikomas praktiškai įvykdomu. Vis dėlto, kai randamas polinomiškai apribotas sudėtingos problemos sprendimo algoritmas, jis dažnai parodo praktinį šios problemos išsprendimo būdą. Tai gali būti laikoma griežtai empiriniu argumentu, paremiančiu kiekybinę Čerčo-Tiuringo tezės versiją.
Mes iki šiol neatsakėme į pagrindinį klausimą: ar egzistuoja ne P klasės išsprendžiamos kalbos, t.y. tokios, kurios negali būti išspręstos polinomiškai apribotais algoritmais?
Kad egzistuoja aplamai neišsprendžiamos problemos, mes parodėme aptardami sustojimo problemą, kurios negalime išspręsti Tiuringo mašina.
Panašiu būdu galima parodyti, kad egzistuoja ne P klasės išsprendžiamos problemos. Norint tai padaryti, reikia aptarti išsprendžiamas problemas su polinomiškai neapribotu sprendimo laiku.
12.Klasė NP
Kiekvienas grafas G aprašomas pora (V,E), čia V yra baigtinė viršūnių aibė, o EĶV´V yra briaunų aibė. Kelias yra tokia viršūnių seka v1,v2, ., vn, kai kiekvienam i (1£ i
