Introducción a la Programación Dinámica

https://github.com/karlbehrensg/programacion-dinamica-y-estocastica

Programación Dinámica

Introducción a la Programación Dinámica

En la década de los 50s Richard Bellman necesitaba financiamiento del gobierno para poder continuar con sus investigaciones, por lo que necesitaba un nombre rimbombante para que no fueran capaz de rechazar su solicitud, por lo que eligió programación dinámica. Las propias palabras de Bellman fueron:

“[El nombre] Programación Dinámica se escogió para esconder a patrocinadores gubernamentales el hecho que en realidad estaba haciendo Matemáticas. La frase Programación Dinámica es algo que ningún congresista puede oponerse.” - Richard Bellman.

Ya sabiendo que Programación Dinámica no esta relacionado con su nombre, lo cierto es que si es una de las técnicas mas poderosas para poder optimizar cierto tipos de problemas.

Los problemas que puede optimizar son aquellos que tienen una subestructura óptima, esto significa que una solución óptima global se puede encontrar al combinar soluciones óptimas de subproblemas locales.

También nos podemos encontrar con los problemas empalmados, los cuales implican resolver el mismo problema en varias ocasiones para dar con una solución óptima.

Una técnica para obtener una alta velocidad en nuestro programa es la Memorización, el cual consiste en guardar cómputos previos y evitar realizarlos nuevamente. Normalmente se utiliza un diccionario, donde las consultas se pueden hacer en O(1), y para ello hacemos un cambio de tiempo por espacio.

Alguien más lo ve a 1,25x?

La programación dinámica es la optimización de un algoritmo mediante el desarrollo de subsistemas que van a reducir su tiempo de ejecución.

“El nombre Programacion Dinamica se escogio para esconder a patrocinadores gubernamentales el hecho de que en realidad estaba haciendo Matematicas. La frase Programacion Dinamica es algo a lo que ningun congresiste puede oponerse” - Richard Bellman

Los problemas que esta técnica puede optimizar son los que tienen una subestructura optima y ademas tiene ser un tipo de problema empalmado (ejem: Fibonacci)

• Subestructura Optima: una solucion optima local se puede encontrar al combinar soluciones optimas de subproblemas locales.
• Problemas empalmados: Una solucion optima que involucra resolber el mismo problema en varias ocaciones
  La optimizacion se basa en la “Memoization” (memorizacion)
• Es una tecnica para guardar computos previos con el fin de no realizarlos nuevamente
• Normalmente se utiliza un diccionario donde las consultas se pueden hacer en O(1)
• Intercambia Tiempo por Espacio

jaja ya sueño con el profe jajajaja

¿Es decir, que el término de sub-estructuras óptimas es un sinónimo de “Divide y vencerás”?

jajajaja el nombre solo fue para obtener financiación

Entonces la memorización es como crear una memoria cache donde dentro de un diccionario u otra estructura de datos se almacenen los resultados del funcionamiento de un algoritmo para hacer mas rápido el acceso a ellos. O eso entendí.

Como es posible que los diccionarios tengan O(1).
y otras estructuras de almacenamiento no.

o entendí mal?

¿porque se llama programación dinámica? --> Burocracia 😃

# Programácion dinámica y estocástica

Objetivos

• Aprender cuando utilizar programación dinámica y sus beneficios.
• Entender la diferencia entre programas deterministas y estocásticos.
• Aprender a utilizar programación estocástica.
• Aprender a crear simulaciones computacionales básicas.

No hay que dejarse confundir por el nombre rimbombante, ya que este es simplemente un nombre de marketing que le dio su creador Richard Bellman para conseguir financiamiento y ofuscar el hecho de que esto son simplemente matemáticas.

• Subestructura óptima: Es decir que una solución global óptima se puede encontrar al combinar soluciones óptimas de subproblemas locales.
• Problemas empalmados: Una solución óptima que involucra resolver el mismo problema en varias ocaciones.

Memoization:

Es una técnica qué consiste en guardar los cómputos realizados previamente en un resultado para poder consultarlo en lugar de repetir el cómputo. Un diccionario se puede consultar en O(1) (no importa el tamaño del diccionario, las consultas siempre toman lo mismo)

