apuntes de programación y estructuras de datos ...pred/tads2.pdf•para resolver problemas de...

Apuntes de Programación y estructuras dedatos. Abstracción y modularidad

Nikos Mylonakis

[email protected]

Dept. Llenguatges i Sistemes Informatics Universitat Politecnica de Catalunya

Barcelona

Nikos Mylonakis, UPC (Spain) April 16, 2009 – p.1/42

• Para resolver problemas de cierta envergadura seutiliza normalmente la técnica de diseño que seconoce con el nombre de diseño modular.

• La idea básica es descomponer el problema ensubproblemas que se puedan resolver con unconjunto de subprogramas que tengan una ciertacohesión y que sean más tratables que elproblema original

• Al conjunto de subprogramas que resuelve unsubproblema se le llama módulo funcional.

• Un módulo puede hacer uso de un subprogramade otro módulo si éste aparece en su interfaz


• Un interfaz es un conjunto de cabeceras desubprogramas que pueden ser utilizados por otrosmódulos

• Los interfaces aparecieron para minimizar elacoplamiento entre los módulos. Se dice que esconveniente un diseño con acoplamiento débilentre módulos.

• Con este fin, en un interfaz sólo tienen queaparecer los subprogramas principales del móduloy no los subprogramas que son utilizados paraimplementar los subprogramas principales

• Esta descomposición se conoce con el nombre dedescomposición funcional Nikos Mylonakis, UPC (Spain) April 16, 2009 – p.3/42

• Más adelante apareció un nuevo tipo dedescomposición o abstracción que se conoce conel nombre de abstracción de datos

• La idea básica es determinar los tipos abstractosde datos que se requieren para resolver elproblema

• Estos tipos de datos serán utillizadas pordiferentes módulos funcionales

• La novedad principal de este mecanismo deabstracción es que no permite accederdirectamente a la representación de la estructurade datos.


• De nuevo sólo podemos acceder mediante lasoperaciones principales declaradas en el interfaz.Esto garantiza el acoplamiento débil entre losmódulos

• Esta técnica de diseño permite especificar primerotodos los módulos funcionales y de datos ydespués implementarlos con las modificacionesoportunas o primero especificar e implementarunos módulos funcionales y después especificar eimplementar el resto


• Las estructuras de datos se suelen implementar alfinal cuando ya se sabe con seguridad cuáles sonlas operaciones que interesan que sean máseficientes. Si es posible éstas han de poder serejecutables en tiempo constante.

• Veamos como ejemplo el cálculo de la frecuenciade aparición de cada letra minúscula en un textodadoaccion frecuencia (sal f: tabla_frec, ent s: sec decaracter){ Pre: La secuencia s está cerrada }{ Post: f contiene la frecuencia de las letrasminúsculas de s }


• El módulo tendría adicionalmente una funciónauxiliar que determinaría si una letra es minúscula

• La estructura de datos tabla_frec estaría definidaen otro módulo con las siguientes operaciones enel interfaz:

accion inicializar_cero(sal f: tabla_frec){Pre: Cierto }{Post: Inicializamos la tabla de frecuencia a cero }


accion incrementar(ent/sal f: tabla_frec, ent c:caracter){Pre: Cierto }{Post: Incrementamos la frecuencia del carácter c en f}

• En este caso la representación es muy sencillamediante una tabla de carácteres con rango 1..27

• Si cambiamos levemente el problema con el fin dedeterminar la frecuencia de las palabras laestructura de datos se complica si queremosobtener una solución eficiente


• El módulo principal se simplifica pero ahoratenemos dos estructuras de datos: una para laspalabras y otra para almacenar la frecuencia delas palabras

• Una posible representación de la estructura paraalmacenar la frecuencia de las palabras seríamediante una lista ordenada de pares(palabra,frecuencia)

• Esta solución hace que la operación incrementartenga un coste lineal

• Este curso veremos una estructura de datos quemejora el coste de esta operación haciéndoloprácticamente constante Nikos Mylonakis, UPC (Spain) April 16, 2009 – p.9/42

Sintaxis abstracta del lenguaje demódulos

