Edición de «Final del 21/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 15: | Línea 15: | ||
== Ejercicio 3 == | == Ejercicio 3 == | ||
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 | ||
COPIE LO DEL FINAL ANTERIOR. NO ME ACUERDO CUALES ERAN. Háganse una lista de los problemas en general vistos en la materia! | |||
*Problema de camino minimo entre 2 nodos con pesos positivos | *Problema de camino minimo entre 2 nodos con pesos positivos | ||
*Problema de camino minimo entre 2 nodos con pesos arbitrarios | *Problema de camino minimo entre 2 nodos con pesos arbitrarios | ||
*Arbol generador Minimo | *Arbol generador Minimo | ||
* | *Encontrar la clique mas grande de un grafo | ||
*Corte Minimo | *Corte Minimo | ||
* | *Encontrar el numero cromatico de un grafo | ||
== Ejercicio 4 == | == Ejercicio 4 == | ||
Explicar que es la clase NP y la clase NP-Completo. Demostrar que un algoritmo es NP-Completo (se inventan ustedes cual asumir como NP-Completo y cual demostrar). | Explicar que es la clase NP y la clase NP-Completo. Demostrar que un algoritmo es NP-Completo (se inventan ustedes cual asumir como NP-Completo y cual demostrar). | ||
