• Author / Uploaded
• Çяistiaи ҼҒє

Citation preview

TIPOS ABSTRACTOS DE DATOS - TADS 4.1 Introducción El objetivo del estudio de las estructuras de datos es la representación de la información (datos) que permitan obtener un algoritmo lo más sencillo posible, para lo cual se tiene en cuenta: 



Identificar y desarrollar de modo formal las entidades y las operaciones que definen la información que se trata, así como determinar qué tipos de problemas pueden resolverse utilizando estas operaciones y entidades. Determinar la representación más idónea de estas estructuras abstractas e implementarlas.

Ejemplo 4.1:- Problemas a enfrentar - Buscar un libro en la biblioteca - Uso de números romanos o arábigos Los problemas reales tienden a ser complejos porque involucran demasiados detalles, y resulta imposible considerar todas las posibles interacciones a la vez, en este aspecto la abstracción constituye una herramienta en la especificación de un TAD, ya que por medio de esta capacidad solo se tienen en cuenta los aspectos más relevantes del problema objeto de análisis y a partir de la abstracción se determina "el que" del problema a tratar, sin preocuparse de entrada por los aspectos de la implementación ("el como"). El razonar en términos de abstracciones conlleva una serie de ventajas:    

La resolución de los problemas se simplifica Las soluciones son más claras y resulta más sencillo razonar sobre su corrección Pueden obtenerse soluciones (o fragmentos de ellas) de utilidad más general, que puedan adaptarse para resolver otros problemas Permite la división de tareas

La evolución de la Programación muestra una tendencia a incluir mecanismos de abstracción cada vez de más alto nivel:  

Ensamblador Lenguajes de alto nivel o Estructuras de control Procedimientos y funciones o Tipos de datos o Módulos o Tipos abstractos de datos o Clases en programación orientada a objetos



Generadores de aplicaciones (hojas de cálculo, gestores de bases de datos, diseño visual de interfaces, ...)

Figura 4.1 Relación Especificación - Abstracción - Implementación La figura 4.1 representa la abstracción como una barrera entre la especificación y la implementación. Los clientes de una entidad solo conocen la parte de la especificación que les permite utilizar la entidad sin preocuparse por la implementación. Para entender el concepto de tipo abstracto de datos analicemos la diferencia entre los tipos predefinidos y los tipos definidos por el programador. 



Un tipo predefinido es un tipo abstracto de datos porque: o Está fijado el conjunto de valores permitidos y el manejo de excepciones es transparente para el cliente. o No es posible acceder directamente a la representación interna de los datos (generalmente). o Está fijado el conjunto de operaciones permitidas sobre dichos valores e implícitamente existen los mecanismos encargados de garantizar que se usan correctamente. o Como programadores sólo necesitamos conocer el comportamiento de las operaciones (P.Ej., las leyes algebraicas por las que se rigen los enteros), sin que tengamos acceso a su implementación concreta. Un lenguaje no soporta la implementación de tipos abstractos de datos si: o La estructura de datos donde se representa la información se define por una parte y las operaciones que manipulan esos datos por otra. o No es posible definir una abstracción que reúna la estructura de datos y las operaciones de forma que la representación de los datos y la implementación de las operaciones sea oculta para los clientes y por lo tanto deban ceñirse a lo indicado explícitamente en la especificación de la estructura de datos.

Ejemplo 4.2:- Ejemplo TAD deficiente Si para definir un tipo de datos para representar fechas, utilizamos una representación como esta: typedef int TDia; typedef enum { enero, febrero, ... , diciembre } TMes;

