10.2. Invariantes de ciclo

Los invariantes se refieren a estados o situaciones que no cambian dentro de un contex-to o porción de código. Hay invariantes de ciclo, que son los que veremos a continuación, e invariantes de estado, que se verán más adelante.

El invariante de ciclo permite conocer cómo llegar desde las precondiciones hasta las post-condiciones. El invariante de ciclo es, entonces, una aseveración que debe ser verdadera al comienzo de cada iteración.

Por ejemplo, si el problema es ir desde el punto A al punto B, las precondiciones dicen que estamos parados en A y las postcondiciones que estamos parados en B, un invariante podría ser "estamos en algún punto entre A y B, en el punto más cercano a B que estuvimos hasta ahora.".

Más específicamente, si analizamos el ciclo para buscar el máximo en una lista desordenada, la precondición es que la lista contiene elementos que son comparables y la postcondición es que se devuelve el elemento máximo de la lista.

def maximo(lista):
    "Devuelve el elemento merximo de la lista o None si estar vacía."
    if not len(lista):
        return None
    max_elem = lista[0]
    for elemento in lista:
        if elemento > max_elem:
            max_elem = elemento
    return max_elem

En este caso, el invariante del ciclo es que max_elem contiene el valor máximo de la porción de lista analizada.

Los invariantes son de gran importancia al momento de demostrar que un algoritmo funciona, pero aún cuando no hagamos una demostración formal es muy útil tener los invariantes a la vista, ya que de esta forma es más fácil entender cómo funciona un algoritmo y encontrar posibles errores.

Los invariantes, además, son útiles a la hora de determinar las condiciones iniciales de un algoritmo, ya que también deben cumplirse para ese caso. Por ejemplo, consideremos el algoritmo para obtener la potencia n de un número.

def potencia(b, n):
    "Devuelve la potencia n del número b, con n entero mayor que 0."
    p = 1
    for i in range(n):
        p *= b
    return p

En este caso, el invariante del ciclo es que la variable p contiene el valor de la potencia correspondiente a esa iteración. Teniendo en cuenta esta condición, es fácil ver que p debe comenzar el ciclo con un valor de 1, ya que ese es el valor correspondiente a p^0.

De la misma manera, si la operación que se quiere realizar es sumar todos los elementos de una lista, el invariante será que una variable suma contenga la suma de todos los elementos ya recorridos, por lo que es claro que este invariante debe ser 0 cuando aún no se haya recorrido ningún elemento.

def suma(lista):
    "Devuelve la suma de todos los elementos de la lista."
    suma = 0
    for elemento in lista:
        suma += elemento
    return suma

10.2.1. Comprobación de invariantes desde el código

Cuando la comprobación necesaria para saber si seguimos "en camino" es simple, se la puede tener directamente dentro del código. Evitando seguir avanzando con el algoritmo si se produjo un error crítico.

Por ejemplo, en una búsqueda binaria, el elemento a buscar debe ser mayor que el elemento inicial y menor que el elemento final, de no ser así, no tiene sentido continuar con la búsqueda. Es posible, entonces, agregar una instrucción que compruebe esta condición y de no ser cierta realice alguna acción para indicar el error, por ejemplo, utilizando la instrucción assert, vista anteriormente.