Varios

Tema 3: Conjuntos, bolsas y funciones. Funciones de dispersión.

3

CONJUNTOS, BOLSAS Y FUNCIONES.
FUNCIONES DE DISPERSIÓN

3.1

TAD: 05/06

EL TAD CONJUNTO.

El TAD Conjunto es una colección de elementos distintos (todos del mismo tipo) junto
con una serie de procedimientos de acceso.
Veamos la diferencia entre esta definición y la del TAD Lista. Los elementos en una lista
notienen porqué ser distintos, y tienen un orden lineal impuesto que refleja el orden en que
fueron insertados en la lista. Por el contrario, en un conjunto no existen elementos duplicados,
y el orden en que los elementos son insertados no es significativo. De esta manera, dos conjuntos
son iguales si poseen los mismos elementos, independientemente del orden en que hayan sido
insertados en cada unode ellos; por otro lado, la inserción de un elemento en un conjunto no
tiene efecto alguno si dicho elemento ya estaba en el conjunto.
Por otro lado, los elementos que forman parte de un conjunto, pueden especificarse de
dos formas:
a) Por enumeración explícita, que se hará como lo haremos nosotros, aunque sólo sirve
para conjuntos finitos.
b) Para conjuntos infinitos -que no vamos a tratardirectamente- se puede dar una
propiedad o predicado P, tal que:
œa P(a) ] a 0 Cjto
Aunque no lo parezca, en computación hay casos en los que se emplea el método b) de
especificación de conjuntos, como p.ej. en una consulta SQL, en la que se retorna el cjto. de
tuplas que verifican una cierta propiedad -si se usa la cláusula DISTINCT-, o una bolsa o
multiconjunto -en caso contrario-.
3.1.1ESPECIFICACIÓN ALGEBRAICA

Como en los TADs lineales, tenemos dos operadores constructores, Crear e Incluir,que
son usados para crear un conjunto vacío e insertar un elemento en un conjunto respectivamente.
Tenemos dos predicados , uno que comprueba si el conjunto es vacío (Es_Vacío) y otro que
comprueba si contiene un determinado elemento (Pertenece). Tenemos una función selectora quedevuelve un conjunto del que ha sido extraído un determinado elemento (Eliminar). Hemos
añadido otras funciones, como Unión, Intersección o Diferencia. Se ha incluído asimismo una
operación Elemento que no debe confundirse con el tipo base Elemento.
tipo Conjunto
dominios Lógico, ù
genérico
Elemento
operaciones
= : Elemento × Elemento
fin genérico

Lógico

1

Tema 3: Conjuntos,bolsas y funciones. Funciones de dispersión.

TAD: 05/06

generadores
Crear:
Conjunto
Agregar: Elemento × Conjunto
Conjunto
constructores
Eliminar: Elemento × Conjunto
Conjunto
Union: Conjunto × Conjunto
Conjunto
Interseccion: Conjunto × Conjunto
Conjunto
Diferencia: Conjunto × Conjunto
Conjunto
selectores
Pertenece: Elemento × Conjunto
Lógico
f: Conjunto × Conjunto
LógicoEs_Vacio: Conjunto
Lógico
Cardinal: Conjunto
ù
Elemento: Conjunto
Elemento
precondiciones
c:Conjunto
Elemento(c) : not Es_Vacio(c)
ecuaciones i, j:Elemento; c:Conjunto
Agregar(i, Agregar(j, c)) == Agregar(j, Agregar(i, c))
Agregar(i, Agregar(i, c)) == Agregar(i, c)
Es_Vacio(Crear) == V
Es_Vacio(Agregar(i, c)) == F
Pertenece(i, Crear) == F
Pertenece(i, Agregar(j, c)) ==
SI i = j ENTONCESV
SI NO
Pertenece(i, c)
f(Crear, c) == V
f(Agregar(i, c1), c2) ==
SI Pertenece(i, c2) ENTONCES
f(c1, c2)
SI NO
F
Eliminar(i, Crear) == Crear
Eliminar(i, Agregar(j, c)) == SI i = j ENTONCES
Eliminar(i, c)
SI NO
Agregar(j, Eliminar(i, c))
Cardinal(Crear) == 0
Cardinal(Agregar(i, c)) = 1 + Cardinal(Eliminar(i, c))
Pertenece(Elemento(c), c) == V
Union(Crear, c) == cUnion(Agregar(i, c1), c2) == Agregar(i, Union(c1, c2)
Interseccion(Crear, c) == Crear
Interseccion(Agregar(i, c1), c2) == SI Pertenece(i, c2) ENTONCES
Agregar(i, Interseccion(c1, c2))
2

Tema 3: Conjuntos, bolsas y funciones. Funciones de dispersión.

TAD: 05/06

SI NO
Interseccion(c1, c2)
Diferencia(c, Crear) == c
Diferencia(c1, Agregar(i, c2)) == Diferencia(Eliminar(i, c1), c2)
fin
De...