ttema1

Ampliacin de Estructuras de Datos y de la Informacin E.S.E. Informtica

Tema 1. Introduccin a los TAD

Objetivos En este tema nos ocupamos inicialmente del concepto de abstraccin, dedicando la mayor atencin a la abstraccin de datos, estudiando aspectos relacionados con su especificacin e implementacin. Tambin sern objeto de atencin la forma en que los lenguajes de programacin soportan la abstraccin de datos y algunas propiedades de los tipos abstractos de datos (TAD). Adems, veremos algunos ejemplos de TAD, presentando tanto su especificacin como su implementacin usando el lenguaje de programacin Java.

Planificacin Se estiman 4 horas.

Contenidos 1. Abstraccin de datos

1.1. Especificacin 1.2. Implementacin 1.3. Lenguajes de programacin 1.4. Propiedades de los TAD

Modificabilidad Clases de operaciones

2. Ejemplo

Bibliografa

Bsica Franch Gutirrez, X., Estructuras de datos. Especificacin, Diseo e implementacin. Ediciones UPC, 1999. Pgs. 19-25, 53-65

Liskov, B. y J. Guttag, Program Development in Java: Abstraction, Specification, and Object-Oriented Design, Addison-Wesley, 2001. Pgs. 1-13, 39-56, 77-123

Departamento de Informtica 1 Reyes Pavn


Complementaria Liskov, B. y J. Guttag, Program Development in Java: Abstraction, Specification, and Object-Oriented Design, Addison-Wesley, 2001. Pgs. 57-75, 125-146, 189-205 Pea Mar, R., Diseo de Programas: Formalismo y Abstraccin, 2 ed., Prentice Hall, 1998. Pgs. 155-226



Tema 1. Introduccin a los TAD

1. Abstraccin de datos

Abstraccin de datos o tipo abstracto de datos (TAD): nuevo tipo de dato ms un conjunto de operaciones que permiten manipular los objetos de dicho tipo

Abstracto los objetos del tipo deben ser manipulados mediante sus operaciones, sin necesidad de ninguna nocin adicional sobre el tipo

Objeto (no variable)

Los TAD permiten: Aadir nuevos tipos de datos: permiten definir y utilizar

tipos de datos distintos a los predefinidos en el lenguaje de programacin

Encapsular informacin:

Es posible localizar la definicin del tipo y el cdigo de todas las operaciones sobre ese tipo en una determinada seccin del programa

Un cambio en el TAD revisar una pequea seccin del programa (no hay detalles en otras partes que puedan ocasionar errores relacionados con ese tipo de datos)

Forma de organizar los programas en unidades lgicas que en muchos lenguajes de programacin pueden compilarse separadamente

Ocultar la representacin:

Los TAD se estructuran en dos partes: interfaz e implementacin

Interfaz: lista de operaciones junto con sus argumentos (tipo de los parmetros de entrada y el




tipo del resultado). Es la nica parte visible al usuario del TAD

Implementacin: lugar en donde se define cmo realizar las operaciones del TAD. Esta parte slo es visible al programador basta con preservar la integridad de la informacin en esta seccin, donde los posibles errores estarn controlados

Para poder utilizar un TAD es necesario disponer de su especificacin: caractersticas del tipo de dato + significado de las operaciones (especificacin de funcin)

El cdigo de las unidades de programa que usan el tipo no dependen de su implementacin

La implementacin puede cambiar sin afectar a las unidades de programa que usan el tipo

Se garantiza la fiabilidad de las unidades de programa que usan un TAD y la integridad de los objetos de ese tipo

Programa

Interfaz

Caractersticas

+ Operaciones

Implementacin

Estructura de datos

+ algoritmos

Solicita operacin

Resultado operacin


Objetivo: separar el uso del tipo de dato de su implementacin dividir el diseo de un TAD en dos partes: especificacin e implementacin

Especificacin: define como se puede utilizar el tipo de dato = sintaxis + semntica

Implementacin: define una posible realizacin del tipo de dato = representacin (o estructura de datos) + algoritmos de las operaciones (en funcin de dicha estructura de datos)

TAD

Especificacin Implementacin

Representacin Algoritmos Sintaxis Semntica

1.1. Especificacin

Especificacin de un TAD = descripcin de los objetos del tipo de dato + operaciones realizables sobre ellos

