TAD Bolsas

CONJUNTOS, BOLSAS Y FUNCIONES.

TAD

Para empezar los TAD son tipos de datos abstractos como su término lo dice, estos son datos lógicos que nos sirven a para representar variedad de conjuntos y datos de manera que para acceder a los mismos se tienen que elaborar una serie de procedimientos lógicos dependiendo de su naturaleza.

El TAD CONJUNTO

Es una colección de elementos distintos (todos del mismo tipo) junto una serie de procedimientos de acceso.

En el TAD lista es realmente importante el orden en el que estos fueron insertados. Pero en un conjunto realmente no existe la duplicación de elemento.

El TAD Bolsa

Es una colección de elementos del mismo tipo que pueden o no ser distintos junto con una serie de procedimientos para acceder a ellos.

Una característica puede ser la multiplicidad ya que es el número de veces que algún elemento del conjunto aparece en la bolsa.

La diferencia que tiene con el TAD conjunto es que si tenemos elementos del conjunto repetidos permanecen incluidos y no se suprimen.

Como un ejemplo de un problema que hace uso del TAD Bolsa (supongamos bolsas de números cardinales), tomemos tres números naturales, encontremos las bolsas de sus factores primos, su máximo común divisor y mínimo común múltiplo. Por ejemplo, dados los números 30, 78 y 84, denotemos las bolsas de sus factores primos como X, Y y Z respectivamente; así pues tenemos: X = {2, 3, 5}, Y = {2, 3, 13} y Z = {2, 2, 3, 7}.

Los factores del m.c.d. vienen dados por la intersección de las tres bolsas, es decir:

m.c.d. = X _ Y _Z

= {2, 3, 5} _ {2, 3, 13} _ {2, 2, 3, 7}

= {2, 3} _ {2, 2, 3, 7}

= {2, 3}

= 6

Los factores del m.c.m. vienen dados por la diferencia simétrica de la unión de las tres bolsas con su intersección.

Reglas de Especificación Algebraica para TDA de Bolsa

- Si hay elementos repetidos, permanecen todas las ocurrencias.

- La operación Eliminar sólo elimina una ocurrencia del elemento que sea.

- La operación Cardinal se utiliza cada vez que se usa el comando agregar.

Tipo Bolsa;

Dominios Lógico, ù

Genérico

Elemento

Operaciones= : Elemento × Elemento Lógico

Fin genérico

Generadores

Crear: --› Bolsa

Agregar: Elemento × Bolsa --› Bolsa

Constructores

Eliminar: Elemento × Bolsa --› Bolsa

Selectores

Elemento: Bolsa --›Elemento

Pertenece: Elemento × Bolsa --› Lógico

Es_Vacia: Bolsa--› Lógico

Cardinal: Bolsa --›ù

NumRep: Elemento × Bolsa--› ù

Precondiciones b:Bolsa

pre Elemento(b) : not Es_Vacia(b)

Ecuaciones i, j:Elemento; b:Bolsa

...