Python - Justificación del algoritmo

Para hacer afirmaciones sobre la eficacia de un algoritmo, necesitamos algunas herramientas matemáticas como prueba. Estas herramientas nos ayudan a proporcionar una explicación matemáticamente satisfactoria sobre el rendimiento y la precisión de los algoritmos. A continuación se muestra una lista de algunas de esas herramientas matemáticas que se pueden utilizar para justificar un algoritmo sobre otro.

• Direct Proof:

  Es la verificación directa de la declaración mediante el uso de cálculos directos. Por ejemplo, la suma de dos números pares es siempre un número par. En este caso, simplemente agregue los dos números que está investigando y verifique que el resultado sea par.

• Proof by induction:

  Aquí comenzamos con una instancia específica de una verdad y luego la generalizamos a todos los valores posibles que son parte de la verdad. El enfoque consiste en tomar un caso de verdad verificada y luego demostrar que también es cierto para el siguiente caso para la misma condición dada. Por ejemplo, todos los números positivos de la forma 2n-1 son impares. Lo probamos para un cierto valor de n, luego lo probamos para el siguiente valor de n. Esto establece que el enunciado es generalmente verdadero mediante prueba de inducción.

• Proof by contraposition:

  Esta prueba se basa en la condición Si No A implica No B, entonces A implica B. Un ejemplo simple es si el cuadrado de n es par, entonces n debe ser par. Porque si el cuadrado de n no es par, entonces n no es par.

• Proof by exhaustion:

  Esto es similar a la prueba directa pero se establece visitando cada caso por separado y probando cada uno de ellos. Un ejemplo de tal demostración es el teorema de los cuatro colores.