Diferencia entre revisiones de «Final del 02/03/10 (Algoritmos III)»
(Página nueva: == Ejercicio 1 == Dado un conjunto de n elementos naturales S = {a1,…, an} y un natural k queremos saber si existe un subconjunto de S cuyos elementos suman k. Diseñar un algoritmo...) |
|||
| (No se muestran 5 ediciones intermedias de otro usuario) | |||
| Línea 1: | Línea 1: | ||
{{Back|Algoritmos y Estructuras de Datos III}} | |||
== Ejercicio 1 == | == Ejercicio 1 == | ||
Dado un conjunto de n elementos naturales S = {a1,…, an} y un natural k queremos saber si existe un subconjunto de S cuyos elementos suman k. Diseñar un algoritmo de programación dinámica para resolver este problema. Mostrar la correctitud y determinar la complejidad del algoritmo propuesto. | Dado un conjunto de n elementos naturales S = {a1,…, an} y un natural k queremos saber si existe un subconjunto de S cuyos elementos suman k. Diseñar un algoritmo de programación dinámica para resolver este problema. Mostrar la correctitud y determinar la complejidad del algoritmo propuesto. | ||
| Línea 4: | Línea 5: | ||
== Ejercicio 2 == | == Ejercicio 2 == | ||
Decidir si las siguientes frases son Verdaderas o Falsas. Justificar: | Decidir si las siguientes frases son Verdaderas o Falsas. Justificar: | ||
(a) G conexo, tiene un único AG sí y solo sí G es un árbol. | |||
(b) Si la arista e es una arista puente de G, entonces e pertenece a todo AG. | (a) G conexo, tiene un único AG sí y solo sí G es un árbol. | ||
(c) Sea G un grafo con pesos en sus aristas. G tiene un único AGM sí y solo sí G es un árbol. | |||
(d) Si G tiene más de un AGM entonces toda arista que pertenece a algún AGM y no pertenece a algún otro AGM, está incluida en un circuito en el cual tiene peso mínimo. | (b) Si la arista e es una arista puente de G, entonces e pertenece a todo AG. | ||
(c) Sea G un grafo con pesos en sus aristas. G tiene un único AGM sí y solo sí G es un árbol. | |||
(d) Si G tiene más de un AGM entonces toda arista que pertenece a algún AGM y no pertenece a algún otro AGM, está incluida en un circuito en el cual tiene peso mínimo. | |||
== Ejercicio 3 == | == Ejercicio 3 == | ||
Analizar el siguiente algoritmo para colorear los ejes de un grafo G: | Analizar el siguiente algoritmo para colorear los ejes de un grafo G: | ||
Dado un grafo G | Dado un grafo G | ||
Poner k = 0 | |||
Mientras X no sea vacío hacer | |||
• k = k + 1 | • k = k + 1 | ||
• encontrar un matching máximo | • encontrar un matching máximo M de G | ||
• para todo | • para todo e en M poner f(e) = k | ||
• G = G \ | • G = G \ M | ||
End | End | ||
a) Demostrar que el algoritmo da un coloreo válido de los ejes de G. | a) Demostrar que el algoritmo da un coloreo válido de los ejes de G. | ||
b) Decir si el algoritmo calcula siempre el índice cromático de G correctamente. | b) Decir si el algoritmo calcula siempre el índice cromático de G correctamente. | ||
c) Sabiendo que existen algoritmos polinomiales de orden O(n3) para determinar un matching máximo determinar la complejidad del algoritmo. | c) Sabiendo que existen algoritmos polinomiales de orden O(n3) para determinar un matching máximo determinar la complejidad del algoritmo. | ||
d) ¿Se podría reemplazar encontrar un matching máximo por encontrar un matching maximal? | d) ¿Se podría reemplazar encontrar un matching máximo por encontrar un matching maximal? | ||
| Línea 31: | Línea 39: | ||
== Ejercicio 5 == | == Ejercicio 5 == | ||
a) ¿Qué es una máquina de Turing no determinística? | a) ¿Qué es una máquina de Turing no determinística? | ||
b) Enunciar el teorema de Cook y explicar su importancia en la teoría de la complejidad de algoritmos. | b) Enunciar el teorema de Cook y explicar su importancia en la teoría de la complejidad de algoritmos. | ||
c) ¿Es cierto que si se probara que P = NP entonces quedaría probado que todo problema NP-hard está en P? | c) ¿Es cierto que si se probara que P = NP entonces quedaría probado que todo problema NP-hard está en P? | ||
d) ¿Cuál es la importancia desde el punto de vista práctico (o sea cuando se necesita resolver un problema real) de saber que un problema es NP-Completo o NP-hard? | d) ¿Cuál es la importancia desde el punto de vista práctico (o sea cuando se necesita resolver un problema real) de saber que un problema es NP-Completo o NP-hard? | ||
[[Category:Finales]] | |||
Revisión actual - 16:48 29 feb 2020
Ejercicio 1[editar]
Dado un conjunto de n elementos naturales S = {a1,…, an} y un natural k queremos saber si existe un subconjunto de S cuyos elementos suman k. Diseñar un algoritmo de programación dinámica para resolver este problema. Mostrar la correctitud y determinar la complejidad del algoritmo propuesto.
Ejercicio 2[editar]
Decidir si las siguientes frases son Verdaderas o Falsas. Justificar:
(a) G conexo, tiene un único AG sí y solo sí G es un árbol.
(b) Si la arista e es una arista puente de G, entonces e pertenece a todo AG.
(c) Sea G un grafo con pesos en sus aristas. G tiene un único AGM sí y solo sí G es un árbol.
(d) Si G tiene más de un AGM entonces toda arista que pertenece a algún AGM y no pertenece a algún otro AGM, está incluida en un circuito en el cual tiene peso mínimo.
Ejercicio 3[editar]
Analizar el siguiente algoritmo para colorear los ejes de un grafo G:
Dado un grafo G
Poner k = 0
Mientras X no sea vacío hacer
• k = k + 1
• encontrar un matching máximo M de G
• para todo e en M poner f(e) = k
• G = G \ M
End
a) Demostrar que el algoritmo da un coloreo válido de los ejes de G.
b) Decir si el algoritmo calcula siempre el índice cromático de G correctamente.
c) Sabiendo que existen algoritmos polinomiales de orden O(n3) para determinar un matching máximo determinar la complejidad del algoritmo.
d) ¿Se podría reemplazar encontrar un matching máximo por encontrar un matching maximal?
Ejercicio 4[editar]
Sea G un grafo y v un vértice no aislado de G. Demostrar que existe un matching de cardinal máximo en G tal que v es un extremo de un eje perteneciente al matching.
Ejercicio 5[editar]
a) ¿Qué es una máquina de Turing no determinística?
b) Enunciar el teorema de Cook y explicar su importancia en la teoría de la complejidad de algoritmos.
c) ¿Es cierto que si se probara que P = NP entonces quedaría probado que todo problema NP-hard está en P?
d) ¿Cuál es la importancia desde el punto de vista práctico (o sea cuando se necesita resolver un problema real) de saber que un problema es NP-Completo o NP-hard?
