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
Matching maximo en un grafo bipartito
*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