Algorithme de Markov
From Wikipedia, the free encyclopedia
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.
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 :
- 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).
- Si une telle règle n'est pas trouvée, l'algorithme s'arrête.
- 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.
- Si la règle est terminale, l'algorithme s'arrête.
- Recommencer à la première étape.
