Optimización de Algoritmos con Programación Dinámica en Python

Curso de Estadística Computacional con Python

Contenido del curso

Introducción

1
Programación Dinámica y Estocástica: Optimización y Modelado de Datos
01:56 min

Programación Dinámica

Caminos Aleatorios

Programas Estocásticos

Simulaciones de Montecarlo

Muestreo e Intervalos de Confianza

Datos Experimentales

Conclusiones

24
Optimización de Programas con Programación Dinámica y Simulaciones
02:54 min

Tomar examen

Cursos Empresas Blog Live Conf Eventos Precios

0:0013:02

Optimización de Algoritmos con Programación Dinámica en Python

Curso de Estadística Computacional con Python

Clase 3 de 24

Clase 3 / 24

Recursos

¿Qué es la Programación Dinámica?

La programación dinámica es una metodología de optimización que ahorra tiempo al intercambiar espacio. Utiliza la memorización para evitar cálculos repetidos al guardar los resultados de subproblemas que se pueden reutilizar. Esto es esencial en problemas donde hay muchas subestructuras comunes, como es el caso de la secuencia de Fibonacci.

¿Cómo se implementa la secuencia de Fibonacci de forma recursiva?

A pesar de ser sencilla de implementar, la solución recursiva a la secuencia de Fibonacci es ineficiente debido al cálculo repetido de los mismos subproblemas. El algoritmo recursivo es el siguiente:

def fibonacci_recursivo(n):
    if n == 0 or n == 1:
        return 1
    else:
        return fibonacci_recursivo(n-1) + fibonacci_recursivo(n-2)

En este enfoque, calcular el Fibonacci de un número grande, como 50, puede ser extremadamente lento. Esto se debe al número exponencial de subproblemas solapados que requieren cálculo.

¿Cómo optimizar la secuencia de Fibonacci usando memorización?

Para optimizar el algoritmo, introducimos la técnica de memorización con un diccionario que almacena los resultados ya calculados:

def fibonacci_dinamico(n, memo = {}):
    if n == 0 or n == 1:
        return 1
    if n in memo:
        return memo[n]
    memo[n] = fibonacci_dinamico(n-1, memo) + fibonacci_dinamico(n-2, memo)
    return memo[n]

Esta solución es significativamente más rápida, porque una vez que un valor de Fibonacci está calculado, no se recalcula.

¿Cómo empezar a usar la función optimizada?

Podemos probar este enfoque en nuestra terminal después de implementar el código:

if __name__ == '__main__':
    n = int(input("Escoge un número: "))
    print(f"Fibonacci de {n} es {fibonacci_dinamico(n)}")

Al correr este script, se podrá calcular rápidamente Fibonacci para números tan grandes como 10,000, siempre que se ajuste la recursión máxima de Python, como se muestra a continuación:

import sys
sys.setrecursionlimit(10002)

Esto asegura que nuestra función pueda manejar la profundidad de llamada necesaria para valores grandes.

Reflexiones sobre el uso de programación dinámica

La programación dinámica es increíblemente poderosa para problemas donde hay solapamiento de subproblemas. Sin embargo, su aplicación debe ser cuidadosa, ya que en problemas sin solapamiento este enfoque no resultaría en optimización alguna; solamente se crearían diccionarios infinitamente grandes sin beneficios perceptibles.

¡Exploren, experimenten y compartan sus hallazgos en cómo la programación dinámica puede aplicarse a otros problemas! Vuestros aportes pueden enriquecer la comunidad de aprendizaje.

Julio Cardenas

Hace 6 años

Hice la siguiente locura para el fibonacci recursivo:

Modifique la funcion para que mostrara calculando fibonacci de n

llame el programa dandole una entrada desde archivo y sacando los resultados a otro archivo, se cuentan las lineas y se sabe cuantas recursiones hizo.

fibonacci de 20:

~/cursoEstocastica $ echo 20 > numero20
 ~/cursoEstocastica $ /bin/python3 optimizacion1_fibonacci.py <numero20 >fr20.txt 

~/prueba fibonacci $ tail -n3 fr20.txt
calculando fibonacci de 1
calculando fibonacci de 0
10946

~/prueba_fibonacci $ wc -l fr20.txt
21892

fibonacci de 20 es 10,946 iteraciones: 21,891

Ahora para n = 30

~/cursoEstocastica $ echo 30 > numero30
 ~/cursoEstocastica $ /bin/python3 optimizacion1_fibonacci.py <numero30 >fr30.txt
  
tail -n3 fr30.txt
calculando fibonacci de 1
calculando fibonacci de 0
1346269

