Base De Programación Dinámica
Páginas: 1 (250 palabras)
Publicado: 13 de abril de 2012
PROGRAMACIÓN DINÁMICA
V. Johann Cortez 13 de abril de 2012
En las ciencias de la computación, la programación dinámica es unmétodo el cual nos permite realizar calculos de una manera mas rapida que usando backtracking, busqueda completa o fuerza bruta. Este métodoconsiste en memorizar cierta información la cual se volvera a consultar permitiendo un mejor desempeño. Un ejemplo claro es lasecuencia de Fibonacci: 0,1,1,2,3,5,8,13,.... Dada la secuencia calcular el numero de la x-ésima posición(comenzando de 0). Donde cada elementoexcepto los dos primeros son resultado de la suma de los dos anteriores. x 0 1 2 3 4 5 6 7 f(x) 0 1 1 2 3 5 8 13 Se podria expresarbajo la formula: f (x) = x , si x 1 El trabajo que se requiere para hallar f(x) es la suma de los trabajos que se requiere para hallarf(x-1) y f(x-2). Usando recursión primero hallariamos f(x - 1) y luego f(x - 2). Pero nos damos cuenta que al hallar f(x - 1) estariamoshallando ya f(x - 2), ya que:
f (x − 1) = f (x − 2) + f (x − 3)
Este valor podriamos guardarlo para no desarrollarlo nuevamente. La
idea principal de la programación dinámica es guardar valores que se necesitaran
despues.
1
MEMORIZANDO
Si en uninicio nuestro algoritmo se habria parecido a esto :
funcion fib(x) //Este algoritmo tiene una complejidad enorme O(2 ^ n). si x
V. Johann Cortez 13 de abril de 2012
En las ciencias de la computación, la programación dinámica es unmétodo el cual nos permite realizar calculos de una manera mas rapida que usando backtracking, busqueda completa o fuerza bruta. Este métodoconsiste en memorizar cierta información la cual se volvera a consultar permitiendo un mejor desempeño. Un ejemplo claro es lasecuencia de Fibonacci: 0,1,1,2,3,5,8,13,.... Dada la secuencia calcular el numero de la x-ésima posición(comenzando de 0). Donde cada elementoexcepto los dos primeros son resultado de la suma de los dos anteriores. x 0 1 2 3 4 5 6 7 f(x) 0 1 1 2 3 5 8 13 Se podria expresarbajo la formula: f (x) = x , si x 1 El trabajo que se requiere para hallar f(x) es la suma de los trabajos que se requiere para hallarf(x-1) y f(x-2). Usando recursión primero hallariamos f(x - 1) y luego f(x - 2). Pero nos damos cuenta que al hallar f(x - 1) estariamoshallando ya f(x - 2), ya que:
f (x − 1) = f (x − 2) + f (x − 3)
Este valor podriamos guardarlo para no desarrollarlo nuevamente. La
idea principal de la programación dinámica es guardar valores que se necesitaran
despues.
1
MEMORIZANDO
Si en uninicio nuestro algoritmo se habria parecido a esto :
funcion fib(x) //Este algoritmo tiene una complejidad enorme O(2 ^ n). si x
Leer documento completo
Regístrate para leer el documento completo.