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 |