Final del 21/12/15 (Algoritmos III)

De Cuba-Wiki

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

Obtenido de «https://www.cubawiki.com.ar/index.php?title=Final_del_21/12/15_(Algoritmos_III)&oldid=10235»