Toda solución de programación dinámica evita usar una solución top-down recursiva que directamente traduzca a un algoritmo la ecuación recurrente correspondiente al problema. Esto es asà porque, normalmente, el coste en tiempo de esa solución es extremadamente alto pues resuelve muchas veces los mismos subproblemas. Para evitar resolver muchas veces los mismos subproblemas, un algoritmo de [...]
En la página de material adicional de esta web puede encontrarse: Un artÃculo que describe un par de métodos de ordenación por fusión (o mezcla) “in situ” y analiza su coste (acceso con clave aquÃ). Un par de capÃtulos de libros sobre métodos de ordenación en memoria externa basados en la idea de la ordenación por [...]
En la transparencia 55 de programación dinámica quedó como ejercicio el cálculo de los nodos de las secuencias que componen los caminos mÃnimos desde cualquier nodo i a cualquier nodo j. Hay varias formas de resolverlo. Una muy sencilla consiste en guardar una matriz adicional C[v,w] en la que se almacene un nodo u que [...]
. Las soluciones de programación dinámica aparecen en prácticamente todos los dominios de aplicación. Seleccionamos aquà algunos ejemplos en Visión, Juegos, Robótica y Bioinformática: Dynamic Programming and Graph Algorithms in Computer Vision: A Survey. Dynamic programming and board games: A survey (acceso restringido con usurio/clave). Some dynamic programming problems useful to solve the mobile robot [...]
Uno de los ejemplos más sencillos (más que los vistos en clase) de aplicación de la programación dinámica es el cálculo del término n-ésimo de la sucesión de Fibonacci. La definición de la sucesión o función de Fibonacci es: Fib(n) = 1, si n = 0,1 Fib(n) = Fib(n-1) + Fib(n-2), si n > 1 [...]
. El algoritmo conocido como “de Karatsuba y Ofman” para multiplicar enteros de n cifras con un coste asintótico en O(nlog 3)  ( ≈ O(n1,59) )  aparece publicado en el artÃculo ”Multiplication of multidigit numbers on automata”, A. Karatsuba, Y. Ofman, en el nº 145, pp. 293-294, de las actas de la Academia de Ciencias de [...]
En la página de material adicional de esta web puede encontrarse: Un artÃculo que describe un par de métodos de ordenación por fusión (o mezcla) “in situ” y analiza su coste (acceso con clave aquÃ). Un par de capÃtulos de libros sobre métodos de ordenación en memoria externa basados en la idea de la ordenación por [...]
La anotación en el blog de Jeremy Kun: When Greedy Algorithms are Perfect: the Matroid. Más allá de los matroides: los gridoides.
. Leer esta anotación: http://webdiis.unizar.es/asignaturas/AB/?p=1009
. Aquà y aquÃ.