CC30A Algoritmos y Estructuras de Datos

Prof. Rodrigo Paredes

Tarea 1

Fecha de entrega: martes 27 de agosto. No se aceptarán tareas atrasadas.

Objetivos

En esta tarea se pretende, junto con familiarizar al alumno con Java, entregarle una metodología que le permita: enfrentar un problema, construir un algoritmo que lo resuelva, definir un conjunto de pruebas que permitan analizar alguna característica interesante del problema, realizar los experimentos y por último modelar el comportamiento de la característica de interés.

El problema que vamos a abordar en esta tarea consiste en contar las inversiones de un arreglo. En clases vimos que la cantidad media de inversiones en un arreglo compuesto por elementos distribuidos uniformemente (sin elementos repetidos) es n(n-1)/4. En esta tarea vamos a verificar esto experimentalmente.

Descripción de la tarea

Si consideramos el orden ascendente, una inversión en un arreglo de números es cualquier par ordenado (i,j) con la propiedad de que i < j, pero a[i] > a[j] (el par (a[i], a[j] esta "desordenado" en el sentido ascendente). Por ejemplo, el areglo (1, 2, 4, 3, 5) tiene 1 inversión, y el arreglo (5, 1, 2, 3, 4) tiene 4 inversiones. Recuerde que la cantidad de inversiones de un arreglo corresponde a la cantidad de intercambios de elementos que necesita efectuar un algoritmo de ordenación que intercambia elementos adyacentes.

Se van a considerar tres algoritmos de ordenamiento de costo cuadrático:

burbuja
inserción
selección

Estos tres algoritmos se pueden adaptar de modo de, además de ordenar, cuenten exactamente todas las inversiones que tenía el arreglo original (desordenado). Por ejemplo, utilizando burbuja, basta con contar la cantidad de intercambios de elementos que se realicen durante toda la ejecución.

El programa que tendrán que desarrollar para esta tarea consiste en:

Generar un arreglo A = {1, 2, 3, ..., N}
B = desordenar(A)
Copiar el arreglo en tres arreglos auxiliares burB, insB, selB
1. burB = B,
2. insB = B
3. selB = B
ordenar burB con burbuja, y contar la cantidad de inversiones del arreglo original
ordenar insB con inserción, y contar la cantidad de inversiones del arreglo original
ordenar selB con selección, y contar la cantidad de inversiones del arreglo original

Para desordenar los arreglos utilice el siguiente algoritmo:

desordenar (int[] A) {
n = número de elementos de A
while (n > 1) {
    j = random(n - 1);
    intercambia A[j] con A[n]
    n--;
}
}

La metodología mostrada se utilizará con arreglos de distinto tamaño N, y para cada tamaño N se realizarán varias pruebas. De este modo vamos a verificar como aumenta la cantidad promedio de inversiones de un arreglo en función a su tamaño, independiente del algoritmo de ordenación que utilicemos, mediante una técnica de ajuste funcional.

Pruebas

Para cada valor de N, genere 5 arreglos desordenados y calcule el promedio de la cantidad de inversiones de los 5 arreglos de tamaño N para cada algoritmo de ordenación.

Considere N = 1000, 2000, 3000, 4000, ... , 10000.

Por último, tabule sus resultados de cantidad de inversiones, muestrelos en gráficos y calcule el ajuste polinomial de acuerdo al siguiente modelo:

p(N) = a · N^b

En esta parte tiene que calcular las constantes a y b. Para ello aplican logaritmo a la expresión anterior:

log(p(N)) = log(a) + N log(b)

y luego realizan una regresión lineal sobre esta expresion.

Restricciones

El programa debe ser escrito en Java.
Plazo de entrega: martes 27 de agosto. No se recibirán tareas atrasadas.
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).
Algoritmos de ordenación solicitados.

También esta prohibido el uso de las clases que se entregan en cc10a.
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.

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.