Edición de «Final del 09/12/15 (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 4: | Línea 4: | ||
== Ejercicio 1 == | == Ejercicio 1 == | ||
Dar un algoritmo de programación dinámica que resuelva el problema de la mochila | Dar un algoritmo de programación dinámica que resuelva el problema de la mochila. https://es.wikipedia.org/wiki/Problema_de_la_mochila | ||
== Ejercicio 2 == | == Ejercicio 2 == | ||
Línea 12: | Línea 12: | ||
Para los siguientes problemas, decidir si pertenecen a P o a NP-hard. En el caso de que se conozca un algoritmo polinomial, dar su nombre y complejidad | Para los siguientes problemas, decidir si pertenecen a P o a NP-hard. En el caso de que se conozca un algoritmo polinomial, dar su nombre y complejidad | ||
Problema de camino minimo entre 2 nodos con pesos positivos | |||
Problema de camino minimo entre 2 nodos con pesos arbitrarios | |||
Arbol generador Minimo | |||
Encontrar la clique mas grande de un grafo | |||
Matching maximo en un grafo bipartito | |||
Encontrar el numero cromatico de un grafo | |||
== Ejercicio 4 == | == Ejercicio 4 == | ||
Dar un algoritmo aproximado para el TSP. Decir su cota de aproximacion y demostrarla | Dar un algoritmo aproximado para el TSP. Decir su cota de aproximacion y demostrarla |