la programación dinámica es un método para reducir el tiempo de ejecución de un algoritmo mediante la utilización de sub-problemas superpuestos y sub-estructuras óptimas, como se describe a continuación.

El matemático Richard Bellman inventó la programación dinámica en 1953.

Dejo un resumen 😄
Si tienen alguna sugerencia me lo comentan por favor.

Richard Bellman: sinónimo de creatividad en una época en donde lograr recursos del gobierno de EEUU requería de creatividad e ingenio.

Vale la pena mencionarlo como estrategia de “marketing” que fue efectiva y hoy nos tiene aprendiendo sus métodos y técnicas.

Richard Ernest Bellman (1920–1984) fue un matemático aplicado, cuya mayor contribución fue la metodología denominada programación dinámica.

Programación Dinámica
Nombre rimbombante dado por Richad Bellman para conseguir financiación del estado.
Técnica de optimización de problemas algorítmicos

Búsqueda de la solución óptima

• Subestructura Optima → buscamos la solución optima a través del uso de las soluciones optimas de los subproblemas decompuestos
• Problemas empalmados → Solución optima cuando tenemos que resolver un mismo problema varias ocasiones a través de la memorización

Memorización:

• Guardamos cómputos previos, para evitar realizarnos nuevamente, generalmente en un diccionario al que posteriormente hacemos consultas → O(1)
• Con esta técnica intercambiamos tiempo (evitamos volver hacer un mismo computo) por espacio (almacenamos los computos en un diccionario)

Me pareció muy interesante el tema de la Memoization, el concepto lo entendí, pero me quedo la curiosidad de la etimología de la palabra. Así que para los que les interesa saber este tipo de cosas, en Wikipedia lo explican:

Quote: “El término “memoization” fue utilizado por primera vez por Donald Michie en 19683​ y deriva del latín memorandum (“que debe ser recordado”), ya que se describe como “convertir [el resultado de] una función en algo a ser recordado” . Aunque “memoización” puede ser confundida con “memorización” (Porque ambas proviene de la misma fuente), el término memoización tiene un uso exclusivo y específico en el desarrollo informático.”

Adicionalmente, también en StackOverflow hay una respuesta que da un poco de claridad sobre la diferencia entre “Memorization” y “Memoization”.

Saludos!

Es super interesante el cómo tengo 3 años usando memoizacion por medio de PowerQuery en Excel sin saber ni siquiera cómo se llamaba. Solo sabía que usaba la memoria ram y eso me dejaba procesar datos de forma muchoooooo más rápida en mis modelos de datos. Al fin a aprender cómo funciona internamente!

Este curso me vaa ayudar muchísimo para los cursos de la Universidad

Notas de la sesión 😄
Introducción a la programación dinámica.

• Es uno de los conceptos mas difíciles de digerir, en parte porque el nombre no tiene mucho que ver con la técnica.
• Surge en la década de los 50 con Richard Bellman, quien le puso un nombre fancy para recibir fondos del gobierno 😆.

[El nombre] programación dinámica se escogió para esconder a patrocinadores gubernamentales el hecho que en realidad estaba haciendo matemáticas. La frase Programación Dinámica es algo que ningún congresista puede oponerse.

• Es una de las técnicas mas poderosas para poder optimizar. Los problemas que se optimizan deben tener una subestructura óptima y además debe haber problemas empalmados.
  • Subestructura óptima: Una solución global óptima se puede encontrar al combinar soluciones óptimas de sub-problemas locales.
  • Problemas empalmados: Una solución óptima que involucra resolver el mismo problema en varias ocasiones.
• Ya hicimos algo parecido en merge sort (subestructura, no empalmados), problema del morral y fibonacci (subestructura y empalmados).
• Memoization:
  • La memorización es una técnica para guardar cómputos previos y evitar realizarlos nuevamente.
  • Normalmente se utiliza un diccionario, donde las consultas se pueden hacer en $O(1)$.
  • Intercambiamos tiempo de ejecución por espacio en memoria.

Origen del Nombre (Programación Dinámica)

Este nombre no tiene ninguna relación con lo que el nombre proyecta. El origen del nombre se dio para que los patrocinadores vieran esto como algo atractivo matemáticamente hablando.

La programación dinámica es un método de reducción de tiempo para la ejecución de un algoritmo mediante el uso de subproblemas superpuestos (problemas empalmados) y subestructuras óptimas.

