Cómo engañar a la heurística de "probar algunos casos de prueba": Algoritmos que parecen correctos, pero en realidad son incorrectos

Para intentar probar si un algoritmo para algún problema es correcto, el punto de partida habitual es intentar ejecutar el algoritmo a mano en una serie de casos de prueba simples; pruébelo en algunos ejemplos de problemas, incluidos algunos "casos de esquina" simples ". Esta es una gran heurística: es una excelente manera de eliminar rápidamente muchos intentos incorrectos de un algoritmo y de comprender por qué el algoritmo no funciona.

Sin embargo, cuando aprenden algoritmos, algunos estudiantes se sienten tentados a detenerse allí: si su algoritmo funciona correctamente en un puñado de ejemplos, incluidos todos los casos de esquina que pueden pensar intentar, entonces concluyen que el algoritmo debe ser correcto. Siempre hay un estudiante que pregunta: "¿Por qué necesito probar que mi algoritmo es correcto, si puedo probarlo en algunos casos de prueba?"

Entonces, ¿cómo engañas a la heurística "prueba un montón de casos de prueba"? Estoy buscando algunos buenos ejemplos para demostrar que esta heurística no es suficiente. En otras palabras, estoy buscando uno o más ejemplos de un algoritmo que superficialmente parece ser correcto, y que genera la respuesta correcta en todas las entradas pequeñas que cualquiera pueda encontrar, pero donde el algoritmo realmente no funciona Tal vez el algoritmo funciona correctamente en todas las entradas pequeñas y solo falla para las entradas grandes, o solo falla para las entradas con un patrón inusual.

Específicamente, estoy buscando:

1. Un algoritmo La falla tiene que estar en el nivel algorítmico. No estoy buscando errores de implementación. (Por ejemplo, como mínimo, el ejemplo debe ser independiente del lenguaje y la falla debe relacionarse con preocupaciones algorítmicas en lugar de problemas de implementación o ingeniería de software).

2. Un algoritmo que alguien podría inventar. El pseudocódigo debería verse al menos plausiblemente correcto (por ejemplo, el código que está ofuscado u obviamente dudoso no es un buen ejemplo). Puntos de bonificación si se trata de un algoritmo que a algún alumno se le ocurrió al tratar de resolver un problema de tarea o examen.

3. Un algoritmo que pasaría una estrategia de prueba manual razonable con alta probabilidad. Es improbable que alguien que prueba algunos casos de prueba pequeños a mano descubra la falla. Por ejemplo, "simular QuickCheck a mano en una docena de casos de prueba pequeños" no debería revelar que el algoritmo es incorrecto.

4. Preferiblemente, un algoritmo determinista. He visto a muchos estudiantes pensar que "probar algunos casos de prueba a mano" es una forma razonable de verificar si un algoritmo determinista es correcto, pero sospecho que la mayoría de los estudiantes no supondría que probar algunos casos de prueba es una buena manera de verificar probabilidades algoritmos Para los algoritmos probabilísticos, a menudo no hay forma de saber si alguna salida en particular es correcta; y no puede hacer suficientes ejemplos a mano para hacer una prueba estadística útil sobre la distribución de salida. Por lo tanto, preferiría centrarme en los algoritmos deterministas, ya que llegan de manera más clara al corazón de los conceptos erróneos de los estudiantes.

Me gustaría enseñar la importancia de probar que su algoritmo es correcto, y espero utilizar algunos ejemplos como este para ayudar a motivar las pruebas de corrección. Preferiría ejemplos que sean relativamente simples y accesibles para estudiantes universitarios; Los ejemplos que requieren maquinaria pesada o un montón de antecedentes matemáticos / algorítmicos son menos útiles. Además, no quiero algoritmos que sean "antinaturales"; Si bien puede ser fácil construir algún algoritmo artificial extraño para engañar a la heurística, si se ve muy poco natural o tiene una puerta trasera obvia construida solo para engañar a esta heurística, probablemente no sea convincente para los estudiantes. ¿Algún buen ejemplo?

Creo que un error común es utilizar algoritmos codiciosos, que no siempre es el enfoque correcto, pero que podría funcionar en la mayoría de los casos de prueba.

Ejemplo: las denominaciones de monedas, y un número , expresan como una suma de : s con la menor cantidad de monedas posible. n n d $d_1,\dots,d_k$$n$$n$$d_i$

Un enfoque ingenuo es usar la moneda más grande posible primero y producir con avidez tal suma.