typedef int TAnyo; typedef struct { TDia dia; TMes mes; TAnyo anyo; } TFecha; Debido a que se tiene libre acceso a la representación del tipo de datos, es posible realizar operaciones absurdas con respecto a la semántica, como: fecha.mes = febrero; fecha.dia = 30; Al decir que TFecha es un TAD debe poseer las operaciones que restrinjan la asignación de valores erróneos como el día 30 al mes de febrero. 4.2 Definición y Concepto Un tipo abstracto de dato o TAD es un modelo matemático compuesto por una colección de operaciones definidas sobre un conjunto de objetos abstractos que modelan elementos del mundo, donde dichas operaciones simulan el comportamiento que el elemento modelado tiene en el mundo del problema. El concepto de tipo de dato abstracto (TAD, Abstract Data Types ), fue propuesto por primera vez hacia 1974 por John Guttag y otros, pero no fue hasta 1975 que por primera vez Liskov lo propuso para el lenguaje CLU. Un TAD está caracterizado por un conjunto de operaciones (funciones) al cual se le denomina usualmente como su interfaz pública y representa el comportamiento del TAD; mientras que la implementación (como la parte privada del TAD) está oculta al programa cliente que lo usa. Todos los lenguajes de alto nivel tienen predefinidos TAD; que son los tipos denominados simples y las estructuras predefinidas, y estos tienen sus interfaces públicas que incluyen las operaciones como la +, -, *, etc. Cuando se habla de un TAD no se hace ninguna alusión al tipo de los elementos sino tan sólo a la forma en que están dispuestos estos elementos. Sólo interesa la estructura que soporta la información y sus operaciones. Para determinar el comportamiento estructural basta con observar la conducta que seguirán los datos. Un TAD tendrá una parte que será invisible al usuario la cual hay que proteger y que se puede decir que es irrelevante para el uso del usuario y está constituida tanto por la maquinaria algorítmica que implemente la semántica de las operaciones como por los datos que sirvan de enlace entre los elementos del TAD, es decir, información interna necesaria para la implementación que se esté haciendo para ese comportamiento del TAD. Resumiendo podemos decir, que tanto la implementación de las operaciones como los elementos internos del TAD serán privados al acceso externo y ocultos a cualquier otro nivel.

Un TAD representa una abstracción:  

Se destacan los detalles de la especificación (el qué). Se ocultan los detalles de la implementación (el cómo).

Se puede decir que un TAD es un tipo de dato, que se agrega al lenguaje de programación, para representar un elemento involucrado en el problema que se desea resolver. De esta forma se le permite al lenguaje que se le acerque al mundo del problema, manejando los datos que allí se encuentran. En el proceso de desarrollo de software, dentro del mundo del problema casi siempre es posible identificar entidades que permiten expresar la solución en términos más sencillos, más fáciles de mantener y de probar. Un tipo abstracto de datos se compone de:  

Una especificación Una implementación

4.2.1 Encapsulamiento: El encapsulamiento consiste en aislar las cuestiones de implementación de las de especificación, es decir, en esconder los detalles de implementación de un determinado objeto, sea este un tipo de dato o un algoritmo, y mostrar tan sólo su especificación. De este modo, nos centraremos en el qué y ocultaremos el cómo. Por ejemplo, en el caso del tipo de datos REAL, el lenguaje proporciona al usuario la capacidad de definir variables de este tipo, de acceder y modificar su contenido, de realizar operaciones aritméticas con las mismas. Sin embargo, el usuario no tiene que preocuparse de cómo se almacenan los distintos números reales, ni del tratamiento que es necesario realizar con sus representaciones binarias para sumarlos o multiplicarlos. La técnica que se utiliza para lograr la ocultación de la información es el encapsulamiento. El uso de la abstracción y el ancapsulamiento proporcionan varias ventajas a la hora de desarrollar programas complejos o definir nuevos tipos de datos:     

Simplificación en el código resultante. El código obtenido es más sencillo de entender al no tratar al mismo tiempo todos los detalles del problema. Reduce los errores al permitirnos trabajar con un código más sencillo. Facilita el mantenimiento del código al separar claramente las distintas operaciones y permitirnos depurar cada una por separado. Permite cambiar la implementación de ciertas partes del código sin afectar al resto. Permite reutilizar los tipos. Una vez definido un nuevo tipo de datos, puede ser utilizado para la resolución de más de un problema. Para ello, la persona que implementó los procedimientos de manipulación no tiene porque ser la misma que los use. Basta con que el usuario final entienda el significado del nuevo tipo de datos y conozca la especificación de los procedimientos para su manejo. Esta es una clara demostración de que la implementación puede quedar oculta para el usuario final.