• Subestructura Óptima
  Lo que plantea esta es básicamente dividir un problema general en varios pequeños para encontrar una solución más eficiente. El concepto lo encuentro muy similar a lo que sería “Divide and Conquer”.

• Subproblemas Superpuestos o Problemas Empalmados
  Se refiere a problemas que pueden ser dividido en subproblemas que pueden ser utilizados una y otra vez

Memoization o Memorización
Esto literalmente hace lo que dice la palabra, memorizar. Puesto que lo que hace es optimizar programas computacionales mediante la memorización de resultados de llamados de funciones y retornar estos resultados cuando los valores de entrada a la función sean los mismos. En resumen, es para no perder el tiempo en algo que nuestra función ya conoce.

++Resumen para estudiar: ++

-El nombre Programacion Dinamica no tiene nada que ver con su contenido, fue solo una estrategia de Richard Bellman para crear interés

-Es utilizada para optimizar problemas con:

-Subestructura óptima: Combinar soluciones, ej: Problema del morral, fibonacci recursivo, merge sort

-Problemas empalmados: Resolver mismo problema en varias ocasiones. Ej: Fibonacci recursivo al llamarlo una y otra vez,  diferencia de merge sort que cada vez que crea una lista genera un nuevo problema por resolver

No tengo claro cuál es el learning path que habla el prof! Creo que he hecho todos sus curso y por ejemplo no sé cuál es el problema del ‘morral’. Alguien sabe?

La historia de Richard Bellman y la programación dinámica está estrechamente vinculada al desarrollo de esta poderosa técnica en la ciencia de la computación.

Richard Bellman fue un matemático y científico estadounidense nacido el 26 de agosto de 1920 en Brooklyn, Nueva York. Se destacó en varios campos, incluyendo matemáticas aplicadas, ingeniería eléctrica y ciencias de la computación. Obtuvo su Ph.D. en matemáticas en la Universidad de Princeton en 1946.

En la década de 1950, mientras trabajaba en la Rand Corporation, un instituto de investigación estadounidense dedicado a la ciencia militar y la política, Bellman se enfrentó a problemas de optimización en los que tenía que tomar decisiones secuenciales con el objetivo de maximizar o minimizar una función objetivo. Estos problemas eran difíciles de resolver utilizando métodos tradicionales de optimización matemática.

Bellman tuvo una idea innovadora: dividir estos problemas en subproblemas más pequeños y resolverlos de manera recursiva. Al hacerlo, pudo encontrar soluciones óptimas a problemas más complejos al combinar las soluciones de los subproblemas. Llamó a esta técnica “programación dinámica” no porque tuviera algo que ver con la “dinámica” en el sentido físico, sino porque quería evitar que su trabajo fuera confundido con otros en el campo de la optimización matemática.

Uno de los problemas más conocidos en los que Bellman aplicó la programación dinámica fue el “problema del tiempo discreto de optimalidad” (DTOP por sus siglas en inglés). A partir de sus investigaciones, publicó el artículo “On the Theory of Dynamic Programming” en 1952, en el que presentó formalmente la técnica de programación dinámica y su aplicación a una amplia gama de problemas de optimización. En este trabajo, introdujo el “principio del óptimo de Bellman”, que es fundamental en la programación dinámica.

Desde entonces, la programación dinámica se ha convertido en una herramienta esencial para resolver problemas complejos en diversas áreas, incluyendo ciencias de la computación, matemáticas, ingeniería, economía, biología y más. Ha demostrado ser especialmente útil para resolver problemas de optimización con soluciones superpuestas y estructuras recursivas.

Richard Bellman recibió numerosos reconocimientos a lo largo de su carrera, incluyendo la Medalla Nacional de Ciencias en 1979, que es el más alto honor otorgado en Estados Unidos por logros en ciencias y tecnología. Su trabajo y contribuciones en programación dinámica han dejado un legado duradero y continúa siendo una herramienta fundamental en el campo de la ciencia de la computación y la optimización. Richard Bellman falleció el 19 de marzo de 1984 en Los Ángeles, California, dejando un impacto significativo en el campo de las ciencias y las matemáticas.

Resumen

Click Aquí

Aquí mis apuntes de la clase

