Final del 09/12/15 (Algoritmos III)

De Cuba-Wiki
Saltar a: navegación, buscar
Back.png Volver a la página de la materia

Final tomado por Javier Marenco. El final constaba de 4 ejercicios a ser resueltos por escrito.


Ejercicio 1[editar]

Dar un algoritmo de programación dinámica que resuelva el problema de la mochila, siendo numeros naturales los pesos y costos de los items a guardar. https://es.wikipedia.org/wiki/Problema_de_la_mochila

Ejercicio 2[editar]

Sea un grafo tal que es isomorfo a . Probar que o .

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
  • Arbol generador Minimo
  • Encontrar la clique mas grande de un grafo
  • Corte Minimo
  • Encontrar el numero cromatico de un grafo

Ejercicio 4[editar]

Dar un algoritmo aproximado para el TSP. Decir su cota de aproximacion y demostrarla