4.3 Representación de un Objeto Abstracto Al comenzar con el proceso de diseño de un TAD es necesario tener una representación abstracta del objeto sobre el cual se quiere trabajar, sin necesidad de establecer un compromiso con ninguna estructura de datos concreta, ni con ningún tipo de lenguaje de programación seleccionado. Esto va a permitir expresar las condiciones, relaciones, restricciones y operaciones de los elementos modelados, sin necesidad de restringirse a una representación interna concreta. El primer paso en el proceso de modelado de un TAD consiste en definir el estado interno del objeto abstracto por medio de algún formalismo matemático, gráfico o descriptivo Ejemplo 4.3:- Descripción TAD Matriz TAD Matriz 0

k

m-1

0

i

xi,k

n-1 Con esta notación es posible hablar de cada uno de los componentes de una matriz, de sus dimensiones, de la noción de fila y columna, de la relación entre elementos, sin necesidad de establecer unas estructuras de datos concretas para manejarlos. Ejemplo 4.4:- Descripción TAD Diccionario

En esta notación, se hacen explícitas agunas características del elemento diccionario, que está formado por un conjunto de palabras que a su vez posee un conjunto de significados. 4.4 Invariante de un TAD El invariante de un TAD establece la validez para cada uno de sus objetos abstractos en términos de condiciones sobre su estructura interna y sus componentes, indicando en que casos un objeto abstracto modela un elemento posible del mundo del problema. Estructuralmente, el invarianrte esta compuesto por condiciones que restringen el dominio de los componentes internos y por relaciones entre ellos. El invariante está relacionado con la corrección de la implementación del TAD en los siguientes aspectos:

 

Las operaciones sólo están obligadas a funcionar sobre representantes válidos del TAD. Las operaciones que generen valores del tipo representante deben comprometerse a que éstos sean siempre representantes válidos.

Lo importante no es escribir el invariante de la representación formalmente, sino determinar (aún con una descripción informal) de entre todos los valores que puede tomar el tipo representante cuáles representan valores válidos del TAD que estamos diseñando. Ejemplo 4.5:- Invariante TAD Diccionario TAD Diccionario: El invariante debe incluir condiciones como: - Las palabras están ordenadas ascendentemente y no hay repetidas -> elem(i).palabra Falso Igual(Sucesor(n),Sucesor(m)) => Igual(n,m) Suma(Cero,n) => n Suma(Sucesor(n),m) => Sucesor(Suma(m,n)) Ejemplo 4.7:- Especificación Semi - Formal TAD Bolsa Definir el TAD bolsa como una colección de elementos no ordenados, con repetición. Las operaciones a definir son: BolsaVacia, Agregar, EsVacia, Esta, Cuantos, Sucesor, Unión, Total, Intersección. BolsaVacia: Crea una bolsa sin ningún elemento. Agregar: Agrega un elemento a la lista EsVacia: Visualiza si una bolsa está vacia. Esta: Decide si un elemento se encuentra dentro de una bolsa. Cuantos: Indica la acntidad de veces que esta repetido un elemento Sucesor: Indica el cardinal más uno. Total: Indica el cardinal de la bolsa. Unión: Construye la bolsa unión de dos bolsas Intersección: Construye la bolsa intersección de dos bolsas dadas. TAD: Bolsa

