Algoritmia básica (AB)
El reto de diseñar algoritmos eficientes para resolver problemas puede resultar apasionante

sguenos en twitter

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 [...]

Se ha publicado una hoja de problemas (algoritmos de programación dinámica).

. Veremos en clase alguna de las ideas básicas del algoritmo del simplex (ver transparencias 54 a 70 de la asignatura, o transparencias 16 a 36 de estas otras del material adicional). No obstante, su implementación detallada dista de ser sencilla. Por ejemplo, en esta anotación del blog de Jeremy Kun puede encontrarse una descripción [...]

. No es extraño que en entrevistas de trabajo relacionadas con la Computación aparezcan problemas resolubles mediante programación dinámica. Aquí hay algunos de ellos: What are the top 10 most popular dynamic programming problems among interviewers?

. Probablemente este miércoles podamos empezar a trabajar en clase con los problemas de la hoja de programación dinámica. Pero únicamente lo haremos si los habéis trabajado antes vosotros… Para plantear una solución de programación dinámica, normalmente, deben seguirse los pasos siguientes: Definir de manera precisa una función parametrizada tal que, para algunos valores de [...]

En la próxima clase hablaremos de la distancia de edición entre secuencias. El problema tiene aplicaciones, entre otras muchas, en los dominios de la bioinformática (ver el enlace http://webdiis.unizar.es/asignaturas/AB/?p=93) y de la robótica (ver http://webdiis.unizar.es/asignaturas/AB/?p=1144).

Three seemingly unrelated problems (matrix chain multiplication, optimal BST, and optimal polygons triangulation). Dynamic Programming and Graph Algorithms in Computer Vision: A Survey. Dynamic programming and board games: A survey (acceso para alumnos de AB). Some dynamic programming problems useful to solve the mobile robot localization problem. Systematic Dynamic Programming in Bioinformatics.