La gestion des ensembles
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.
- : Vrai, : Faux
- : Faux
- : [1, 2]
- : [1, 2, 3, 4, 5]
- : [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
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é.
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.
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.
FONCTION UNORDERED_UNION(A: ENSEMBLE, B: ENSEMBLE) VARIABLE i: ENTIER VARIABLE C: ENSEMBLE C.compteur <- 0 POUR i DE 0 À A.compteur-1: 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 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.
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.
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é.
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.
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.
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 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.
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 TANT QUE RETOURNER C FIN FONCTION
- Écrivez une fonction qui effectue la différence de deux ensembles ordonnés.
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 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
- kossolax
- Last Edited
- Feb 10 2021, 7:24 PM