Tarea 9 de Análisis y Diseño de Algoritmos
Trimestre 2013 Otoño
Entrega: 6 de noviembre de 2013 a las 22:00.
Escribe un programa llamado cintaNN.c que implemente tu algoritmo
para la pregunta 1 del examen de abajo. La entrada para tu programa
será un entero N, seguido de las longitudes L1, L2,
..., LN, seguido de los enteros M1,
M2, ..., MN. Puedes suponer que todos estos
enteros están en el rango de 1 a 1000. La salida de tu programa
deberá ser el orden I1, ..., IN en el que se
deben almacenar los archivos.
Notas: Tus programas no
deben leer ni escribir nada adicional a lo que se indica en el
enunciado. El tiempo de ejecución de tus algoritmos será considerado
como parte de la evaluación.
Examen 4 de Análisis y Diseño de Algoritmos
Trimestre 2013 Otoño
Entrega: 6 de noviembre de 2013 a las 16:00 en mi oficina.
Pregunta 1 (5 puntos): Diseña y analiza un algoritmo glotón
para el siguiente problema: dados N archivos A1, A2,
..., AN de longitudes L1, L2, ...,
LN
que serán almacenados en una cinta y se leerán M1,
M2, ..., MN veces, encuentre el orden AI1,
AI2, ..., AIN en el que se deben almacenar de
modo que se minimice el tiempo total de lectura suponiendo que cada
lectura comienza con la cinta rebobinada hasta el principio, cada
lectura toma tiempo proporcional a la longitud de todos los archivos
anteriores al que se quiere leer, incluyéndolo (es decir, leer
el archivo AIK toma tiempo proporcional a LI1+LI2+...+LIK).
Este
problema es una generalización del visto en clase donde M1
= M2 = ... = MN = 1.
Pregunta 2 (5+5 puntos): Dada una gráfica G = (V, E) un ciclo de G de longitud k es una
sucesión de vértices y aristas v1, e1, v2,
e2, ..., vk, ek, vk+1 =
v1 tal que v1, v2, ..., vk
son todos distintos y ei es la arista que une a vi
con vi+1 para toda 1 <= i <= k. Considera los
siguientes tres problemas:
- HAMILTON: Dada una gráfica G = (V, E), ¿tendrá G un ciclo que
pase por todos sus vértices?
- CICLO: Dada una gráfica G = (V, E) y un número entero k,
¿tendrá G un ciclo de longitud al menos k?
- AGENTE: Dada una gráfica G = (V, E), un costo positivo para
cada arista de G y un número real c, ¿tendrá G un ciclo que pase
por todos sus vértices y que la suma de los costos de sus
aristas sea a lo más c?
Supón que HAMILTON es NP completo. Demuestra que (a) CICLO es NP
completo y que (b) AGENTE es NP completo.