UNIVERSIDAD NACIONAL AUTONOMA DE COSTA RICA

SEDE REGION BRUNCA

PEREZ ZELEDÓN

INGENIERIA EN SISTEMAS

Organización de Datos

TAREA DE INVESTIGACION

TITULO: TIPOS ABSTRACTOS DE DATOS (TAD)

TIPOS ABSTRACTOS DE DATOS (TAD)

CONCEPTOS BÁSICOS

Abstracción una descripción simplificada de la realidad; el principio de ignorar aquellos aspectos de un objeto que son irrelevantes para un propósito específico con el fin de concentrarse en aquellos que sí son relevantes.

La abstracción depende del dominio del problema.

Objeto una abstracción de algo en el dominio de un problema. Incluye un modelo de datos - atributos e información; y, un modelo de comportamiento - interacción y servicios.

TAD Es un modelo de datos, asociado con un conjunto de operaciones que pueden ser realizadas por o en el modelo de datos. Una definición formal independiente de la representación. (Base matemática de la tecnología de objetos)

Un tipo describe una colección de objetos, caracterizada por un contenido, operaciones, axiomas y precondiciones.

Un objeto perteneciente al conjunto de objetos descrito por un TAD es una instancia de ese TAD.

Encapsulamiento encerrar el modelo (datos + funcionalidad) en una "cápsula" (como un todo) al que se puede acceder sólo a través de comandos (funcionalidad-servicios) o de cuestionamientos (queries) (información-estado), sin necesidad de conocer los detalles de la implementación.

Ocultamiento de información impedimento de acceso directo a la definición del modelo y su implementación por razones de protección; así como de acceso indiscriminado a las características del TAD. Se debe poder especificar si una característica está disponible para todos los clientes, para ninguno o para ciertos clientes.

Axiomática algebraica técnica estándar para especificación de los TAD's, que facilita las pruebas de correctitud de la implementación y la ejecución conceptual del diseño de grandes sistemas. Presenta tres condiciones básicas para describir con propiedad los TAD's:

• permite una descripción precisa y sin ambigüedad

• es completa

• permite controlar la sobre especificación (no involucrar demasiados detalles, o ligar la especificación a algún tipo de implementación)

Aserciones Las características de un TAD tienen propiedades formalmente especificadas, que deben ser reflejadas en las clases correspondientes. Las aserciones - las precondiciones y postcondiciones de los procesos, y las invariantes de clase - permiten hacer esto; ellas describen el efecto de estas características sobre los objetos, independientemente de cómo las características hayan sido implementadas.

Aplicaciones de las aserciones:

• ayudar a producir sw confiable

• proveer documentación sistemática

• herramienta central para prueba y depuración

PILAS

Pila - objeto que sirve para almacenar y recuperar otros objetos con una disciplina LIFO (Last in first out) o sea (Ultimos en entrar primeros en salir)

TAD Pila[item]

declare

NUEVA:{} → Pila

PUSH: Pila X item → Pila

POP:Pila → Pila

TOP:Pila → item

PILAVACIA:Pila → boolean

axiomas

para todo s → Pila, i → item se tiene

a1. POP(PUSH(s,i)) = s

a2. TOP(PUSH(s,i)) = i

a3. PILAVACIA(NUEVA) = true

a4. PILAVACIA(PUSH(s,i)) = false

precondiciones

POP(s:Pila) requiere no PILAVACIA (s)

TOP(s:Pila) requiere no PILAVACIA (s)

Esto especifica un patrón de tipo.

"Item" denota un tipo arbitrario no especificado, seguramente con su propia especificación de TAD - un parámetro genérico formal.

Para obtener un tipo Pila se requiere proveer un parámetro genérico real.

La declaración de los servicios utiliza funciones definidas en el sentido matemático, (PUSH:Pila * item → Pila) ellas no deben producir ni efectos colaterales ni cambios de ninguna clase (libres de cambios - aplicativas). Sin embargo cuando se pasa a su implementación, habrá que introducir la noción de cambio.

Hay varias categorías de funciones: creadoras, de consulta y comandos.

Se las reconoce, en la declaración de un TAD T dado, según dónde T aparece:

