📑 Table of Contents▼

En informatique théorique, un algorithme de Markov est un système de réécriture de chaîne qui utilise des règles de grammaire pour agir sur une chaîne de symboles. Il a été démontré que les algorithmes de Markov étaient Turing-complets, ce qui signifie qu'ils constituent un modèle de calcul suffisamment général. Les algorithmes de Markov ont été nommées d'après le mathématicien Andreï Markov.

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

Algorithme

modifier

Les règles sont une suite de couples de chaînes, habituellement présentées sous la forme schéma → remplacement. Certaines règles peuvent en outre être qualifiées de terminales.

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

  1. Vérifier les règles dans l'ordre, du haut vers le bas, jusqu'à en trouver une dont le schéma peut être trouvé dans la chaîne d'entrée (ainsi, si plusieurs schémas conviennent, seule la première règle rencontrée sera prise en compte).
  2. Si une telle règle n'est pas trouvée, l'algorithme s'arrête.
  3. Sinon, l'occurrence la plus à gauche du schéma dans la chaîne d'entrée est remplacée par la chaîne de remplacement donnée par la règle.
  4. Si la règle est terminale, l'algorithme s'arrête.
  5. Recommencer à la première étape.

Exemple

modifier

Les règles suivantes réécrivent un nombre binaire en version unaire ; par exemple, 101 sera réécrit comme une chaîne de 5 barres consécutives.

Règles

modifier
  1. "|0" → "0||"
  2. "1" → "0|"
  3. "0" → ""

Chaîne d'entrée

modifier

"101"

Exécution

modifier

L'application de l'algorithme donne successivement les chaînes :

  1. "0|01"
  2. "00||1"
  3. "00||0|"
  4. "00|0|||"
  5. "000|||||"
  6. "00|||||"
  7. "0|||||"
  8. "|||||"

Références

modifier
  • Caracciolo di Forino, A. String processing languages and generalized Markov algorithms. In Symbol manipulation languages and techniques, D. G. Bobrow (Ed.), North-Holland Publ. Co., Amsterdam, The Netherlands, 1968, pp. 191–206.
  • Andreï Markov 1960. The Theory of Algorithms. American Mathematical Society Translations, series 2, 15, 1-14.

Liens externes

modifier


📚 Artikel Terkait di Wikipedia

Chaîne de Markov

Processus de Markov Propriété de Markov Couverture de Markov Martingale Équation maîtresse Bruno Sericola : Chaînes de Markov - Théorie, algorithmes et applications

Méthode de Monte-Carlo par chaînes de Markov

aléatoires sur les chaînes de Markov (algorithme de Metropolis-Hastings, échantillonnage de Gibbs), alors que d'autres algorithmes, plus complexes, introduisent

Modèle de Markov caché

de Markov caché Un modèle de Markov caché (MMC, terme et définition normalisés par l’ISO/CÉI [ISO/IEC 2382-29:1999]) —en anglais : hidden Markov model

Algorithme de Metropolis-Hastings

{\displaystyle \pi } sur un univers Ω {\displaystyle \Omega } , cet algorithme définit une chaîne de Markov dont la distribution stationnaire est π {\displaystyle

Processus de Markov

En mathématiques, un processus de Markov est un processus stochastique possédant la propriété de Markov. Dans un tel processus, la prédiction du futur

Algorithme de Viterbi

plus générale, l'algorithme de Viterbi est utilisé dans les cas où le processus sous-jacent est modélisable comme une chaîne de Markov discrète à états

Modélisation de Markov dynamique

Les algorithmes de modélisation de Markov dynamique ou de compression de Markov dynamique (ou DMC pour Dynamic Markov compression) constituent une famille

Processus de décision markovien

théorie des probabilités, un processus de décision markovien (en anglais Markov decision process, MDP) est un modèle stochastique où un agent prend des