Edición de «Final del 09/12/15 (Algoritmos III)»

{{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 ==
Dar un algoritmo de programación dinámica que resuelva el problema de la mochila. https://es.wikipedia.org/wiki/Problema_de_la_mochila

== Ejercicio 2 ==
Sea <math>G = (V,\quad E)</math> un grafo tal que <math>G</math> es isomorfo a <math>G^c</math>. Probar que <math> |V| \equiv 0 \quad \pmod 4 </math> o <math> |V| \equiv 1 \quad \pmod 4 </math>.

== 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
Arbol generador Minimo
Encontrar la clique mas grande de un grafo
Matching maximo en un grafo bipartito
Encontrar el numero cromatico de un grafo

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