Si T aparece solo a la derecha de " → ", como en el caso de NUEVA, es una función creadora. Este tipo de funciones producen instancias de T a partir de instancias de otros tipos (si hay argumentos) o, como en este caso, a partir de nada.

Si T aparece solo a la izquierda de " → ", como en el caso de TOP, o de PILAVACIA, la función es de consulta. Este tipo de funciones modela operaciones que retornan propiedades de instancias de T.

Si T aparece en los dos lados de "→ ", se trata de funciones de comando. Estas modelan operaciones que conllevan a nuevas instancias de T desde instancias existentes de T.

Es necesario incluir la definición de las funciones, pues, como en matemática, su declaración no basta; cualquier otro tipo (otros dispensadores) podría cumplir con tal declaración (más evidente si se utilizan nombres más generales). Pero eso implica adoptar una representación del tipo; para evitarlo, tal definición se hace a través de axiomas.

Los dos primeros axiomas expresan la propiedad básica LIFO de una pila. Los axiomas tercero y cuarto indican cuándo una pila está vacía y cuándo no.

Las especificaciones de TAD's son implícitas porque:

• definen implícitamente un conjunto de objetos

• sus funciones son definidas implícitamente, a través de axiomas que describen sus propiedades.

No son especificaciones exahustivas, siempre pueden aparecer nuevas operaciones y nuevas propiedades. El ser implícitas implica apertura. Pero cualquier extensión que se haga debe preservar la especificación primaria.

En OOP el mecanismo para llevar a cabo dicha extensión es la herencia.

Por otro lado, algunas funciones no están definidas para todos los elementos del conjunto - funciones parciales. La especificación del dominio para estas funciones parciales se hace a través de las precondiciones.

Estas especificaciones proveen un modelo general de computación con estructuras de datos. Gracias a ellas se puede describir secuencias de operaciones complejas a través de expresiones matemáticas y mirar el proceso de computación como un caso de simplificación algebráica:

Ejemplo:

