Tipos Abstractos de datos

Concepto

Cuando se escribe un programa para resolver un problema, con el enfoque tradicional se pasa directamente de la realidad a una implementación en el lenguaje de programación. Con los TAD se establece un nivel intermedio, donde se quiere moderar lo esencial de la realidad sin comprometerse con detalles de implementación. De hecho, es posible consideras diferentes implentaciones.

Un TAD es una estructura algebraica, o sea, un conjunto de objetos con ciertas operaciones definidas sobre ellos. Piense, por ejemplo, en la calculadora: los elementos que maneja son cantidades numéricas y las operaciones que tiene definidas sobre éstas son las operaciones aritméticas. Otro ejemplo posible es el TAD matriz; los elementos que maneja son las matrices y las operaciones son aquellas que nos permiten crearlas, sumarlas, invertirlas, etc.

Es posible observar que las operaciones de un

Tipo Abstracto son de diferentes clases: algunas de ellas nos deben permitir crear objetos nuevos, otras determinar su estado, unas construir otros objetos a partir de algunos ya existentes, etc.

La implementación tradicional frente a los TAD

Según la clásica ecuación de Wirth:

Programa = Datos + Algoritmo

El enfoque tradicional se ciñe bastante bien a esta concepción

Con los TAD se identifican ciertas operaciones o partes del algoritmo que manipulan los datos. En la ecución de Wirth la parte Algoritmo la podemos expresar como:

Algoritmo = Algoritmo de datos + Algoritmo de control

Se entirnde como Algoritmo de datos a la parte del algoritmo encargada de manipular las estructuras de datos del problema, y Algoritmo de control a la parte restante ( la que representa en sí el método de solución del problema, independiente hasta cierto punto de las estructuras de datos seleccionadas ).

Entonces podemos reescribir:

Programa = Datos + Algoritmo de Datos + Algoritmos de Control

Colocando Datos + Algoritmo de Datos como Implementación de TAD se establece la siguiente ecución:

Programa = Implementación del TAD + Algoritmo de Control

que describe el enfoque de desarrollo con Tipos Abstractos de Datos.

Clasificación

Hay operaciones que nos sirven para crear nuevos objetos abstractos, otras para obtener información acerca de ellos, y algunas para construir nuevos elementos a partir de ptros ya existentes. De esta forma las operaciones las podemos clasificar de esta manera:

Operaciones para crear objetos

Iniciales: Se utilizan para crear onjetos del TAD, en cuya creación no se requieren ningunos objetos abstractos del mismo tipo.

Constructores: Utilizadas para crear objetos del TAD cuya creación depende de objetos del mismo tipo.

Operaciones para transformar objetos de TAD

Simplificadoras: Son operaciones cuyo codominio es el TAD que se define, pero que dan como resultado objetos que pueden ser descritos utilizando unicamente operaciones iniciales y constructoras.

Operaciones para analizar los elementos del TAD

Analizadoras: Son operaciones cuyo codominio no es el TAD que se define, sino otro ya conocido. El proposito de este tipo de operaciones es obtener información concerniente a cualquiera de los objetos abstractos de tipo.

Las operaciones simplificadoras y analizadoras inducen una noción de equivalencia entre los elementos de TAD que se define; si dos objetos abstractos son indistinguibles mediante operaciones simplificadoras y analizadoras, el observador deberia concluir que se trata del mismo objeto.

Implementacion

Cuando ya se tiene bien diseñado un Tipo Abstracto, el siguiente paso es decidir una implementación para el mismo. Esto implica escoger unas estructuras de datos para representar cada uno de los objetos abstractos y escribir una rutina(Procedimiento o función) en un lenguaje de programación, que simule el funcionamiento de cada una de las operaciones de acuerdo con su especificación. La selección de las estructuras de datos determina, en muchos casos, la complegidad del algoritmo que implementa una operación y es, por esta razón, de gran importancia su escogencia. Existen estructuras de datos muy dependientes de un lenguaje de programación y debido a esto deben trata de evitarse cuando el TAD se quiere hacer portable.

Tomado del libro:

"Estructuras de datos (Un enfoque desde tipos abstractos)"
Jorge Villalobos, Alejandro Quintero, Mario Otero
Ediciones Uniandes