PDF de programación - Tema 1. Tipos abstractos de datos - Estructuras de Datos y Algoritmos

Estructuras de Datos 

y Algoritmos

Tema 1. Tipos abstractos de datos

Prof. Dr. P. Javier Herrera

Índice

1
2
3

Concepto de TAD, terminología y ejemplos
Especificación algebraica de TAD’s
Construcción de especificaciones

Tema 1. Tipos abstractos de datos ‐ Curso 2014/15

22

1. Tipos Abstractos de Datos

•

•

•

Un tipo abstracto de datos (TAD) es un conjunto de valores junto con las operaciones que 
sobre él se pueden aplicar, las cuales cumplirán diversas propiedades que determinarán su 
comportamiento.

Es necesario utilizar una notación formal para describir el comportamiento de las 
operaciones.

El calificativo “abstracto” responde al hecho de que los valores de un tipo pueden ser 
manipulados solamente mediante sus operaciones, conociendo sobre ellas únicamente las 
propiedades que cumplen, sin que sea necesario ningún conocimiento adicional sobre la 
representación del tipo o la implementación de dichas operaciones.

Tema 1. Tipos abstractos de datos ‐ Curso 2014/15

33

1. Tipos Abstractos de Datos

•

La manipulación de los objetos de un tipo solo depende del comportamiento descrito en su 
especificación y es independiente de su implementación.

Especificación
•
•
•

La especificación de un TAD consiste en establecer las propiedades que lo definen. 
Una especificación ha de ser precisa, general, legible y no ambigua. 
La especificación de un tipo define totalmente su comportamiento a cualquier usuario que lo 
necesite.

Implementación
•

La implementación de un TAD consiste en determinar una representación para los valores del 
tipo y en codificar sus operaciones a partir de esta representación, todo ello utilizando un 
lenguaje de programación. 
La implementación ha de ser estructurada, eficiente y legible. 
Una implementación del TAD es totalmente transparente a los usuarios del tipo y no se 
puede escribir hasta haber determinado claramente su especificación.

•
•

Tema 1. Tipos abstractos de datos ‐ Curso 2014/15

44

1.1 Especificación algebraica de TADs

•

•

Entre diversas propuestas que existen para especificar el comportamiento de las operaciones 
sobre un tipo de datos, vamos a considerar la conocida como especificación algebraica o 
ecuacional, que se basa en describir el comportamiento mediante ecuaciones, lo cual facilita 
el estilo habitual de razonamiento ecuacional, basado en sustituir iguales por iguales.

Una especificación algebraica consta fundamentalmente de tres componentes:

– Tipos: son nombres de conjuntos de valores. Entre ellos está el tipo principal del TAD, 

aunque puede haber también otros que se relacionen con este.

– Operaciones: son funciones con un perfil asociado que indica el tipo de cada uno de los 

argumentos y el tipo del resultado. En una especificación algebraica no se permiten 
funciones que devuelvan varios valores, ni tampoco procedimientos no funcionales.

– Ecuaciones: son igualdades entre términos formados con las operaciones y variables, y 

definen el comportamiento de las operaciones.

Tema 1. Tipos abstractos de datos ‐ Curso 2014/15

55

1.2 Signatura de un TAD

•

•

Definimos la signatura de un TAD como los tipos que utiliza junto con los nombres y perfiles 
de las operaciones.

Por ejemplo, para especificar el TAD de los booleanos utilizamos la siguiente signatura:

tipos bool
operaciones

cierto
falso

_ ∧ _
_ ∨ _

￢ _

→ bool
:
→ bool
:
: bool bool → bool
: bool bool → bool
→ bool
: bool

Tema 1. Tipos abstractos de datos ‐ Curso 2014/15

66

1.2 Signatura de un TAD

•

TAD de los booleanos y números naturales:

tipos bool, nat
operaciones

￢ _
cero
suc
suma
ig

cierto
falso

_ ∧ _
_ ∨ _

→ bool
:
→ bool
:
: bool bool → bool
: bool bool → bool
: bool
→ bool
→ nat
:
: nat
→ nat
: nat nat
→ nat
: nat nat → bool

Tema 1. Tipos abstractos de datos ‐ Curso 2014/15

77

1.3 Clasificación de las operaciones

•

•

Para escribir las ecuaciones es necesario clasificar las operaciones según el papel que 
queremos que jueguen en relación con el tipo principal s:

– Constructoras (o generadoras): devuelven un valor de tipo s. Pensadas para construir 

todos los valores de tipo s. Puede haber más de un subconjunto de operaciones 
constructoras, del que habrá que elegir uno.

– Modificadoras: devuelven también un valor de tipo s. Pero están pensadas para hacer 

cálculos que produzcan resultados de tipo s.

– Observadoras: devuelven un valor de un tipo diferente a s. Pensadas para obtener 

valores de otros tipos a partir de valores de tipo s.

Conjuntos de constructoras para bool y nat:
constr1(bool) = {cierto, falso}

constr2(bool) = {cierto, ￢ }

constr(nat) = {cero, suc}

Tema 1. Tipos abstractos de datos ‐ Curso 2014/15

88

1.4 Términos

•

•

Dada la signatura de un TAD y un conjunto de variables X con tipo, es posible construir el 
conjunto (generalmente infinito) de términos de tipo s mediante la aplicación de las 
operaciones del TAD. Cada termino representa una aplicación sucesiva de operaciones del 
TAD, y puede contener variables.

