PDF de programación - Problemas de algoritmia avanzada

Problemas de Algoritmia Avanzada

Curso 2004–2005

25 de noviembre de 2004

Advertencia: todos los problemas descritos en este documento
admiten diversas formas de ser resueltos, por lo que no debe su-
ponerse que, necesariamente, otras formas de resolver el problema
son incorrectas. En caso de duda, consúltese con los profesores de
la asignatura.

Índice

1. Programación dinámica

2. Ramificación y poda

3. Simulación

. Soluciones de los ejercicios

2

7

8

10

1

1. Programación dinámica
Ejercicio 1. Una empresa constructora desea subcontratar para las distin-
tas tareas que hay que ejecutar (cada una de las cuales puede considerarse
como una etapa del trabajo) a otras empresas. El coste de cada tarea depen-
de de qué decisión se tomó en la etapa anterior, de forma que las tareas se
pueden representar como un grafo multietapa en el que los nodos se disponen
en niveles (etapas) y las aristas van siempre de los nodos de una etapa a los
nodos de la siguiente, tal y como se refleja en el ejemplo de la figura 1. Cada
arista (x, y) tiene además un coste asociado d(x, y). Escribe un algoritmo de
programación dinámica para encontrar la secuencia óptima de decisiones.

Figura 1: Un ejemplo de grafo multietapa.

Ejercicio 2. Dada una secuencia finita de números enteros estrictamente
positivos S = {a1, a2, ..., aN}, se desea extraer una subsecuencia tan larga
como sea posible que sea no decreciente. Por ejemplo, si

S = {7, 2, 6, 5, 6}

las subsecuencias {2, 5, 6} y {2, 6, 6} son no decrecientes y de longitud máxi-
ma. Escribe un algoritmo recursivo y otro de programación dinámica ite-
rativa para resolver este problema. Dibuja el árbol de llamadas que genera
la función recursiva para los datos del ejemplo y marca aquellos nodos que
son calculados si se usa un almacén para evitar repeticiones. Compara este
número con el número de cálculos que hace el algoritmo iterativo.
Ejercicio 3. Un robot con dos brazos debe soldar una serie de puntos
r1, . . . , rN en un circuito. Aunque el orden de soldadura no puede cambiar-
se, puede elegirse qué brazo realizará la soldadura. Se quiere encontrar la

2

k=0k=2k=2k=3abcdeFS35765483612 secuencia de movimientos que minimiza la longitud total de los desplaza-
mientos realizados si inicialmente ambos brazos se encuentran en la posición
r0 y las distancias son conocidas.

d
1
2
3
4

0
100
89
45
61

1
-

100
63
108

2
100

-
60
36

3
63
60
-
50

r2◦

◦r3

r4◦

r0◦

◦r1

Figura 2: Un caso de circuito de soldadura.

Comprueba que la solución voraz no es correcta para el ejemplo de la
figura 2.
Escribe una función de programación dinámica recursiva que permita
resolver el problema y analiza su coste temporal en función de N .
Dibuja el árbol de llamadas recursivas que se genera para los datos del
ejemplo y escribe el resultado en cada nodo.
Compara el número de cálculos con el de un esquema recursivo puro y
con el de un esquema iterativo.

Ejercicio 4. Escribe un programa monedas(M ) que calcule el número míni-
mo de monedas necesarias para conseguir exactamente la cantidad M . Para
ello, debemos utilizar un máximo de ci monedas de valor vi. Si no es posible
obtener la cantidad M , el programa escribirá ∞.

denominación v1
c1

disponible

v2
c2

. . .
. . .

vN
cN

Ejercicio 5. El personal de la universidad está organizado jerárquicamente
como un árbol cuya raíz ocupa el rector. Para el vino de honor de fin de curso
se quiere invitar al máximo posible de empleados de forma que no coincida
ningún empleado con su superior inmediato. Escribe un algoritmo de progra-
mación dinámica para calcular el número máximo f (x, a) de subordinados
de la persona x a los que se puede invitar si x acude al ágape (a = 1) o si
no acude (a = 0). Para ello, conocemos el conjunto s(x) de subordinados
inmediatos de x (nodos del árbol cuyo padre es x).

3

Ejercicio 6. Al volver de Polinesia, un explorador llevaba una maleta de
capacidad M completamente llena con objetos de gran valor. Cada objeto
proviene de una isla diferente y los sistemas de transporte permiten viajar
entre ellas según un grafo multietapa como el de la figura 1, en el que cada
nodo q contiene el peso w(q) del objeto situado en la isla. Escribe un algo-
ritmo lo más eficiente posible para encontrar una ruta que permita recoger
K objetos (uno por etapa) con peso total M .
Ejercicio 7. Un problema que aparece con frecuencia en las redes de or-
denadores es el de encontrar la ruta que permite transmitir los datos de
un ordenador S a otro F a mayor velocidad. Las conexiones entre máquinas
permiten una velocidad máxima de transmisión que supondremos idéntica en
ambos sentidos. La velocidad de transmisión a través de una ruta que utiliza
varias conexiones está determinada en la práctica por la conexión más lenta
(véase la figura 3). Escribe un algoritmo recursivo para resolver el problema
adecuado para el uso de programación dinámica.

Figura 3: Ejemplo de grafo de conexiones. Un camino de velocidad máxima entre S
y F aparece marcado como línea de puntos. Las conexiones no dibujadas equivalen
a lineas de velocidad cero.

