Algoritmo

UNA METODOLOGÍA PARA EL DISEÑO DE ESTRUCTURAS DE DATOS COMPLEJAS
Xavier Burgués1, Xavier Franch 1
1

L.S.I.-U.P.C. (Departament Llenguatges i Sistemes Informàtics, Universitat Politècnica de Catalunya) e-mail: diafebus|franch@lsi.upc.es Resumen: Se propone una metodología para el diseño e implementación de estructuras de datos complejas, con el objetivo de paliar la ausencia de propuestas eneste campo. La metodología está compuesta por cuatro etapas: análisis del enunciado, modelización del dominio, identificación de tipos abstractos de datos componentes y optimización de la estructura.

1.- MOTIVACIÓN. El contenido habitual de las asignaturas de estructuras de datos de las licenciaturas e ingenierías en informática distingue claramente dos partes, como mínimo: el estudio de unrepertorio versátil de tipos abstractos de datos (TADs) junto con su implementación individual mediante técnicas eficientes de representación, y una aproximación a la problemática del diseño e implementación de nuevas estructuras de datos (EDs), medianamente complejas, combinando dichos TADs invididuales para formar la solución. Si bien para la primera parte existen un sinfín de textos de indudablecalidad (especialmente por lo que a las EDs se refiere; no tanto a su estudio como implementación de TADs), no podemos decir lo mismo de la segunda. El diseño de nuevas EDs es un problema que algunos de estos libros o bien no abordan o bien tratan enumerando una serie de ideas generales que el programador debe ser capaz de aplicar a su contexto concreto, sin disponer de unas pautas bien definidasque lo guíen.

El objetivo de este artículo es proporcionar una metodología rigurosa para el diseño de nuevas EDs. Por “rigurosa” entendemos: una metodología con unas etapas bien definidas, usando unas notaciones con un significado claramente establecido. La metodología consta de cuatro etapas: análisis del enunciado, modelización del dominio, identificación de TADs componentes y optimización dela ED resultante.

2.- ANÁLISIS DEL ENUNCIADO. El objetivo de esta primera etapa consiste en dejar explícitas todas aquellas cuestiones del enunciado relevantes al diseño de la ED. Sin considerar las cuestiones habituales en una fase de análisis de los requisitos (resolución de ambigüedades, detección de inconsistencias, etc.), nos interesa aquí: § Determinar las operaciones aplicables sobre elnuevo TAD, es decir, su signatura. Estas operaciones deben tener un comportamiento claramente definido, ya sea mediante una especificación formal, ya sea mediante una explicación detallada de su funcionamiento. § Detallar las características de los datos involucrados en el nuevo TAD. Básicamente, qué se sabe sobre su volumen (conocido o desconocido y, en el primer caso, una cifra aproximada obien una calificación – “muchos”, ...) y también cualquier otra característica que pueda influir en el diseño o implementación de la ED (por ejemplo, intervalo válido de valores de un campo numérico). § Identificar los requisitos no funcionales de la ED. Básicamente, nos referimos aquí a la eficiencia esperada de las operaciones y a restricciones del espacio ocupado. La precisión puede variar de unproblema a otro, desde requisitos muy precisos (“la operación de consulta debe ser de coste constante”) hasta otros informales (“debe favorecerse el tiempo de ejecución de las operaciones de consulta”). Por ejemplo, consideremos el enunciado siguiente:
Se quiere gestionar el uso de videoclips en una emisora de TV. Cada video tiene un título que lo identifica, una duración expresada en minutos yestá editado por una compañía. Debe ser posible añadir elementos y listar los existentes. Asímismo, se debe dar soporte a la política de emisión siguiente para elegir un videoclip de una

duración dada: si hay videoclips no emitidos, se escoge el último adquirido; si no, se escoge el que hace más tiempo que se emitió.

Su análisis podría resultar en la información siguiente (por motivos de...