Tipos de Datos Abstractos
-
Upload
agomer08197 -
Category
Documents
-
view
9 -
download
0
description
Transcript of Tipos de Datos Abstractos
Tipos Abstractos de Datos Unidad 1: Fundamentos de estructura de datos
Tipos de datos
• Un tipo de dato es una colección de valores
• Han sido estudiados los tipos de datos que
implementan lenguajes como C++ o Java (Boolean,
Integer, Character...)
• Estos tipos son conocidos como “tipos simples”
• Estos tipos pueden ser utilizados en programas sin
necesidad de que los detalles sobre su
implementación sean conocidos
Tipos Abstractos de Datos (TAD)
• Con los lenguajes de programación estructurados
(años 60’s) surge el concepto de tipo de datos.
• Ese concepto es insuficiente para software a
gran escala: sólo el compilador restringe el uso
de los datos.
• En los 70’s aparece el concepto de TAD: un tipo
de dato no sólo es el conjunto de valores, sino
también sus operaciones con sus propiedades.
TAD
• Se pueden encontrar varias definiciones para el concepto
de Tipo Abstracto de Datos (TAD):
▫ Conjunto de Operaciones.
▫ Modelo matemático con una serie de operaciones definidas en
ese modelo.
▫ Tipo de datos definido de forma única mediante un tipo y un
conjunto de operaciones definidas sobre el tipo.
▫ El conjunto constituido por la estructura de datos y las
operaciones asociadas a la misma que permite modelar el
comportamiento de una entidad real.
TAD = valores + operaciones
Definición de TAD
• Un Tipo Abstracto de Datos es un conjunto de
valores y de operaciones definidos mediante una
especificación independiente de cualquier
representación.
TAD
• 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 pueden realizarse 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.
TAD
• 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 por completo 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
Características de un TAD
• Ocultamiento. El TAD tiene un comportamiento de “caja
negra” dado que quien lo usa sabe qué puede hacer pero
no cómo lo hace.
• Encapsulamiento (y, en consecuencia, Protección). El
usuario de TAD’s no tiene acceso y, por tanto, no puede
modificar sus características. No obstante, puede partir de
él para construir otros TAD’s
Características de un TAD
• Compilación separada: El resultado de la compilación
del TAD se pone a disposición de los usuarios en forma de
unidades que pueden utilizarse como si estuvieran
predefinidas en el lenguaje de programación.
Ejemplos de Tipos de TAD’s
•Pilas
▫Concepto
▫Modelo gráfico
•Colas
▫Concepto
▫Modelo gráfico
Pilas- concepto
Una pila es una agrupación de elementos
de determinada naturaleza o tipo (datos de
personas, números, procesos informáticos,
automóviles, etc.) entre los que existe
definida una relación de orden (estructura
de datos).
Pilas- concepto
En función del tiempo, algunos elementos
de dicha naturaleza pueden llegar a la pila
o salir de ella (operaciones/acciones). En
consecuencia el estado de la pila varia.
Pilas- concepto
Una pila presenta el comportamiento LIFO
(Last Input First Output) y el criterio de
ordenación se establece en sentido inverso
al orden de llegada.
Así pues, el ultimo elemento que llego al
conjunto será el primero en salir del mismo,
y así sucesivamente.
Pila – Modelo Gráfico
•Se pude representar gráficamente una
pila según aparece en la figura 1: una
estructura de datos vertical, en la que los
elementos se insertan y extraen por la
parte superior.
Pila – Modelo Gráfico
Figura 1. Modelo gráfico de pila
54172983
Cima
Fondo
desapilar apilar
Cola - Concepto
Una cola es una agrupación de elementos
de determinada naturaleza o tipo (datos de
personas, números, procesos informáticos,
automóviles, etc.) entre los que existe
definida una relación de orden (estructura
de datos).
Cola - Concepto
En función del tiempo, algunos elementos
pueden llegar a la cola o salir de ella
(operaciones / acciones). En
consecuencia el estado de la cola varia.
Cola - Concepto
Una cola presenta comportamiento FIFO
(First Input First Output) y se respeta como
criterio de ordenación el momento de la
llegada: el primer elemento de la cola, será
el que primero llego a ella y, en
consecuencia, el primero que saldrá, y así
sucesivamente.
Cola – Modelo Gráfico
Se puede representar gráficamente una
cola según aparece en la Figura 2: una
estructura de datos horizontal, en la que
los elementos se insertan por el extremo
derecho, y se extraen por la parte
izquierda.
Cola – Modelo Gráfico
Principio Fin
7 3 1 2 6 9 0 8 11 4 3 6
Desencolar Encolar
Figura 2. Modelo gráfico de cola
Implementación de un TAD
• Es importante comprender 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
Implementación de un TAD
• ¿Cómo debe implementarse un TAD?
• Deben considerarse detalles acerca de la
complejidad espacial de las estructuras 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
costo 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 estrechamente relacionados:
1. Análisis de datos y operaciones
2. Elección del TAD
3. Elección de la implementación
Declaración de un TAD
•Especificación algebraica, con dos
componentes
1. Signatura (Sintaxis) se compone de:
a) Definición de los posibles valores del tipo
b) Operaciones definidas
2. Axiomas (Semántica): relaciones y
restricciones que se establecen sobre el
modelo.
Ejemplo 1: TAD Booleano
TAD BOOLEANO;SIGNATURA
VALORESBOOLEAN={TRUE, FALSE}
OPERACIONESINIC:BOOLEAN BOOLEANNOT:BOOLEAN BOOLEANOR:BOOLEAN x BOOLEAN BOOLEANAND:BOOLEAN x BOOLEAN BOOLEAN
Ejemplo 1: TAD Booleano
TAD BOOLEANO;AXIOMAS
INIC(p)=pNOT(TRUE)=FALSENOT(NOT(p))=pp OR NOT(p)=TRUEp OR p=pp AND NOT(p)=FALSEp AND p=p
Ejemplo 2: TAD Número_NaturalTAD Número_Natural;
UTILIZA Booleano;SIGNATURA
VALORESNAT
OPERACIONESINIC:NAT NATCERO: NATESCERO:NAT BOOLEANSUCC:NAT NATSUMA:NAT x NAT NATIGUALES:NAT x NAT NAT
Ejemplo 2: TAD Número_NaturalTAD Número_Natural;
AXIOMAS
INIC(X)=XCERO()=0ESCERO(CERO)=TRUEESCERO(SUCC(X))=FALSESUMA(CERO,X) = XSUMA(SUCC(X),Y) = SUCC(SUMA(X,Y))SUCC(X) = SUMA(X,1)IGUAL(X,CERO) = IF ESCERO(X) THEN TRUE ELSE FALSEIGUAL(CERO,SUCC(X)) = FALSEIGUAL(SUCC(X),SUCC(Y)) = IGUAL(X,Y)