Ingenieria En Electronica

Definición:
En informática, 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 subestructurasóptimas, como se describe a continuación.

Inventor:
El matemático Richard Bellman inventó la programación dinámica en 1953 que se utiliza para optimizar problemas complejos que pueden serdiscretizados y secuencializados.

Principio de optimalidad
Cuando hablamos de optimizar nos referimos a buscar alguna de las mejores soluciones de entre muchas alternativas posibles. Dichoproceso de optimización puede ser visto como una secuencia de decisiones que nos proporcionan la solución correcta. Si, dada una subsecuencia de decisiones, siempre se conoce cuál es la decisiónque debe tomarse a continuación para obtener la secuencia óptima, el problema es elemental y se resuelve trivialmente tomando una decisión detrás de otra, lo que se conoce como estrategia voraz.En otros casos, aunque no sea posible aplicar la estrategia voraz, se cumple el principio de optimalidad de Bellman que dicta que «dada una secuencia óptima de decisiones, toda subsecuencia deella es, a su vez, óptima». En este caso sigue siendo posible el ir tomando decisiones elementales, en la confianza de que la combinación de ellas seguirá siendo óptima, pero será entoncesnecesario explorar muchas secuencias de decisiones para dar con la correcta, siendo aquí donde interviene la programación dinámica.
Contemplar un problema como una secuencia de decisiones equivalea dividirlo en problemas más pequeños y por lo tanto más fáciles de resolver como hacemos en Divide y Vencerás, técnica similar a la de programación dinámica. La programación dinámica seaplica cuando la subdivisión de un problema conduce a:
• Una enorme cantidad de problemas.
• Problemas cuyas soluciones parciales se solapan.
• Grupos de problemas de muy distinta complejidad.