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
{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
EXCELENTEEEEE
ResponderEliminar