En informática teórica , un algoritmo de Markov es un sistema de reescritura de cadenas que utiliza reglas similares a la gramática para operar sobre cadenas de símbolos. Se ha demostrado que los algoritmos de Markov son Turing completos , 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, destinados a ser aplicados a cadenas en diferentes alfabetos.
La definición de cualquier algoritmo normal consta de dos partes: la definición del alfabeto del algoritmo (el algoritmo se aplicará a las cadenas de estos símbolos alfabéticos) y la definición de su esquema . El esquema de un algoritmo normal es un conjunto finito ordenado de las llamadas fórmulas de sustitución , cada una de las cuales puede ser simple o final . Las fórmulas de sustitución simples están representadas por cadenas de la forma, dónde y son dos cadenas arbitrarias en el alfabeto del algoritmo (llamadas, respectivamente, los lados izquierdo y derecho de la sustitución de la fórmula). De manera similar, las fórmulas de sustitución final se representan mediante cadenas de la forma, dónde y son dos cadenas arbitrarias en el alfabeto del algoritmo. Esto supone que los caracteres auxiliares y no pertenecen al alfabeto del algoritmo (de lo contrario, se deben seleccionar otros dos caracteres para realizar su función como divisores de los lados izquierdo y derecho, que no están en el alfabeto del algoritmo).
Aquí hay un ejemplo de un esquema de algoritmo normal en el alfabeto de cinco letras :
El proceso de aplicar el algoritmo normal a una cadena arbitraria. en el alfabeto de este algoritmo hay 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 de las fórmulas de sustitución no hay un lado izquierdo que esté incluido en el, entonces el algoritmo termina y el resultado de su trabajo se considera la cadena . De lo contrario, la primera de las fórmulas de sustitución cuyos lados izquierdos se incluyen enestá seleccionado. Si la fórmula de sustitución tiene la forma, luego de todas las posibles representaciones de la cadena de la forma (dónde y son cadenas arbitrarias) el que tiene el más corto esta elegido. Entonces el algoritmo termina y el resultado de su trabajo se considera. Sin embargo, si esta fórmula de sustitución tiene la forma, luego de todas las posibles representaciones de la cadena de la forma de el que tiene el mas corto se elige, después de lo cual la cuerda se considera el resultado del paso actual, sujeto a procesamiento adicional en el paso siguiente.
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 .
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, inherente a la definición de un algoritmo normal hay una serie de ideas utilizadas en lenguajes de programación destinados a manejar 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 puede ser ordinaria o terminante.
Dada una cadena de entrada :
- Verifique las Reglas en orden de arriba hacia abajo para ver si se puede encontrar alguno de los patrones en la cadena de entrada .
- Si no se encuentra ninguno, el algoritmo se detiene.
- Si se encuentra uno (o más), utilice 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 .
- Si la regla que se acaba de aplicar era de terminación, el algoritmo se detiene.
- 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.
Reglas
- "A" -> "manzana"
- "B" -> "bolsa"
- "S" -> "tienda"
- "T" -> "el"
- "la tienda" -> "mi hermano"
- "nunca usado" -> . "regla de terminación"
Cadena de símbolo
"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.
- "Compré una B de As de T S."
- "Compré una B de manzanas de T S."
- "Compré una bolsa de manzanas de T S."
- "Compré una bolsa de manzanas en la tienda T".
- "Compré una bolsa de manzanas en la tienda".
- "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.
Reglas
- "| 0" -> "0 ||"
- "1" -> "0 |"
- "0" -> ""
Cadena de símbolo
"101"
Ejecución
Si el algoritmo se aplica al ejemplo anterior, terminará después de los siguientes pasos.
- "101"
- "0 | 01"
- "00 || 1"
- "00 || 0 |"
- "00 | 0 |||"
- "000 |||||"
- "00 |||||"
- "0 |||||"
- "|||||"
Ver también
Referencias
- Caracciolo di Forino, A. Lenguajes de procesamiento de cadenas y algoritmos de Markov generalizados. En Lenguajes y técnicas de manipulación de símbolos, DG Bobrow (Ed.), North-Holland Publ. 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 American Mathematical Society, series 2, 15, 1-14.
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