Algoritmul Markov - Markov algorithm

În informatică teoretică , un algoritm Markov este un sistem de rescriere a șirurilor care folosește reguli de tip gramatică pentru a opera pe șiruri de simboluri. Algoritmii Markov s-au dovedit a fi Turing-complet , ceea ce înseamnă că sunt potriviți ca model general de calcul și pot reprezenta orice expresie matematică din notația sa simplă. Algoritmii Markov poartă numele matematicianului sovietic Andrey Markov, Jr.

Refal este un limbaj de programare bazat pe algoritmi Markov.

Descriere

Algoritmii normali sunt verbali, adică intenționați să fie aplicați șirurilor din diferite alfabete.

Definiția oricărui algoritm normal constă din două părți: definiția alfabetului algoritmului (algoritmul va fi aplicat șirurilor acestor simboluri alfabetice) și definiția schemei sale . 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 reprezentate de șiruri de formă , unde și sunt două șiruri arbitrare din alfabetul algoritmului (numite, respectiv, laturile stânga și dreapta substituției formulei). În mod similar, formulele de substituție finală sunt reprezentate de șiruri de formă , unde și sunt două șiruri arbitrare din alfabetul algoritmului. Aceasta presupune că caracterele auxiliare și nu aparțin alfabetului algoritmului (în caz contrar, ar trebui selectate alte două caractere pentru a-și îndeplini rolul de separatoare ale laturilor stânga și dreaptă, care nu se află în alfabetul algoritmului). ${\ displaystyle L \ to D}$${\ displaystyle L}$${\ displaystyle D}$${\ displaystyle L \ to \ cdot D}$${\ displaystyle L}$${\ displaystyle D}$${\ displaystyle \ to}$${\ displaystyle \ to \ cdot}$

Iată un exemplu de schemă algoritmică normală în alfabetul cu cinci litere : ${\ displaystyle | * abc}$

${\ displaystyle \ 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}} \ right.}$

Procesul de aplicare a algoritmului normal la un șir arbitrar din alfabetul acestui algoritm este o secvență discretă de pași elementari, constând din următoarele. Să presupunem că acesta este cuvântul obținut în pasul anterior al algoritmului (sau cuvântul original , dacă pasul curent este primul). Dacă dintre formulele de substituție nu există nicio parte din stânga care este inclusă în , atunci algoritmul se termină, iar rezultatul muncii sale este considerat a fi șirul . În caz contrar, este selectată prima dintre formulele de substituție ale căror laturi stângi sunt incluse . Dacă formula de substituție este de formă , atunci din toate reprezentările posibile ale șirului formei (unde și sunt șiruri arbitrare) se alege cea cu cea mai scurtă . Apoi algoritmul se termină și rezultatul muncii sale este considerat a fi . Cu toate acestea, dacă această formulă de substituție este de formă , atunci din toate reprezentările posibile ale șirului formei celui cu cea mai scurtă , după care șirul este considerat a fi rezultatul pasului curent, subiect la procesarea ulterioară în pasul următor. ${\ displaystyle V}$${\ displaystyle V '}$${\ displaystyle V}$${\ displaystyle V '}$${\ displaystyle V '}$${\ displaystyle V '}$${\ displaystyle L \ to \ cdot D}$${\ displaystyle V '}$${\ displaystyle RLS}$${\ displaystyle R}$${\ displaystyle S}$${\ displaystyle R}$${\ displaystyle RDS}$${\ displaystyle L \ to D}$${\ displaystyle V '}$${\ displaystyle RLS}$${\ displaystyle R}$${\ displaystyle RDS}$

De exemplu, procesul de aplicare a algoritmului descris mai sus la cuvântul rezultate din secvența de cuvinte , , , , , , , , , și , după care algoritmul se oprește cu rezultatul . ${\ displaystyle | * ||}$${\ displaystyle | b * |}$${\ displaystyle ba | * |}$${\ displaystyle a | * |}$${\ displaystyle a | b *}$${\ displaystyle aba | *}$${\ displaystyle baa | *}$${\ displaystyle aa | *}$${\ displaystyle aa | c}$${\ displaystyle aac}$${\ displaystyle ac |}$${\ displaystyle c ||}$${\ displaystyle ||}$

