Final del 21/12/15 (Algoritmos III)
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
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 arbitrarios
- Arbol generador Minimo
- Encontrar la clique mas grande de un grafo
- Corte Minimo
- Encontrar el numero cromatico de un grafo
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).
