Prueba matemática de corrección de algoritmo y eficiencia

Introducción

Al diseñar un algoritmo completamente nuevo, se necesita un análisis muy completo de su correccióneficiencia .
Lo último que desearía es que su solución no sea adecuada para un problema que fue diseñado para resolver en primer lugar.
En este artículo hablaremos de los siguientes temas:
DESCARGO DE RESPONSABILIDAD : como puede ver en los títulos de la sección, esto no es de ninguna manera, forma o forma destinada a la aplicación directa. Es la teoría de la ciencia de la computación , y solo está destinada a una comprensión más profunda de ciertos campos de la programación práctica.

Inducción matemática

La inducción matemática (IM) es una herramienta esencial para probar la afirmación que demuestra la corrección de un algoritmo. La idea general de MI es probar que una afirmación es cierta para cada número natural n.
¿Qué significa esto realmente?
Esto significa que tenemos que pasar por 3 pasos:
  1. Hipótesis de inducción : defina la regla que queremos probar para cada uno n, llamémosla reglaF(n)
  2. Base de inducción : probar que la regla es válida para un valor inicial, o más bien como un punto de partida, esto se prueba a menudo resolviendo la Hipótesis de Inducción F(n)para n=1o cualquier valor inicial que sea apropiado
  3. Paso de inducción : demostrando que si sabemos que eso F(n)es cierto, podemos stepdar un paso adelante y asumir que F(n+1)es correcto
Si siguió estos pasos, ¡ahora tiene el poder de hacer un bucle! No, realmente, esto básicamente nos da la capacidad de hacer algo como esto:
for (i in range(n)):  
    T[i] = True

Ejemplo básico

problema :
Si definimos S(n)como la suma de los primeros nnúmeros naturales, por ejemplo S(3) = 3+2+1, probemos que la siguiente fórmula se puede aplicar a cualquiera n:
S(norte)=(norte+1)norte2
Sigamos nuestros pasos:
  1. Hipótesis de inducción : S(n)definida con la fórmula anterior.
  2. Base de inducción : En este paso tenemos que demostrar que S(1) = 1:
    S(1)=(1+1)12=22=1
  3. Paso de inducción : en este paso debemos probar que si la fórmula se aplica a S(n), también se aplica a S(n+1)lo siguiente:
    $$ S (n + 1) = \ frac {(n + 1 + 1) * (n + 1)} {2} = \ frac {(n + 2) * (n + 1)} {2} $$S(norte+1)=(norte+1+1)(norte+1)2=(norte+2)(norte+1)2
Esto se conoce como una implicación (a => b), lo que simplemente significa que debemos demostrar que bes correcto siempre que sepamos que aes correcto.
S(norte+1)=S(norte)+(norte+1)=(norte+1)norte2+(norte+1)=norte2+norte+2norte+22
=norte2+3norte+22=(norte+2)(norte+1)2
Tenga en cuenta que S(n+1) = S(n) + (n+1)solo significa que estamos calculando recursivamente la suma. Ejemplo con literales: S(3) = S(2) + 3= S(1) + 2 + 3 = 1 + 2 + 3 = 6
QED

Prueba de corrección

Debido a que el método que utilizamos para probar la corrección de un algoritmo se basa en las matemáticas, o más bien en la función , cuanto más similar sea la solución a una función matemática real, más fácil será la prueba.
¿Por qué es esto lo que puedes preguntar? Bueno, la programación imperativa práctica tiene esta cosa llamada estado , esto significa que la salida de un programa depende de 3 cosas:
  1. Su secuencia de instrucciones
  2. Sus valores de entrada
  3. su estado , o más bien, todas las variables previamente inicializadas que pueden cambiar de alguna manera el valor de salida

Ejemplo de estado del programa

def foo(x):  
    x = y + 1
    return x
