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

Al diseñar un algoritmo completamente nuevo, se necesita un análisis muy completo de su corrección y eficiencia. Lo último que querrías es tu solución...

Introducción

Al diseñar un algoritmo completamente nuevo, se necesita un análisis muy completo de su corrección y eficiencia.

Lo último que querría es que su solución no sea adecuada para un problema para el que fue diseñado para resolver en primer lugar.

Nota: Como puede ver en la tabla de contenido, esto no es de ninguna manera, forma o formato destinado a la aplicación directa. Es Teoría de las Ciencias de la Computación, y solo está destinado 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 (MI) es una herramienta esencial para probar la declaración que prueba la corrección de un algoritmo. La idea general de MI es probar que un enunciado es verdadero para todo 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 n, llamemos a la regla F(n)
  2. Base de inducción: Demostrar que la regla es válida para un valor inicial, o más bien un punto de partida; esto a menudo se prueba resolviendo la hipótesis de inducción F(n) para n=1 o cualquier valor inicial es apropiado
  3. Paso de inducción: Probar que si sabemos que F(n) es verdadero, podemos dar un paso un paso adelante y asumir que F(n+1) es correcto

Si seguiste estos pasos, ¡ahora tienes el poder de hacer loops! No, de verdad, esto básicamente nos da la capacidad de hacer algo como esto:

1
2
for (i in range(n)):
    T[i] = True

Ejemplo básico

Problema:

Si definimos S(n) como la suma de los primeros n números naturales, por ejemplo S(3) = 3+2+1, pruebe que la siguiente fórmula se puede aplicar a cualquier n :

$$
S(n)=\frac{(n+1)*n}{2}
$$

Tracemos 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 probar que S(1) = 1:

    $$
    S(1)=\frac{(1+1)*1}{2}=\frac{2}{2}=1
    $$

  3. Paso de inducción: En este paso, debemos demostrar que si la fórmula se aplica a S(n), también se aplica a S(n+1) de la siguiente manera:

    $$ S(n+1)=\frac{(n+1+1)*(n+1)}{2}=\frac{(n+2)*(n+1)}{2} $$

Esto se conoce como una implicación (a=>b), lo que significa que tenemos que probar que b es correcta siempre que sepamos que a es correcta.

$$
S(n+1)=S(n)+(n+1)=\frac{(n+1)*n}{2}+(n+1)=\frac{n^2+ n+2n+2}{2}
$$

