1158070 Optimización en redes
1151032 Temas selectos de Ingeniería en Computación I
Trimestre 2013 Invierno

Evaluación de los Temas 1 y 2: Redes y ruta más corta
Fecha de entrega: 11 de febrero de 2013 a las 10:00

Los alumnos de posgrado deberán hacer toda la evaluación. Los de licenciatura deberán resolver una parte de cada sección de la evaluación. Manden su tarea a mi correo (franz) en un pdf.

Sección I: Lectura de un capítulo de libro o de un artículo (6 puntos)

  1. Lea la Sección 6.5a del libro Combinatorial Optimization de Schrijver y aplique el algoritmo descrito allí a la gráfica G = (V, E) en la que V = {1, 2, ..., 8} y existe una arista entre los vértices p y q si y sólo si p y q son primos relativos.
  2. Lea y haga un resumen de una cuartilla de la Sección 10.1 del libro Randomized Algorithms de Motwani y Raghavan.

Sección II: Solución de problemas prácticos (6 puntos)

Considere la gráfica dirigida D = (V, A) con V = {r, a, b, d, f, g, h, j, k} y listas de adyacencia (como parejas de vecino y costo) Lr = (a, 2), (k, 7), (b, 5); La = (d, 8), (f, 4); Lb = (k, 3), (f, 2); Ld = (h, 5); Lf = (g, 3), (j, 7); Lg = (h, 4), (j, 3); Lj = (k, 4), (h,3); Lk = (d, 2), (h, 9), (g, 6), (f, 1); Lh = vacía. Resuelva el problema de caminos más cortos desde el vértice r:

  1. Usando el algoritmo de Dijkstra.
  2. Usando el algoritmo acíclico.

Sección III: Problemas teóricos de árboles (4 puntos)

  1. Demuestre con un ejemplo que un árbol de caminos más cortos en una gráfica no es necesariamente un árbol abarcador de costo mínimo de la misma gráfica.
  2. Demuestre con un ejemplo que un árbol abarcador de costo mínimo en una gráfica no es necesariamente un árbol de caminos más cortos de la misma gráfica.

Sección IV: Problemas teóricos de caminos más cortos (4 puntos)

En los siguientes dos problemas, el algoritmo diseñado debe basarse en la solución de un problema de caminos más cortos.

  1. Considere una gráfica dirigida D = (V, A) con costos en los arcos y dos subconjuntos disjuntos R y S de vértices. Diseñe un algoritmo para encontrar un camino de costo mínimo que una algún vértice en R con algún vértice de S.
  2. Considere n números enteros a1, ..., an. Se desea encontrar valores de i y j tales que 1 <= i <= j <= n+1 tales que se minimize la suma ai + ... + aj-1. Diseñe un algoritmo cuyo tiempo de ejecución sea O(n).