Demostración matemática de la corrección y eficiencia del algoritmo

 

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 en primer lugar.

En este artículo hablaremos de los siguientes temas:

• Inducción matemática
• Prueba de corrección
• Invariantes de bucle
• Análisis de eficiencia: relaciones de recurrencia
• Relaciones de recurrencia: lineal y no lineal
• Resolución de relaciones de recurrencia lineal homogénea
• Teorema de Maestría en Ciencias de la Computación
• Ejemplo: programación dinámica
• Ejemplo: búsqueda binaria
• Conclusión

DESCARGO DE RESPONSABILIDAD : como puede ver en los títulos de las secciones, esto no es de ninguna manera, forma o forma destinada a una aplicación directa. Es Teoría de las Ciencias 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 (MI) es una herramienta esencial para probar la afirmación que prueba la exactitud de un algoritmo. La idea general de MI es probar que un enunciado es verdadero para cada número natural n.

¿Qué significa esto realmente?

Esto significa que tenemos que seguir 3 pasos:

• Hipótesis de inducción : Defina la regla que queremos probar para cada n, llamemos a la reglaF(n)
• 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=1o cualquier valor inicial que sea apropiado
• Paso de inducción : demostrar que si sabemos que 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, de verdad, esto básicamente nos da la posibilidad 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, demuestre que la siguiente fórmula se puede aplicar a cualquiera n:

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

Sigamos nuestros pasos:

• Hipótesis de inducción : S(n)definida con la fórmula anterior
• Base de inducción : En este paso tenemos que demostrar que S(1) = 1:

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

• 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)lo siguiente:

  $$
  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 simplemente significa que tenemos que demostrar que bes correcto siempre que sepamos que aes correcto.

$$
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 la suma de forma recursiva. 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 estamos usando para probar la corrección de un algoritmo se basa en matemáticas, o más bien en funciones , 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, puedes preguntar? Bueno, la programación imperativa práctica tiene esto llamado estado , esto significa que la salida de un programa depende de 3 cosas:

• Su secuencia de instrucciones
• Sus valores de entrada
• su estado , o más bien, todas las variables previamente inicializadas que pueden cambiar de alguna manera el valor de salida

Ejemplo de estado de programa

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 conocemos ese maldito yvalor?

Verá, 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 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 siguiente mejor opción para demostrar la corrección: la recursividad . La recursividad 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 recursividad

def factorial(n):
    if (n==0):
        return 1
    else:
        return n*factorial(n-1)

Convertido a forma de recurrencia:

$$
Factorial (n) = n * Factorial (n-1)
$$

Invariantes de bucle

Todo esto suena bien, pero hasta ahora, no hemos dicho nada sobre la representación de bucles y estados del programa 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 la inducción matemática en nuestro modelo de análisis de algoritmos, porque es el único método que conocemos que puede incriminar valores iterativamente en matemáticas, como en el código real.

La forma más sencilla de resolver ambos problemas (con inducción matemática) son las invariantes de bucle :

Un ciclo invariante es una fórmula lógica o simplemente un conjunto de reglas, eso es cierto antes, durante y después del ciclo 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 de bucle invariante

Un ciclo invariante puede ser tan complicado y simple como usted quiera. Sin embargo, el punto es que debe construirse para que se asemeje lo más posible al problema en cuestión.

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

(
x
>
y
)
∨
(
x
<
y
)
∨
(
x
==
y
)

Pero, al usar una tautología (una fórmula lógica que siempre es correcta) como un ciclo invariante, realmente no logramos nada, la única razón por la que técnicamente se clasifica como un ciclo invariante es que cumple con los 3 requisitos:

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

Ejemplo:

Echemos un vistazo al siguiente código y determinemos el invariante de ciclo óptimo:

x = 10
y = 4
z = 0
n = 0
while(n < x):
    z = z+y
    n = n+1

Lógicamente, este código simplemente 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 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 se ha incrementado y.

Entonces esto significa que ambos z = n*yy n <= xpueden aplicarse en todo momento . Lo único que queda por hacer es comprobar si realmente se pueden utilizar como invariantes de bucle.

Ejemplo de bucle invariante: prueba por inducción

