Tarea 3 de Análisis de Algoritmos (2006 Otoño)

Fecha de entrega: 28 de noviembre de 2006 en clase

1. [3 puntos] Diseñe y analize un algoritmo glotón para el siguiente problema: dados N archivos A₁, A₂, ..., A_N de longitudes L₁, L₂, ..., L_N que serán almacenados en una cinta y se leerán M₁, M₂, ..., M_N veces, encuentre el orden A_I1, A_I2, ..., A_IN 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 A_IK toma tiempo proporcional a L_I1+L_I2+...+L_IK). Este problema es una generalización del visto en clase donde M₁ = M₂ = ... = M_N = 1.
   
2. [4 puntos] Una subgráfica S = (V, T) es un árbol abarcador de una gráfica no dirigida G = (V, E) si S es un árbol (es decir, si S es conexa y no tiene ciclos) y T es un subconjunto de E. Si cada arista de E tiene un costo, el costo de una subgráfica de G es la suma de los costos de sus aristas. Se puede encontrar un árbol abarcador de G de costo mínimo siguiendo el algoritmo de Kruskal (que a su vez utiliza el algoritmo de unión y búsqueda):
   
   1. Comience con T vacío y F la colección de conjuntos con exactamente un vértice de G.
   2. Ordene las aristas de G en orden ascendente por costo.
   3. Mientras F tenga al menos dos elementos:
   3.1. Sea (u,v) la siguiente arista según el orden.
   3.2. Si búsqueda(u) es diferente a búsqueda(v) entonces unión(u,v) y agrega a T la arista (u,v).
   
   Demuestre que al final del algoritmo la subgráfica S = (V, T) es un árbol abarcador de costo mínimo. Pista: primero demuestre que S es un árbol abarcador y luego que es de costo mínimo.
   
3. [3 puntos] Considere el problema de la mochila dado por encontrar el menor costo posible de objetos que se pueden meter en una mochila de capacidad M y N objetos de volumen V₁, V₂, ..., V_N y costo C₁, C₂, ..., C_N Demuestre que ninguno de los siguientes órdenes funcionan para resolver este problema con un algoritmo glotón: (a) ordenar los objetos ascendentemente según su volumen, (b) ordenar los objetos ascendentemente según su costo, (c) ordenar los objetos ascendentemente según su costo por unidad de volumen.