Busqueda...

Cargando...

TDA (Tipos de Datos Abstractos)


TDA: Tipos de Datos Abstractos

TDA (Tipo de Datos Abstractos): Un tipo de dato abstracto (TDA) o Tipo abstracto de datos (TAD) es un modelo matemático compuesto por una colección de operaciones definidas sobre un conjunto de datos para el modelo. Cuando se usa en un programa de computación, un TDA es representado por su interfaz, la cual sirve como cubierta a la correspondiente implementación. La idea es que los usuarios de un TDA tengan que preocuparse sólo por la interfaz, pero no por la implementación, ya que esta puede ir cambiando con el tiempo y, si no existiera encapsulación, afectar a los programas que usan el dato. Esto se basa en el concepto de Ocultación de información, una protección para el programa de decisiones de diseño que son objeto de cambio.
La solidez de un TDA reposa en la idea de que la implementación está escondida al usuario. Solo la interfaz es pública. Esto significa que el TDA puede ser implementado de diferentes formas, pero mientras se mantenga consistente con la interfaz, los programas que lo usan no se ven afectados.
Hay una diferencia, aunque a veces sutil, entre el Tipo de Dato Abstracto y la Estructura de Dato usada en su implementación. Por ejemplo, un TDA de una lista puede ser implementado mediante un Arreglo o una Lista Enlazada o hasta un Árbol binario de búsqueda. Una lista es un Tipo de Dato Abstracto con operaciones bien definidas (agregar elemento, agregar al final, agregar al principio, recuperar, eliminar, etc) mientras una lista enlazada es una estructura de datos basada en punteros o referencias (dependiendo del lenguaje) que puede ser usada para crear una representación de una Lista. La Lista Enlazada es comúnmente usada para representar una TDA Lista, y a veces, hasta confundida. Un ejemplo es la clase Linked List de Java, la cual ofrece una gran cantidad de métodos que no corresponden a una Lista Enlazada "pura", sino a un fuerte TDA.
De forma similar, un TDA Árbol binario de búsqueda puede ser representado de muchas maneras: Árbol binario, Árbol AVL, Árbol rojo-negro, Arreglo, etc. A pesar de la implementación un Árbol binario siempre tiene las mismas operaciones (insertar, eliminar, encontrar, etc.)
Separar la interfaz de la implementación no siempre significa que el usuario ignora totalmente la implementación de la rutina, pero lo suficiente para no depender de ningún aspecto de la implementación. Por ejemplo, un TDA puede ser creado usando un script o cualquiera que pueda ser decompilado (como C).
En la terminología de Lenguaje Orientado a Objeto, un TDA es una clase; una instancia de un TDA o clase, es un objeto. Además es utilizado constantemente por programadores de computadoras.
Los TDA por lo general establecen conceptos puros de la programación orientada a objetos como lo son el encapsulamiento y ocultamiento de información. Sin embargo, existen lenguajes puramente procedimentales que pueden emplear TDA para definir nuevos tipos de datos con un nivel de abstracción superior al nivel de abstracción de una acción nominada, con funcionalidad única y operaciones que trabajan sobre el tipo de datos definido. En la mayoría de los lenguajes los TDA representan librerías definidas por el usuario, fomentando la creación y ampliación del repertorio de librerías que ofrece el lenguaje de programación en cuestión. En el paradigma orientado a objetos los TDA son vistos como clases, pero al final en el paradigma que se implementen semánticamente tienen el mismo concepto: un conjunto de datos con operaciones definidas.
Un TDA se define en base a su especificación algebraica y operacional. Se debe especificar el invariante, que es el modelo que refleja la estructura del dato a definir, pero sin comprometerla con detalles de implementación, es decir no se pueden usar estructuras ni del pseudoformal ni de ningún otro lenguaje, recordando que la especificación de un TDA es una especificación matemática.


Ejemplo completo. Definición del TDA:
Se define el TDA Racional, que establece el tipo de dato racional, no suministrado por el pseudoformal. Formalmente la definición de un numero racional es:
a/b , donde a pertenece al conjunto de los números Z (enteros), y b pertenece al conjunto de los números Z sin el cero.
TDA Racional
Especificación Sintáctica

