Normál algoritmus

Az oldal jelenlegi verzióját még nem ellenőrizték tapasztalt közreműködők, és jelentősen eltérhet a 2021. november 10-én felülvizsgált verziótól ; az ellenőrzések 2 szerkesztést igényelnek .

Markov normál algoritmusa (algoritmusa) ( NAM , szintén Markov-algoritmus ) az egyik szokásos módja az algoritmus fogalmának formális meghatározásának (egy másik jól ismert módszer a Turing-gép ). A normálalgoritmus fogalmát A. A. Markov (junior) vezette be az 1940 -es évek végén az asszociatív számítások elméletének egyes problémáinak megoldhatatlanságáról szóló munkáiban. Az "algori f m" szó hagyományos írásmódja és kiejtése ebben a kifejezésben szintén a szerzőjéhez nyúlik vissza, aki sok éven át matematikai logika tanfolyamot tanított a Moszkvai Állami Egyetem Mechanikai és Matematikai Karán .

A normál algoritmus a karakterláncok újraírásának módszerét írja le, hasonlóan a formális nyelvtanokhoz . A NAM egy Turing-teljes nyelv, amely kifejezőerejében egyenértékű a Turing-géppel , és így a modern programozási nyelvekkel. A Refal funkcionális programozási nyelv a NAM alapján jött létre .

Leírás

A normál algoritmusok verbálisak, azaz különféle ábécé szavakra való alkalmazásra szolgálnak.

Bármely normál algoritmus definíciója két részből áll: az algoritmus ábécéjének meghatározása (azokra a szavakra, amelyek karaktereiből az algoritmust alkalmazni fogja) és a sémájának meghatározásából . A normál algoritmus sémája úgynevezett helyettesítési képletek véges rendezett halmaza , amelyek mindegyike lehet egyszerű vagy végleges . Az egyszerű helyettesítési képletek formájú szavak , ahol és két tetszőleges szó az algoritmus ábécéjében (ezeket a helyettesítési képlet bal és jobb oldalának nevezik). Hasonlóképpen, a végső helyettesítési képletek formájú szavak , ahol és két tetszőleges szó az algoritmus ábécéjében. Feltételezzük, hogy a és a segédbetűk nem tartoznak az algoritmus ábécéjéhez (egyébként két másik betűt kell választani, hogy elválasztó szerepet töltsön be a bal és a jobb oldali rész között). $L-től D-ig$ $L$ $D$ $L\to \cdot D$ $L$ $D$ $\nak nek$ $\to \cdot$

Egy ötbetűs ábécé normál algoritmussémája például a séma $|*abc$

$\left\{{\begin{matrix}|b&\to &ba|\\ab&\to &ba\\b&\to &\\{*}|&\to &b*&\\{*}&\to &c&\ \|c&\&c\\ac&\&c|\\c&\cdot \end{mátrix}}\jobbra.$

Az algoritmus ábécéjében szereplő tetszőleges szóra a normál algoritmus alkalmazásának folyamata elemi lépések diszkrét sorozata, amely a következőkből áll. Legyen az algoritmus előző lépésében kapott szó (vagy az eredeti szó , ha az aktuális lépés az első). Ha a helyettesítési képletek között nincs olyan, akinek a bal oldala benne lenne , akkor az algoritmus munkája befejezettnek tekintendő, és ennek a munkának az eredménye a szó . Ellenkező esetben a helyettesítési képletek közül, amelyek bal oldali részét tartalmazza , a legelső kerül kiválasztásra. Ha ennek a helyettesítési képletnek az alakja van , akkor a szó alakban szereplő összes lehetséges reprezentációja közül kiválasztjuk azt, amelyik a legrövidebb, ami után az algoritmust az eredménnyel befejezettnek tekintjük . Ha ennek a helyettesítési képletnek az alakja van , akkor a szó összes lehetséges reprezentációja közül az alakban azt választjuk ki, amelyikhez a legrövidebb, ami után a szó az aktuális lépés eredményének minősül, és a következőnél további feldolgozásra kerül. lépés. $V$ $V'$ $V$ $V'$ $V'$ $V'$ $L\to \cdot D$ $V'$ $RLS$ $R$ $RDS$ $L-től D-ig$ $V'$ $RLS$ $R$ $RDS$

Például az algoritmus fent jelzett sémával való alkalmazása során a , , , , , , , , és szavak egymás után megjelennek a szó mellett, ami után az algoritmus az eredménnyel zárul . Lásd alább további példákat. $|*||$ $|b*|$ $ba|*|$ $a|*|$ $a|b*$ $aba|*$ $baa|*$ $aa|*$ $aa|c$ $aac$ $ac|$ $c||$ $||$

Bármely normál algoritmus egyenértékű valamilyen Turing-géppel , és fordítva, bármely Turing-gép egyenértékű valamilyen normál algoritmussal. A Church-Turing tézis egy változatát , amelyet a normál algoritmusokkal kapcsolatban fogalmaztak meg, általában "normalizációs elvnek" nevezik.

A normál algoritmusok kényelmes eszköznek bizonyultak a konstruktív matematika számos ágának megalkotásához . Ezenkívül a normál algoritmus meghatározásában rejlő ötleteket számos programozási nyelvben használják, amelyek a szimbolikus információk feldolgozására irányulnak - például a Refal nyelvben .

Példák

1. példa

A Markov-algoritmus használata karakterláncokon történő transzformációkhoz.

Ábécé:

{ a ... i, A ... I, "szóköz", "pont" }

Szabályok:

A → narancs
kg-tól kilogrammig
M → bolt
T → hangerő
bolt →. istálló (végső képlet)
abban a bódéban → azon a piacon

Forrás sor:

T M-ben vettem kg Aov-t.

Az algoritmus végrehajtásakor a karakterlánc a következő változásokon megy keresztül:

Vettem egy kg narancsot a T M-ben.
Vettem egy kiló narancsot a T.M-ben.
Vettem egy kiló narancsot a T boltban.
Vettem egy kiló narancsot abban a boltban.
Vettem egy kiló narancsot abban a bódében.

Ezzel az algoritmus végrehajtása befejeződött (mivel az általunk véglegessé tett 5-ös képlet el fog érni).

2. példa

Ez az algoritmus a bináris számokat " egyessé " alakítja (amelyben egy N nem negatív egész szám rekordja N pálcikából álló karakterlánc). Például a 101-es bináris szám 5 pálcikává alakul: |||||.

Ábécé:

{ 0, 1, | }

Szabályok:

1 → 0|
|0 → 0||
0 → "" (üres karakterlánc)

Forrás sor:

101

Teljesítmény:

0|01
0|00|
00||0|
00|0|||
000|||||
00|||||
0|||||
|||||

Lásd még

Egyéb absztrakt implementátorok és formális számítástechnikai rendszerek

Normál algoritmusokon alapuló nyelvek

REFAL
cs

Egyéb algoritmusok

Operátori algoritmus

Linkek

Szótárak és enciklopédiák	Nagy orosz