CC30A Algoritmos y Estructuras de Datos

Prof. Rodrigo Paredes

Tarea 5 (recuperativa)

Objetivos

El objetivo de esta tarea es estudiar el costo en tiempo y memoria que se necesita para construir un t-spanner. Se utilizarán grafos euclidianos no dirigidos completos representados con matriz de adyacencia y el algoritmo básico de construcción de t-spanners que se muestra en el documento adjunto.

Descripción de la tarea

Para los fines de esta tarea, un grafo euclidiano no dirigido completo es un conjunto de puntos (x,y) dentro del cuadrado unitario [0,1]×[0,1], en donde los arcos del grafo representan la longitud entre los extremos del arco y se consideran todos los arcos entre todos los nodos del grafo. El costo de un arco es igual a la distancia euclidiana entre los extremos (esto es, el costo de un arco es igual a su longitud).

Definición de t-spanner. Considere un grafo G = G(V, A) formado por un conjunto de vértices V y un conjunto de arcos con pesos no negativos A. En este grafo es posible determinar los caminos más cortos entre todos los pares de vértices. Este problema se puede resolver utilizando |V| iteraciones del algoritmo de cálculo de caminos más cortos (Dijkstra), considerando todos los vértices como nodo de origen; o con el algoritmo de Floyd. Un t-spanner es un grafo G' = G' (V, E); E subconjunto de A (note que utiliza el mismo conjunto de vértices y un subconjunto de los arcos), construido a partir del grafo G original, considerando una versión relajada de la condición de encontrar los caminos más cortos entre pares de nodos. La principal propiedad de un t-spanner es que garantiza que el costo del camino entre cualquier par de vértices del grafo G' es a lo sumo t veces la distancia del camino mínimo obtenido en el grafo original G, lo que se conoce como condición de t-spanner. Note que al menos necesita |V| - 1 arcos, para que el grafo G' sea conexo y que a lo más necesita insertar los A arcos del grafo original G. Mayor información se muestra en el documento adjunto.

Usted debe escribir un programa tspanner que pueda ser ejecutado como:

        java tspanner [-v] n t nreps

donde n es el número de nodos del grafo, t el factor de "estiramiento" de las distancias y nreps el número de veces que se debe repetir el experimento.

El programa debe repetir nreps veces lo siguiente:

Generar un grafo euclidiano aleatorio no dirigido completo con n nodos.
Aplicar el algoritmo básico de construcción de t-spanners sobre este grafo para el valor de t indicado.
Anotar el tiempo requerido en la construcción del grafo (para esto puede utilizar el método public long getTime() de la clase Time o Date) y la cantidad de arcos que contiene el t-spanner construido.

Al terminar, el algoritmo debe imprimir el tiempo de construcción del t-spanner y la cantidad de arcos del t-spanner para cada repetición, y los valores promedio de tiempo y arcos para las nreps repeticiones. Si se especifica la opción -v (verboso), el programa debe comenzar escribiendo la lista de todos los arcos del árbol mínimo, de a uno por línea. Cada arco se imprime indicando las coordenadas de sus extremos y la distancia entre ellos: x1 y1 x2 y2 dist. (Esta opción le permitirá examinar el t-spanner resultante y depurar su programa). Por ejemplo: 0.2 0.2 0.5 0.6 0.5.

Pruebas

Utilizando este programa, usted debe realizar un estudio para tratar de determinar de qué manera varía el tiempo de construcción promedio del t-spanner y la cantidad de arcos promedio en función de la cantidad de nodos n. Proponga un modelo de ajuste en función de la cantidad de nodos del grafo.

Utilice nreps = 5, t = 1.5, 2.0 y 2.5 y n= 100, 200, 300, 400y 500.

Restricciones

Implemente el grafo con matriz de adyacencia.
El programa debe ser escrito en Java.
Queda prohibido utilizar bibliotecas o clases preconstruidas en el lenguaje que implementen:

Listas, o arreglos (por ejemplo NO use la clase List y sus derivadas, y NO use la clase Arrays y sus derivadas).
Grafos

