domingo, 30 de marzo de 2008

Conjuntos


Abajo

Clase 10: Conjuntos

ESTRUCTURA DE DATO DE TIPO CONJUNTOS

Turbo Pascal es uno de los pocos lenguajes de computadoras que brinda una cantidad de herramientas para las operaciones entre conjuntos. Dada la importancia que tiene este concepto no solo para la matemática sino también para otras disciplinas, a continuación se tratará este tema.
Un conjunto es una colección de elementos bien definidos. En el caso de Turbo Pascal, esos elementos deben ser todos del mismo tipo y ese tipo debe ser ordinal. La cantidad máxima de elementos está limitada a 256 y los valores ordinales estarán comprendido en el intervalo 0 a 255. El tipo conjunto permite manipular con un solo nombre una serie de valores o elementos, siendo estos, las componentes de la estructura conjunto. La manera en que Turbo Pascal determina si un elemento pertenece o no al conjunto, es a través de un enmascaramiento a nivel de bit. En principio si un bit está en 0 significa que el elemento no está presente y si un bit está en 1 significa que el elemento sí está presente. Una estructura de tipo conjunto ocupará una cantidad n de bytes, en donde n depende de los valores extremos del tipo base del conjunto. La máxima cantidad de bytes será de 32, ya que 32 x 8 = 256, de esta manera por cada bit se podrá determinar si un elemento de entre 256 máximos estará o no presente en el conjunto. Las siguientes expresiones determinan:


en donde:

MIN es el valor extremo inferior.
MAX es el valor extremo superior.
x representa un valor del tipo base


Representación interna en una estructura de datos de tipo conjunto

A continuación se considera el siguiente caso:

  1. un tipo base en el intervalo 0 a 15
  2. un conjunto A = {2,5,0,12,8,15,9,11}

MIN = 0
MAX = 15


Cantidad de bytes a usar por la estructura: 15 div 8 – MIN div 8 + 1 = 2

Número de byte de un valor x= 2: 2 div 8 – 0 div 8 = 0
Número de bit de un valor x=2: 2 mod 8 = 2

Número de byte de un valor x= 5: 5 div 8 – 0 div 8 = 0
Número de bit de un valor x=5: 5 mod 8 = 5

Número de byte de un valor x= 0: 0 div 8 – 0 div 8 = 0
Número de bit de un valor x=0: 0 mod 8 = 0

Número de byte de un valor x=12: 12 div 8 – 0 div 8 = 1
Número de bit de un valor x=12: 12 mod 8 = 4

Número de byte de un valor x= 8: 8 div 8 – 0 div 8 = 1
Número de bit de un valor x=8: 8 mod 8 = 0

Número de byte de un valor x=15: 15 div 8 – 0 div 8 = 1
Número de bit de un valor x=15: 15 mod 8 = 7

Número de byte de un valor x= 9: 9 div 8 – 0 div 8 = 1
Número de bit de un valor x=9: 9 mod 8 = 1

Número de byte de un valor x=11: 11 div 8 – 0 div 8 = 1
Número de bit de un valor x=11: 11 mod 8 = 3

Un bit en 0, en un número de byte y de bit correspondiente, indica que el número no pertenece al conjunto. En cambio un bit en 1, en un número de byte y de bit correspondiente, indica que el número pertenece al conjunto. De esta manera en la representación gráfica de más arriba está indicando que los elementos 2, 5, 7, 8, 11, 12, 14 y 15 pertenecen al conjunto A.

Diagramas de Venn o esquema de Euler

Permiten representar de manera gráfica resultados de las operaciones del álgebra de conjuntos.

Las operaciones básicas entre conjunto son:













Conjuntos en Turbo Pascal

En la sección type primero vamos a definir un tipo conjunto por medio de las palabras reservadas set of y a continuación el tipo base de cada elemento del conjunto, de la siguiente manera:

type
tCjto = set of tipo_base;

El tipo_base debe ser de tipo ordinal, pero no cualquier ordinal, solamente aquellos cuyos valores ordinales estén comprendidos en (0; 255). Por lo tanto, no solo los reales y las cadenas quedan excluidos, sino también el tipo integer, shortint, longint, word. Así que, los tipos definidos por Turbo Pascal han de ser el byte, char, boolean y aquellos definidos por el usuario por enumeración y por intervalo.

