1. No category

Instituto de Computación - Facultad de Ingeniería
Programación 3 - Curso 2015- Tarea 2
Tarea semanal 2.3: Algoritmos Greedy
1.
Objetivos
Resolver problemas mediante la técnica Greedy.
2.
Conocimientos previos
Greedy.
3.
Preguntas
1. ¿En qué consiste la técnica Greedy?
2. Dé un ejemplo de problema y un algoritmo basado en la técnica Greedy aplicada a él que no siempre
devuelva la solución buscada.
3. ¿En qué propiedad basan su correctitud los algoritmos de Prim y Kruskal?
4. ¿Cómo aplica el algoritmo de Prim esa propiedad?
5. ¿Cómo aplica el algoritmo de Kruskal esa propiedad?
6. Describa semejanzas y diferencias entre los algoritmos de Prim y de Dijkstra. Muéstrelo con un ejemplo.
4.
Problema
En la organización del congreso se planteó el problema max_charlas, en el que no hay que maximizar la cantidad de asistentes sino la cantidad de charlas a ser desarrolladas. Tal como en el problema
max_asistentes hay una única sala cuyo intervalo de disponibilidad contiene al de desarrollo de cada una de
las charlas.
En la discusión entre los encargados de diseñar los algoritmos se planteó la posibilidad de resolver
max_charlas con la técnica Greedy. Se propuso la siguiente estrategia: ordenar las charlas de manera creciente según algún atributo. Se asigna la primera charla y luego en orden creciente se asigna cada una si es
compatible con las ya asignadas. Es decir, se propuso el siguiente algoritmo:
charlas[1..n] está ordenada según el atributo considerado
S ← {1}
for i = 2 TO n do
if ∀j∈{1,··· ,i−1} (j ∈
/ S ∨ compatibles(i, j)) then
S ← S ∪ {i}
return S
Los atributos propuestos fueron:
1. Fecha de inicio.
2. Fecha de fin.
3. Duración.
Se plantean las siguientes preguntas
1
Instituto de Computación - Facultad de Ingeniería
Programación 3 - Curso 2015- Tarea 2
a. ¿Es realmente Greedy esta estrategia?
b. ¿Cuál es el orden de complejidad, en función de n, de estos algoritmos? Si para alguno de los atributos
es posible conseguir un orden menor, modifique el algoritmo para lograrlo.
c. Para cada uno de estos atributos demuestre que el algoritmo permite resolver de forma óptima el
problema max_charlas o muestre un contraejemplo en caso de que no se pueda. Se sabe que con al
menos uno de los atributos el algoritmo cumple el objetivo.
Ayuda. Para la demostración suponga que t = ht1 , t2 , . . . , tp i es la solución obtenida por el algoritmo
y que hs1 , s2 , . . . , sr i es una tupla genérica en la que cada par de charlas son compatibles entre sí.
Además asuma que, independientemente de cómo fue obtenida, la tupla s está ordenada según el
mismo atributo que la tupla t. El objetivo es demostrar que p ≥ r.
Para esto suponga que p < r. Demuestre por inducción en p que:
charlas[tp ].atributo ≤ charlas[sp ].atributo
Como consecuencia note que la charla sp+1 es compatible con todas las charlas de t. A partir de esto
concluya el absurdo.
d. También se pensó en tomar como atributo la cantidad de charlas con las que se superpone cada una.
Mostrar con un contraejemplo por qué no funciona esta estrategia.
5.
Entrega
La solución debe incluir lo siguiente:
1. Respuestas de las preguntas de la sección 3.
2. Demostración y contraejemplos de las propuestas del problema de la sección 4.
Se debe entregar la solución antes del viernes 30 de octubre a las 17:00 vía EVA. El archivo debe estar
en formato PDF y debe llamarse G-2-3.pdf, donde G es el número del grupo. Además se debe entregar
una copia impresa en la clase de monitoreo de la semana que comienza el 2 de noviembre.
2