Diseño
y Programación Orientados a Objetos
1er. Sem 2008
Tarea 1: Herencia e Interfaces: programación genérica
Recomendación: Lea detenidamente la tarea, si algo no lo
entiende consulte en clases, si es preciso se incorporarán
aclaraciones al final.
Esta tarea tiene por objeto
que:
- Usted se familiarice con el ambiente de
desarrollo que usará en otras tareas y su proyecto.
- Evalúe la herramienta que resulte más cómoda
para
usted.
En clases he sugerido trabajar con Emacs o Jgrasp.
- Practique la creación de (o aprenda a crear) Makefile
- Ejercite la generación automática de
documentación usando javadoc.
- Ejercite los conceptos de clases, herencia, interfaces y entrada
y salida de datos.
Descripción General
En esta tarea usted ejercitará interfaces y herencia a
través de algunos ejercicios de programación
genérica. Para ello deberá implementar dos algoritmos de
búsqueda y dos algoritmos de ordenamiento; sus implementaciones
deben procurar ser genéricas.
Dos algoritmos de ordenamiento son Bubble Sort e Insertion Sort
y dos algoritmos de búsqueda son búsqueda lineal (linear
search) y búsqueda binaria (binary search). Busque estos
algoritmos en wikipedia.
Los algoritmos serán aplicados a arreglos de N objetos de la
clase Estudiante. Para esta clase se tiene:
public class Persona {
private Persona() {}
public Persona (String nombre) {
this.nombre=nombre;
}
public String getName() {
return nombre;
}
private String nombre;
}
public class Estudiante {
private Estudiante() {}
public Estudiante(String nombre, float promedioPonderado) {
super(nombre);
pp= promedioPonderado;
}
public float getPromedioPonderado() {
return pp;
}
private float pp;
}
Usted deberá completar estas clases para dar cumplimiento a los
requerimientos de la primera y segunda parte de esta tarea.
La clase Ordenador es una clase abstracta con el
siguiente método:
/**
* Superclass para distintas implementaciones de algoritmos de
ordenamiento.
* @author Agustín J. González
*/
public abstract class Ordenador
{
/** Ordena una arreglo de objetos Comparable.
* @param A Arreglo de objetos comparables.
*/
public abstract void ordenar(Comparable[] A);
/** Obtiene el número de comparaciones realizadas en la
última invocación a ordenar.
* @return número de comparaciones hechas para ordenar el arreglo.
*/
public abstract int getNumComparaciones();
/** Obtiene el número de intercambio o enroques de datos
(swaps) durante la última operación de ordenamiento.
* @return número de intercambios de datos en última
comparación.
*/
public abstract int getNumIntercambios();
}
Primera Parte
Cree la clase BubbleSorter y la clase InsertionSorter como clases
heredadas de Ordenador.
Estas clases serán probadas en un programa que leerá
desde un archivo los nombres de
aproximadamente 50 estudiantes
(será proporcionado) a los cuales usted asociará
promedios ponderados aleatorios (entre 55 y 100). El ayudante bien
puede usar otro archivo con igual estructura (un nombre por
línea). La lectura será almacenada en un arreglo de
Estudiantes. Como respuesta su
programa entregará el tamaño del arreglo analizado, el
número de comparaciones y el
número de intercambios requeridos para ordenar el arreglo por
sus promedios ponderados. Luego de dar estos valores, esperará
por un retorno de carro para arrojar el listado de alumnos ordenados
por nombre promedio ponderado con el promedio ponderado nombre de cada uno.
Su programa debe repetir lo previo usando el algoritmo BubbleSort y
luego Insertion Sort.
Se espera que su programa de prueba contenga al menos dos
métodos: uno que efectuará la tarea antes señalada
(por ejemplo computarParte1)
usando como parámetro un objeto de clase Ordenador y el
método main. Éste invocará dos veces el
método previo primero con
un
instancia de BubbleSorter y luego con una instancia de
InsertionSorter. La idea es que usted vea cómo el método
computarParte1 puede diseñarse en forma genérica para
trabajar en un caso con un algoritmo y luego con el otro, el cual
será pasado como argumento.
Segunda Parte
Similar a lo anterior cree la clase abstracta Buscador, la cual tiene
los métodos:
int buscar(Object [] A, Object obj); retorna el índice del
arreglo que contiene el objeto ó -1 en caso de no encontrarlo.
int getNumComparaciones(); retorna el número de
comparaciones efectuadas para dar con el objeto o concluir que no
está.
Implemente las clases LinearSearcher y BinarySearcher como subclases de
Buscador. En el caso de binary search se debe cumplir que el arreglo de
datos del método buscar esté previamente ordenado.
Extienda su programa de prueba previo para arrojar el número de
comparaciones requeridas para buscar exitosamente un alumno (es
decir un alumno que está en misma lista usada en la primera
parte). Usted debe mostrar en pantalla el número de alumnos del
arreglo y el
número de comparaciones para encontrarlo. Primero
hágalo con búsqueda lineal y luego con algoritmo
de búsqueda binaria.
Observación: Daniel Caro
ayer hizo notar la diferencia entre búsqueda lineal y
búsqueda binaria. Mientras en la primera usar equals() es lo
natural y pedido, en búsqueda binaria se requiere comparar los
elementos para hacer la búsqueda. Esta comparación se
debe hacer con método compareTo(). Como resultado la
búsqueda retorna el índice del objeto con igual nota y no
necesariamente el objeto igual - equals - al argumento usado en
método buscar().
En la misma línea otro de sus compañeros
destacó que el arreglo en este caso no podía ser un
arreglo de Objetos dado que éstos no ofrecen el método
compareTo. Ayer expliqué la forma de resolver esta
situación; manteniendo la firma del método (para que la
redefinición opere y así también le ligado
dinámico) en el código poner algo del tipo:
Comparable [] newA;
if ( A[0] instance of
Comparable) newA= (Comparable
[]) A;
else return -1;
Hacer algo similar con el parámetro que se busca.
La tarea será revisada usando una ventana terminal o
consola en aragorn. Se requiere que
usted cree un archivo Makefile para que el ayudante compile su trabajo
usando:
$ make
Para ejecutar su programa el ayudante ejecutará
$ make run
Para generar la documentación el se correrá:
$ make doc
Notas:
En la documentación de esta tarea, no es necesario que usted
haga una descripción en alto nivel de los algoritmos usados.
Usted debe
entregar su código documentado siguiendo el estándar del
utilitario javadoc. Dé una mira al Generador
de Documentación y en particular los rótulos.
El archivo de nombres proporcionado
fue obtenido a partir de la lista del curso,
la cual fue procesada para generar los
nombres naturales.
Considere que el ayudante podría desarrollar otro main para
probar sus clases. Por ejemplo al buscar podría hacerlo con una
objeto copia (clone) de alguno del arreglo.
Vea el ejemplo
de
Makefile. Más información
sobre
Makefiles.