A la recherche d'une bijection...

Bonsoir a tous,

je cherche depuis quelques jours une bijection "sympathique" de $\N^2$ sur $\N$ ou alors de $\N^2$ sur $\R$. Par sympathique j'entends une fonction qui s'exprime "facilement" ainsi que sa réciproque....par exemple qu'on pourrait programmer aisément.
Je n'ai malheureusement rien trouver, alors si quelqu'un avait ca sous la main ou pas trop loin....

Merci d'avance et bonne rentrée !

Hoeg

Réponses

  • Une réponse classique consiste à numéroter "en diagonale"
    0 , 1 , 3 , 6
    2 , 4 , 7
    5 , 8

    etc... On obtient (m,n)-->(m+n)(m+n+1)/2+m

    Il ne peut pas y avoir de bijection entre N et R ( Cantor)

    Salutations
  • Bonjour Hoeg.

    Pol t'a donné la fonction de Gödel, en voici une autre assez élémentaire :

    Tu décomposes tes deux nombres en base 9; puis tu les concatène en mettant un 9 pour la virgule.

    Exemple :
    (48,35) devient : 53938 !

    Certes, ce n'est qu'une injection : n'appartient à l'image que les entiers dont le développement décimal ne contient qu'un chiffre 9, et encore uniquement s'il n'est ni en premier rang ni en dernier rang.

    Par contre la méthode permet de coder directement les éléments de $\N^{(\N)}$, c'est-à-dire l'ensemble de toutes les suites finies d'entiers.

    Bruno
  • Merci pour vos reponses !
    Effectivement j'etais dans le pate pour la bijection de $\N^2$ sur $\R$, desole.
    Par contre Bruno, ta fonction me parait un peu compliquee pour l'application que je voudrais en faire...mon objectif serait de trouver un stockage pour matrice creuse et de pouvoir avoir avec une seule donnee l'information sur la position ligne/colonne d'un coefficient non nul ; avec ta fonction Bruno, je devrais manipuler des tableaux intermediaires ce qui au final rend la chose un peu compliquee et peut etre longuette. Peut etre que ma recherche est inutile d'ailleurs...mais je vais essayer de voir ce que donne la fonction de Godel en commencant par chercher la reciproque.

    Encore merci....et si jamais vous avez autre chose....

    Bonne journee

    Hoeg
  • juste pour revenir a ma bijection de $\N^2$ sur $\R$, je pensais evidemment a une bijection de $\N^2$ sur $\Q$ mais en informatique il n'y a pas de rationnels....donc si quelqu'un connait une telle bijection (de $\N^2$ sur $\Q$) qui ne soit pas trop sensible numeriquement, ca me plairait aussi...

    Hoeg
  • Salut,
    pour moi, la bijection la plus naturelle entre N^2 et N* reste:
    (m,n)->(2*m+1)*2^n
    Cependant, sa réciproque n'est pas très aisée à exprimer...

    Bonne journée.
  • Bonjour

    Je ne conais pas de bijection "simple" entre $\N^2$ et $\Q$, mais il me semble qu'elles ne peuvent pas avoir de bonnes propriétées numériques car elles ne peuvent pas respecter l'ordre usuel dans $\Q$.

    Pour la réciproque de la fonction de Gödel (je connaissait pas le nom de cette fonction) :
    $k \longrightarrow (m,n)$ avec $$m=k- \frac{S(S+1)}2 , n=S-m \ et \ S =Int(\frac {-1+ \sqrt {1+ 8 k }}2)$$.
    Ceci pour essayer Latex

    Bonne continuation
  • Je ne vois pas l'intérêt de vouloir à tout prix stocker la paire d'indices (i,j) sous la forme d'un seul nombre.

    Ne me dis pas que c'est pour un gain de place : si i et j sont de l'ordre de N, la fonction de Gödel te donnera un nombre de l'ordre N², donc deux fois plus gros à stocker...
  • Pour stocker la paire d'indices (i,j) sous la forme d'un seul nombre, il suffit de remplacer (i,j) par i+nj où n est la taille de la matrice. Si n est trop grand pour que cela marche, la remarque de Le Furet s'applique.
    Cordialement.
  • En général, quand on code différemment une matrice à trou, c'est que sa taille est trop importante pour qu'on la stocke de façon classique.
  • Pour pol.

    Sauf erreur de ma part, Gödel l'a introduite à l'occasion de sa démonstration du premier théorème d'incomplétude : il s'agit d'exhiber un énoncé non démontrable dans une théorie plus forte que l'arithmétique du second ordre.

    Pour cela, Gödel code chaque formule par un entier et pour ce faire, il utilise cette fameuse fonction.

    Bruno
  • Le Furet, c'est exactement mon cas...j'ai parle de matrice creuse....et les stockages que j'ai vu ne me semblent pas forcement optimaux c'est tout. Je ne dis pas que ce aue je cherche est forcement optimal ni meme utile, je ovulais juste me faireune idee...

    Merci a tous pour vos reponses
  • On peut aussi coder une suite (a1,a2,..,an) sous la forme N=2^a1*3^a2*...*p(k)^ak: c'est une bijection.
  • juste pour revenir sur la reciproque de Gödel...tu pourrais me dire comment tu la calcules Pol ? J'ai du mal a voir d'ou peut venir le $\sqrt{1+8k}$.

    Hoeg
  • C'est le discriminant de l'équation du second degré :
    $$x^2 + x - 2\,k = 0$$

    Bruno
  • Pour préciser on recherche la "diagonale" dans la quelle se trouve k en résolvant l'équation donnée par Bruno.
    Salutations
  • C'est ton équation, je n'y pensais plus.

    Bruno
  • Juste une question. En y réfléchissant je ne connais pas de bijection explicite entre $\N \ et \ \Q$.
    Quelqu'un en connait-il ?

    Salutations pol
Connectez-vous ou Inscrivez-vous pour répondre.