Por ejemplo, las monedas con valor , y darán respuestas correctas con codicia para todos los números entre y excepto el número .5 1 1 14 10 = 6 + 1 + 1 + 1 + 1 = 5 + $6$$5$$1$$1$$14$$10 = 6+1+1+1+1 = 5+5$

Inmediatamente recordé un ejemplo de R. Backhouse (esto podría haber estado en uno de sus libros). Aparentemente, había asignado una tarea de programación donde los estudiantes tenían que escribir un programa Pascal para probar la igualdad de dos cadenas. Uno de los programas entregados por un estudiante fue el siguiente:

issame := (string1.length = string2.length);

if issame then
  for i := 1 to string1.length do
    issame := string1.char[i] = string2.char[i];

write(issame);

Ahora podemos probar el programa con las siguientes entradas:

"universidad" "universidad" Verdadero; Okay$\Rightarrow$

"curso" "curso" Verdadero; Okay$\Rightarrow$

"" "" Verdadero; Okay$\Rightarrow$

"curso" "universitario" falso; Okay$\Rightarrow$

"conferencia" "curso" Falso; Okay$\Rightarrow$

"precisión" "exactitud" Falso, OK$\Rightarrow$

Todo esto parece muy prometedor: tal vez el programa sí funciona. Pero una prueba más cuidadosa con decir "puro" y "verdadero" revela una salida defectuosa. De hecho, el programa dice "Verdadero" si las cadenas tienen la misma longitud y el mismo último carácter.

Sin embargo, las pruebas habían sido bastante exhaustivas: teníamos cadenas con diferente longitud, cadenas con igual longitud pero diferente contenido, e incluso cadenas iguales. Además, el estudiante incluso había probado y ejecutado cada rama. Realmente no se puede argumentar que las pruebas han sido descuidadas aquí, dado que el programa es muy simple, puede ser difícil encontrar la motivación y la energía para probarlo lo suficientemente a fondo.

Otro lindo ejemplo es la búsqueda binaria. En TAOCP, Knuth dice que "aunque la idea básica de búsqueda binaria es relativamente sencilla, los detalles pueden ser sorprendentemente difíciles". Aparentemente, un error en la implementación de búsqueda binaria de Java pasó desapercibido durante una década. Fue un error de desbordamiento de enteros, y solo se manifestó con una entrada lo suficientemente grande. Bentley también cubre detalles engañosos de implementaciones de búsqueda binaria en el libro Programming Pearls .

En pocas palabras: puede ser sorprendentemente difícil estar seguro de que un algoritmo de búsqueda binaria es correcto simplemente probándolo.

El mejor ejemplo que he encontrado es la prueba de primalidad:

entrada: número natural p, p! = 2
salida: es pa prime o no?
algoritmo: calcular 2 ** (p-1) mod p. Si resultado = 1, entonces p es primo, de lo contrario p no lo es.

Esto funciona para (casi) todos los números, excepto para unos pocos ejemplos de contadores, y uno realmente necesita una máquina para encontrar un contraejemplo en un período de tiempo realista. El primer contraejemplo es 341, y la densidad de los contraejemplos en realidad disminuye con el aumento de p, aunque casi logarítmicamente.

En lugar de usar solo 2 como la base de la potencia, uno puede mejorar el algoritmo usando también primos pequeños adicionales que aumenten como base en caso de que el primo anterior devuelva 1. Y aún así, hay un contraejemplo de este esquema, a saber, los números de Carmichael, aunque bastante raro

Aquí hay uno que me arrojaron los representantes de Google en una convención a la que fui. Fue codificado en C, pero funciona en otros lenguajes que usan referencias. Perdón por tener que codificar en [cs.se], pero es el único que lo ilustra.

swap(int& X, int& Y){
    X := X ^ Y
    Y := X ^ Y
    X := X ^ Y
}

Este algoritmo funcionará para cualquier valor dado a x e y, incluso si tienen el mismo valor. Sin embargo, no funcionará si se llama swap (x, x). En esa situación, x termina como 0. Ahora, esto podría no satisfacerte, ya que de alguna manera puedes probar que esta operación es matemáticamente correcta, pero aún así olvidarte de este caso límite.

Hay toda una clase de algoritmos que es inherentemente difícil de probar: generadores de números pseudoaleatorios . No puede probar una sola salida, pero tiene que investigar (muchas) series de salidas con medios estadísticos. Dependiendo de qué y cómo realice la prueba, puede pasar por alto características no aleatorias.