Propiedades de la especificacin: Precisa: dice slo lo imprescindible

General: adaptable a diferentes contextos

Legible: debe transmitir el comportamiento del tipo

No ambigua: debe evitar dobles interpretaciones



Formas de realizar la especificacin: Formal: mediante axiomas algebraicos

Informal: usando el lenguaje natural. Para conseguir mayor precisin se utilizan un conjunto de clusulas especificacin cuasi-formal

Especificacin cuasi-formal del TAD

Esquema de especificacin Nombre del tipo de dato

Declaracin de tipos: tipos de datos que va a utilizar el TAD (tipos predefinidos de un lenguaje de programacin u otros TAD)

Caractersticas: descripcin de los objetos mediante otros previsiblemente comprensibles para el lector de la especificacin. Indica si los objetos son o no modificables

Operaciones: especificacin de cada operacin siguiendo una notacin cuasi-formal



Especificacin de cada operacin

Permite centrarnos en qu hace una funcin y no en cmo lo hace.

Tipos: Formal: mediante asertos de entrada y salida

(precondicin y postcondicin)

Informal usando lenguaje natural ambigedad. Para conseguir mayor precisin se puede realizar una cierta formalizacin mediante clusulas especificacin cuasi-formal

Clusulas de la especificacin cuasi-formal: Necesita: Conjunto de condiciones suficientes para asegurar

la ejecucin adecuada de la funcin restricciones bajo las cuales se define la abstraccin. Ejs:

funcin raizCuadrada (x: real) devuelve real; { Necesita: x 0 Produce: Devuelve la raz cuadrada de x }

funcin buscaEnOrden (a: vector de entero; x: entero) devuelve entero; { Necesita: a est ordenado en orden ascendente Produce: Si x est en a, devuelve el ndice del vector donde est almacenada. En caso contrario, devuelve 1. }

Modifica: Nombres de las entradas (argumentos o variables no locales) que se modifican en la invocacin a la funcin identificacin de efectos laterales.

Produce: Comportamiento de la funcin para todas las entradas que cumplen la clusula necesita: qu salidas produce y qu modificaciones se realizan sobre las variables indicadas en la clusula modifica. Se asume que la clusula necesita se satisface y no se dice nada sobre el comportamiento de la funcin en caso contrario.

Abstraccin parcial vs. total:



Parcial: presenta una clusula necesita

Desventaja: queda en manos del usuario comprobar si se cumplen las restricciones de la clusula necesita

Ventaja: en ocasiones pueden implementarse ms eficientemente que las totales (ej: buscaEnOrden) o de manera ms simple (con menos comprobaciones)

Total: caso contrario son ms seguras

Clusula necesita vs. excepciones Clusula necesita:

Cuando la funcin va a utilizarse slo en un contexto muy limitado, en el que es fcil verificar que se satisfacen las restricciones, y si esto supone una implementacin ms eficiente o ms simple

Excepciones:

Siempre que sea posible, la implementacin debera comprobar las restricciones de la clusula necesita y lanzar una excepcin en caso de que no se satisfagan. Puede no tener sentido como en buscaEnOrden

La clusula produce debe identificar las condiciones que provocan la excepcin

Si una excepcin se produce para un cierto subconjunto de valores de los argumentos, este subconjunto no debera aparecer en la clusula necesita

Ejemplo de conversin de una abstraccin parcial en total:

funcin raizCuadrada (x: real) devuelve real lanza ExcepcionNegativo { Produce: Si x < 0 lanza ExcepcionNegativo, sino devuelve la raz cuadrada de x }



Ejemplo: especificacin cuasi-formal del tipo racional Tipo Racional

Declaracin de tipos Racional, Entero

Caractersticas El valor abstracto de un objeto del tipo ser un nmero racional Los objetos no son modificables

Operaciones funcin ConstruirRacional (n, d: Entero) devuelve Racional lanza ExcepcinDenominadorCero { Produce: Si d = 0 lanza ExcepcinDenominadorCero, sino devuelve el nmero racional n/d }

funcin Numerador (r: Racional) devuelve Entero { Produce: el numerador de r. }

funcin Denominador (r:Racional) devuelve Entero { Produce: el denominador de r. } funcin Suma (r1, r2:Racional) devuelve Racional { Produce: el racional r1+ r2. } funcin Simplifica (r: Racional) devuelve Racional { Produce: un racional equivalente a r e irreducible. } fin Racional

