Page MenuHomePhabricator

La gestion des ensembles
Updated 3 Days AgoPublic

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.

  • 3A3 \in A: Vrai, 5A5 \in A: Faux
  • A=BA=B: Faux
  • ABA \setminus B: [1, 2]
  • ABA \cup B: [1, 2, 3, 4, 5]
  • ABA \cap B: [3, 4]

    La plupart des langages de programmation proposent de gérer les ensembles directement dans le langage. Toutefois, il est important de comprendre leurs coûts réels ainsi que leurs fonctionnements. Pour ce cours, considérons la structure de données suivante :
STRUCTURE ENSEMBLE:
   VARIABLE compteur: ENTIER
   VARIABLE tableau: TABLEAU DE N ENTIER
FIN STRUCTURE
Remarquez que pour l'instant, il n'est pas possible d'augmenter la taille d'un tableau de façon dynamique. Nous devons donc borner nos ensembles à une valeur finie. Pour ce faire, préfixer N à une valeur maximum autorisée d'élément, même si votre ensemble ne contient qu'un seul élément.

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

Non ordonné

  • Écrivez une fonction qui détermine si un élément d'une valeur donnée appartient ou non à un ensemble non-ordonné.
UNORDERED_IN
FONCTION UNORDERED_IN(A: ENSEMBLE, x: ENTIER)
    VARIABLE i: ENTIER
    POUR i DE 0 À A.compteur-1:
        SI A.tableau[i] == x:
            RETOURNER Vrai
        FIN SI
    FIN POUR
    RETOURNER Faux
FIN FONCTION
  • Écrivez une fonction qui détermine si deux ensembles non-ordonnés sont égaux.
UNORDERED_EQUAL
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-1:
        SI UNORDERED_IN(B, A.tableau[i]) == Faux:
            RETOURNER Faux
        FIN SI
    FIN POUR
    RETOURNER Vrai
FIN FONCTION
  • Écrivez une fonction qui effectue l'union de deux ensembles non-ordonnés.
UNORDERED_UNION
FONCTION UNORDERED_UNION(A: ENSEMBLE, B: ENSEMBLE)
    VARIABLE i: ENTIER
    VARIABLE C: ENSEMBLE

    C.compteur <- 0
    POUR i DE 0 À A.compteur-1:
        C.tableau[ C.compteur ] <- A.tableau[i]
        C.compteur <- C.compteur + 1
    FIN POUR
    POUR i DE 0 À B.compteur-1:
        C.tableau[ C.compteur ] <- B.tableau[i]
        C.compteur <- C.compteur + 1
    FIN POUR

    RETOURNER C
FIN FONCTION
  • Écrivez une fonction qui effectue l'intersection de deux ensembles non-ordonnés.
UNORDERED_INTERSECTION
FONCTION UNORDERED_INTERSECTION(A: ENSEMBLE, B: ENSEMBLE)
    VARIABLE i: ENTIER
    VARIABLE C: ENSEMBLE

    C.compteur <- 0
    POUR i DE 0 À A.compteur-1:
        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
  • Écrivez une fonction qui effectue la différence de deux ensembles non-ordonnés.
UNORDERED_DIFF
FONCTION UNORDERED_DIFF(A: ENSEMBLE, B: ENSEMBLE)
    VARIABLE i: ENTIER
    VARIABLE C: ENSEMBLE

    C.compteur <- 0
    POUR i DE 0 À A.compteur-1:
        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

Ordonné

Les fonctions que nous avons écrites précédemment peuvent être modifiées pour tenir compte de l'ordre des ensembles. Nous obtenons ainsi une amélioration notable dans la vitesse d'exécution, mais ces algorithmes sont un peu plus compliqués à écrire. L'astuce est de comparer, pas à pas, les deux ensembles simultanément pendant l'évaluation.

  • Écrivez une fonction qui détermine si un élément d'une valeur donnée appartient ou non à un ensemble ordonné.
ORDERED_IN
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
  • Écrivez une fonction qui détermine si deux ensembles ordonnés sont égaux.
ORDERED_EQUALS
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-1:
        SI A.tableau[i] != B.tableau[i]
            RETOURNER Faux
        FIN SI
    FIN POUR

    RETOURNER Vrai
FIN FONCTION
  • Écrivez une fonction qui effectue l'union de deux ensembles ordonnés.
ORDERED_UNION
FONCTION ORDERED_UNION(A: ENSEMBLE, B: ENSEMBLE)
    VARIABLE i: ENTIER
    VARIABLE j: ENTIER
    VARIABLE C: ENSEMBLE

    i <- 0
    j <- 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 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
  • Écrivez une fonction qui effectue l'intersection de deux ensembles ordonnés.
ORDERED_INTERSECTION
FONCTION ORDERED_INTERSECTION(A: ENSEMBLE, B: ENSEMBLE)
    VARIABLE i: ENTIER
    VARIABLE j: ENTIER
    VARIABLE C: ENSEMBLE

    i <- 0
    j <- 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 TANT QUE

    RETOURNER C
FIN FONCTION
  • Écrivez une fonction qui effectue la différence de deux ensembles ordonnés.
ORDERED_DIFF
FONCTION ORDERED_DIFF(A: ENSEMBLE, B: ENSEMBLE)
    VARIABLE i: ENTIER
    VARIABLE j: ENTIER
    VARIABLE C: ENSEMBLE

    i <- 0
    j <- 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
            i <- i + 1
            j <- j + 1
    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
Last Author
Steve
Last Edited
Sun, Jan 24, 12:17 PM

Event Timeline

Steve moved this document from Ensembles.Thu, Jan 7, 9:59 AM
Steve edited the content of this document. (Show Details)Thu, Jan 7, 10:27 AM
Steve edited the content of this document. (Show Details)Thu, Jan 7, 4:19 PM
Steve edited the content of this document. (Show Details)Thu, Jan 7, 4:39 PM
Steve edited the content of this document. (Show Details)
Steve edited the content of this document. (Show Details)Thu, Jan 7, 4:54 PM
Steve edited the content of this document. (Show Details)Thu, Jan 7, 5:03 PM
Steve edited the content of this document. (Show Details)Thu, Jan 7, 5:08 PM
Steve edited the content of this document. (Show Details)Thu, Jan 7, 5:11 PM
Steve edited the content of this document. (Show Details)
Steve changed the title from Ensembles to La gestion des ensembles.Thu, Jan 7, 5:26 PM
Steve edited the content of this document. (Show Details)Thu, Jan 7, 7:35 PM
Steve edited the content of this document. (Show Details)
Steve edited the content of this document. (Show Details)Thu, Jan 14, 6:18 PM
Steve edited the content of this document. (Show Details)Mon, Jan 18, 2:39 PM
Steve edited the content of this document. (Show Details)Sun, Jan 24, 12:17 PM
Steve published a new version of this document.