|
|
Ingeniería Informática Ingeniería Telemática Curso 2004-2005 |
Algoritmos y Estructuras de Datos Fundamentos de Programación 2 PRÁCTICA 1 |
|
|
Ingeniería Informática Ingeniería Telemática Curso 2004-2005 |
Algoritmos y Estructuras de Datos Fundamentos de Programación 2 PRÁCTICA 1 |
Gestión de un listado de libros
a. Realización de una tarea de programación que fomente la capacidad de análisis de un problema para, a partir de un enunciado abstracto, ser capaz de identificar las distintas fases que se deben abordar para alcanzar la solución.
b. Capacidad de modificación de un algoritmo dado (de ordenación y búsqueda) para que adaptarlo al planteamiento de un problema concreto.
c. Comparación de, al menos, dos métodos de ordenación directa y dos métodos de búsqueda (secuencial con centinela y binaria).
En general, cuando se tiene gran cantidad de información es conveniente informatizar el tratamiento de la misma para facilitar, entre otros, los procesos de búsqueda y clasificación.
En el caso que nos ocupa, se dispone del orden de 11.000 registros con información de libros (autor y título) sobre los que se desea poder realizar búsquedas.
Para ello se tendrá que realizar un programa que lea los datos de los libros, los almacene en memoria y luego ofrezca la posibilidad de realizar búsquedas sobre ellos, tanto de los libros de un determinado autor como de un libro concreto.
En esta práctica hay dos aspectos relevantes:
Por un lado, la tarea concreta de realizar un programa con una serie de especificaciones.
Respecto a este aspecto, el primer punto que se debe afrontar es la realización del formulario de documentación del programa, y como paso previo a esta documentación un primer proceso de análisis del problema y división del mismo en subtareas. Este análisis debe permitir definir qué funciones va a tener el programa y el organigrama del programa principal. Si al plantear las diferentes funciones que conformen el programa, se considera que alguna de ellas es realmente compleja se debe desarrollar esa función construyendo su organigrama.
Por otro lado, se plantea el objetivo de comparar diferentes algoritmos, tanto de ordenación como de búsqueda.
Los métodos de ordenación que se van a comparar serán el método Quick-Sort y algún otro, de entre los métodos directos de ordenación, que debe decidir el estudiante y justificar. Esto métodos se aplicarán para ordenador por autor los registros de libros.
Los métodos de búsqueda que se deben aplicar serán el método de búsqueda secuencial (con centinela) para la búsqueda de los libros por título y el método de búsqueda dicotómica (binaria) para la búsqueda de libros por autor.
El primer paso será decidir una estructura de datos válida para guardar los registros de los libros.
A continuación, y una vez leídos los registros (que están almacenados en el archivo “libros.dat” que se puede descargar desde la página web)*, se le ofrecerá al usuario la posibilidad de elegir, de entre los dos implementados, el método de ordenación para ordenar los registros por el autor. Para ordenar se tendrán que utilizar, adecuadamente adaptados a los datos que se manejan en este problema, los algoritmos de ordenación comentados en el apartado anterior. Además, para obtener información sobre la eficiencia de los métodos de ordenación, se deberán añadir contadores de comparaciones y asignaciones (exclusivamente de elementos del vector) en los algoritmos de ordenación, y mostrar los resultados tras la ordenación.
Finalmente, el programa deberá permitir al usuario buscar un libro o todos los libros escritos por un autor. Para ello solicitará, mediante en un pequeño menú, el tipo de búsqueda que se desea realizar (por autor o por título) y los datos que se desean buscar. Al estar ordenada la lista de libros por autor, sólo se podrá aplicar la búsqueda dicotómica en la búsqueda por autor. La búsqueda por título tendrá que realizarse de manera secuencial. En este caso, también habrá que modificar adecuadamente los algoritmos para que pueda aplicarse sobre la información que se maneja.
El programa, además de proporcionar los resultados de la búsqueda (datos de libros o información sobre su ausencia) deberá indicar el número de comparaciones realizadas sobre elementos del vector para poder localizar la información. Por esa razón, será necesario de nuevo la introducción en los algoritmos de contadores que contabilicen este tipo de operaciones.
(*) Formato del archivo de libros: la información de un libro ocupa 2 líneas. En la primera línea aparece el autor del libro y en la segunda el título.
Cinco días después de realizada la sesión de prácticas se entregará al profesor/a la siguiente información:
1) Archivo con el programa (pr01##.cpp)
dónde ## es el número asignado a la pareja (01, 02,...) en cada grupo de prácticas.
Al comenzar la siguiente sesión de prácticas se entregará al profesor el formulario con la documentación definitiva de la práctica reflejando todo el trabajo realizado realmente en la práctica.
Antes de poder empezar a realizar cualquiera de las prácticas es necesario presentar las hojas de especificación de programas (formulario de documentación de programas) con las tareas que se van a realizar en la práctica, explicando brevemente como se van a solucionarse los problemas que se plantean.
ENTREGA DE PROGRAMAS:
Los
días 12, 13, 14, 15 y 16 de Marzo de 2005, correspondientes
con las fechas de realización de prácticas 7, 8, 9, 10
y 11 de Marzo.
ENTREGA DE FORMULARIOS
DEFINITIVOS DE DOCUMENTACIÓN:
Los días 14, 15 y
16 de Marzo y 7 y 8 de Abril de 2005, correspondientes con las fechas
de realización de prácticas 7, 8, 9, 10 y 11 de Marzo.