Programacion dinamica

INTRODUCCION

Este trabajo de investigación fue elaborado a lo largo del semestre Enero-Junio 09, en la materia Taller de Investigación II.

Se abordaron distintos aspectos relacionados con Programación Dinámica, para así poder comprender mejor su funcionamiento, además de analizar los distintos tipos de problemas que se pueden presentar con la programación dinámica.

Este trabajo presentade manera sintetizada y clara, los puntos más importantes concernientes a la programación dinámica, pero teniendo en cuenta que el trabajo se enfoca más en los beneficios de ocupar la programación dinámica con respecto al tiempo de ejecución.

MARCO TEORICO

La programación dinámica es un enfoque general para la solución de problemas en los que es necesario tomar decisiones en etapassucesivas. Las decisiones tomadas en una etapa condicionan la evolución futura del sistema, afectando a las situaciones en las que el sistema se encontrará en el futuro (denominadas estados), y a las decisiones que se plantearán en el futuro.
Conviene resaltar que a diferencia de la programación lineal, el modelado de problemas de programación dinámica no sigue una forma estándar. Así, para cada problemaserá necesario especificar cada uno de los componentes que caracterizan un problema de programación dinámica.
El procedimiento general de resolución de estas situaciones se divide en el análisis recursivo de cada una de las etapas del problema, en orden inverso, es decir comenzando por la última y pasando en cada iteración a la etapa antecesora. El análisis de la primera etapa finaliza con laobtención del óptimo del problema.
La programación dinámica se suele utilizar en problemas de optimización, donde una solución está formada por una serie de decisiones. Igual que la técnica divide y vencerás, resuelve el problema original combinando las soluciones para sub-problemas más pequeños. Sin embargo, la programación dinámica no utiliza recursividad, sino que almacena los resultados de lossub-problemas en una tabla, calculando primero las soluciones para los problemas pequeños ,Con esto se pretende evitar la repetición de cálculos para problemas más pequeños.
Los algoritmos divide y vencerás están dentro de los métodos descendentes .Empezar con el problema original y descomponer en pasos sucesivos en problemas de menor tamaño .Partiendo del problema grande, descendemos haciaproblemas más sencillos.
La programación dinámica, por el contrario, es un método ascendente: Resolvemos primero los problemas pequeños (guardando las soluciones en una tabla) y después vamos combinando para resolver los problemas más grandes.

ARBOL DEL PROBLEMA

ARBOL DEL PROBLEMA

En el ámbito de la programación se buscan soluciones a problemas, pero al resolver ciertos problemas nosencontramos con los siguientes acontecimientos:

• TOMA DE DECISIONES ERRONEAS EN ETAPAS SUCESIVAS.

• PROCESAMIENTO INEFICIENTE DE DATOS.

Debido a estos acontecimientos tenemos como consecuencia:

• RESULTADOS NO OPTIMOS DE PROCESAMIENTO DE DATOS.

• NECESIDAD DE CAPACIDAD COMPUTACIONAL.

Ante este tipo de necesidades se empezaron a buscar soluciones hasta que el matemático“Richard Bellman” encontró la solución a este problema y le llamo programación dinámica.

HIPOTESIS

Se piensa que con la programación dinámica el tiempo de ejecución y de manejo de información se reducirá proporcionalmente al tamaño del problema

OBJETIVOS GENERALES

• Conocer las ventajas de la programación dinámica

• Conocer en que consiste la programación dinámica.OBJETIVOS ESPECIFICOS

• Determinar las ventajas de la programación dinámica en cuanto a tiempo de ejecución se refiere.

JUSTIFICACION

Esta investigación se lleva a cabo con el fin de conocer varios aspectos relacionados con “programación dinámica” y los beneficios que nos otorga en cuanto tiempo de ejecución se refiere.

Conociendo a fondo la función e importancia de programación...