• La programación dinámica no está relacionada con su nombre y fue escogido para esconder el hecho de que se estaba haciendo matemáticas.
  • El nombre “Programación Dinámica” fue inventado por Richard Bellman en la década de los 50 para ocultar el hecho de que estaba haciendo matemáticas.
• La programación dinámica es una técnica poderosa para optimizar ciertos tipos de problemas con estructura óptima.
• La estructura óptima significa que la solución global se puede encontrar encontrando soluciones óptimas a problemas locales.
• Para utilizar programación dinámica, deben haber problemas empalmados.
• La optimización se logra a través de la memorización, que es una técnica para evitar cómputos adicionales guardando resultados previos en una estructura de datos para acceder a ellos rápidamente.
• Al guardar los resultados en memoria, se puede ahorrar tiempo de cómputo.

Hahaha, grande Richard Bell, me recordó cuando se estaba construyendo el Foro Sol en el entonces Departamento del Distrito Federal les preguntaron que andaban haciendo, les dijeron que estaban creando caminos para que los camiones de carga pudieran transitar sin ningún problema 😅

La programación dinámica es solo un nombre que se invento RIchard Bellman.

La programación dinámica es uno de los conceptos más difíciles de digerir dentro del mundo de las ciencias de la computación.
[El nombre] Programación dinámica se escogió para esconder a patrocinadores gubernamentales el hecho que en realidad estaba haciendo matemáticas. La frase programación dinámica es algo que ningún congresista puede oponerse.

grande richar todo sea por las lucas xd

Al guardar los resultados en memoria, estamos intercambiando tiempo por espacio.

El hecho de guardar los resultados, hacen que nuestra O sea O de 1.

Para hacer la Memoization, solo necesitamos una estructura de datos y un acceso rápido a esta.

A través de la Memoisation or memoization, que simplemente, es guardar cómputos previos y evitar realizarlos nuevamente.

La optimización es sencilla y además, implementarla, hace que nuestra complejidad algorítmica disminuya.

Es justo en la repetición de problemas, que podemos generar una optimización.

Problemas empalmados: Una solución óptima que involucra resolver el mismo problema en varias ocasiones.

Es muy interesante, debido a que los problemas con Subestructura óptima, también tienen la gran mayoría, problemas empalmados, que son problemas que se repiten una y otra vez.

Unos ejemplos de problemas con Subestructura Óptima: Fibonancci Sequence, The Knapsack Problem, Factorials, Merge sort.

Problemas con Subestructura Óptima: Una solución global óptima se puede encontrar al combinar soluciones óptimas de subproblemas locales.

Problemas que se pueden resolver con programación dinámica: Subestructura Óptima y Problemas empalmados.

La programación dinámica, puede tener un nombre embustero, pero lo cierto, es que una de las técnicas más poderosas en ciencias computacionales para la optimización de algunas categorías de problemas.

Definitavemente, la programación dinámica, no tiene nada que ver con su nombre.

Según Richard: Programación Dinámica se escogió para esconder a patrocinadores gubernamentales el hecho de que en realidad estaba haciendo matemáticas. La Frase Programación Dinámica, es algo al que ningún congresista puede oponerse.

Para conseguir inversión, Richard deicidió darle un nombre a sus investigaciones, que hiciera parecer su estudio como algo complicado.

En la década de los 50 Richard Bellman, necesitaba grants, así que decidió acudir al gobierno, para desarrollar sus investigaciones en matemáticas.

La programación dinámica, es uno de los temas más dificiles de digerir dentro de las ciencias de la computación.

Me recuerda a la relatividad!!!
Adicional es interesante que el nombre tenga que ver con marketing.

Para mi esto es como una filosofía, cuando tu creas un plan es por que tienes una meta que se ve muy difícil de alcanzar, así que subdivides esa meta en metas que puedes cumplir en un menor rango de tiempo, de modo que al juntar todos esos pequeños logros llegues a tu meta, ahí inviertes tu tiempo y energía, y dependes de tu concentración para volver eficiente ese tiempo que destines en cada tarea.

Mi resumen 🐍

cuando se refiere a memoria de nuestro computador quiere decir memoria RAM o memoria ROM ??

La programación dinámica es una técnica matemática que
se utiliza para la solución de problemas matemáticos
seleccionados, en los cuales se toma un serie de decisiones
en forma secuencial.

