Se ha publicado una hoja de problemas (algoritmos de ramificación y poda).

Desde hoy, 9 de mayo, hasta el próximo día 30, está abierto el periodo de realización de encuestas sobre la docencia de la asignatura:

http://encuestas.unizar.es/

Las encuestas son muy importantes para facilitar la mejora, año a año, de la asignatura. Os rogamos dediquéis unos minutos de vuestro tiempo para responderlas.

El curso pasado alcanzamos un 72.73% de respuestas en esta asignatura. Nos gustaría igualar o superar esa cifra.

En la transparencia 55 de programación dinámica quedó como ejercicio el cálculo de los nodos de las secuencias que componen los caminos mínimos desde cualquier nodo i a cualquier nodo j. Hay varias formas de resolverlo. Una muy sencilla consiste en guardar una matriz adicional C[v,w] en la que se almacene un nodo u que esté en el camino mínimo de v a w. Para ello, en el interior de los tres bucles del algoritmo, hay que modificar la instrucción condicional añadiendo la actualización de esa matriz C:

  si D[i,k]+D[k,j]<D[i,j] entonces
    D[i,j]:=D[i,k]+D[k,j];
    C[i,j]:=k
  fsi

La matriz se ha debido inicializar al principio del algoritmo (por ejemplo con valores nulos). El algoritmo para el cálculo del camino mínimo de i a j, usando la matriz C, queda como:

  procedimiento camino(ent i,j:vértice;
                       ent C:vector[vértice,vértice] de entero)
  variable k:vértice
  principio
    k:=C[i,j];
    si k≠0 entonces
      camino(i,k,C);
      escribir(k);
      camino(k,j,C)
    fsi
  fin

Se han publicado en Moodle.

.

Las soluciones de programación dinámica aparecen en prácticamente todos los dominios de aplicación. Seleccionamos aquí algunos ejemplos en Visión, Juegos, Robótica y Bioinformática:

1. Dynamic Programming and Graph Algorithms in Computer Vision: A Survey.
2. Dynamic programming and board games: A survey (acceso restringido con usurio/clave).
3. Some dynamic programming problems useful to solve the mobile robot localization problem.
4. Systematic Dynamic Programming in Bioinformatics.

Uno de los ejemplos más sencillos (más que los vistos en clase) de aplicación de la programación dinámica es el cálculo del término n-ésimo de la sucesión de Fibonacci.

La definición de la sucesión o función de Fibonacci es:

Fib(n) = 1, si n = 0,1

Fib(n) = Fib(n-1) + Fib(n-2), si n > 1

La solución más natural para calcular el término n-ésimo sería, por tanto, traducir esa definición recursiva de la función a nuestro pseudocódigo:

  función FibRec(n:natural) devuelve natural
  principio
    si n≤1 entonces
      devuelve 1
    sino
      devuelve FibRec(n-1)+FibRec(n-2)
    fsi
  fin

El inconveniente de esa solución es su coste, exponencial en el valor de n. La ineficiencia de FibRec se debe a que se producen llamadas repetidas de la función para calcular valores que ya se habían calculado previamente, no se ha conservado su resultado, y por tanto hay que volver a calcularlos.

La solución de programación dinámica pasaría por utilizar una tabla auxiliar en la que almacenar las soluciones de todos los “subproblemas” (valores de Fib para valores menores que n) resueltos:

El algoritmo iterativo para devolver el n-ésimo término de Fibonacci calculando la tabla sería:

  función FibIterProto(n:natural) devuelve natural
  variables i:natural; T:vector[0..n] de natural
  principio
    si n≤1 entonces
      devuelve 1
    sino
      T[0]:=1;
      T[1]:=1;
      para i:=2 hasta n hacer
        T[i]:=T[i-1]+T[i-2]
      fpara;
      devuelve T[n]
    fsi
  fin 

El último paso en la mejora proviene de detectar que en el algoritmo anterior no es necesario todo el vector auxiliar, pues basta con almacenar los dos últimos valores calculados:

  función FibIter(n:natural) devuelve natural
  variables i,suma,x,y:natural {x e y para almacenar los dos últimos
                 términos calculados y suma para almacenar el actual}
  principio
    si n≤1 entonces
      devuelve 1
    sino
      x:=1;
      y:=1;
      para i:=2 hasta n hacer
        suma:=x+y;
        y:=x;
        x:=suma
      fpara;
      devuelve suma
    fsi
  fin 

Se ha publicado una hoja de problemas (algoritmos de programación dinámica).

La prueba escrita intermedia (prevista en la guía docente) será el miércoles 29 de marzo 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).

Existe un algoritmo de coste asintótico lineal, en el caso peor, para el problema de selección, es decir, para el cálculo del k-ésimo menor elemento (o estadístico de orden k) de un vector de tamaño n. Por tanto, en particular, puede usarse para el cálculo de la mediana (haciendo k = techo(n/2) ).

Os lo incluyo debajo, extraído del libro Introducion to Algorithms, de Cormen, Leiserson, Rivest y Stein.

Una vez se dispone de un algoritmo de coste lineal (caso peor) para el cálculo de la mediana, existe una modificación del algoritmo quicksort que tiene coste O(n logn) en el caso peor. Consiste en elegir la mediana como el pivote que se utiliza para la partición del vector en dos trozos, en cada llamada recursiva del quicksort.

.

El algoritmo conocido como “de Karatsuba y Ofman” para multiplicar enteros de n cifras con un coste asintótico en O(n^{log 3})  ( ≈ O(n^1,59) )  aparece publicado en el artículo ”Multiplication of multidigit numbers on automata”, A. Karatsuba, Y. Ofman, en el nº 145, pp. 293-294, de las actas de la Academia de Ciencias de la extinta Unión Soviética (Doklady Akademii Nauk SSSR) en 1962.

Curiosamente, el mencionado artículo no fue escrito por Anatoli Alekséyevich Karatsuba (Grozny, URSS, 31 de enero de 1937 — Moscú, Rusia, 28 de septiembre de 2008) sino que, tal y como relata él mismo en su artículo “The complexity of computations” (publicado en Proceedings of the Steklov Mathematical Institute, vol. 211, pp. 169-183, 1995, copia local con clave aquí), fue escrito por Kolmogorov, probablemente ayudado por Ofman, y sin el conocimiento de Karatsuba, quien era realmente el autor del algoritmo:

[...] Later in 1962 Kolmogorov wrote a short article (probably in collaboration with Ofman) and published it in Doklady Akad. Nauk SSSR. The article was entitled: A. Karatsuba and Y. Ofman, “Multiplication of Multiplace Numbers on Automata” (Doklady Akad. Nauk SSSR, vol. 145, No. 2, pp. 293-294). I learned about the article only when I was given its reprints.

En el mismo artículo de 1995, Karatsuba reivindica su autoría:

In this section I present my algorithm for multiplying numbers. Now it is called the KML algorithm or, briefly, KML (Karatsuba Multiplication).

Anatoli Alekséyevich Karatsuba

Con posterioridad, se han desarrollado algoritmos asintóticamente más rápidos que el de Karatsuba, como el de Schönhage–Strassen (1971), de coste Θ(n log(n) log(log(n))), o el de Martin Fürer (2007), de coste n log(n) 2^{Θ(log*(n))}.