Si te pidiera que me dieras el valor de salida de esta función x=1, naturalmente dirías:
Bueno, señor, ¿cómo sabríamos el valor de salida si no conocemos ese yvalor maldito ?
Usted ve, ese es exactamente el punto, este (imperativo) programa como cualquier otro tiene un estado , que se define por una lista de variables y sus valores correspondientes. Sólo entonces la salida de este programa es verdaderamente determinista .
Determinista - un sistema sin factores aleatorios
Esto abre una historia completamente nueva sobre los paradigmas de programación que tienen un estado completamente transparente, o en otras palabras, NO TIENEN VARIABLES . Esto puede parecer una locura, pero existe, y se utiliza con poca frecuencia, especialmente la programación funcional en Haskell .
Pero debido a que tradicionalmente no tenemos conceptos funcionales a nuestra disposición en la programación imperativa, nos conformamos con la mejor opción para demostrar la corrección, la recursión . La recursión es muy fácil para la interpretación matemática porque es equivalente a las relaciones de recurrencia (más sobre las relaciones de recurrencia en los siguientes segmentos).

Ejemplo de Recursión

def factorial(n):  
    if (n==0):
        return 1
    else:
        return n*factorial(n-1)
Convertido a la forma de recurrencia:
Funadotoryounal(norte)=norteFunadotoryounal(norte-1)

Invariantes de bucle

Todo esto suena bien y elegante, pero hasta ahora, no hemos dicho nada sobre la representación de bucles y estados de programas como fórmulas matemáticas. Las variables en el estado de un programa plantean un problema porque todas ellas deben mantenerse controladas todo el tiempo, en caso de que uno se vuelva loco.
Además, los bucles plantean un problema porque hay muy pocos equivalentes matemáticos. Esto significa que tenemos que incorporar la inducción matemática en nuestro Modelo de Análisis de Algoritmos , porque es el único método que sabemos que puede incriminar iterativamente los valores en matemáticas, como en el código real.
La forma más sencilla de resolver ambos problemas (con inducción matemática) es invariantes de bucle :
Un bucle invariante es una fórmula lógica o simplemente un conjunto de reglas, que es cierto antes, durante y después del bucle en cuestión (por lo que es imparcial a la iteración). Es imperativo que contenga reglas para todas las variables que se producen en dicho bucle porque debemos vincularlas todas al conjunto de valores que queremos que sean.

Selección invariante en bucle

Un bucle invariante puede ser tan complicado y tan simple como quieras que sea. Sin embargo, el punto es que debe ser construido para parecerse al problema en cuestión lo más cerca posible.
Por ejemplo, siempre puedo decir que lo siguiente es un bucle invariante:
(X>y)(X<y)(X==y)
Pero, al utilizar una tautología (una fórmula lógica que siempre es correcta) como invariante de bucle, realmente no logramos nada, la única razón por la que está técnicamente clasificado como invariante de bucle es que cumple con los 3 requisitos:
  1. La fórmula es correcta ANTES de la ejecución del bucle
  2. La fórmula es correcta DURANTE la ejecución del bucle, incluyendo todos los pasos intermedios
  3. La fórmula es correcta después de la ejecución del bucle.

Ejemplo:

Echemos un vistazo al siguiente código y determinemos la invariante de bucle óptima:
x = 10  
y = 4  
z = 0  
n = 0  
while(n < x):  
    z = z+y
    n = n+1
Lógicamente, este código solo calcula el valor x * y lo almacena en z, esto significa que z = x*yOtra condición que sabemos que siempre será verdadera es n <= x(más sobre los iguales en el ejemplo). Pero, ¿estos dos realmente solo se aplican después de que el programa haya terminado de computar?
El nvalor es esencialmente el número de bucles que ya se ejecutaron, pero también, es el número de veces que el zvalor ha aumentado y.
Así que esto significa que ambos z = n*y y n <= x pueden aplicarse en todo momento . Lo único que queda por hacer es comprobar si realmente se pueden utilizar como un invariante de bucle.