Pentru alte exemple, a se vedea mai jos.

Orice algoritm normal este echivalent cu o anumită mașină Turing și viceversa - orice mașină Turing este echivalentă cu un anumit algoritm normal. O versiune a tezei Church-Turing formulată în raport cu algoritmul normal este numită „principiul normalizării”.

Algoritmii normali s-au dovedit a fi un mijloc convenabil pentru construirea multor secțiuni ale matematicii constructive . Mai mult, inerent definiției unui algoritm normal sunt o serie de idei utilizate în limbaje de programare care vizează gestionarea informațiilor simbolice - de exemplu, în Refal .

Algoritm

De Regulile sunt o succesiune de perechi de șiruri, de obicei , prezentate sub formă de model → înlocuire . Fiecare regulă poate fi fie obișnuită, fie finală.

Având un șir de intrare :

1. Verificați regulile în ordine de sus în jos pentru a vedea dacă oricare dintre modele poate fi găsit în șirul de intrare .
2. Dacă nu se găsește niciunul, algoritmul se oprește.
3. Dacă se găsește unul (sau mai multe), utilizați primul dintre ele pentru a înlocui cea mai stângă apariție a textului potrivit din șirul de intrare cu înlocuirea acestuia .
4. Dacă regula aplicată tocmai a fost una care se termină, algoritmul se oprește.
5. Mergeți la pasul 1.

Rețineți că după fiecare cerere de regulă, căutarea începe de la prima regulă.

Exemplu

Următorul exemplu prezintă funcționarea de bază a unui algoritm Markov.

Reguli

1. „A” -> „măr”
2. „B” -> „geantă”
3. „S” -> „magazin”
4. „T” -> „cel”
5. "magazinul" -> "fratele meu"
6. "a never used" -> . „regulă de încheiere”

Șir de simboluri

"Am cumpărat un B de As de la T S."

Execuţie

Dacă algoritmul este aplicat exemplului de mai sus, șirul de simboluri se va modifica în modul următor.

1. "Am cumpărat un B de As de la T S."
2. „Am cumpărat un B de mere de la T S.”
3. „Am cumpărat o pungă de mere de la T S.”
4. „Am cumpărat o pungă cu mere de la magazinul T.”
5. „Am cumpărat o pungă cu mere de la magazin”.
6. „Am cumpărat o pungă de mere de la fratele meu”.

Algoritmul se va termina apoi.

Alt exemplu

Aceste reguli oferă un exemplu mai interesant. Ei rescriu numere binare omologilor lor unari. De exemplu, 101 va fi rescris într-un șir de 5 bare consecutive.

Reguli

1. "| 0" -> "0 ||"
2. "1" -> "0 |"
3. "0" -> ""

Șir de simboluri

„101”

Execuţie

Dacă algoritmul este aplicat exemplului de mai sus, acesta se va termina după pașii următori.

1. „101”
2. "0 | 01"
3. "00 || 1"
4. "00 || 0 |"
5. "00 | 0 |||"
6. "000 |||||"
7. "00 |||||"
8. „0 |||||”
9. "|||||"

Vezi si

• Luni (limbaj de programare)
• Gramatica formală

Referințe

• Caracciolo di Forino, A. Limbaje de procesare a șirurilor și algoritmi Markov generalizați. În limbaje și tehnici de manipulare a simbolurilor, DG Bobrow (Ed.), North-Holland Publ. Co., Amsterdam, Olanda, 1968, pp. 191–206.
• Andrey Andreevich Markov (1903-1979) 1960. Teoria algoritmilor. American Mathematical Society Translations, seria 2, 15, 1-14.

linkuri externe

• Yad Studio - IDE algoritmi Markov și interpret (Open Source)
• Interpretul algoritmului Markov
• Interpretul algoritmului Markov
• Interpretori de algoritmi Markov la Rosetta-Code