Conjuntos/Bolsas

📖

Un conjunto es una estructura de datos de acceso inmediato

Sin repeticiones (en la bolsa si puede)

No ordenado

Estos son representados en un lenguaje como los indices de un array, y el dato es el valor de dicho índice

💡

La diferencia entre los conjuntos y las bolsas que que los conjuntos toman valores booleanos mientras que las bolsas pueden toman como valor un tipo de dato numérico que representa el valor/cardinalidad/multiplicidad de dicho elemento en la bolsa

Operaciones

Pertenece

Añadir/Sacar

Intersección, Unión o Diferencia

Especificación

Tipos externos
TElemento

Tipos propios
TConjunto
TBolsa

Operaciones
Constructoras generadoras
crearConjuntoVacio → TConjunto
anadir: TConjunto X TElemento → TConjunto
Observadoras selectoras
(parcial) consulta: TConjunto → TElemento
Observadoras no selectoras
esConjuntoVacio: TConjunto → Boolean
pertenece: TConjunto X TElemento → Boolean
esSubconjunto: TConjunto X TConjunto → Boolean
cardinal: TConjunto → Integer
multiplicidad: TBolsa → Integer
Constructora no generadora
quitar: TConjunto X TElemento → TConjunto
union: TConjunto X TConjunto → TConjunto
interseccion: TConjunto X TConjunto → TConjunto
diferencia: TConjunto X TConjunto → TConjunto

Ecuaciones de definitud
DEF ( consulta(Poner(c, i)) )

Variables
c , c<N> , conjunto → TConjunto
i , j , e , e<N> → TElemento

Ecuaciones
Observadoras no selectoras
esConjuntoVacio
esConjuntoVacio(crearConjuntoVacio) = True
esConjuntovacio(Poner(conjunto, i)) = False
pertenece
pertenece(crearConjuntoVacio, i) = False
pertenece(poner(cº, i), j) = (i = j) || pertenece(c, j)
esSubconjunto
esSubconjunto(crearConjuntoVacio, c2) = True
esSubconjunto(poner(c, i), c2) = pertenece(c2, i) && esSubconjunto(c, c2)
cardinal
cardinal(crearConjuntoVacio) = 0
cardinal(poner(c, i)) = SI pertenece(c, i) → ( cardinal(c) ) || ( 1 + cardinal(c) )
Constructoras no generadoras
quitar
quitar(crearConjuntoVacio, j) = crearConjuntoVacio
quitar(poner(c, i), j) = SI ( i = j) → ( quitar(c, j) ) || ( poner(quitar(c, j), i) )
union
union(crearConjuntoVacio, c2) = c2
union(poner(c1, i), c2) = poner(union(c1, c2), i)
interseccion
interseccion(crearConjuntoVacio, c2) = crearConjuntoVacio
interseccion(poner(c1, i), c2) = SI pertenece(c2, i) → ( poner(interseccion(c1, c2), i) ) || ( interseccion(c1, c2) )
diferencia
diferencia(c, crearConjuntoVacio) = c
diferencia(c1, poner(c2, i)) = diferencia(quitar(c1, i), c2)

Unidad Conjuntos

unit uConjunto;
    
interface
    
    uses uElemento

    type
        TConjunto = array[TElemento] of boolean;

implementation
    
    procedure crearVacio(var c:TConjunto); 
    var i:TElemento;
    begin
        for i:=INI to FIN do c[i] := False;
    end;


    procedure poner(var c:TConjunto; e:TElemento); begin
        c[e] := True;
    end;


    procedure quitar(var c:TConjunto; e:TElemento); begin
        c[e] := False;
    end;


    function pertenece(var c:TConjunto; e:TElemento):boolean; begin
        pertenece := c[e];
    end;


    procedure union(var u:TConjunto; var c1, c2:TConjunto);
    var i:TElemento;
    begin
        for i:=INI to FIN do u[i] := c1[i] or c2[i];
    end;


    procedure interseccion(var u:TConjunto; var c1, c2:TConjunto);
    var i:TElemento;
    begin
        for i:=INI to FIN do u[i] := c1[i] and c2[i];
    end;


    procedure diferencia(var u:TConjunto; var c1, c2:TConjunto);
    var i:TElemento;
    begin
        for i:=INI to FIN do u[i] := c1[i] and (not c2[i]);
    end;

end.

unit uElemento;
    
interface
    
    const
        INI = 1;
        FIN = 10;

    type
        TElemento = INI..FIN;
    
implementation
    
end.

Unidad Bolsas

unit uBolsa;
    
interface
    uses uElemento
    type
        TBolsa = array[TElemento] of integer;
implementation
    

    procedure crearVacio(var b:TBolsa); 
    var i:TElemento;
    begin
        for i:=INI to FIN do b[i] := 0;
    end;


    procedure poner(var b:TBolsa; e:TElemento); begin
        b[e] := b[e]+1;
    end;


    procedure quitar(var b:TBolsa; e:TElemento); begin
        b[e] := b[e]-1;
    end;


    function pertenece(var b:TBolsa; e:TElemento):boolean; begin
        pertenece := b[e] > 0;
    end;


    function multiplicidad(var b:TBolsa; e:TElemento):integer; begin
        pertenece := b[e];
    end;


    procedure union(var u:TBolsa; var b1, b2:TBolsa);
    var i:TElemento;
    begin
        for i:=INI to FIN do u[i] := b1[i] + b2[i];
    end;


    procedure interseccion(var u:TBolsa; var b1, b2:TBolsa);
    var i:TElemento;
    begin
        for i:=INI to FIN do u[i] := min(b1[i] and b2[i]);  // Definir min()
    end;


    procedure diferencia(var u:TBolsa; var b1, b2:TBolsa);
    var i:TElemento;
    begin
        for i:=INI to FIN do u[i] := b1[i] - b2[i];
    end;

end.

unit uElemento;
    
interface
    const
        INI = 1;
        FIN = 10;
    type
        TElemento = INI..FIN;
implementation
    
end.