Ejemplo de invariante de bucle - Prueba por inducción

Primero, debemos probar que el bucle invariante es verdadero antes de ingresar al bucle (que es el equivalente de probar y la base de inducción ):
# <=> - logical equivalency, left and right sides of the equation have the same logical value (True or False)
# <= - less or equal (not to be confused with implication, which also looks like a arrow to the left)
x = 10  
y = 4  
z = 0  
n = 0  
# RULE 1: z == n*y
# 0 == 0*4 = 0 <=> True
# so RULE 1 applies

# RULE 2: n <= x
# 0 <= 10 <=> True
# so RULE 2 applies, therefore the invariant is valid before entering the loop
En segundo lugar, debemos verificar si el invariante es verdadero después de cada ciclo finalizado (excluyendo el último), lo hacemos observando la transición de z,nz',n', dónde z'cuáles n'son los valores de zndespués de que se haya ejecutado el siguiente ciclo.
Por lo tanto, z' = z+yn' = n+1Tenemos que probar, esencialmente, que si sabemos que el invariante es cierto para zn, también es cierto para z'n':
z=z+yz=norteynorte=norte+1Si el seguimiento es válido, el invariante es válido: z=nortey?z=(norte+1)y=nortey+y=z+y
En tercer lugar, debemos comprobar si el invariante es verdadero después de la última iteración del bucle. Porque nes un entero y sabemos que n-1<xes cierto, pero n<xes falso, eso significa que n=x(esta es la razón por la cual el invariante tiene que incluir n<=x, no n<x).
Por eso lo sabemos z = x*y.
QED

Análisis de eficiencia: relaciones de recurrencia

Cuando se habla de eficiencia de algoritmos, lo primero que surge son las relaciones de recurrencia. Esto solo significa que una función como f(n)es dependiente de sus valores anteriores y posteriores, como f(n-1)f(n+1).
El ejemplo más simple de este tipo de función sería la secuencia de Fibonacci:
Fyosegundoonorteunadodoyo(norte)=Fyosegundoonorteunadodoyo(norte-1)+Fyosegundoonorteunadodoyo(norte-2)
Es posible que realmente reconozca este concepto de mi artículo sobre Programación Dinámica . Y sí, el problema es muy similar, sin embargo, el método de resolución es muy diferente.
Al analizar la eficiencia del algoritmo, hay básicamente dos tipos de relaciones que resolverás:
  1. Relaciones de recurrencia homogéneas lineales.
  2. Relaciones de recurrencia no lineales - Caso de uso del teorema maestro

Resolviendo relaciones homogéneas de recurrencia lineal

Al leer el título anterior, puedes preguntarte
"¡¿Qué en el nombre de dios es esta matemática tontería?!?!"
Bueno, primero echemos un vistazo a la fórmula general:
F(norte)=una1F(norte-1)+una2F(norte-2)+...+unakF(norte-k).
Ahora vamos a dividir la definición en partes de tamaño byte (juego de palabras intencionado):
  1. Lineal se refiere al hecho de que los elementos de función F(something)son a la primera potencia.
  2. Homogéneo se refiere al hecho de que todas las dupletas de elementos a*F(something)son uniformes, lo que significa que una constante no puede estar presente ( a*F(something) = constno puede suceder)
Estas relaciones de recurrencia se resuelven utilizando la siguiente sustitución:
(1)  F(norte)=rnorte
  • r ser un número (complejo) convenientemente elegido
Enumeraré fórmulas útiles para poder hacer referencia a ellas más fácilmente en el ejemplo.
Estamos utilizando un número complejo porque necesitamos una variable que pueda alternar entre varios valores, de los cuales todos pueden (pero no tienen que) ser diferentes. Todos los cuales son roots(soluciones) a la ecuación anterior.
Aclaración:
  • complexlos números tienen una forma de x = a + bixsiendo el número complejo, absiendo enteros simples, y isiendo la constante:yo=-1
  • Como puedes notar ies un número muy particular, lo que significa que en realidad tiene un ciclo :yo=-1yo2=-1yo3=-1-1yo4=1yo5=yo,
  • esto significa que itiene un ciclo delength = 5
  • otros números complejos pueden ser hechos a medida para tener un ciclo preciso, donde no hay dos elementos iguales (excepto los elementos inicial y final)
