PDF de programación - Abstracciones y especificaciones - Estructura de datos

Programa de teoría
AED I. Estructuras de Datos.

1. Abstracciones y especificaciones.
2. Conjuntos y diccionarios.
3. Representación de conjuntos mediante árboles.
4. Grafos.

AED II. Algorítmica.

1. Análisis de algoritmos.
2. Divide y vencerás.
3. Algoritmos voraces.
4. Programación dinámica.
5. Backtracking.
6. Ramificación y poda.

A.E.D. I

Tema 1. Abstracciones y especificaciones.

1

AED I: ESTRUCTURAS DE DATOS
Tema 1. Abstracciones y

Especificaciones.

1.1. Abstracciones, tipos y mecanismos.
1.2. Especificaciones informales.
1.3. Especificaciones formales.

1.3.1. Método axiomático (o algebraico).
1.3.2. Método constructivo (u operacional).

A.E.D. I

Tema 1. Abstracciones y especificaciones.

2

1

1.1. Abstracciones, tipos y mecanismos.

procedure ordenar(a: array;

var b: array);

type persona;

class pila;

Abstraer: Eliminar lo irrelevante y quedarnos con lo

realmente importante.
¿Qué es lo importante?

A.E.D. I

Tema 1. Abstracciones y especificaciones.

3

1.1. Abstracciones, tipos y mecanismos.

MECANISMOS DE ABSTRACCIÓN

Abstracción por especificación: Solo

necesitamos conocer qué va a hacer el
procedimiento y no cómo funciona.
(Encapsulación y ocultación de implement.)

Abstracción por parametrización: Un

algoritmo, un tipo, o una variable se definen
en base a unos parámetros.
(Genericidad)

A.E.D. I

Tema 1. Abstracciones y especificaciones.

4

2

1.1. Abstracciones, tipos y mecanismos.
TIPOS DE ABSTRACCIONES
• Abstracciones

Rutinas, funciones,
procedimientos

funcionales

• Abstracciones

de datos

Tipos Abstractos de
Datos (TAD)

• Abstracciones
de iteradores

Iteradores

A.E.D. I

Tema 1. Abstracciones y especificaciones.

5

1.1. Abstracciones, tipos y mecanismos.
TIPO ABSTRACTO DE DATOS:
Dominio abstracto de valores junto con las
operaciones aplicables sobre el mismo.
TIPO DE DATOS:
Conjunto de valores que puede tomar una
variable, un parámetro o una expresión.
ESTRUCTURA DE DATOS:
Disposición en memoria de los datos
necesarios para almacenar valores de un
tipo.

A.E.D. I

Tema 1. Abstracciones y especificaciones.

6

3

1.1. Abstracciones, tipos y mecanismos.

Ejemplos

• TAD: Enteros
• Tipo de datos: Tipo integer de Pascal, o

tipo int de C/C++

• Estructura de datos: Representación

mediante enteros de 16 bits, 32 bits, listas
de dígitos (enteros largos), etc.

A.E.D. I

Tema 1. Abstracciones y especificaciones.

7

1.1. Abstracciones, tipos y mecanismos

• La evolución de los lenguajes de

programación tiende a introducir cada vez
más abstracciones.

Lenguajes
de bajo nivel

Lenguajes

Lenguajes

estructurados

orientados a objetos

(Basic, Fortran,
Ensamblador, …)

(Pascal, C,

Modula, ADA, …)

(Smalltalk, C++,
Java, Eiffel, …)

A.E.D. I

Tema 1. Abstracciones y especificaciones.

8

4

1.1. Abstracciones, tipos y mecanismos

• La evolución de los lenguajes de

programación tiende a introducir cada vez
más abstracciones.

• Soporte de TAD:

– Lenguajes estructurados (tipos definidos
por el usuario): Los datos y las operaciones
van aparte.

– Lenguajes orientados a objetos (clases):
Los datos y las operaciones constituyen una
unidad, el concepto de clase.

A.E.D. I

Tema 1. Abstracciones y especificaciones.

9

