Metodología Greedy

¿Es siempre óptimo un algoritmo resuelto con la técnica Greedy?

• No

• Si

• Si, pero solo para los problemas de optimización

• No, excepto para los problemas de evalución

Las propiedades requeridas para resolver un problema mediante metodología greedy de forma óptima son:

• Elección greedy y Superposición de subproblemas

• Superposición de problemas y jerarquía (ordenamiento) de subproblemas

• Subestructura óptima y elección greedy

• Subestructura óptima y jerarquía (ordenamiento) de subproblemas

La definición "la solución al problema contiene dentro de sí la solución óptima de sus subproblemas" corresponde a la propiedad

• Elección greedy

• Subestructura óptima

• Solapamiento de subproblemas

• Optimalidad recursiva

La definición "La solución global puede obtenerse realizando una elección óptima local" corresponde a la propiedad

• codicia eficiente

• subestructura óptima

• solapamiento jerárquica

• Elección greedy

Árbol recubridor mínimo: El algoritmo de Prim genera el mismo resultado que el algoritmo de Kruskal, al calcular el MST de un Grafo

• Si

• No

• Únicamente si el grafo es completo

• Únicamente si los pesos de los ejes son todos unitarios (1)

Árbol recubridor mínimo: Ante mismos criterios de desempate, el algoritmo de Kruskal aplicado a un Grafo genera siempre el mismo MST

• Verdadero

• Falso

• Depende de la implementación

• Depende del algoritmo de ordenamiento

Ante mismos criterios de desempate, el algoritmo de Prim aplicado a un Grafo genera siempre el mismo MST, sin importar de qué vértice se parta

• Verdadero

• Falso

Interval Schedulling: Dados N intervalos de tiempo, definimos "si" y "fi" como cuándo empieza y cuándo termina el intervalo "i". Decimos que Ni no es compatible con Nj cuando se superponen sus intervalos en el tiempo. Si queremos encontrar la mayor cantidad de intervalos que no se superpongan, cuál de las siguientes estrategias obtiene el óptimo?

• Ordernar los intervalos por "si" (ascendiente) e ir eligiendo por orden, depreciando los intervalos que se superponen al elegido.

• Ordernar los intervalos por "fi - si" (ascendiente)e ir eligiendo por orden, depreciando los intervalos que se superponen al elegido.

• Ordernar los intervalos por cantidad de incompatibilidades (ascendiente) e ir eligiendo por orden, depreciando los intervalos que se superponen al elegido.

• Ordenar los intervalos por "si" (descendente) e ir eligiendo por orden, depreciando los intervalos que se superponen al elegido.

Interval schedulling: La mejor complejidad temporal que se puede lograr para resolver cualquier instancia de este problema es

• O(n)

• O(n^2)

• O(n log n)

• O(1)

Interval schedulling: La mejor complejidad espacial que se puede lograr para resolver el problema es ...

• O(n)

• O(n log n)

• O(1)

• O(n^2)