.

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:

1. Definir de manera precisa una función parametrizada tal que, para algunos valores de sus parámetros, nos aporte la solución del problema originalmente propuesto.
2. Escribir una ecuación recurrente (o relación de recurrencia) para esa función parametrizada, detallando para qué valores de sus parámetros es válida la ecuación, y escribir los casos base de la función (casos particulares de sus parámetros para los que se puede expresar el valor de la función sin necesidad de recurrencias).
3. Detallar qué tabla es necesaria para almacenar los valores de la función parametrizada, y qué orden puede seguirse para calcularla. Detallar si se precisa alguna otra tabla auxiliar para reconstruir la solución para la que la función alcanza el óptimo.
4. Escribir en pseudocódigo el algoritmo para rellenar la tabla de los valores óptimos de la función parametrizada y, si se solicita, escribir el algoritmo para construir la solución para la que se alcanza el óptimo del problema original.

Ejemplo de aplicación de estos pasos para el problema de “Multiplicación de una secuencia de matrices” (transparencias 31 a 40 de clase):

1. Función m(i,j) = número mínimo de multiplicaciones de escalares necesarias para multiplicar la subsecuencia de matrices M_i, …, M_j.
   El problema originalmente propuesto es calcular m(1,n).
2. m(i,i) = 0, para i = 1..n (casos base).
   m(i,j) = min_1≤k<j {m(i,k)+m(k+1,j)+d_i-1d_kd_j}, para todos los i, j tales que 1≤i<j≤n.
3. Matriz triangular superior para almacenar los m(i,j), con 1≤i≤j≤n. Puede calcularse por diagonales, empezando por la diagonal principal y, desde ahí, hacia arriba.
   Matriz auxiliar de iguales dimensiones para almacenar los índices k para los que se consigue el mínimo de la ecuación recurrente para cada uno de los m(i,j). Es la matriz km[i,j] en el algoritmo de la transparencia nº 38.
4. Algoritmos de la página 38 y de la página 40 de las transparencias.

¿Tenéis alguna idea para la función parametrizada (punto (1) de los anteriores) de alguno de los problemas de la hoja? El foro de Moodle es un buen sitio para compartir ideas…

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).

Se han publicado en moodle (en este enlace).

Se puede leer aquí el artículo de divulgación:

Researchers store images in DNA, search for and perfectly retrieve them.

Y aquí puede encontrarse el artículo de investigación:

A DNA-Based Archival Storage System (por James Bornholt, Randolph Lopez, Douglas M. Carmean, Luis Ceze, Georg Seelig y Karin Strauss).

La prueba escrita intermedia (prevista en la guía docente) será el miércoles 6 de abril a las 15:00 (duración: 2 horas) en el aula 12 del edificio Ada Byron.

Consistirá en un par de problemas de los temas de algoritmos voraces y divide y vencerás.

Se permitirá utilizar material impreso (transparencias, libros…) pero no se permitirá el uso de dispositivos electrónicos (teléfonos, tabletas, etc).

.

Punteros a cosas (curiosidades) mencionadas hoy en clase:

• algoritmo de coste lineal para el cálculo del k-ésimo elemento de un vector (y por tanto para el cálculo de la mediana)
• orígenes del algoritmo de Karatsuba
• premio Turing de este año
  • su algoritmo (ojo, hay una errata en esa página; cuando en un párrafo de la parte final habla del “problema del algoritmo discreto”, debería decir el “problema del logaritmo discreto”)

.

Como vimos ayer en clase, el algoritmo voraz para devolver una cantidad de dinero con el menor número posible de monedas es correcto (es decir, calcula el número mínimo de monedas) para los sistemas de monedas “habituales”, como el del Euro o el Dólar, que suelen denominarse sistemas canónicos de monedas.

Sin embargo, en general, el voraz no es un algoritmo correcto, no calcula el valor mínimo (ejemplo de monedas marcianas).

Aquí podéis acceder (sólo desde la red de Unizar, o desde vuestra casa usando https://vpn.unizar.es) a un artículo reciente que estudia el sistema de monedas que se requiere para que el algoritmo voraz sea correcto (ojo, no es fácil de leer porque, como ocurre con la mayoría de trabajos de investigación, requiere cierta experiencia en el tema):

Xuan Cai: “Canonical Coin Systems for CHANGE-MAKING Problems“. Proceedings of the Ninth International Conference on Hybrid Intelligent Systems, pp. 499–504. Shenyang, China, August 12-14, 2009.

Inicio de clases de Algoritmia Básica (curso 2015-16): el 9 de febrero a las 15:00 horas en el aula 12 del edificio Ada Byron.

Se ha actualizado la información en esta web para el curso 2015-16 (profesores, evaluación, guía oficial, etc.).