Examen 4 de Análisis y Diseño de Algoritmos
Trimestre 2015 Invierno
Entrega: 6 de abril de 2015 a las 13:00 en mi oficina
Pregunta 1: Propón tres algoritmos glotones 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 una vez, 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). Nota:
al menos uno de los tres algoritmos que propangas debe resolver
el problema, para los otros dos debes mostrar casos en los que no
sirva.
Pregunta 2: Diseña y analiza un algoritmo glotón que resuelva
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).
Pregunta 3: Investiga sobre cinco problemas NP completos que
no hayamos mencionado en clase. En particular, debes dar el nombre
del problema, la definición del problema, la referencia de dónde se
demostró que era NP completo y al menos una aplicación práctica de
ese problema.