Normální algoritmus

Aktuální verze stránky ještě nebyla zkontrolována zkušenými přispěvateli a může se výrazně lišit od verze recenzované 10. listopadu 2021; kontroly vyžadují 2 úpravy .

Normální algoritmus (algoritmus) Markova ( NAM , také Markovův algoritmus ) je jedním ze standardních způsobů, jak formálně definovat koncept algoritmu (další známá metoda je Turingův stroj ). Koncept normálního algoritmu zavedl A. A. Markov (junior) na konci 40. let v pracích o neřešitelnosti některých problémů v teorii asociativních výpočtů. Tradiční pravopis a výslovnost slova „algori f m“ v tomto termínu pochází také od jeho autora, který řadu let vyučoval kurz matematické logiky na Fakultě mechaniky a matematiky Moskevské státní univerzity .

Normální algoritmus popisuje metodu přepisování řetězců, podobnou formálním gramatikám . NAM je Turingův úplný jazyk, díky čemuž je ekvivalentní ve vyjadřovací síle Turingovu stroji, a tedy moderním programovacím jazykům. Na bázi NAM byl vytvořen funkcionální programovací jazyk Refal .

Popis

Normální algoritmy jsou verbální, to znamená, že jsou určeny k použití na slova v různých abecedách.

Definice každého normálního algoritmu se skládá ze dvou částí: definice abecedy algoritmu (na slova, z jejichž znaků bude algoritmus aplikován) a definice jeho schématu . Schéma normálního algoritmu je konečná uspořádaná množina takzvaných substitučních vzorců , z nichž každý může být jednoduchý nebo konečný . Jednoduché substituční vzorce jsou slova ve tvaru , kde a jsou dvě libovolná slova v abecedě algoritmu (nazývaná levá a pravá strana substitučního vzorce). Podobně konečné substituční vzorce jsou slova ve tvaru , kde a jsou dvě libovolná slova v abecedě algoritmu. Předpokládá se, že pomocná písmena a nepatří do abecedy algoritmu (jinak by měla být vybrána dvě další písmena, která budou hrát roli oddělovače mezi levou a pravou částí). $L až D$ $L$ $D$ $L\do \cdot D$ $L$ $D$ $\na$ $\to \cdot$

Příkladem normálního schématu algoritmu v pětipísmenné abecedě je schéma $|*abc$

$\left\{{\begin{matrix}|b&\to &ba|\\ab&\to &ba\\b&\to &\\{*}|&\to &b*&\\{*}&\to &c&\ \|c&\to &c\\ac&\to &c|\\c&\to \cdot \end{matrix}}\vpravo.$

Proces aplikace normálního algoritmu na libovolné slovo v abecedě tohoto algoritmu je diskrétní sekvence elementárních kroků, sestávající z následujících. Nechť je slovo získané v předchozím kroku algoritmu (nebo původní slovo , pokud je aktuální krok prvním). Pokud mezi substitučními vzorci není žádný, jehož levá strana by byla zahrnuta do , pak je práce algoritmu považována za dokončenou a výsledkem této práce je slovo . Jinak mezi substitučními vzorci, jejichž levá část je obsažena v , je vybrán ten úplně první. Pokud má tento substituční vzorec tvar , pak se ze všech možných reprezentací slova ve tvaru vybere jedno, pro které je nejkratší, načež se algoritmus považuje za dokončený s výsledkem . Pokud má tento substituční vzorec tvar , pak se ze všech možných reprezentací slova ve tvaru vybere to, které je nejkratší, načež se slovo považuje za výsledek aktuálního kroku, který je předmětem dalšího zpracování v dalším krok. $PROTI$ $PROTI'$ $PROTI$ $PROTI'$ $PROTI'$ $PROTI'$ $L\do \cdot D$ $PROTI'$ $RLS$ $R$ $RDS$ $L až D$ $PROTI'$ $RLS$ $R$ $RDS$

Například v průběhu procesu aplikace algoritmu se schématem uvedeným výše se slova , , , , , , , , a objevují postupně za slovem , načež algoritmus končí s výsledkem . Další příklady naleznete níže. $|*||$ $|b*|$ $ba|*|$ $a|*|$ $a|b*$ $aba|*$ $baa|*$ $aa|*$ $aa|c$ $aac$ $ac|$ $c||$ $||$

Jakýkoli normální algoritmus je ekvivalentní nějakému Turingovu stroji a naopak jakýkoli Turingův stroj je ekvivalentní nějakému normálnímu algoritmu. Varianta Church-Turingovy teze , formulovaná ve vztahu k normálním algoritmům, se běžně nazývá „princip normalizace“.

Normální algoritmy se ukázaly jako vhodný nástroj pro konstrukci mnoha odvětví konstruktivní matematiky . Kromě toho se myšlenky, které jsou součástí definice normálního algoritmu, používají v řadě programovacích jazyků orientovaných na zpracování symbolických informací - například v jazyce Refal .

Příklady

Příklad 1

Použití Markovova algoritmu pro transformace na řetězcích.

Abeceda:

{ a ... i, A ... I, "mezera", "tečka" }

pravidla:

A → oranžová
kg na kilogram
M → obchod
T → hlasitost
obchod →. stání (konečná formule)
v tom stánku → na tom trhu

Zdrojový řádek:

Koupil jsem kg Aov v T M.

Když je algoritmus spuštěn, řetězec prochází následujícími změnami:

Koupil jsem v T M kg pomerančů.
Koupil jsem kilo pomerančů v T.M.
Koupil jsem kilo pomerančů v T shopu.
Koupil jsem v tom obchodě kilo pomerančů.
V tom stánku jsem koupil kilo pomerančů.

Tím je provádění algoritmu dokončeno (protože bude dosaženo vzorce č. 5, který jsme učinili konečným).

Příklad 2

Tento algoritmus převádí binární čísla na " single " (ve kterém záznam nezáporného celého čísla N je řetězec N tyčinek). Například binární číslo 101 se převede na 5 tyčinek: |||||.

Abeceda:

{ 0, 1, | }

pravidla:

1 → 0|
|0 → 0||
0 → "" (prázdný řetězec)

Zdrojový řádek:

101

Výkon:

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

Viz také

Další abstraktní implementátoři a formální výpočetní systémy

Jazyky založené na normálních algoritmech

REFAL
Čt

Jiné algoritmy

Algoritmus operátora

Odkazy

Slovníky a encyklopedie	Velký Rus