Diferencia entre revisiones de «Final del 21/12/15 (Algoritmos III)»

De Cuba-Wiki
(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
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, sin ciclos negativos
*Arbol generador Minimo
*Arbol generador Minimo
*Encontrar la clique mas grande de un grafo
*Conjunto independiente maximo
*Conjunto independiente maximal
*Corte Minimo
*Corte Minimo
*Encontrar el numero cromatico de un grafo
*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[editar]

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[editar]

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[editar]

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[editar]

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).