Matematicas

Tipos Abstractos de Datos
Tema 1. Estructuras de Datos y de la Información

Tipos de Datos
Un Tipo de Datos es una colección de valores Han sido estudiados los tipos de datos que implementan lenguajes como ADA o Java (Boolean, Integer, Character...) Estos tipos son conocidos como “tipos simples” Estos tipos pueden ser utilizados en nuestros programas sin necesidad de que los detalles sobre suimplementación sean conocidos

1

Tipos Abstractos de Datos (TAD) (I)
Podemos encontrar varias definiciones para el concepto de Tipo Abstracto de Datos (TAD)
TAD: Conjunto de Operaciones. Weiss, Data Structures andAlgorithms. p.46. TAD: Modelo matemático con una serie de operaciones definidas en ese modelo. Aho, Hopcroft, Ullman, Data Structures and Algorithms. p.11. TAD: Tipo de datosdefinido de forma única mediante un tipo y un conjunto de operaciones definidas sobre el tipo. Hernández, Lázaro, Dormido, Ros. Estructuras de Datos y Algoritmos. p.3.

Tipos Abstractos de Datos (TAD) (II)
Un Tipo Abstracto de Datos es una abstracción donde se encuentran encapsulados los estados potenciales en los que se puede encontrar una entidad de ese tipo y las operaciones que puedenrealizarse sobre ella. Abstraer: Separar por medio de una operación intelectual las cualidades de un objeto para considerarlas aisladamente o para considerar el mismo objeto en su pura esencia o noción.

2

Tipos Abstractos de Datos (TAD) (II)
Como se ha mencionado, se trata de una abstracción. No se incluyen detalles sobre la implementación de las operaciones. Los TAD son independientes porcompleto de la implementación.

Estructuras de Datos
En muchos textos, pueden encontrarse confundidos los términos TAD y Tipo de Datos, así como TAD y Estructura de Datos. Estructura de Datos: Conjunto de variables que se encuentran relacionadas. Con Estructura de Datos, por tanto, nos referimos a la implementación física de un TAD.

3

Atributos de un TAD
El encapsulamiento y la ocultación deinformación son atributos internos del diseño. Un TAD tiene estas propiedades:
–

Encapsulamiento: La información referente a la definición del tipo y todas las operaciones que pueden realizarse sobre el mismo se encuentran en el mismo lugar. Ocultación de Información: La información acerca de la implementación se encuentra oculta al usuario.

–

Implementación de un TAD
Es importantecomprender la diferencia entre un TAD y su implementación Las implementaciones no dejan de ser importantes, y su elección es crítica Al final, el usuario no debe preocuparse de cómo está implementado un TAD. Su única preocupación debe ser el uso del mismo

4

Implementación de un TAD (II)
¿Cómo debe implementarse un TAD? Deben considerarse detalles acerca de la complejidad espacial de lasestructuras y temporal de las operaciones Preguntas que debe formularse el programador:
– –

¿Cómo será la estructura de datos? ¿Cómo crecerá? Según lo anterior y otras consideraciones ¿cuál será el coste de una implementación u otra para cada operación?

TAD: Diseño e implementación
Debido a todo lo expuesto, el diseñador de un TAD debe enfrentarse a tres pasos bien distintos, pero íntimamenterelacionados:
1. 2. 3.

Análisis de datos y operaciones Elección del TAD Elección de la implementación

5

Declaración de un TAD: Especificación Algebraica
Una especificación algebraica de un TAD tiene dos componentes:
1.

Signatura (Sintaxis): Se compone de
a) b)

Definición de los posibles valores del tipo Operaciones definidas

2.

Axiomas (Semántica): Relaciones y restriccionesque se establecen sobre el modelo

Ejemplo 1: TAD Booleano
TAD Booleano; SIGNATURA VALORES BOOLEAN={TRUE,FALSE} OPERACIONES INIC:BOOLEAN BOOLEAN NOT:BOOLEAN BOOLEAN OR: BOOLEAN x BOOLEAN BOOLEAN AND: BOOLEAN x BOOLEAN BOOLEAN

6

Ejemplo 1: TAD Booleano (II)
AXIOMAS INIC(p) = p NOT(TRUE) = FALSE NOT(NOT(p)) = p p OR NOT(p) = TRUE p OR p = p p AND NOT(p) = FALSE p AND p = p

Ejemplo...