TOP(POP(PUSH(POP(PUSH(PUSH(NUEVA( ),x1),x2)),

¿QUE ES UN TAD ?

TAD son las siglas de tipo abstracto de dato. La filosofía de la programación

usando esta técnica consiste en abstraer , ocultar , los aspectos de bajo

nivel de un tipo, de tal manera que se puedan usar por otros programadores

sin tener que recurrir a sentencias de bajo nivel para su uso.

Un tipo puede ser los clásicos de enteros , caracteres ,cadenas , puntos

flotantes típicos de lenguajes. Esos son los tipos definidos por el lenguaje. Aparte de esos algunos lenguajes permiten la combinación de estos formando

otros nuevos llamados estructuras.

El C realiza eso con la palabra clave struct .

En determinados lenguajes a esa estructura se le puede dar un nombre y

determinadas características como privacidad y generacidad.

El C nos permite renombrar las estructuras dándoles un nombre

característico

typedef struct [nombre_struct] { tipo nombre_variable; ... } nombre_tipo;

Pero el C no nos permite , como en el ADA , impedir que se puedan acceder a

los subcampos de la estructura mediante la declaración de tipo privado. Esta

librería no contiene esa característica y aunque trata los tipos que contiene

con funciones de forma que se tratan de forma privada por las subrutinas

contenidas en ella , el programador que la use no tiene ningún impedimento

para acceder a subcampos de los tipos . Este problema será crucial , si se

realiza eso habrá graves riesgos de que el TAD no funciona como se espera.

Por consiguiente no es aconsejable realizar ese tipo de operaciones y acceder

a todas las operaciones del TAD mediante las funciones creadas a su efecto.

Los TAD's podrían ser:

- colas

- pilas

- listas

- listas ordenadas

- Árboles multicaminos

- Árboles binarios

- Áboles binarios ordenados

- Árboles equilibrados

- conjuntos

- grafos

- complejos

- matrices dinámicas

- operaciones aritméticas para matrices dinámicas

- ficheros secuenciales

- ficheros directos

¿Por que usar un TAD'S ?

La razón fundamental es por que esas funciones estan creadas ya , realizan lo que deben independientemente de lo que queramos guardar y no nos tenemos que preocupar mas de su tratamiento.

Con la filosofía de abstracción resulta sencillo la construcción de programas complejos y grandes. Primero se debe preocuparse por la creación de unos 1buenos pilares como son las estructuras de almacenamiento como las tratadas en esta librería , una vez echo esto ya puede almacenarse información sin tener que crear nuevas funciones para cada tipo ,con el consiguiente ahorro de código y memoria .

. Crear una librería para mantener una función de ayuda mediante hipertexto y otras cosas que se pueden ir necesitando. Una característica peculiar es que los TADS pueden estar encapsulados unos en otros, por ejemplo mi librería de menus tiene un kernel de TAD'S.

Además la gran ventaja es que programando abstractamente puedes reutilizar código sin tener que cambiar ni una sola línea en muchos programas. En cambio tiene diversos inconvenientes. Uno de los dichos es que se debe tener una disciplina de no intentar acceder al bajo nivel de la librería , ya que se puede desbaratar el TAD. Segundo es que es bastante mas ineficiente en velocidad ya que recurren a muchas llamadas a funciones , y las llamadas a funciones son más lentas que el código en línea. Pero este problema da lugar a una reflexión : Hasta que punto se debe complicar el código para obtener un programa rápido , si en el programa la velocidad de ejecución es vital , puede que no sea interesante el uso de la generalidad en los TADS y por tanto crearse sus propias funciones , pero en programas muy complejos donde la velocidad no es fundamental se debe sacrificar parte de ella para obtener un código mas legible y sencillo de modificar . Quien no se ha perdido en un programa C de un alumno de primero con su increíble de lió de punteros ?

Introducción a los tipos abstractos de datos

Un ejemplo

Pensemos en el concepto abstracto de cantidad. Es posible definir diferentes sistemas para representar este concepto, así como ciertos mecanismos para operar con el.

En la prehistoria se usaban palitos. Los romanos usaban combinaciones de siete letras (I, V, X, L, C, D y M). Actualmente las personas utilizamos el sistema decimal basado en secuencias de dígitos (0,1,..,9) y en pesos según su posición. Los computadores (hoy en día) por su parte utilizan el sistema binario (0,1). En todos estos sistemas se puede definir la forma de sumar, restar, etc.

Las operaciones indican también conceptos que son independientes de la representación.

Por ejemplo. En una calculadora utilizada en un problema de contabilidad, es indiferente como representa esta los números, sólo nos interesa que realice las cuentas correctamente.

Es decir, puede existir una separación entre la solución a un problema y la forma de representar los datos utilizados. Este método aplicado a la escritura de programas, hace que sean más legibles y flexibles a los cambios.

ESQUEMA DE UN ABSTRACT DATA TYPE

• Programas = TADs + Algoritmos de control

A partir de la ecuación:

Programa = Datos + Algoritmo

Podemos expresar Algoritmo de la forma:

Algoritmo = Algoritmos de datos + Algoritmo de control

Donde Algoritmo de datos es la parte encargada de manipular las estructuras de datos del problema (sus operaciones), y Algoritmo de control la que representa el método de solución del problema, independiente (hasta cierto punto) de las estructuras de datos elegidas.

Tenemos ahora:

Programa = Datos + Algoritmos de datos + Algoritmo de control

Agrupando los datos y sus operaciones definimos un tipo abstracto de dato (TAD).

TAD: Dato y sus operaciones, definidas estas mediante una especificación independiente de representación.

Es decir:

Programa = Tipos abstractos de datos + Algoritmo de control

Comentario Final acerca de Tipos abstractos de datos

Una de las principales contribuciones de los lenguajes de alto nivel es que el programador no tiene que preocuparse de cómo se representan físicamente los datos en el computador. De esta idea surge el concepto de tipo de datos. Una extensión del mismo es el tipo abstracto de datos. Su implementación es de nuevo desconocida para el programador, esta vez no porque desconozca la arquitectura del computador subyacente, sino porque es encapsulado en un módulo que no permite el acceso directo a los detalles de su implementación. En su lugar, se proporciona al programador operaciones sobre el tipo que son invocaciones a entradas del módulo que lo encapsula.