~/prueba_fibonacci $ wc -l fr30.txt
2692538

fibonacci de 30 es 1,346,269 iteraciones: 2,692,537

ahora para n=40

~/cursoEstocastica $ echo 40 > numero40
~/cursoEstocastica $ /bin/python3 optimizacion1_fibonacci.py <numero40 >fr40.txt 

tail -n3 fr40.txt
calculando fibonacci de 1
calculando fibonacci de 0
165580141

~/prueba_fibonacci $ wc -l fr40.txt
331160282

fibonacci de 40 es 165,580,141 iteraciones: 331,160,282

La locura es que casi acabo con mi disco duro:

~/prueba fibonacci $ ls -l
total 8480784
-rw-rw-r-- 1 julio julio     569422 jun 23 18:40 fr20.txt
-rw-rw-r-- 1 julio julio   70034644 jun 23 18:42 fr30.txt
-rw-rw-r-- 1 julio julio 8613691911 jun 23 18:49 fr40.txt
-rw-rw-r-- 1 julio julio          3 jun 23 18:40 numero20
-rw-rw-r-- 1 julio julio          3 jun 23 18:42 numero30
-rw-rw-r-- 1 julio julio          3 jun 23 18:43 numero40
-rw-rw-r-- 1 julio julio          0 jun 23 19:15 prueba.txt

la prueba con n=40 se comio 8 gigas!!!!

Esteban Blanco Ortuno

Hace 6 años

Muy ocurrente tu experimento, me gusta

Comentarios (318)318 comentarios

Facundo Nicolás García Martoni

Profesor

Hace 7 años

DAVID STEVEN BOCAREJO IBAÑEZ

Manuel Oviedo

Julio Manuel Valdés Alcántara

Harvi Calle

Diego Fernando Charfuelan Burbano

Irvin Vallejo

Yeison Tapasco

Gilberto Daniel Hermosillo Camacho

Brayan Alejandro

Vicente Benavides

Erika Itzel Hernández López

Samuel Delgado Muñoz

David Aroesti

Luis Davaria

Guillermo Sanchez

Jose Ignacio Melendez Albarracin

Anthony Guzman Lopez

Sebastian CA

Karl Behrens Gil

Nicolás Peralta Páez

JESUS ALBERTO CARREÑO MARTINEZ

Juan David Vergara Torres

Iván Ricardo Bohórquez Basto

Enrique Devars

Humberto SC

Hace 5 años

Emilian Harastasan

Oscar Hernan Pomi Piazza

Santiago Perez Moncada

Lizett Enríquez

jose zuñiga

Luis Fernando Pedroza Taborda

Ronny De Abreu

Andres Felipe Benavides Montoya

Daniel Luque Soria

Israel Yance

Daniel Alejandro Cumaco Robayo

Nicolás Morales Samaniego

Josue Noha Valdivia

David Ruiz

Introducción

Programación Dinámica y Estocástica: Optimización y Modelado de Datos

Programación Dinámica

Programación Dinámica: Optimización de Problemas con Memorización

Optimización de Algoritmos con Programación Dinámica en Python

Caminos Aleatorios

Simulaciones con Caminos Aleatorios en Programación

Camino Aleatorio en Programación Orientada a Objetos

Algoritmo de Caminata Aleatoria en Python: Clase Borracho

Simulación de Caminata Aleatoria con Python

Visualización de Caminatas Aleatorias con Python y Bokeh

Programas Estocásticos

Programación Estocástica: Aplicaciones y Ejemplos Prácticos

Cálculo de Probabilidades y Simulación de Montecarlo

Simulaciones de Probabilidades con Dados en Python

Inferencia Estadística: Conceptos y Aplicaciones Prácticas

Cálculo de la Media Aritmética en Python paso a paso

Media, Varianza y Desviación Estándar en Estadística

Distribución Normal: Propiedades y Aplicaciones Estadísticas

Simulaciones de Montecarlo

Simulaciones de Montecarlo: Historia y Aplicaciones Prácticas

Simulación de Montecarlo para Probabilidades en Juegos de Cartas

Simulaciones de Montecarlo para Aproximar Pi

Estimación de Pi mediante Monte Carlo y Simulación Estadística

Muestreo e Intervalos de Confianza

Muestreo Estadístico: Aleatorio y Estratificado

Teorema del Límite Central: Transformación de Distribuciones

Datos Experimentales

Validación de teorías científicas con datos experimentales

Regresión Lineal con NumPy y Matplotlib en Google Colab

Conclusiones

Optimización de Programas con Programación Dinámica y Simulaciones

Optimización de Algoritmos con Programación Dinámica en Python