$$
=\frac{n^2+3n+2}{2}=\frac{(n+2)*(n+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

Q.E.D.

Prueba de corrección

Debido a que el método que estamos usando para probar la corrección de un algoritmo está basado en matemáticas, o más bien basado en funciones, cuanto más se parezca la solución a una función matemática real, más fácil será la prueba.

¿Por qué es esto usted puede pedir? Bueno, la programación imperativa práctica tiene algo llamado 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

1
2
3
def foo(x):
    x = y + 1
    return x

Si te pidiera que me dieras el valor de salida de esta función para x=1, naturalmente dirías:

Bueno, caramba, señor, ¿cómo sabríamos el valor de salida si no sabemos ese maldito valor y?

Verás, ese es exactamente el punto, este programa (imperativo) como cualquier otro tiene un estado, que está definido por una lista de variables y sus valores correspondientes. Solo 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 usa con poca frecuencia, especialmente 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 lo mejor para probar la corrección, recursión. La recursividad es muy fácil para la interpretación matemática porque es equivalente a las relaciones de recurrencia (más información sobre las relaciones de recurrencia en los siguientes segmentos).

Ejemplo de recursividad

1
2
3
4
5
def factorial(n):
    if (n==0):
        return 1
    else:
        return n*factorial(n-1)

Convertido a forma de recurrencia:

$$
Factoriales(n)=n*Factoriales(n-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 bajo control todo el tiempo, en caso de que una se vuelva loca.

Además, los bucles plantean un problema porque hay muy pocos equivalentes matemáticos para ellos. Esto significa que tenemos que incorporar inducción matemática en nuestro Modelo de análisis de algoritmos, porque es el único método que conocemos que puede incriminar iterativamente 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 ocurren en dicho ciclo porque necesitamos vincularlas todas al conjunto de valores que queremos que sean.

Selección invariable de bucle

Un bucle invariante puede ser tan complicado y simple como quieras que sea. Sin embargo, el punto es que debe construirse para parecerse lo más posible al problema en cuestión.

Por ejemplo, siempre puedo decir que lo siguiente es un bucle invariante:

$$(x > y) \vee (x < y) \vee (x==y)$$

Pero, al usar 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 se clasifica técnicamente como invariante de bucle es que cumple con los 3 requisitos:

  1. La fórmula es correcta ANTES de la ejecución del ciclo
  2. La fórmula es correcta DURANTE la ejecución del bucle, incluidos todos los pasos intermedios
  3. La fórmula es correcta DESPUÉS de la ejecución del ciclo

Ejemplo:

Echemos un vistazo al siguiente código y determinemos la invariante de bucle óptima:

1
2
3
4
5
6
7
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 y lo almacena en z, esto significa que z = x*y. Otra condición que sabemos que siempre será cierta es n <= x (más información sobre los iguales en el ejemplo). Pero, ¿estos dos realmente solo se aplican después de que el programa haya terminado de computar?

El valor n es esencialmente el número de bucles que ya se ejecutaron, pero también es el número de veces que el valor z se ha incrementado en y.

Esto significa que tanto z = n*y como n <= x podrían aplicarse en todo momento. Lo único que queda por hacer es verificar si realmente se pueden usar como un bucle invariante.

Ejemplo de bucle invariable: prueba por inducción

Primero, necesitamos probar que el bucle invariante es verdadero antes de entrar en el bucle (que es el equivalente a probar y la base de la inducción):

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
# <=> - 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, necesitamos verificar si el invariante es verdadero después de cada ciclo terminado (excluyendo el último), lo hacemos observando la transición de z,n a z',n'', donde z’yn’son los valores dez yn` después de que se haya ejecutado el siguiente bucle.

Por lo tanto, z' = z+y y n' = n+1. Básicamente, necesitamos probar que si sabemos que el invariante es cierto para z y n, también es cierto para z`` y n’`:

$$z^{\prime} = z + y z = n \ast y n^{\prime} = n + 1\text{Si\ el\ siguiente\ es\ válido,\ el\ invariable\ es\ válido:~} z^{\prime} = n^{\prime} \ast y? z^{\prime} = (n + 1) \ast y = n \ast y + y = z + y$$

En tercer lugar, debemos verificar si el invariante es verdadero después de la última iteración del ciclo. Como n es un número entero y sabemos que n-1<x es verdadero, pero n<x es 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 lo tanto sabemos que z = x*y.

Q.E.D.

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) depende de sus valores anterior y posterior, como f(n-1) y f(n+1).

El ejemplo más simple de este tipo de función sería la secuencia de Fibonacci:

$$
Fibonacci(n)=Fibonacci(n-1)+Fibonacci(n-2)
$$

Es posible que reconozcas 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á:

  1. Relaciones de recurrencia lineales homogéneas
  2. Relaciones de recurrencia no lineales: caso de uso del teorema maestro

Resolución de relaciones de recurrencia lineal homogénea

Al leer el título anterior, es posible que se esté preguntando

"¡¿Qué diablos es este galimatías matemático?!?!"

Bueno, primero echemos un vistazo a la fórmula general:

$$F(n) = a_{1}F(n - 1) + a_{2}F(n - 2) + … + a_{k}F(n - k).$$

Ahora dividamos la definición en partes del tamaño de un byte (juego de palabras):

  1. Lineal se refiere al hecho de que los elementos de la función F(algo) están elevados a la primera potencia
  2. Homogéneo se refiere al hecho de que todas las duplas de elementos a*F(algo) son uniformes, lo que significa que una constante no puede estar presente (a*F(algo) = const no puede suceder)

Estas relaciones de recurrencia se resuelven utilizando la siguiente sustitución:

$$
(1) \ \ F(n) = r^n
$$

  • r es un número (complejo) convenientemente elegido

Estaré enumerando fórmulas útiles para que pueda hacer referencia a ellas más fácilmente en el ejemplo

Estamos usando un número complejo porque necesitamos una variable que pueda recorrer una cantidad de valores, de los cuales todos pueden (pero no tienen que) ser diferentes. Todos los cuales son raíces (soluciones) de la ecuación anterior.

Aclaración:

  • Los números complejos tienen la forma de x = a + bi, siendo x el número complejo, a y b siendo números enteros simples, y i siendo la constante:
    $$
    \begin{alinear}
    i=\raíz cuadrada{-1}
    \end{alinear}
    $$
  • como puedes notar i es un número muy particular, lo que significa que en realidad tiene un ciclo:
    $$
    \begin{alinear}
    i=\raíz cuadrada{-1}\,
    i^2=-1\,
    i^3=-1*\sqrt{-1}\,
    i^4=1\,
    i^5=i,
    \end{alinear}
    $$
  • esto significa que i tiene un ciclo de longitud = 5
  • se pueden personalizar otros números complejos para que tengan 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:

$$r^{k} - a_{1}r^{k - 1} - a_{2}r^{k - 2} - … - a_{k} = 0$$

Esto representa una ecuación muy conveniente, donde r puede tener k posibles 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á por el bien de su cordura y la mía):

$$F(n) = \sum\limits_{i = 1}^{k}c_{i}r_{i}^{n}$$

  • ci siendo coeficientes desconocidos que indican qué r tiene el mayor impacto al calcular el valor de F(n)

Además, si el valor de una raíz (r por ejemplo) aparece más de una vez, decimos que r tiene la multiplicidad (m) mayor que 1.

Esto altera ligeramente la ecuación anterior:

$$(2)\ \ F(n) = \sum\limits_{i = 1}^{s}h_{i}(n)$$

  • siendo hi el elemento puede contener ri, que se calcula (teniendo en cuenta la multiplicidad) según la fórmula:

$$(3)\ \ h_{i}(n) = (C_{i,0} + C_{i,1}n + C_{i,2}n^{2} + … + C_{i ,mi - 1}n^{m_{i} - 1})r_{i}^{n}$$

Felicitaciones, ahora podemos resolver las ecuaciones de recurrencia más básicas. ¡Vamos a probarlo!

Teorema del maestro en ciencias de la computación {#teorema del maestro en ciencias de la computación}

¿Recuerdas cuando dije que lo anterior eran solo las relaciones de recurrencia básica? 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(n) = aT(\frac{n}{b})+ cn^k
$$

  • de las cuales todas las constantes son iguales o mayores que ceroa,b,c,k >= 0 y b =/= 0

Esta es una relación de recurrencia mucho más común porque encarna el principio de divide y vencerás (calcula T(n) calculando un problema mucho más pequeño como T(n/b)) .

La fórmula que usamos para calcular T(n) en el caso de este tipo de relación de recurrencia es la siguiente:

$$T(n) = \left{ \begin{matriz} {O(n^{log_{b}a})} & {\text{for~}a > b^{k}} \ {O(n^{k}log\ n)} & {\text{for~}a = b^{k}} \ {O(n^{k})} & {\text{para~}a < b^{k}} \ \end{matriz} \right.$$

Debido a que la fórmula anterior es suficientemente lógica, y debido a que la prueba no es realmente trivial, le aconsejo que la recuerde como está... pero si aún quiere ver la prueba, lea el Teorema 5.1 prueba 1-2 en Este artículo.

Ejemplo: búsqueda binaria

Si tenemos una matriz ordenada A de longitud n y queremos averiguar cuánto tiempo nos llevaría encontrar un elemento específico, llamémoslo z por ejemplo. Primero debemos echar un vistazo al código que usaremos para encontrar dicho elemento usando la búsqueda binaria:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
# 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 que requiere más tiempo de esta búsqueda es la recursión, esto significa que podemos representar el tiempo que le toma al algoritmo de búsqueda binaria buscar a través de una matriz de longitud n usando la siguiente relación de recurrencia:

$$
T(n)=T(\frac{n}{2})+1
$$

El 1 representa una operación constante como la comprobación de valores (como leftIndex == rightIndex, esta constante no es realmente tan importante teniendo en cuenta que es mucho más pequeña que T(n) y T(n) \b)).

Al hacer coincidir la fórmula básica del teorema maestro con la fórmula de búsqueda binaria, sabemos:

$$
a=1,b=2,c=1,k=0\\ $$

Usando la fórmula del teorema maestro para T(n) obtenemos que:

$$
T(n) = O(log \ n)
$$
Entonces, la búsqueda binaria es realmente más eficiente que la búsqueda lineal estándar.

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

Echemos un último vistazo a la secuencia de Fibonacci (la última vez, lo prometo):

$$
Fibonacci(n)=Fibonacci(n-1)+Fibonacci(n-2)
$$

La programación dinámica, como sabemos por mi último artículo tiene la complejidad temporal de O(n) porque utiliza la memorización y genera el arreglo linealmente, sin mirar -backs (construye la matriz desde cero).

Ahora demostremos que es mucho más eficiente usar la Programación Dinámica.

Análisis de complejidad de tiempo de Fibonacci {#análisis de complejidad de tiempo de fibonacci}

Digamos que T(n) representa el tiempo que se necesita para calcular el elemento n-th de la secuencia de Fibonacci.

Entonces sabemos que se aplica la siguiente fórmula:

$$
T(n)=T(n-1)+T(n-2)
$$

Primero, necesitamos obtener la forma implícita de la ecuación (charla matemática para colocar todo en un lado, de modo que el otro lado solo tenga un cero):

$$
T(n)-T(n-1)-T(n-2)=0
$$

Ahora, usemos la sustitución estándar (fórmula (1)):

$$
r^n-r^{n-1}-r^{n-2}=0
$$

Para simplificar aún más la ecuación, dividamos ambos lados con r elevado a la potencia más baja presente en la ecuación (en este caso es n-2):

$$r^{n} - r^{n - 1} - r^{n - 2} = 0\ /r^{n - 2} r^{n - (n - 2)} - r^{n - 1 - (n - 2)} - r^{n - 2 - (n - 2)} = 0 r^{2} - r^{1} - r^{0} = 0 r^{2} - r - 1 = 0$$

Este paso se realiza para que podamos reducir el problema a una ecuación cuadrática.

Usando la fórmula ecuación cuadrática obtenemos los siguientes valores posibles para r:

$$r_{1} = \frac{1 + \sqrt{5}}{2},r_{1} = \frac{1 - \sqrt{5}}{2}$$

Ahora, usando la fórmula (2), determinamos la fórmula básica para Fibonacci(n):

$$T(n) = C_{1} \ast r_{1}^{n} + C_{2} \ast r_{2}^{n}$$

Porque sabemos que Fibonacci(0) = 0 y Fibonacci(1) = 1, por lo tanto T(0) = 0 y T(1) = 1 (técnicamente, T(0) y T(1) podría ser cualquier número constante de operaciones necesarias para calcular sus valores, pero en realidad no afecta tanto el resultado, por lo que, en aras de la simplicidad, son 0 y 1 , al igual que Fib(0) y Fib(1)), podemos usarlos para resolver la ecuación anterior para C1 y C2:

$$T(0) = 0 = C_{1} \ast r_{1}^{0} + C_{2} \ast r_{2}^{0} = C_{1} + C_{2}\text {Que\ significa:~}C_{1} = - C_{2}$$

Ellos, usando T(1):

$$T(1) = 1 = C_{1} \ast r_{1}^{1} + C_{2} \ast r_{2}^{1} = C_{1} \ast r_{1} + C_{2} \ast r_{2}\text{Porque\ conocemos\ los\ valores\ de\ r1\ y\ r2,\ y\ los\ siguientes:~}C_{1} = - C_{2}\text{Podemos\ sustituir\los\ en\ la\ ecuación\ principal:~}\ 1 = - C_{2} \ast \frac{1 + \sqrt{5}}{2} + C_{2} \ast \frac{1 - \sqrt{5}}{2}$$

Cuando resolvemos la ecuación anterior para C2 obtenemos:

$$C_{1} = - \frac{1}{\sqrt{5}}\ C_{2} = \frac{1}{\sqrt{5}}$$

Lo que significa que ahora tenemos la solución final a la relación de recurrencia:

$$T(n) = - \frac{1}{\sqrt{5}} \ast (\frac{1 + \sqrt{5}}{2})^{n} + \frac{1}{\ sqrt{5}} \ast (\frac{1 - \sqrt{5}}{2})^{n}$$

Deducción de la complejidad del algoritmo a partir de la relación de recurrencia {#deducción de la complejidad del algoritmo a partir de la relación de recurrencia}

Porque T(n) representa el número de pasos que un programa necesita para calcular el elemento n-th en la secuencia, siendo n también el valor de entrada, o más comúnmente, el tamaño de entrada en bits. La solución anterior nos dice que el algoritmo que estamos usando tiene una complejidad exponencial.

Dato curioso:

El método anterior también se puede usar para encontrar la fórmula para calcular el valor definido para el elemento n-ésimo en la secuencia de Fibonacci (las funciones representarían el valor del n-ésimo elemento en lugar de cuántas operaciones necesita para calcularlos)

Debido a que O(a^n) (recursivo - complejidad de tiempo exponencial) es un orden de magnitud mucho mayor que O(n) (programación dinámica - complejidad de tiempo lineal), ahora tenemos una respuesta definitiva por qué la programación dinámica es superior en tiempo a la recursividad tradicional.

Conclusión

Sé que este artículo puede parecer un poco redundante. Pero las pruebas de corrección y eficiencia son las piedras angulares de la teoría informática moderna y la razón principal por la que este campo sigue avanzando a un ritmo acelerado.

La informática no es lo mismo que la programación, es solo uno de sus muchos casos de uso. Y creo que sería bueno que la gente entendiera mejor lo que realmente es, al menos únicamente a través de este artículo.