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 el próximo esquema algorítmico que veremos en clase, 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.

.

.

“A new kind of cipher that would take millions of years to break.”

Ese era el título del artículo publicado por Martin Gardner (conocidísimo divulgador científico norteamericano) en la sección Mathematical Games de la revista Scientific American, vol. 237(2), pp. 120-124, en agosto de 1977 (puede descargarse aquí).

En él, Gardner describía el método de criptografía de clave pública conocido como RSA, recién desarrollado por los investigadores del M.I.T. R.L. Rivest, A. Shamir y L.M. Adleman, y que sería publicado un año después en su artículo:

R.L. Rivest, A. Shamir y L.M. Adleman: “A method for obtaining digital signatures and public-key cryptosystems”, Communications of the ACM, 21(2), pp. 120-126, 1978.

En el artículo divulgativo de Scientific American, Gardner publicaba además el reto de descifrar un mensaje cifrado por el grupo del M.I.T. (ver figura). El reto exigía factorizar un nº de 128 cifras. El primer lector que descifrase el mensaje sería premiado con una recompensa de 100 dólares por el M.I.T. Se estimaba entonces que eran necesarios 2 millones de veces la edad del Universo de cálculo ininterrumpido del mejor computador de aquel momento para descifrar el mensaje. El M.I.T. no estaba dispuesto a pagar los 100 dólares fácilmente…

En abril de 1994, Atkins, Graff, Lenstra y Leyland resolvieron el problema propuesto por Gardner en 1977 tras más de 6 meses de cálculo, utilizando unos 1600 computadores de todo el mundo trabajando como una máquina paralela virtual. Ganaron los 100 dólares prometidos y los donaron a la Free Software Foundation. La solución era:

The Magic Words are Squeamish Ossifrage

—————

Mañana veremos en clase los detalles del algoritmo RSA, como aplicación de los métodos eficientes de multiplicación y potenciación de números grandes que hemos visto en clase los días pasados.

Se han publicado en la página de problemas algunos ejercicios del tema que estamos viendo en clase.

.

Existe un algoritmo de coste asintótico lineal, en el caso peor, para el cálculo del 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) ).

Puede verse aquí.

Me habéis preguntado en clase si se conoce algún algoritmo mejor que el de coste cuadrático visto en clase para el problema de la transparencia 84 de algoritmos voraces.

He encontrado una respuesta en el libro Computer Algorithms, de Ellis Horowitz, Sartaj Sahni, and Sanguthevar Rajasekaran (Computer Science Press, 1998):

It can be reduced from O(n²) to nearly O(n) by using the disjoint set union and find algorithms…

Se refiere a los algoritmos para implementar conjuntos disjuntos o clases de equivalencia (union-find) que vimos en clase hace unos días (descritos en la página de material adicional). El coste de la solución propuesta es O(n α(2n,n)), donde α(2n,n) es la inversa de la función de Ackermann (y crece muy, muy despacio, siendo prácticamente imposible encontrar un n para el que la función α valga más de 4), por lo que el coste de la solución resulta, prácticamente, lineal.

Os dejo en la página de material adicional esta sección del libro de Horowitz et al. en la que se describe el problema y algo sobre esa solución (no es fácil de leer).

.

Hemos visto en clase que algunos problemas poseen la estructura algebraica subyacente de matroide y en ese caso pueden resolverse correctamente con un algoritmo voraz.

Existe una extensión del concepto de matroide que permite llegar un poco más lejos, para resolver más problemas con algoritmos voraces: se trata de los gridoides. En Wikipedia o en este informe (acceso con clave) se explica qué son.

Pero tampoco los gridoides caracterizan exactamente todos los problemas que pueden resolverse con un algoritmo voraz.

Hay trabajos posteriores que llegan más allá. Por ejemplo, en el trabajo “An Exact Characterization of Greedy Structures“ (acceso con clave), sus autores, Paul Helman, Bernard M.E. Moret y Henry D. Shapiro, presentan una caracterización para una estructura de problemas para los que un algoritmo voraz calcula una solución óptima.

Y la investigación continúa…

Podría pensarse que el coste de la creación de un montículo (heap) con n elementos está en O(n log n), dado que hay que insertar n datos y cada inserción, en el caso peor, sería O(log n).
Pues bien, haciendo el “cálculo fino” (penúltima transparencia de este fichero) puede demostrarse que realmente ese coste está en O(n).
Puede verse también, en detalle, en el libro [CLRS09, pp. 151-169].

Como se dijo en clase y aparece en la Guía académica oficial, se estima que es necesario un trabajo personal no presencial de 4 horas semanales, en promedio, para superar esta asignatura (además de la asistencia a clase y de la realización de las prácticas de laboratorio).

En la página de “Problemas” podéis encontrar ya algunos enunciados de ejercicios para ir trabajando en casa.

Hoy, para ver una implementación eficiente del algoritmo de Kruskal, hemos hablado de la función α como inversa de la función de Ackerman. Si alguien anda buscando crecimientos grandes para perder un poco el tiempo, puede echar un vistazo a la notación sagital de Knuth, a la notación sagital encadenada de Conway, a la notación de Steinhaus–Moser, a los números de Graham, o a los números del castor ataread. Un ensayo sobre quién puede decir el número más grande, aquí.