Final del 09/12/15 (Algoritmos III)

Plantilla:Back 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, siendo numeros naturales los pesos y costos de los items a guardar. https://es.wikipedia.org/wiki/Problema_de_la_mochila

Ejercicio 2

Sea $G=(V,\quad E)$ un grafo tal que $G$ es isomorfo a $G^{c}$. Probar que $|V|\equiv 0\quad {\pmod {4}}$ o $|V|\equiv 1\quad {\pmod {4}}$.

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