[Iremos publicando noticias. Para recibirlas, puedes añadir este enlace: "RSS de las entradas" en tu agregador de noticias o bien seguirnos en Twitter.]
Muchos de los problemas que afrontan las grandes empresas informáticas no podrían abordarse si no existieran algoritmos eficientes que los resolvieran. Ejemplos de estos problemas incluyen el tratamiento de grandes volúmenes de datos, la optimización del rendimiento de sistemas, la realización de búsquedas múltiples, etc. En sus ofertas de empleo para expertos en computación, estas empresas solicitan a menudo propuestas para solucionar problemas de programación concretos.
Dropbox es una popular empresa internacional que ofrece un servicio gratuito de alojamiento de archivos. En su página web:
https://www.dropbox.com/jobs/challenges
solicita a los aspirantes a trabajar en la empresa soluciones para tres problemas de programación. Echémosle un vistazo al problema “The Dropbox Diet”.
La entrada del problema consiste en una lista de pares, cada par está compuesto por una cadena de caracteres que representa una actividad y un número entero (positivo o negativo) que representa una cantidad de calorías. ¿Qué debe hacer nuestro programa? Muy sencillo, encontrar un conjunto no vacío de actividades cuya suma de calorías sea cero (0). Si no existe tal conjunto, la salida del programa debe ser “no hay solución”.
Aunque sencillo de enunciar, el problema propuesto es equivalente al problema de la suma de subconjuntos (http://en.wikipedia.org/wiki/Subset_sum_problem), que es NP-completo. Por tanto encontrar un algoritmo polinomial para resolverlo no sólo abriría la puerta grande de Dropbox, sino que solucionaría uno de los problemas seleccionados por el Clay Mathematics Institute como problema del milenio (http://www.claymath.org/millennium/P_vs_NP/). El premio por solucionar cualquiera de los problemas del milenio es de 106 dólares.
Uno de los temas que se tratará en Algoritmia Básica está relacionado con Programación Dinámica. Veremos que el uso de técnicas de Programación Dinámica permite desarrollar un algoritmo pseudo-polinómico para resolver el problema de la suma de conjuntos. De ahí a resolver el problema del milenio… sólo falta eliminar “pseudo”.
