Universidad Simon Bolvar Departamento de Computacin y Tecnologa de la Informacin CI-2612 - Algoritmos y Estructuras II

Prctica 1

Un Multidiccionario es un Tipo Abstracto de Datos (TAD) que permite almacenar pares (clave, valor), pero a su vez cada clave puede estar asociada a ms de un valor. En el Multidiccionario no existe una nocin de orden entre los pares que contiene. Las operaciones que ofrece este TAD son: (i) crear, operacin que dado un tamao mximo de claves y de valores por clave, crea un Multidiccionario vaco; (ii) agregar, operacin que dados un Multidiccionario, una clave y un valor, agrega la asociacin entre esa clave y ese valor al Multidiccionario; (iii) eliminar, operacin que dados un Multidiccionario, una clave y un valor, elimina la asociacin entre dicha clave y valor del Multidiccionario; (iv) esta, operacin que dados un Multidiccionario y una clave indica si dicha clave est asociada a algn valor en el Multidiccionario; (v) presente, operacin que dados un Multidiccionario, una clave y un valor, indica si la asociacin entre esa clave y ese valor est presente en el Multidiccionario; (vi) buscar, operacin que dado un Multidiccionario y una clave, devuelve alguno de los valores a los que est asociado dicha clave en el Multidiccionario; (vii) cantidadValores, operacin que dado un Multidiccionario y una clave, indica cuntos valores estn asociados a dicha clave en el Multidiccionario. Este TAD se especificar usando como modelo abstracto de representacin las estructuras matemticas funcin y conjunto, si el tipo de las claves es T0, y el tipo de los valores es T1, entonces los valores de este TAD estn dados por una funcin parcial de T0 en conjunto de T1, donde cada valor de T0 est asociado a un conjunto no vaco de T1. Se considerar un nmero mximo de claves distintas a almacenar (MAXC), y un nmero mximo de valores a almacenar por clave (MAXV). A continuacin se presenta una especificacin parcial del TAD:

Especificacin A de TAD Multidiccionario(T0,T1) Modelo de Representacin

const MAXC,MAXV : int var contenido : T0 -+-> set T1 (funcin parcial)

Invariante de Representacin MAXC > 0 MAXV > 0 # dom(contenido) MAXC (c: cdom(contenido): 0< #contenido(c) MAXV)

Operaciones proc crear (in mc,mv : int; out md : Multidiccionario) { Pre: mc > 0 mv > 0 } { Post: md.MAXC=mc md.MAXV=md md.contenido = {} }

proc agregar (in-out md : Multidiccionario; in c : T0; in v : T1) { Pre: . } { Post: }

proc eliminar proc esta proc presente proc buscar proc cantidadValores

Fin TAD

1. Complete cada una de las pre y post condiciones del Modelo abstracto.

Dada la siguiente especificacin del TAD Multidiccionario para el modelo concreto:

Especificacin B de TAD Multidiccionario(T) refinamiento de A Modelo de Representacin

const MAXC,MAXV : int type PAR: record clave:T0; valor:T1 end var elems: array [0..MAXC*MAXV) of PAR var tam: int

Invariante de Representacin MAXC > 0 MAXV > 0 0 tam MAXC*MAXV

Relacin de Acoplamiento contenido = { i : 0i 0 } { Post: md.MAXC=mc md.MAXV=md md.tam = 0 }

proc agregar (in-out md : Multidiccionario; in c : T0; in v : T1) { Pre: md.tam < md.MAXC*md.MAXV } { Post: md.elems= md0.elems (md0.tam:(c,v)) md.tam = md0.tam +1}

proc eliminar proc esta proc presente proc buscar proc cantidadValores

Fin TAD

2. Complete cada una de las pre y post condiciones de las operaciones del modelo concreto.

3. Implemente la operacin agregar y eliminar del TAD Multidiccionario.

4. Para la operacin agregar del TAD Multiconjunto visto en clase, demuestre que la precondicin del modelo abstracto y del modelo concreto son consistentes segn la nocin de refinamiento de datos. A continuacin se muestran ambas precondiciones: PreA: # B.contenido < B.MAX PreC: (i : 0i