Les opérations ensemblistes

Un ensemble désigne une collection d’objets distincts. Un ensemble peut être vu comme une sorte de sac virtuel entourant ses éléments, ils peuvent être représentés à l’aide de diagrammes de Venn. Les éléments d’un ensemble ne sont pas spécialement ordonnés et il ne contient pas d’éléments dupliqués. Un même objet peut être élément de plusieurs ensembles. Par exemple : samedi est un élément de l’ensemble des jours de la semaine, mais également dans l’ensemble weekend.

Il est possible d’effectuer des opérations mathématiques sur les ensembles, le résultat est alors un autre ensemble. Les opérations élémentaires sont: la différence, l’union et l’intersection. Pour effectuer ces opérations, il est nécessaire de savoir si un élément appartient à un ensemble ou non. Deux ensembles sont égaux uniquement si tous leurs éléments sont communs.

Par exemple, l’ensemble A contient les éléments 1, 2, 3, 4 et l’ensemble B contient 3, 4, 5.

• ​\( 3 \in A \)​est vrai, alors que ​\( 5 \in A \)​est faux.
• ​\( A=B \)​est faux.
• ​\( A \setminus B \)​renvoi un ensemble de [1, 2]
• ​\( A \cup B \)​est l’ensemble de [1, 2, 3, 4, 5]
• ​\( A \cap B \)​correspond à l’ensemble [3, 4]

STRUCTURE ENSEMBLE:
   VARIABLE compteur: ENTIER
   VARIABLE tableau: TABLEAU DE N ENTIER
FIN STRUCTURE

Nous pouvons alors utiliser les ensembles comme ceci :

VARIABLE A, B: ENSEMBLE
A.compteur = 4
A.tableau[0] = 1
A.tableau[1] = 2
A.tableau[2] = 3
A.tableau[3] = 4

B.compteur = 3
B.tableau[0] = 3
B.tableau[1] = 4
B.tableau[2] = 5

Gardez à l’esprit que la variable compteur doit toujours informer l’utilisateur du nombre précis d’élément dans un ensemble. Par exemple, pour ajouter un élément à notre ensemble A, nous pouvons utiliser cette variable pour justement insérer l’élément suivant.

A.tableau[ A.compteur ] = 42
A.compteur = A.compteur + 1

Les ensembles non ordonnés

FONCTION UNORDERED_IN(A: ENSEMBLE, x: ENTIER)
    VARIABLE i: ENTIER
    POUR i DE 0 À A.compteur:
        SI A.tableau[i] == x:
            RETOURNER Vrai
        FIN SI
    FIN POUR
    RETOURNER Faux
FIN FONCTION

FONCTION UNORDERED_EQUAL(A: ENSEMBLE, B: ENSEMBLE)
    VARIABLE i: ENTIER

    SI A.compteur != B.compteur:
       RETOURNER Faux
    FIN SI

    POUR i DE 0 À A.compteur:
        SI UNORDERED_IN(B, A.tableau[i]) == Faux:
            RETOURNER Faux
        FIN SI
    FIN POUR
    RETOURNER Vrai
FIN FONCTION

FONCTION UNORDERED_UNION(A: ENSEMBLE, B: ENSEMBLE)
    VARIABLE i: ENTIER
    VARIABLE C: ENSEMBLE

    C.compteur <- 0
    POUR i DE 0 À A.compteur:
        SI UNORDERED_IN(B, A.tableau[i]) == Faux:
            C.tableau[ C.compteur ] <- A.tableau[i]
            C.compteur <- C.compteur + 1
        FIN SI
    FIN POUR
    POUR i DE 0 À B.compteur:
        C.tableau[ C.compteur ] <- B.tableau[i]
        C.compteur <- C.compteur + 1
    FIN POUR

    RETOURNER C
FIN FONCTION

FONCTION UNORDERED_INTERSECTION(A: ENSEMBLE, B: ENSEMBLE)
    VARIABLE i: ENTIER
    VARIABLE C: ENSEMBLE

    C.compteur <- 0
    POUR i DE 0 À A.compteur:
        SI UNORDERED_IN(B, A.tableau[i]) == Vrai:
            C.tableau[ C.compteur ] <- A.tableau[i]
            C.compteur <- C.compteur + 1
        FIN SI
    FIN POUR

    RETOURNER C
FIN FONCTION

