Diferencia entre revisiones de «Final del 21/02/13 (Algoritmos III)»

De Cuba-Wiki
(Página creada con «{{Back|Algoritmos y Estructuras de Datos III}} == Ejercicio 1 == Dado un conjunto Sn {a1, a2, ... ,an} de naturales, se quiere saber cual es el largo de la secuencia creci...»)
 
Sin resumen de edición
Línea 8: Línea 8:
== Ejercicio 2 ==
== Ejercicio 2 ==
Sea G un grafo y T un AGM de G.  
Sea G un grafo y T un AGM de G.  
a) Probar que si e arista de G no pertenece a G, entonces e es una de las aristas más pesadas del circuito al que pertenece.
a) Probar que si e arista de G no pertenece a G, entonces e es una de las aristas más pesadas del circuito al que pertenece.
b) Probar que si e es puente en G pertenece a T
b) Probar que si e es puente en G pertenece a T
c) Si T es AGM de G y e no pertenece a T, es T un AGM de G\{e} ? Todo árbol mínimo de G\{e} es AGM de T?
c) Si T es AGM de G y e no pertenece a T, es T un AGM de G\{e} ? Todo árbol mínimo de G\{e} es AGM de T?


== Ejercicio 3 ==
== Ejercicio 3 ==
Sea G conexo y completo Kn con n>=3 con pesos en los ejes y no dirigido. Decir si es cierto lo siguiente y justificar la respuesta:
Sea G conexo y completo Kn con n>=3 con pesos en los ejes y no dirigido. Decir si es cierto lo siguiente y justificar la respuesta:
a) Si un cto hamiltoniano mínimo de G contiene a un camino hamiltoniano mínimo. Es el camino igual al cto pero sin su arista más pesada?
a) Si un cto hamiltoniano mínimo de G contiene a un camino hamiltoniano mínimo. Es el camino igual al cto pero sin su arista más pesada?
b) Algún cto hamiltoniano mínimo contiene a un camino mínimo hamiltoniano?
b) Algún cto hamiltoniano mínimo contiene a un camino mínimo hamiltoniano?
c) Todo cto hamiltoniano mínimo contiene a un camino hamiltoniano mínimo?
c) Todo cto hamiltoniano mínimo contiene a un camino hamiltoniano mínimo?
d) Repetir a, b, c pero sabiendo que los pesos de los ejes cumplen con la desigualdad triangular
d) Repetir a, b, c pero sabiendo que los pesos de los ejes cumplen con la desigualdad triangular


Línea 24: Línea 31:
== Ejercicio 5 ==
== Ejercicio 5 ==
a) Enunciar el teorema de Cook y dar su importancia.
a) Enunciar el teorema de Cook y dar su importancia.
b) Si P = NP, podemos decir que P = Np-Hard?
b) Si P = NP, podemos decir que P = Np-Hard?
c) Cuál es la ventaja de saber si un problema es Np-completo o np-hard en la práctica?
c) Cuál es la ventaja de saber si un problema es Np-completo o np-hard en la práctica?


[[Category:Finales]]
[[Category:Finales]]

Revisión del 05:29 23 feb 2013

Plantilla:Back

Ejercicio 1

Dado un conjunto Sn {a1, a2, ... ,an} de naturales, se quiere saber cual es el largo de la secuencia creciente más larga. Desarrollar un algoritmo utilizando programación dinámica. Cuál es su complejidad? Cómo hay que modificar al algoritmo si queremos que además devuelva la secuencia?

Ejercicio 2

Sea G un grafo y T un AGM de G.

a) Probar que si e arista de G no pertenece a G, entonces e es una de las aristas más pesadas del circuito al que pertenece.

b) Probar que si e es puente en G pertenece a T

c) Si T es AGM de G y e no pertenece a T, es T un AGM de G\{e} ? Todo árbol mínimo de G\{e} es AGM de T?

Ejercicio 3

Sea G conexo y completo Kn con n>=3 con pesos en los ejes y no dirigido. Decir si es cierto lo siguiente y justificar la respuesta:

a) Si un cto hamiltoniano mínimo de G contiene a un camino hamiltoniano mínimo. Es el camino igual al cto pero sin su arista más pesada?

b) Algún cto hamiltoniano mínimo contiene a un camino mínimo hamiltoniano?

c) Todo cto hamiltoniano mínimo contiene a un camino hamiltoniano mínimo?

d) Repetir a, b, c pero sabiendo que los pesos de los ejes cumplen con la desigualdad triangular

Ejercicio 4

Que obtenemos si cortamos en la iteración k al algotirmo de dijkstra?

Ejercicio 5

a) Enunciar el teorema de Cook y dar su importancia.

b) Si P = NP, podemos decir que P = Np-Hard?

c) Cuál es la ventaja de saber si un problema es Np-completo o np-hard en la práctica?