Az algoritmusok rögzítési módszerei
Az absztrakt automatákon alapuló algoritmus (Turing gép)
A rekurzív függvényeken alapuló algoritmus meghatározása
A rekurzió egy olyan függvény meghatározásának folyamata, amelyben az argumentumok tetszőleges értékeire vonatkozó értékét ismert módon fejezzük ki az argumentum kisebb értékeinek függvényében.
Az a függvény, amelyre létezik értékelési algoritmus bármely függvénynek a függvénydefiníció tartományában, számítható.
Olyan függvény, amelyre a rekurzió alapján számítási módszer hatékony, rekurzív.
A rekurzív függvények osztálya megegyezik az egyetemesen meghatározott számítható függvények osztályával - az egyház tézisével.
Egy függvényt, amelyet nem az összes argumentum értékére definiálunk, hanem csak egy bizonyos részhalmazra, részleges függvénynek nevezzük.
Az algoritmusok által kiszámítható összes részfunkció részben rekurzív - Kleene tézise.
A részleges rekurzív függvények fogalmát használjuk a probléma algoritmikus oldhatóságának vagy feloldhatatlanságának bizonyítására.
Az algoritmikus folyamatok olyan folyamatok, amelyeket egy megfelelően rendezett "gép" képes végrehajtani.
A "gép" ebben az esetben néhány absztraktot jelent, amely csak a képzeletbeli gépben létezik.
Általában egy ilyen gép a következő részekből áll:
- a korlátlan mindkét oldal információs szalag, osztva cellák, amely a korlátlan memória a gép. Minden cellában csak egy karaktert tárolhat, beleértve a nulla értéket is;
- az olvasó / írófejből, amely mentén a szalag mozoghat;
- A vezérlőeszköz, amely minden egyes pillanat alatt valamilyen "állapotban" van. A vezérlőegység lehet bizonyos véges számú állapotban, ha ez az állapot végleges, a gép befejezi a munkát.
Egy ilyen gép a szalagot egy cellát balra vagy jobbra mozgatja, a cellák tartalma változatlan marad, vagy megváltoztathatja az észlelt cellának állapotát, és a szalagot helyben hagyja. A Turing gép tetszőleges véges ábécében működik és véges számú megrendelést végez.
A Turing gépek univerzális végrehajtók, amelyek használatával szimulálhatják a matematikusok által leírt összes algoritmikus folyamatot. Bebizonyosodott, hogy ezeken a gépeken kiszámítható funkciók csoportja pontosan egybeesik az összes részleges rekurzív függvény osztályával. így az egyik típusú vagy másik probléma algoritmusának létezésére vagy hiányára vonatkozó kérdést úgy kell értelmezni, mint egy szükséges tulajdonsággal rendelkező Turing-gép létezését vagy nem létezését.
A Turing-gép intuitív megértése: ez egy végtelen szalag, amelyet cellákra osztanak. A kocsi ketrecekkel megy. A ketrecbe írt levél elolvasása után a kocsi jobbra, balra vagy helyben marad, míg a betűt újra cseréli. Néhány betű megállítja a kocsit, és leáll.
Számos módszer létezik olyan algoritmusok rögzítésére, amelyek láthatósága, kompaktsága és formalizációjuk miatt különböznek egymástól. Legelterjedtebb: verbális, grafikus, szoftveres.
A felvétel grafikus módszere egyes grafikus szimbólumok - blokkok használatát jelenti, amelyek mindegyike egy bizonyos típusú műveletet jelez.
Minden blokk előírja bizonyos műveletek végrehajtását. A blokkok készlete egy algoritmust vagy blokkdiagramot képez.
Egyes blokkok kijelölése a GOST 19.701-90 szerint ALGORITMUSOK, DATA PROGRAMOK ÉS RENDSZEREK RENDSZEREI