Représentation de l'ensemble vide

Bonjour,

Je définie actuellement des classes pour des structures algébriques élémentaires (ensemble, groupe, anneau, corps). Je suis confronté à la problématique de la représentation de l'ensemble vide.

Par exemple, mon groupe possède une méthode qui permet de vérifier l'existence d'un élément neutre.
Sur l'ensemble des entiers relatifs muni de l'addition la méthode renvoie bien sûr 0 (zéro). Mais si je tente de former un groupe qui n'a pas d'élément neutre qu'est-ce que ma méthode est sensée renvoyer ?

Merci d'avance pour vos éléments de réponse.

[edit] ERRATUM: élément nul -> élément neutre [/edit]

hello,

si ton ensemble est vide, il ne contient pas d'élément, donc pas d'élément neutre...
Donc si tu demandes s'il a un élément neutre, je dirais qu'on attend pour réponse faux.

Après ta question ne concerne pas tellement du C++ mais plus des maths

bonjour,
si tu es dans le cas d'une fonction qui renvoie un élément unique s'il existe, la bonne valeur de retour est, non pas faux (qui ne peut pas être la réponse à la question "quel est l'élément neutre") mais indéfini. Si tu renvoie ta réponse par pointeur la bonne réponse est nullptr. Si tu travailles à l'aide de smart-pointers (comme recommandé pour éviter les problèmes de gestion de la mémoire), tu renvoies un smart pointer (ex: std:unique_ptr) valide dans le cas défini, non valide si l'élément neutre n'est pas défini. Cela laisse à l'appelant la nécessité de vérifier la validité du pointeur ou smart-pointer pour savoir s'il peu utiliser l'élément neutre.

Citation:

---

si tu es dans le cas d'une fonction qui renvoie un élément unique s'il existe, la bonne valeur de retour est, non pas faux (qui ne peut pas être la réponse à la question "quel est l'élément neutre") mais indéfini.

---

je crois qu'on parle pas de la même méthode.

Etant le seul à avoir écrit faux, je suppose que tu me reprends.
Ma ligne est pourtant claire, je parle du retour de la fonction
bool yaTilUnElementNeutre()

Quant au retour de getElementNeutre(), ca dépend du type retourné :).
Si c'est un Element, ptet bien retourner un Element qu'on peut identifier invalide (un peu comme string::npos retourne un index qu'on sait que rien n'est trouvé)

Salut,

Citation:

---

Envoyé par Tymk

Bonjour,

Je définie actuellement des classes pour des structures algébriques élémentaires (ensemble, groupe, anneau, corps). Je suis confronté à la problématique de la représentation de l'ensemble vide.

Par exemple, mon groupe possède une méthode qui permet de vérifier l'existence d'un élément neutre.
Sur l'ensemble des entiers relatifs muni de l'addition la méthode renvoie bien sûr 0 (zéro). Mais si je tente de former un groupe qui n'a pas d'élément nul qu'est-ce que ma méthode est sensée renvoyer ?

---

Ben, 0, que voudrais tu que la fonction renvoie d'autre :question: (je présume que tu voulais dire "Mais si je tente de former un groupe qui n'a pas d'élément nul neutre" :question:)

Par contre, au niveau de ta classe Ensemble, il y a très certainement quelque chose à faire afin de permettre à l'utilisateur de cette classe de savoir si un ensemble donné est vide ou non.

Cela prendra sans doute la forme d'une fonction bool isEmpty() (ou similaire) qui renverra true si le nombre d'éléments contenus par ton ensemble est égal à 0 et false si ton ensemble contient un élément ou plus ;)

Bonjour,

La manière dont j'ai exposé mon problème prête à confusion.

Ma problématique est de savoir comment en C++ je peux représenter l'ensemble vide en tant que valeur retour de ma méthode.
Dans ce cas, mon ensemble n'est pas vide mais il ne comporte pas d'élément neutre. Ma méthode trouver_élément_neutre() doit donc retourner "rien". Ce qui correspond mathématiquement à l'ensemble vide.

Je ne suis pas sûr de la manière de procéder. Je peux rajouter un élément "spécial" à mon ensemble. Comme par exemple renvoyer une valeur supérieure à l'élément le plus grand de mon ensemble (je travaille sur des ensembles finis).
Cela me paraît être une bonne technique pour me compliquer la vie et écrire des conneries dans la suite de mon programme...

L'approche par les pointeurs tel que le conseil therwald me paraît déjà plus adaptée.

Citation:

---

Ma méthode trouver_élément_neutre() doit donc retourner "rien". Ce qui correspond mathématiquement à l'ensemble vide.

---

Conceptuellement c'est faux.

