Diferencia entre revisiones de «Final del 21/12/15 (Algoritmos III)»
(asi quedaba mejor) |
(Cambios en el ejercicio 3) |
||
| 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 | ||
*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, sin ciclos negativos | ||
*Arbol generador Minimo | *Arbol generador Minimo | ||
* | *Conjunto independiente maximo | ||
*Conjunto independiente maximal | |||
*Corte Minimo | *Corte Minimo | ||
* | *Planaridad | ||
== 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). | ||
Revisión actual - 22:35 21 dic 2015
Plantilla:Back Final tomado por Javier Marenco. El final constaba de 4 ejercicios a ser resueltos por escrito.
Ejercicio 1
Explicar lo que es un algoritmo pseudopolinomial. Explicar en que se diferencia de uno polinomial. Dar un ejemplo de uno pseudopolinomial y calcular su complejidad.
Spoiler: Un ejemplo puede ser el factorial recursivo.
Ejercicio 2
Para un digrafo con ejes positivos sin ciclos, nombrar un algoritmo para encontrar el camino máximo entre s y t. ¿Sigue funcionando lo propuesto si hay ciclos?
Spoiler: no es simplemente un algoritmo tenes que hacer algunas cosas mas
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
- Problema de camino minimo entre 2 nodos con pesos positivos
- Problema de camino minimo entre 2 nodos con pesos arbitrarios, sin ciclos negativos
- Arbol generador Minimo
- Conjunto independiente maximo
- Conjunto independiente maximal
- Corte Minimo
- Planaridad
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).
