BIJECTION EXPLICITE ENTRE N ET Q+

Information sur la source

Catégorie :Maths & Algorithmes Niveau : Débutant Date de création : 23/06/2004 Date de mise à jour : 24/06/2004 17:00:20 Vu / téléchargé: 2 327 / 87

Auteur : cosmobob

Ecrire un message privé

Ce membre participe au partage de revenus publicitaires

Note :

10,00 / 10

Commentaire sur cette source (17)

Ajouter un commentaire et/ou une note

Description

Cliquez pour voir la capture en taille normale

Voici une source qui montre une bijection explicite entre N et Q+.
Cela signifie que l'on peut compter les rationnels, ce qui peut paraitre surprenant car Q est dense dans R, et que l'on ne peut pas compter les réels.

comme vous le savez peut-etre, on peut associer de maniere unique un couple d'entiers à un entier. Une illustration connue est de compter en 'diagonale' comme dans la capture d'écran que j'ai mise.
Quand il s'agit maintenant de compter les rationnels, les choses se compliquent : si on fait exactement pareil qu'avec N², cad compter en diagonale, on va compter plusieurs fois le meme entier (1/2 = 2/4 = 4/8, par exemple).
On pourrait parcourir tout N² en diagonale (comme dans la capture d'écran) et éliminer les rationnels que l'on a déja rencontrés, mais l'algorithme serait en O(n), cad tres long...

L'idée est d'utiliser la décomposition en fraction continue des rationnels, l'algorithme passe alors en O(log(n)).
La source est livrée avec un fichier pdf qui m'a permis d'écrire ce bout de code.

Conclusion

mise a jour le 24/06/04 avec utilisation des __int64 (on peut mtnt chercher le 100 000 000 000 eme rationnel par exemple)

Fichier Zip

Pour les "Membres Club", vous pouvez télécharger directement un fichier contenu dans le zip sans télécharger le zip en entier !

bijection.dsp 4 443 octets
bijection.dsw 543 octets
brocot.pdf151 193 octets
fraction.cpp 3 975 octets
fraction.h 1 092 octets
main.cpp 4 851 octets

Télécharger le zip

Sources du même auteur

Toutes les sources de cosmobob

Sources de la même categorie

Toutes les sources de la catégorie Maths & Algorithmes

Commentaires

Commentaire de cosmobob le 23/06/2004 20:49:25

Ha, j'oubliais. Le code est livré avec une classe fraction faite vite fait pour manipuler les rationnels, qui est peut etre pas complete...

Si vous avez des remarques sur l'idée de la bijection, hésitez pas.
Commentaire de JCDjcd le 23/06/2004 21:25:37

Ce qui est interressant dans ce resultat c'est que Q (ou Q+) est petit comme ensemble par rapport a R, et que Q est denombrable.
Mais on en conclu donc que dans R il y a bcp plus d'irrationnel que de rationnel (l'un denombrable, l'autre non).

sinon pourquoi des que l'on rentre une chaine "non reglementaire" ca defile grave a l'ecran ?
Commentaire de cosmobob le 23/06/2004 21:36:19

c'est qd tu rentres pas un entier (genre un caractere, un flotant ou un entier trop grand (>2^32)), il y a un probleme avec cin que j'ai pas su résoudre... si quelqu'un sait comment detecter l'erreur lors d'une entrée (autrement qu'en faisant des getc successif et formater soi meme), pour sortir proprement, dites le que j'update la source.

ce qui est aussi 'rigolo', c'est que bien qu'il y ait bcp plus de réels que de rationnels, l'existence d'un ensemble intermédiaire (contenant Q et inclus dans R, mais en bijection avec ni l'un ni l'autre) est un problème indécidable, ce qui pointe les limites de notre axiomatique sur les ensembles. (quelqu'un sait il rajouter un axiome 'simple' pour que ce probleme soit décidable? pour l'instant non, on veut rajouter le probleme ou sa négation tout entier)

et puis compter les rationnels, c'est qd meme qqc d'assez contraire au sens commun, alors que pourtant c'est possible
Commentaire de Chouchou182 le 23/06/2004 23:30:14

Salut

Je pense avoir résolu le problème lié à cin provoquant un affichage ininterrompu en cas de saisie maladroite de la part de l'utilisateur. Voila les modifications :
  -Saisie de 'choix' pour le menu :
      fflush(stdin) ;
      choix = getchar() - 48 ;
  -Saisie de 'valeur' pour la case 1:
            char val[50] ;
            cin >> val;
            valeur = atoi(val) ;
  -Méthode de saisie d'une fraction:
istream & operator >> (istream & in, fraction &b)
{
   char val[50] ;
   in >> val ;
   b.numerateur = atoi(val) ;
   in >> val ;
   b.denominateur = atoi(val) ;
   b.simplifier();
   return in;
}

Le principe est simple : on récupère la saisie de l'utilisateur comme une chaîne de caractères et transforme à l'aide de atoi. En cas d'erreur, atoi renvoie 0 donc le programme continue sans problème.

Bonne Prog !

Chouchou.
Commentaire de cosmobob le 24/06/2004 00:20:02

ué bon jsavais qu'on pouvait se débrouiller avec getc mais bon... sinon pour in >> val, ben ca fait un buffer overflow si on ecrit trop de caracteres, ce qui a cependant moins de chances d'arriver que de taper autre chose qu'un entier.

enfin voila ca jle savais qu'on pouvait s'en sortir de cette maniere, mais yatil moyen de s'apercevoir que ce qui a été rentré par cin>> n'est pas correct? (pkoi cela ne leve til pas une exception par ex: ?)

