UEA: Diseño de Algoritmos
Trimestre: 2007 Invierno
Entrega: 9 de marzo de 2007 a las 10pm

Problema 1: Diseñe un algoritmo usando la técnica de programación dinámica para resolver el siguiente problema: Sea N un entero positivo y A un arreglo A[1], A[2], ..., A[N] de enteros positivos. Los índices 1 <= I1 < I2 < ... < IK <= N forman un subarreglo ascendente de A de longitud K si se cumple que A[I1] < A[I2] < ... < A[IK]. Su algoritmo deberá encontrar un subarreglo ascendente de A con la mayor longitud posible. Por ejemplo, si A = [3, 1, 4, 1, 5, 9, 2, 6, 5] entonces los índices I1 = 1, I2 = 3, I3 = 5 e I4 = 8 forman el subarreglo ascendente [3, 4, 5, 6] de longitud 4. Escriba un programa llamado arreglo basado en su algoritmo que acepte como entrada el entero positivo N y un arreglo A de N enteros positivos y que escriba como salida la máxima longitud K de un subarreglo ascendente de A seguido de los K índices correspondientes. De nuevo, si la entrada fuera 9 3 1 4 1 5 9 2 6 5 entonces la salida podría ser 4 1 3 5 8. Puede suponer que 1 <= N <= 1000 y que A es un arreglo de int. Notas: Observe que puede haber más de una salida correcta y que el primer número de la entrada y el primer número de la salida indican cuántos números siguen.

Problema 2: Diseñe un algoritmo usando la técnica de programación dinámica para resolver el siguiente problema: Un estudiante está cursando M materias y le quedan D días para estudiar. La principal preocupación del estudiante es no reprobar todas las materias. Si la probabilidad de reprobar cada una de las M materias es p1, p2, ..., pM entonces la probabilidad de reprobar todas las materias es el producto p1p2...pM. La probabilidad de reprobar una materia depende del número de días completos que le dedique a estudiar esa materia. Usted tiene una tabla P que para cada materia J (con 1 <= J <= M) y cada número de días I (con 0 <= I <= D) dice la probabilidad PI,J de que el estudiante repruebe la materia J si la estudia I días. Su algoritmo deberá encontrar cuántos días deberá de estudiar el estudiante cada una de sus M materias para minimizar la probabilidad de que repruebe todas sus materias. Por ejemplo, si M = 3, D = 4 y la tabla P dice que
P
 0 días
 1 día
 2 días
 3 días
 4 días
Materia 1
 0.8
 0.7
 0.65
 0.62
 0.6
Materia 2
 0.75
 0.7
 0.67
 0.65
 0.62
Materia 3
 0.9
 0.7
 0.6
 0.55
 0.5
entonces el estudiante deberá estudiar 1 día la materia 1, 0 días la materia 2 y 3 días la materia 3 (para una probabilidad de 0.7*0.75*0.55 = 0.28875). Escriba un programa llamado estudia basado en su algoritmo que acepte como entrada los enteros M y D y una tabla P de flotantes con M renglones y D+1 columnas como la descrita arriba y que escriba como salida la probabilidad pedida seguida de un vector de M enteros indicando cuántos días debe de estudiar cada una de las M materias. De nuevo, si la entrada fuera
3 4
0.8 0.7 0.65 0.62 0.6
0.75 0.7 0.67 0.65 0.62
0.9 0.7 0.6 0.55 0.5
entonces la salida podría ser 0.28875 1 0 3. Puede suponer que 1 <= M <= 10 y que 1 <= D <= 100. Nota: Use el tipo double para todos los flotantes y observe que puede haber más de una salida correcta.