Algoritmai. Pagrindiniai reikalavimaiAlgoritmai tai fiktyvios procedūros padedančios vienareikšmiškai gauti rezultatus. Pagrindinai algoritmai taikomi matematikoje negalimų uždavinių sprendimui.Technikoje algoritmai – tai galimybė uždavinį spręsti programiškai.Pagrindinės algoritmų savybės:1.Algoritmas naudojamas su pradiniais duomenimis ir algoritmas duoda rezultatus. Pasirodo ir tarpiniai rezultatai. Taigi riekia nurodyti ir duomenų reikalavimus. Duomenys gali būti ir vaizdiniai. Todėl algoritmų teorijoje nenaudojamas žodinis duomenų apibrėžimas. Fiksuojami baigtiniai pradinių objektų rinkiniai ir baigtinis kitų objektų sudarymo būdų ir elementariųjų objektų rinkinys. Elementariųjų objektų rinkinys sudaro baigtinį pradinių simbolių alfabetą.Tipinis kitų objektų sudarymo būdas – indukcija.Baigtinio alfabeto baigtinio ilgio žodžiai – tipiškiausias algoritminių duomenų pavyzdys.2.Duomenys talpinami atmintyje. Ji paprastai laikoma vienalyte ir diskretine, viena ląstelė atsimena vieną duomenų simbolį. Teoriškai atmintis gali būti begalinė.3.Algoritmas susideda iš elementarių žingsnių arba veiksmų, skirtingų žingsnių arba veiksmų aibė yra begalinė. Tipinis pavyzdys – kompiuterio komandų sistema.4.Algoritmų žingsnių seka determinuota: po kiekvieno žingsnio nurodomas kitas, kurį reikia atlikti, arba sustojama.5.Iš algoritmų reikalaujama rezultatyvumo:t.y. kad po baigtinio žingsnių skaičiaus būtų sustojama ir rodomas rezultatas.6.Reikia skirti:– Algoritmo aprašą (instrukcijos/programa)– alg. realizacijos mechanizmą (kompiuterį) – algoritmo vykdymo procesą – veiksmų seką, gaunamą pritaikant algoritmą konkretiems duomenims.Algoritmų modeliaiTaikomas metodas:1.Parenkamas baigtinis pradinių objektų rinkinys, tie objektai laikomi elementariais2.Parenkamas baigtinis naujų objektų sudarymo būdų rinkinysAlgoritminiai modeliai turi būti universalūs, t.y., tikti visų algoritmų aprašymui. Todėl gali kilti klausimas: ar konkrečių priemonių parinkimas nesumažins formalizavimo bendrumo?1.Įrodoma, kad vieną modelį galima pakeisti kitu, t.y., kad bet kuris algoritmas, aprašytas vieno modelio priemonėmis, gali būti aprašytas ir kito modelio priemonėmis; 2.Algoritmų teorijoje pasinaudojant modelio pakeičiamumu pavyko sukurti invariantišką modelių atžvilgiu sąvokų sistemą, įgalinančią aptarti algoritmų savybes nepriklausomai nuo formalizacijos. Ta sąvokų sistema pagrįsta apskaičiuojamų funkcijų sąvoka.
Yra trys pagrindiniai universalių algoritmų modelių tipai:1.Tipas susieja algoritmo sąvoką su tradicinėmis matematikos sąvokomis – apskaičiavimais ir skaitmeninėmis funkcijomis; geriausiai išvystytas ir ištirtas šitokių modelių tipas – rekursyviosios funkcijos – istoriškai pirmoji algoritmo sąvokos formalizacija;2.Tipas remiasi algoritmo vaizdavimu determinuotu įtaisu, gebančiu atlikti labai primytivias operacijas. Pagrindinis šio tipo teorinis modelis – Tiuringo mašina (1936m.)3.Tipas – bet alfabetų žodžių perdirbimas, šio tipo privalumai – maksimalus abstraktumas ir galimybė pritaikyti algoritmo sąvoką bet kokios prigimties objektams(nebūtinai skaitiniams)Modelių pavyzdžiai – Posto sistemos, normaliniai Markovo algoritmai.
Efektyvios procedūros ir algoritmaiMašinos neturi intelektualaus lankstumo.Skaičiavimo mašina yra tikslaus proceso apdorojimas1.Viskas kas gali būti padaryta su skaičiavimo mašina gali būti atitinkamai aprašyta.2.Bet kuri procedūra, kurią galima tiksliai aprašyti gali būti suprogramuota skaičiavimo mašina. Šiuo atveju remiamasi A.M. Tiuringo darbais. Kyla 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 apibrėžti procesai, kurių negalima aprašyti?Efektyvi procedūra(EP) – tai aibė nuosekliai laike atliekamų instrukcijų/taisyklių, tiksliai reglamentuojančių mūsų ar kieno nors elgesį.Šis apibrėžimas netikslus, nes instrukcijų interpretavimas neturi priklausyti nuo kokio nors subjekto.Subjekto sugebėjimas įvykdyti instrukcijas priklauso nuo jo žinių, intelekto lygio.Šią problemą galima išspręsti, jei kartu su taisyklėmis apibrėžtume ir interpretuojančio įrenginio konstrukciją. Tai padėtų išvengti neapibrėžtumų.Patogu būtų turėti:– kalbą, kuria aprašoma elgesio taisyklių aibė– vieną – vienintelę mašiną, kuri interpretuotų tos kalbos nurodymus ir žingsnis po žingsnio tiksliai atliktų nurodytus procesus.Pagrindinė tokios 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.Kiekviename darbo žingsnyje į tą mašiną dalį, kuri turi baigtinį būsenų skaičių, įvedamas perskaitytas iš juostos simbolis. Mašinos atsakymas gali pakeisti tą simbolį arba perstumti mašiną į bet kurią pusę – kito takto metu bus skaitomas naujas simbolis. Tai reiškia, kad be tos atminties, kurią turi dalis su baigtiniu būsenų skaičiumi, yra elementari išorinė atmintis. kadangi juostos ilgio neribojame, ši atmintis teoriškai yra begalinė.Pagal mašinos ir juostos ryšį gali pasirodyti, kad tos neribotos atminties panaudojimo galimybės nedidelės, tačiau 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 galima pavadinti EP, gali būti realizuotas Tiuringo mašina.Tiuringo mašinosTai baigtinis automatas sujungtas su išorine atmintimi (juosta). Juosta suskirstyta į ląsteles, į kiekvieną ląstelę galima rašyti simbolį. Baigtinis automatas su juosta sujungtas galvute, kuri skaito, rašo pasislenka per vieną poziciją.Baigtinis automatas aprašomas įėjimo simbolio alfabetu S0…Sn, išėjimo simbolių aibe r0…rn vidinių bus aibė q0…qnAprašomas dviem f-jomisQ(t+1)=G(Q(t),S(t))- aprašo vidinės būsenos pasikeitimąR(t+1)=F(Q(t),S(t))- aprašo baigtinio automato būsenątiuringo mašinoje išėjimas atlieka dvi funkcijas: įrašymas į ląstelę ir pasislinkimas, taigi jo išėjimas: R(t+1)=F(Q(t),S(t))-> simbolisD(t+1)=D(Q(t),S(t))-> apraš) galvutės judėjimo kryptį.Kiekvienam darbo taktebūdama būsenoje qi, skaito simbolį si, pereina į būseną Q(qi,sj) spausdina F(qi,sj) ir pasislenka D(qi,sj)
Spausdinant naują simbolį senasis ištrinamas. Iš pradžių juosta tuščia išskyrus baigtinį ląstelių skaičių.Tiuringo automatas aprašoma “penkiukėmis”:SB – sena būsena qi SS – skaitomas simbolis SjNB – nauja būsena Q(qi,sj) arba qijĮS – įrašomas simbolis R(qi,sj) arba sijJK – judėjimo kryptis D(qi,sj) arba dijqi sj qij sij dijq0q0q1 01Pa q0q1H 000 DD–Pa – pabaiga, H – sustojaTM skaičiavimai apibrėžiami nurodant sąlygą:1.Nurodoma pradinė baigtinio automato q02.Nurodant skaičiančios galvutės padėtį.Tiuringo mašinų atminties valdymasPaieškaUi – žodžių aibėNi – kiekvienas žodis turi požymįŽodžiai ir jų požymiai atvaizduoti dvejetaine forma, išdėstyti juostose poromis NiUi ir atskirti simboliais. Simboliai Y žymi aibės pradžią ir pabaigą. visi požymiai vienodo ilgio.Informacijos masyve reikia rasti žodį su požymiu N. Tiuringo mašinos juosta atrodo taip: …. Y N X N1U1 N2U2 X … X NIUI X … Informacinis masyvas ….X 101 X 001 X 011 X 101 111 X 111 000 X …. Mašina naudoja du papildomus simbolius A=0 ir B=1 (jie pažymi papildomą informaciją)TM darbo algoritmą aprašysime būsenose atitinkamomis funkcijomis:1.Simboliai 1/0, esantys į kairę nuo galvutės iki kairiojo Y pakeičiami simboliais B/A2.Požymio N skiltys iš kairės pusės po vieną keičiamos į A/B;3.4.Perėjimas į dešinę iki pirmo skaitmens 1/0 (tai bus tikrinamojo požymio skiltis) keičia į B/A ir patikrina sutapimąį 5.būseną patenkama, jei skiltys sutapo ir grįžtama iki kairiojo Y kito požymio skilties išrinkimui.į 6. būseną patenkama, jei lyginamos skiltys nesutapo, pereinama dešinėn iki pirmo X, grįžti į pirmą būseną (visas nepatikrintas N ir Ni skaitmenines skiltis pakeisti į A/B ir kartoti procesą su kito žodžio požymiu)
Kai 2-oje 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 žodisKai 6 būsenoje aptinkamas Y, tai reiškia, kad žodžio su tokiu požymiu informacijos masyve nėra.TM juosta suradus požymį suradus atrodo taip:Y 101 X AAB ABB X BAB 110 X 111 000 Y N D N1 U1 N2 U2 N3 U3Jeigu žodžio su ieškomu požymiu nėra, galvutė sustoja ties dešiniuoju Y.PerrašymasSuradus žodžio požymį dažniausiai reikia informaciją perrašyti į kitą vietą. Šiuo atveju TM perrašo žodį į požymio N vietą. Gaunama tokia juosta. Y 101 X AAB ABB X BAB 110 X 111 000 Y N D N1 U1 N2 U2 N3 U3TM darbo algoritmą aprašysime būsenose atliekamomis funkcijomis:1. – Judama dešinėn, randama pirma skaitmeninė žodžio skiltis, atsimenama, 0/1 pakeičiama į A/B2.3. – Grįžtama kairėn iki Y4.5. – Judama dešinėn iki pirmo skaitmens, įrašoma atsiminta žodžio skiltis raidine forma A/B; Darbas baigiamas perskaičius simbolį X6. – galvutė gražinama į pradinę padėtį ir valdymas perduodamas pirmai būsenai – kitos žodžio skilties paieškai;Po darbo baigtinio automato vidinė būsena parodo kito žodžio požymio vyriausiąją skiltį.
TM naudojimas F-jų skaičiavimuiTM gali užduoti kažkokią f-ją. kalbėsim tik kur argumentai sveiki skaičiai 0,1,2…f(x) yra apskaičiuojama pagal Tiuringą jeigu jos reikšmės gali būti apskaičiuojamos TM, kurios juostos pradžioje užrašytas tik argumentas X ir mašinai sustojus juostoje atsiranda skaičius f(x)Tiuringas įrodė, kad galima sukurti vieną vienintelę mašiną U su fiksuota baigtinio automato struktūra ir turinčią tokią savybę, kad bet kuriai TM “T” egzistuoja tokia simbolių seka dT kad jeigu tuščioj juostoj duotas vienetinis skaičius X, o po to seka dT ir U būsenoje q0 pradeda darbą nuo kairiojo dT simbolio, tai mašinai sustojus juostoje atsiranda skaičius F(x). Tai reiškia, kad mašina U modeliuoja mašinos “T” darbą nepriklausomai nuo sudėtingumo.
Mašinos U egzistavimas yra patvirtinimas, kad TM efektyvumas pagrįstasGaliausiai parodoma, kad neegzistuoja efektyvesnis įvertinimas.11.UTMUTM naudojamas interpretuojančių mašinų darbo principas. Jei turime kažkokios TM aprašymą, ir duomenų Sx aprašą, tai galima sumodeliuoti TM ir rasti f-ją, kurią TM turi sumodeliuoti. UTM reikia to paties T aprašo juostoje dT, simbolių sekos Sx aprašo, darbinės zonos juostoje ir sugebėjimo teisingai interpretuoti Tm darbą. UTM darbas paprastas: pagal žymę M nustatyti kurioje vietoje mašina pradeda dirbti, reikia atsiminti mašinos būsenas, skaityti simbolius, kreiptis į penkiukių lentelę, surasti naują būseną, kokį simbolį įrašyti ir kur pasislinkti. UTM juosta begalinė tik į vieną pusę, tai tik dviejų simbolių mašina(supaprastinimas), juostoje galima išskirti keturias zonas.1. begalinė į kairę pusę(darbinė zona), 2. Mašinos T būsena, 3. Simbolis, kurį mašina ką tik perskaitė, arba įrašys, 4. Mašinos T aprašas dT.UTM darbo ciklą galima suskaidyti į keturias dalis.1.Paieška.-dešiniojoje juostos pusėje (T apraše) ieško pirmos poros “būsena-simbolis”, sutampančios su informacija zonoje “režimas” Visa skaitmeninė informacija perkoduojama simboliais, ir grįžtama prie kairiojo kraštinio X.2. Perrašymas- galvutė juda į dešinę, praleidžia visas raides, o po jų esančius skaičius qij ir sij perrašo į zoną režimas.3.Atstatymo etapas- 3.1. juda kairėn iki žymės M, ištrina ją, ir vietoje jos įrašo dij raidine forma.3.2.Judama dešinėn iki kairiojo X ir visos raidės A/B keičiamos į 0/1. Judama dešinėn iki pirmo skaitmens ir kairėn keičiant visus A/B į 0/1. 3.3. Skaitomas simbolis Sij atsimenama viena iš išėjimo rodyklių , o vietoje jo įrašomas pagalbinis simbolis S. 3.4.Baigiamoji fazė. 1) mašina juda kairėn iki A/B; 2) Vietoje A/B spausdinamas Sij;3)juda kairėn arba dešinėn;4)skaito tos lentelės turinį, atsimena; 5) ir vietoje jos spausdina M;6)juda dešinėn iki simbolio S ir rašo A arba B. UTM gali imituoti bet kurį procesą.12.Efektyvaus išsprendžiamumo problemos12.1. Sustojimo problema.Kai TM pradeda dirbti gali praeiti daug laiko, kol ji sustos, tačiau skaičiavimo procesas gali būti begalinis, taigi naudinga turėt procedūrą, kuri suskaičiuotų kada TM su begaline juosta sustos. UTM problemos sprendimą supaprastinę galime TM aprašą dT patalpinti vieną juostą ir tą aprašą paduoti bet kuriai TM. Jei T su t nesustoja, tai T su dT irgi nesustos. Kita sprendimo kryptis, rasti viršutinę skaičiavimo trukmės ribą. Mašina T turi baigtinį būsenų skaičių Q, simb. sk. S, juostoje žinomas netuščių langelių kiekis N. Ir būtų galima sudaryti kintamųjų f-s f(Q,S,N) ir daryti prielaidą: jei mašina per f(Q,S,N) laiką nesustos, tai ji niekada nesustos. Rašoma kad laiko riba egzistuoja, tačiau neegzistuoja mašina, kuri galėtų tą ribą apskaičiuoti.12.2. Sustojimo problemos neišsprendžiamumas.Turim mašiną D galinčią pagal TM aprašą dT ir juostos aprašą t nustatyti ar toj mašinoj T baigsis skaičiavimai, kadangi uždavinys bendras ir jei ta mašina D gali išspręsti sustojimo problemą visoms (T,t) poroms, tai turi galėti išspręsti ir daliniam atvejui, kai juostoje t yra pačios mašinos aprašas dT (dT, dT) Čia mes galime padaryti naują mašiną E => , kuri nedaug skiriasi nuo mašinos D.x- bet koks simbolis, t.y. įvedamas amžinas ciklas, kuris neleidžia mašinai E* sustoti , jei patenkama į būseną “taip”. Mašina E* sustoja, jei T su dT nesustoja, ir atvirkščiai.Žudantis klausimas: kas bus jei E* duosime juostą d E (jos pačios aprašą). To negali būti, ir tai rodo, kad nei mašina E* nei E nei D negali egzistuoti. Taigi prieštaros būdu įrodėme, kad nėra mašinos, kuri atsakytų į bendrą klausimą. Sustojimo problemos neišsprendžiamumas įrodo, kad negalima sukurti procedūros, kuri patikrintų ar mašima sustos ar ne. Kai atmintis baigtinė, sustojimo problema bent jau teoriškai išsprendžiama.
13. Raiso teorema (jos apibendrinimai)Peržiūrėjus algoritmiškai neišsprendžiamų uždavinių aibę, matome, kad tai susiję su savianalize,kai mašina nagrinėja savo aprašą.Raiso teorema. Bet kuri netriviali, apskaičiuojamų f-jų savybė algoritmiškai neišsprendžiama. Tikslesnė 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. Raiso teoremos prasme ta , kad pagal algoritmo aprašą negalima spręsti apie to algoritmo f-jos savybes. Pagal du algoritmus negalima nustatyti ar jie apskaičiuoja tą pačią funkciją. Yra sintaksinės ir semantinės algoritmų savybės. Pagal algoritmo sintaksę, negalima nieko nustatyti apie jo semantiką.1. bendro algoritmo išsprendžiančiu tą problemą nebuvimas nereškia, kad daliniu atveju tos problemos išspręsti negalima;2. Neišsprendžiamumo pasirodymas- tai dažniausiai pernelyg bendros/plačios uždavinio formuluotės rezultatas.