Ya hemos visto varias implementaciones de módulos.Veamos ahora su sintaxis abstracta:

modulo < nombre >

usa < lista_modulos >

ops < operaciones >

implementacion

< representacion >

< subprogramas >

fmodulo


• El nombre del módulo coincide con el nuevo tipoque estamos definiendo

• usa < modulos >

Al incluir el nombre de un módulo o tad en estalista nos permite utilizar cualquier elemento de suinterfaz en el módulo que estamos definiendo.


• < operaciones > Aquí definimos un conjunto deoperaciones.

• Toda operación que no aparezca en la cláusulaops pero esté definida dentro del módulo, no podráser importada por otro módulo.


• < representacion > La representación consiste enuna declaración de constantes y una declaraciónde tipos con la misma sintaxis que en notaciónalgorítmica.

• Uno de los tipos ha de tener el nombre del nombredel módulo.


• < subprogramas > Aquí se definen las operacionesdel módulo utilizando como parámetros formalesla representación del nuevo tipo definido en elmódulo.

• Para cada operación, tenemos que definir sucabecera,a continuación su especificaciónindicando su precondición y postcondición yfinalmente el código.


Especificación algebraica

• Hasta ahora hemos visto especificación pre/postde subprogramas

• Para el caso de las estructuras de datosdefiníamos una representación de la estructuraque se utilizaba para la especificación pre/post delas operaciones.

• En este curso vamos a ver una nueva forma deespecificar estructuras de datosindependientemente de la representación de laestructura que se conoce como especificaciónalgebraica de tipos abstractos de datos (tads).


• Una especificación algebraica de un tad consisteen un conjunto de géneros, una signatura con laaridad de las operaciones del tad y un conjunto deecuaciones entre términos generados por lasoperaciones más un conjunto de variablesasociados a cada género.

• Un término sin variables denota un valor del tadmientras que un término con variables denota unconjunto de valores no necesariamente acotadodel tad

• Los términos con variables se utilizan en lasecuaciones para expresar propiedades de lasoperaciones de los tads


• Veamos como primer ejemplo la especificaciónalgebraica del tad pila de enteros

• Los géneros del tad son pila_ent y entero

• La signatura contiene las operaciones siguientescon su correspondiente aridad

pila_vacia :→ pila_ent

empilar : entero × pila_ent → pila_ent

desempilar : pila_ent → pila_ent parcial

cima : pila_ent → entero parcial


• Cualquier valor de una pila es expresableúnicamente con las operaciones pila_vacia yempilar.

• Por ejemplo la pila con valores 2 4 y 6 en la cimase expresaría mediante el términoempilar(6, empilar(4, empilar(2, pila_vacia)))

• Pero tenemos adicionalmente una operacióndesempilar que modifica el estado de una pila y laoperación cima que consulta el último elementoinsertado en la pila.

• La especificación de su funcionamiento ha de sermediante propiedades expresadas en forma deecuaciones. Nikos Mylonakis, UPC (Spain) April 16, 2009 – p.18/42

• Una propiedad de la operación desempilar es queal desempilar cualquier pila p al que se le haempilado i obtenemos la misma pila p

• Esto se expresa mediante la ecuacióndesempilar(empilar(i, p)) = p donde p es unavariable del género pila_ent e i una variable delgénero entero.

• Otra propiedad de la operación cima es que lacima de cualquier pila p a la que se le empila i es i.

• Esto se expresa mediante la ecuacióncima(empilar(i, p)) = i


• Estas dos ecuaciones no completan laespecificación de Pila_ent

• Adicionalmente tenemos que expresar que nopodemos aplicar las operaciones desempilar y cima

a la pila_vacia.• Esto se expresa mediante términos seguidos de la

flecha ↑. En nuestro caso desempilar(pila_vacia) ↑ ycima(pila_vacia) ↑.

• Esto completa la especificación algebraica del tadPila_ent


• Veamos ahora la especificación algebraica del tadtabla de frecuencia de palabras (Tabla_frec_pal)

especificacion Tabla_frec_pal

usa palabra, natural

ops

inicializar :→ tabla_frec_pal

incrementar : tabla_frec_pal × palabra

→ tabla_frec_pal

frecuencia : tabla_frec_pal × palabra → natural


axiomas

incrementar(incrementar(tfp, p), q)

= incrementar(incrementar(tfp, q), p)

frecuencia(inicializar, p) = 0

frecuencia(incrementar(tfp, p), p)

= frecuencia(tfp, p) + 1

p 6= q ⇒ frecuencia(incrementar(tfp, p), q)

= frecuencia(tfp, q)

fespecificacion


• En este caso mediante las operaciones inicializare incrementar_frec podemos generar todos lasposibles tabla de frecuencia

• Para definir las propiedades de la operaciónconsultora frecuencia requerimos de una ecuacióncondicional

• Esta ecuación condicional tiene como premisauna operación booleana sobre las palabras

• En general podremos tener un conjunto deconjunciones con ecuaciones y expresionesbooleanas


Sintaxis abstracta

especificacion < nombre > [< par_formal >]usa < lista_modulos >

< signatura >

axiomas

< ecuaciones >

fespecificacion


• El interfaz de las especificaciones es igual que elde los módulos pudiendo tener especificacionesgenéricas con la excepción que en la signatura delas operaciones sólo se tiene que expresar suaridad en el formato descrito en los ejemplos

• Las ecuaciones pueden ser ecuaciones simplesde términos con variables, ecuacionescondicionales o un término seguido de ↑ queindica que ese término o conjunto de términos noestá definido

• La interpretación de una ecuación t1=t2 si t1 y t2no tienen variables es que t1 y t2 están definidos ydenotan el mismo valor.


• Una substitución σ es una asociación de variablesa términos sin variables

• La interpretación de una ecuación t1 = t2 si t1 y t2tienen variables es que para toda substitución σ delas variables por términos definidos σ t1 y σ t2están definidos y denotan el mismo valor

• La interpretación de una ecuación condicional esque para toda substitucion σ que haga que laspremisas sean ciertas entonces σ t1 y σ t2 estándefinidos y denotan el mismo valor


Semántica

• Para determinar si una especificación es correctaes conveniente saber exactamente que denota ypara ello hay que definir una semántica.

• Veamos un ejemploespecificacion treselemops

a:treselem;b:treselem;c:treselem;s:treselem → treselem;


axiomas

s(a)=b;s(b)=c;s(c)=a

• A una misma especificación se le pueden dardiferentes semánticas

• Las diferentes semánticas asocian una clase deálgebras a cada especificación


• Un álgebra consiste en un conjunto de valorespara cada género y una función para cadaoperación de la signatura

• Mediante una semántica laxa asociamos unaclase de álgebras que pueden ser muy diferentesentre sí.

• Ejemplos de estas álgebras para nuestro ejemploson:

• A1treselem = {1, 2, 3}, aA1 = 1, bA1 = 2, cA1 = 3,sA1(1) = 2, sA1(2) = 3, sA1(3) = 1




• Btreselem = {1, 2, 3, 4, 5, 6}, aB = 1, bB = 2, cC = 3,sB(1) = 2, sB(2) = 3, sB(3) = 1, sB(4) = 5, sB(5) =5, sB(6) = 5

• Ctreselem = {2}, aC = 2, bC = 2, cC = 2,sC(2) = 2


• Un álgebra satisface una especificación sisatisface todas sus ecuaciones.

• Podemos comprobar que las 5 álgebras dadassatisfacen la especificación

• De éstas se dice que las 3 primeras son isomorfaspues existe una biyección entre ellas

• Para dar semántica a TADS a nosotros no nosinteresan las 2 últimas álgebras


• Como ahora veremos la semántica inicial noincluirá estas 2 últimas álgebras y definirá unaclase isomorfa de álgebras como las 3 primerasde nuestro ejemplo

• Para ello incluye 2 condiciones adicionalesademás de que se tienen que satisfacer todas lasecuaciones de la especificación

• La primera condición es ausencia de elementosextraños. Es decir ausencia de valores del álgebraque no tengan un término que denote ese valor


• La segunda condición es ausencia de confusión.Es decir que no haya dos términos que denoten elmismo valor si no se puede deducir de lasecuaciones de la especificación.

• Se puede comprobar fácilmente que en nuestroejemplo el álgebra B tiene elementos extraños y elálgebra C tiene confusión.

• En cambio las tres primeras álgebras Ai no tienenni elementos extraños ni confusión y se puededemostrar que son isomorfas entre sí


• Se puede demostrar formalmente que si seimponen estas dos condiciones la semánticaobtenida es una única clase isomorfa de álgebras.

• A esta semántica se le llama semantica inicial y esla semántica que utilizaremos para nuestraespecificación algebraica de TADS

• Por tanto para determinar si un TAD T satisfaceuna especificación tendremos que comprobarestas dos condiciones (ausencia de elementosextraños y ausencia de confusión) además desatisfacer todas las ecuaciones


• Ahora vamos a ver una metodología para definirespecificaciones algebraicas de TADS

• Esta metodología se verá con el ejemplo de laespecificación de los conjuntos de enteros

• La primera cuestión a resolver es determinar lasoperaciones a incluir. En un diseño modularqueda determinado por las necesidades de lasabstracciones funcionales pero en este ejemplopodemos incluir inicialmente las usuales


• Estas serían:

∅ :→ conjunto_ent;

union : conjunto_ent × conjunto_ent → conjunto_ent;

borrar_ent : entero × conjunto_ent → conjunto_ent;

pert : entero × conjunto_ent → booleano

• La segunda cuestión es determinar si con lasoperaciones podemos generar todos los posiblesvalores del TAD. En nuestro caso la respuesta esnegativa y necesitamos añadir una nuevaoperación


• Podemos añadir una operación que genere unconjunto de un elemento o una operacion queañada un entero a un conjunto. Nosotrosdecidimos incorporar esta última con aridad

ampliar : entero × conjunto_ent → conjunto_ent

• Con estas operaciones podemos generarconjuntos no acotados de enteros aunque noinfinitos


• La tercera cuestión es determinar un conjuntomínimo con en el cual podemos generar todo elconjunto de valores

• En nuestro caso escogemos ∅ y la operaciónampliar.

• La cuarta cuestión es determinar si existen paresde términos generados por constructoras que hande denotar el mismo valor.

• Si es así tenemos que añadir ecuaciones quecaractericen esto


• En nuestro ejemplo tenemos que añadir lossiguientes axiomas:

ampliar(i, ampliar(j, c)) = ampliar(j, ampliar(i, c));

ampliar(i, ampliar(i, c)) = ampliar(i, c)

• Ahora es conveniente determinar una formaestandar o canónica de denotar todos los posiblesvalores de un género y comprobar que mediantenuestras ecuaciones podemos convertir cualquiertérmino en término canónico


• En nuestro caso una forma canónica derepresentar un conjunto {i1,. . . ,in} es añadiendoordenadamente los elementos mediante laoperación ampliar

• Es fácil comprobar que cualquier término queañade elementos de forma arbitraria repitiendoinserciones, mediante las 2 ecuaciones descritaspodemos convertirlo a un término canónico

• La ultima cuestión consiste en definir lasoperaciones no constructoras. Una forma usual deproceder es tratar en diferentes ecuaciones lasdiferentes operaciones constructoras para losargumentos del género que tratamos.


• Esto a veces no es necesario y a veces serequiere un mayor análisis de caso que dependedel problema

• Los axiomas requeridos serían los siguientes:

union(∅, s) = s;

union(ampliar(v, s1), s2) = ampliar(v, union(s1, s2))

borrar_ent(i, ∅) = ∅

borrar_ent(i, ampliar(i, s)) = borrar_ent(i, s)

i 6= j ⇒ borrar_ent(i, ampliar(j, s)) =

ampliar(j, borrar_ent(i, s))


pert(i, ∅) = falso;

pert(i, ampliar(j, s)) = (i = j) ∨ pert(i, s)

Esto concluye la especificación del TAD conjunto deenteros


apuntes de programación y estructuras de datos ...pred/tads2.pdf•para resolver problemas de...

Documents