notation - the - Art of Computer notación de programación pregunta
monsters inc art of the title (5)
No estoy 100% seguro, pero parece que Q es el conjunto de todos los pares ordenados (s, j) para 0 <= J <= N. Este será tu dominio. Es el conjunto de todos los estados posibles dados algunos N y cadena s.
Yo soy tu subconjunto de Q donde todos los pares ordenados contienen J = 0, o tus estados iniciales. Omega es su subconjunto de Q donde todos los pares ordenados contienen J = N, o sus estados finales.
f es la función real sobre el dominio Q.
EDITAR
Piense en la definición de la función como algo similar a una función, pero diferentes casos dependiendo de la entrada dada. Piensa en una función que escribirías en un idioma. ex:
tuple f(string s, int i)
{
if (Tj not in s)
(s, aj)
else if ( p is shortest possible length such that s = pYjw)
(pYjw,bj)
else if ( i == N )
(s, N)
}
Otro ejemplo es la definición de la función de Fibonacci . ¿Ves cómo se define eso? ¿Tener sentido?
Estoy empezando a leer el volumen 1 de TAOCP y tengo problemas para entender el estilo.
Knuth menciona un método computacional para ser cuádruple (Q, I, Omega, f), pero me cuesta entender qué pretende ser cada uno de estos. Entiendo su primer ejemplo, pero no entiendo su segundo
Estoy mirando la página 8 de la tercera edición.
Cerca del final del capítulo hay un algoritmo que habla de conjuntos de cadenas.
(He reemplazado las variables griegas por otras más fáciles de escribir, lo siento)
Deje A ser un conjunto finito de letras, y deje que A * sea el conjunto de todas las cadenas en A. La idea es codificar los estados del cálculo para que estén representados por cadenas de A *
Q = (s,j) where s is in A* and j is an integer, 0 <= j <= N
I = subset of Q with j = 0
Omega = subset with j = N
f = function below
(tenga en cuenta que p & w son cadenas) If y s son cadenas en A *, decimos que T ocurre en s si s tiene la forma pTw para las cadenas p y w.
f(s,j) = (s,aj) if Tj does not occur in s; f(s,j) = (pYjw,bj) if p is the shortest possible string for which s = pYjw f(s,N) = (s,N)
Entiendo el concepto de hacer conjuntos de cadenas, pero no entiendo todo lo que está tratando de decir aquí. ¿Por qué necesito Q, I, Omega? ¿Qué es lo que realmente me está explicando (¿por qué necesito 3 funciones en f?)?
¿Alguien puede ayudar a arrojar algo de luz?
Q = conjunto de estados (de modo que (s, j) representa estado s en el tiempo j )
I = estados iniciales (de ahí el requisito de que j == 0 )
Omega = estados finales (de ahí el requisito de que j == N )
f = función de transición
Además, no hay tres funciones llamadas f sino que f está dividida en partes, definida por tres ecuaciones.
si hubieras pasado por el algoritmo de gcd del euclid que dijo antes en el libro. la idea es marcar el comienzo de cada iteración como una etapa inicial y luego definir el número de estados que vendrán en una iteración de ciclo (es decir, N). ahora como recordarás, aceptamos la respuesta y detuvimos el cálculo cuando el resto de m dividido por n fue igual a cero. es decir, estábamos buscando una ocurrencia particular de una cadena Yj. cuando la compuación llega a su etapa final en el ciclo, está obligada a detenerse o reiterarse.
recuerde que estamos definiendo un ''método computacional'' y no un algoritmo. ¿Qué es un método computacional ingenuamente?
un "procedimiento" que tiene todas las características de un algoritmo, excepto que posiblemente carece de finitud, se puede llamar un método computacional.
simplemente ponga Q es un método computacional.
Q = {all possible states of computations, I, Ω}
I = {all possible inputs}
Ω = {all possible outputs}
f = computational rule
f es una función de Q en sí misma.
f: Q ---> Q
[I] [Ω]
f debe dejar Ω pointwise fixed lo que significa:
f (q) = q, ∀ q ∈ Ω observa que no es una función diferente, pero la misma regla computacional solo se separa a Ω
Ahora un procedimiento tendrá una secuencia. Y obviamente, un método computacional también debe tener una secuencia. Por lo tanto,
Cada entrada x en el conjunto I define una secuencia computacional x 0 , x 1 , x 2 , ..., como sigue: x 0 = x y x k + 1 = f (x k ) para k ≥ 0.
¿Cómo x 0 = x? No olvide que la entrada x es una secuencia, por lo que la secuencia de entrada inicial sería x 0 . Como estamos tratando con una secuencia, y cuando nos preocupamos por los "k" estados, importa el orden y la posición de los elementos en la secuencia. Y así, la regla computacional f es tal que la posición o palabra más precisa ''estado'' del k elemento k sería k + 1 ° estado. de esa manera, podemos aplicar por separado la función a cada nuevo estado para obtener el estado que sigue.
si x k + 1 no está en Ω, entonces no tiene sentido por definición de una función. De ahí la redacción de Knuth.
Se dice que la secuencia computacional termina en k pasos si k es el entero más pequeño para el cual x k está en Ω y en este caso, se dice que produce la salida x k de x.
Por lo tanto, esta es la definición de un método computacional. la regla computacional es el algoritmo.
Para una divulgación completa, recientemente escribí un artículo sobre la comprensión de la definición formal de un algoritmo de Knuth (pre-ejemplo). Una parte sustancial de lo siguiente es solo una copia / pega del texto relevante del artículo que responde a su primera pregunta en profundidad;
Su primera pregunta sobre (Q, I, Ω, f)
Definamos formalmente un método computacional para ser un cuádruple (Q, I, Ω, f), en el que Q es un conjunto que contiene subconjuntos I y Ω y f es una función de Q en sí misma.
Cuando Knuth se refiere a un método computacional como un cuádruple, simplemente está diciendo que un método computacional se compone de cuatro partes claramente definidas. Él etiqueta estas cuatro partes como (Q, I, Ω, f) . Luego pasa a describir brevemente cada componente de este cuádruple. I y Ω son conjuntos (colecciones de cosas), y Q también es un conjunto que contiene las cosas en los conjuntos I y Ω . En este punto, es fácil suponer erróneamente que quiere decir que Q contiene solo los conjuntos I y Ω y nada más. Pero luego descubrimos que este no es el caso. Por último, describe f como una función de Q en sí misma. Lo que esto significa es que f es un proceso que toma una entrada que es un elemento del conjunto Q y devuelve o emite otro elemento desde Q
Además f debería dejar Ω pointwise fijo; es decir, f (q) debería ser igual a q para todos los elementos q de Ω.
Lo que esto significa esencialmente es que, lo que devuelve nuestra función f, será el mismo que su argumento (es decir, el valor no cambiará) si el argumento es un miembro o elemento de (cosa en) establecido Ω . Esto tiene más sentido cuando Knuth hace una aclaración en su siguiente declaración; Alerta de spoiler - Ω es el conjunto de salidas posibles de nuestro método computacional. Una vez que sabemos esto, es un poco más fácil de entender. Pasar un resultado de regreso a nuestra función no lo cambiará.
Las cuatro cantidades Q, I, Ω, f están destinadas a representar respectivamente los estados de la computación, la entrada, la salida y la regla computacional.
Entonces Q es un conjunto que contiene todos los estados posibles del cálculo, es decir, todas las posibles variaciones de entrada, salida y todas las etapas intermedias. El conjunto I contiene todas las entradas posibles. El conjunto Ω contiene todas las salidas posibles (lo siento si estropeé esa revelación para ti antes). Y finalmente, f representa la regla computacional; es decir, los procesos / es aplicados a cada estado para obtener el estado siguiente, eventualmente (con suerte) hasta que obtengamos nuestro resultado.
Para aclarar, f representa una función única que tiene salidas definidas en función de sus posibles entradas. Solo tiene tres resultados posibles en este ejemplo específico, y podría tener más (o menos) en otros algoritmos. Entonces, ¿cuál es el propósito de definir los componentes de un algoritmo de esta manera? Al hacer que se definan usando la notación formal, también se pueden analizar y someter a examen matemático cuando se trata de analizar algoritmos específicos.
Pregunta sobre el tratamiento del algoritmo como un conjunto de cadenas
Respondí otra pregunta sobre este tema aquí . Pero esencialmente lo que Knuth hace aquí es usar un algoritmo de Markov para lograr lo que ya ha descrito. Vale la pena estudiar (y trabajar con algunos ejemplos de) los algoritmos de Markov para ayudarlo a comprender exactamente lo que está ocurriendo aquí.
Referencias