Taller Analisis y Diseño de Algoritmos

788 palabras 4 páginas
Diseño y Análisis de Algoritmo

Proyecto Final

Carlos Andrés González Castro

Cód.: 1105675

Universidad de San Buenaventura
Seccional Cali
OBJETIVOS:

Diseñar un algoritmo 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 comportamiento del 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 algoritmo mediante la utilización de tres factores importantes como lo son la memoizacion, subproblemas superpuestos y subestructuras óptimas.

La programación
…ver más…
Supóngase que los valores de cada función se almacenan en un vector. Este problema tiene una aplicación real muy interesante, en donde fi representa la función de interés que proporciona el banco i, y lo que deseamos es maximizar el interés total al invertir una cantidad determinada de dinero M. Los valores xi van a representar la cantidad a invertir en cada uno de los n bancos.

Solución

Sea fi un vector que almacena el interés del banco i (1 ≤ i n) para una inversión de 1, 2, 3,..., M pesetas. Esto es, fi(j) indicará el interés que ofrece el banco i para j pesetas, con 0 < i ≤ n , 0 < j ≤ M. Para poder plantear el problema como una sucesión de decisiones, llamaremos In(M) al interés máximo al invertir M pesetas en n bancos,
In(M) = f1(x1) + f2(x2) + ... + fn(xn) que es la función a maximizar, sujeta a la restricción x1 +x2 + ... + xn = M.
Veamos cómo aplicar el principio de óptimo. Si In(M) es el resultado de una secuencia de decisiones y resulta ser optima para el problema de invertir una cantidad M en n bancos, cualquiera de sus subsecuencias de decisiones ha de ser también óptima y así la cantidad In–1(M – xn) = f1(x1) + f2(x2) + ... + fn–1(xn–1).
Será también óptima para el subproblema de invertir (M – xn) pesetas en n – 1 bancos. Y por tanto el principio de óptimo nos lleva a plantear la siguiente relación en

Documentos relacionados

  • Analisis y diseño de sistemas
    8236 palabras | 33 páginas
  • Analisis y diseños de sistemas
    800 palabras | 4 páginas
  • taller de algoritmo
    886 palabras | 4 páginas
  • Análisis Y Diseño De Sistemas Y Procedimientos
    3980 palabras | 16 páginas
  • Técnicas de analisis de algoritmos
    881 palabras | 4 páginas
  • Analisis y diseño de puesto
    1845 palabras | 8 páginas
  • Estándares de calidad en el diseño de algoritmos y construcción de programas
    6169 palabras | 25 páginas
  • Plan y diseño de un taller de costura
    2465 palabras | 10 páginas
  • Análisis y Diseño de Sistemas Kendall & Kendall
    1477 palabras | 6 páginas
  • Diseño y analisis de experimentos de paracaidas
    1213 palabras | 5 páginas