Un caso famoso donde las cosas salieron terriblemente mal es RANDU . Pasó el escrutinio disponible en ese momento, que no tuvo en cuenta el comportamiento de las tuplas de los resultados posteriores. Los triples ya muestran mucha estructura:

Básicamente, las pruebas no cubrieron todos los casos de uso: si bien el uso unidimensional de RANDU fue (probablemente en su mayoría) correcto, no admitió su uso para muestrear puntos tridimensionales (de esta manera).

El muestreo pseudoaleatorio adecuado es un asunto complicado. Afortunadamente, hay poderosos conjuntos de pruebas en estos días, por ejemplo, dieharder que se especializan en lanzar todas las estadísticas que conocemos en un generador propuesto. ¿Es suficiente?

^{Para ser justos, no tengo idea de lo que puede probar para los PRNG.}

Máximo local 2D

entrada: 2 dimensiones matriz $n \times n$$A$

salida: un máximo local: un par tal que A [ i , j ] no tiene una celda vecina en la matriz que contenga un valor estrictamente mayor. $(i,j)$$A[i,j]$

$A[i, j+1], A[i, j-1], A[i-1, j], A[i+1, j]$$A$

entonces cada celda en negrita es un máximo local. Cada matriz no vacía tiene al menos un máximo local.

$O(n^2)$

$A$$X$$X$$A$$(i, j)$$X$$(i, j)$$(i', j')$

$A \setminus X$$A$$X$$(i', j')$$A'$

$A'$$A$

$(i', j')$$A'$$A'$$(i', j')$$\diamond$

$\frac{n}{2}\times\frac{n}{2}$$A'$$(i, j)$

$T(n)$$n\times n$$T(n) = T(n/2) + O(n)$$T(n) = O(n)$

Por lo tanto, hemos demostrado el siguiente teorema:

$O(n)$$n\times n$

O tenemos?

Estos son ejemplos de primalidad, porque son comunes.

(1) Primalidad en SymPy. Edición 1789 . Hubo una prueba incorrecta en un sitio web conocido que no falló hasta después de 10 ^ 14. Si bien la solución fue correcta, solo estaba reparando agujeros en lugar de repensar el problema.

(2) Primalidad en Perl 6. Perl6 ha añadido is-prime que utiliza una serie de pruebas de RM con bases fijas. Hay contraejemplos conocidos, pero son bastante grandes ya que el número predeterminado de pruebas es enorme (básicamente oculta el problema real al degradar el rendimiento). Esto se abordará pronto.

(3) Primalidad en FLINT. n_isprime () devuelve verdadero para los compuestos , ya que corregido Básicamente el mismo problema que SymPy. Usando la base de datos Feitsma / Galway de pseudoprimos SPRP-2 a 2 ^ 64 ahora podemos probar estos.

(4) Matemáticas de Perl :: Primalidad. is_aks_prime roto . Esta secuencia parece similar a muchas implementaciones de AKS: mucho código que funcionó por accidente (por ejemplo, se perdió en el paso 1 y terminó haciendo todo por división de prueba) o no funcionó para ejemplos más grandes. Lamentablemente, AKS es tan lento que es difícil probarlo.

(5) Pari pre-2.2 es_prime. Matemáticas :: Boleto Pari . Se utilizaron 10 bases aleatorias para las pruebas de MR (con semilla fija en el inicio, en lugar de la semilla fija de GMP en cada llamada). Le dirá que 9 es primo sobre 1 de cada 1 millón de llamadas. Si elige el número correcto, puede hacer que falle con relativa frecuencia, pero los números se vuelven más dispersos, por lo que no aparece mucho en la práctica. Desde entonces han cambiado el algoritmo y la API.

Esto no está mal, pero es un clásico de las pruebas probabilísticas: ¿cuántas rondas das, por ejemplo, mpz_probab_prime_p? Si le damos 5 rondas, seguramente parece que funciona bien: los números tienen que pasar una prueba de Fermat de base 210 y luego 5 pruebas de Miller-Rabin de bases preseleccionadas. No encontrará un contraejemplo hasta 3892757297131 (con GMP 5.0.1 o 6.0.0a), por lo que tendrá que hacer muchas pruebas para encontrarlo. Pero hay miles de contraejemplos bajo 2 ^ 64. Entonces sigues aumentando el número. ¿Cuán lejos? ¿Hay un adversario? ¿Qué tan importante es una respuesta correcta? ¿Estás confundiendo bases aleatorias con bases fijas? ¿Sabes qué tamaños de entrada recibirás?

