Informatica

UNIVERSIDAD DE GRANADA
E.T.S. DE INGENIERIAS INFORMATICA y DE
TELECOMUNICACION
Departamento de Ciencias de la
Computacion e Inteligencia Articial
Algortmica
Guion de Practicas
Practica 3: Algoritmos Voraces (Greedy)
Curso 2012-2013
Grado en Informatica
1. Objetivo
El objetivo de esta practica es que el estudiante aprecie la utilidad de los metodos voraces
(greedy) pararesolver problemas de forma muy eciente, en algunos casos obteniendo soluciones
optimas y en otros aproximaciones. Para ello cada equipo de estudiantes debera resolver uno de
los problemas (asignado al azar) que se describen en la seccion 2, as como exponer y defender su
propuesta en clase. Adicionalmente, todos los equipos deberan implementar algoritmos voraces
para resolver elproblema del viajante de comercio, siguiendo las indicaciones descritas en la
seccion 3.
2. Problemas
2.1. Contenedores en un barco
Se tiene un buque mercante cuya capacidad de carga es de K toneladas y un conjunto de
contenedores c1; : : : ; cn cuyos pesos respectivos son p1; : : : ; pn (expresados tambien en toneladas).
Teniendo en cuenta que la capacidad del buque es menor que la suma totalde los pesos
de los contenedores:
Dise~ne un algoritmo que maximice el numero de contenedores cargados, y demuestre su
optimalidad.
Dise~ne un algoritmo que intente maximizar el numero de toneladas cargadas.
2.2. Minimizando el numero de visitas al proveedor
Un granjero necesita disponer siempre de un determinado fertilizante. La cantidad maxima
que puede almacenar la consume en rdas, y antes de que eso ocurra necesita acudir a una
tienda del pueblo para abastecerse. El problema es que dicha tienda tiene un horario de apertura
muy irregular (solo abre determinados das). El granjero conoce los das en que abre la tienda,
y desea minimizar el numero de desplazamientos al pueblo para abastecerse.
Dise~nar un algoritmo greedy que determine en que das debe acudir alpueblo a comprar
fertilizante durante un periodo de tiempo determinado (por ejemplo durante el siguiente
mes).
Demostrar que el algoritmo encuentra siempre la solucion optima.
2.3. Minimizando el tiempo medio de acceso
Sean n programas P1; P2; : : : ; Pn que hay que almacenar en una cinta. El programa Pi
requiere si kilobytes de espacio y la cinta es sucientemente larga para almacenartodos los
programas.
Se sabe con que frecuencia se utiliza cada programa: una fraccion i de las solicitudes afecta
al programa Pi (y por tanto
Pni
=1 i = 1). Los datos se almacenan en la cinta con densidad
constante y la velocidad de la cinta tambien es constante. Una vez que se carga el programa,
la cinta se rebobina hasta el principio.
Si los programas se almacenan por orden i1; i2; :: : ; in el tiempo medio requerido para cargar
un programa es, por tanto:
^ T = c
Xn
j=1
2
4ij
Xj
k=1
sik
3
5
donde la constante c depende de la densidad de grabacion y de la velocidad de la cinta.
Se desea minimizar ^ T empleando un algoritmo voraz. Demuestre la optimalidad del algoritmo
o encuentre un contraejemplo que muestre que el algoritmo no es optimo para los siguientescriterios de seleccion:
Programas en orden no decreciente de si.
Programas en orden no creciente de i.
Programas en orden no creciente de i=si.
2.4. Recubrimiento de un grafo no dirigido
Consideremos un grafo no dirigido G = (V;E). Un conjunto U se dice que es un recubrimiento
de G si U  V y cada arista en E incide en, al menos, un vertice o nodo de U, es decir
8(x; y) 2 E, bien x 2 Uo y 2 U. Un conjunto de nodos es un recubrimiento minimal de G si
es un recubrimiento con el menor numero posible de nodos.
Dise~nar un algoritmo greedy para intentar obtener un recubrimiento minimal de G. Demostrar
que el algoritmo es correcto, o dar un contraejemplo.
Dise~nar un algoritmo greedy que obtenga un recubrimiento minimal para el caso particular
de grafos que sean arboles....