- 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.
El curso próximo se impartirá por primera vez la asignatura optativa “Bioinformática“, de la especialidad de Computación.
El próximo miércoles 29 de abril, a las 15:00 h., la presentará en clase (aula 12, edificio Ada Byron) la profesora Elvira Mayordomo.
TÃtulo: ¿Desarrollamos?
Fecha/hora/lugar/: Miércoles 29 de abril, 16:00 h., aula 12 del edificio Ada Byron.
Breve descripción:
¿Cómo es la arquitectura de un producto software complejo? ¿Qué metodologÃa se establece para controlar el ciclo de vida de desarrollo? ¿Cómo son los modelos de integración con otros sistemas corporativos? ¿Cómo es la infraestructura hardware y de comunicaciones requerida para el despliegue? ¿Cómo son las medidas de seguridad de la información de nivel alto? ¿Qué competencias y habilidades requiere la gestión de un proyecto de implantación software?
Ponente:
Fernando Cortés, CEO de Endalia, Ingeniero en Informática por la Universidad de Zaragoza, nos trasladará una visión global desde la perspectiva y la experiencia de proyectos de implantación de software para la gestión integral de capital humano en organizaciones como Airbus Group, La Caixa, Ineco, IBM, Esade, Banco Santander, Infojobs, entre otros.
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 cálculo de la visibilidad (eliminación de superficies ocultas en una imagen);
- para el cálculo de campos magnéticos en determinados dominios;
- los métodos de análisis de elementos finitos también utilizan la triangulación para hacer tratable el problema;
- los meteorólogos triangularizan para calcular las predicciones del tiempo;
- en algunos algoritmos de teorÃa del caos también aparecen triangulaciones para resolver ecuaciones diferenciales;
- se usa también en el renderizado de imágenes (generación de imágenes virtuales mediante el cálculo de la iluminación, a partir de un modelo 3D);
- …
En relación con la última aplicación mencionada, puede verse una publicación reciente sobre generación de personajes en videojuegos en la web de la Especialidad en Computación (hacer clic en la imagen siguiente).
Se han publicado los resultados de la prueba intermedia en el tablón moodle de la asignatura.
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Ã.
La prueba escrita intermedia de la asignatura será el miércoles 8 de abril, a las 15:00 horas en el aula 12 del edificio Ada Byron. Se permite llevar y usar el material impreso que se quiera, pero no dispositivos electrónicos.
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?
Es el problema conocido como la suma de subconjuntos, puede verse como un caso particular del problema de la mochila (no fraccionable), y el mejor algoritmo exacto conocido para resolverlo tiene coste exponencial.
Veremos una solución (de coste pseudo-polinómico) en el siguiente tema sobre algoritmos de programación dinámica.