54. Resumen de métodos computacionales¶

54.1. Conjeturar y comprobar¶

Los métodos de guess and check engloban toda una familia de métodos, que incluyen métodos de enumeración exhaustiva, bisección, algunos métodos estocásticos, algoritmos genéticos, ...

Encontrar la raiz cuadrada de un número natural

def raiz_cuadrada(x):
    g = primera_conjetura(x)
    while True:
        if suficientemente_proximos(g*g, x):
            return g
        g = nueva_conjetura(x,g)

(g + x/g)/2

54.2. Enumeración exhaustiva¶

La enumeración exhaustiva o fuerza bruta se utiliza cuando el número de casos a probar no es prohibitivamente alto y la evaluación de cada caso es sencilla. Por ejemplo:

Encontrar la raiz cúbica de un número natural.

def raiz_cubica(n):
    i = 1
    while i**3 < n:
        i = i + 1
    if i**3 == n:
        return i
    return False

54.3. Búsqueda por bisección¶

La búsqueda por bisección se utiliza cuando las posibles soluciones están totalmente ordenadas y se puede determinar cuál es la posible solución que se encuentra entre dos dadas. Por ejemplo:

Encontrar la raiz cúbica de un número real con una precisión dada

def raiz_cubica(x, epsilon):
    low = 0.0
    high = max(1.0, x)
    r = (high + low)/2.0
    while abs(r**3 - x) >= epsilon:
        if r**3 < x: low = r
        else: high = r
        r = (high + low)/2.0
    return r

54.4. Método de Newton-Raphson¶

Para el problema particular de encontrar las raizes de un polinomio \(p(x) = 0\) el mátodo de Newton Raphson establece un método que converge más rápidamente que la búsqueda por bisección. Se basa en esl siguiente teorema:

Sea :math:`p(x)` un polinomio en :math:`x`. Sea :math:`g` conjetura que aproxima una raiz, es decir :math:`p(g) simeq 0`. Entonces :math:`g - p(g)/p’(g)` es mejor conjetura.

Por ejemplo:

Encontrar la raiz cúbica de un número real con una precisión dada

def raiz_cubica(k, epsilon):
    x = k/2.0
    while abs(x**3 - k) >= epsilon:
        x -= (x**3 - k)/(3*x**2)
    return x

54.5. Divide y vencerás¶

Divide y vencerás es un principio general para resolución de problemas que pueden ser descompuestos en problemas más pequeños. Debe cumplir un requisito:

• Subestructura óptima. La solución del problema puede componerse a partir de soluciones a problemas más pequeños

Por ejemplo:

Encontrar la potencia n-sima de un número real

def pot(x, n):
  if n == 1: return x
  if n % 2 == 0:
    y = pot(x, n//2)
    return y*y
  else:
    y = pot(x, (n-1)//2)
    return y*y*x

54.6. Programación dinámica¶

Cuando la solución a un problema exige rehacer repetidamente los mismos cálculos es posible reducir el trabajo aplicando memoization (guardando los valores ya calculados). Deben cumplirse dos requisitos:

• Subestructura óptima. La solución del problema puede componerse a partir de las soluciones a problemas más pequeños
• Subproblemas solapados. Los problemas más pequeños son frecuentemente repetidos.

Por ejemplo:

Calcular el término n-simo de la sucesión de Fibonacci

def fib(n, mem = {}):
    if n == 0 or n == 1:
        return 1
    try:
        return mem[n]
    except KeyError:
        res = fib(n-1, mem) + fib(n-2, mem)
        mem[n] = res
        return res

54.7. Poda del espacio de búsqueda¶

En algunos casos la búsqueda exhaustiva no es posible por existir un número excesivo de posibles soluciones. En esos casos pueden utilizarse técnicas que reducen el espacio de búsqueda.

Una técnica muy efectiva es la propagación de restricciones. Se trata de determinar restricciones de la solución final y propagarlas en los subproblemas para obtener nuevas restricciones en la solución final. Por ejemplo, en la solución al Sudoku:

class Restricciones(object):
    def _filtrar(self):
        while self._nuevos_fijos:
            self._nuevos_fijos = False
            self._filtrarFilas()
            self._filtrarColumnas()
            self._filtrarBloques()
    #...