Un élement neutre, ce n'est pas un ensemble. (sauf si tu as un ensemble d'ensembles...).

Donc quand tu retournes un element qu'il soit neutre, ou pas, tu retournes pas un ensemble mais un élément.

Maintenant, si tu veux retourner un element vide, ben retournes le.
Que tu checkes ton élément retourné par Element::notValid, ou bien Element==NULL dans le cas d'un pointeur, c'est pareil, il faut que tu checkes.

A choisir, j'éviterais les pointeurs qui n'ont rien de justifié jusqu'à présent.

Au lieu de faire ta méthode qui doit gérer le cas de l'élément neutre qui n'existe pas, tu ferais mieux d'imposer à ton appelant de checker l'existence de l'élément avant de faire l'appel de la fonction!
De toute façon il doit le checker, autant lui proposer une méthode lui permettant de checker avant.

Bonsoir,

ou bien une méthode du type bool GetNeutral(Element& _neutre); peut être intéressante

Citation:

---

Envoyé par galerien69

Maintenant, si tu veux retourner un element vide, ben retournes le.
Que tu checkes ton élément retourné par Element::notValid, ou bien Element==NULL dans le cas d'un pointeur, c'est pareil, il faut que tu checkes.

A choisir, j'éviterais les pointeurs qui n'ont rien de justifié jusqu'à présent.

---

Certes. Mais je ne vois pas vraiment comment m'en sortir sans utiliser de pointeur. Dans un premier temps je travaille sur un ensemble d'entier et je ne sais pas comment représenter cet état "notValid" avec des unsigned int.

Citation:

---

Envoyé par galerien69

Au lieu de faire ta méthode qui doit gérer le cas de l'élément neutre qui n'existe pas, tu ferais mieux d'imposer à ton appelant de checker l'existence de l'élément avant de faire l'appel de la fonction!
De toute façon il doit le checker, autant lui proposer une méthode lui permettant de checker avant.

---

Oui. Mais, pour vérifier l'existence d'un élément neutre, je n'ai pas trouvé mieux que de faire une recherche exhaustive jusqu'à mettre la main sur un élément qui satisfasse aux conditions. Comme cette opération est coûteuse en ressource j'en profite pour retourner cet élément et ainsi éviter de relancer une recherche ultérieurement.
Une autre approche pourrait être de retourner un booléen tout en stockant la valeur (ou le pointeur) de l'élément neutre quand je le trouve.

Quelque chose dans le genre de ce que Bousk suggère : (avec p le nombre d'éléments de l'ensemble et add() la loi de composition)

Code:

---

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

bool GROUPE::cherche_neutre () { // £e € E, Va € E e*a = a*e = a for (unsigned int e=0; e <= p; e++) { if ( test_neutre(e) == true ) { this->elt_neutre = e; return true; } } return false; // pas d'élément neutre }   bool GROUPE::test_neutre (unsigned int e) { for (unsigned int a=0; a <= p; a++) { if ( add(e, a) != a || add(a, e) != a ) return false; } return true; }

---

Dans ce cas, le membre elt_neutre serait initialisé à NULL dans le cas d'un pointeur. Et je ne vois pas comment faire autrement que d'utiliser un pointeur.

Citation:

---

Envoyé par galerien69

Conceptuellement c'est faux.

Un élement neutre, ce n'est pas un ensemble. (sauf si tu as un ensemble d'ensembles...).

---

Je ne vois pas bien où est le problème de concept. Tout élément peut être vu comme un singleton et donc un ensemble. A terme, je vais justement être obligé de retourner des sous-ensembles pour traiter le cas où mon groupe admettrait plusieurs éléments neutres.

Citation:

---

Envoyé par Tymk

Certes. Mais je ne vois pas vraiment comment m'en sortir sans utiliser de pointeur. Dans un premier temps je travaille sur un ensemble d'entier et je ne sais pas comment représenter cet état "notValid" avec des unsigned int.

---

En te basant sur le principe du "null object" dont j'ai parlé plus haut ;)

En fait, tu dois penser en termes des services rendus par ton éléments.

Un élément nul est un élément qui répondra à toutes les questions en donnant une valeur connue comme invalide.
Un élément d'ensemble devra, typiquement, répondre à au moins trois questions:

