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)
Abstracciones, tipos y mecanismos.
TIPOS DE ABSTRACCIONES
Abstraccionesfuncionales
Abstracciones de datos
Abstraccionesde iteradores
Rutinas, funciones, procedimientos
Tipos Abstractos deDatos (TAD)
Iteradores
TIPO ABSTRACTO DE DATOS:
TIPO DE DATOS:
ESTRUCTURA DE DATOS:
Dominio abstracto de valores junto con las operaciones aplicables sobre el mismo.
Conjunto de valores que puede tomar una variable, un parámetro o una expresión.
Disposición en memoria de los datos necesarios para almacenar valores de un tipo.
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.
La evolución de los lenguajes de programación tiende a introducir cada vez más abstracciones.
Lenguajes
de bajo nivel
(Basic, Fortran, Ensamblador, …)
Lenguajes
estructurados
(Pascal, C,Modula, ADA, …)
Lenguajes
orientados a objetos
(Smalltalk, C++, Java, Eiffel, …)
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.
Pascal ObjectPascal
type
Pila = register
tope: integer;
datos: array [1..10] of integer;
end;
proc push (i: integer; var p:Pila);
proc pop (var p: Pila);
func top (p: Pila): integer;
type
Pila = class
private:
tope: integer;
datos: array [1..10] of integer;
public:
proc push (i: integer);
proc pop;
func top: integer;
end;
Pascal 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);
…
var
p1, p2: Pila;
i: integer;
begin
p1.push(10);
p1.push(20);
p1.pop;
i:= p1.top;
p1.tope:= 243;
i:= p1.top;
…
Error de compilación:
“tope” es privado
Especificaciones: Tipos de notaciones
Notaciones informales.
Notaciones formales.
Algebraicas (o axiomáticas).
Operacionales (o constructivas).
Especificaciones informales.
Notación
Operación (ent : ; : , …, sal )
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.
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.
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 …
Ejemplo de especificación informal de funciones:
Abstracciones de datos.
Notación
TAD es
Descripción
Descripción textual del tipo
Operaciones
Especificación informal de las operaciones de la lista anterior
Fin .
Página siguiente  |