Diferencia entre revisiones de «Final del 09/12/15 (Algoritmos III)»
De Cuba-Wiki
(Página creada con «{{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 al...») |
Sin resumen de edición |
||
| (No se muestran 2 ediciones intermedias del mismo usuario) | |||
| Línea 4: | Línea 4: | ||
== Ejercicio 1 == | == 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 | 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 == | == Ejercicio 2 == | ||
| Línea 12: | Línea 12: | ||
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 | ||
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 | ||
Arbol generador Minimo | *Arbol generador Minimo | ||
Encontrar la clique mas grande de un grafo | *Encontrar la clique mas grande de un grafo | ||
*Corte Minimo | |||
Encontrar el numero cromatico de un grafo | *Encontrar el numero cromatico de un grafo | ||
== Ejercicio 4 == | == Ejercicio 4 == | ||
Dar un algoritmo aproximado para el TSP. Decir su cota de aproximacion y demostrarla | Dar un algoritmo aproximado para el TSP. Decir su cota de aproximacion y demostrarla | ||
Revisión actual - 02:58 10 dic 2015
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 un grafo tal que es isomorfo a . Probar que o .
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
- Corte Minimo
- Encontrar el numero cromatico de un grafo
Ejercicio 4
Dar un algoritmo aproximado para el TSP. Decir su cota de aproximacion y demostrarla