$10^{16}$

Estos son bastante difíciles de probar correctamente. Mi estrategia incluye pruebas unitarias obvias, más casos extremos, más ejemplos de fallas vistas antes o en otros paquetes, prueba frente a bases de datos conocidas donde sea posible (por ejemplo, si realiza una sola prueba de MR de base-2, entonces ha reducido la inviabilidad computacional tarea de probar 2 ^ 64 números para probar unos 32 millones de números), y finalmente, muchas pruebas aleatorias utilizando otro paquete como estándar. El último punto funciona para funciones como primalidad donde hay una entrada bastante simple y una salida conocida, pero algunas tareas son así. He usado esto para encontrar defectos tanto en mi propio código de desarrollo como problemas ocasionales en los paquetes de comparación. Pero dado el espacio de entrada infinito, no podemos probar todo.

En cuanto a probar la corrección, aquí hay otro ejemplo de primalidad. Los métodos BLS75 y ECPP tienen el concepto de un certificado de primalidad. Básicamente, después de realizar búsquedas para encontrar valores que funcionen para sus pruebas, pueden generarlos en un formato conocido. Entonces se puede escribir un verificador o que alguien más lo escriba. Estos se ejecutan muy rápido en comparación con la creación, y ahora (1) ambos fragmentos de código son incorrectos (de ahí que prefiera otros programadores para los verificadores), o (2) la matemática detrás de la idea de la prueba es incorrecta. El n. ° 2 siempre es posible, pero generalmente han sido publicados y revisados ​​por varias personas (y en algunos casos son lo suficientemente fáciles como para que usted lo revise).

En comparación, los métodos como AKS, APR-CL, la división de prueba o la prueba determinista de Rabin, no producen otro resultado que no sea "primo" o "compuesto". En el último caso, podemos tener un factor que puede verificar, pero en el primer caso nos queda nada más que este bit de salida. ¿Funcionó el programa correctamente? No sé.

Es importante probar el software en más que unos pocos ejemplos de juguetes, y también revisar algunos ejemplos en cada paso del algoritmo y decir "dada esta entrada, ¿tiene sentido que esté aquí con este estado?"

El algoritmo de barajado de Fisher-Yates-Knuth es un ejemplo (práctico) y sobre el cual uno de los autores de este sitio ha comentado .

El algoritmo genera una permutación aleatoria de una matriz dada como:

 // To shuffle an array a of n elements (indices 0..n-1):
  for i from n − 1 downto 1 do
       j ← random integer with 0 ≤ j ≤ i
       exchange a[j] and a[i]

$i$$j$$0 \le j \le i$

Un algoritmo "ingenuo" podría ser:

 // To shuffle an array a of n elements (indices 0..n-1):
  for i from n − 1 downto 1 do
       j ← random integer with 0 ≤ j ≤ n-1
       exchange a[j] and a[i]

En qué parte del bucle se elige el elemento a intercambiar entre todos los elementos disponibles. Sin embargo, esto produce un muestreo sesgado de las permutaciones (algunas están sobrerrepresentadas, etc.)

En realidad, uno puede inventar la mezcla de pescador-yates-knuth usando un análisis de conteo simple (o ingenuo) .

$n$$n! = n \times n-1 \times n-2 ..$$n$$n-1$

El principal problema para verificar si el algoritmo de barajado es correcto o no ( sesgado o no ) es que debido a las estadísticas, se necesita una gran cantidad de muestras. El artículo de codinghorror que enlace arriba explica exactamente eso (y con pruebas reales).

El mejor ejemplo (léase: algo que me duele más) que he visto tiene que ver con la conjetura de collatz. Estuve en una competencia de programación (con un premio de 500 dólares en la línea por el primer lugar) en el que uno de los problemas era encontrar el número mínimo de pasos necesarios para que dos números alcancen el mismo número. La solución, por supuesto, es dar un paso alternativo a cada uno hasta que ambos alcancen algo que se haya visto antes. Nos dieron un rango de números (creo que estaba entre 1 y 1000000) y nos dijeron que la conjetura de collatz había sido verificada hasta 2 ^ 64, por lo que todos los números que nos dieron eventualmente convergerían en 1. Usé 32 bits enteros para hacer los pasos con sin embargo. Resulta que hay un número oscuro entre 1 y 1000000 (170 mil algo) que hará que un número entero de 32 bits se desborde a su debido tiempo. De hecho, estos números son extremadamente raros debajo de 2 ^ 31. Probamos nuestro sistema en busca de NÚMEROS ENORMES muy superiores a 1000000 para "garantizar" que no se produjera un desbordamiento. Resulta que un número mucho más pequeño que simplemente no probamos causó un desbordamiento. Debido a que usé "int" en lugar de "largo", solo obtuve un premio de 300 dólares en lugar de un premio de $ 500.