FONCTION UNORDERED_DIFF(A: ENSEMBLE, B: ENSEMBLE)
    VARIABLE i: ENTIER
    VARIABLE C: ENSEMBLE

    C.compteur <- 0
    POUR i DE 0 À A.compteur:
        SI UNORDERED_IN(B, A.tableau[i]) == Faux:
            C.tableau[ C.compteur ] <- A.tableau[i]
            C.compteur <- C.compteur + 1
        FIN SI
    FIN POUR

    RETOURNER C
FIN FONCTION

Les ensembles ordonnés

FONCTION ORDERED_IN(A: ENSEMBLE, x: ENTIER)
    VARIABLE i: ENTIER
    i = 0
    TANT QUE i<A.compteur ET a.tableau[i] <= x:
        SI A.tableau[i] == x:
            RETOURNER Vrai
        FIN SI
        i <- i +1
    FIN POUR
    RETOURNER Faux
FIN FONCTION

FONCTION ORDERED_EQUALS(A: ENSEMBLE, B: ENSEMBLE)
    VARIABLE i: ENTIER

    SI A.compteur != B.compteur:
       RETOURNER Faux
    FIN SI

    POUR i DE 0 À A.compteur:
        SI A.tableau[i] != B.tableau[i]
            RETOURNER Faux
        FIN SI
    FIN POUR

    RETOURNER Vrai
FIN FONCTION

FONCTION ORDERED_UNION(A: ENSEMBLE, B: ENSEMBLE)
    VARIABLE i: ENTIER
    VARIABLE j: ENTIER
    VARIABLE C: ENSEMBLE

    i <- 0
    j <- 0
    C.compteur <- 0

    TANT QUE i < A.compteur ET j < B.compteur:
        SI A.tableau[i] < B.tableau[j]:
            C.tableau[ C.compteur ] <- A.tableau[i]
            C.compteur <- C.compteur + 1
            i <- i + 1
        SINON SI A.tableau[i] > B.tableau[j]:
            C.tableau[ C.compteur ] <- B.tableau[j]
            C.compteur <- C.compteur + 1
            j <- j + 1
        SINON
            C.tableau[ C.compteur ] <- B.tableau[j]
            C.compteur <- C.compteur + 1
            i <- i + 1
            j <- j + 1
        FIN SI
    FIN TANT QUE

    TANT QUE i < A.compteur
        C.tableau[ C.compteur ] <- A.tableau[i]
        C.compteur <- C.compteur + 1
        i <- i + 1
    FIN TANT QUE

    TANT QUE j < B.compteur
        C.tableau[ C.compteur ] <- B.tableau[j]
        C.compteur <- C.compteur + 1
        j <- j + 1
    FIN TANT QUE

    RETOURNER C
FIN FONCTION

FONCTION ORDERED_INTERSECTION(A: ENSEMBLE, B: ENSEMBLE)
    VARIABLE i: ENTIER
    VARIABLE j: ENTIER
    VARIABLE C: ENSEMBLE

    i <- 0
    j <- 0
    C.compteur <- 0

    TANT QUE i < A.compteur ET j < B.compteur:
        SI A.tableau[i] < B.tableau[j]:
            i <- i + 1
        SINON SI A.tableau[i] > B.tableau[j]:
            j <- j + 1
        SINON
            C.tableau[ C.compteur ] <- B.tableau[j]
            C.compteur <- C.compteur + 1
            i <- i + 1
            j <- j + 1
        FIN SI
    FIN TANT QUE

    RETOURNER C
FIN FONCTION

FONCTION ORDERED_DIFF(A: ENSEMBLE, B: ENSEMBLE)
    VARIABLE i: ENTIER
    VARIABLE j: ENTIER
    VARIABLE C: ENSEMBLE

    i <- 0
    j <- 0
    C.compteur <- 0

    TANT QUE i < A.compteur ET j < B.compteur:
        SI A.tableau[i] < B.tableau[j]:
            C.tableau[ C.compteur ] <- A.tableau[i]
            C.compteur <- C.compteur + 1
            i <- i + 1
        SINON SI A.tableau[i] > B.tableau[j]:
            j <- j + 1
        SINON
            i <- i + 1
            j <- j + 1
        FIN SI
    FIN TANT QUE

    TANT QUE i < A.compteur
        C.tableau[ C.compteur ] <- A.tableau[i]
        C.compteur <- C.compteur + 1
        i <- i + 1
    FIN TANT QUE

    RETOURNER C
FIN FONCTION