Diferencia entre revisiones de «Final del 21/12/15 (Algoritmos III)»
(Página creada con «{{Back|Algoritmos y Estructuras de Datos III}} Final tomado por Javier Marenco. El final constaba de 4 ejercicios a ser resueltos por escrito. == Ejercicio 1 == Explicar...») |
(asi quedaba mejor) |
||
| Línea 9: | Línea 9: | ||
== Ejercicio 2 == | == 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? | 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 == | == Ejercicio 3 == | ||
Revisión del 22:12 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
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).
