Introducción a las Estructuras de Datos (Parte 2)

CHenry [chenry@lab.matcom.uh.cu]

Tipos de Datos Abstractos (TDA).

Para brindar descripciones adecuadas a los objetos de un tipo determinado, se necesita una metodología que cumpla las siguientes condiciones:

Descripciones precisas y sin ambigüedades, es decir, que exprese con claridad y de manera concisa la funcionalidad del tipo de dato que se pretende describir.

Descripción completa, o lo más completa posible, de las propiedades que distinguen a un determinado tipo de dato del resto de los tipos.

Especificar solo lo necesario (NO a las sobreespecificaciones).

Ejemplo 3:
En la descripción de los objetos de tipo Pila se deben especificar sólo aquellas operaciones propias de una pila, y no otras de carácter específico que estén relacionadas con una implementación determinada, como es la propiedad estáLlena de una pila que sólo tiene lugar cuando la implementación se hace sobre una memoria de tamaño fijo como lo es un arreglo. Si esta propiedad aparece en la descripción, entonces se está haciendo una sobreespecificación de los objetos de este tipo.

Por lo tanto, para describir el comportamiento de un tipo de objetos, que es lo mismo que describir el tipo de dato al que pertenecen, se necesita seguir un método que permita:
• completitud
• precisión en las descripciones

Y no tenga:
• ambigüedades
• sobreespecificaciones

Definición 4:

Un axioma es una sentencia clara y evidente por si misma que no necesita ser demostrada (5). Un axioma es una verdad lógica.

Ejemplo 4:
• Una pila, al crearse, está vacía.
• Todo elemento es igual a sí mismo.

Definición 5:

Una función f: A -> B es total si está definida x A. Una función es parcial cuando no es total.

Definición 6:

Sea la función parcial f: A -> B definida en C A (subconjunto propio, o sea, nunca llega a ser A). La función cf: A -> {true, false} es una función característica de f si x A se cumple que cf(x) = true si y solo si x C.

Definición 7:

Una precondición es una función característica de una función parcial. En otras palabras, es una condición necesaria para que dado un elemento del dominio de una función parcial se pueda evaluar dicha función en ese elemento.

Ejemplo 5:
• Para pedir el tope de una pila, esta no puede estar vacía.

Definición 8:

Un Tipo de Dato Abstracto (TDA) es un modelo matemático formado por un conjunto de operaciones (funciones parciales o totales) definidas sobre él y que cumplen con determinados axiomas y precondiciones. En resumen, algo así como:

Modelo Matemático = conjunto de operaciones + axiomas + precondiciones

Un Tipo de Dato Abstracto describe un tipo de dato, y a su vez, todo tipo de dato está caracterizado por un Tipo de Dato Abstracto. A la hora de especificar un Tipo de Dato Abstracto, deben tenerse en cuenta los siguientes aspectos:

• Tipo de dato que describe (nombre que se le da al tipo).
• Funciones (una por cada operación definida sobre el tipo de dato descrito).
• Axiomas (condiciones que se imponen a las funciones para describir el comportamiento deseado).
• Precondiciones (condiciones necesarias para que se puedan efectuar determinadas operaciones definidas sobre el tipo de dato).

Ejemplo 6:
Hagamos la descripción de los objetos de tipo Pila (STACK). Cualquier otra definición de un Tipo de Dato Abstracto puede tomar este ejemplo como base.
• Tipo:
STACK [G]

En esta definición del tipo de dato se está haciendo una descripción genérica de una pila (una pila de enteros tiene las mismas operaciones y el mismo comportamiento que una pila de cadenas de caracteres). Las propiedades de una pila no dependen de la información que en ella se almacena, lo más correcto es entonces definir un ADT genérico que las describa a todas por igual.

Cuando se especifica STACK [G], G es un parámetro formal genérico que representa simbólicamente el tipo de información que se almacenará.

De STACK [G] se hacen derivaciones a través de G, por ejemplo:
• STACK [INTEGER]
• STACK [STRING]
• STACK [CUENTA_BANCARIA]

