Abstraccion de datos

Vista previa del material en texto

Algoritmos y Estructuras de 
Datos
Departamento de Informática
LAS - TUP
Unidad 3 - Clase 1
Unidad N° 3: Introducción a la abstracción de datos
Objetivos:
● Los conceptos de Tipos Abstractos de Datos (TAD).
● Especificar un TAD.
● Implementar un TAD.
Unidad N° 3: Introducción a la abstracción de datos
● Analogía
● Niveles de abstracción de datos
● Tipo de dato abstracto
○ Definiciones.
○ Especificaciones.
○ Operaciones.
○ Implementación.
○ Ventajas.
○ Aplicaciones.
Introducción a la abstracción de datos
Conceptos anteriores:
Un Tipo de Datos es una colección de valores.
Estructuras de Datos: Conjunto de variables que se encuentran relacionadas.
Abstracción: 
Analogía
Supongamos que tenemos una docena de pelotas de tenis, las cuales no pueden 
descomponerse en partes más elementales (elementos atómicos).
Demos a cada pelota una identificación individual (de 1 a 12).
Imaginemos a las 12 pelotas flotando en el espacio alineadas según su número 
de identificación. Dichos números establecen una relación entre ellos. Tenemos 
una estructura.
Analogía
Con las pelotas queremos: 
● Extraer una de ellas según su identificación. 
● Agregar una (en el espacio dejado por otra, manteniendo la misma 
identificación). 
Es decir, sobre la colección de pelotas queremos realizar un conjunto de 
operaciones.
Analogía
Tenemos entonces una estructura abstracta de pelotas de tenis que consiste 
de: 
● una colección de objetos atómicos,
● organizados según una cierta estructura y
● con determinadas operaciones especificadas
Decidir
Tenemos que decidir como cumplir con nuestra imaginación, usando 
objetos reales e implementaciones reales. 
No importa la estructura física a usar. Queremos que actúe como nuestra 
estructura abstracta. 
Algunos medios de almacenamiento físicos posibles: una caja de cartón 
de 3 filas, una canasta, etc.
Analogía
Si usamos una caja de cartón: la pelota k está en fila:=(k-1) div 4, columna:=(k-1) 
mod 4 
Esta forma de almacenamiento es conveniente para ubicar una pelota como 
también para almacenarlos. Sería igual de conveniente si usamos una canasta?. 
Analogía
Si usamos una caja de cartón: la pelota k está en fila:=(k-1) div 4, columna:=(k-1) 
mod 4 
Esta forma de almacenamiento es conveniente para ubicar una pelota como 
también para almacenarlos. Sería igual de conveniente si usamos una canasta?. 
La elección de la forma de almacenamiento afecta a la eficiencia con la que 
realizamos las operaciones.
Interesa
Estamos interesados en diferentes formas de organizar y operar sobre 
colecciones de objetos. Es decir: 
● Objetos de interés → objetos dato 
● Formas de almacenamiento → diferentes tipos de memoria 
● Operaciones sobre los datos → algoritmos
Resultado
Si combinamos 
los datos atómicos de interés, 
una organización de los mismos y 
las operaciones sobre los mismos, tendremos un tipo de datos especial, llamado 
Tipo Abstracto de Datos (TAD).
Definiciones: Tipo Abstracto de Datos
TAD: Conjunto de Operaciones. Weiss, Data Structures and Algorithms. 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 datos definido 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.
Tipo Abstracto de Datos
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.
Con Estructura de Datos, por tanto, nos referimos a la implementación física de 
un TAD.
Tipo Abstracto de Datos
El encapsulamiento y la ocultación de informació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.
Especificaciones
Un TAD puede especificarse de dos maneras:
No Formal: Usando un lenguaje natural.
Formal: Usando un lenguaje de programación.
En JAVA utilizaremos las interfaces para definir los TAD.
Especificación
La implementación
La colección de pelotas (junto con las operaciones) será implementada a nivel de 
programación, mediante un TAD. 
El programador implementará las operaciones y elegirá la estructura de datos 
más conveniente. 
El usuario del TAD usará las operaciones para operar con las pelotas pero NO 
podrá acceder directamente a los datos NI sabrá cómo se implementó el TAD. 
Por tanto, la comunicación entre ambos será posible mediante una interfaz.
JAVA
Las estructuras de datos se implementan como clases.
Las estructuras de datos (clases) debe implementar las operaciones definidas en 
el TAD (interfaz).
La clase describe cómo se realizan las operaciones de TAD.
Un TAD define “qué” operaciones pero no “como” hacerlas.
Un TAD puede tener diferentes implementaciones.
JAVA
Esta construcción (la clase) permite, por tanto, encapsular datos y operaciones 
sobre los mismos, por lo que se revela idónea para construir TADs.
Cada clase Java se corresponde con un fichero, que representa la declaración e 
implementación de un TAD.
En el archivo que contenga el TAD deben encontrarse representados los atributos 
de la clase (privados), el nombre y forma de las operaciones que se exportan (su 
interfaz), y su implementación.
JAVA
Implementación
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
¿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?
Diseño e implementación
Debido a todo lo expuesto, el diseñador de un TAD debe enfrentarse a tres pasos 
bien distintos, pero íntimamente relacionados:
1. Análisis de datos y operaciones
2. Definir el TAD
3. Definir la implementación