CC30A Algoritmos y Estructuras de Datos

Prof. Rodrigo Paredes

Tarea 4

Fecha de entrega: jueves 21 de noviembre. No se aceptarán tareas atrasadas.

Objetivos

El objetivo de esta tarea es estudiar el costo en tiempo que se necesita para construir el árbol cobertor mínimo en función de la densidad de arcos del grafo. Se utilizarán grafos euclidianos no dirigidos representados con listas de adyacencia y el algoritmo Kruskal visto en clases.

Descripción de la tarea

Para los fines de esta tarea, un grafo euclidiano no dirigido 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 los arcos considerados en el grafo se eligen al azar. 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). Vamos a considerar un conjunto de arcos escogidos al azar de tamaño variable, comenzando con un grafo con pocos arcos hasta llegar al grafo completo; el tamaño del conjunto de arcos estará dado por la densidad de arcos. Un grafo con densidad 0.01 tiene 0.01*n(n-1)/2 arcos, es decir, tiene el 1% del total de arcos posible; un grafo con densidad 1.0 tiene 1.0*n(n-1)/2 arcos, es decir, es el grafo completo. Para medir como afecta la densidad al costo en tiempo se utilizará la representación de lista de adyacencia. Para no obtener resultados "inesperados", nos tenemos que asegurar que el grafo es conexo.

Usted debe escribir un programa acm (por "árbol cobertor mínimo") que pueda ser ejecutado como:

        java acm [-v] n densidad nreps

donde n es el número de nodos del grafo, densidad es la densidad de arcos del grafo (un valor en el rango [0.01, 1.00]) 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 con n nodos y densidad*n(n-1)/2 arcos.
Aplicar el algoritmo de Kruskal sobre este grafo para calcular el árbol cobertor de costo mínimo.
Anotar el tiempo requerido en la construcción del grafo (para esto puede utilizar el método public long getTime() de la clase Time)

Al terminar, el algoritmo debe imprimir el valor promedio del tiempo de construcción del árbol. 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 árbol 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 árbol en función de la densidad para un valor de n fijo en 1000, es decir, un grafo con 1000 nodos (si tienen problemas de memoria realicen las pruebas con 500 nodos e indiquen esto en el informe). Proponga un modelo de ajuste en función de la cantidad de arcos del grafo, se espera que a menor densidad la construcción del árbol cobertor mínimo sea más rápida.

Utilice nreps = 10 y densidad = 0.01, 0.02, 0.04, 0.06, 0.08, 0.10, 0.20, 0.40, 0.60, 0.80, 1.00.

Bonus

Analice como varía el peso del árbol y determine a partir de qué densidad el peso del árbol se "estabiliza". Indique el criterio de estabilización (por ejemplo, que la variación del costo sea menor a e%, o algo que sea "razonable") y muestre en un gráfico la variación del peso del árbol versus la densidad de arcos del grafo. Refine el gráfico en el rango en que se "estabiliza" el peso del árbol (esto es, una vez detectado el rango [a,b] en que estabiliza el peso del árbol, realice mediciones del peso dentro del rango).

Restricciones

Implemente el grafo con lista 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.
Conectividad del grafo: Supongamos que se numeran los nodos desde 0 hasta |V| - 1 (en el caso de la tarea desde 0 a 1000-1=999). Para asegurarse de que el grafo es conexo, lo más simple es que el grafo inicialmente contenga arcos (i,i+1) con i en el rango [0,|V|-2], por ejemplo: que el grafo contenga los arcos (0,1), (1,2), (2,3), (3,4), .. ,(998,999).

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.