Diferencia entre revisiones de «Final del 21/02/13 (Algoritmos III)»
(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...») |
|||
| (No se muestran 3 ediciones intermedias del mismo usuario) | |||
| 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 | |||
a) Probar que si e arista de G no pertenece a T, 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? | ||
d) Teniendo en cuenta los puntos anteriores proponer un algoritmo que devuelve un AGM. Dar su complejidad. | |||
== 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 | ||
== Ejercicio 4 == | == Ejercicio 4 == | ||
Que obtenemos si cortamos en la iteración k al algotirmo de dijkstra? | Que obtenemos si cortamos en la iteración k al algotirmo de dijkstra? Justificar | ||
== 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 actual - 05:32 23 feb 2013
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 T, 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?
d) Teniendo en cuenta los puntos anteriores proponer un algoritmo que devuelve un AGM. Dar su complejidad.
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? Justificar
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?
