Representación de conjuntos en un ordenador (Union, interseccion….) + Software

Para realizar intersecciones o uniones de dos o más conjuntos en un ordenador, puede ser algo tardado para él, sin embargo, podemos hacer la representación de estos conjuntos usando valores binarios.

Por ejemplo, si tenemos:

U= 1,2,3,4,5,6,7,8,9

A= 1,2,3

B= 1,4,5

Podemos representar los conjuntos A y B con valores binarios con respecto al universo U, es decir, si el valor x del conjunto existe en U, se pondrá un 1 en su respectiva posición, de lo contrario, se pondrá un 0. Esto hace automáticamente que los subconjuntos sean del mismo tamaño que A.

Entonces A y B quedarían:

A= 1,1,1,0,0,0,0,0,0

B= 1,0,0,1,1,0,0,0,0

Realizar una intersección con estos valores binarios es tan sencillo como aplicar la tabla de verdad de AND

Si aplicamos AND a cada bit, obtendríamos como resultado la cadena: 100000000, puesto que sólo se cumple el operador en las posiciones 1 de los conjuntos. Por lo tanto, el resultado sería: 1, ya que la primera posición en el Universo corresponde precisamente al número 1.

Intersección: x pertence a la intersección sí pertenece a A (Y) pertenece a B.

Unión: x pertenece a la union si pertenece a A (O) pertenece a B.

Diferencia A-B: x pertenece a la diferencia si pertenece a A (Y) (NO) pertenece a B.

Diferencia B-A: x pertenece a la diferencia si (NO) pertenece a A (Y) si pertenece a B.

Diferencia simétrica: x pertenece a la diferencia si pertenece a A (O) pertenece a B (Y) (NO) pertenece a la interseccion de A y B.

Complemento de A: x pertenece al complemento si (NO) pertenece a A.

El software que les pongo a disposición está realizado en Java usando NetBeans y contempla las operaciones de conjuntos “explicadas”. Su punto más fuerte se da en el botón “Comenzar” que es cuando pasa los conjuntos a sus representaciones binarias.

De ahí, se activan los menus de “Operaciones” y se ve claramente lo fácil que es realizar intersecciones y las demás operaciones manejando binarios y no haciendo búsquedas completas a cada conjunto y al universo 😀

Espero que les sirva, cualquier duda pueden comunicarse vía correo eléctrónico o por twitter

Descarga

Publicado el febrero 16, 2012 en Programacion y etiquetado en , , . Guarda el enlace permanente. Deja un comentario.

Responder

Introduce tus datos o haz clic en un icono para iniciar sesión:

Logo de WordPress.com

Estás comentando usando tu cuenta de WordPress.com. Cerrar sesión / Cambiar )

Imagen de Twitter

Estás comentando usando tu cuenta de Twitter. Cerrar sesión / Cambiar )

Foto de Facebook

Estás comentando usando tu cuenta de Facebook. Cerrar sesión / Cambiar )

Google+ photo

Estás comentando usando tu cuenta de Google+. Cerrar sesión / Cambiar )

Conectando a %s

A %d blogueros les gusta esto: