Programación Dinamica
Páginas: 2 (480 palabras)
Publicado: 20 de enero de 2015
PROGRAMACION DINAMICA
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 subproblemas superpuestos y subestructurasóptimas. El matemático Richard Bellman inventó la programación dinámica en 1953 que se utiliza para optimizar problemas complejos que pueden ser discretizados y secuencializados.
ORIGEN DE LAPROGRAMACION DINAMICA
Su inicio y desarrollo básico se debe a Richard Bellman [BEL57-62B] al principio de los cincuenta. La trascendencia de esta metodología no se limita a la Investigación Operativa,sino que es también de gran importancia en la Teoría del Control Óptimo, en estrecha relación con el principio del máximo de Pontryagin [PON62]. En lo que aquí nos concierne, el desarrollo de laProgramación Dinámica se ha visto limitado en su aplicabilidad concreta debido a la complejidad computacional que le acompaña, tanto debido a la cardinalidad del espacio de estado como al número de períodosque intervienen. En este sentido, el trabajo de Larson ha colaborado a su tratamiento, pero muchos autores aún consideran a la Programación Dinámica como un punto de vista conceptual y un bagajeteórico para el análisis de problemas; y no como un método -o conjunto de ellos- implantable en algoritmos de tipo general. En esta dirección, los trabajos de Denardo [DEN51], identificando la estructura delos procesos de decisiones secuenciales, suponen un avance para establecerlos.
CARACTERISTICAS
LA PROGRAMACION HACE USO DE:
SUB PROBLEMAS SUPERPUESTOS
Decir que un problematiene subproblemas superpuestos es decir que se usa un mismo subproblema para resolver diferentes problemas mayores. Por ejemplo, en la sucesión de Fibonacci (F3 = F1 + F2 y F4 = F2 + F3) calcular cada términosupone calcular F2. Como para calcular F5 hacen falta tanto F3 como F4, una mala implementación para calcular F5 acabará calculando F2 dos o más veces. Esto sucede siempre que haya subproblemas...
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 subproblemas superpuestos y subestructurasóptimas. El matemático Richard Bellman inventó la programación dinámica en 1953 que se utiliza para optimizar problemas complejos que pueden ser discretizados y secuencializados.
ORIGEN DE LAPROGRAMACION DINAMICA
Su inicio y desarrollo básico se debe a Richard Bellman [BEL57-62B] al principio de los cincuenta. La trascendencia de esta metodología no se limita a la Investigación Operativa,sino que es también de gran importancia en la Teoría del Control Óptimo, en estrecha relación con el principio del máximo de Pontryagin [PON62]. En lo que aquí nos concierne, el desarrollo de laProgramación Dinámica se ha visto limitado en su aplicabilidad concreta debido a la complejidad computacional que le acompaña, tanto debido a la cardinalidad del espacio de estado como al número de períodosque intervienen. En este sentido, el trabajo de Larson ha colaborado a su tratamiento, pero muchos autores aún consideran a la Programación Dinámica como un punto de vista conceptual y un bagajeteórico para el análisis de problemas; y no como un método -o conjunto de ellos- implantable en algoritmos de tipo general. En esta dirección, los trabajos de Denardo [DEN51], identificando la estructura delos procesos de decisiones secuenciales, suponen un avance para establecerlos.
CARACTERISTICAS
LA PROGRAMACION HACE USO DE:
SUB PROBLEMAS SUPERPUESTOS
Decir que un problematiene subproblemas superpuestos es decir que se usa un mismo subproblema para resolver diferentes problemas mayores. Por ejemplo, en la sucesión de Fibonacci (F3 = F1 + F2 y F4 = F2 + F3) calcular cada términosupone calcular F2. Como para calcular F5 hacen falta tanto F3 como F4, una mala implementación para calcular F5 acabará calculando F2 dos o más veces. Esto sucede siempre que haya subproblemas...
Leer documento completo
Regístrate para leer el documento completo.