PDF de programación - Programa de teoría Parte I. Estructuras de Datos

Programa de teoría

Parte I. Estructuras de Datos.

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

Parte 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.

Tema 1. Abstracciones y especificaciones.

1

PARTE 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.

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.

Tema 1. Abstracciones y especificaciones.

3

1.1. Abstracciones, tipos y mecanismos.

MECANISMOS DE ABSTRACCIÓN

Abstracción por especificación: Sólo

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.

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.

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.

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

• Estructura de datos: Representación

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

A.E.D.

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.

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.

A.E.D.

Tema 1. Abstracciones y especificaciones.

9

1.1. Abstracciones, tipos y mecanismos.
Pascal
type
Pila = register
tope: integer;
datos: array [1..10] of integer;

ObjectPascal

type
Pila = class
private:
tope: integer;
datos: array [1..10] of integer;
public:
proc push (i: integer);
proc pop;
func top: integer;

end;

proc push (i: integer; var p:Pila);
proc pop (var p: Pila);
func top (p: Pila): integer;

end;

A.E.D.

Tema 1. Abstracciones y especificaciones.

10

5

1.1. Abstracciones, tipos y mecanismos
Pascal
var
p1, p2: Pila;
i: integer;

ObjectPascal
var
p1, p2: Pila;
i: integer;

begin
push(10, p1);
push(20, p1);
pop(p1);
i:= top(p1);
p1.tope:= 243;
i:= top(p1);
…

begin
p1.push(10);
p1.push(20);
p1.pop;
i:= p1.top;
p1.tope:= 243;
i:= p1.top;
…

A.E.D.

Tema 1. Abstracciones y especificaciones.

Error de
compilación:
“tope” es
privado
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.

Tema 1. Abstracciones y especificaciones.

12

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.

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.

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.

Tema 1. Abstracciones y especificaciones.

15

1.2.1. Abstracciones funcionales.

• Ejemplo de especificación informal de funciones:

Especificación OpenCV

Nombre de
la operación

Descripción
corta
Sintaxis

Explicación de
los parámetros

Descripción
detallada

A.E.D.

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.

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.

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.

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.

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

Descripción

Operaciones

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)

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

...

…

…

…
Fin Conjunto.

A.E.D.

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.

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;
Pila (int maximo);
Push (T valor);
T Pop ();

public:

}

A.E.D.

Tema 1. Abstracciones y especificaciones.

23

1.2. Especificaciones informales.
1.2.3. Abstracciones de iteradores.

• Ejemplo: Sobre el TAD CjtoEnteros queremos añadir

operaciones para calcular la suma, el producto, ...

Operación suma_conj (ent c: CjtoEnteros; sal entero)
Calcula: Devuelve la suma de los elementos de c.
....

Ope