Algoritmai. Pagrindiniai reikalavimai
Algoritmai 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ų modeliai
Taikomas metodas:
1.Parenkamas baigtinis pradinių objektų rinkinys, tie objektai laikomi elementariais
2.Parenkamas baigtinis naujų objektų sudarymo būdų rinkinys
Algoritminiai 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 algoritmai
Mašinos neturi intelektualaus lankstumo.
Skaičiavimo mašina yra tikslaus proceso apdorojimas
1.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: