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 18: | Línea 17: | ||
Dado un grafo G | Dado un grafo G | ||
Poner k = 0 | Poner k = 0 | ||
Mientras X | |||
Mientras <math>X \neq \empty</math> hacer | |||
• k = k + 1 | • k = k + 1 | ||
• encontrar un matching máximo M de G | |||
• para todo e | • encontrar un matching máximo de M de G | ||
• G = G \ M | |||
• para todo <math>e \in M</math> poner f(e) = k | |||
• G = G \ {M} | |||
End | End | ||
Línea 45: | Línea 51: | ||
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? | ||