tipos de datos abstractos tda -...

Tipos de Datos Abstractos TDA

Tipos de Datos Abstractos

FUERTE BALDERRAMA URIEL 1


O 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:

O En 1977 Liskov lo introduce para el Lenguaje CLU.llina

O En 1982 Stroustrup lo incorpora para el lenguaje C (C con clases)

27/06/2013 FUERTE BALDERRAMA URIEL 2


O Definición y Conceptos Básicos 1. Liskop establece que “Un TDA define una clase de objetos

abstractos la cual está completamente caracterizada por las operaciones definidas para estos objetos”.

2. Guttag expresa que un TDA es “Una clase de objetos definida por una especificación independiente de la representación”.

3. Aho, Hopcroft y Ullman señalan que un TDA se entiende como “un modelo matemático con una serie de operaciones definidas en ese modelo”.



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.



O Definición y Conceptos Básicos Para crear los nuevos tipos de abstracciones es

necesario


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.



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.


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.



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.


2


Implementación Esta implica el desarrollo - codificación de los

procedimientos o funciones, basándose en la

representación seleccionada.


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.



Especificación Sintáctica DOMINIO RANGO PRIMERO : SECUENCIA ELEMENTO ÚLTIMO : SECUENCIA ELEMENTO PONERPRI : SECUENCIA x ELEMENTO SECUENCIA PONERULT: SECUENCIA x ELEMENTO SECUENCIA LONGITUD: SECUENCIA ENTERO MAYOR: SECUENCIA x SECUENCIA SECUENCIA MENOR: SECUENCIA x SECUENCIA SECUENCIA OBTENER: SECUENCIA x POSICIÓN ELEMENTO



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,…, e n) entonces PRIMERO = e1

sino PRIMERO = Fin (S) if S =(e1,e2,…, e n) then PRIMERO = e1 else PRIMERO = Fin (S)



Especificación Semántica Función ULTIMO (S :SECUENCIA) : ELEMENTO


postcondición: en o Fin (S)

acción: si S = (e1,e2,…, e n) entonces ULTIMO = e n

sino ULTIMO = Fin (S) if S =(e1,e2,…, e n) then ULTIMO = e n else ULTIMO = Fin (S)



O Especificación Semántica Procedimiento PONERPRI (Var S :SECUENCIA, E: ELEMENTO)


postcondición: S = (e1) o S = (e1,e2, e3,…,en)

acción: si S = ( ) entonces S = (e1)

sino Si S = (e2, e3,…,e n) entonces S = (e1,e2, e3,…, e n)

if S =( ) then S = e1 else if S = (e2, e3,…, e n) then S = (e1,e2,e3,…, e n) 27/06/2013 FUERTE BALDERRAMA URIEL 15


Especificación Semántica Procedimiento PONERULT (Var S :SECUENCIA, E: ELEMENTO)


postcondición: S = (en) o S = (e1,e2, e3,…,e n)

acción: si S = (e n) entonces S = (e n)

sino Si S = (e1,e2, e3,…,en-1) entonces S = (e1,e2, e3,…,en-1,en)

if S =(e n) then S = (e1,e2, e3,…,e n) else if S = (e1,e2, e3,…,e-1) then S = (e1,e2, e3,…, e n -1,e n)



Especificación Semántica Función LONGITUD (S :SECUENCIA) : ENTERO


postcondición: LONGITUD (S)

acción: si S = ( ) entonces LONGITUD = 0

sino Si S = (e1,e2,…,en) LONGITUD = n

if S =( ) LONGITUD = o else if S = (e1,e2,…,en) LONGITUD = n



Especificación Semántica Función MAYOR (S1, S2 :SECUENCIA) : SECUENCIA


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;



Especificación Semántica Función MENOR (S1, S2 :SECUENCIA) : SECUENCIA


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;



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



O 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: Tipo SECUENCIA = arreglo [1..n] de CARACTER; Var S SECUENCIA;



O Representación Gráfica Gráficamente podríamos ver la SECUENCIA S de esta forma:

POSICIÓN 1 2 n –

1 n


…

e1: ELEMENTO : CARACTER



O Implementación Función PRIMERO (S :SECUENCIA) :

ELEMENTO var e : CARÁCTER; principio si S[1] <> “” entonces e : = S [1] sino e : = “” PRIMERO := e; fin;

O Implementación Función ULTIMO(S :SECUENCIA) : ELEMENTO var i : ENTERO; principio i .= 1; mientras (i <= n) y (S[ i ] <> “”) hacer principio i := i + 1; fin; ULTIMO := S[ i – 1]; fin;



Implementación Procedimiento PONERPRI (Var S

:SECUENCIA; e: ELEMENTO) var i : entero; principio i := n; mientras (i > 0) hacer principio S[ i ]:= S [ i – 1]; i := i – 1; fin; S [ 1 ] := e; fin;

Implementación

Procedimiento PONERULT (Var S :SECUENCIA; e: ELEMENTO)

var i : entero; principio i := 1; mientras ( i < = n) y (S[ i ] < >

“”) hacer principio i := i + 1; fin; S[ i ] := e; fin;



Implementación Función LONGITUD (S :SECUENCIA) : ENTERO var i : ENTERO; principio i:=1; mientras (i <= n) y (S [ i ] < > “”) hacer principio i:= i + 1; fin; si i = n y S[ i ] <> “” entonces LONGITUD := i; sino LONGITUD := i -1; fin;

Implementación

Función MAYOR (S1, S2 :SECUENCIA) : SECUENCIA

principio si LONGITUD (S1) >=

LONGITUD (S2) entonces MAYOR := S1

sino MAYOR := S2 fin;



O Implementación

Función MENOR (S1, S2 :SECUENCIA) : SECUENCIA

principio si LONGITUD (S1) <= LONGITUD

(S2) entonces MENOR := S1 sino MENOR := S2 fin;


Referencias

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

FUER

TE B

ALD

ERR

AMA

UR

IEL

27

tipos de datos abstractos tda -...

Documents