algoritmų teorija

algortmų teòrija, matematikos bei informatikos mokslų šaka, tirianti algoritmų savybes. Jos nagrinėjamos atsižvelgiant į algoritmais nustatomą pradinių duomenų ir rezultatų atotykį, įvairių algoritmų sudarymą bei jų sudėtingumą. Sakoma, kad visuma objektų, kuriems pritaikomas nagrinėjamas algoritmas, sudaro algoritmo pritaikymo aibę. Algoritmas u apskaičiuoja funkciją f, jei jo pritaikymo aibė X sutampa su funkcijos f apibrėžimo sritimi ir kiekvienam aibės X elementui x algoritmas u priskiria f(x). Algoritmas u išsprendžia aibę A (tokia aibė vadinama rekursine) aibės X atžvilgiu, jei X yra algoritmo u pritaikymo aibė ir kiekvienam elementui iš aibių A ir X sankirtos algoritmas u priskiria žodį taip, o kiekvienam elementui iš aibių X ir A skirtumo – žodį ne. Sakoma, kad funkcija apskaičiuojama, jei egzistuoja ją apskaičiuojantis algoritmas. Aibė vadinama išsprendžiama aibės X atžvilgiu, jei egzistuoja algoritmas, išsprendžiantis tą aibę X atžvilgiu. Algoritmo su tam tikromis savybėmis sudarymas vadinamas algoritmine problema; pvz., sudaryti algoritmą turimai funkcijai apskaičiuoti. Algoritminė problema neišsprendžiama, jei negalima sudaryti norimo algoritmo (pvz., diofantinių lygčių neišsprendžiamumą įrodė Jurijus Matijasevičius 1970). Nagrinėjami algoritmų sudėtingumų įverčiai. Trukmė ir sintaksinis algoritmo aprašymas yra pagrindiniai algoritmo sudėtingumo kriterijai. Algoritmų teorija atsirado 1934–37, kai buvo tikslinama intuityvioji algoritmo sąvoka, taikant bendrą rekursyviųjų funkcijų sąvoką (Jacquesʼas Herbrand’as, K. Gödelis, Alonzo Churchas, S. C. Kleene’as), ir idealizuotos skaičiavimo mašinos sąvoka (A. M. Turingas, E. L. Postas). Vėliau algoritmo sąvoką tikslino daugelis matematikų. Įrodyta, kad visi pasiūlytieji patikslinimai yra ekvivalentūs. Be to, nepavyko rasti nė vienos intuityviąja prasme apskaičiuojamos funkcijos, kuri nebūtų rekursyvioji. Tai buvo pagrindiniai argumentai, kuriais remiantis Alonzo Churchas 1936 paskelbė tezę: algoritmiškai apskaičiuojamųjų funkcijų aibė sutampa su rekursyviųjų funkcijų aibe. Lietuvoje algoritmų sudėtingumą nagrinėjo bei kai kurių algoritmų apatinius įverčius aprašė Stasys Jukna.

35