1.1. Abstracciones, tipos y mecanismos.
C
struct Pila {
int tope;
int datos[10];

class Pila {

C++

private:

Pila
datos
34

tope

int tope;
int datos[10];

};

public:

void push (Pila *p, int valor);
void pop (Pila *p);
int top (Pila p);

void push (int valor);
void pop ( );
int top ( );

};

A.E.D. I

Tema 1. Abstracciones y especificaciones.

0

1

2

3

4

5

6

7

8

9

10

20

51

5

Pila p1, p2;
int i;

push(&p1, 34);
push(&p1, 20);
push(&p1, 51);
pop(&p1);
i= top(p1);
p1.tope= 243;
i= top(p1);
...

Error de
ejecución:
se sale del
array datos

Pila p1, p2;
int i;

p1.push(34);
p1.push(20);
p1.push(51);
p1.pop();
i= p1.top();
p1.tope= 243;
i= p1.top();
...

8

Error de
compilación:
tope es
privado

9

A.E.D. I

Tema 1. Abstracciones y especificaciones.

11

1.1. Abstracciones, tipos y mecanismos.

Especificaciones: Tipos de

notaciones

• Notaciones informales.
• Notaciones formales.

– Algebraicas (o axiomáticas).
– Operacionales (o constructivas).

A.E.D. I

Tema 1. Abstracciones y especificaciones.

12

1.1. Abstracciones, tipos y mecanismos.
C

C++

Pila
datos
34

tope

0

1

2

3

4

5

6

7

20

51

6

1.2. Especificaciones informales.

1.2.1. Abstracciones funcionales.

Notación

Operación <nombre> (ent <id>: <tipo>; <id>: <tipo>,

..., sal <tipo>)
Requiere: Establece restricciones de uso.
Modifica: Identifica los datos de entrada que se
modifican (si existe alguno).
Calcula: Descripción textual del comportamiento
de la operación.

A.E.D. I

Tema 1. Abstracciones y especificaciones.

13

1.2. Especificaciones informales.

1.2.1. Abstracciones funcionales.

Ejemplo 1: Eliminar la repetición en los elementos de un array.
Operación QuitarDuplic (ent a: array [entero])

Modifica: a
Calcula: Quita los elementos repetidos de a. El límite inferior

del array no varía, pero sí lo puede hacer el superior.

Ejemplo 2: Buscar un elemento en un array de enteros.
Operación Buscar (ent a: array [entero]; x: entero; sal i: entero)

Requiere: a debe estar ordenado de forma ascendente.
Calcula: Si x está en a, entonces i debe contener el valor del
índice de x tal que a[i] = x. Si x no está en a, entonces i =
sup+1, donde sup es el índice superior del array a.

A.E.D. I

Tema 1. Abstracciones y especificaciones.

14

7

1.2.1. Abstracciones funcionales.

Generalización: una operación está definida independiente-

mente de cual sea el tipo de sus parámetros.

Ejemplo 3: Eliminar la repetición en los elementos de un array.
Operación QuitarDuplic [T: tipo](ent a: array [T])

Requiere: T debe tener una operación de comparación

IgualQue(ent T, T; sal booleano).

Modifica: a
Calcula: Quita los elementos repetidos de a. El límite inferior

del array no varía, pero sí lo puede hacer el superior.

Ejemplo 4: Buscar un elemento en un array de enteros.
Operación Buscar [T: tipo](ent a: array [T]; x: T; sal i: entero)

Requiere: T debe tener dos operación de comparación

MenorQue(ent T, T; sal bool), Igual(ent T, T; sal bool).
a debe estar ordenado de forma ascendente.

Calcula: Si x está en a, entonces i debe contener ...

A.E.D. I

Tema 1. Abstracciones y especificaciones.

15

1.2.1. Abstracciones funcionales.
• Ejemplo de especificación informal de funciones:

Especificación de las librerías STL de C++: www.cplusplus.com

Nombre de la

operación
Sintaxis

Descripción
en lenguaje

natural

Parámetros

Valor
devuelto

Ejemplo de

uso

Orden de
complejidad

A.E.D. I

Tema 1. Abstracciones y especificaciones.

16

