PDF de programación - Tema 2. Introducción a los TADs. Los tipos lineales

DLSI (Univ. Alicante)

Tema 2. Introducción. Los tipos lineales

Introducción a los TADs. Los tipos lineales

TEMA 2

PROGRAMACIÓN Y ESTRUCTURAS DE

DATOS

DLSI (Univ. Alicante)

Tema 2. Introducción. Los tipos lineales

Introducción. Los tipos lineales

1. Introducción a los TADs
2. Vectores
3. Listas
4. Pilas
5. Colas

2

1

DLSI (Univ. Alicante)

Tema 2. Introducción. Los tipos lineales

1. Introducción a los TADs

TAD: Tipo Abstracto de Datos
Tipo de datos:

Clasifica los objetos de los programas (variables,
parámetros, constantes) y determina los valores que
pueden tomar
También determina las operaciones que se aplican

Entero: operaciones aritméticas enteras (suma, resta, …)
Booleano: operaciones lógicas (y, o, …)

Abstracto:

La manipulación de los datos sólo dependen del
comportamiento descrito en su especificación (qué hace)
y es independiente de su implementación (cómo se hace)
Una especificación Múltiples implementaciones

DLSI (Univ. Alicante)

Tema 2. Introducción. Los tipos lineales

1. Introducción a los TADs

Especificación de un TAD:

Consiste en establecer las propiedades que lo definen
Para que sea útil debe ser:

Precisa: sólo produzca lo imprescindible
General: sea adaptable a diferentes contextos
Legible: sea un comunicador entre especificador e implementador
No ambigua: evite problemas de interpretación

Definición informal (lenguaje natural) o formal (algebraica)

3

4

2

DLSI (Univ. Alicante)

Tema 2. Introducción. Los tipos lineales

1. Introducción a los TADs

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
Para que sea útil debe ser:

Estructurada: facilita su desarrollo
Eficiente: optimiza el uso de recursos Evaluación de distintas
soluciones mediante la complejidad (espacial y temporal)
Legible: facilita su modificación y mantenimiento

5

DLSI (Univ. Alicante)

Tema 2. Introducción. Los tipos lineales

1. Introducción a los TADs
ESPECIFICACIÓN ALGEBRAICA (I)

Especificación algebraica (ecuacional): establece las
propiedades de un TAD mediante ecuaciones con variables
cuantificadas universalmente, de manera que las propiedades
dadas se cumplen para cualquier valor que tomen las
variables
Pasos:

Identificación de los objetos del TAD y sus operaciones
(declaración del TAD, módulos que usa, parámetros)
Definición de la signatura (sintaxis) de un TAD (nombre del
TAD y perfil de las operaciones)
Definición de la semántica (significado de las operaciones)

Operación: es una función que toma como parámetros
(entrada) cero o más valores de diversos tipos, y produce
como resultado un solo valor de otro tipo. El caso de cero
parámetros representa una constante del tipo de resultado

6

3

DLSI (Univ. Alicante)

Tema 2. Introducción. Los tipos lineales

1. Introducción a los TADs
ESPECIFICACIÓN ALGEBRAICA (II)

MODULO …

USA …
PARAMETRO TIPO …

OPERACIONES

…
…

FPARAMETRO
TIPO (GÉNERO) …
OPERACIONES

…
…

FMODULO

DLSI (Univ. Alicante)

1. Introducción a los TADs
ESPECIFICACIÓN ALGEBRAICA (III)

Tema 2. Introducción. Los tipos lineales

MODULO NATURAL1

TIPO natural
OPERACIONES

cero : natural
suc : natural natural

FMODULO

Mediante aplicación sucesiva de cero y suc se obtienen los

distintos valores del tipo:

cero, suc(cero), suc(suc(cero)), …

7

8

4

DLSI (Univ. Alicante)

1. Introducción a los TADs
ESPECIFICACIÓN ALGEBRAICA (IV)

Tema 2. Introducción. Los tipos lineales

MODULO NATURAL2

TIPO natural
OPERACIONES

cero : natural
suc : natural natural
suma : natural natural natural

FMODULO

¿suma(cero, suc(cero)) y suc(cero) denotan valores distintos?

¿ suma(cero, suc(cero)) y suma(suc(cero), cero) denotan el mismo

valor?

9

DLSI (Univ. Alicante)

Tema 2. Introducción. Los tipos lineales

1. Introducción a los TADs
ESPECIFICACIÓN ALGEBRAICA (V)

Solución:

Utilización de ecuaciones de la forma t1 = t2, donde t1 y t2 son
términos sintácticamente correctos del mismo tipo
Semánticamente, expresa que el valor construido mediante el
término t1 es el mismo que el valor construido mediante el
término t2
Para no tener que escribir infinitas ecuaciones, se admite que
los términos que aparecen en una ecuación tengan variables

10

5

DLSI (Univ. Alicante)

1. Introducción a los TADs
ESPECIFICACIÓN ALGEBRAICA (VI)

Tema 2. Introducción. Los tipos lineales

MODULO NATURAL3

TIPO natural
OPERACIONES

cero : natural
suc : natural natural
suma : natural natural natural

VAR

x, y: natural
ECUACIONES

suma(x, cero) = x
suma(cero, x) = x
suma(x, suc(y)) = suc(suma(x, y))

FMODULO

11

DLSI (Univ. Alicante)

Tema 2. Introducción. Los tipos lineales

1. Introducción a los TADs

EJERCICIOS

