Puede un algoritmo de ser parte de una prueba?

Question

Soy un estudiante de grado. He leído varios artículos en la teoría de grafos y encontró algo extraño: un algoritmo es parte de una prueba. En el papel, a excepción de las dos últimas frases, frases describe un algoritmo de etiquetado.

Puede un algoritmo de ser parte de una prueba? No entiendo por qué puede ser parte de una prueba. Le pregunté a mi supervisor, pero él no se lo explique.

LEMA$\,\,\,\bf 1.$ Si $B(G)-b$,$B(G+e)<2b$.

Prueba: Deje $f$ ser un óptimo de numeración de $G$, y deje $V(G)-\{v_1,\ldots,v_n\}$, numeradas por lo que el $f(v_i)-i$. Deje $v_lv_m$ ser el borde añadido. Definimos una nueva numeración $f'$ tal que $|f'(x)-f'(y)|<2|f(x)-f(y)|$, y también se $|f'(v_l)-f'(v_m)|-1$. Deje $r-\lfloor(l+m)/2\rfloor$, y establecer$f'(v_r)-1$$f'(v_{r+1})-2$. Para el resto de las $v_i$ tal que $|i-r|<\min\{r-1,n-r\}$, vamos a $f'(v_i)-f'(v_{i+1})+2$ si $i<r$ $f'(v_i)-f'(v_{i-1})+2$ si $i>r$. Esto define $f'$ de todos los vértices, excepto un conjunto de la forma $v_i,\ldots,v_k$ o $v_{n+1-k},\ldots,v_n$, dependiendo del signo de $r-\lfloor(n+1)/2\rfloor$. En el primer caso, asignamos $f'(v_i)-n+1-i$$i<k$; en el segundo, asignamos $f'(v_i)-i$$i>n-k$. La renumeración $f'$ números de los vértices hacia el exterior de $v_r$ conseguir $|f'(x)-f'(y)|<2|f(x)-f(y)|$. Desde que comenzamos a mitad de camino entre el$v_l$$v_m$, también tenemos $|f'(v_l)-f'(v_m)|-1$.

Answer 1

Yep! Las pruebas a veces implican cálculos complicados: la presentación de un algoritmo para hacer el cálculo es una buena manera de mostrar que el cálculo se puede hacer, y para analizar los resultados del cálculo.

En algunos campos-por ejemplo, la teoría de grafos-algoritmos se utilizan muy a menudo. A menudo, la manera más fácil de probar que algo se puede hacer es escribir un algoritmo que hace, y demostrar que el algoritmo funciona.

Usted puede pensar en este enfoque como un proceso sistemático y práctico para desarrollar y organizar complicado inductivo de las pruebas. Pero yo en realidad iba a pensar de otra forma: la inducción es sólo una más bien simplista tipo de algoritmo para la generación de una prueba. es decir, el algoritmo es "usar el argumento me llama el "caso base" para demostrar que para una $1$, a continuación, de forma iterativa aplicar el argumento me llama el "inductivo paso" para demostrar que para cada una de las sucesivas entero positivo".

Answer 2

Confieso que no he leído el párrafo cerrado (que contiene inexplicables en la notación; de todos modos yo no soy un experto en teoría de grafos), así que esto es una respuesta a su pregunta general.

Absolutamente sí, un algoritmo puede ser parte de una prueba. En ciertas situaciones (y para aquellos con ciertas inclinaciones) un algoritmo puede ser el mejor tipo posible de la prueba. Permítanme dar un simple ejemplo.

En mi clase de álgebra lineal recientemente le dijo a los estudiantes que cualquier permutación de $\{1,\ldots,n\}$ puede ser obtenida como la composición de los relatos, es decir, intercambio de dos elementos a la vez. Este no es un hecho obvio de que si usted no ha pensado en ello antes. Cuál fue mi prueba? Bueno, me dijo que de hecho, usted puede elegir el transposiciones a elementos adyacentes, y entonces yo les dije a los estudiantes que la forma más sencilla de ver esto es pensar acerca de cómo hacerlo en la práctica. Es fácil dar un algoritmo: inicio con el elemento que desea ir en la $n$º lugar. Si es que hay ya, genial. Si no es así, a continuación, seguir haciendo una secuencia de adyacentes swaps de llevar un paso más cerca de la $n$th posición cada vez. Haga esto hasta que se mete en la $n$th posición. Ahora podemos ver lo que nos queda como una permutación de $\{1,\ldots,n-1\}$ y trabajo por inducción.