Conocida la especificacin de un tipo, y slo sta, puede realizarse cualquier algoritmo que utilice el TAD

Ej: producto de dos nmeros racionales

funcin Multiplica (r1, r2: Racional) devuelve Racional { Produce: el racional r1 * r2. } inicio retorna Simplifica(ConstruirRacional (Numerador(r1) * Numerador(r2), Denominador(r1) * Denominador(r2))) ffuncin;

1.2. Implementacin

Se elige una representacin, o estructura de datos, para los objetos y se realizan los algoritmos correspondientes a las operaciones en funcin de dicha representacin



La representacin elegida debe permitirnos implementar las operaciones de forma eficiente, razonablemente simple y hacer posible que algunas de las operaciones ms habituales se ejecuten ms rpidamente

Como unas representaciones hacen ms eficientes unas operaciones que otras estudiar las distintas posibilidades

Ej: implementacin del TAD Racional en Java public class Racional { private int num, den; public Racional (int n, int d) throws ExcepcionDenominadorCero { if (d == 0) throw new ExcepcionDenominadorCero("Racional: denominador cero"); num = n; den = d; } public int numerador() { return num; } public int denominador() { return den; } public Racional suma(Racional r) { return new Racional(num * r.den + den * r.num, den * r.den); } public Racional simplifica() { int mcd = OpEnteros.mcd(num, den); return new Racional(num / mcd, den / mcd); } }

Normalmente existirn varias implementaciones para una misma especificacin



1.3. Lenguajes de programacin

La abstraccin de datos es una tcnica de diseo de programas su utilizacin independiente del lenguaje de programacin

El uso e implementacin de TAD con lenguajes de programacin que no los soportan convenientemente deficiencias en: Ocultacin de la representacin: No ocultan la

representacin de los objetos no pueden comprobar el buen uso de la abstraccin de datos

Inicializacin de las estructuras de datos: No disponen de un procedimiento automtico de inicializacin de las estructuras de datos que se utilizan para representar a los objetos del tipo invocar a una accin para inicializar convenientemente dichas estructuras

Compilacin independiente

Abstracciones polimrficas: Un TAD puede ser polimrfico con respecto a los tipos de los elementos que contienen sus objetos. Un procedimiento o iterador puede ser tambin polimrfico con respecto a los tipos de uno o ms de sus argumentos

Ej. de LP con deficiencias: Pascal units de Turbo Pascal permiten:

Ocultar la representacin de un tipo de dato (o al menos se puede dejar inaccesible)

Inicializar las estructuras de datos Compilar de forma independiente

Abstraccin de datos en Java Lenguaje orientado a objetos basado en clases



Facilita la ocultacin de la representacin mediante la visibilidad de los atributos (private)

Permite la inicializacin de las estructuras de datos mediante los mtodos constructor

Cada clase se puede compilar independientemente.

Posee mecanismos para realizar abstracciones polimrficas

Permite el polimorfismo funcional como de tipos Una superclase comn a todas: Object Parmetros de tipo (generics, a partir de Java 1.5)

La abstraccin de datos es una tcnica de diseo de programas el desarrollo de programas en un LP que no soporte convenientemente la abstraccin de datos no impide el utilizar sta en el diseo de los mismos

El usuario de la abstraccin es el responsable de mantener el paradigma de programacin (el compilador no aporta ningn mecanismo de control del buen uso de la misma)

1.4. Propiedades de los TAD

Modificabilidad

TAD modificable = puede cambiar el estado de los objetos del tipo pueden cambiar los valores de sus atributos

Disear un TAD modificable o no modificable? No modificable: los objetos deben mantener de forma natural

sus valores (ej.: racionales, complejos)




Ms fiables, pero Con objetos que se crean y rechazan frecuentemente

recuperacin de espacios de memoria debe realizarse a menudo (por ej., empleando tcnicas de recogida de basura)

Modificable (ej.: colas de clientes en sistemas de simulacin)

TAD Racional no modificable: Todas las operaciones devuelven objetos nuevos consumo

de memoria

No existen operaciones que puedan modificar los objetos

Ej:

Racional r1 = new Racional(10, 5); Racional r2 = new Racional(2, 3); Racional r3 = r1.suma(r2).simplifica();

En las abstracciones modificables el consumo de memoria no es un factor crtico operaciones que modifican objetos en lugar de crear nuevos

Ej.: Si la operacin Simplifica fuera una operacin modificadora:

Racional r3 = r1.suma(r2); r3.simplifica();

10

5 2

3

40

15 8

3

r1

r2

r3

Heap



Pueden los objetos compartir espacio de memoria? Inters: aprovechar al mximo el espacio de memoria

disponible (tanto TAD modificables, como no modificables)

Ej.: TAD Lista cuyos elementos son caracteres. A partir de la lista l1=('a' 'b' 'c') se crea la lista l2=('b' 'c'). Posibilidades:

El espacio de memoria ocupado por cada uno de los elementos de ambas listas sea distinto objetos no compartidos

'a' 'b' 'c'l1

'b' 'c'l2

Espacio de memoria ocupado por los elementos comunes 'b' y 'c'

sea el mismo, en cuyo caso los objetos estn compartidos y se ahorra el espacio correspondiente a dos caracteres

'a' 'b' 'c'l1

l2

10

5 2

3

8

3

r1

r2

r3

Heap


Las modificaciones en una de las listas pueden afectar a la otra. Ej.: insertar un elemento al final de una de ellas (l2.insertaFinal('d')) modificara ambas

'a' 'b' 'c' l1

l2

'd'

Este problema slo se produce si las abstracciones de datos son modificables

Clases de operaciones

Creadores: crean objetos de su tipo de dato sin tomar ningn objeto del mismo tipo como entrada. Todos los creadores son constructores, aunque no ocurre lo contrario

Productores: crean objetos del tipo de dato tomando algn objeto del mismo tipo como entrada

Modificadores: modifican los objetos del tipo de dato slo se dan en las abstracciones modificables

Observadores: toman como entrada objetos del tipo de dato y devuelven resultados de otros tipos

Ej.: TAD Racional Creadores: Racional

Productores: suma y simplifica

Modificadores: ninguno

Observadores: numerador y denominador



2. Ejemplo

Especificacin public class Conjunto { // Declaracin de tipos: Conjunto, // Caractersticas: // Conjunto ilimitado de elementos de tipo . Un Conjunto tpico es

// {x1, , xn} siendo xi de tipo // Los objetos son modificables // Constructores public Conjunto() // Produce: Inicializa this al vaco // Mtodos public void inserta(E x) // Modifica: this // Produce: Aade x a los elementos de this, esto es, // this_post = this { x } public void elimina(E x) // Modifica: this // Produce: Elimina x de this, esto es, this_post = this { x } public boolean pertenece(E x) // Produce: Si x est en this devuelve cierto; falso en caso contrario public int cardinal() // Produce: Devuelve el nmero de elementos de this public E elige() throws ExcepcionConjuntoVacio // Produce: Si this est vaco lanza la excepcin // ExcepcionConjuntoVacio. En caso contrario, devuelve un // elemento cualquiera de this. }




Implementacin public class Conjunto { private Vector elementos; // la representacin del tipo // Constructores public Conjunto() { elementos = new Vector(); } // Mtodos public void inserta(E x) { if (elementos.indexOf(x) < 0) elementos.addElement(x); } public void elimina(E x) { int i = elementos.indexOf(x); if (i >= 0) { elementos.setElementAt(elementos.lastElement(), i); elementos.removeElementAt(elementos.size()-1); } } public boolean pertenece(E x) { return elementos.indexOf(x) >= 0; } public int cardinal() { return elementos. size(); } public E elige() throws ExcepcionConjuntoVacio { if (elementos. size() == 0) throw new ExcepcionConjuntoVacio("Conjunto.elige: Conjunto vaco."); return elementos.lastElement(); } }

Tema 1. Introduccin a los TADObjetivosPlanificacinContenidos1. Abstraccin de datos1.1. Especificacin1.2. Implementacin1.3. Lenguajes de programacin1.4. Propiedades de los TAD Modificabilidad Clases de operaciones

2. EjemploBibliografaBsicaComplementaria

Tema 1. Introduccin a los TAD1. Abstraccin de datos1.1. EspecificacinEspecificacin cuasi-formal del TADEspecificacin de cada operacin

1.2. Implementacin1.3. Lenguajes de programacin1.4. Propiedades de los TADModificabilidadClases de operaciones

2. Ejemplo

ttema1

Documents