Edición de «Final del 02/03/10 (Algoritmos III)»
De Cuba-Wiki
Puedes deshacer la edición. Antes de deshacer la edición, comprueba la siguiente comparación para verificar que realmente es lo que quieres hacer, y entonces publica los cambios para así efectuar la reversión.
| Revisión actual | Tu texto | ||
| Línea 1: | Línea 1: | ||
== 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 5: | Línea 4: | ||
== 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. | |||
(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. | |||
(b) Si la arista e es una arista puente de G, entonces e pertenece a todo AG. | (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. | ||
(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 | |||
Poner k = 0 | |||
Mientras <math>X \neq \empty</math> hacer | |||
• k = k + 1 | |||
• encontrar un matching máximo de M de G | |||
• para todo <math>e \in M</math> poner f(e) = k | |||
• G = G \ {M} | |||
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 39: | Línea 31: | ||
== 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? | ||
