algoritmo de markov

En informática teórica , un algoritmo de Markov es un sistema de reescritura de cadenas que utiliza reglas similares a gramaticales para operar con cadenas de símbolos. Se ha demostrado que los algoritmos de Markov son completos de Turing , lo que significa que son adecuados como modelo general de cálculo y pueden representar cualquier expresión matemática a partir de su notación simple. Los algoritmos de Markov llevan el nombre del matemático soviético Andrey Markov, Jr.

Refal es un lenguaje de programación basado en algoritmos de Markov.

Descripción

Los algoritmos normales son verbales, es decir, están destinados a ser aplicados a cadenas en diferentes alfabetos.

La definición de cualquier algoritmo normal consta de dos partes: un alfabeto , que es un conjunto de símbolos, y un esquema . El algoritmo se aplica a cadenas de símbolos del alfabeto. El esquema es un conjunto finito y ordenado de fórmulas de sustitución . Cada fórmula puede ser simple o definitiva . Las fórmulas de sustitución simples están representadas por cadenas de la forma , donde y son dos cadenas arbitrarias en el alfabeto. De manera similar, las fórmulas de sustitución finales están representadas por cadenas de la forma . ${\displaystyle L\to D}$ ${\displaystyle L}$ ${\displaystyle D}$ ${\displaystyle L\to \cdot D}$

A continuación se muestra un ejemplo de un esquema de algoritmo normal en el alfabeto de cinco letras : ${\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.}$

El proceso de aplicar el algoritmo normal a una cadena arbitraria en el alfabeto de este algoritmo es una secuencia discreta de pasos elementales, que consta de lo siguiente. Supongamos que es la palabra obtenida en el paso anterior del algoritmo (o la palabra original , si el paso actual es el primero). Si en las fórmulas de sustitución no hay ningún lado izquierdo incluido en , entonces el algoritmo termina y el resultado de su trabajo se considera la cadena . En caso contrario, se selecciona la primera de las fórmulas de sustitución cuyos lados izquierdos están incluidos . Si la fórmula de sustitución es de la forma , entonces de todas las representaciones posibles de la cadena de la forma (donde y son cadenas arbitrarias) se elige la que tiene la más corta . Entonces el algoritmo termina y se considera que el resultado de su trabajo es . Sin embargo, si esta fórmula de sustitución tiene la forma , entonces, de todas las representaciones posibles de la cadena , se elige la forma más corta , después de lo cual la cadena se considera el resultado del paso actual, sujeto para su posterior procesamiento en el siguiente paso. ${\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}$

Por ejemplo, el proceso de aplicar el algoritmo descrito anteriormente a la palabra da como resultado la secuencia de palabras , , , , , , , y , después de lo cual el algoritmo se detiene con el resultado . ${\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 ||}$

Para ver otros ejemplos, consulte a continuación.

Cualquier algoritmo normal es equivalente a alguna máquina de Turing , y viceversa: cualquier máquina de Turing es equivalente a algún algoritmo normal. Una versión de la tesis de Church-Turing formulada en relación con el algoritmo normal se denomina "principio de normalización".

Los algoritmos normales han demostrado ser un medio conveniente para la construcción de muchas secciones de la matemática constructiva . Además, en la definición de un algoritmo normal hay una serie de ideas utilizadas en los lenguajes de programación destinados a procesar información simbólica, por ejemplo en Refal .

Algoritmo

Las Reglas son una secuencia de pares de cadenas, generalmente presentadas en forma de patrón → reemplazo . Cada regla podrá ser ordinaria o extintiva.

Dada una cadena de entrada :

1. Verifique las Reglas en orden de arriba a abajo para ver si alguno de los patrones se puede encontrar en la cadena de entrada .
2. Si no se encuentra ninguno, el algoritmo se detiene.
3. Si se encuentra uno (o más), use el primero de ellos para reemplazar la aparición más a la izquierda del texto coincidente en la cadena de entrada con su reemplazo .
4. Si la regla que se acaba de aplicar era terminante, el algoritmo se detiene.
5. Vaya al paso 1.

Tenga en cuenta que después de cada aplicación de regla, la búsqueda comienza desde la primera regla.

Ejemplo

El siguiente ejemplo muestra el funcionamiento básico de un algoritmo de Markov.

Normas

1. "A" -> "manzana"
2. "B" -> "bolsa"
3. "S" -> "tienda"
4. "T" -> "el"
5. "la tienda" -> "mi hermano"
6. "nunca usado" -> . "regla de terminación"

Cadena de símbolos

"Compré una B de As de T S."

Ejecución

Si el algoritmo se aplica al ejemplo anterior, la cadena de símbolo cambiará de la siguiente manera.

1. "Compré una B de As de T S."
2. "Compré una B de manzanas de T S."
3. "Le compré una bolsa de manzanas a T S."
4. "Compré una bolsa de manzanas en la tienda T".
5. "Compré una bolsa de manzanas en la tienda".
6. "Le compré una bolsa de manzanas a mi hermano".

Entonces el algoritmo terminará.

Otro ejemplo

Estas reglas dan un ejemplo más interesante. Reescriben números binarios en sus contrapartes unarias. Por ejemplo, 101 se reescribirá en una cadena de 5 compases consecutivos.

Normas

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

Cadena de símbolos

"101"

Ejecución

Si el algoritmo se aplica al ejemplo anterior, finalizará después de los siguientes pasos.

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

Ver también

• Gramática formal

Referencias

• Caracciolo di Forino, A. Lenguajes de procesamiento de cadenas y algoritmos generalizados de Markov. En Lenguajes y técnicas de manipulación de símbolos, DG Bobrow (Ed.), Publ. de Holanda Septentrional. Co., Amsterdam, Países Bajos, 1968, págs. 191-206.
• Andrey Andreevich Markov (1903-1979) 1960. La teoría de los algoritmos. Traducciones de la Sociedad Estadounidense de Matemáticas, serie 2, 15, 1-14. (Traducción del ruso, Trudy Instituta im. Steklova 38 (1951) 176-189 ^[1] )

1. Kushner, Boris A. (28 de mayo de 1999). "El análisis constructivo de Markov; la visión de un participante". Informática Teórica . 219 (1–2): 268, 284. doi : 10.1016/S0304-3975(98)00291-6 .

enlaces externos

• Yad Studio - IDE e intérprete de algoritmos de Markov (código abierto)
• Intérprete del algoritmo de Markov
• Intérprete del algoritmo de Markov
• Intérpretes del algoritmo de Markov en Rosetta-Code