Usando la sustitución mencionada anteriormente, obtenemos el polinomio característico :
rk-una1rk-1-una2rk-2-...-unak=0
Esto representa una ecuación muy conveniente, donde rpuede haber kposibles soluciones (raíces). Además, podemos representar F(n)como una combinación lineal de todos sus predecesores (la prueba de la corrección de esta fórmula no se mostrará para tu salud mental y la mía):
F(norte)=yo=1kdoyoryonorte
  • cisiendo desconocidos los coeficientes que indican cuál rtiene el mayor impacto al calcular el valor deF(n)
Además, si el valor de una raíz ( rpor ejemplo) aparece más de una vez, decimos que rtiene la multiplicidad ( m) mayor que 1.
Esto altera ligeramente la ecuación anterior:
(2)  F(norte)=yo=1shyo(norte)
  • hisiendo el elemento que puede contener ri, que se calcula (teniendo en cuenta la multiplicidad) de acuerdo con la fórmula:
(3)  hyo(norte)=(doyo,0+doyo,1norte+doyo,2norte2+...+doyo,metroyo-1nortemetroyo-1)ryonorte
Enhorabuena, ya que pueden resolver las más esqueleto ecuaciones de recurrencia. ¡Vamos a probarlo!

Teorema de la maestría en informática

¿Recuerdas cuando dije que lo anterior eran sólo los huesos desnudos relaciones de recurrencia? Bueno, ahora veremos un tipo de relación de recurrencia más complicado, pero mucho más útil.
La forma básica de este nuevo tipo de relación de recurrencia es:
T(norte)=unaT(nortesegundo)+donortek
  • de los cuales todas las constantes son iguales o mayores que cero a,b,c,k >= 0yb =/= 0
