Taller Analisis y Diseño de Algoritmos
Proyecto Final
Carlos Andrés González Castro
Cód.: 1105675
Universidad de San Buenaventura
Seccional Cali
OBJETIVOS:
Diseñar unalgoritmo dinámico que nos informe la ganancia que nos deja invertir dinero en un banco maximizando los intereses.
Calcular la función temporal para el algoritmo
Comprender el comportamientodel algoritmo respecto a tiempo por tamaño.
MARCO TEORICO
Programación Dinámica
La programación dinámica es un método para reducir el tiempo de ejecución de un algoritmomediante la utilización de tres factores importantes como lo son la memoizacion, subproblemas superpuestos y subestructuras óptimas.
La programación toma normalmente uno de los dos siguientesenfoques:
Top-down: El problema se divide en subproblemas, y estos se resuelven recordando las soluciones por si fueran necesarias nuevamente. Es una combinación de memoización y recursión.
Bottom-up:Todos los problemas que puedan ser necesarios se resuelven de antemano y después se usan para resolver las soluciones a problemas mayores. Este enfoque es ligeramente mejor en consumo de espacio yllamadas a funciones, pero a veces resulta poco intuitivo encontrar todos los subproblemas necesarios para resolver un problema dado.
El diseño de un algoritmo de Programación Dinámica consta delos 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álculodel 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 lainformación contenida en la tabla anterior.
INTERESES BANCARIOS
Dadas n funciones f1, f2,..., fn y un entero positivo M, deseamos maximizar la función f1(x1) + 2(x2) + ... +...
Regístrate para leer el documento completo.