Ejemplos de tipos bases:

type

Cjto = set of byte;

Se ha definido un tipo Cjto que es igual a set of byte, en donde set of establece el tipo conjunto y byte dice que los elementos son todos del tipo base byte.

type
tFelinos = (leon,tigre,gato,lince,jaguar,guepardo,pantera);
tAlgunFelino = gato..guepardo;
tFieras = set of tFelinos;
tAlgunaFiera = set of tAlgunFelino;

Los tipos definidos por el usuario no pueden ser leídos o emitidos por medio de los procedimientos read o write, debido a que estos valores no son conocidos por anticipado. Una forma de evitar este inconveniente es utilizar una estructura de selección múltiple, como se indica a continuación:

Case random(7) of
0: Felix:= leon;
1: Felix:= tigre;
2: Felix:= gato;
3: Felix:= lince;
4: Felix:= jaguar;
5: Felix:= guepardo;
6: Felix:= pantera
end;


Case Felix of
leon: writeln(‘leon’);
tigre: writeln(‘tigre’);
gato: writeln(‘gato’);
lince: writeln(’lince’);
jaguar: writeln(‘jaguar’);
guepardo: writeln(‘guepardo’);
pantera: writeln(‘pantera’)
end;

var
Cfieras : tFieras;
CalgunaFiera : tAlgunaFiera;

Los tipos definidos por el usuario por enumeración o por intervalo son ordinales.
tFelinos es un tipo de dato definido por el usuario, siendo sus elementos valores constantes y no pueden repetirse en otra definición. Cada elemento ocupa una posición ordinal comenzando desde 0 y siguiendo con incremento de 1. Por lo tanto, leon = 0, tigre = 1, gato = 3 y así sucesivamente.
Esto permite entonces establecer una relación leon menor tigre menor gato menor ... menor pantera.


