Cuarto examen parcial de Diseño de Algoritmos

Trimestre 2010 Primavera
Entrega: 12 de julio de 2010 a las 13:00.

Abajo encontrarás tres problemas, cada uno con un valor de 20 puntos para totalizar hasta 60 puntos. Para resolverlos puedes auxiliarte de programas de computadora pero no necesitas entregarlos. Lo único que debes entregar es lo que se pide (en un correo electrónico a la cuenta donde ya has enviado tus demás tareas). Si obtienes P <= 40 puntos entonces esa será tu calificación de tu cuarto examen parcial. Si obtienes P > 40 puntos entonces tu calificación del cuarto examen parcial será 40 y te contabilizaré (P-40) puntos adicionales en tus tareas.

Problema 1: El problema del corte máximo es el de encontrar un subconjunto A de los vértices de una gráfica G = (V, E) tal que el costo total de las aristas que van de un vértice de A a un vértice que no está en A es tan grande como sea posible. El archivo corte.txt contiene la matriz de costos de una gráfica completa G con 100 vértices (numerados del 0 al 99 de arriba a abajo y de izquierda a derecha). Encuentre un subconjunto A (diga cuántos y cuáles vértices son) para el cual el costo del corte (calcúlelo y dígalo) correspondiente sea tan grande como le sea posible. Evaluación: 20 puntos a la mejor solución, los demás obtendrán una calificación proporcional.

Problema 2: El problema del agente viajero es el de encontrar un circuito que visite exactamente una vez cada uno de los vértices de una gráfica G = (V, E) tal que el costo total de las aristas que forman el circuito es tan pequeño como sea posible. El archivo viaje.txt contiene la matriz de costos de una gráfica completa G con 100 vértices (numerados del 0 al 99 de arriba a abajo y de izquierda a derecha). Encuentre un circuito (diga en qué orden se visitan los vértices) con costo (calcúlelo y dígalo) tan pequeño como sea posible. Evaluación: 20 puntos a la mejor solución, los demás obtendrán una calificación inversamente proporcional.

Problema 3: El problema del camino más largo es el de encontrar un camino que vaya de un vértice origen a un vértice destino de una gráfica G = (V, E) tal que no repita vértices y que el costo total de las aristas que lo forman sea tan grande como sea posible. El archivo largo.txt contiene la matriz de costos de una gráfica completa G con 100 vértices (numerados del 0 al 99 de arriba a abajo y de izquierda a derecha). Encuentre un camino (diga cuántos vértices lo forman y en qué orden se visitan) del vértice 0 al vértice 99 con costo (calcúlelo y dígalo) tan grande como sea posible. Evaluación: 20 puntos a la mejor solución, los demás obtendrán una calificación proporcional.