Subredes

UNIVERSIDAD DEL VALLE ESCUELA DE INGENIERÍA DE SISTEMAS Y COMPUTACIÓN FUNDAMENTOS DE ANÁLISIS Y DISEÑO DE ALGORITMOS ANDRÉS FERNANDO VELASCO MINIPROYECTO 2 NOVIEMBRE DE 2010
1. Introducción Elpresente proyecto tiene por objeto enfrentar a los estudiantes del curso: • • • • • • al análisis de un problema simple de optimización; al diseño de una solución usando programación dinámica; al diseño deuna solución usando un algoritmo voraz; a la implementación en un lenguaje de alto nivel de las soluciones diseñadas; al cálculo de complejidad temporal de las soluciones; y al problema de presentarclaramente en un documento corto lo esencial de su proyecto.

2. El problema En un río hay n embarcaderos, en cada uno de los cuales se puede alquilar un bote para ir a otro embarcadero que esté másabajo en el río. No se puede remontar el río. Una tabla de tarifas indica los costes de viajar entre los distintos embarcaderos. Se supone que puede ocurrir que un viaje entre i y j salga más baratohaciendo escala en k embarcaderos que yendo directamente. El problema consistirá en determinar la forma de viajar con coste mínimo entre un par de embarcaderos. Vamos a llamar a la tabla de tarifas,T. Así, T[i,j] será el coste de ir del embarcadero i al j. La matriz será triangular superior de orden n, donde n es el número de embarcaderos. 3. Análisis y diseño Usted deberá diseñar y analizar: • •Una solución usando programación dinámica: Siga los cuatro pasos descritos en clase y documente claramente cada uno de ellos. Una solución usando un algoritmo voraz: Describa claramente su algoritmohaciendo énfasis en el criterio usado para las decisiones voraces y en la corrección o no de su algoritmo con respecto a la optimalizad de la solución. Para cada caso haga un análisis de lacomplejidad en tiempo y en espacio de sus algoritmos. Para el caso voraz haga un análisis lo más detallado que pueda sobre la cercanía de sus soluciones al óptimo. Si siempre da el óptimo, presente una prueba...