TAREA DE I.O.

INTRODUCCION

Existe una serie de problemas cuyas soluciones pueden ser expresadas recursivamente en términos matemáticos, y posiblemente la manera más natural de resolverlos es mediante unalgoritmo recursivo. Sin embargo, el tiempo de ejecución de la solución recursiva, normalmente de orden exponencial y por tanto impracticable, puede mejorarse substancialmente mediante la ProgramaciónDinámica.
La Programación Dinámica no sólo tiene sentido aplicarla por razones de eficiencia, sino porque además presenta un método capaz de resolver de manera eficiente problemas cuya solución ha sidoabordada por otras técnicas y ha fracasado.
Donde tiene mayor aplicación la Programación Dinámica es en la resolución de problemas de optimización. En este tipo de problemas se pueden presentar distintassoluciones, cada una con un valor, y lo que se desea es encontrar la solución de valor óptimo (máximo o mínimo).
Para que un problema pueda ser abordado por esta técnica ha de cumplir dos condiciones:• La solución al problema ha de ser alcanzada a través de una secuencia de decisiones, una en cada etapa.
• Dicha secuencia de decisiones ha de cumplir el principio de óptimo.
En grandes líneas,el diseño de un algoritmo de Programación Dinámica consta de los siguientes pasos:
1. Planteamiento de la solución como una sucesión de decisiones y verificación de que ésta cumple el principio deóptimo.
2. Definición recursiva de la solución.
3. Cálculo del valor de la solución óptima mediante una tabla en donde se almacenan soluciones a problemas parciales para reutilizar los cálculos.
4.Construcción de la solución óptima haciendo uso de la información contenida en la tabla anterior.


CONCEPTOS DE PROGRAMACION DINAMICA
La programación dinámica es un enfoque general para lasolución de problemas en los que es necesario tomar decisiones en etapas sucesivas. Las decisiones tomadas en una etapa condicionan la evolución futura del sistema, afectando a las situaciones en las que...