Tipos Abstractos de Datosinformatica.utem.cl/~mcast/ESDATOS/TADS/Ttema1.pdf · binaria en un vector ordenado ... $ Desequilibrio entre acciones abstractas o de alto nivel y tipos

Algoritmos y Estructuras de Datos II I.T. en Informática de Gestión/Sistemas Universidad de Huelva 1

Tema 1 Tipos Abstractos de Datos

Objetivos

! Introducir el mecanismo de abstracción y justificar la necesidad de los TAD

! Diferenciar adecuadamente los conceptos de especificación e implementación de TAD

! Presentar la especificación algebraica como método formal de definición de TAD

Contenidos

1.1 Concepto de abstracción, terminología y ejemplos

1.1.1 Concepto de abstracción

1.1.2 Tipos abstractos de datos

1.2 Programación con TAD

1.2.1 Los TAD como base del diseño modular

1.2.2 La programación en gran escala

1.2.3 TAD genéricos y algoritmos genéricos



Duración

! 5 clases (7,5 h)

Contenidos

1.3 Especificación algebraica de TAD

1.3.1 Introducción

1.3.2 Signatura de una especificación algebraica

1.3.3 Ecuaciones de una especificación algebraica

1.4 Construcción de especificaciones

1.4.1 Operaciones: clasificación

1.4.2 Escritura de ecuaciones

1.4.3 Situaciones de error

1.4.4 Ejemplos de especificaciones algebraicas



Bibliografía

! Estructuras de datos. Especificación, diseño e implementaciónAutor: Xavier Franch GutiérrezEditorial: Ediciones UPC, 1999Págs. 19-65

! Diseño de programas. Formalismo y abstracciónAutor: Ricardo Peña MaríEditorial : Prentice-Hall, 1999Págs. 155-204



ABSTRACCIÓN: Método de resolución de problemas que consiste en destacar los detalles importantes y dejar a un lado los irrelevantes

! Ejemplos de abstracción en ciencia de la computación:

! Lenguajes de alto nivel respecto lenguaje ensamblador

! Procedimientos y funciones con parámetros

! Librerías de los lenguajes de programación

! Lenguajes visuales (DELPHI, Visual Basic, Visual C, etc.)

1.1 Conceptos, terminología y ejemplos

1.1.1 Concepto de abstracción


Tema 1

! Distinguimos 2 formas de abstracción

! Abstracción de acciones o funcional

" Procedimientos y funciones

" Se le asigna un nombre y se parametriza

" Se oculta información

" Separación entre qué hace (especificación) y cómo se hace (implementación)

! Abstracción de Datos

" Tipos básicos o estándar: entero, carácter, booleano, etc.

" Tipos simples definidos por el programador: enumerado, subrango

" Tipos estructurados: array, registro → constructores genéricos (genericidad)

" Tipo Abstracto de Datos (TAD)

Tipos Abstractos de Datos


Tema 1

Definición de TAD

Colección de valores y de operaciones definidas sobre ellos mediante una especificación independiente de cualquier representación

! La programación con TAD requiere 2 pasos que generan 2 piezas de documentación

" PASO 1: Definición o especificación del tipo

# Visible al usuario

# Precisa, legible y no ambigua

# Nombre del tipo + sintaxis y semántica de las operaciones

" PASO 2: Implementación del tipo

# Oculta al usuario

# Estructurada, eficiente y legible

# Elección de la representación más adecuada + algoritmos de las operaciones


1.1.2 Tipos Abstractos de Datos



TAD

Especificación Implementación

Representación Algoritmos Sintaxis Semántica

! Objetivo: separar el uso del tipo de dato de su implementación


Tema 1

! Métodos para especificar un tipo abstracto de datos

! Especificación formal (especificación algebraica)

! Especificación informal (lenguaje natural)

! Especificación semi-formal

! Para el tipo

# Nombre

# Descripción

# Características

# Valores no admitidos

! Para las operaciones

# Parámetros

# Valor de retorno

# Precondiciones. Requisitos que se deben cumplir para que una llamada al procedimiento o función se comporte como se describe en “efecto”

# Efecto. Resultado que se produce cuando se realiza una llamada correcta

# Excepciones. Comportamiento cuando se da una circunstancia que no permite la realización exitosa de su ejecución




! Precondiciones vs. Excepciones

