Terminación y corrección

Terminación y corrección

Al crear un algoritmo, se deben tener en cuenta los siguientes tres criterios: terminación, corrección y complejidad.

La terminación garantiza que el algoritmo termina después de un cierto número de operaciones elementales. La corrección asegura que el algoritmo dé el resultado esperado cuando finalice.

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.

algoritmo de terminación y corrección

Considere el siguiente algoritmo:

algoritmo de terminación y corrección

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.

algoritmo de terminación y corrección

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 convergente a una cantidad que toma sus valores en un conjunto bien fundado y que estrictamente disminuye con cada paso en un bucle. Un conjunto bien fundado es un conjunto totalmente ordenado en el que no hay una secuencia infinita estrictamente decreciente. La existencia de un bucle convergente para un bucle garantiza que el algoritmo termine saliendo de él. Por ejemplo, en el caso del algoritmo de Euclides, y es un convergente.

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.

algoritmo 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.

Compartir, repartir