El argumento anterior es sin duda un algoritmo: esto es algo que un estudiante de CS tendría poco de problemas de programación. Y es una prueba convincente. Lo convincente acerca de ella, por supuesto, es que usted puede ver por qué el algoritmo está haciendo lo que se supone que debe hacer. Podríamos escribir más formalmente, si queríamos, como un mundial de inducción argumento, y entonces podríamos usar el bien-principio de orden para argumentar que el movimiento del elemento de un paso cada vez más próxima a donde se quiere ir, significa que finalmente va a llegar, pero eso me parece excesivo en el presente caso.

En resumen: un algoritmo sin duda puede ser parte de una prueba, pero con la excepción de completamente trivial de los casos, un algoritmo, escrito en la forma en que un equipo puede aceptar, por ejemplo -, no debe ser la totalidad de la prueba. La otra parte importante es una explicación de por qué el algoritmo está haciendo lo que se alega para hacer. A veces simple, a veces no. De hecho, hay algunos increíbles teoremas que decir (más o menos) en general es imposible de averiguar qué es un algoritmo que se va a hacer, así que los algoritmos que son parte de las pruebas deben ser relativamente sencillo especie cuyo funcionamiento se puede explicar a un ser humano.

Último momento: Por la forma en que, "Cuando es un algoritmo de prueba preferida y cuando es un pensamiento puro/la existencia de la prueba preferida?" sería una fantástica pregunta, en mi opinión.

Answer 3

La prueba muestra cómo volver a numerar los vértices con los enteros $1,\ldots,n$ de tal manera que $|f\,'(v_\ell)-f\,'(v_m)|=1$ donde $e=v_\ell v_m$ es el nuevo borde, y $$|f\,'(x)-f\,'(y)|\le 2|f(x)-f(y)|$$ for each edge $xy$ of $G$. You have to think through the construction to see that it actually does this, but that's not too hard to do. This shows that $G+e$ has a numbering $f\,'$ que

$$\max_{xy\in E(G)\cup\{e\}}|f\,'(x)-f\,'(y)|\le 2\max_{xy\in E(G)}|f(x)-f(y)|\;,\tag{1}$$

donde $E(G)$ es el conjunto de aristas de $G$.

Supongo que desde el contexto que $B(G)$ es el mínimo sobre todas las numeraciones $g$ de $$\max_{xy\in E(G)}|g(x)-g(y)|\;;$$ $f$ is a numbering that achieves this minimum. Thus, $(1)$ shows that $G+e$ has a numbering $f\,'$ que

$$\max_{xy\in E(G)\cup\{e\}}|f\,'(x)-f\,'(y)|\le 2B(G)\;.$$

De ello se sigue que si $f''$ es un óptimo de numeración, el significado que alcanza el valor mínimo posible de

$$\max_{xy\in E(G)\cup\{e\}}|g(x)-g(y)|\;,$$

entonces

$$B(G+e)=\max_{xy\in E(G)\cup\{e\}}|f''(x)-f''(y)|\le \max_{xy\in E(G)\cup\{e\}}|f\,'(x)-f\,'(y)|\le 2B(G)\;,$$

que es lo que el lema de reclamaciones.

Es cierto que este esquema de numeración puede ser considerado como un algoritmo, pero que es realmente lado el punto: el punto real es que hace que sea claro para el lector por qué el lema es cierto, que es precisamente lo que una prueba se supone que debe hacer. También es cierto que sólo describir el esquema no rellene todos los detalles de la prueba, como he dicho, usted todavía tiene que convencer a ti mismo que funciona como se indica. Pero eso es cierto de todas las pruebas fuera de la muy limitada reino de formal teorema-resultando: que siempre tiene que llenar algunos de los detalles para usted.

Answer 4

Por el Curry-Howard correspondencia con la lógica de la proposición en intuitionistic lógica puede ser tomado como el tipo de la firma de un cálculo lambda de expresión. Equivalentemente, podemos usar combinadores en lugar de lambdas, y tienen un combinador correspondiente a cada lógico axioma o regla de inferencia.

Cálculo Lambda con tipos es lo suficientemente potente como para ser un lenguaje de programación real; de hecho, hay varios lenguajes de programación en uso hoy en día, que son poco más que cálculo lambda con tipos adicionales tales como la máquina de los números enteros y eficiente de estructuras de datos, y una buena dosis de azúcar sintáctico.

Cálculo Lambda también es turing completo, lo que significa que puede utilizar una máquina de turing para una prueba de una instrucción lógica también.

Por lo tanto, un algoritmo (que se ha demostrado correcta) es una prueba.