CC30A Algoritmos y Estructuras de Datos

Tarea 1

Fecha de entrega: lunes 02 de octubre

Objetivos

El objetivo de esta tarea es implementar los algoritmos de árbol de expansión mínimo de un grafo Kruskal y Prim, y luego realizar una discusión en donde se comparen las ventajas y desventajas de un algoritmo sobre el otro.

Descripción de la tarea

El objetivo de los algoritmos de construcción del árbol de expansión mínimo de un grafo no direccional definido con pesos no negativos, es encontrar el árbol que conecte todos los nodos de un grafo (razón por la que es llamada "árbol de expansión") y que la suma del peso de los arcos sea la mínima (razón por la cual es llamado "mínimo").
Para mayor información sobre los algoritmos Kruskal y Prim, remítase a los apuntes de clases. También se tiene información en la bibliografía existente de algoritmos en la biblioteca central (revisen el Cormen y el Sedgewick).

Restricciones

El programa puede ser escrito utilizando uno de los siguientes lenguajes imperativos, disponibles en anakena.dcc.uchile.cl, cipres.cec.uchile.cl, o los computadores del Zocalo del CEC.

C

C++

Java

Pascal

Turing

Para la implementación del algoritmo de Kruskal, deben implementar el algoritmo "Union Find".

Para la implementación del algoritmo de Prim, debe emplear un arreglo para controlar los costos.

Pruebas

Grafo 1
Grafo 2
Grafo 3

Línea 1: K
Línea 2: N_i, N_f, peso_if
Línea 3: N_i, N_f, peso_if
Línea 4: N_i, N_f, peso_if
Línea 5: N_i, N_f, peso_if
...
Línea j: N_i, N_f, peso_if

Donde:

K representa la cantidad de nodos, numerados desde 0 hasta K-1
N_i= nodo inicial del arco
N_f= nodo final del arco
peso_if = peso del arco que conecta los nodos N_i y N_f.

En la figura se ve el Grafo 1, indicando los arcos del árbol de expansión mínimo

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 la Magaly), 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 segir la siguiente pauta:

Portada

Informe Tarea X

Nombre de la tarea X

	Fecha:	fecha entrega
	Autor(es):	nombre(s) alumno(s)
	E-mail:	correo del (los) alumno(s)

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: Mostrar el uso de la metodología Top-Down, 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 anakena, en cipres o en los computadores del zocalo. Si las indicaciones que Usted entrega son erroneas al momento de compilar, la evaluación de su tarea será severamente penalizada.

Pruebas: Se debe señalar claramente cual es la llamada al programa y su salida. El número de pruebas puede variar dependiendo del problema. En general tres pruebas es suficiente.
Discusión:

Realize un análisis de la complejidad de de los dos algoritmos de construcción del árbol de extensión mínimo.
Indicar los tiempos teóricos de cada algoritmo.
Indicar en que caso es mejor un algoritmo sobre el otro. Justifique sus respuestas.
Compare los tiempos de ejecución de cada algoritmo empleado.

Anexos:

Listados: Se debe incluir un listado con el programa completo que se compiló realmente.
Otros: De ser necesario, cualquier información adicional se debe agregar en los anexos y debe ser ferenciada en alguna sección del informe de la tarea.