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?

Fecha/hora/lugar/: Miércoles 29 de abril, 16:00 h., aula 12 del edificio Ada Byron.

Breve descripción:

¿Cómo es la arquitectura de un producto software complejo? ¿Qué metodología se establece para controlar el ciclo de vida de desarrollo? ¿Cómo son los modelos de integración con otros sistemas corporativos? ¿Cómo es la infraestructura hardware y de comunicaciones requerida para el despliegue? ¿Cómo son las medidas de seguridad de la información de nivel alto? ¿Qué competencias y habilidades requiere la gestión de un proyecto de implantación software?

Ponente:

Fernando Cortés, CEO de Endalia, Ingeniero en Informática por la Universidad de Zaragoza, nos trasladará una visión global desde la perspectiva y la experiencia de proyectos de implantación de software para la gestión integral de capital humano en organizaciones como Airbus Group, La Caixa, Ineco, IBM, Esade, Banco Santander, Infojobs, entre otros.

La siguiente es una de las preguntas del reto del año pasado.

You are trying to solve a very complex problem. In order to simplify it, you have divided it into many sub tasks. Most of these sub-tasks can be run in parallel, but some are dependent on the previous resolution of other tasks. There is no limit on the number of tasks that can be run in parallel. Each task has an associated computation time.

You are be given a subset of these tasks. For each of them you need to specify what is the minimal computation time for resolving the task (you must consider task dependencies).

The relations between the tasks are represented in the file contained in this archive: in.zip. This file is in the following format:

#Number of tasks
n

#Task duration <- task x has an associated computation time of tx
x,tx

#Task dependencies <- the resolution of task x depends of previously
#                     solving tasks y,z,w
x,y,z,w

It is imposible for two different tasks to be dependent on the resolution of one common task:

#Task dependencies <- this is not valid
x,y
z,y

The expected output is the following format: taskId taskComputationTime

x tx
y ty
z tz

From the standard input you will receive a set of tasks for which to compute the total time in the following format:

x,y,z

Sample input file

#Number of tasks
6

#Task duration
0,2
1,3
2,4
3,9
4,7
5,9

#Task dependencies
0,4
3,0,1,2
4,5

Sample standard input for tasks to compute time

3,1,4

Sample output

3 27
1 3
4 16

Como veréis, si lo pensáis un poco, la solución no es difícil en este caso. Pero se pueden plantear problemas de planificación de tareas cuya solución es algo más complicada. Alguno de ellos veremos en la asignatura…

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 10⁶ 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”.