1. Quelle est ta valeur :question: dont la réponse sera du type envisagé pour ton ensemble (valeur numérique entière ou valeur numérique "réelle)
2. Es tu l'élément neutre :question: dont la réponse est un booléen
3. Es-tu valide (comprends : peux tu faire partie de l'ensemble duquel on t'a sorti):question: dont la réponse sera également un booléen.
4. Es-tu égal à un autre élément :question:

Un objet nul renverrait, par exemple std::limits<int>::max() (si sa valeur est évaluée sous la forme d'entiers) à la première question, false à la deuxième (car ce n'est surement pas l'élément neutre) et false à la troisième (parce que tu auras compris qu'il doit représenter quelque chose d'invalide).

Pour la quatrième question, l'objet nul répondra "true" s'il est comparé à un autre objet nul (à un autre objet qui répond "false" quand on lui demande s'il est valide) et false dans tous les autres cas.

Un objet non nul répondra pour sa part "true" s'il est en présence d'un autre objet non nul identique ;)

Tu peux très bien garder un élément qui fournira ces réponses sous la forme d'un membre de ta classe.

Cet objet serait:

• constant car il ne faut en aucun cas permettre qu'il soit modifié d'une quelconque manière
• statique parce qu'il sera commun à tous les ensemble de même type, mais aussi parce qu'il servira "d'étalon" pour savoir si un élément a été trouvé ou non (on peut donc vouloir s'en servir sans avoir d'ensemble auquel le demander)
• public parce qu'il n'y a pas forcément d'intérêt à le placer dans l'accessibilité privée si c'est pour, de toutes manières, fournir une fonction statique qui le renverrait ;)

A chaque fois que tu est confronté à une recherche qui n'a donné aucun résultat, tu renvoies, tout simplement, cet objet nul ;)

Citation:

---

Oui. Mais, pour vérifier l'existence d'un élément neutre, je n'ai pas trouvé mieux que de faire une recherche exhaustive jusqu'à mettre la main sur un élément qui satisfasse aux conditions. Comme cette opération est coûteuse en ressource j'en profite pour retourner cet élément et ainsi éviter de relancer une recherche ultérieurement.

---

C'est l'une des manières que tu peux envisager ;)

Une autre solution, facilitée par l'existence de l'objet nul pourrait, selon l'utilisation que tu prévois de tes ensemble, de mettre "en cache" la présence (ou l'absence) de l'élément neutre.

Plutôt que de chercher systématiquement parmi tous les éléments de ton ensemble si tu y trouves l'élément neutre à chaque fois que tu en as besoin, tu pourrais tout aussi bien vérifier si l'élément que tu rajoutes dans ton ensemble est l'élément neutre ou non et, si c'est l'élément neutre, l'utiliser pour mettre à jour une variable membre qui serait dédiée au maintien de cet élément

Quand tu crées ton ensemble vide, cette variable membre prendrait les mêmes valeurs que l'objet nul, parce que l'élément neutre n'existe forcément pas.

Si, durant les manipulations que tu fais subir à ton ensemble, tu rajoutes l'élément neutre, il te suffira de mettre la variable membre à jour (et, pourquoi pas, faire en sorte d'éviter les tests sur les prochains éléments que tu ajouteras) ;)

Cela rendra l'ajout de nouveaux éléments un peu plus lent, mais cela aura l'énorme bénéfice de permettre un accès constant à l'élément neutre, qu'il existe ou non.

C'est pour cela que je te disais qu'il faut voir la manière dont tu envisages l'utilisation de tes ensembles! La mise en cache sera intéressante si tu fais peu d'ajouts à tes ensembles pour beaucoup de recherches, alors qu'elle sera plutôt contre productive si tu fais beaucoup d'ajouts pour peu de recherches ;)

Citation:

---

Une autre approche pourrait être de retourner un booléen tout en stockant la valeur (ou le pointeur) de l'élément neutre quand je le trouve.

---

Ou alors, tu commences à réfléchir en terme des services que tu attends de la part de tes ensembles!

Si l'on réfléchit aux services associés à la présence (ou à l'absence) d'un élément neutre, tu es en droit d'attendre deux services distincts de la part de ton ensembles:

Le premier te permet de récupérer l'élément neutre s'il existe (autrement, il renvoie... l'objet nul), alors que le second devrait te permettre d'interroger ton ensemble pour savoir si, oui ou non, il dispose d'un élément neutre.

Cela se traduirait, en gros, par la présence de deux fonctions distinctes que l'on pourrait appeler findNeutralElement() et hasNeutralElement().

La première renverrait l'élément neutre (s'il existe) et la seconde renverrait un booléen qui répond à la question.

Mais il n'y a strictement rien qui t'interdit de baser le comportement de hasNeutralElement sur le résultat renvoyé par findNeutralElement si tu restes sur le principe de rechercher l'élément neutre à chaque fois que tu en as besoin, surtout, si tu dispose de l'objet nul ;)

Citation:

---

Quelque chose dans le genre de ce que Bousk suggère : (avec p le nombre d'éléments de l'ensemble et add() la loi de composition)

Code:

---

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

bool GROUPE::cherche_neutre () { // £e € E, Va € E e*a = a*e = a for (unsigned int e=0; e <= p; e++) { if ( test_neutre(e) == true ) { this->elt_neutre = e; return true; } } return false; // pas d'élément neutre }   bool GROUPE::test_neutre (unsigned int e) { for (unsigned int a=0; a <= p; a++) { if ( add(e, a) != a || add(a, e) != a ) return false; } return true; }

---

Dans ce cas, le membre elt_neutre serait initialisé à NULL dans le cas d'un pointeur. Et je ne vois pas comment faire autrement que d'utiliser un pointeur.

---

Avec le principe de l'objet nul, cela devient possible elt_neutre prend, par défaut, les valeurs correspondant à l'objet nul et prend les valeurs qui vont bien dés qu'il existe un élément neutre :D

Citation:

---

Je ne vois pas bien où est le problème de concept. Tout élément peut être vu comme un singleton et donc un ensemble. A terme, je vais justement être obligé de retourner des sous-ensembles pour traiter le cas où mon groupe admettrait plusieurs éléments neutres.

---

Ah non!!!

En tout cas, pas dans l'acception informatique du terme.

Chaque élément est unique dans un ensemble, mais le terme de singleton, lorsqu'on parle informatique un principe (plustot mal aimé :D) qui permet de s'assurer que quoi qu'il arrive, il n'y aura jamais qu'une et une seule instance d'un objet d'un type donné.

Et le problème conceptuel vient du fait que tu es en réalité face à deux notions bien particulières que sont la notion d'ensemble et la notion d'éléments.

La première représente "le contenant" (le "bocal") alors que la seconde représente "le contenu" (les bonbons qui sont dans le bocal).

Lorsque tu recherches un bonbon donné, tu peux envisager de renvoyer un nouveau bocal qui contiendra tous les bonbons que tu as sélectionnés (ou peut être aucun si tu n'as pas trouvé ton bonheur), mais tu ne peux, conceptuellement parlant (en informatique en tout cas) pas envisager de remplir un bocal avec d'autres bocaux (sauf si tu as un ensemble de bocaux :D).

Hé oui, l'informatique a beau être très fortement basée sur les théories mathématiques, elle présente parfois quelques règles qui rendent certaines théories mathématique inapplicables :D

Citation:

---

Envoyé par Tymk

Je ne vois pas bien où est le problème de concept. Tout élément peut être vu comme un singleton et donc un ensemble. A terme, je vais justement être obligé de retourner des sous-ensembles pour traiter le cas où mon groupe admettrait plusieurs éléments neutres.

---

Par contre, dans ce cas, tu peux tout simplement partir dès le début sur le fait de renvoyer une collection d'éléments, si conceptuellement la notion de plusieurs éléments neutres est valide (je suis quelque peu rouillé avec la théorie des ensembles, qui date pour moi de la terminale...presque 20 ans en arrière). L'intérêt? Dans ce cas tu codera tout naturellement l'absence d'élément neutre par une collection de taille 0.
Alors le 'check' est simple: pas d'élément neutre <=> taille 0 de l'ensemble des éléments neutres. Rien ne t'empêche bien sûr de proposer une fonction qui fasse ce test et renvoie un booléen pour simplifier les écritures. Pour ce qui est de cacher le résultat, comme c'est "de la tambouille interne" rien ne t'interdit de fonctionner sur un pointeur ou une autre solution si tu la préfères, ce sera encapsulé, donc pas d'impact pour le code client.

Citation:

---

où mon groupe admettrait plusieurs éléments neutres.

---

mm soit a et b deux elements neutre pour la même loi.
si b est neutre alors qqsoit x,
add(x,b)=x
en particulier add(a,b)=a

si a est neutre alors qq soit x,
add(a,x)=x
en particulier add(a,b)=b

donc a=b.

Je ne compte qu'un élément neutre...
Et je ne vois pas l'intérêt de retourner une liste d'élément neutres qui sont neutres pour des lois différentes. A quoi sert un élément neutre si tu sais pas pour quelle loi il est neutre?

Je me suis arrêté à la définition d'un groupe et l'unicité de l'élément neutre n'est pas exigé.
Effectivement en y réfléchissant un peu plus son implication est plutôt triviale.

Merci. Ca m'évitera du code complètement inutile.

Pour le reste, je parts sur l'explication très détaillée de koala01.

Merci à tous.

http://fr.wikipedia.org/wiki/Groupe_...m.C3.A9triques

Parfois, dans la STL, est retournée une paire où le premier élément est un booléen et le second élément une valeur. Le second élément n'a de sens que si si le premier est à true.