¿Qué es una prueba de corte y pegado?

Question

He visto referencias para cortar y pegar pruebas en ciertos textos de algoritmos. ¿Cuál es la idea principal de tales pruebas? y ¿cómo hago para usarlos para probar algo?

Answer 1

El término "cortar y pegar" aparece en los algoritmos a veces cuando se hace programación dinámica (y otras cosas también, pero es ahí donde lo vi por primera vez). La idea es que para usar programación dinámica, el problema que está tratando de resolver probablemente tenga algún tipo de redundancia subyacente. Utiliza una tabla o una técnica similar para evitar resolver los mismos problemas de optimización una y otra vez. Por supuesto, antes de comenzar a utilizar la programación dinámica, sería bueno probar que el problema tiene esta redundancia, de lo contrario no obtendrá nada utilizando una tabla. Esto a menudo se denomina propiedad de "subproblema óptimo" (por ejemplo, en CLRS).

La técnica "cortar y pegar" es una forma de demostrar que un problema tiene esta propiedad. En particular, desea mostrar que cuando se presenta una solución óptima a un problema, necesariamente ha utilizado soluciones óptimas para los subproblemas constituyentes. La prueba es por contradiccion. Supongamos que se le ocurre una solución óptima a un problema mediante el uso de soluciones subóptimas a subproblemas. Entonces, si tuviera que reemplazar ("cortar") esas soluciones de subproblemas subóptimos con soluciones de subproblemas óptimas (al "pegarlas"), mejoraría su solución óptima. Pero, dado que su solución fue óptima por suposición, tiene una contradicción. Hay otros pasos involucrados en tal prueba, pero esa es la parte de "cortar y pegar".

Answer 2

Cortar y pegar es una forma utilizada en los conceptos de la teoría de gráficos, idea es esto: suponga que tiene solución para el problema A, quiere decir que algún borde/nodo debería estar disponible en solución. Suponga que tiene una solución sin borde/nodo especificado, intenta reconstruir una solución cortando un borde/nodo y pegando el borde/nodo especificado y diciendo que el nuevo beneficio de la solución es al menos igual que la solución anterior.

Una de las muestras más importantes está probando atributos MST (lo que demuestra que la elección codiciosa es lo suficientemente buena). ver presentation on MST from CLRS book.

Answer 3

'cortar y pegar' técnica se puede utilizar para demostrar tanto la corrección del algoritmo voraz (tanto la estructura óptima y la propiedad codiciosos-elección' y dinámica corrección algoritmo de programación.

Greedy corrección

Esta conferencia señala Correctness of MST del MIT 2005 exposiciones de clase de algoritmo de licenciatura 'cortar y pegar' técnica para demostrar tanto la estructura óptima y la propiedad codiciosos-elección.

Esta conferencia señala Correctness of MST del MIT 6.046J/18.410J primavera 2015 uso 'cortar y técnica de "pasteurización" para probar gr EEdy elección propiedad

Programación Dinámica corrección

Una explicación más auténtico para 'cortar y pegar' se introdujo en CLRS (tercera edtion) Capítulo 15.3 Elemento de programación dinámica en la página 379

"4 . Usted muestra que las soluciones a los subproblemas utilizados dentro de la solución óptima del problema deben ser óptimas utilizando una técnica de "cortar y pegar" , lo hace suponiendo que cada una de las soluciones de subproblema no es óptima y luego deriva una contradicción En particular, al "cortar" la solución de subproblemas no óptima y "pegar" la óptima, usted muestra que puede obtener una mejor solución al problema original, contradiciendo así su suposición de que ya tenía una solución óptima. Si hay más de un subproblema, por lo general son tan similares que el argumento de cortar y pegar uno puede modificarse para los demás con poco esfuerzo."

Answer 4

prueba por la contradicción

P se supone que es falsa, que es! P es cierto.

Se muestra que! P implica dos afirmaciones contradictorias entre sí, Q y! Q.

Dado que Q y! Q no pueden ser ambos verdaderos, la suposición de que P es falsa debe ser incorrecta y P debe ser verdadera.