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

sguenos en twitter

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

En la técnica de divide y vencerás, un ejemplar del problema se divide en ejemplares más sencillos del mismo problema que se resuelven separadamente (son ejemplares, de alguna manera, independientes) y sus soluciones se combinan para crear una solución del ejemplar del problema original. En el próximo esquema algorítmico que veremos en clase, programación dinámica, los subproblemas en [...]

. Las transparencias sobre la solución del problema del viajante de comercio 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.