No es extraño que en entrevistas de trabajo relacionadas con la Computación aparezcan problemas resolubles mediante programación dinámica.

Aquí hay algunos de ellos:

What are the top 10 most popular dynamic programming problems among interviewers?

“Integer multiplication in time O(n log n)”,
por David Harvey y Joris Van Der Hoeven.

Esto supondría un avance importante en relación con una conjetura realizada en 1971 por Schonhage y Strassen.

Por supuesto, el interés es teórico (de momento). Es válido para enteros de más de 2⁴⁰⁹⁶ bits.

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

Leer esta anotación: http://webdiis.unizar.es/asignaturas/AB/?p=1009

Aquí y aquí.

.

Los siguientes párrafos están extraídos de este informe de la Oficina Ejecutiva del Presidente de los Estados Unidos: Report to the President and Congress. Designing a digital future: Federally funded research and development in networking and information technology (página 71, diciembre, 2010).

Progress in Algorithms Beats Moore’s Law

Everyone knows Moore’s Law –a prediction made in 1965 by Intel co-founder Gordon Moore that the density of transistors in integrated circuits would continue to double every 1 to 2 years.

Fewer people appreciate the extraordinary innovation that is needed to translate increased transistor density into improved system performance. This effort requires new approaches to integrated circuit design, and new supporting design tools, that allow the design of integrated circuits with hundreds of millions or even billions of transistors, compared to the tens of thousands that were the norm 30 years ago. It requires new processor architectures that take advantage of these transistors, and new system architectures that take advantage of these processors. It requires new approaches for the system software, programming languages, and applications that run on top of this hardware. All of this is the work of computer scientists and computer engineers.

Even more remarkable –and even less widely understood– is that in many areas, performance gains due to improvements in algorithms have vastly exceeded even the dramatic performance gains due to increased processor speed.

The algorithms that we use today for speech recognition, for natural language translation, for chess playing, for logistics planning, have evolved remarkably in the past decade. It’s difficult to quantify the improvement, though, because it is as much in the realm of quality as of execution time.

In the field of numerical algorithms, however, the improvement can be quantified. Here is just one example, provided by Professor Martin Grötschel of Konrad-Zuse-Zentrum für Informationstechnik Berlin. Grötschel, an expert in optimization, observes that a benchmark production planning model solved using linear programming would have taken 82 years to solve in 1988, using the computers and the linear programming algorithms of the day. Fifteen years later –in 2003– this same model could be solved in roughly 1 minute, an improvement by a factor of roughly 43 million. Of this, a factor of roughly 1,000 was due to increased processor speed, whereas a factor of roughly 43,000 was due to improvements in algorithms! Grötschel also cites an algorithmic improvement of roughly 30,000 for mixed integer programming between 1991 and 2008.

The design and analysis of algorithms, and the study of the inherent computational complexity of problems, are fundamental subfields of computer science.

Un ejemplo reciente de aplicación es el planteado en este artículo, en el que se presenta un algoritmo de ramificación y poda para la solución del problema de balance de flota en un sistema de bicicletas de uso compartido:

“A branch-and-bound algorithm for solving the static rebalancing problem in bicycle-sharing systems”, por A.A. Kadri, I. Kacem y K. Labadi; en Computers & Industrial Engineering, Vol. 95, May 2016, Pág. 41–52 (el artículo puede verse completo o descargar el PDF de forma gratuita desde la red de Unizar).

Sistema de bicicletas de uso compartido (© artículo enlazado arriba)

No es extraño que en entrevistas de trabajo relacionadas con la Computación aparezcan problemas resolubles mediante programación dinámica.

Aquí hay algunos de ellos:

What are the top 10 most popular dynamic programming problems among interviewers?

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

“Simplex is not a polynomial time algorithm. Certain rare kinds of linear programs cause it to go from one corner of the feasible region to a better corner and then to a still better one, and so on for an exponential number of steps. For a long time, linear programming was considered a paradox, a problem that can be solved in practice, but not in theory!

Then, in 1979, a young Soviet mathematician called Leonid Khachiyan came up with the ellipsoid algorithm, one that is very different from simplex, extremely simple in its conception (but sophisticated in its proof) and yet one that solves any linear program in polynomial time. Instead of chasing the solution from one corner of the polyhedron to the next, Khachiyan’s algorithm confines it to smaller and smaller ellipsoids (skewed highdimensional balls). When this algorithm was announced, it became a kind of “"mathematical Sputnik", a splashy achievement that had the U.S. establishment worried, in the height of the Cold War, about the possible scientific superiority of the Soviet Union. The ellipsoid algorithm turned out to be an important theoretical advance, but did not compete well with simplex in practice. The paradox of linear programming deepened: A problem with two algorithms, one that is efficient in theory, and one that is efficient in practice!

A few years later Narendra Karmarkar, a graduate student at University of California, Berkeley, came up with a completely different idea, which led to another provably polynomial algorithm for linear programming. Karmarkar’s algorithm is known as the interior point method, because it does just that: it dashes to the optimum corner not by hopping from corner to corner on the surface of the polyhedron like simplex does, but by cutting a clever path in the interior of the polyhedron. And it does perform well in practice.

But perhaps the greatest advance in linear programming algorithms was not Khachiyan’s theoretical break through or Karmarkar’s novel approach, but an unexpected consequence of the latter: the fierce competition between the two approaches, simplex and interior point, resulted in the development of very fast code for linear programming.”

(Credit: S. Dasgupta, C. H. Papadimitriou, and U. V. Vazirani, Algorithms, McGraw-Hill, 2008.)