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

sguenos en twitter

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(nlog 3)  ( ≈ O(n1,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 1 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)).

En la página de material adicional de esta web puede encontrarse:

  • Un artículo que describe un par de métodos de ordenación por fusión (o mezcla) “in situ” y analiza su coste (acceso con clave aquí).
  • Un par de capítulos de libros sobre métodos de ordenación en memoria externa basados en la idea de la ordenación por fusión (acceso con clave aquí y aquí).
  • La demostración de que el coste promedio del quicksort está en n log n (acceso con clave aquí).
  • Comparación práctica de velocidades de métodos de ordenación: un appletotro applet.

Se ha publicado una hoja de problemas (algoritmos de divide y vencerás).

Una compañía de televisión por cable pretende dar servicio a un nuevo barrio de la ciudad. Tiene restricciones impuestas por el ayuntamiento, de manera que sólo puede echar el cable por algunas de las calles. Además, algunas de las conexiones posibles entre las casas serían muy costosas, por ser demasiado largas o por requerir un soterramiento demasiado profundo. Así que la compañía tiene que calcular la forma más barata de llegar a todas las casas por medio del cable.

 

 

La solución de este problema se obtiene representando las conexiones posibles entre las casas con un grafo (las casas serían los vértices y las aristas las calles por las que se tiene permiso para echar el cable), y calculando el árbol de recubrimiento de peso mínimo (minimum spanning tree).

Los dos algoritmos más conocidos para resolver el problema anterior, el de Prim y el de Kruskal, son ejemplos típicos de algoritmos voraces. En esta asignatura veremos en qué consiste el esquema voraz de resolución de problemas y en qué casos da lugar a algoritmos correctos y por qué.

Haz clic en la imagen inferior para ver un applet que resuelve el problema.