Terminación y corrección
Al crear un algoritmo, se deben tener en cuenta los siguientes tres criterios: terminación, corrección y complejidad.
Ejemplo
Un ser humano y un perro no envejecen de la misma manera. Para determinar el equivalente humano de la edad de un perro de menos de 15 kg se utiliza la siguiente tabla, donde x representa la edad real del animal (en años), y y el equivalente humano en términos de envejecimiento.
Considere el siguiente algoritmo:
Vamos a comprobar la terminación. Es una suite de acondicionamiento con cálculos elementales en su interior. Una vez que todas las condiciones se verifican en orden, el algoritmo finaliza.
En términos de corrección, el algoritmo realiza bien las operaciones descritas en la tabla.
Difícil ejemplo
En general, la terminación es difícil de verificar porque no siempre sabemos, a priori, el número de instrucciones realizadas. La corrección es complicada cuando uno está en presencia deayuda con la decisión o investigación de operaciones. Entonces es necesario usar principios Matemáticas para probar que el algoritmo es correcto.
Tomemos el ejemplo del cálculo del mcd en modo iterativo.
El algoritmo finaliza si se cumple la condición para detener el bucle, es decir, si se cancela y. En el bucle, y se reemplaza por un resto módulo y. Entonces, en cada paso, y disminuye estrictamente mientras permanece positivo o cero. Por lo tanto, y finalmente llega a 0, por lo que salimos del bucle. El algoritmo termina bien después de un cierto número de iteraciones.
Inicialmente, x = ay y = b. En el ciclo, reemplazamos (x, y) por (y, x mod y). Sabemos que pgcd (x, y) = pgcd (y, x mod y). Entonces, en cada iteración, pgcd (x, y) = pgcd (a, b). Al final del ciclo, tenemos ay = 0, o pgcd (x, 0) = x. Por inducción deducimos que devolvemos pgcd (a, b). El algoritmo calcula correctamente el mcd deseado.
Herramienta de terminación y corrección
Llamamos invariante de bucle a una propiedad que, si es verdadera al entrar en un bucle, permanece verdadera después de cada paso a través de este bucle. Por lo tanto, es cierto a la salida de este bucle. El bucle invariante es análogo al principio de recurrencia. La demostración de un bucle invariante adaptado permite probar la corrección de un algoritmo. Por ejemplo, gcd(a,b)=gcd(x,y) es un bucle invariante.
Tomaremos como ejemplo un algoritmo con aleatoriedad para probar las nociones de terminación y corrección.
En informática, la aleatoriedad atribuye un valor en un rango de valores. El pseudoaleatorio está limitado por el tamaño del contenedor (int, double, etc.) o por el algoritmo utilizado (generación de un número módulo un número muy grande). En el algoritmo, asumimos que nyp son enteros estrictamente positivos. Si estos tienen una operación que lo hace negativo, entonces se asignará automáticamente el valor de 0.
En la segunda parte de la condición, x decrece mientras que y tiene un valor aleatorio (estrictamente acotado). x por lo tanto tiende hacia el valor 0. En la primera parte de la condición, y decrece hacia 0 desde su valor aleatorio. Por lo tanto, concluimos que el algoritmo reduce y a 0, luego reduce x antes de volver a dar un valor a y.
Por inducción concluimos que x tenderá a 0 después de un cierto número de iteraciones, por lo que ya no se visitará la segunda parte. Y y también tiende a 0, por lo que salimos del bucle. Por lo tanto, hemos probado que el algoritmo termina. No es útil hablar de corrección en este caso ya que no teníamos especificaciones para comprobar.
Se observa que algún algoritmo no tiene prueba de terminación que la famosa función Syracuse.