Esta es una relación de recurrencia mucho más común porque encarna el principio de dividir y vencer(se calcula T(n)calculando un problema mucho más pequeño como T(n/b)).
La fórmula que utilizamos para calcular T(n)en el caso de este tipo de relación de recurrencia es la siguiente:
T(norte)={O(nortelosolsegundouna)para una>segundokO(norteklosol norte)para una=segundokO(nortek)para una<segundok
Debido a que la fórmula anterior es lo suficientemente lógica y porque la prueba no es realmente trivial, le aconsejaría que la recuerde tal como está ... pero si todavía desea ver la prueba, lea el teorema 5.1, prueba 1-2, en este artículo .

Ejemplo: Binary Search

Si tenemos una serie ordenada Ade longitud ny queremos averiguar cuánto tiempo nos llevaría encontrar un elemento específico, llamémoslo, zpor ejemplo. Primero debemos ver el código que usaremos para encontrar dicho elemento mediante la búsqueda binaria:
# leftIndex and rightIndex indicate which part of the original array
# we are currently examining, the initial function call is find(A,z,1,n)
import math  
def find(A, z, leftIndex, rightIndex):  
    # if our search range is narrowed down to one element,
    # we just check if it's equal to z, target being the index of the wanted element
    # A[target]=z
    if leftIndex == rightIndex:
        if A[leftIndex] == z:
            return leftIndex
        else:
            return -1
    else:
        middlePoint = math.ceil((leftIndex + rightIndex) / 2)
        print("{} {} {}".format(leftIndex, rightIndex, middlePoint))
        # because the array is sorted, we know that if z < X[middlePoint],
        # we know it has to be to the left of said element,
        # same goes if z >= X[middlePoint] and we call
        # find(A, z, leftIndex, middlePoint - 1)
        # if z == A[middlePoint]:
        #     return middlePoint
        if z < A[middlePoint]:
            return find(A, z, leftIndex, middlePoint - 1)
        else:  # z >= A[middlePoint]
            # leaving the middle point in this call is intentional
            # because there is no middle point check
            # except when leftIndex==rightIndex
            return find(A, z, middlePoint, rightIndex)

def main():  
    A = [1, 3, 5, 7, 8, 9, 12, 14, 22]
    z = 12
    target = find(A, z, 0, len(A))
    print("Target index: {}".format(target))

if __name__ == "__main__":  
    main()
La parte más intensiva en el tiempo de esta búsqueda es la recursión, esto significa que podemos representar el tiempo que toma el algoritmo de búsqueda binaria para buscar a través de una matriz de longitud nutilizando la siguiente relación de recurrencia:
T(norte)=T(norte2)+1
La 1representación de una operación constante como valor de control (como leftIndex == rightIndex, esta constante no es realmente tan importante teniendo en cuenta que es mucho más pequeño que tanto T(n)T(n\b)).
De la coincidencia de la fórmula básica del teorema maestro con la fórmula de búsqueda binaria que conocemos:
una=1,segundo=2,do=1,k=0 
Usando la fórmula del Teorema Maestro para T (n) obtenemos que:
T(norte)=O(losol norte)Por lo tanto, la búsqueda binaria realmente es más eficiente que la búsqueda lineal estándar.

Ejemplo: Programación Dinámica VS Recursión

Echemos un vistazo final a la secuencia de Fibonacci (la última vez, lo prometo):
Fyosegundoonorteunadodoyo(norte)=Fyosegundoonorteunadodoyo(norte-1)+Fyosegundoonorteunadodoyo(norte-2)
La programación dinámica, como sabemos por mi último artículo, tiene la complejidad del tiempo O(n)porque utiliza la memorización y genera la matriz de forma lineal , sin mirar hacia atrás(construye la matriz desde el principio).
Ahora probemos que es mucho más eficiente usar la Programación Dinámica.

Análisis de complejidad de tiempo de Fibonacci

Digamos que T(n)representa el tiempo que se necesita para calcular el n-thelemento de la secuencia de Fibonacci.
Entonces sabemos que se aplica la siguiente fórmula:
T(norte)=T(norte-1)+T(norte-2)
Primero, necesitamos obtener la forma implícita de la ecuación ( matemática para completar todo en un lado, de modo que el otro lado solo tenga un cero):
T(norte)-T(norte-1)-T(norte-2)=0
Ahora, usemos la sustitución estándar (fórmula (1)):
rnorte-rnorte-1-rnorte-2=0
Para simplificar aún más la ecuación, dividamos ambos lados con rla potencia de la potencia más baja presente en la ecuación (en este caso es n-2):
rnorte-rnorte-1-rnorte-2=0 /rnorte-2rnorte-(norte-2)-rnorte-1-(norte-2)-rnorte-2-(norte-2)=0r2-r1-r0=0r2-r-1=0
Este paso se realiza para que podamos reducir el problema a una ecuación cuadrática .
Usando la fórmula de ecuación cuadrática obtenemos los siguientes valores posibles para r:
r1=1+52,r1=1-52
Ahora, usando la fórmula (2) , determinamos la fórmula básica para Fibonacci(n):
T(norte)=do1r1norte+do2r2norte
Porque sabemos eso Fibonacci(0) = 0Fibonacci(1) = 1, por lo tanto, T(0) = 0T(1) = 1(técnicamente, T(0)T(1)podría ser cualquier cantidad constante de operaciones necesarias para calcular sus valores, pero en realidad no afecta mucho el resultado, así que para simplificar, son 01, simplemente, como Fib(0)Fib(1)), podemos usarlos para resolver la ecuación anterior para C1C2:
T(0)=0=do1r10+do2r20=do1+do2Lo que significa: do1=-do2
Ellos, utilizando T(1):