Ya tenéis disponible el guión de la práctica 2. Se trata de resolver el problema del viajante de comercio mediante dos estrategias: fuerza bruta y programación dinámica. Una vez implementadas las estrategias, hay que comparar sus tiempos de ejecución para distintos tamaños del problema.
.
Hoy veremos en clase un problema de comparación de secuencias de caracteres (transparencias 41 a 47 de programación dinámica), concretamente el problema de la distancia de edición entre dos secuencias.
La solución de este problema (y de otros similares) tiene aplicaciones en diversos ámbitos, entre ellos la biologÃa computacional, asà como, de forma mucho más concreta, el mantenimiento de versiones de ficheros con editores de textos.
También en el ámbito de la robótica puede resultar útil la solución del problema de la distancia de edición entre cadenas. En el artÃculo “Solving the mobile robot localization problem using string matching algorithms“, fruto del Proyecto Fin de Carrera de una estudiante de esta Escuela (publicado en Proceedings of the 2004 IEEE/RSJ International Conference on Intelligent Robots and Systems IROS’04, Sendai, Japan, 2004, pp. 2475-2480), se presenta una solución al problema del robot secuestrado en términos de problemas de distancia de edición resueltos con algoritmos de programación dinámica.
.
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 programación dinámica, los subproblemas en que se divide el problema original no son independientes, en el sentido siguiente: los subproblemas comparten subproblemas entre ellos. Por tanto, una solución de divide y vencerás resolverÃa repetidas veces esos subproblemas compartidos, haciendo más trabajo del necesario. En programación dinámica se utiliza la técnica de la memorialización (memoization) para almacenar y reutilizar las soluciones de los subproblemas comunes, evitando resolverlos más de una vez.
Algo de información: en este enlace.
Casi seguramente (se confirmará en clase más adelante) el test intermedio será el dÃa 30 de abril, en las horas habituales de clase, sobre los temas: “algoritmos voraces”, “divide y vencerás” y “programación dinámica”; y se permitirá usar apuntes pero no dispositivos electrónicos.
Está disponible en la página de ejercicios una hoja de ejercicios sobre algoritmos de programación dinámica (en caso de entregar alguno de ellos, debe hacerse no más tarde del 30/04/2013).
Tras esta hoja, habrá otras dos más.
Se prevén cortes de luz (mantenimiento) en Ada Byron. Es posible que se apaguen los servidores web. Bajad material para estos dÃas si lo necesitáis
Se suspende la clase del martes 26 de marzo debido a un viaje de trabajo del profesor.
Está disponible en la página de ejercicios una hoja de ejercicios sobre algoritmos de dividir para vencer (en caso de entregar alguno de ellos, debe hacerse no más tarde del 09/04/2013).
He detectado que algunos siguen pensando que el coste de la creación de un montÃculo (heap) con n elementos está en O(n log n). Pues bien, haciendo el “cálculo fino” (penúltima transparencia del siguiente fichero) puede verse que realmente ese coste está en O(n).
Puede verse en detalle en el libro [CLRS09, pp. 151-169].