Donde INTEGER, STRING y CUENTA_BANCARIA son también tipos de datos abstractos. Cuando se define un TDA genérico se presenta una recursión, porque se puede definir entonces STACK [STACK [INTEGER]].

• Funciones (describen las operaciones que se pueden realizar con los objetos de tipo STACK [G]; el concepto matemático que más se corresponde a la representación de las operaciones es el de función; cada función describe una operación):
• push: STACK[G] x G => STACK[G]
• pop: STACK[G] -> STACK[G]
• top: STACK[G] -> G
• empty: STACK[G] => BOOLEAN
• new: STACK[G]

Normalmente cuando le hacemos push a una pila, lo que se hace es poner el elemento en el tope de esa misma pila. Pero conceptualmente, cuando hacemos esta operación lo que obtenemos es una nueva pila que contiene los elementos de la anterior más el nuevo elemento. Por lo que la operación push se puede representar de manera funcional. Igualmente sucede con la operación pop.

La operación new es una función de creación. En este caso particular no necesita de ningún argumento, por eso escribimos new: STACK[G] y no new: => STACK[G], aunque esta segunda variante es más formal.

La notación f: A => B indica que la función es total (está definida para todos los valores del dominio). La función pop es parcial porque no está definida para las pilas vacías, por eso se utiliza -> en vez de =>

En las funciones push y pop, STACK[G] aparece en el dominio y en la imagen, por eso se dice que estas operaciones son de transformación. En el caso de empty y top, STACK[G] aparece solamente en el dominio, en este caso son funciones de consulta. Se dice además que new es de creación porque STACK[G] aparece solamente en el dominio. Lo mismo ocurre con otros tipos de datos abstractos.

• Axiomas (indican que lo que estamos describiendo es una pila y no otra cosa. Expresan cual es la semántica que las funciones tienen que cumplir; es falso decir que un tipo de dato que tenga las operaciones anteriormente descritas sea una pila):

Sea s de tipo STACK[G], x de tipo G.
• top(push(s, x)) = x: expresa la estrategia de almacenamiento de la información (LIFO).
• pop(push(s, x)) = s: expresa la estrategia de almacenamiento de la información (LIFO).
• empty(new): expresa que toda pila nueva se genera vacía.
• not empty(push(s, x)): cualquier pila tras habérsele hecho un push no esta vacía.

Como se ve, la interrelación entre las diferentes funciones expresadas a través de los axiomas, deja explícita las particularidades que distinguen el funcionamiento de cada una de ellas.

• Precondiciones (condiciones que determinan para una operación descrita a través de una función parcial cuáles son los valores del dominio para los que existe su imagen):
• pop(s: STACK[G]): not empty(s). La función pop no está definida para pilas vacías, o sea, para hacer un pop es necesario que la pila no este vacía.
• top(s: STACK[G]): not empty(s). La función top no está definida para pilas vacías, o sea, para pedir el top de una pila es necesario que esta tenga algún elemento.

Finalmente el tipo de dato abstracto queda formalizado de la manera siguiente:

Pila
Tipo	STACK[G]
Funciones	push: STACK[G] x G Þ STACK[G] pop: STACK[G] -> STACK[G] top: STACK[G] -> G empty: STACK[G] => BOOLEAN new: STACK[G]
Axiomas	top(push(s, x)) = x pop(push(s, x)) = s empty(new) not empty(push(s, x))
Precondiciones	pop(s: STACK[G]): not empty(s) top(s: STACK[G]): not empty(s)

La definición del tipo de dato abstracto no implica que las operaciones definidas sean las únicas. Para representaciones concretas, pude que sea necesario añadir nuevas operaciones.

Ejemplo 7:
Cuando se desea implementar un STACK sobre un espacio fijo de memoria, debemos añadir la operación:
isfull: STACK[G] => BOOLEAN

a partir de la cual se detectan las situaciones de overflow sobre la pila.

Un Tipo de Dato Abstracto es, en resumen, un mecanismo formal para describir cualquier estructura de datos que queramos diseñar desde el punto de su funcionalidad.

Artículos relacionados