. 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.
En la próxima clase veremos el problema de la triangulación óptima de polÃgonos (óptima en el sentido de incluir un conjunto de cuerdas de longitud total mÃnima). El problema tiene muchas aplicaciones: en robótica se utiliza para la generación del plan de movimientos de un robot; algo parecido se precisa en informática gráfica para el [...]
La semana próxima, probablemente, hablaremos del problema del viajante de comercio (TSP). Las transparencias sobre la solución del TSP con programación dinámica están basadas en el material del libro: Algorithmics. Theory and Practice, de Gilles Brassard y Paul Bratley (ed. Prentice Hall, 1988). En este enlace (acceso restringido) pueden encontrarse las páginas correspondientes.
Mañana hablaremos en clase de la distancia de edición entre secuencias de caracteres. 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).
Se han publicado en la página de problemas algunos ejercicios del tema de programación dinámica. El último de ellos es el que ya mencionamos aquÃ.
Si en el ejercicio 3 de la hoja de problemas de divide y vencerás hacemos un pequeño cambio permitiendo hacer variable el número de datos que tienen que sumar una cantidad dada, el problema es sensiblemente más “difÃcil”: Dado un conjunto S de enteros y un entero x, ¿existe algún subconjunto de S cuya suma sea x? [...]