" Precondiciones:

# Contexto muy limitado (fácil verificar que se satisfacen las restricciones), implementación más eficiente o más simple

" Excepciones:

# Siempre que sea posible, la implementación debería comprobar las restricciones y lanzar una excepción en caso de que no se satisfagan. Puede no tener sentido, como en una búsqueda binaria en un vector ordenado

# Si una excepción se produce para un cierto subconjunto de valores de los argumentos, este subconjunto no debería aparecer en la cláusula precondiciones



! Ejemplo. Un TAD para almacenar fichas de personas con una serie de operaciones:

Documento de definición del TAD Ficha de personas

Definición del TIPO

Nombre: ficha

Descripción: Este tipo almacena información sobre personas. Se puede almacenar el nombre, la edad y el número de hijos

Características: Permite nombres iguales. Admite cualquier cadena de caracteres como nombre. Otras características.

Valores no admitidos: Los descritos en la operación Crear


Tema 1

Definición de las OPERACIONES

constructor Crear (n: cadena; e, h: byte);{

Parámetros:

n: cadena de caracteres donde se almacena el nombre de la persona

e: número natural que indica la edad de la persona

h: número natural que indica el número de hijos que tiene la persona

Devuelve:

Precondiciones:

0 < e ≤ 110

0 ≤ h ≤ 15

Efecto:

Crea una ficha con los valores indicados en los argumentos

Excepciones:

Si (e < 16 y h > 0) no se crea la ficha

}




...

function Descuento: Real;{

Parámetros:

Devuelve:

El porcentaje del descuento

Precondiciones:

Efecto:

Calcula el descuento de una persona dependiendo del número de hijos que tenga, según esta tabla:

Un 25% si tiene 1 ó 2 hijos

Un 50% si tiene entre 3 y 5 hijos



Excepciones:

}


Tema 1

En PASCAL, los TAD se crean en unidades independientesunit tadFicha;

interface

uses ...

type cadena = String[50];

type Ficha = object

public

constructor crear (n: cadena; e, h: byte);

procedure ver;

function descuento: real;

private

nombre: cadena;

edad: 1..110;

hijos: 0..15;

end;

implementation

uses ...

constructor Ficha.crear (n: cadena; e, h: byte);

{ codificación de la operación }

end. { Fin de la unidad }



Tema 1

! El usuario sólo podrá crear y manipular variables de tipo ficha con las operaciones que se ofrecenprogram usuario;

uses tadFichas;

var f1, f2, f3, f4: Ficha;

d1: Real;

res: Integer;

f1 := ¿?

f2.crear ('José Luís … ', 30, 3); { resultado correcto }

f3.crear ('Antonio … ', 5, 2); { salta una excepción }

f4.crear ('Isabel … ', 26, -5); { no cumple las precondiciones. Resultado impredecible }

d1 := f2.descuento ;

La encapsulación u ocultación de la información consiste en:

$ Privacidad de la representación. El usuario no conoce los detalles de cómo se representan los

datos en la memoria del ordenador.

$ Protección del tipo. El usuario sólo puede usar las operaciones definidas en la especificación.




! Abstracción →TAD distingue entre:

! Elementos importantes

" La interfaz que debe conocer el usuario

" Nombre del tipo y los encabezamientos + la especificación de las operaciones

! Detalles ocultables

" Elección de la representación de los valores

" Implementación de las operaciones básicas:

# Si no se eligen operaciones útiles, el tipo carecerá de funcionalidad

# Una de las operaciones permita generar valores del tipo → operación generadora



1.2 Programación con TAD

1.2.1 Los TAD como base del diseño modular

! Modularidad. Mecanismo que permite descomponer el código de un proyecto software

! Módulo. Unidad de programa que puede ser desarrollada independientemente del resto

! Un diseño modular correcto desde el punto de vista de la Ingeniería de la Programación o Ingeniería del Software, debe cumplir una serie de requisitos:

$ Facilidad de descomponer un problema en subproblemas menos complejos

$ Mínima conexión entre los módulos

$ Los cambios y mejoras del proyecto deben afectar sólo a un número pequeño de módulos

! Los TAD son una base ideal para la división modular

$ Interfaz simple + ocultación de información

$ Cambios en la implementación sin afectar a los programas que usan el tipo

$ Tamaño adecuado



! El diseño descendente junto con la abstracción funcional no es suficiente:

$ Desequilibrio entre acciones abstractas o de alto nivel y tipos de datos concretos o de bajo nivel

$ Decisiones sobre la representación de los datos se toman desde el principio

1.2.2 La programación en gran escala

algoritmos + estructuras de datos = programas

algoritmos de datos

algoritmos de control

algoritmos de control + TAD = programas


Tema 1

! Ejemplo: Programa que lea una secuencia de enteros desde fichero y escriba en pantalla cada entero distinto leído junto con su frecuencia de aparición, en orden decreciente de frecuencias


algoritmo estadística

importa tadFrecuencias

vart: tablaF; nombre: cadena; dato: entero;

fvarinicio

escribir (‘Nombre del fichero: ’);

leer (nombre); asociar (f, nombre);iniciarLectura (f);

t.inicializar;

mientras fin (f) hacerleer (f, dato);t.añadir (dato);

fmientraspara orden:= 1 hasta t.total hacer

escribir (‘Número: ’, t.infoEnt(orden), ‘Frecuencia: ’,

t.infoFrec(orden));fpara

falgoritmo

ENTRADA: 5 15 25 5 7 5 7 15 7 5

SALIDA: 5 4

7 3

15 2

25 1

El algoritmo recoge sólo los aspectos esenciales. Falta implementar el tipo

tablaF y sus operaciones



Documento de definición del TAD tablaF

Definición del TIPO

Nombre: tablaF

Descripción: Almacena números enteros junto con la frecuencia de aparición de cada uno de ellos

Características: Se utiliza para contar las veces en las que aparece cada número cuando se lee una

secuencia de números enteros

Valores no admitidos:


Tema 1


constructor inicializar;

{

Parámetros:

Devuelve:

Precondiciones:

Efecto:

crea una tabla de frecuencias vacía

Excepciones:

}



Tema 1


acción añadir (n: entero);

{

Parámetros:

n: entero que debe añadirse a la tabla de frecuencias

Devuelve:

Precondiciones:

Efecto:

Si n no está en la tabla, lo añade e inicializa a 1 su frecuencia de apariciones. En caso contrario, se incrementa en 1 su frecuencia.

Excepciones:

}



Tema 1


función total: entero;

{

Parámetros:

Devuelve:

el número de enteros distintos que hay en la tabla

Precondiciones:

Efecto:

Excepciones:

}



Tema 1


función infoEnt (i:entero): entero;

{

Parámetros:

i: posición i-ésima de la tabla

Devuelve:

entero que ocupa el i-ésimo lugar en la tabla en orden decreciente de frecuencias

Precondiciones:

1 ≤ i ≤ total

Efecto:

Excepciones:

}





función infoFrec (i:entero): entero;

{

Parámetros:

i: posición i-ésima de la tabla

Devuelve:

número de veces que se encuentra el entero que ocupa la posición i-ésima en la tabla, según el orden descendiente de frecuencias

Precondiciones:

1 ≤ i ≤ total

Efecto:

Excepciones:

}


Tema 1

! Siguiente refinamiento: elección de la representación del tipo tablaF e implementación de las operaciones


tipo

elemento = registronúmero, frec: entero;

fregistro;

tablaF = clasefrecs: tabla [1..max] de elemento;numElems: entero;

fclase;

! Distintas soluciones

! Ninguna debe influir en el código del algoritmo principal

! Ejemplo: la ordenación se puede hacer en las operaciones infoX en lugar de ir ordenándola cada vez que se añade un elemento mediante la operación añadir



! La parametrización aplicada a la abstracción de datos permite definir TAD genéricos. Ej.: tablaF capaz de almacenar frecuencias de elementos de un tipo cualquiera

! Se pueden definir también acciones genéricas: se utilizan parámetros en lugar de tipos concretos. Ej.:

acción intercambiar(x, y: entero); acción intercambiar (x, y: T);var t: entero; var t: T;inicio inicio

t := x; x := y; y := t t := x; x := y; y := tfacción facción

1.2.3 TAD genéricos y algoritmos genéricos



1.3 Especificación algebraica de un TAD

1.3.1 Introducción

! Especificación algebraica. Técnica formal para especificar tipos abstractos de datos

OBJETIVO

Definir sin ambigüedades un tipo de datos

conjunto de valores

sintaxis y significado de cada operación

permitida

VENTAJAS

! Define tipos independientemente de cualquier representación e implementación

! Consigue unanimidad en la interpretación del tipo

! Posibilita la obtención de código automáticamente a partir de la especificación algebraica(aún no muy desarrollado)



número y tipo de los parámetros, y tipo del resultado

1.3.2 Signatura de una especificación algebraica

! Signatura. Define los géneros y los nombres de las operaciones con sus perfiles

CARACTERISTICAS

! Notación funcional

! Cada operación es una función con 0 o más parámetros

! Todas las operaciones devuelven un único valor de un tipo determinado

nombres de los nuevos tipos a especificar



Ejemplo: Signatura del TAD tablaF

palabras reservadas para indicar el comienzo y el

final de una especificación

importación de definiciones hechas en otras especificaciones

nombre de los tipos que se van a especificar

nombre de operación

perfil de operación

espec tadFrecuencia

usa naturales, enteros

género tablaF

operaciones

inicializar: % tablaF

añadir: tablaF entero % tablaF

total: tablaF % natural

infoEnt: tablaF natural % entero

infoFrec: tablaF natural % natural

fespec



OTRAS CARACTERISTICAS

! Existen operaciones sin parámetros CONSTANTES

# t.inicializar;

# En un lenguaje imperativo:

• t := inicializar();

• inicializar(t);

! La traducción de notación algebraica (funcional) a OO es inmediata. El parámetro cuyo tipo es el que aparece en el género se convierte en el objeto sobre el que se aplica el método

# inicializar se transforma en un procedimiento sin parámetros

# total se transforma en una función sin parámetros

# añadir, infoEnt, infoFrec se transforman en funciones con un único parámetro



Ejemplo. Posible signatura de los tipos booleanos y naturales con el 0

espec boolnat

géneros booleano, natural

operaciones

verdad, falso : % booleano

_ : booleano % booleano

_ ∧ _ , _ ∨ _ : booleano booleano % booleano

0 : % natural

suc : natural % natural

_ + _ , _ * _ : natural natural % natural

_ ≤ _ , _ > _ : natural natural % booleano

fespec

Constantes

Notación prefija. El nombre de la operación y los parámetros entre paréntesis, separados por comas.

suc(x) = y

Notación infija. El símbolo _ indica la posición de los argumentos o

parámetros.

x ≤ y = verdad



! Para cada género existe un conjunto de términos bien formados ⇒ sintácticamentecorrectos

! Cada constante es un término y mediante la aplicación sucesiva y correcta de símbolos de operaciones de una signatura se pueden construir términos

! Ejemplos de términos bien formados :

0

(suc (suc (0)) * suc(0)) ≤ suc(0)

((verdad ∧ falso) ∧ ( falso)) ∨ (0 > (suc (0)))

! Cada valor del tipo puede caracterizarse por un término denominado término canónico



1.3.3 Ecuaciones de una especificación algebraica

! También se conocen con el nombre de axiomas

! Determinan las propiedades y el comportamiento de las operaciones

! Toda especificación debe cumplir:

& sólo pertenecen al tipo los valores que puedan ser creados mediante términos sintácticamente correctos

& cada término bien formado denota un valor diferente del tipo especificado



Ejemplo. Queremos especificar el tipo naturales con el 0

espec naturales_1género natural

operaciones0 : % natural

suc : natural % naturalfespec

# únicos valores que pueden construirse:

0, suc (0), suc (suc (0)), suc (suc (suc (0))), etc.

# cada término denota un valor diferente

Añadimos a la especificación la operación suma


operaciones0 : % naturalsuc : natural % natural

_ + _ : natural natural % naturalfespec

# incumple la segunda propiedad

# "suc (0)" y "0 + suc (0)“ generan el natural 1



! 2 puntos de vista respecto al papel de las ecuaciones en las especificaciones algebraicas:

# igualar términos que generan el mismo valor (punto de vista algebraico)

# definir el comportamiento de las operaciones con todas las posibles combinaciones de valores (patrones) que pueden tomar sus parámetros (punto de vista semántico)

! Formato de una ecuación: término_1 = término_2

# donde término_1 y término_2 son términos bien formados de un mismo género



espec naturales_3

género natural

operaciones

0 : % natural

suc : natural % natural

_ + _ : natural natural % natural

ecuaciones x, y: natural

x + 0 = x

x + suc (y) = suc (x+y)

fespec

! Punto de vista algebraico

# igualar términos

! Punto de vista semántico

# definir el comportamiento de las operaciones con todos los patrones o representantes del tipo



Ejemplo. Completar la especificación algebraica de los booleanos

espec bool

género booleano

operaciones

verdad, falso: % booleano

_: % booleano

_ ∧ _ , _ ∨ _ : booleano booleano % booleano

ecuaciones b: booleano

verdad =

falso =

b ∨ verdad = verdad ∨ b =

b ∨ falso = falso ∨ b =

b ∧ verdad = verdad ∧ b =

b ∧ falso = falso ∧ b =

fespec



1.4 Construcción de especificaciones

1.4.1 Operaciones: clasificación

! g: símbolo o identificador del género correspondiente al tipo que se desea especificar

! OP(g): conjunto de operaciones relacionadas con g

! Clasificación:

' Constructoras. Cons(g)

& Generadoras. Gen(g)

& Modificadoras. Mod(g)

' Observadoras. Obs(g)

Gen(g)

Cons(g) =

Mod(g)

OP(g) =

Obs(g)



espec naturales

usa booleanos

género natural

operaciones

0 : % natural

suc: natural % natural

_ + _ : natural natural % natural

_ ≤ _ : natural natural % booleano

fespec

Natural

espec secuenciaDeNaturales

usa naturales_3

género secN

operaciones

[ ] : % secN {secuencia vacía}

[ _ ] : natural % secN {secuencia unitaria}

_ ++ _ : secN secN % secN {concatenar secuencias}

_ ⊕ _ : natural secN % secN

{añadir un natural a una secuencia}

ecuaciones x: natural; s, s1, s2, s3: secN

s ++ [ ] = s

[ ] ++ s = s

(s1 ++ s2) ++ s3 = s1 ++ (s2 ++ s3)

x ⊕ s = [x] ++ s

fespec

Bolsa

¿Clasificación de las operaciones?



! El conjunto Gen(g) puede ser:

& Conjunto libre de generadoras: todo término formado sólo por constructoras generadoras denota un valor diferente en el tipo de datos correspondiente a g

& Conjunto no libre de generadoras: dos o más términos distintos formados sólo por constructoras generadoras denotan un mismo valor del tipo

¿Son libres o no libres?

• Gen (natural) = {0, suc}

• Gen (secN) = { [ ], _ ⊕ _ }

• Gen (secN) = { [ ], [ _ ], _ ++ _ }



1.4.2 Escritura de ecuaciones

! Paso 1. Elegir conjunto de operaciones generadoras

! Paso 2. Si Gen(g) es un conjunto no libre, escribir ecuaciones entre generadoras. Si es libre, no hacer nada

! Paso 3. Escribir todas las ecuaciones necesarias para definir el comportamiento de cada operación modificadora

! Paso 4. Escribir todas las ecuaciones necesarias para definir el comportamiento de cada operación observadora



1.4.3 Situaciones de error

Ejemplo. Queremos añadir la operación predecesor a los naturales


operaciones0 : % natural

suc : natural % naturalparcial pred: natural % natural

dominios de definición x: natural

pred (suc (x))

ecuaciones x: natural

pred (suc (x)) = x

fespec

# la operación predecesor no está definida para el natural 0 → situación de error

# es una operación parcial → no puede aplicarse a todos los valores del dominio

# en la sección dominios de definición se especifican los dominios donde están definidas las operacionesparciales de la especificación



1.4.4 Ejemplos de especificaciones algebraicas

espec conjunto de caracteresusa booleanos, caracteres, naturalesgenero conjcaroperaciones

∅ : % conjcarponer, quitar: carácter conjcar % conjcar

_ ∪ _ , _ ∩ _ : conjcar conjcar % conjcar_ ∈ _ : carácter conjcar % booleanoesVacío: conjcar % booleanocardinal: conjcar % natural

Ejemplo. Completar la especificación algebraica del TAD Conjunto de caracteres.

Documents

Tipos Abstractos de Datosinformatica.utem.cl/~mcast/ESDATOS/TADS/Ttema1.pdf · binaria en un vector ordenado ... $ Desequilibrio entre acciones abstractas o de alto nivel y tipos