Tbool = {cierto, falso, (￢cierto) ∨ falso, ig(cero, suc(cero)), …}

Tbool (X) = {cierto, falso, ￢b, ig(n,m), …}

siendo X = {b : bool, n : nat, m : nat, …}

Tnat = {cero, suc(cero), suc(suc(cero)), suma(suc(cero), cero), …}

Un tipo especial de términos son aquellos que sólo contienen operaciones constructoras: son 
los términos construidos. Es necesario que las constructoras permitan generar al menos un 
término construido distinto para cada posible valor del tipo que se especifica.

bool = {cierto, falso}
bool = {cierto, ￢cierto, ￢￢cierto, …}

TC1
TC2
TCnat = {cero, sucn(cero)}, n ≥ 1

Tema 1. Tipos abstractos de datos ‐ Curso 2014/15

99

1.5 Ecuaciones

•

•

Son de la forma

t = t′

con t y t′ términos con variables Ts(X) para cierto tipo s.

Las ecuaciones deben reflejar el comportamiento de las operaciones para cualquier 
aplicación correcta de las mismas. Una operación está definida si las ecuaciones determinan 
su comportamiento respecto a todas las posibles combinaciones de valores que pueden 
tomar sus parámetros.

– Las ecuaciones deben permitir convertir cualquier término en un término construido: el 

resultado de la secuencia de operaciones que representa el término.

– Mediante las ecuaciones ha de ser posible deducir todas las equivalencias que son 
válidas entre los términos, es decir, identificar las secuencias de operaciones que 
producen el mismo resultado. Conviene evitar las ecuaciones redundantes.

Tema 1. Tipos abstractos de datos ‐ Curso 2014/15

1010

1.5 Ecuaciones

•

Ecuaciones para booleanos:

variables

b : bool
ecuaciones

cierto ∧ b = b
falso ∧ b = falso
cierto ∨ b = cierto
falso ∨ b = b
(￢cierto)∨ falso = falso ∨ falso = falso
cierto ∧ (cierto ∨ falso) = cierto ∧ cierto = cierto
cierto ∧ (cierto ∨ falso) = cierto ∨ falso = cierto

￢cierto = falso
￢falso = cierto

•

Usando las ecuaciones podemos convertir cualquier término en un término construido.

Tema 1. Tipos abstractos de datos ‐ Curso 2014/15

1111

Especificación de los booleanos

especificación BOOLEANOS
tipos bool
operaciones

{ Constructora }
{ Constructora }

→ bool
:
→ bool
:
: bool bool → bool
: bool bool → bool
→ bool
: bool

cierto
falso

_ ∧ _
_ ∨ _
cierto ∧ b = b
falso ∧ b = falso
cierto ∨ b = cierto
falso ∨ b = b

￢ _
variables

b : bool
ecuaciones

￢cierto = falso
￢falso = cierto

fespecificación

Tema 1. Tipos abstractos de datos ‐ Curso 2014/15

1212

1.6 Metodología de constructoras

•

•

Elección de un conjunto de operaciones como constructoras: operaciones que son suficientes 
para generar todos los valores del tipo y tales que la eliminación de cualquiera de ellas del 
conjunto impide construir alguno de los valores del tipo. Puede haber más de uno.

Aserción de las relaciones entre constructoras.
– El conjunto de operaciones constructoras puede o no ser libre. Se dice que las 

operaciones constructoras de un TAD son no libres si existen términos construidos 
diferentes que sean equivalentes entre sí. En caso contrario, se dice que las operaciones 
constructoras son libres.

– Si las constructoras son libres entonces no escribimos ninguna ecuación que las 
relacione; por el contrario, si las constructoras no son libres es necesario escribir 
ecuaciones que permitan determinar las equivalencias que nos interesen entre términos 
construidos. 
Por ejemplo: ￢￢b = b siendo b : bool

Tema 1. Tipos abstractos de datos ‐ Curso 2014/15

1313

1.6 Metodología de constructoras

•

Especificación del resto de operaciones, una a una, respecto a las constructoras.

– Definición de los efectos de aplicar las operaciones sobre términos formados 

exclusivamente por constructoras.

– Al especificar operaciones observadoras asegurar dos propiedades: consistencia y 

completitud suficiente. Si se ponen ecuaciones de más, se pueden igualar términos que 
son diferentes en el tipo correspondiente, mientras que si se ponen de menos, se puede 
generar un número indeterminado (posiblemente infinito) de nuevos valores, diferentes 
a los ya existentes.

Tema 1. Tipos abstractos de datos ‐ Curso 2014/15

1414

Especificación de los naturales

especificación NATURALES
usa BOOLEANOS
tipos nat
operaciones

cero
suc
_ + _, _ * _, _ - _
exp
_ == _, _ ≠ _

: → nat
: nat
→ nat
: nat nat → nat
: nat nat → nat
: nat nat → bool

{ Constructora }
{ Constructora }

variables

n,m : nat

Tema 1. Tipos abstractos de datos ‐ Curso 2014/15

1515

Especificación de los naturales

ecuaciones

cero + m =   m
suc(n) + m =   suc(n + m)
cero * m =   cero
suc(n) * m =   (n * m) + m
cero − m =   cero
suc(n) − cero      =   suc(n)
suc(n) − suc(m)  =   n − m
exp(n, cero)        =   suc(cero)

exp(n, suc(m))    =   n∗ exp(n,m)

{ Al restar a un número otro mayor el resultado que se obtiene es cero }

cero == cero        =   cier