Ejercicio 8. Una empresa de alquiler de vehículos debe renovar su flota de
forma que ningún automóvil en activo tenga más de M = 10 meses y para
planificar las compras dispone de la previsión del precio de los automóviles
para los próximos T = 100 meses:

w1, w2, ..., wT

Los precios pueden subir o bajar cada mes y el objetivo es mantener los
vehículos hasta el mes T (y medio) gastando el menor dinero posible en ad-
quisiciones. Escribe un algoritmo recursivo y justifica que el coste temporal es

4

acdbFS634322231 exponencial en función de T . Transfórmalo mediante programación dinámica
recursiva y justifica el nuevo coste en función de T y M .
Ejercicio 9. Algunas normas tipográficas establecen que las líneas deben
contener entre 40 y 60 caracteres. Supongamos que no queremos partir las
palabras y que conocemos los tamaños (incluidos los signos de puntuación y
espacios en blanco adyacentes) s1, s2, ...sN de las N palabras de un párrafo
de M líneas. Si el objetivo es minimizar la longitud de la línea más larga
del párrafo, escribe un algoritmo de programación dinámica recursiva que
minimice la longitud de la línea más larga de un párrafo. A continuación,
dibuja una tabla A[N ][M ] con los valores que calcula el algoritmo anterior si
la secuencia de tamaños es 20, 15, 12, 12, 24, 18 , 17, 14, 10 y el número de
líneas M = 3. ¿Cuál es la solución óptima? Trasforma el algoritmo anterior
en uno iterativo y compara la eficiencia de uno y otro.
Ejercicio 10. Un estudiante se ha matriculado de tres asignaturas. Su fa-
milia le ha exigido que, para irse de vacaciones, apruebe al menos una de
ellas. Le quedan cuatro días para estudiar y no le da buen resultado estudiar
más de una asignatura diferente el mismo día.

La tabla siguiente nos da la probabilidad pk(t) de suspender la asignatura
k si se dedican t días de estudio a esa asignatura. ¿Cuántos días debe dedicar
a cada asignatura?

t(días) AA TBO TV
0.72
0.64
0.58
0.54
0.52

0.61
0.55
0.52
0.46
0.41

0
1
2
3
4

0.90
0.80
0.70
0.60
0.50

Ejercicio 11. El algoritmo de Cocke, Younger y Kasami (CYK) permi-
te determinar si una frase es correcta sintácticamente y, en ese caso, cuál
es su árbol de análisis sintáctico, según una gramática escrita en forma de
Chomsky. Una gramática G = (V, T, R, S) en forma de Chomsky consiste en:

un conjunto finito V = {A1, A2, ..., A|V |} de símbolos variables;
un alfabeto T = {a1, a2, ..., a|T|} de símbolos terminales que forman las
frases;
un símbolo inicial S ∈ V ;

un conjunto finito R de reglas formado por

5

1.

2.

reglas de sustitución de una variable por un terminal del tipo
Ai → ak, y
reglas de sustitución de una variable por dos variables como Ai →
AjAk.

Dada la gramática G, escribiremos λ2(i, j) = {k : Ak → AiAj ∈ R} y
λ1(a) = {k : Ak → a ∈ R}. Justifica que el algoritmo CYK puede deducirse
de la aplicación de programación dinámica a un programa recursivo simple.
Ejercicio 12. Para seguir una dieta adecuada queremos elegir una combi-
nación de platos de un menú de forma que el precio total no supere nuestro
presupuesto M , el valor proteico sea como mínimo W y el valor calórico lo
más bajo posible. Para cada plato i conocemos su precio pi, su contenido
en proteínas qi y calorías ci. Diseña un algoritmo para encontrar la selección
óptima.
Ejercicio 13. Tenemos N programas de tamaños w1, w2, ..., wN y de un
número ilimitado de discos de almacenamiento de M kilobytes (por ejemplo,
M = 1400). Si los programas no pueden fragmentarse en discos distintos,
¿cuál es el número mínimo de discos necesario para guardar todos los pro-
gramas?
Ejercicio 14. Una empresa de suministro de agua dispone de N cubas de
capacidades c1, c2, . . . , cN y debe transportar M litros de agua. Para disminuir
el riesgo de volcado de los camiones, las cubas deben ir lo más llenas posible.
Si las cubas sólo pueden usarse una vez:

1. Escribe un algoritmo de programación dinámica recursiva que permita
calcular f (n, m), el mínimo espacio sobrante cuando se deben trans-
portar m litros usando sólo cubas comprendidas entre la 1 y la n.

2. Dibuja el árbol de llamadas recursivas para el siguiente ejemplo: N = 4,
M = 100, c1 = 55, c2 = 40, c2 = 35, c3 = 15. Escribe el valor de n, m y
f (n, m) en cada nodo.

3. Compara el coste de este algoritmo con uno recursivo puro y con una

versión iterativa del mismo.

Ejercicio 15.

Un problema que se plantea frecuentemente en la secuenciación de DNA
es encontrar fragmentos comunes en varias cadenas. Las cadenas de DNA se
pueden representar como secuencias de nucleótidos (adenina, timina, citosina
y guanina) del tipo GATTACACAGATA... Escribe un algoritmo de programa-
ción dinámica recursiva para encontrar la subsecuencia común más larga a

6

tres cadenas x, y y z de este tipo. Justifica cuál es el c