tAlgunFelino es un tipo también definido por el usuario en la que se establece indicando un valor que indica el extremo inferior y otro valor que indica el extremo superior.
Cfieras es una variable de tipo tFieras, por lo tanto, los valores que podrá contener son elementos del tipo base tFelinos, es decir, leon, tigre, gato...
CalgunaFiera es una variable de tipo tAlgunaFiera, por lo tanto, los valores que podrá contener son elementos del tipo base tAlgunFelino, es decir, gato, lince, jaguar, leopardo.

  • Las funciones Succ, Pred, Ord, y Chr pueden aplicarse a objetos de tipo ordinal.
  • Las constantes de conjuntos se encierran entre corchetes y separadas por coma.

    Ejemplos:

    [3,9..12,5,31,15]
    [‘a’..’z’,’A’..’Z’]
    [‘+’,’-‘,’*’,’/’]

    También es posible que los elementos estén referidos por expresiones:
    [12,a..b,i+2,ord(‘A’)..ord(‘C’),x div 2,ord(cad[k])+2,Pred(b)+5..Succ(b)+5,2*i]
    si a=5, b=8, x=52, i=15, k=3 y cad= ‘algoritmos’, entonces los elementos que pertenecen al conjunto son: 12, 5, 6, 7, 8, 17, 65, 66, 67, 26, 105, 12, 13, 14, 30 y con #14.

    Una constante de conjunto especial es el conjunto vacío {} representado por [ ].
    El conjunto universal U está formado por todos los elementos del tipo base del conjunto, p.e. si el tipo base es byte, entonces el U = [0..255].
    Podemos asignarles un nombre a las constantes conjuntos en la sección const:

    const
    CJTO_VACIO = [];
    CJTO_UNIVERSAL = [0..255]; son todos los elementos del tipo base.
    OPER_ARIT = [‘+’,’-‘,’*’,’/’]

    Operadores de conjuntos

    + para la unión entre conjuntos: A + B
    * para la intersección entre conjuntos: A * B
    - para la diferencia entre conjuntos: A – B

    Las prioridades son:

    1º. *
    2º. +, -.

    La diferencia simétrica se obtiene de la siguiente manera:

    (A + B) – (A * B) o por
    (A – B) + (B – A)
    El complemento de A, indicado por ~A, es igual al U – A, es decir:

    ~A = U – A

    Turbo Pascal brinda además de los operadores + y – los procedimientos Include y Exclude para incluir o excluir un elemento de un conjunto.

    Include(A,x)
    Exclude(A,x)

    Como la unión, la diferencia se refiere entre conjuntos, para incluir o excluir un elemento de un conjunto utilizando los operadores + o – debemos encerrar el elemento a incluir o excluir encerrado entre corchetes, de esta manera, lo estaremos transformando en conjunto, como se muestra a continuación:

    A := A + [x]
    A := A – [x]

    Include(A,x) es más eficiente que hacer A:= A + [x]
    Exclude(A,x) es más eficiente que hacer A:= A – [x]

    La pertenencia de un elemento en un conjunto se establece de la siguiente manera:

    x in A
  • el resultado será de tipo boolean si el elemento x pertenece al conjunto A el resultado es true, caso contrario es false.

    La no pertenencia de un elemento en un conjunto se establece de la siguiente manera:

    not (x in A)

    El resultado de esta evaluación es verdadero si el valor que contenga x está en el conjunto, caso contrario será falso.

    Ejemplo:

    x:= 4;
    A:= [2..7,20,12];
    if x in A then
    writeln(‘el valor ‘,x,’ pertenece al conjunto A)
    else
    writeln(‘el valor ‘,x,’ no pertenece al conjunto A’);

    Emite: el valor 4 pertenece al conjunto A. ¿por qué?


    Dos conjuntos pueden ser comparados por: =, <>, >=, <=.

    Ejemplos:

    A = B
    Si A = {7, 3, 9, 12} y B = {9, 3, 12, 7} entonces comparar si A = B es verdadero.
    A <> B
    Si A = {5, 2, 8} y B = {5, 2, 8, 6} entonces comparar si A <> B es verdadero.
    A >= B es falso si A = {5, 2, 8} y B = {5, 2, 8, 6}
    A <= B es verdadero

    Si A = {} y B = {3, 1}
    A <= B es verdadero

    Para emitir los elementos que pertenecen a un conjunto debemos emplear una variable del tipo base y que recorra cada uno de los valores del conjunto universal y preguntar si pertenece al conjunto, como se muestra a continuación:

    A:= [];
    for x:= 1 to 100 do
    Include(A,2*x);
    for x:= 0 to 255 do
    if x in A then
    write(x,’ ‘);

    La cardinalidad de un conjunto, indicado por #, es la cantidad de elementos que contiene. Para averiguar la cardinalidad de un conjunto en Turbo Pascal establecemos un ciclo como en el ejemplo anterior, pero contando con incremento en 1 en una variable cada vez que un elemento pertenece al conjunto, como se muestra a continuación:

    card:= 0;
    for x:= 0 to 255 do
    if x in A then
    inc(card);
    writeln(‘#A= ‘,card);



    Conjuntos a nivel de bit


    Aquellos lenguajes de computadoras que no brinden los beneficios del tipo conjunto podrán efectuarse de una forma alternativa a nivel de bit. Para ello, deberá contener algún operador para el tratamiento de operaciones a nivel de bit. Esos operadores que trabajan con operandos de tipo entero y producen resultados de tipo entero, Turbo Pascal los contiene y son:

    Desplazamiento de bit a izquierda: shl
    Desplazamiento de bit a derecha: shr
    Operador lógico conjunción: and
    Operador lógico disyunción: or
    Operador lógico disyunción exclusivo: xor
    Operador lógico negación: not -operador unario-.

    Las operaciones i shl j y i shr j desplazan el valor de i a la izquierda o a la derecha j bits ingresando por el extremo opuesto ceros. El tipo de resultado es del mismo tipo de i.

    Ejemplo:

    x <-- 01010011 010 10011 000

    Si se hace x <-- x shl 3 los bits se desplazan de derecha a izquierda, ingresan ceros por el extremo derecho y los bits del extremo izquierdo se van perdiendo, por lo tanto, el resultado de esa operación será que en x su valor ha sido cambiado a: 10011000, es decir, los 3 dígitos de la extrema izquierda se perdieron e ingresaron 3 ceros por la extrema derecha, representado de esta otra manera



    Una de las características más destacadas de estos tipos de operaciones a nivel de bit es que se pueden realizar operaciones de multiplicación y división en enteros muy rápidamente cuando la base es 2, el primer operando establece el exponente de dicha base. Si los bits son desplazados j posiciones hacia la izquierda estamos multiplicando y si se desplazan j posiciones hacia la derecha estamos dividiendo. Por ejemplo si a = 2, realizar la siguiente operación a shl 3 = 16, ya que a x 23 = 2 x 23 = 2 x 8 = 16. De la misma manera si a = 16, realizar a shr 3 = 2, ya que a / 23 = 16 / 23 = 16 / 8 = 2.
    Las siguientes operaciones a nivel de bit con los operadores lógicos and, or, not que se indican a continuación es para ilustrar como se opera y el resultado que se obtiene, un valor de 0 = false y un valor de 1 = true.


    Ejemplos:



    Operaciones con conjuntos a nivel de bit en donde A y B son variables de tipo word, por lo tanto el elemento más pequeño es 0 y el elemento más grande es 15. El conjunto vacío es poner todos los bits en 0, como se indica a continuación: VACIO <-- 0
    El conjunto universal es poner a todos los bits en 1, como se indica a continuación:
    UNIVERSAL <-- $FFFF en donde $ indica notación sistema de numeración hexadecimal.

    Ejemplos:

    Unión: C = A or B
    0110011010011101 A = {0,2,3,4,7,9,10,13,14}
    or 1100111011101110 B = {1,2,3,5,6,7,9,10,11,14,15}
    1110111011111111 C = {0,1,2,3,4,5,6,7,9,10,11,13,14,15}
    Intersección: C = A and B
    0110011010011101 A = {0,2,3,4,7,9,10,13,14}
    and 1100111011101110 B = {1,2,3,5,6,7,9,10,11,14,15}
    0100011010001101 C = {0,2,3,7,9,10,14}
    Diferencia: C = A - B
    0110011010011101 A = {0,2,3,4,7,9,10,13,14}
    and not 1100111011101110 B = {1,2,3,5,6,7,9,10,11,14,15}
    Hacemos primero B ß not B B = {0,4,8,12,13}
    quedando 0011000100010001 Se complementaron los bits de B, es decir, 0 x 1 y 1 x 0.
    por último hacemos el and :
    0110011010011101 A = {0,2,3,4,7,9,10,13,14}
    and 0011000100010001 B = {0,4,8,12,13}
    0010000000010001 C = {0,4,13}
    Diferencia simétrica: C = A xor B
    0110011010011101 A = {0,2,3,4,7,9,10,13,14}
    xor 1100111011101110 B = {1,2,3,5,6,7,9,10,11,14,15}
    1010100001110011 C = {0,1,4,5,6,8,11,13,15}
    Complemento: C = U and not A
    0110011010011101 A = {0,2,3,4,7,9,10,13,14}
    not A 1001100101100010 A <-- not A A = {1,5,6,8,11,12,15} 1111111111111111 U = {0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15} and 1001100101100010 not A 1001100101100010 C = {1,5,6,8,11,12,15} Pertenencia: (A shr x) mod 2 <> 0
    0110011010011101 A = {0,2,3,4,7,9,10,13,14}
    Determinar si x = 4 pertenece al conjunto A. Desplazamos los bits del conjunto A, 4 posiciones hacia la derecha resultando 0000011001101001, notamos que se perdieron los 4 bits de la extrema derecha del conjunto A y se incorporaron 4 ceros por la extrema izquierda. Luego al dividir por 2, nos queda un resto de 1 y como es distinto de 0 decimos que 4 Î A.
    Subconjunto: A and B = A verdadero A Í B
    0101110010011110 A = {1,2,3,4,7,10,11,12,14}
    and 1101111011111110 B = {1,2,3,4,5,6,7,9,10,11,12,14,15}
    0101110010011110 C = {1,2,3,4,7,10,11,12,14}

    luego notamos que el conjunto C es igual al conjunto A, por lo tanto decimos que el conjunto A es subconjunto de B.


    Nota: ¿Qué sucederá si desplazamos bits, en una variable con signo?

    Página inicial






    Anterior: Archivos II

    Siguiente: Arreglos




    Arriba

    No hay comentarios: