Brainscape's Knowledge GenomeTM

Browse over 1 million classes created by top students, professors, publishers, and experts.


See full index

Final TDA > Greedy: Interval Scheduling & Interval Partitioning Problem > Flashcards

Greedy: Interval Scheduling & Interval Partitioning Problem Flashcards

1
Q

¿Para qué tipo de problemas es la metodología de resolución greedy?

A

Para problemas de optimización (maximización o minimización).

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
2
Q

¿Cómo funciona Greedy?

A

Greedy divide al problema en subproblemas, con una jerarquía entre ellos.

Cada subproblema se va resolviendo iterativamente mediante una elección heurística, habilitsndo nuevos subproblemas.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
3
Q

¿Todos los problemas pueden resolverse por el mismo algoritmo Greedy? ¿Todos resultan en la solución óptima?

A

No.

Para cada problema, existen diferentes algoritmos Greedy, y no todos resultan en la solución óptima.

Además, no todos los problemas pueden resolverse mediente un algoritmo greedy (no todos llegan a soluciones óptimas), para ello deben tener ciertas propiedades.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
4
Q

¿Cuáles son las propiedades requeridas para una resolución óptima con un algoritmo Greedy?

A
  1. Elección Greedy
  • Seleccionar una solución local óptima, esperando que la misma nos acerque a la solución óptima global.
  • Analizar el conjunto de los elementos del problema en el estado en que llegaron al mismo y elegir heurísticamente “la mejor solución” local.
  • Un subproblema está condicionado por las elecciones de los anteriores subproblemas y así mismo condiciona a los subproblemas siguientes.
  1. Subestructura Óptima
  • Un problema contiene una subestructura óptima si la solución óptima global del mismo contiene en su interior a las soluciones óptimas de sus subproblemas.
  • La elección greedy resolverá iterativamente los subproblemas de forma óptima y los llevará a la solución óptima global.
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
5
Q

Indique los 6 pasos en la construcción de una estrategia Greedy

A
  1. Determinar la subestructura óptima del problema
  2. Construir una solución recursiva
  3. Mostrar que si realizamos la elección greedy, nos quedaremos en última instancia con sólo 1 subproblema.
  4. Mostrar que la elección greedy se puede realizar siempre y de forma segura.
  5. Construir el algoritmo recursivo que solucione el problema.
  6. Convertir el algoritmo recursivo en uno iterativo.
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
6
Q

Describa el problema de Interval Scheduling

A

Sea P un conjunto de n pedidos {p1, p2, ..., pn}.

Cada pedido i tiene un tiempo s_i donde inicia y un tiempo t_i donde finaliza.

Lo que se quiere hacer es seleccionar el subconjunto de P de mayor tamaño posible de modo que todas las tareas seleccionadas sean compatibles entre sí.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
7
Q

¿Cuándo un par de tareas son compatibles?

A

Un par de tareas son compatibles si y sólo si no hay solapamiento en el tiempo entre ellas.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
8
Q

Interval Scheduling: ¿Cuáles son las heurísticas que no funcionan y cuál es la que sí lo hace?

A

Las que no funcionan:
- Aquel que comienza antes
- Aquel que dura menos tiempo
- Aquel que tiene menos incompatibilidades

La que sí funciona:
- Aquel que termina antes.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
9
Q

Explique el comportamiento del algoritmo tradicional de Interval Scheduling (O(n^2))

A 
Sea P un set de pedidos
Sea A el subconjunto máximo

Mientras P no esté vacío
        Sea i el pedido en P con menor tiempo de finalización
        A += i

        Quitar de P todos los pedidos incompatibles con i

Retornar A
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
10
Q

Resolver:

Evento A: Inicia a las 9:00 y termina a las 10:30 (duración de 1.5 horas).

Evento B: Inicia a las 10:15 y termina a las 11:45 (duración de 1.5 horas).

Evento C: Inicia a las 11:00 y termina a las 12:30 (duración de 1.5 horas).

Evento D: Inicia a las 12:00 y termina a las 13:30 (duración de 1.5 horas).

Evento E: Inicia a las 13:15 y termina a las 14:45 (duración de 1.5 horas).

A

{a, c, e}

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
11
Q

Optimalidad: Explique cómo se verifica que la solución A del problema de Interval Scheduling es óptima

A

No se puede asegurar que A = O.

Pero podemos ver que |A| = |O|.
Esto significa que el número de elementos en el conjunto A es igual al número de elemntos en el conjunto O.
=> El algoritmo encontró una solución con la misma cantidad de elementos que la óptima.

Si A no fuese óptimo, O debería tener más pedidos. Como no los tiene, se dice que A es óptimo.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
12
Q

¿El algoritmo Greedy retorna siempre un set A óptimo para Interval Scheduling?

A

Sí.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
13
Q

¿Cuál es la implementación eficiente de Interval scheduling?

A
  • Ordenamos los pedidos por tiempo de finalización
  • Iteramos, ignorando los incompatibles y seleccionando el próximo disponible, y guardando el tiempo de finalización del último elemento elegido (para poder comparar).
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
14
Q

¿Cuál es la complejidad de Interval Scheduling (implementación eficiente) en cada una de sus partes, y cuál es la complejidad temporal y espacial general?

A
  • El proceso de ordenamiento es O(n logn)
  • La iteración es O(n)

=> Entonces:
- La complejidad temporal es O(n logn)
- La complejidad espacial es O(n)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
15
Q

Interval Scheduling: Con los siguientes pedidos, resolver.

evento	s	f
a		4	6
b		2	5
c		1	3
d		6	8
e		3	7
A

A = {c,a,d}

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
16
Q

Describa el Interval Partitioning Problem

A

Sea E un conjunto de n eventos {e1, e2, ..., en}.
Sea S un conjunto de salas.

Cada evento e tiene:
- Una fecha de inicio f_s
- Una fecha de finalización f_e

Se quiere asignar cada evento a una sala, minimizando la cantidad de salas utilizadas.

17
Q

¿Cómo se le llama al número máximo de salas necesarias en Interval Partitioning Problem?

A

Se le llama profundidad.

18
Q

Explique qué implica la solución eficiente (no mejorada, O(n^2) de complejidad) de Interval Partitioning Problem.
Describa el pseudocódigo.

A

Sea d la profundidad del conjunto de eventos:

  1. Usamos etiquetas {1, 2, …, d} para asignar eventos a una sala.
  2. Ordenamos los eventos por su fecha de inicio (O(n logn)).
  3. Iteramos por los eventos ordenados, etiquetando uno a uno con una etiqueta que no haya sido asignada previamente a un evento que se superpone.
Sea E el set de eventos.
Ordenar E según fecha de inicio.

Por cada evento Ej:
        Por cada evento Ei que precede a Ej y con el que se superpone:
                  Excluir la etiqueta de Ei para Ej

       Si existe una etiqueta {1, 2, ..., d} que no fue excluida:
              Asignar la menor etiqueta posible a Ej
       De lo contrario:
              Dejar Ej sin etiquetar

Retornar los eventos etiquetados.
19
Q

Resuelva Interval Partitioning Problem:
evento s f
a 1 8
b 2 6
c 6 9
d 10 11
e 3 4
f 5 7

A
  • Etiqueta 1: a, d
  • Etiqueta 2: b, c
  • Etiqueta 3: e, f
20
Q

¿Qué complejidad tiene Interval Partitioning Problem (forma no mejorada)? Explique parte por parte, y en general.

A
  • Ordenar es O(n logn)
  • Iterar por cada evento es O(n)
  • Verificar por cada evento anterior es O(n)

=> Complejidad total es O(n^2)

21
Q

Interval Partitioning Problem: ¿Puede quedar un evento sin etiquetar?

A

En el peor de los casos, podemos llegar hasta la etiqueta d (profundidad). Podría quedar un evento sin etiquetar.

22
Q

Interval Partitioning Problem: ¿Pueden dos eventos superpuestos tener la misma etiqueta?

A

No, por diseño del algoritmo.

23
Q

Interval Partitioning Problem: ¿Puedo asignar cualquier etiqueta?

A

No, siempre se van reutilizando las etiquetas a medida que se van liberando.

24
Q

Interval Partitioning Problem: ¿Cómo se puede mejorar la eficiencia?

A
  • Podemos evitar tener uan segunda iteración de eventos usando una estructura de datos diferente.
  • También nos interesa conocer la primer etiqueta disponible, por cada etiqueta podríamos almacenar la fecha de liberación.
  • Si la fecha de inicio del evento es anterior a la liberación, necesitamos una sala nueva. Sino, se asigna y se actualiza la fecha.

=> Se puede usar un heap de mínimos.

25
Q

Interval Partitioning Problem: Describa el algoritmo mejorado

A
  • Sea E los eventos ordenados por fecha de inicio.
  • Sea Q una cola de prioridad
  • Sea u la última sala usada
1. Tomar el primer evento, asignar la primer etiqueta.
2. Agregar a la cola de prioridad la etiqueta con la fecha de finalización del primer evento.
3. Para todos los otros eventos, repetir lo siguiente:

a) Obtener el minimo de Q.
b) si la liberación del minimo es menor al tiempo de inicio del evento, actualizar la etiqueta de u en Q con el tiempo finalización del evento.
c) Si no es menor, sumar 1 a la etiqueta, y guardar en Q la etiqueta nueva con el tiempo de finalización del evento.

4. Retornar los eventos etiquetados.
26
Q

Interval Partitioning Problem: Con los siguientes pedidos, resolver

a) con método no mejorado (O(n^2))
b) con método mejorado (O(n logn))

evento s f
a 4 6
b 2 5
c 1 3
d 6 8
e 3 7

A

Etiquetas:

1: c, e
2: b, d
3: a

27
Q

Interval Partitioning Problem: Explique la complejidad del algoritmo mejorado, parte por parte y de forma general.

A
  • Ordenar es O(n logn)
  • Usar un heap es O(logn) para push y O(1) para pop.
  • Se itera 1 vez por cada evento, y por cada evento, se hacen operaciones de heap.

=> Complejidad total: O(n logn)

28
Q

¿Qué es la latencia?

A

La latencia es “cuánto tarda en terminar un evento, una vez pasado el deadline”.

Si una tarea se prorgama para comenzar en el tiempo s, dura un tiempo t y su deadline es d, decimos que la latencia es:

l = s + t - d, si es mayor o igual a cero
ó
l = 0, si la suma es menor a cero
29
Q

Describa el modelo de planificación para minimizar la latencia

A

Sea P un conjunto de n pedidos {p1, p2, ..., pn}.

Cada pedido i tiene:
- Una duración ti no fraccionable
- Una fecha de entrega (deadline) di.

Queremos programar el inicio de cada uno de los pedidos a realizar sin superposición, de forma de minimizar la máxima latencia.

30
Q

¿Qué es la latencia máxima?

A

La latencia máxima de una secuencia de pedidos programados es la máxima de esas latencias.

31
Q

Latencia: explique el pseudocódigo.
¿La solución deja tiempos muertos? ¿Existe una solución óptima?

A
  1. Ordenar los pedidos en función de su deadline.
  2. Hora de finalización, 0
  3. Recorriendo los pedidos:

a. Asignar el pedido i al intervalo que comienza en f
b. Sumar a f la duración del pedido, actualizando su valor.

  1. Retornar el set de intervalos programados.

La solución no deja tiempos muertos ni de inactividad, y podemos afirmar que existe una solución óptima sin tiempos muertos.

32
Q

Latencia:
Tenemos los siguientes pedidos:

  • 1 = (1,2)
  • 2 = (3,6)
  • 3 = (2,4)

¿Cómo los programamos?

A

Debemos programarlos de acuerdo al deadline (del más cercano al más lejano), para minimizar la latencia.

(1, 3, 2)

33
Q

¿Qué son las inversiones?

A

Sea A' una programación de pedidos, decimos que A' tiene una inversión si un pedido i (ti, di) está programado antes que otro pedido j (tj, dj), siendo que el deadline de j es menor que el deadline de i.

34
Q

¿Qué posibles casos de inversiones hay? ¿Resolver una inversión, qué resultados puede tener?

A
  1. Ambos deadlines ocurren después de la finalización de los pedidos. Intercambiar no empeora la latencia total, sigue siendo óptimo.
  2. Los deadlines ocurren antes de los pedidos, intercambiarlos podría mejorar la latencia.

En general, resolver una inversión mejora o mantiene la latencia máxima, pero no la empeora.

35
Q

Interval Partitioning Problem: Sean B, C programaciones diferentes y sin inversiones ni tiempos muertos, ¿entonces qué tiempo de latencia tienen B y C?

A

Si B y C no tienen inversiones ni tiempos muertos, pero son diferentes, entonces existen pedidos que comparten el mismo deadline.

Por lo tanto B y C tienen el mismo tiempo de latencia total, porque invertir el orden de esos pedidos no altera la latencia máxima.

36
Q

Interval Partitioning Problem: ¿Qué pasa si B y C no tienen inversiones, pero son diferentes?

A

Si B y C no tienen inversiones, pero son diferentes, entonces existen pedidos que comparten el mismo deadline. Invertir el orden de esos pedidos no altera la latencia máxima.

37
Q

Interval Partitioning Problem: ¿Qué se debe hacer mientras exista una inversión?

A

Mientras exista una inversión, se van a realizar intercambios. Al finalizar, nos quedaremos con una programación óptima, sin inversiones.

38
Q

Interval Partitioning Problem: ¿Por qué la solución por Greedy es óptima?

A

Sea A una programación sin inversiones ni tiempos muertos.

  • Existe una programación sin tiempos muertos y sin inversiones.
  • Cualquier programación sin tiempos muertos e inversiones es equivalente a otra de iguales características (como el óptimo).
  • El algoritmo Greedy retorna una programación sin tiempos muertos e inversiones.

=> La solución entregada por Greedy es óptima.

Final TDA (17 decks)

Brainscape helps you reach your goals faster, through stronger study habits.
© 2024 Bold Learning Solutions. Terms and Conditions