Valores: bolsa de elementos ordenados que pueden repetirse Operaciones: BolsaVacia, Agregar, EsVacia, Esta, Cuantos, Unión, Sucesor,Total, Intersección Sintaxis: BolsaVacia: Bolsa. Agregar(Bolsa, Elemento): Bolsa EsVacia(Bolsa): Boolean Esta(Bolsa, Elemento): Boolean Cuantos(Bolsa, Elemento): Natural Sucesor(Bolsa): Natural Total(Bolsa): Natural Unión(Bolsa, Bolsa): Bolsa Intersección(Bolsa, Bolsa): Bolsa Semántica: Sean B,C de tipo Bolsa; e, e1 de tipo elemento Agregar(Agregar (B, e), e1) => Agregar(Agregar (B, e1), e) EsVacia(BolsaVacia) => True EsVacia(Agregar (B, e)) => False Esta(BolsaVacia, e) => False Esta(Agregar (B, e), e1) => Si igual(e,e1) entonces True Si_no Esta(B, e1) Cuantos(BolsaVacia, e): Cero Cuantos (Agregar (B, e), e1) => Si igual(e,e1) entonces Sucesor(Cuantos (B, e1)) Si_no Cuantos (B, e1) Sucesor(BolsaVacia) => Cero Total(BolsaVacia) => Cero Total(Agregar (B, e)) => Sucesor(Total(B)) Union(B, BolsaVacia) => BolsaVacia Union(B, Agregar (C, e)) => Agregar (Union (C, B), e) Interseccion(B, BolsaVacia) => BolsaVacia Interseccion(B, Agregar (C, e)) => Si Esta(B,e) entonces Agregar (Interseccion (B, C),e) Si_no Interseccion (B, C) 4.5.2 Especificación formal De manera formal el TAD se puede especificar de la a partir del siguiente esquema: Tabla 4.1 Esquema Especificación TAD Especificación TAD TAD: Nombre Descripción objeto abstracto (Gráfica o Textual) Invariante del TAD

Operaciones: operacion1(listado de tipo de argumentos): tipo del resultado operacionn(listado de tipo de argumentos): tipo del resultado Prototipo operacion1 /*Descripción {precondiciones: {postcondiciones: ...}

operación*/ ...}

Las precondiciones y postcondiciones pueden referirse, únicamente, a los elementos que componen el objeto abstracto y a los argumentos que recibe. No pueden incluir ningún otro elemento del contexto en ele cual se van a ejecutar. En la especificación de las operaciones, se debe considerar implícito en la precondición y postcondición, que el objeto abstarcto sobre el cual se va a operar cumple el invariante. Es importante proporcionar un abreve descripción de cada operación, de manera que el cliente pueda darse una rápida idea de los servicios que un TAD ofrece, sin necesidad de entrar a hacer una interpretación de su especificación formal. Al seleccionar los nombres de las operaciones se debe tener en cuenta que no pueden existir dos operaciones con el mismo nombre en un programa, incluso si pertenecen a TAD diferentes. Por esta razón es recomendable agregar un mismo sufijo a todas las operaciones de un TAD, de tal forma que las identifique. Ejemplo 4.8:- Especificación TAD Matriz Especificación TAD Matriz TAD: Matriz Conjunto de valores enteros agrupados en n filas y m columnas, donde cada elemento se puede referenciar a partir de la columna y fila que ocupa dentro del objeto. 0

k

0

i n-1

xi,k

m-1

Invariante: n>0,m>0 Operaciones: CrearMat(entero,entero): AsignarMat(Matriz,entero,entero,entero): InfoMat(Matriz,entero,entero): FilasMat(Matriz): ColsMat(Matriz): entero

Matriz Matriz entero entero

Matriz CrearMat(int filas,int cols) /*Construye y retorna una matriz de filas-1 filas y cols-1 columnas, inicializando todos sus elementos a cero*/ {precondiciones: filas>0,cols>0} {postcondiciones: CrearMat es una matriz de [0..fila-1,0..cols-1],x[i,k]=0} void AsignarMat(Matriz mat,int fila,int col,int valor) /*Asigna a la celda [fila,col] el {precondiciones: {postcondiciones: mat[fila,col]=valor} int InfoMat(Matriz mat,int fila,int col) /*Retorna el contenido de {precondiciones: {postcondiciones: InfoMat=mat[fila,col]} void FilasMat(Matriz mat) /*Asigna a la celda

la

valor de valor*/ 0