Sea el conjunto de los números naturales con las operaciones cero
y suc. Define la sintaxis y la semántica de las operaciones “==“ y
“<=“ que permiten realizar una ordenación de los elementos del
conjunto

12

6

DLSI (Univ. Alicante)

Tema 2. Introducción. Los tipos lineales

1. Introducción a los TADs

EJERCICIOS

Completa en esta misma hoja las ecuaciones que aparecen a
continuación y que expresan el comportamiento de las operaciones
de: resta en el conjunto de los números Naturales en el que sólo
existen las operaciones cero: →natural y la operación suc:
natural →natural (devuelve el sucesor de un número Natural). Se
asume que el primer operando de la resta es siempre mayor o igual
que el segundo.

resta(natural,natural) →natural
resta( , ) = ..................................................
resta(
) = ..................................................

,

13

DLSI (Univ. Alicante)

1. Introducción a los TADs
ESPECIFICACIÓN ALGEBRAICA (VII)

Tema 2. Introducción. Los tipos lineales

¿Cómo podemos estar seguros de que no son necesarias más
ecuaciones?
Propiedades importantes: consistencia y completitud

Si se ponen ecuaciones de más, se pueden igualar términos
que están en clases de equivalencia diferentes, mientras que
si se ponen de menos, se puede generar un número
indeterminado de términos incongruentes con los
representantes de las clases existentes

14

7

DLSI (Univ. Alicante)

Tema 2. Introducción. Los tipos lineales

1. Introducción a los TADs
ESPECIFICACIÓN ALGEBRAICA (VIII)

Clasificación de las operaciones:

Constructoras: devuelven un valor del tipo

Generadoras: permiten generar, por aplicaciones sucesivas, todos los
valores del TAD a especificar
Modificadoras: el resto

Consultoras: devuelven un valor de un tipo diferente

En general, las operaciones modificadoras y consultoras se
especifican en términos de las generadoras. En ocasiones, una
operación modificadora puede especificarse en términos de
otras modificadoras o consultoras. Diremos que se trata de
una operación derivada

15

DLSI (Univ. Alicante)

1. Introducción a los TADs
ESPECIFICACIÓN ALGEBRAICA (IX)

Tema 2. Introducción. Los tipos lineales

Ecuación condicional: es equivalente a un conjunto finito de
ecuaciones no condicionales

si (n1 <> n2) entonces

saca(añade(s, n1), n2) = añade(saca(s, n2), n1)

sino

saca(añade(s, n1), n2) = saca(s, n2)

fsi

16

8

DLSI (Univ. Alicante)

Tema 2. Introducción. Los tipos lineales

1. Introducción a los TADs
ESPECIFICACIÓN ALGEBRAICA (X)

Operaciones auxiliares: se introducen en una especificación
para facilitar su escritura y legibilidad. Son invisibles para los
usuarios del TAD (también se les llama ocultas o privadas)

17

DLSI (Univ. Alicante)

1. Introducción a los TADs
ESPECIFICACIÓN ALGEBRAICA (XI)

Tema 2. Introducción. Los tipos lineales

Tratamiento de errores: puede ocurrir que alguna operación sea una función parcial (no se
puede aplicar sobre ciertos valores del dominio de los datos)

MODULO NATURAL4

TIPO natural
OPERACIONES

cero : natural
suc, pred : natural natural
suma, mult : natural natural natural

VAR x, y: natural;
ECUACIONES

suma(cero, x) = x
suma(x, cero) = x
suma(x, suc(y)) = suc(suma(x, y))
mult(cero, x) = cero
mult(x, cero) = cero
mult(suc(y), x) = suma(mult(y, x), x)
pred(suc(x)) = x

FMODULO

¿Cuánto vale pred(cero)?

18

9

DLSI (Univ. Alicante)

1. Introducción a los TADs
ESPECIFICACIÓN ALGEBRAICA (XII)

Tema 2. Introducción. Los tipos lineales

Tratamiento de errores:

Se añade una constate a la signatura que modeliza un valor
de error: errornat natural
Se añade una ecuación que completa la especificación de
pred: pred(cero) = errornat
Se supondrá que los valores sobre los que se aplica una
operación en una ecuación normal están libres de error

19

DLSI (Univ. Alicante)

Tema 2. Introducción. Los tipos lineales

1. Introducción a los TADs

IMPLEMENTACIÓN (I)

Dada una especificación de un tipo, se pueden construir
diversas implementaciones
Cada implementación se define en un módulo diferente,
llamado módulo de implementación
La construcción de estos módulos consta de dos fases:

Elección de una representación para los diferentes tipos
definidos en la especificación
Codificación de las operaciones en términos de la
representación elegida

20

10

DLSI (Univ. Alicante)

Tema 2. Introducción. Los tipos lineales

1. Introducción a los TADs

IMPLEMENTACIÓN (II)

Mecanismos de abstracción en los lenguajes de programación:

Encapsulamiento de la representación del TAD
Ocultación de la información, para limitar las operaciones
posibles sobre el TAD
Genericidad, para lograr implementaciones genéricas válidas
para distintos tipos
Herencia, para reutilizar implementaciones

Los lenguajes de programación tradicionales (Fortran, Basic,
Pascal, C) resultan ineficientes para utilizar los mecanismos
de abstracción
Es necesario emplear lenguajes modernos (ADA, C++, Java,
C#)

21

DLSI (Univ. Alicante)

Tema 2. Introducción. Los tipos lineales

2. Vectores

Un vector es un conjunto ordenado de pares <índice, valor>. Para