bon de toute facons le but de la source c'est pas les trucs comme ca sur les entrées sorties...
Commentaire de Saros le 24/06/2004 10:14:04

(fraction)1 / resultat;
Là, il n'y a pas que le 1 qui est considéré comme fraction ? Je veux dire, pour tout mettre en fraction, c'est pas ça :
(fraction)(1 / resultat);

Je suis un peu perdu à vrai dire ^^... Je vais commencer à lire le PDF...
Commentaire de cosmobob le 24/06/2004 10:37:13

si ya que le 1 qui est alors considéré comme fraction, mais apres la division a été redéfinie pour les fractions, donc pas de problemes...
si tu fais (fraction) (1/resultat) il faudrait que yait un operateur de division entre un entier (1) et une fraction (resultat) ce qui n'est pas le cas.

sinon pour le pdf faut un assez bon niveau scientifique pour comprendre qd meme.
Commentaire de MetalDwarf le 24/06/2004 15:15:25

Oui je connaissais ce petit truc de l isomorphisme entre N et Q+, c est vrai que c est assez surprenant... Cependant quand on y regarde de plus pres on ne peux pas "vraiment" compter les rationnels car quand on s eloigne la diagonale devient de plus en plus longue, ce qui montre un passage progressif a un ensemble "qu on ne peut pas compter".
Enfin pour ce qui est de la theorie des ensemble il est vrai qu elle possede ses limites, mais il est inutile de vouloir une theorie parfaite car c est impossible!! (theoreme d incompletude de Gödel)
Commentaire de cosmobob le 24/06/2004 15:43:34

ben si on peut compter les rationnels, vu qu'il s'agit d'un ensemble dénombrable. une bijection explicite avec N est donnée dans la source donc... dans ce que tu dis, tu confonds l'infini avec la non dénombrabilité. et la le comptage n'est pas en diagonale comme avec N². Tiens au fait, une bijection explicite de N² -> N est par exemple la fonction qui au couple (p,q) associe (p+q)(p+q+1)/2 + q (comptage en diagonale).
regarde, d'apres la source, le 1000e rationnel est 41/9, et le millionieme est 1153/325.
par contre il ne s'agit pas d'un isomorphisme, pour la simple et bonne raison qu'il ne s'agit pas du tout d'un morphisme (aucun isomorphisme de Z dans Q n'est possible, car l'image de Z par un isomorphisme fi est de la forme fi(1).Z, ce qui n'est pas le cas de Q)
Commentaire de cosmobob le 24/06/2004 17:02:16

j'ai reglé le probleme de saisie, et j'ai remplacé tous les int par des __int64, ce qui permet de moins limiter le domaine de définition des deux fonctions.
Commentaire de BlackGoddess le 25/06/2004 08:31:01

      fflush(stdin) ;
      choix = getchar() - 48 ;
  -Saisie de 'valeur' pour la case 1:
            char val[50] ;
            cin >> val;

>> fflush est du C, cin du C++, au niveau des flux c'est tres mauvais de mélanger

vérifier une saisie :

int i;

if(cin >> i)
  cout << "correct\n";
else
  cout << "incorrect\n";
Commentaire de cosmobob le 25/06/2004 10:36:59

pour vérifier la saisie, if (cin >> i) ne marche pas chez moi (ca rentre toujours dans correct, car ca doit renvoyer un pointeur ou qqc vers le flux, qui n'est en tout k jamais nul)
ya til un moyen officiel? (c'est une biblioteque standard ... normalement oui !!)
sinon le fflush(stdin) est avant le getc qui est du C..., c'est 'mauvais' de mélanger, encore une fois je vois pas du tout pourkoi, de maniere interne c'est géré différement, donc pas de conflit. ya des conflits au cas ou plsrs threads font des entrées/sorties en meme temps, meme si tout est en C ou tout en C++... et la ya rien de simultané.
Commentaire de cosmobob le 25/06/2004 11:13:37

bon, avec iostream et pas iostream.h, le if (cin >> i) marche.
par contre, pour remettre a l'etat normal, cin.clear() marche pas du tout... comment se fait-ce? :p
Commentaire de vecchio56 le 26/06/2004 14:35:25 administrateur CS

j'ai entendu un truc qui consiste à partir de zéro et à conter les rationnels en tournant autour, c'est comme ca que tu a fait? (j'ai pas trop e temps de ragerder la source)
Commentaire de cosmobob le 26/06/2004 16:03:43

non. tourner autour doit vouloir dire: classer les rationnels suivant la somme numerateur+denominateur. la ils sont classés suivant la somme des coefficients du développement en fraction continue.
Commentaire de raphaducasse le 27/05/2005 17:21:03

j ai aussi bossé sur ces histoires de suites de Brocot et ton prgm tourne vrmt bien. Il y a par un inconveniant majeur : le fait que tu sois limité a des entiers < 2^63 (parce que ca fait pas des fractions si précises que ca etant donné que tu passe par le dvp en frac cont). Je suis en train de creer une class BigInt pour parlier a ça. En plus, vu que cet algorithme est rapide, ca permet d 'implementer efficacement des series de rationnels. Si tu veux mes docs sur ce que j ai fait, fait moi savoir.
Commentaire de cosmobob le 22/06/2005 10:50:08

et oui a la base il s'agissait d'une illustration de l'algorithme, qui illustre de facon explicite et constructiviste l'equipotence de Z et de Q. car en tant que tel, trouver le rationnel associé a l'entier 2^83, ca ne sert pas a gd chose :)
tes docs m'interessent cela dit !!