tipos de datos abstractos
Upload: instituto-universitario-de-tecnologia-dr-federico-rivero-palacio
Post on 28-Jun-2015
6.377 views
DESCRIPTION
Esta presentación explica sobre la definición y los conceptos básicos, especificación sintáctica, especificación semántica e implementación de los Tipos de datos abstractos (TDA)TRANSCRIPT
CONTENIDO: Introducción Historia Definición y Conceptos Básicos Especificación Sintáctica Especificación Semántica Representación Implementación
13/04/23 Marbella Castañeda 2
Historia
El origen del concepto de tipo de dato abstracto se remonta al tipo class en el lenguaje SIMULA 67 (Birtwistle et al. 1973).
Desde entonces se han desarrollado varios lenguajes que
manejan tipos de datos abstractos:
En 1977 Liskov lo introduce para el Lenguaje CLU.llina
En 1982 Stroustrup lo incorpora para el lenguaje C (C con clases)
13/04/23 Marbella Castañeda 3
Definición y Conceptos Básicos
1. Aho, Hopcroft y Ullman (1988) señalan que un TDA se entiende como “un modelo matemático con una serie de operaciones definidas en ese modelo”.
2. Guttag (1977) expresa que un TDA es “Una clase de objetos definida por una especificación independiente de la representación”.
3. Liskop (1974) establece que “Un TDA define una clase de objetos abstractos la cual está completamente caracterizada por las operaciones definidas para estos objetos”.
13/04/23 Marbella Castañeda 4
Definición y Conceptos Básicos
Caracterización:
Los TDA son generalizaciones de los tipos de datos primitivos (enteros,
reales, etc), al igual que los procedimientos y funciones son
generalizaciones de operaciones primitivas (suma, resta, etc).
Un TDA se caracteriza por un conjunto de operaciones las cuales
representan el comportamiento del TDA.
El TDA permite crear nuevos tipos de abstracciones de datos que están
presentes implícitamente o explícitamente en el dominio del problema, y
que no son provistos por el lenguaje.
13/04/23 Marbella Castañeda 5
Definición y Conceptos Básicos
Para crear los nuevos tipos de abstracciones es necesario
13/04/23 Marbella Castañeda 6
1
Definir objetos y las operaciones válidas
Elegir la representación concreta del objeto abstracto en término de las estructuras o tipos de datos presentes en los lenguajes de alto nivel
2 3
Desarrollar los algoritmos para las operaciones, basándose en la representación seleccionada.
Crear nuevos tipos de abstracciones.
A través de las especificaciones Sintácticas y Semántica se
describen los objetos abstractos y las operaciones abstractas del
tipo que se crea. La representación e implementación, requiere
de la elección de las estructuras de datos provistas por el
lenguaje y del desarrollo – codificación de los procedimientos y/o
funciones.
13/04/23 Marbella Castañeda 7
Especificación Sintáctica y Semántica
Para definir los objetos abstractos y sus propiedades (operaciones) se describe
el tipo de dato independientemente de cualquier representación e
implementación.
Para ello es necesario definir el TDA en términos de su especificación sintáctica
y semántica:
1. La especificación sintáctica define el nombre de los objetos abstractos
y de las operaciones indicando para cada una de ellas el dominio y el rango.
2. La especificación semántica define el significado de cada operación usando
los símbolos introducidos en la parte sintáctica.
13/04/23 Marbella Castañeda 8
1
Especificación Sintáctica y Semántica
La Especificación Semántica puede ser especificada tanto de
modo formal o informal. La primera generalmente es
rigurosamente formulada y fundamentada bajo la simbología
matemática. La segunda puede especificarse en un lenguaje
natural.
13/04/23 Marbella Castañeda 9
Representación Interna
La representación interna para los objetos del TDA, se especifica
en términos de las estructuras de datos provistas por los
lenguajes de programación. Un TDA puede tener diversas
representaciones, las cuales deben cumplir con la especificación
definida para el tipo.
13/04/23 10
2
Marbella Castañeda
Implementación
Esta implica el desarrollo - codificación de los procedimientos o
funciones, basándose en la representación seleccionada.
13/04/23 Marbella Castañeda 11
3
Ejemplo
El tipo SECUENCIA es un tipo estructurado formado por componentes de
un mismo tipo, Si e es del tipo de los ELEMENTOS de SECUENCIA
entonces la misma será tratada como una SECUENCIA de e.
ELEMENTOS puede ser un tipo ENTERO, CARACTER, LÓGICOS.
13/04/23 Marbella Castañeda 12
Especificación Sintáctica DOMINIO
RANGOPRIMERO : SECUENCIA ELEMENTOÚLTIMO : SECUENCIA ELEMENTOPONERPRI : SECUENCIA x ELEMENTO SECUENCIAPONERULT: SECUENCIA x ELEMENTO SECUENCIALONGITUD: SECUENCIA ENTEROMAYOR: SECUENCIA x SECUENCIA SECUENCIAMENOR: SECUENCIA x SECUENCIA SECUENCIAOBTENER: SECUENCIA x POSICIÓN ELEMENTO
13/04/23 Marbella Castañeda 13
Especificación Semántica
Función PRIMERO (S :SECUENCIA) : ELEMENTO
precondición: ninguna
postcondición: e1 o Fin (S)
acción: si S = (e1,e2,…,en) entonces PRIMERO = e1
sino PRIMERO = Fin (S)
13/04/23 Marbella Castañeda 14
Especificación Semántica
Función ULTIMO (S :SECUENCIA) : ELEMENTO
precondición: ninguna
postcondición: en o Fin (S)
acción: si S = (e1,e2,…,en) entonces ULTIMO = en
sino ULTIMO = Fin (S)
13/04/23 Marbella Castañeda 15
Especificación Semántica
Procedimiento PONERPRI (Var S :SECUENCIA, E: ELEMENTO)
precondición: ninguna
postcondición: S = (e1) o S = (e1,e2, e3,…,en)
acción: si S = ( ) entonces S = (e1)
sino Si S = (e2, e3,…,en) entonces S = (e1,e2,
e3,…,en)
13/04/23 Marbella Castañeda 16
Especificación Semántica
Procedimiento PONERULT (Var S :SECUENCIA, E: ELEMENTO)
precondición: ninguna
postcondición: S = (en) o S = (e1,e2, e3,…,en)
acción: si S = (en) entonces S = (en)
sino Si S = (e1,e2, e3,…,en-1) entonces S =
(e1,e2, e3,…,en-1,en)
13/04/23 Marbella Castañeda 17
Especificación Semántica
Función LONGITUD (S :SECUENCIA) : ENTERO
precondición: ninguna
postcondición: LONGITUD (S)
acción: si S = ( ) entonces LONGITUD = 0
sino Si S = (e1,e2,…,en) LONGITUD = n
13/04/23 Marbella Castañeda 18
Especificación Semántica
Función MAYOR (S1, S2 :SECUENCIA) : SECUENCIA
precondición: ninguna
postcondición: MAYOR = S1 o MAYOR = S2
acción: si LONGITUD (S1) > LONGITUD (S2) entonces
MAYOR := S1;
si LONGITUD (S2) > LONGITUD (S1) entonces
MAYOR := S2;
13/04/23 Marbella Castañeda 19
Especificación Semántica
Función MENOR (S1, S2 :SECUENCIA) : SECUENCIA
precondición: ninguna
postcondición: MENOR = S1 o MENOR = S2
acción: si LONGITUD (S1) < LONGITUD (S2) entonces
MENOR := S1;
si LONGITUD (S2) < LONGITUD (S1) entonces
MENOR := S2;
13/04/23 Marbella Castañeda 20
Especificación Semántica
Función OBTENER (S :SECUENCIA, P : POSICIÓN) : ELEMENTO
precondición: S < > ( )
postcondición: P tiene la posición del elemento ep en la
Secuencia S
acción: si S = (e1,e2,…ep,..en) entonces OBTENER = ep
13/04/23 Marbella Castañeda 21
Representación Interna
Seleccionemos una estructura de datos existentes en los lenguajes de
programación que nos permita simular una SECUENCIA. Asumamos que
los ELEMENTOS que contiene la SECUENCIA son representados por letras
del alfabeto (mayúsculas y minúsculas), dígitos y caracteres especiales.
Por lo que el tipo debe ser CARACTER y la cantidad de ELEMENTOS que
puede contener la SECUENCIA tiene un máximo de n ELEMENTOS.
Por lo que la representación formal de este tipo se define de la siguiente manera:
TipoSECUENCIA = arreglo [1..n] de CARACTER;
VarS SECUENCIA;
13/04/23 Marbella Castañeda 22
Representación Gráfica
Gráficamente podríamos ver la SECUENCIA S de esta forma:
POSICIÓN
1 2 n – 1 n
13/04/23 Marbella Castañeda 23
…
e1: ELEMENTO : CARACTER
Implementación
Función PRIMERO (S :SECUENCIA) : ELEMENTO
vare : CARÁCTER;
principiosi S[1] <> “” entonces e : = S [1]sino
e : = “”PRIMERO := e;
fin;
Implementación
Función ULTIMO(S :SECUENCIA) : ELEMENTO
vari : ENTERO;
principioi .= 1;mientras (i <= n) y (S[ i ] <> “”) hacerprincipio
i := i + 1;fin;ULTIMO := S[ i – 1];
fin;
13/04/23 Marbella Castañeda 24
Implementación
Procedimiento PONERPRI (Var S :SECUENCIA; e: ELEMENTO)
vari : entero;
principioi := n;mientras (i > 0) hacerprincipio
S[ i ]:= S [ i – 1];i := i – 1;
fin;S [ 1 ] := e;
fin;
ImplementaciónProcedimiento PONERULT (Var
S :SECUENCIA; e: ELEMENTO)var
i : entero;principio
i := 1;mientras ( i < = n) y (S[ i ] < > “”) hacerprincipio
i := i + 1;fin;S[ i ] := e;
fin;
13/04/23 Marbella Castañeda 25
Implementación
Función LONGITUD (S :SECUENCIA) : ENTERO
vari : ENTERO;
principioi:=1;mientras (i <= n) y (S [ i ] < > “”) hacerprincipio
i:= i + 1;fin;si i = n y S[ i ] <> “” entonces
LONGITUD := i;sino
LONGITUD := i -1;fin;
ImplementaciónFunción MAYOR (S1, S2 :SECUENCIA) :
SECUENCIAprincipio
si LONGITUD (S1) >= LONGITUD (S2) entonces MAYOR := S1sino
MAYOR := S2fin;
13/04/23 Marbella Castañeda 26
Implementación
Función MENOR (S1, S2 :SECUENCIA) : SECUENCIA
principiosi LONGITUD (S1) <= LONGITUD (S2) entonces MENOR := S1sino
MENOR := S2fin;
13/04/23 27Marbella Castañeda
ReferenciasAho A., Hopcroft J., Ullman J (1988). Estructura de Datos y
Algoritmos. Addison Wesley Iberoamericana, Delaware, USA
Liskov, B. (1974). Programing with Abstract Data Types. ACM. Sygplan. Vol 9 – 4.
Zambrano, N. y Sepúlveda, J. (1988). Tipos De Datos Y
Estructuras De Datos Fondo editorial acta científica venezolana. Universidad Central de Venezuela.
13/04/23 Marbella Castañeda 28