Cuarto examen parcial de Diseño de Algoritmos
Trimestre 2012 Invierno
Entrega: 2 de abril de 2012 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. Recuerda
que la calificación de este examen se promediará con la
de los otros tres exámenes.
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.