Inscription / Connexion Nouveau Sujet
Relations d'ordre
Bonsoir,
j'aimerais savoir comment dénombrer les relations d'ordres en général (pas forcément totale). Par exemple sur un ensemble à 4 éléments comment faire pour ne pas en rater une?
Merci bien et bonne soirée.
Bonsoir,
une relation d'ordre sur E est une partie de E² qui vérifie certaines propriétés.
Pour un ensemble à 4 éléments il suffit de vérifier 65 536 cas.
Merci bien.
Juste pour être sur, lorsqu'on me dit de donner le nombre de relations d'ordre sur l'ensemble P({ {1,2,3} }) par exemple, il s'agit bien de trouver les relations d'ordres de {1,2,3} ?
Bonjour,
est un ensemble à deux éléments.
En effet, c'est l'ensemble des parties de l'ensemble , ensemble qui contient lui-même un seul élément, à savoir
.
Plus précisément :
Il s'agit donc de dénombrer les relations d'ordre sur cet ensemble à deux éléments...
Dites, comment vous faîtes pour dénombrer le nombre de relations d'ordre possible d'un ensemble à n éléments ?
Parce que je ne connais pas de formule qui me donne ça ... ?
Il n'y a pas de formule générale pour compter le nombre d'ordres partiels sur un ensemble à n éléments. Il semble que la réponse ne soit explicitement connue que jusqu'à n=18.
Pour n=4, il y a 219 ordres partiels.
Référence : OEIS 
Je vois ...
Assez étonnant les résultats ... Bref, je vais essayer de creuser un peu le sujet de mon côté ...
Merci 
Bonsoir,
amateur75
j'aimerais savoir comment dénombrer les relations d'ordres en général (pas forcément totale). Par exemple sur un ensemble à 4 éléments comment faire pour ne pas en rater une?
Le problème que tu te poses est à classer dans la théorie des graphes avec le vocabulaire adéquat. Une relation d'ordre sur un ensemble sur un ensemble
L'idée de base de mon algorithme est:
1) Construire une relation d'ordre total notée
2) Prendre une partie
Quand je dis ajouter un élément
a) insérer avant un élément y: c'est à dire je pose x\le y et x n'est pas comparable aux éléments précédents y.
b) insérer après un élément y: c'est à dire je pose y\le x et x n'est pas comparable aux éléments suivants y.
c) insérer entre deux éléments y et z, y\le z: c'est à dire je pose y\le x\le z, x n'est pas comparable aux éléments compris entre y et z (s'il y en a).
Les insertions à exclure sont celles qui donnent un ordre total:
i) insérer x avant le 1er élément de F_k
ii) insérer x après le derneir élément de F_k
iii) insérer x entre 2 éléments y et z consécutifs de F_k
Quand toutes les insertions sont faites, on ajoute à F_k tous les éléments de son complémentaire comme éléments comparables uniquement à eux-mêmes, on a alors muni E d'un relation d'ordre partiel.
3)
4) Reprendre tous
aprée un élen . je
Click intempestif. sur "POSTER"
3) Pour l'ajout du 2ème, reprendre les parties ainsi construites et insérer le 2ème élément sans précaution particulière, l'ordre sera partiel.
Ayant fini l'insertion, on ajoute à K_{k+1} les éléments restants de son complémentaire comme éléments comparables uniquement à eux-mêmes.
.....
n-k) A cette étape, il restera un seul élément à ajouter, on fera toutes les insertions possibles, chaque insertion donne un ensemble E ordonné.
n-k+1), on complétera la construction en prenant E muni de la structure d'ordre totale initiale, ce qu'on pouvait faire depuis mais c'est trop tard pour la correction.
PS:
1) Vérifier à chaque étape 2) que le choisi n'a pas été déjà utilisé avant,
peut hériter d'une même relation structure d'ordre total à partir de 2 relations d'ordre total distinctes de E,
2) Il y a certains points à détailler : algorithme d'insertion des éléments.
3) On peut à posteriori supprimer les structures en double.
4) Cet algorithme donne-t-il toutes les relations d''ordre sur E.
Merci à tous pour ces réponses.
@ delta-B je vais regarder tout ça quand j'aurais un peu de temps (notamment la théorie des graphes).
Bonne journée à tous.
Je ne pense pas que ce qu'écrit delta-B puisse mener à grand chose d'utile pour l'énumération des relations d'ordre.
Bonjour.
@ Robot
Je n'ai jamais dit que ce j'ai proposé donnait la solution, j'ai même précisé qu'il y avait des lacunes à combler et dans ce cas mais elle donnera au moins une minoration du nombre de relation d'ordre qu'on peut construire sur E.
As-tu quelque chose de mieux à proposer?
PS: je pensais à l'utilisation d'un SGBD pour son implémentation sur machines.
Le lien que j'ai mis montre que c'est un problème énumératif bien costaud. S'il y avait un algorithme pas trop compliqué, on ne serait certainement pas coincé à .
Bonsoir.
Le lien que tu as donné contient des références dont la plus récente date de 2000 sauf une qui n'est pas précisée. Quels algorithmes et moyens informatiques a-t-on utilisés. C'est-on intéressé depuis au problème. Vu les résultats donnés, pour n=18 on a 241939392597201176602897820148085023 cas possibles quand est-ce on l'a trouvé, même si l'algorithme est simple, quel est le temps machine pour son exécution.
J'ai été amené pour un collègue à trouver toutes les solutions dans de l'inéquation
.
L'idée principale que j'ai utilisée est la suivante: si je connais une solution "partielle" , quelles sont les valeurs possibles de
? ça c'était ça au temps du MsDos. J'ai du tenir compte des ruptures de courant, je lançais le soir à la sortie du travail le programme pour récupérer les résultats le lendemain, mais le lendemain, il tournait encore et j'ai même grillé un CPU.
Les moyens informatiques sont-ils les mêmes sont-ils aujourd'hui qu'il y a 14 ans, le problème n'est peut-être pas l'algorithme mais un problème de mémoire et du temps d'éxécution.
Ne peut-on reprendre l'algorithme pour n=18, le modifier pour utiliser les ressources d'aujourd'hui, programmation parallèle, utilisation des moyens disponibles sur internet (PC des particuliers) (Voir ou . (Le 1er lien donne le version anglaise (Wikipédia), on peut changer la langue après
J'y participe par l'utilisation de mon PC et j'ai actuellement un problème qui tourne et qui nécessite dans les 200 heures d'exécution, 50 heures sont déjà passées et un autre qui utilise CPU et GPU.
L'algorithme que j'ai proposé et tel qu'il est conçu est, je te l'accorde, surement inutilisable pour les résultats qu'on veut obtenir mais pas en que tel mais pour son temps d'exécution et les ressources à utiliser.
Si l'on regarde l'algorithme que j'ai proposé, la partie principale de celui-ci commence par le choix de la partie ordonnée (étape 1) , les étapes 2) à n-k+1) ne nécessite aucune donnée à part G_{n-k} qu'on peut déterminer à l'étape 1). Ceci se traite bien par un travail distribué, un programme principal
qui crée les (E,\le) et les parties ordonnées E_k (sans doublons) et qui se charge de distribuer le travail à un programme
qui débute lui à l'étape 2), un programme
qui récupère les résultats des
(on même que les
lui envoient) (pour éventuellement supprimer par exemple les doublons) .
Ma compétence s'arrête ici et même avant et tout ceci n'est que pures réflexions de Amateur76 à Aamateur75
PS: Le nombre de parties totalement ordonnées est
J'ai été amené pour un collègue à trouver toutes les solutions dans
Tu rigoles ? C'est un problème bien connu, le calcul du nombre de solutions se traite en deux coups de cuillères à pot, sans ordinateur bien sûr : c'est le nombre de façons de ranger
Ca n'a rien à voir avec le problème du dénombrement des ordres.
Bonjour.
Ca n'a rien à voir avec le problème du dénombrement des ordres.
Exact! mais pour le problème que j'ai cité, il fallait en trouver les solutions mais les dénombrer.
Bref passons! je me suis attaqué à un problème qui me dépasse. Juste pour la consolation, ne peut-on pas avoir une majoration du nombre d'ordre sur un ensemble à n+1 éléments à partir de celui d'un ensemble à n éléments.
Je me rends.
Annuler
connectez vous
algèbre en post-bac