8

1.2. Especificaciones informales.

1.2.2. Abstracciones de datos.

Notación

TAD <nombre_tipo> es <lista_operaciones>

Descripción

Descripción textual del tipo

Operaciones

Especificación informal de las operaciones
de la lista anterior

Fin <nombre_tipo>.

A.E.D. I

Tema 1. Abstracciones y especificaciones.

17

1.2.2. Abstracciones de datos.

TAD CjtoEnteros es Vacío, Insertar, Suprimir, Miembro,

EsVacío, Unión, Intersección, Cardinalidad

Descripción

Los CjtoEnteros son conjuntos matemáticos modificables,
que almacenan valores enteros.

Operaciones

Operación Vacío (sal CjtoEnteros)

Calcula: Devuelve un conjunto de enteros vacío.
Operación Insertar (ent c: CjtoEnteros; x: entero)

Modifica: c.
Calcula: Añade x a los elementos de c. Después de la

inserción, el nuevo conjunto es c U {x}.

…

Fin CjtoEnteros.

A.E.D. I

Tema 1. Abstracciones y especificaciones.

18

9

1.2.2. Abstracciones de datos.

TAD ListaEnteros es Crear, Insertar, Primero, Ultimo, Cabeza,

Cola, EsVacío, Igual

Descripción

Las ListaEnteros son listas de enteros modificables. Las
listas se crean con las operaciones Crear e Insertar…

Operaciones

Operación Crear (sal ListaEnteros)

Calcula: Devuelve una lista de enteros vacía.

Operación Insertar (ent l: ListaEnteros; x: entero)

Modifica: l.
Calcula: Añade x a la lista l en la primera posición.

…

Fin ListaEnteros.

A.E.D. I

Tema 1. Abstracciones y especificaciones.

19

1.2.2. Abstracciones de datos.

• Generalización (parametrización de tipo): El

tipo se define en función de otro tipo pasado
como parámetro.

• Útil para definir tipos contenedores o

colecciones. P. ej. Listas, pilas, colas, arrays,
conjuntos, etc.

• En lugar de:
ListaEnteros
ListaCadenas
ListaReales
….

 Tenemos:

Lista[T]

• Instanciación: Lista[entero], Lista[cadena],…

A.E.D. I

Tema 1. Abstracciones y especificaciones.

20

10

1.2.2. Abstracciones de datos.

TAD Conjunto[T: tipo] es Vacío, Insertar, Suprimir, Miembro,

EsVacío, Unión, Intersección, Cardinalidad

Los Conjunto[T] son conjuntos matemáticos modificables,
que almacenan valores de tipo T.

Operación Vacío (sal Conjunto[T])

Operación Insertar (ent c: Conjunto[T]; x: T)

Operación Suprimir (ent c: Conjunto[T]; x: T)

Descripción

Operaciones

...

…

…

…
Fin Conjunto.

Operación Miembro (ent c: Conjunto[T]; x: T; sal booleano)

A.E.D. I

Tema 1. Abstracciones y especificaciones.

21

1.2.2. Abstracciones de datos.

TAD Lista[T] es Crear, Insertar, Primero, Ultimo, Cabeza,

Cola, EsVacío, Igual

Descripción

Las Lista[T] son listas modificables de valores de tipo T.
Las listas se crean con las operaciones Crear e Insertar...

Operaciones

Operación Crear (sal Lista[T])

…

Operación Insertar (ent l: Lista[T]; x: entero)

…

Operación Primero (ent l: Lista[T]; sal Lista[T])

…

Fin Lista.

A.E.D. I

Tema 1. Abstracciones y especificaciones.

22

11

1.2.2. Abstracciones de datos.

• En C++ es posible definir tipos parametrizados.
• Plantillas template:

template <class T>

class Pila {

private:

int tope;
int maxDatos;
T *datos;

public:

Pila (int maximo);
Push (T valor);
T Pop ();

};

A.E.D. I

Tema 1. Abstracciones y especificaciones.

23

1.2. Especificaciones informales.
1.2.3. Abstracciones de iteradores.

• Ejemplo: Sobre el TA