También esta prohibido el uso de las clases que se entregan en cc10a.
Para ordenar el conjunto de arcos utilice heapsort, quicksort o mergesort (uno de los tres solamente), usted debe implementar el algoritmo de ordenación escogido.
La tarea es individual.
Para la tarea tienen que entregar un informe de resultados junto al código fuente (el programa que implementa la tarea). No se aceptan códigos si informe ni informes sin código.
Cualquier falta a las restricciones anteriores invalida irrevocablemente la tarea. Revisen las normas descritas en el plan del curso

Hints

Para la generación de números aleatorios pueden utilizar el método Math.random(), o un objeto de la clase Random (mayor referencia en la API de java). Se recomienda el uso de la clase Random.
Recuerde que para representar un grafo no dirigido hay que considerar que los arcos son bidireccionales.
El documento que acompaña la tarea corresponde al capítulo de antecedentes de una tesis. Les recomiendo que se lean detenidamente las secciones 2.2.1, 2.2.2, 2.2.3, 2.2.6, 2.2.7 en donde se explica en detalle conceptos básicos de grafos (2.2.1), la definición del t-spanners (2.2.2), un ejemplo de construcción de t-spanners para un grafo dado (2.2.3), el algoritmo básico de construcción de t-spanners (2.2.6) y el análisis del algoritmo básico (2.2.7). Las secciones 2.2.4 tiene que ver con la relación entre t-spanners y la aplicación principal de la tesis y el 2.2.5 con el estado del arte de los algoritmos de t-spanners que van mucho más alla de lo que se les pide en la tarea (si les interesa se los explico en algún momento).

Ponderación

El informe equivale a un 50% de la nota de tarea.
El código equivale a un 50% de la nota de tarea.

Entrega de la tarea

La entrega de la tarea debe incluir un informe escrito donde se describa y documente el programa realizado, y se incluyan ejemplos de entradas y salidas.
El informe debe ser entregado en la Secretaría Docente de Computación (donde Magaly, tercer piso Edificio de Computación, hasta las 17:00 horas del último día de plazo), y el código fuente (junto a un archivo README que explique como compilar) debe ser enviado utilizando el Cursomático de cc30a.
El contenido del informe debe seguir la siguiente pauta común para todas las tareas:

Portada

Informe Tarea X

Nombre de la tarea X

	Fecha:	fecha entrega
	Autor:	nombre alumno
	Sección:	sección que corresponda
	E-mail:	correo del alumno

Introducción: Descripción del problema y de su solución
Análisis del Problema: Se expone en detalle el problema, los supuestos que se van a ocupar, las situaciones de borde, y la metodología para abordar el problema.
Solución del problema:

Algoritmo de solución: Se detallan los pasos a seguir para solucionar el problema. De ser necesario, se recomienda incluir figuras, tablas, etc., que permitan mejorar la comprensión del problema.
Diagrama de Estados: Muestra en forma global el programa.
Diseño: Explicitar las Pre y Post condiciones consideradas, mostrar los invariantes empleados.
Implementación: Se debe mostrar el código del programa que soluciona el problema (omita los detalles que no tengan relevancia para el problema), explicando lo que hace el código. Se recomienda usar nombres representativos a las variables. NOTA: El código generado para resolver la tarea debe corresponder al diseño descrito, preocúpese de realizar los comentarios que sean necesarios.
Modo de uso: Se debe explicar el modo de uso del programa y el modo de compilación. Nota: la tarea debe ser compilable en cipres o en los computadores del zócalo. Si las indicaciones que Usted entrega son erróneas al momento de compilar, la evaluación de su tarea será severamente penalizada.

Resultados: En esta sección se deben indicar las pruebas realizadas y sus resultados. Se debe señalar claramente cuál es la llamada al programa y su salida. En esta sección debe incluir las tablas y gráficos necesarios solicitados, y el análisis de los resultados. En este capítulo adjunten las conclusiones obtenidas de los resultados de la tarea.
Anexos:

Listados: Se debe incluir un listado con el programa completo que se compiló realmente (utilicen una fuente pequeña (8 pt) en este listado).
Otros: De ser necesario, cualquier información adicional se debe agregar en los anexos y debe ser referenciada en alguna sección del informe de la tarea.