Algorithme de Markov - Markov algorithm

En informatique théorique , un algorithme de Markov est un système de réécriture de chaînes qui utilise des règles de type grammaire pour opérer sur des chaînes de symboles. Les algorithmes de Markov se sont avérés être complets de Turing , ce qui signifie qu'ils conviennent comme modèle général de calcul et peuvent représenter n'importe quelle expression mathématique à partir de sa notation simple. Les algorithmes de Markov portent le nom du mathématicien soviétique Andrey Markov, Jr.

Refal est un langage de programmation basé sur des algorithmes de Markov.

Description

Les algorithmes normaux sont verbaux, c'est-à-dire destinés à être appliqués à des chaînes de différents alphabets.

La définition de tout algorithme normal se compose de deux parties: la définition de l' alphabet de l'algorithme (l'algorithme sera appliqué aux chaînes de ces symboles alphabétiques), et la définition de son schéma . Le schéma d'un algorithme normal est un ensemble ordonné fini de formules dites de substitution , chacune pouvant être simple ou finale . Les formules de substitution simples sont représentées par des chaînes de la forme , où et sont deux chaînes arbitraires dans l'alphabet de l'algorithme (appelées respectivement les côtés gauche et droit de la substitution de formule). De même, les formules de substitution finales sont représentées par des chaînes de la forme , où et sont deux chaînes arbitraires dans l'alphabet de l'algorithme. Cela suppose que les caractères auxiliaires et n'appartiennent pas à l'alphabet de l'algorithme (sinon deux autres caractères pour remplir leur rôle de diviseurs des côtés gauche et droit, qui ne sont pas dans l'alphabet de l'algorithme, doivent être sélectionnés). ${\ displaystyle L \ à D}$${\ displaystyle L}$${\ displaystyle D}$${\ displaystyle L \ à \ cdot D}$${\ displaystyle L}$${\ displaystyle D}$${\ displaystyle \ to}$${\ displaystyle \ à \ cdot}$

Voici un exemple de schéma d'algorithme normal dans l'alphabet à cinq lettres : ${\ displaystyle | * abc}$

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

Le processus d'application de l'algorithme normal à une chaîne arbitraire dans l'alphabet de cet algorithme est une séquence discrète d'étapes élémentaires, comprenant les éléments suivants. Supposons que ce soit le mot obtenu à l'étape précédente de l'algorithme (ou le mot d'origine , si l'étape courante est la première). Si parmi les formules de substitution il n'y a pas de côté gauche inclus dans , alors l'algorithme se termine et le résultat de son travail est considéré comme la chaîne . Sinon, la première des formules de substitution dont les côtés gauches sont inclus est sélectionnée. Si la formule de substitution est de la forme , alors parmi toutes les représentations possibles de la chaîne de la forme (où et sont des chaînes arbitraires), celle avec la plus courte est choisie. Ensuite, l'algorithme se termine et le résultat de son travail est considéré comme étant . Cependant, si cette formule de substitution est de la forme , alors parmi toutes les représentations possibles de la chaîne, la forme de celle avec la plus courte est choisie, après quoi la chaîne est considérée comme le résultat de l'étape en cours, sujet pour un traitement ultérieur à l'étape suivante. ${\ displaystyle V}$${\ displaystyle V '}$${\ displaystyle V}$${\ displaystyle V '}$${\ displaystyle V '}$${\ displaystyle V '}$${\ displaystyle L \ à \ cdot D}$${\ displaystyle V '}$${\ displaystyle RLS}$${\ displaystyle R}$${\ displaystyle S}$${\ displaystyle R}$${\ displaystyle RDS}$${\ displaystyle L \ à D}$${\ displaystyle V '}$${\ displaystyle RLS}$${\ displaystyle R}$${\ displaystyle RDS}$

Par exemple, le procédé d'application de l'algorithme décrit ci - dessus pour les mots des résultats dans la séquence de mots , , , , , , , , , et , après quoi l'algorithme arrête le résultat . ${\ 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 ||}$

Pour d'autres exemples, voir ci-dessous.

Tout algorithme normal est équivalent à une machine de Turing , et vice versa - toute machine de Turing est équivalente à un algorithme normal. Une version de la thèse de Church-Turing formulée en relation avec l'algorithme normal est appelée le «principe de normalisation».

Les algorithmes normaux se sont avérés être un moyen pratique pour la construction de nombreuses sections de mathématiques constructives . De plus, la définition d'un algorithme normal comprend un certain nombre d'idées utilisées dans les langages de programmation visant à gérer des informations symboliques - par exemple, dans Refal .

Algorithme

Les règles sont une séquence de paires de chaînes, généralement présentées sous forme de motif → remplacement . Chaque règle peut être ordinaire ou terminale.

Étant donné une chaîne d' entrée :

1. Vérifiez les règles dans l'ordre de haut en bas pour voir si l'un des modèles peut être trouvé dans la chaîne d' entrée .
2. Si aucun n'est trouvé, l'algorithme s'arrête.
3. Si un (ou plusieurs) est trouvé, utilisez le premier d'entre eux pour remplacer l'occurrence la plus à gauche du texte correspondant dans la chaîne d' entrée par son remplacement .
4. Si la règle qui vient d'être appliquée était terminale, l'algorithme s'arrête.
5. Passez à l'étape 1.

Notez qu'après chaque application de règle, la recherche recommence à partir de la première règle.

Exemple

L'exemple suivant montre le fonctionnement de base d'un algorithme de Markov.

Des règles

1. "A" -> "pomme"
2. "B" -> "sac"
3. "S" -> "boutique"
4. "T" -> "le"
5. "la boutique" -> "mon frère"
6. "un jamais utilisé" -> . "règle de fin"

Chaîne de symboles

"J'ai acheté un B d'As à T S."

Exécution

Si l'algorithme est appliqué à l'exemple ci-dessus, la chaîne Symbol changera de la manière suivante.

1. "J'ai acheté un B d'As à T S."
2. "J'ai acheté un B de pommes à T S."
3. "J'ai acheté un sac de pommes à T S."
4. "J'ai acheté un sac de pommes au magasin T."
5. "J'ai acheté un sac de pommes à la boutique."
6. "J'ai acheté un sac de pommes à mon frère."

L'algorithme se terminera alors.

Un autre exemple

Ces règles donnent un exemple plus intéressant. Ils réécrivent les nombres binaires en leurs homologues unaires. Par exemple, 101 sera réécrit en une chaîne de 5 mesures consécutives.

Des règles

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

Chaîne de symboles

«101»

Exécution

Si l'algorithme est appliqué à l'exemple ci-dessus, il se terminera après les étapes suivantes.

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

Voir également

• Thue (langage de programmation)
• Grammaire formelle

Les références

• Caracciolo di Forino, A. Langages de traitement de chaînes et algorithmes de Markov généralisés. Dans Langages et techniques de manipulation de symboles, DG Bobrow (Ed.), North-Holland Publ. Co., Amsterdam, Pays-Bas, 1968, pp. 191–206.
• Andrey Andreevich Markov (1903-1979) 1960. La théorie des algorithmes. Traductions de l'American Mathematical Society, séries 2, 15, 1-14.

Liens externes

• Yad Studio - IDE et interpréteur d'algorithmes de Markov (Open Source)
• Interpréteur d'algorithme de Markov
• Interpréteur d'algorithme de Markov
• Interprètes d'algorithmes de Markov chez Rosetta-Code