Primero, necesitamos demostrar que el invariante del ciclo es verdadero antes de entrar en el ciclo (que es el equivalente de la base de prueba y 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 terminado (excluyendo el último), lo hacemos observando la transición desde z,na z',n', dónde z'y n'son los valores de zy ndespués de que se haya ejecutado el siguiente ciclo.

Por tanto, z' = z+yy n' = n+1. Necesitamos demostrar esencialmente que si sabemos que el invariante es verdadero para zy n, también es cierto para z'y n':

con
′

=
z
+
y

z
=
n
∗
y

n
′

=
n
+
1

Si lo siguiente es válido, el invariante es válido: 

con
′

=

n
′

∗
y
?

Te puede interesar:Git: eliminar sucursales de forma local y remota

con
′

=
(
n
+
1
)
∗
y
=
n
∗
y
+
y
=
z
+
y

En tercer lugar, debemos verificar si el invariante es verdadero después de la última iteración del ciclo. Porque nes un número entero y sabemos que n-1<xes verdadero, pero n<xfalso, eso significa que n=x(esta es la razón por la que el invariante debe 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)depende de sus valores anteriores y posteriores, 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 reconozca este concepto en 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á:

• Relaciones lineales de recurrencia homogénea
• 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 pregunte

«¡¿Qué en el nombre de Dios es este galimatías matemático?!?!»

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

F
(
n
)
=

un
1

F
(
n
–
1
)
+

un
2

F
(
n
–
2
)
+
.
.
.
+

a
k

F
(
n
–
k
)
.

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

• Lineal se refiere al hecho de que los elementos de la función F(something)están a la primera potencia
• Homogéneo se refiere al hecho de que todos los duplets 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 mediante la siguiente sustitución:

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

• 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 usando un número complejo porque necesitamos una variable que pueda recorrer varios valores, de los cuales todos pueden (pero no es necesario) ser diferentes. Todos los cuales son roots(soluciones) a la ecuación anterior.

Aclaración:

• complexlos números tienen una forma de x = a + bi, xsiendo el número complejo, ay bsiendo enteros simples, y isiendo la constante:
  $$
  begin {align}
  i = sqrt {-1}
  end {align}
  $$

• como puede notar, ies un número muy particular, lo que significa que en realidad tiene un ciclo :
  $$
  begin {align}
  i = sqrt {-1},
  i ^ 2 = -1,
  i ^ 3 = -1 * sqrt {-1} ,
  i ^ 4 = 1,
  i ^ 5 = i,
  end {align}
  $$

• este medio itiene un ciclo delength = 5

• otros números complejos se pueden personalizar 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 :

r
k

−

un
1

r

k
–
1

−

un
2

r

k
–
2

−
.
.
.
−

a
k

=
0

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

F
(
n
)
=

∑

i
=
1

a

c
yo

r

yo

norte

• cisiendo coeficientes desconocidos que indican cuál rtiene mayor impacto a la hora de 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
(
n
)
=

∑

Te puede interesar:Git: volver a una confirmación anterior

i
=
1

s

h
i

(
n
)

• hisiendo el elemento que puede contener ri, que se calcula (teniendo en cuenta la multiplicidad) de acuerdo con la fórmula:

(
3
)

h
i

(
n
)
=
(

C

yo
,
0

+

C

yo
,
1

n
+

C

yo
,
2

n
2

+
.
.
.
+

C

i
,
m
i
−
1

norte

m
i

−
1

)

r
i
n

Felicitaciones, ahora podemos resolver las ecuaciones de recurrencia más básicas. ¡Probémoslo!

Teorema de Maestría en Ciencias de la Computación

¿ReStrings cuando dije que lo anterior fueron sólo los huesos desnudos recurrencia relaciones? 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 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 incorpora 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
)
=

{

O
(

norte

l
o

g
b

a

)

para
un
>

b
k

O
(

norte

a

l
o
g

n
)

para
a
=

b
k

O
(

norte

a

)

para
un
<

b
k

Te puede interesar:Git: cambiar el nombre de una sucursal local y remota

Debido a que la fórmula anterior es lo suficientemente lógica , y debido a que la prueba no es realmente trivial, le aconsejaría que la recuerde tal como está … pero si aún desea ver la prueba, lea la prueba 1-2 del teorema 5.1 en este artículo .

Ejemplo: búsqueda binaria

Si tenemos una matriz ordenada Ade longitud ny queremos saber cuánto tiempo nos tomaría encontrar un elemento específico, llamémoslo zpor ejemplo. Primero debemos echar un vistazo al código que usaremos para encontrar dicho elemento usando 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 tiempo de esta búsqueda es la recursividad, 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 nusando la siguiente relación de recurrencia:

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

La 1representación de una operación constante como la verificación de valor (como leftIndex == rightIndex, esta constante no es realmente tan importante considerando que es mucho más pequeña que ambos T(n)y T(nb)).

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 recursividad

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 de tiempo O(n)porque usa la memorización y genera la matriz de forma lineal, sin retrocesos (construye la matriz desde cero).

Ahora demostremos que es mucho más eficiente usar la programación dinámica.

Análisis de complejidad del 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 (n) = T (n-1) + T (n-2)
$$

Primero, necesitamos obtener la forma implícita de la ecuación (las matemáticas hablan de 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 ^ nr ^ {n-1} -r ^ {n-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):

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

Te puede interesar:Git: buscar una rama remota

Este paso se hace para que podamos resumir el problema en una ecuación cuadrática .

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

r
1

=

1
+

5

2

,

r
1

=

1
−

5

2

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

T
(
n
)
=

C
1

∗

r
1
n

+

C
2

∗

r
2
n

Porque sabemos eso Fibonacci(0) = 0y Fibonacci(1) = 1, por lo tanto, T(0) = 0y 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 0y 1, solo como Fib(0)y Fib(1)), podemos usarlos para resolver la ecuación anterior para C1y C2:

T
(
0
)
=
0
=

C
1

∗

r
1
0

+

C
2

∗

r
2
0

=

C
1

+

C
2

Lo que significa: 

C
1

=
−

C
2

Ellos, usando T(1):

T
(
1
)
=
1
=

C
1

∗

r
1
1

+

C
2

∗

r
2
1

=

C
1

∗

r
1

+

Te puede interesar:Git: revertir una fusión

C
2

∗

r
2

Porque conocemos los valores de `r1` y` r2`, y lo siguiente: 

C
1

=
−

C
2

Podemos sustituirlos en la ecuación principal: 

1
=
−

C
2

∗

1
+

5

2

+

C
2

∗

1
−

5

2

Cuando resolvemos la ecuación anterior C2obtenemos:

C
1

=
−

1

5

C
2

=

1

5

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

T
(
n
)
=
–

1

5

∗
(

1
+

5

2

)
n

+

1

5

∗
(

1
−

5

2

)
n

Deducir la complejidad del algoritmo de la relación de recurrencia

Porque T(n)representa el número de pasos que necesita un programa para calcular el n-thelemento en la secuencia, nsiendo 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.

Hecho de la diversión:

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

Debido a que O(a^n)(recursiva – 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 el 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 moderna de la informática y la principal razón 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.

 

Te puede interesar:Git: cambiar la URL del repositorio remoto