Contenido
PalancaTerminació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 igual. Para determinar el equivalente humano de la edad de un perro de menos de 15 kg, utilizamos la siguiente tabla, donde x es la edad real del animal (en años) e y es el equivalente humano en términos de envejecimiento.
Considere el siguiente algoritmo:
Revisemos la terminación. Es una suite de acondicionamiento con cálculos elementales en su interior. Una vez que se han verificado todas las condiciones en orden, el algoritmo finaliza.
En cuanto a la corrección, el algoritmo realiza 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 de parada del bucle, es decir, si se cancela y. En el bucle, y se reemplaza por un resto de módulo y. Entonces, con cada pasaje, disminuye estrictamente mientras permanece positivo o cero. Por lo tanto, y termina llegando a 0, luego salimos del ciclo. 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 a un bucle a una propiedad que, si es verdadera al entrar en un bucle, permanece verdadera después de cada paso a través de ese bucle. Por tanto, es cierto a la salida de este bucle. El invariante de bucle es análogo al principio de inducción. La demostración de un invariante de bucle adaptado permite probar la exactitud de un algoritmo. Por ejemplo, pgcd (a, b) = pgcd (x, y) es un ciclo 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.