Markovův algoritmus - Markov algorithm

V teoretické informatiky , je Markov algoritmus je řetězec přepisování systém , který používá gramatiky like pravidla pro provoz na řetězce symbolů. Ukázalo se, že Markovovy algoritmy jsou Turingovy úplné , což znamená, že jsou vhodné jako obecný model výpočtu a mohou reprezentovat jakýkoli matematický výraz z jeho jednoduché notace. Markovovy algoritmy jsou pojmenovány po sovětském matematikovi Andrey Markovovi ml.

Refal je programovací jazyk založený na Markovových algoritmech.

Popis

Normální algoritmy jsou verbální, to znamená, že mají být použity pro řetězce v různých abecedách.

Definice libovolného normálního algoritmu se skládá ze dvou částí: definice abecedy algoritmu (algoritmus se použije na řetězce těchto abecedních symbolů) a definice jeho schématu . Schéma normálního algoritmu je konečná uspořádaná sada takzvaných substitučních vzorců , z nichž každý může být jednoduchý nebo konečný . Jednoduché substituční vzorce jsou reprezentovány řetězci formuláře , kde a jsou dva libovolné řetězce v abecedě algoritmu (nazývané levá a pravá strana substituce vzorce). Podobně jsou konečné substituční vzorce reprezentovány řetězci formuláře , kde a jsou dva libovolné řetězce v abecedě algoritmu. To předpokládá, že by měly být vybrány pomocné znaky a nepatří do abecedy algoritmu (v opačném případě by měly být vybrány dva další znaky, které plní svoji roli oddělovače levé a pravé strany, které nejsou v abecedě algoritmu). ${\ displaystyle L \ až D}$${\ displaystyle L}$${\ displaystyle D}$${\ displaystyle L \ to \ cdot D}$${\ displaystyle L}$${\ displaystyle D}$${\ displaystyle \ to}$${\ displaystyle \ to \ cdot}$

Zde je příklad normálního schématu algoritmu v pětipísmenné abecedě : ${\ displaystyle | * abc}$

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

Proces aplikace normálního algoritmu na libovolný řetězec v abecedě tohoto algoritmu je diskrétní sekvence elementárních kroků, skládající se z následujících. Předpokládejme, že toto je slovo získané v předchozím kroku algoritmu (nebo původní slovo , pokud je aktuální krok první). Pokud ze substitučních vzorců není žádná levá strana, která je zahrnuta do , pak se algoritmus ukončí a za výsledek jeho práce se považuje řetězec . Jinak je vybrán první ze substitučních vzorců, jejichž levé strany jsou zahrnuty . Pokud má substituční vzorec tvar , pak je ze všech možných reprezentací řetězce formuláře (kde a jsou libovolné řetězce) vybrán ten s nejkratší . Poté se algoritmus ukončí a výsledek jeho práce se považuje za . Pokud má však tento substituční vzorec formu , pak je vybrána ze všech možných reprezentací řetězce forma té s nejkratší , po které je řetězec považován za výsledek aktuálního kroku, předmět k dalšímu zpracování v dalším kroku. ${\ 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 \ až D}$${\ displaystyle V '}$${\ displaystyle RLS}$${\ displaystyle R}$${\ displaystyle RDS}$

Například proces aplikování algoritmu je popsáno výše, slovních výsledky v pořadí slov , , , , , , , , , a , po kterém algoritmus se zastaví s výsledkem . ${\ 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 ||}$

Další příklady viz níže.

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. Verze tezi Church-Turing formulované ve vztahu k normálnímu algoritmu se nazývá „princip normalizace“.

Normální algoritmy se ukázaly jako vhodný prostředek pro konstrukci mnoha částí konstruktivní matematiky . V definici normálního algoritmu je navíc obsažena řada myšlenek používaných v programovacích jazycích zaměřených na zacházení se symbolickými informacemi - například v Refalu .

Algoritmus

Tyto pravidla jsou sled dvojic řetězců, obvykle prezentovány ve formě vzoru → výměně . Každé pravidlo může být buď běžné, nebo ukončující.

Vzhledem k vstupnímu řetězci:

1. Zkontrolujte pravidla v pořadí shora dolů, abyste zjistili, zda lze ve vstupním řetězci najít některý ze vzorů .
2. Pokud žádný není nalezen, algoritmus se zastaví.
3. Pokud je jeden (nebo více) nalezen, použijte první z nich k nahrazení levého výskytu shodného textu ve vstupním řetězci jeho nahrazením .
4. Pokud právě použité pravidlo bylo zakončovací, algoritmus se zastaví.
5. Přejděte na krok 1.

Všimněte si, že po každé aplikaci pravidel začne hledání znovu od prvního pravidla.

Příklad

Následující příklad ukazuje základní provoz Markovova algoritmu.

Pravidla

1. „A“ -> „jablko“
2. „B“ -> „taška“
3. „S“ -> „nakupovat“
4. „T“ -> „the“
5. „obchod“ -> „můj bratr“
6. "nikdy nepoužito" -> . „pravidlo ukončení“

Řetězec symbolů

„Koupil jsem B As od T S.“

Provedení

Pokud je algoritmus použit na výše uvedený příklad, řetězec Symbol se změní následujícím způsobem.

1. „Koupil jsem B As od T S.“
2. „Koupil jsem B jablka od T S.“
3. „Koupil jsem sáček jablek od T S.“
4. „Koupil jsem sáček jablek z obchodu T.“
5. „Koupil jsem si v obchodě pytel jablek.“
6. „Koupil jsem pytel jablek od svého bratra.“

Algoritmus se poté ukončí.

Další příklad

Tato pravidla poskytují zajímavější příklad. Přepisují binární čísla na své unární protějšky. Například 101 bude přepsán na řetězec 5 po sobě jdoucích pruhů.

Pravidla

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

Řetězec symbolů

„101“

Provedení

Pokud se algoritmus použije na výše uvedený příklad, ukončí se po následujících krocích.

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

Viz také

• Thue (programovací jazyk)
• Formální gramatika

Reference

• Caracciolo di Forino, A. Řetězcové jazyky zpracování a zobecněné Markovovy algoritmy. V jazycích a technikách manipulace se symboly, DG Bobrow (Ed.), North-Holland Publ. Co., Amsterdam, Nizozemsko, 1968, s. 191–206.
• Andrey Andreevich Markov (1903-1979) 1960. Teorie algoritmů. Překlady americké matematické společnosti, série 2, 15, 1-14.

externí odkazy

• Yad Studio - Markovovy algoritmy IDE a tlumočník (Open Source)
• Markovův algoritmický tlumočník
• Markovův algoritmický tlumočník
• Markovovy algoritmické tlumočníky v Rosetta-Code