Algoritm normal

Versiunea actuală a paginii nu a fost încă examinată de colaboratori experimentați și poate diferi semnificativ de versiunea revizuită pe 10 noiembrie 2021; verificările necesită 2 modificări .

Un algoritm (algoritm) normal al lui Markov ( NAM , de asemenea un algoritm Markov ) este una dintre modalitățile standard de a defini formal conceptul de algoritm (o altă metodă binecunoscută este o mașină Turing ). Conceptul de algoritm normal a fost introdus de A. A. Markov (junior) la sfârşitul anilor 1940 în lucrările despre imposibilitatea unor probleme din teoria calculelor asociative. Ortografia și pronunția tradițională a cuvântului "algori f m" în acest termen se întorc și la autorul său, care timp de mulți ani a predat un curs de logică matematică la Facultatea de Mecanică și Matematică a Universității de Stat din Moscova .

Algoritmul normal descrie o metodă de rescriere a șirurilor, similară cu gramaticile formale . NAM este un limbaj Turing complet , ceea ce îl face echivalent ca putere expresivă cu o mașină Turing și, prin urmare, cu limbaje de programare moderne. Limbajul de programare funcțional Refal a fost creat pe baza NAM .

Descriere

Algoritmii normali sunt verbali, adică sunt destinati să fie aplicați cuvintelor din diferite alfabete.

Definiția oricărui algoritm normal constă din două părți: definiția alfabetului algoritmului (la cuvintele din ale căror caractere va fi aplicat algoritmul) și definirea schemei acestuia . Schema unui algoritm normal este un set finit ordonat de așa-numitele formule de substituție , fiecare dintre acestea putând fi simplă sau finală . Formulele simple de substituție sunt cuvinte de forma , unde și sunt două cuvinte arbitrare din alfabetul algoritmului (numite, respectiv, părțile din stânga și din dreapta formulei de substituție). În mod similar, formulele de substituție finale sunt cuvinte de forma , unde și sunt două cuvinte arbitrare din alfabetul algoritmului. Se presupune că literele auxiliare și nu aparțin alfabetului algoritmului (în caz contrar, alte două litere ar trebui alese pentru a juca rolul de separator între părțile din stânga și din dreapta). $L la D$ $L$ $D$ $L\la \cdot D$ $L$ $D$ $\la$ $\la \cdot$

Un exemplu de schemă normală de algoritm într-un alfabet de cinci litere este schema $|*abc$

$\left\{{\begin{matrix}|b&\la &ba|\\ab&\la &ba\\b&\la &\\{*}|&\la &b*&\\{*}&\la &c&\ \|c&\la &c\\ac&\la &c|\\c&\la \cdot \end{matrice}}\dreapta.$

Procesul de aplicare a algoritmului normal unui cuvânt arbitrar din alfabetul acestui algoritm este o succesiune discretă de pași elementari, constând din următoarele. Fie cuvântul obținut la pasul anterior al algoritmului (sau cuvântul original dacă pasul curent este primul). Dacă printre formulele de substituție nu există nimeni a cărui parte stângă ar fi inclusă în , atunci munca algoritmului este considerată finalizată, iar rezultatul acestei lucrări este cuvântul . În caz contrar, dintre formulele de substituție, a căror parte din stânga este inclusă în , este selectată chiar prima. Dacă această formulă de substituție are forma , atunci dintre toate reprezentările posibile ale cuvântului în forma , se alege una pentru care este cea mai scurtă, după care algoritmul este considerat finalizat cu rezultatul . Dacă această formulă de substituție are forma , atunci din toate reprezentările posibile ale cuvântului în forma , se selectează cea pentru care este cea mai scurtă, după care cuvântul este considerat rezultatul pasului curent, supus prelucrării ulterioare la următorul Etapa. $V$ $V'$ $V$ $V'$ $V'$ $V'$ $L\la \cdot D$ $V'$ $RLS$ $R$ $RDS$ $L la D$ $V'$ $RLS$ $R$ $RDS$

De exemplu, în cursul procesului de aplicare a algoritmului cu schema indicată mai sus , cuvintele , , , , , , , , , și apar secvențial cuvântului , după care algoritmul se termină cu rezultatul . Vedeți mai multe exemple mai jos. $|*||$ $|b*|$ $ba|*|$ $a|*|$ $a|b*$ $aba|*$ $baa|*$ $aa|*$ $aa|c$ $aac$ $ac|$ $c||$ $||$

Orice algoritm normal este echivalent cu o mașină Turing și invers, orice mașină Turing este echivalentă cu un algoritm normal. O variantă a tezei Church-Turing , formulată în raport cu algoritmii normali, este denumită în mod obișnuit „principiul normalizării”.

Algoritmii normali s-au dovedit a fi un instrument convenabil pentru construirea multor ramuri ale matematicii constructive . În plus, ideile inerente definiției algoritmului normal sunt utilizate într-o serie de limbaje de programare orientate către procesarea informațiilor simbolice - de exemplu, în limbajul Refal .

Exemple

Exemplul 1

Utilizarea algoritmului Markov pentru transformări pe șiruri.

Alfabet:

{ a ... i, A ... I, „spațiu”, „punct” }

Reguli:

A → portocaliu
kg în kilogram
M → magazin
T → volum
magazin →. blocaj (formula finală)
în taraba aceea → în piața respectivă

Linia sursă:

Am cumpărat kg Aov în T M.

Când algoritmul este executat, șirul suferă următoarele modificări:

Am cumparat un kg de portocale de la T M.
Am cumpărat un kilogram de portocale de la T.M.
Am cumpărat un kilogram de portocale de la magazinul T.
Am cumpărat un kilogram de portocale de la acel magazin.
Am cumpărat un kilogram de portocale de la tarabă.

Se completează astfel execuția algoritmului (întrucât se va ajunge la formula nr. 5, pe care am făcut-o definitivă).

Exemplul 2

Acest algoritm convertește numerele binare în „ singure ” (în care înregistrarea unui număr întreg nenegativ N este un șir de N stick-uri). De exemplu, numărul binar 101 este convertit în 5 bastoane: |||||.

Alfabet:

{ 0, 1, | }

Reguli:

1 → 0|
|0 → 0||
0 → "" (șir gol)

Linia sursă:

101

Performanţă:

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

Vezi și

Alți implementatori abstracti și sisteme de calcul formale

Limbi bazate pe algoritmi normali

REFAL
Thue

Alți algoritmi

Algoritmul operatorului

Link -uri

Dicționare și enciclopedii	Rusă mare