Primer proyecto práctico de AYDA-2012

Primer proyecto práctico para de Análisis y Diseño de Algoritmos
Postgrado de Computación de la Universidad de Los Andes

Contents

• 1  Introducción
• 2  La clase DynArray<T>
• 3  El trabajo
  • 3.1  Requerimiento para DynArrayStack<T>
  • 3.2  Requerimientos para DynArrayQueue<T>
• 4  Evaluación
• 5  Condiciones

1  Introducción

El fin de este trabajo es diseñar e instrumentar dos clases genéricas llamadas DynArrayStack<T> y DynArrayQueue<T> . DynArrayStack<T> representa una pila instrumentada mediante un arreglo dinámico. Análogamente, DynArrayQueue<T> representa una cola representada mediante un arreglo dinámico.

A efectos de compatibilidad y de mínimo impacto de sustitución por otros tipos abstractos de datos o clases equivalentes, las dos clases requeridas deben exportar exactamente la interfaz de las clases ArrayStack<T> y ArrayQueue<T>. Es posible, si se juzga útil, necesario o pertinente, exportar otros métodos.

Hay dos diferencias fundamentales entre las implementaciones con arreglos estáticos y las implementaciones con arreglos dinámicos:

1. No es necesario especificar la dimensión del arreglo.
2. El consumo de memoria crece y decrece conforme crezca o decrezca la cantidad de elementos almacenados.

Adicionalmente, las dos clases requeridas deben exportar el constructor de copia y el operador de asignación, los cuales actualmente no están presentes en ArrayStack<T> y ArrayQueue<T>. También, ambas clases deben soportar constructores adicionales que permitan definir longitudes de directorio, segmento y bloque.

2  La clase DynArray<T>

Como se mencionó brevemente en clase, la clase DynArray<T> instrumenta un arreglo dinámico. Esta clase podría servir como implementación de las clases requeridas DynArrayStack<T> y DynArrayQueue<T> . En ese sentido, conviene mencionar los siguientes métodos de DynArray<T> :

1. void cut(const size_t & new_dim): el cual libera la máxima cantidad de memoria entre la nueva dimensión new_dim y la antigua antes de invocar a cut().

   DynArray<T> no posee un método que libere memoria entre un rango de entradas. Así, una versión de cut(const size_t & l, const size_t & r) probablemente sea necesaria para liberar memoria en la instrumentación de DynArrayQueue<T> .

2. El simétrico de cut() es void reserve(const size_t & l, const size_t & r): el cual asegura existencia de memoria para el rango de entradas del arreglo comprendido entre l y r.

   Aunque probablemente este método no se requiera para el proyecto, su implementación constituye una plantilla o punto de partida para la versión de void cut(const size_t & l, const size_t & r).

3. DynArray<T> exporta un constructor que recibe de parámetros las longitudes de directorio, segmento y bloque (en potencias de 2).
4. El constructor copia y el operador de asignación se valen de un método llamado copy_array(src), el cual copia, elemento por elemento, las entradas de src hacia las de this. Una crítica a este método es que copiar cada entrada requiere calcular los índices de directorio, segmento y bloque.

   Un enfoque que podría deparar en una mejora notable de desempeño consistiría en copiar de src bloques y segmentos enteros hacia this. Tome en cuenta que, en el caso del operador de asignación, this podría tener tamaños de directorio, segmento y bloque distintos a this.

   Una mejora en copy_array() podría acelerar notablemente el constructor copia y el operador de asignación de las clases requeridas DynArrayStack<T> y DynArrayQueue<T> .

3  El trabajo

El trabajo debe entregar las dos implementaciones solicitadas de DynArrayStack<T> y DynArrayQueue<T> .

3.1  Requerimiento para DynArrayStack<T>

Exactamente la misma interfaz de ArrayStack<T>. Pero se aparta y libera automáticamente memoria conforme crezca y decrezca la pila.

3.2  Requerimientos para DynArrayQueue<T>

Exactamente la misma interfaz de ArrayQueue<T>. Pero se aparta y libera automáticamente memoria conforme crezca y decrezca la cola.

El enfoque que se sugiere es el del arreglo circular planteado en la clase del 22 de marzo. Este enfoque es similar al usado por ArrayQueue<T>, con la excepción de que DynArrayQueue<T> debería de liberar la máxima cantidad de memoria posible (en segmentos y bloques) comprendida entre 0 y l−1 (ver figura)

4  Evaluación

La evaluación se dividirá en dos “partes”:

Clase	%
DynArrayStack<T>	30 %
DynArrayQueue<T>	70%

A su vez, cada parte se evaluará según los siguientes “aspectos”:

Revisión del fuente	30 %
Velocidad	40 %
Consumo de memoria	30 %

Cada fuente se revisará manualmente; todos los fuentes se analizarán con herramientas de detección de similitudes. En función de una comparación global se asignará una puntuación a cada proyecto correspondiente al “aspecto” revisión del fuente.

La velocidad y consumo de memoria se medirán mediante programas de prueba que se revelarán después de la evaluación y publicación de resultados. Por esa razón es extremadamente importante que se asegure de respetar la interfaz solicitada., pues de no hacerlo será imposible evaluar los aspectos de velocidad y consumo de memoria.

El trabajo de mayor velocidad recibirá una calificación que será la más alta de todas (no necesariamente 20). El resto de los trabajos tendrán puntuación normalizada a la más alta. Por ejemplo, si el trabajo más veloz tiene una puntuación de 16 ptos y demora 10 segundos, entonces un trabajo que demore 12 segundos, tendrá una puntuación de 16 × 10/12 = 13.3.

El mismo criterio se aplicará para el consumo de memoria.

La calificación de cada “aspecto” se efectuará según la ponderación estipulada. La calificación definitiva del proyecto será según la ponderación de cada “parte”.

5  Condiciones

El proyecto es estricta y enteramente individual. No está permitido ningún tipo de ayuda externa ni comunicación entre compañeros de curso. Ud y sólo ud debe ser quien haga el trabajo.

Por si acaso no se ha entendido bien: no está permitido el trabajo en equipo.

La entrega consistirá de dos archivos llamados tpl_dynArrayStack.H y tpl_dynArrayQueue.H, correspondientes a las implantaciones de DynArrayStack<T> y DynArrayQueue<T> respectivamente.

Si efectúa modificaciones o añadiduras en la clase DynArray<T> , entonces debe entregar el archivo con las respectivas modificaciones.

Si se juzga conveniente, especialmente si se modifica la clase DynArray<T> , entonces puede ser necesaria una cuartilla explicativa del trabajo.

La fecha de entrega es el lunes 30 de abril, con la secretaria del postgrado.

---

This document was translated from L^AT_EX by H^EV^EA.