El problema de Mochila 0/1 es uno que casi todos los estudiantes piensan que es solucionable mediante un algoritmo codicioso. Eso sucede más a menudo si previamente muestra algunas soluciones codiciosas como la versión problemática de la mochila donde funciona un algoritmo codicioso .

Para esos problemas, en clase , debo mostrar la prueba de Knapsack 0/1 ( programación dinámica ) para eliminar cualquier duda y también para la versión del problema codicioso. En realidad, ambas pruebas no son triviales y los estudiantes probablemente las encuentren muy útiles. Además, hay un comentario sobre esto en CLRS 3ed , Capítulo 16, Página 425-427 .

Problema: el ladrón roba una tienda y puede llevar un peso máximo de W en su mochila. Hay n artículos y un artículo pesa wi y vale vi dólares. ¿Qué artículos debe llevar el ladrón? para maximizar su ganancia ?

Problema de mochila 0/1 : la configuración es la misma, pero los elementos no se pueden dividir en pedazos más pequeños , por lo que el ladrón puede decidir tomar un elemento o dejarlo (opción binaria), pero no puede tomar una fracción de un elemento .

Y puede obtener de los estudiantes algunas ideas o algoritmos que siguen la misma idea que el problema de la versión codiciosa, eso es:

• Tome la capacidad total de la bolsa y coloque tanto como sea posible el objeto de mayor valor, e itere este método hasta que no pueda poner más objeto porque la bolsa está llena o no hay un objeto con menos o igual peso para poner dentro de la bolsa.
• Otra forma incorrecta es pensar: coloque artículos más livianos y coloque estos siguientes de mayor a menor precio.
• ...

¿Es útil para ti? En realidad, sabemos que el problema de la moneda es una versión con problemas de mochila. Pero, hay más ejemplos en el bosque de problemas de la mochila, por ejemplo, ¿qué pasa con la mochila 2D (que es realmente útil cuando quieres cortar madera para hacer muebles , vi en un local de mi ciudad), es muy común pensar que el codicioso trabaja aquí también, pero no.

Un error común es implementar mal los algoritmos de barajado. Ver discusión en wikipedia .

$n!$$n^n$$(n-1)^n$

Python PEP450 que introdujo funciones estadísticas en la biblioteca estándar podría ser de interés. Como parte de la justificación para tener una función que calcula la varianza en la biblioteca estándar de python, el autor Steven D'Aprano escribe:

def variance(data):
        # Use the Computational Formula for Variance.
        n = len(data)
        ss = sum(x**2 for x in data) - (sum(data)**2)/n
        return ss/(n-1)

Lo anterior parece ser correcto con una prueba casual:

>>> data = [1, 2, 4, 5, 8]
>>> variance(data)
  7.5

Pero agregar una constante a cada punto de datos no debería cambiar la varianza:

>>> data = [x+1e12 for x in data]
>>> variance(data)
  0.0

Y la varianza nunca debe ser negativa:

>>> variance(data*100)
  -1239429440.1282566

El problema es sobre los números y cómo se pierde la precisión. Si desea la máxima precisión, debe ordenar sus operaciones de cierta manera. Una implementación ingenua conduce a resultados incorrectos porque la imprecisión es demasiado grande. Ese fue uno de los temas de los que trataba mi curso de numérica en la universidad.

Si bien es probable que esto no sea exactamente lo que buscas, sin duda es fácil de entender y probar algunos casos pequeños sin ningún otro pensamiento conducirá a un algoritmo incorrecto.

$n$$n^2+n+41$$0<d$$d\text{ divides } n^2+n+41$$d < n^2+n+41$

Solución propuesta :

int f(int n) {
   return 1;
}

$n= 0, 1, 2, \dotsc, 39$$n=40$

Este enfoque de "probar algunos casos pequeños e inferir un algoritmo a partir del resultado" aparece con frecuencia (aunque no tan extremadamente como aquí) en las competencias de programación donde la presión es crear un algoritmo que (a) se implemente rápidamente y (b ) tiene un tiempo de ejecución rápido.