Definición de Programación Dinámica desde las soluciones óptimas a problemas.

Mejor dicho, “Memoization” XD

Creador y algo de historia.

Optimizar dentro del tiempo es equivalente a ahorrar espacio en memoria, esto es lo que se concibe como memoization.

Optimización con Memorization.

Richard es mi héroe

Hacer un randomforest cae dentro de la programación dinámica?

Muy interesante la técnica de Menoization.

Esta interesante, vere que puedo aplicar en el trabajo

Yo creo que en algún punto podremos ganar tiempo sin ocupar tanto espacio.

Memorizacion
Consultas O(1)
Intercambia tiempo por espacio

Interesante!

buenardo

Me voy a quedar con los ojos abiertos !😃

import time
import sys

def fibonacci_recursivo(n):
    if n == 0 or n == 1:
        return 1

    return fibonacci_recursivo(n-1) + fibonacci_recursivo(n-2)

def fibonacci_dinamico(n, memo = {}):
    if n == 0 or n == 1:
        return 1

    try:
        return memo[n]
    except KeyError:
        resultado = fibonacci_dinamico(n-1, memo) + fibonacci_dinamico(n-2, memo)
        memo[n] = resultado

        return resultado


if __name__ == '__main__':
    sys.setrecursionlimit(10002)
    
    #introduccion del valor
    n = int(input('Escoge un número: '))

    #registro tiempo de inicio
    tiempo_inicial = time.time()
    resultado = fibonacci_dinamico(n)
    
    #registro tiempo de finalización
    tiempo_final = time.time()

    #tiempo empleado en el cálculo
    tiempo = tiempo_final - tiempo_inicial

    print(resultado)
    print(f'Ha tardado {tiempo}')```

Ok es una breve introducción en la cual nos dice el origen del nombre de programación dinámica y que proviene hacer un nombre rimbombante para así obtener financiamiento, también nos dice que es una herramienta para optimizar un algoritmo ya sea (O**n) o (On*n) y los requerimientos necesarios para es que tenga una subestructura Optima: que el algoritmo internamente tenga procesos óptimos y sea un problema empalmado: que el problema se encuentre en un loop. la manera de solución es por medio de la memorización guardando dentro de un diccionario los datos que se van generando sacrificando así espacio en memoria por velocidad de computo.

Esto me hace recordar cuando utilizaba archivos de propiedades o de texto en java para guardar información y utillizarla en mis aplicaciones, algo como un integrador.

Pongan atenciones aquellos de nosotros que queremos implementar una solución que nos crea un problema nuevo.

Definición de programación Dinámica.

Dejo un articulo de Dan Abramov que me pareció bastante interesante. Habla de memoization con respecto a JavaScript.
whatthefork.is/memoization

Me parece muy curiosa la historia del nombre “Programación Dinámica”. Un claro ejemplo de como muchas veces los investigadores tienen que hacer, digamos, “marketing” a sus trabajos para conseguir dineros del estado.

Excelente introducción!

Cada vez más me emociona este curso!

Entendido

El término “memoization” fue acuñado por Donald Michie en 1968 y se deriva del latín palabra " memorándum " ( “ser recordado”), por lo general truncada como “memo” en Inglés Americano, y por lo tanto lleva el significado de "convertir [el resultados de] una función en algo para ser recordado ". Mientras que “memoization” podría ser confundida con la " memorización " (porque son etimológico afines s), “memoization” tiene un significado especial en la computación.

Sobre este tema existe una referencia más desarrollada en este libro: Lew, A. y H. Mauch,“Dynamic Programming: A computational Tool”, springer, Nueva York, 2007.

Recuerdo que este profe en el curso de python (asi asecas) no me inspiraba nada, pero ha mejorado bastante. Me cae muy bien.

En este apartado se responden las siguientes preguntas:
¿Qué es programación dinámica?
¿Qué elementos permiten la programación dinámica?
¿En qué me ayuda la memorización?

😃

La programación dinámica no es sólo parte de las ciencias de la computación, sino también parte de la Investigación de operaciones.
Mi viejo nemesis en cuando llevaba esa materia, es muy interesante pero puede hacerse muy compleja.

Subestructura Óptima.