TIPOS ABSTRACTOS DE DATOS - TADS
El objetivo del estudio de las estructuras de datos es la representación de la información (datos) que permitan obtener un algoritmo lo más sencillo posible, para lo cual se tiene en cuenta:
Ejemplo 4.1:- Problemas a enfrentar
- Buscar un libro en la biblioteca
- Uso de números romanos o arábigos
Los problemas reales tienden a ser complejos porque involucran demasiados detalles, y resulta imposible considerar todas las posibles interacciones a la vez, en este aspecto la abstracción constituye una herramienta en la especificación de un TAD, ya que por medio de esta capacidad solo se tienen en cuenta los aspectos más relevantes del problema objeto de análisis y a partir de la abstracción se determina "el que" del problema a tratar, sin preocuparse de entrada por los aspectos de la implementación ("el como").
El razonar en términos de abstracciones conlleva una serie de ventajas:
La evolución de la Programación muestra una tendencia a incluir mecanismos de abstracción cada vez de más alto nivel :
Figura 4.1 Relación Especificación - Abstracción - Implementación
La figura 4.1 representa la abstracción como una barrera entre la especificación y la implementación. Los clientes de una entidad solo conocen la parte de la especificación que les permite utilizar la entidad sin preocuparse por la implementación.
Para entender el concepto de tipo abstracto de datos analicemos la diferencia entre los tipos predefinidos y los tipos definidos por el programador.
Ejemplo 4.2:- Ejemplo TAD deficiente
Si para definir un tipo de datos para representar fechas,
utilizamos una representación como esta:
typedef int TDia;
typedef enum { enero, febrero, ... , diciembre } TMes;
typedef int TAnyo;
typedef struct { TDia dia; TMes mes; TAnyo anyo; } TFecha;
Debido a que se tiene libre acceso a la representación del tipo de datos, es posible realizar operaciones absurdas con respecto a la semántica, como:
fecha.mes = febrero;
fecha.dia = 30;
Al decir que TFecha es un TAD debe poseer las operaciones que restrinjan la asignación de valores erróneos como el día 30 al mes de febrero.
Un tipo de dato abstracto o TDA es un modelo matemático compuesto por una colección de operaciones definidas sobre un conjunto de objetos abstractos que modelan elementos del mundo, donde dichas operaciones simulan el comportamiento que el elemento modelado tiene en el mundo del problema.
El concepto de tipo de dato abstracto (TDA, Abstract Data Types ), fue propuesto por primera vez hacia 1974 por John Guttag y otros, pero no fue hasta 1975 que por primera vez Liskov lo propuso para el lenguaje CLU.
Un TDA está caracterizado por un conjunto de operaciones (funciones) al cual se le denomina usualmente como su interfaz pública y representa el comportamiento del TDA; mientras que la implementación (como la parte privada del TDA) está oculta al programa cliente que lo usa. Todos los lenguajes de alto nivel tienen predefinidos TDA; que son los tipos denominados simples y las estructuras predefinidas, y estos tienen sus interfaces públicas que incluyen las operaciones como la +, -, *, etc.
Cuando se habla de un TDA no se hace ninguna alusión al tipo de los elementos sino tan sólo a la forma en que están dispuestos estos elementos. Sólo interesa la estructura que soporta la información y sus operaciones. Para determinar el comportamiento estructural basta con observar la conducta que seguirán los datos.
Un TDA tendrá una parte que será invisible al usuario la cual hay que proteger y que se puede decir que es irrelevante para el uso del usuario y está constituida tanto por la maquinaria algorítmica que implemente la semántica de las operaciones como por los datos que sirvan de enlace entre los elementos del TDA, es decir, información interna necesaria para la implementación que se esté haciendo para ese comportamiento del TDA. Resumiendo podemos decir, que tanto la implementación de las operaciones como los elementos internos del TDA serán privados al acceso externo y ocultos a cualquier otro nivel.
Un TDA representa una abstracción:
Se puede decir que un TAD es un tipo de dato, que se agrega al lenguaje de programación, para representar un elemento involucrado en el problema que se desea resolver. De esta forma se le permite al lenguaje que se le acerque al mundo del problema, manejando los datos que allí se encuentran. En el proceso de desarrollo de software, dentro del mundo del problema casi siempre es posible identificar entidades que permiten expresar la solución en términos más sencillos, más fáciles de mantener y de probar.
Un tipo abstracto de datos se compone de:
4.2.1 Encapsulamiento:
El encapsulamiento consiste en aislar las cuestiones de implementación de las de especificación, es decir, en esconder los detalles de implementación de un determinado objeto, sea este un tipo de dato o un algoritmo, y mostrar tan sólo su especificación.
De este modo, nos centraremos en el qué y ocultaremos el cómo. Por ejemplo, en el caso del tipo de datos REAL, el lenguaje proporciona al usuario la capacidad de definir variables de este tipo, de acceder y modificar su contenido, de realizar operaciones aritméticas con las mismas. Sin embargo, el usuario no tiene que preocuparse de cómo se almacenan los distintos números reales, ni del tratamiento que es necesario realizar con sus representaciones binarias para sumarlos o multiplicarlos. La técnica que se utiliza para lograr la ocultación de la información es el encapsulamiento.
El uso de la abstracción y el ancapsulamiento proporcionan varias ventajas a la hora de desarrollar programas complejos o definir nuevos tipos de datos:
4.3 Representación de un Objeto Abstracto
Al comenzar con el proceso de diseño de un TAD es necesario tener una representación abstracta del objeto sobre el cual se quiere trabajar, sin necesidad de establecer un compromiso con ninguna estructura de datos concreta, ni con ningún tipo de lenguaje de programación seleccionado. Esto va a permitir expresar las condiciones, relaciones, restricciones y operaciones de los elementos modelados, sin necesidad de restringirse a una representación interna concreta.
El primer paso en el proceso de modelado de un TAD consiste en definir el estado interno del objeto abstracto por medio de algún formalismo matemático, gráfico o descriptivo
Ejemplo 4.3:- Descripción TAD Matriz
TAD Matriz
| 0 | k | m-1 | |||
0 |
|||||
i |
xi,k | ||||
n-1 |
Con esta notación es posible hablar de cada uno de los componentes de una matriz, de sus dimensiones, de la noción de fila y columna, de la relación entre elementos, sin necesidad de establecer unas estructuras de datos concretas para manejarlos.
Ejemplo 4.4:- Descripción TAD Diccionario
<[Palabra1, <s11,...,s1k>], [Palabra2, <s21,...,s2k>], [PalabraN, <sN1,...,sNk>]>
En esta notación, se hacen explícitas agunas características del elemento diccionario, que está formado por un conjunto de palabras que a su vez posee un conjunto de significados.
El invariante de un TAD establece la validez para cada uno de sus objetos abstractos en términos de condiciones sobre su estructura interna y sus componentes, indicando en que casos un objeto abstracto modela un elemento posible del mundo del problema. Estructuralmente, el invarianrte esta compuesto por condiciones que restringen el dominio de los componentes internos y por relaciones entre ellos.
El invariante está relacionado con la corrección de la implementación del TAD en los siguientes aspectos:
Lo importante no es escribir el invariante de la representación formalmente, sino determinar (aún con una descripción informal) de entre todos los valores que puede tomar el tipo representante cuáles representan valores válidos del TAD que estamos diseñando.
Ejemplo 4.5:- Invariante TAD Diccionario
TAD Diccionario: <[Palabra1, <s11,...,s1k>], [Palabra2,
<s21,...,s2k>], [PalabraN, <sN1,...,sNk>]>
El invariante debe incluir condiciones como:
- Las palabras están ordenadas ascendentemente y no hay repetidas ->
elem(i).palabra<elem(i+1).palabra, 1<=i<=N
- Los significados están ordenados ascendentemente y no hay repetidos
-> elem(i).sig(r)<elem(i).sig(r+1), 1<=i<=N, 1<=r<=k
- Toda palabra tiene por lo menos asociado un significado -> Para todo elem(i)=[palabra,<sig(1),...,sig(k)>],
k>0.
Si un objeto del TAD no cumple cualquiera de estas condiciones,
implica que no se encuentra modelando un elemento del TAD y por lo tanto la
representación no es válida.
La especificación de un TAD debe cumplir con que es precisa, es general, es legible y no presenta ambigüedad
Una especificación para un tipo abstracto de datos consta
de:
— La identificación del conjunto de valores posibles y,
— La especificación pre/post de cada una de las operaciones.
Inicialmente la especificación de un TAD parte de una metodología semi - formal, donde se especifican Tipo, Sintaxis y Semántica del TAD que se está modelando.
4.5.1 Especificación semiformal
TAD: Nombre del Tipo
Sintaxis: Sintaxis de las operaciones
operacion(listado de tipo
de argumentos): tipo del resultado
Semántica: Efecto de las operaciones
operacion(valores concretos)
=>expresión del resultado
Ejemplo 4.6:- Especificación Semi - Formal TAD Natural
TAD: Natural
Sintaxis:
Cero:Natural
Sucesor(Natural):Natural
Escero(Natural):Booleano
Igual(Natural,Natural):Booleano
Suma(Natural,Natural):Natural
Semántica: Para todo n,m que pertenecen al tipo Natural
EsCero(Cero) => Verdadero
EsCero(Sucesor(n)) => Falso
Igual(Cero,n) => EsCero(n)
Igual(Sucesor(n),Cero) => Falso
Igual(Sucesor(n),Sucesor(m)) => Igual(n,m)
Suma(Cero,n) => n
Suma(Sucesor(n),m) => Sucesor(Suma(m,n))
Ejemplo 4.7:- Especificación Semi - Formal TAD Bolsa
Definir el TAD bolsa como una colección de elementos no ordenados, con repetición.
Las operaciones a definir son: BolsaVacia, Agregar, EsVacia, Esta, Cuantos, Sucesor, Unión, Total, Intersección.
BolsaVacia: Crea una bolsa sin ningún elemento.
Agregar: Agrega un elemento a la lista
EsVacia: Visualiza si una bolsa está vacia.
Esta: Decide si un elemento se encuentra dentro de una bolsa.
Cuantos: Indica la acntidad de veces que esta repetido un elemento
Sucesor: Indica el cardinal más uno.
Total: Indica el cardinal de la bolsa.
Unión: Construye la bolsa unión de dos bolsas
Intersección: Construye la bolsa intersección de dos bolsas dadas.
TAD: Bolsa
Valores: bolsa de elementos ordenados que pueden repetirse
Operaciones: BolsaVacia, Agregar, EsVacia, Esta, Cuantos, Unión, Sucesor,Total,
Intersección
Sintaxis:
BolsaVacia: Bolsa.
Agregar(Bolsa, Elemento): Bolsa
EsVacia(Bolsa): Boolean
Esta(Bolsa, Elemento): Boolean
Cuantos(Bolsa, Elemento): Natural
Sucesor(Bolsa): Natural
Total(Bolsa): Natural
Unión(Bolsa, Bolsa): Bolsa
Intersección(Bolsa, Bolsa): Bolsa
Semántica: Sean B,C de tipo Bolsa; e, e1 de tipo elemento
Agregar(Agregar (B, e), e1) => Agregar(Agregar (B, e1), e)
EsVacia(BolsaVacia) => True
EsVacia(Agregar (B, e)) => False
Esta(BolsaVacia, e) => False
Esta(Agregar (B, e), e1) => Si igual(e,e1) entonces True
Si_no Esta(B, e1)
Cuantos(BolsaVacia, e): Cero
Cuantos (Agregar (B, e), e1) => Si igual(e,e1) entonces Sucesor(Cuantos (B, e1))
Si_no Cuantos (B, e1)
Sucesor(BolsaVacia) => Cero
Total(BolsaVacia) => Cero
Total(Agregar (B, e)) => Sucesor(Total(B))
Union(B, BolsaVacia) => BolsaVacia
Union(B, Agregar (C, e)) => Agregar (Union (C, B), e)
Interseccion(B, BolsaVacia) => BolsaVacia
Interseccion(B, Agregar (C, e)) => Si Esta(B,e) entonces Agregar (Interseccion (B, C),e)
Si_no Interseccion (B, C)
4.5.2 Especificación formal
De manera formal el TAD se puede especificar de la a partir del siguiente esquema:
Tabla 4.1 Esquema Especificación TAD
| Especificación TAD
|
| TAD: Nombre |
| Descripción objeto abstracto (Gráfica
o Textual) |
| Invariante del TAD |
| Operaciones:
operacionn(listado de tipo de argumentos): tipo del resultado |
| Prototipo operacion1 |
| /*Descripción operación*/ {precondiciones: ...} {postcondiciones: ...} |
Las precondiciones y postcondiciones pueden referirse, únicamente, a los elementos que componen el objeto abstracto y a los argumentos que recibe. No pueden incluir ningún otro elemento del contexto en ele cual se van a ejecutar. En la especificación de las operaciones, se debe considerar implícito en la precondición y postcondición, que el objeto abstarcto sobre el cual se va a operar cumple el invariante.
Es importante proporcionar un abreve descripción de cada operación, de manera que el cliente pueda darse una rápida idea de los servicios que un TAD ofrece, sin necesidad de entrar a hacer una interpretación de su especificación formal.
Al seleccionar los nombres de las operaciones se debe tener en cuenta que no pueden existir dos operaciones con el mismo nombre en un programa, incluso si pertenecen a TAD diferentes. Por esta razón es recomendable agregar un mismo sufijo a todas las operaciones de un TAD, de tal forma que las identifique.
Ejemplo 4.8:- Especificación TAD Matriz
| Especificación TAD
Matriz |
||||||||||||||||||||||||||||||||||||
| TAD: Matriz |
||||||||||||||||||||||||||||||||||||
| Conjunto de valores enteros agrupados en n filas y m columnas, donde cada elemento se puede referenciar a partir de la columna y fila que ocupa dentro del objeto.
|
||||||||||||||||||||||||||||||||||||
| Invariante: n>0,m>0 |
||||||||||||||||||||||||||||||||||||
| Operaciones: |
| Matriz CrearMat(int filas,int
cols) |
| /*Construye y retorna una matriz de filas-1 filas
y cols-1 columnas, inicializando todos sus elementos a cero*/ {precondiciones: filas>0,cols>0} {postcondiciones: CrearMat es una matriz de [0..fila-1,0..cols-1],x[i,k]=0} |
| void AsignarMat(Matriz mat,int
fila,int col,int valor) |
| /*Asigna a la celda [fila,col] el valor de valor*/ {precondiciones: 0<=fila<n,0<=col<m} {postcondiciones: mat[fila,col]=valor} |
| int InfoMat(Matriz mat,int fila,int
col) |
| /*Retorna el contenido de la celda [fila,col]*/ {precondiciones: 0<=fila<n,0<=col<m} {postcondiciones: InfoMat=mat[fila,col]} |
| void FilasMat(Matriz mat) |
| /*Asigna a la celda [fila,col] el valor de valor*/ {postcondiciones: FilasMat= n} |
| void ColsMat(Matriz mat) |
| /*Asigna a la celda [fila,col] el valor de valor*/ {postcondiciones: ColsMat= m} |
El invariante del TAD Matriz solo establece una restricción para el número de filas y columnas del objeto abstracto. El TAD matriz cuenta con 5 operaciones que permiten realizar las operaciones básicas para manejar un objeto del TAD, con lo cual es posible resolver cualquier problema que involucre una matriz.
4.6 Clasificación de las operaciones de un TAD
Las operaciones que implemeta un TAD se clasificacn en tres grupos principales, de acuerdo a la función que realiza sobre el objeto abstracto.
Adicionalmente a los tipos de operación básicos existen algunas subcategorías de estas, que le agregan portabilidad al TAD. Dentro de estas operaciones se encuentran las de Comparación, Copia, Destrucción, Salida a pantalla y Persistencia (son operaciones que le permiten a la instancia del TAD persistir a la ejecución del programa que lo utiliza).
El manejo de errores es uno de los aspectos relevantes durante el proceso de diseño de un TAD. Por lo tanto es conveniente considerar los siguientes aspectos:
4.8 Metodología para el diseño de TADS
Para el diseño de un TAD, generalmente se siguen los siguientes pasos:
El contenido de esta página esta basado en el material disponible en: