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.

terminaison et correction algorithme

Considere el siguiente algoritmo:

terminaison et correction algorithme

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 se trata de apoyo a la toma de decisiones o investigación operativa. Luego, deben usarse principios matemáticos para demostrar que el algoritmo es correcto.

Tomemos el ejemplo del cálculo del mcd en modo iterativo.

terminaison et correction algorithme

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.

terminaison et correction algorithme

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.

Dans la deuxième partie de la condition, x décroit tandis que y possède une valeur aléatoire (strictement bornée). x tend donc vers la valeur 0. Dans la première partie de la condition, y décroit vers 0 à partir de sa valeur aléatoire. Nous en concluons donc que l’algorithme fait décroître y à 0, puis décrémente x avant de redonner une valeur à y.

Par récurrence nous en concluons que x tendra vers 0 après un certain nombre d’itération, donc que la deuxième partie ne sera plus visité. Et y tend aussi vers 0, donc nous sortons de la boucle. Nous avons donc prouver que l’algorithme se termine. Il n’est pas utile de parler de correction dans ce cas puisque nous n’avions pas de cahier des charges à vérifier.

Se observa que algún algoritmo no tiene prueba de terminación que la famosa función Syracuse.

Compartir, repartir
es_ESES
A los bloggers de %d les gusta esto: