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

42
Apuntes de Programación y estructuras de datos. Abstracción y modularidad Nikos Mylonakis [email protected] Dept. Llenguatges i Sistemes Inform ´ atics Universitat Polit ´ ecnica de Catalunya Barcelona Nikos Mylonakis, UPC (Spain) April 16, 2009 – p.1/42

Upload: trinhkhanh

Post on 12-Mar-2018

217 views

Category:

Documents


1 download

TRANSCRIPT

Page 1: Apuntes de Programación y estructuras de datos ...pred/tads2.pdf•Para resolver problemas de cierta envergadura se utiliza normalmente la técnica de diseño que se conoce con el

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

Page 2: Apuntes de Programación y estructuras de datos ...pred/tads2.pdf•Para resolver problemas de cierta envergadura se utiliza normalmente la técnica de diseño que se conoce con el

• 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

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

Page 3: Apuntes de Programación y estructuras de datos ...pred/tads2.pdf•Para resolver problemas de cierta envergadura se utiliza normalmente la técnica de diseño que se conoce con el

• 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

Page 4: Apuntes de Programación y estructuras de datos ...pred/tads2.pdf•Para resolver problemas de cierta envergadura se utiliza normalmente la técnica de diseño que se conoce con el

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

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

Page 5: Apuntes de Programación y estructuras de datos ...pred/tads2.pdf•Para resolver problemas de cierta envergadura se utiliza normalmente la técnica de diseño que se conoce con el

• 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

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

Page 6: Apuntes de Programación y estructuras de datos ...pred/tads2.pdf•Para resolver problemas de cierta envergadura se utiliza normalmente la técnica de diseño que se conoce con el

• 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 }

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

Page 7: Apuntes de Programación y estructuras de datos ...pred/tads2.pdf•Para resolver problemas de cierta envergadura se utiliza normalmente la técnica de diseño que se conoce con el

• 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 }

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

Page 8: Apuntes de Programación y estructuras de datos ...pred/tads2.pdf•Para resolver problemas de cierta envergadura se utiliza normalmente la técnica de diseño que se conoce con el

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

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

Page 9: Apuntes de Programación y estructuras de datos ...pred/tads2.pdf•Para resolver problemas de cierta envergadura se utiliza normalmente la técnica de diseño que se conoce con el

• 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

Page 10: Apuntes de Programación y estructuras de datos ...pred/tads2.pdf•Para resolver problemas de cierta envergadura se utiliza normalmente la técnica de diseño que se conoce con el

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

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

Page 11: Apuntes de Programación y estructuras de datos ...pred/tads2.pdf•Para resolver problemas de cierta envergadura se utiliza normalmente la técnica de diseño que se conoce con el

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

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

Page 12: Apuntes de Programación y estructuras de datos ...pred/tads2.pdf•Para resolver problemas de cierta envergadura se utiliza normalmente la técnica de diseño que se conoce con el

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

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

Page 13: Apuntes de Programación y estructuras de datos ...pred/tads2.pdf•Para resolver problemas de cierta envergadura se utiliza normalmente la técnica de diseño que se conoce con el

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

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

Page 14: Apuntes de Programación y estructuras de datos ...pred/tads2.pdf•Para resolver problemas de cierta envergadura se utiliza normalmente la técnica de diseño que se conoce con el

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

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

Page 15: Apuntes de Programación y estructuras de datos ...pred/tads2.pdf•Para resolver problemas de cierta envergadura se utiliza normalmente la técnica de diseño que se conoce con el

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

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

Page 16: Apuntes de Programación y estructuras de datos ...pred/tads2.pdf•Para resolver problemas de cierta envergadura se utiliza normalmente la técnica de diseño que se conoce con el

• 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

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

Page 17: Apuntes de Programación y estructuras de datos ...pred/tads2.pdf•Para resolver problemas de cierta envergadura se utiliza normalmente la técnica de diseño que se conoce con el

• 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

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

Page 18: Apuntes de Programación y estructuras de datos ...pred/tads2.pdf•Para resolver problemas de cierta envergadura se utiliza normalmente la técnica de diseño que se conoce con el

• 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

Page 19: Apuntes de Programación y estructuras de datos ...pred/tads2.pdf•Para resolver problemas de cierta envergadura se utiliza normalmente la técnica de diseño que se conoce con el

• 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

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

Page 20: Apuntes de Programación y estructuras de datos ...pred/tads2.pdf•Para resolver problemas de cierta envergadura se utiliza normalmente la técnica de diseño que se conoce con el

• 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

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

Page 21: Apuntes de Programación y estructuras de datos ...pred/tads2.pdf•Para resolver problemas de cierta envergadura se utiliza normalmente la técnica de diseño que se conoce con el

• 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

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

Page 22: Apuntes de Programación y estructuras de datos ...pred/tads2.pdf•Para resolver problemas de cierta envergadura se utiliza normalmente la técnica de diseño que se conoce con el

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

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

Page 23: Apuntes de Programación y estructuras de datos ...pred/tads2.pdf•Para resolver problemas de cierta envergadura se utiliza normalmente la técnica de diseño que se conoce con el

• 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

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

Page 24: Apuntes de Programación y estructuras de datos ...pred/tads2.pdf•Para resolver problemas de cierta envergadura se utiliza normalmente la técnica de diseño que se conoce con el

Sintaxis abstracta

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

< signatura >

axiomas

< ecuaciones >

fespecificacion

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

Page 25: Apuntes de Programación y estructuras de datos ...pred/tads2.pdf•Para resolver problemas de cierta envergadura se utiliza normalmente la técnica de diseño que se conoce con el

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

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

Page 26: Apuntes de Programación y estructuras de datos ...pred/tads2.pdf•Para resolver problemas de cierta envergadura se utiliza normalmente la técnica de diseño que se conoce con el

• 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

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

Page 27: Apuntes de Programación y estructuras de datos ...pred/tads2.pdf•Para resolver problemas de cierta envergadura se utiliza normalmente la técnica de diseño que se conoce con el

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;

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

Page 28: Apuntes de Programación y estructuras de datos ...pred/tads2.pdf•Para resolver problemas de cierta envergadura se utiliza normalmente la técnica de diseño que se conoce con el

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

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

Page 29: Apuntes de Programación y estructuras de datos ...pred/tads2.pdf•Para resolver problemas de cierta envergadura se utiliza normalmente la técnica de diseño que se conoce con el

• 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

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

Page 30: Apuntes de Programación y estructuras de datos ...pred/tads2.pdf•Para resolver problemas de cierta envergadura se utiliza normalmente la técnica de diseño que se conoce con el

• A2treselem = {1, 2, 3}, aA2 = 2, bA2 = 1, cA2 = 3,sA2(1) = 3, sA2(2) = 1, sA2(3) = 2

• A3treselem = {4, 5, 6}, aA3 = 4, bA3 = 5, cA3 = 6,sA3(4) = 5, sA3(5) = 6, sA3(6) = 4

• 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

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

Page 31: Apuntes de Programación y estructuras de datos ...pred/tads2.pdf•Para resolver problemas de cierta envergadura se utiliza normalmente la técnica de diseño que se conoce con el

• 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

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

Page 32: Apuntes de Programación y estructuras de datos ...pred/tads2.pdf•Para resolver problemas de cierta envergadura se utiliza normalmente la técnica de diseño que se conoce con el

• 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

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

Page 33: Apuntes de Programación y estructuras de datos ...pred/tads2.pdf•Para resolver problemas de cierta envergadura se utiliza normalmente la técnica de diseño que se conoce con el

• 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í

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

Page 34: Apuntes de Programación y estructuras de datos ...pred/tads2.pdf•Para resolver problemas de cierta envergadura se utiliza normalmente la técnica de diseño que se conoce con el

• 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

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

Page 35: Apuntes de Programación y estructuras de datos ...pred/tads2.pdf•Para resolver problemas de cierta envergadura se utiliza normalmente la técnica de diseño que se conoce con el

• 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

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

Page 36: Apuntes de Programación y estructuras de datos ...pred/tads2.pdf•Para resolver problemas de cierta envergadura se utiliza normalmente la técnica de diseño que se conoce con el

• 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

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

Page 37: Apuntes de Programación y estructuras de datos ...pred/tads2.pdf•Para resolver problemas de cierta envergadura se utiliza normalmente la técnica de diseño que se conoce con el

• 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

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

Page 38: Apuntes de Programación y estructuras de datos ...pred/tads2.pdf•Para resolver problemas de cierta envergadura se utiliza normalmente la técnica de diseño que se conoce con el

• 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

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

Page 39: Apuntes de Programación y estructuras de datos ...pred/tads2.pdf•Para resolver problemas de cierta envergadura se utiliza normalmente la técnica de diseño que se conoce con el

• 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

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

Page 40: Apuntes de Programación y estructuras de datos ...pred/tads2.pdf•Para resolver problemas de cierta envergadura se utiliza normalmente la técnica de diseño que se conoce con el

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

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

Page 41: Apuntes de Programación y estructuras de datos ...pred/tads2.pdf•Para resolver problemas de cierta envergadura se utiliza normalmente la técnica de diseño que se conoce con el

• 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))

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

Page 42: Apuntes de Programación y estructuras de datos ...pred/tads2.pdf•Para resolver problemas de cierta envergadura se utiliza normalmente la técnica de diseño que se conoce con el

pert(i, ∅) = falso;

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

Esto concluye la especificación del TAD conjunto deenteros

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