Son para trabajarlos en casa, antes del miércoles próximo.

• 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 applet, otro applet.

Son para trabajarlos en casa antes del martes 19 de marzo.

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

• 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 applet, otro applet.

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

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.