Operacion
Entrada
Salida
Crear_racional
Entero, entero
Real
Suma
Racional, racional
Racional
Resta
Racional, racional
Racional
Producto
Racional, racional
Racional
Division
Racional, racional
Racional
Numerador
Racional
Entero
Denominador
Racional
Entero
Valor_real
Racional
Real

Especificación Semántica
Invariante
Racional = (n, d)
donde
n Z ^ d Z – {0}
Sea R1, R2 {Racional} ^ R1 = (n1, d1), R2 = (n2, d2), siendo n1,n2 Z ^ d1,d2 Z – {0}

{Pre: }
operación crear_racional (n1 : entero, d1 : entero) : racional
{Post: crear_racional ← (n1,d1)}


{Pre: }
operación suma (R1 : racional, R2: racional) : racional
{Post: suma ← ( (n1*d2) + (d1* n2) , d1*d2) ) }

{Pre: }
operación resta (R1 : racional, R2: racional) : racional
{Post: resta ← ( (n1*d2) - (d1* n2) , d1*d2) ) }

{Pre: }
operación producto (R1 : racional, R2: racional) : racional
{Post: producto ← (n1*n2 , d1*d2 ) }

{Pre: }
operación división (R1 : racional, R2: racional) : racional
{Post: division ← (n1*d2 , d1*n2 ) }

{Pre: }
operación numerador (R1 : racional) : entero
{Post: numerador ← n1 }

{Pre: }
operación denominador (R1 : racional) : entero
{Post: denominador ← d1 }

{Pre: }
operación valor_real (R1 : racional) : real
{Post: valor_real ← ( n1/d1 ) }

Ejemplo completo. Implementación del TDA:
TDA Racional //Implementación
Tipo
Racional = registro
numerador, denominador : entero
finregistro

proc crear_racional (n1 : entero, d1 : entero, ref R1 : racional)
inicio
R1.numerador ← n1
R1.denominador ← d1
finproc

proc suma (R1 : racional, R2 : racional, ref R3 : racional)
inicio
R3.numerador ← (R1.numerador * R2.denominador) + (R1.denominador * R2.numerador)
R3.denominador ← (R1.denominador * R2.denominador)
finproc

proc resta (R1 : racional, R2 : racional, ref R3 : racional)
inicio
R3.numerador ← (R1.numerador * R2.denominador) - (R1.denominador * R2.numerador)
R3.denominador ← (R1.denominador * R2.denominador)
finproc

proc multiplicación (R1 : racional, R2 : racional, ref R3 : racional)
inicio
R3.numerador ← (R1.numerador * R2.numerador)
R3.denominador ← (R1.denominador * R2.denominador)
finproc

proc división (R1 : racional, R2 : racional, ref R3 : racional)
inicio
R3.numerador ← (R1.numerador * R2.denominador)
R3.denominador ← (R1.denominador * R2.numerador)
finproc


funcion numerador (R1 : racional) : entero
inicio
retornar (R1.numerador)
finfuncion

función denominador (R1 : racional) : entero
inicio
retornar (R1.denominador)
finfuncion

funcion valor_real (R1 : racional) : real
inicio
retornar (R1.numerador / R1.denominador)
finfuncion



Ejemplo completo. Uso del TDA:

Algoritmo Calculo
//Se escribe “USO” seguido de la palabra TDA seguida de un underscore (piso) seguida del nombre
//del TDA
USO TDA_Racional
Const
Tipo
Var
R1, R2, R3 : Racional
n1,d1,n2,n2 : entero
Inicio
leer (n1)
leer (d1)
leer (n2)
leer (d2)
crear_racional (n1,d1,R1)
crear_racional (n2,d2,R2)
suma (R1,R2,R3)
escribir (“La fraccion suma es ”, numerador(R3), “/”, denominador(R3))
Fin

No hay comentarios:

Publicar un comentario en la entrada