Répondre à la discussion
Affichage des résultats 1 à 7 sur 7

formalisation mathématique d'un graphe



  1. #1
    craz_rose

    formalisation mathématique d'un graphe


    ------

    Bonjour,
    je suis en fait informaticienne, mais j'ai un problème mathématique à résoudre.

    Alors je considère l'espace des nombre entiers.
    Je fixe un nombre N d'éléments (par exemple 1000000) (et donc je travaille sur les éléments de 1 à N-1, ou de 0, ce n'est pas trés important).

    A partir de là, je construis un graphe de la façon suivante (une skip-Liste binaire si vous connaissez) :
    L'axe des ordonnées contient les nombres entiers à traiter.
    L'axe des y correspond aux niveaux de l'élément.
    Tous les éléments appartiennent au niveau 0.
    Les autres niveaux de l'éléments sont déterminés de la façon suivante: si x est divisible par 2, alors il appartient au niveau 1,
    s'il est divisible par 4 ( 2 puissance 2), alors il appartient au niveau 2, s'il est divisible par 8 (2 puissance 3)alors il appartient au niveau3... jusqu'au niveau maximal de l'élement qui correspond à log2(x) si x est une puissance de 2.

    Ainsi, les éléments impairs n'appartiennent qu'au niveau 0.
    l'elément 6 appartient aux niveaux 0 et 1.
    8 appartient aux niveaux 0, 1, 2 et 3.

    Ma question est la suivante:
    je veux déterminer le nombre d'éléments que je parcourt si je traverse le graphe de la façon suivante:

    je pars d'un élément x donné et je veux arriver à l'élément N.
    Je prends le niveau le plus haut auquel appartient l'élément x
    (par exemple 3 pour l'élément 8).
    et je regarde le successeur au meme niveau ( ca me donnera 16).
    Maintenant je prends l'élément 16 (niveaux 0,1,2,3,4).
    Je prends le niveau le plus haut auquel il appartient et je regarde le successeur, ca me donne 32.
    Maintenant je prends l'élément 32(niveaux 0,1,2,3,4,5).
    Je prends le niveau le plus haut auquel il appartient, soit 5, et je prends le successeur, soit 64 et ainsi de suite.

    l'élément 8 étant un cas particulier, je prends un autre exemple.Soit l'élément 5 (niveau 0), son successeur est donc 6.
    6 (niveau 0 et 1) a pour successeur de haut niveau (niveau 1) 8.
    ensuite pour l'élément 8 celà se passe comme décrit précédemment.

    Ce dont j'ai besoin en premier lieu, c'est le nombre d'éléments traversés pour arriver à N.
    Etant informaticienne, j'arrive à créer un programme qui permet de calculer ce nombre pour x et N donnés.
    Mais ce dont j'ai besoin c'est une formule mathématique ou, faute de pouvoir le faire, une formalisation mathématique du problème.

    Une fois ce nombre calculer, mon but était de pouvoir démontrer l'hypothèse suivante:

    Pour N donné, il n'existe pas d'éléments x1 et x2 telque:
    1. x1 est différent de x2
    2. x1 et x2 ont le même niveau maximal (par exemple 4 et et 12 car 4 appartient aux niveaux 0, 1 et 2 et pareil pour l'lémément 12)...
    3.les niveaux maximaux de la skip Liste lors de l'insertion de x1 et lors de l'insertion de x2 sont égaux. Par exemple, si j'insère 7, le niveau maximal de la skipListe est 2 ême si 7 n'appartient qu'au niveau 0( car 4 a déjà été inésré et il appartient aux niveaux 0, 1 et 2). Si j'insère 8, le niveau maximal de la skipListe est égale au niveau de l'élément inséré et est égale à 3. Si j'insère 9 le niveau de l'élément est 0 et le niveau de la skip Liste est 3...

    4. Le nombre de successeurs de x1 et de x2 est égal.
    5. tout ceci est récursif.

    Par exemple:
    si je prends x1=11, x2=13 et N=16
    alors 11->12->16
    et 13->14->16

    A la première itération on a 11 différent de 13, 11 et 13 appartiennent tous les deux uniquement au niveau 0 et finalement le niveau maximal lors de leurs insertions était 3 (correspondant à l'élément 8).
    Maintenant je prends x1=12 (le seccesseur de 11)
    et x2=14 (le successeur de 13)

    alors on a:
    12 appartient aux niveaux (0, 1 et 2) alors que 14 n'appartient qu'aux niveaux (0 et 1).

    Ce qui rejoint notre hypothèse.


    Je pense en fait à une suite numérique mais je n'arrive pas à formaliser.
    On pourrait alors soit travailler en base 2, ou travailler à l'échelle logarithmique.
    Ce sont deux pistes ùais je n'arrive à faire aboutir aucune d'entre elles.
    Pourriez vous m'aider??


    Je vous remercie d'avance pour votre attention et votre aide et espère avoir été assez claire.
    Je me tiens à votre disposition pour toute information supplémentaire.
    Merci pour tout.

    -----

  2. Publicité
  3. 📣 Nouveau projet éditorial de Futura
    🔥🧠 Le Mag Futura est lancé, découvrez notre 1er magazine papier

    Une belle revue de plus de 200 pages et 4 dossiers scientifiques pour tout comprendre à la science qui fera le futur. Nous avons besoin de vous 🙏 pour nous aider à le lancer...

    👉 Je découvre le projet

    Quatre questions à explorer en 2022 :
    → Quels mystères nous cache encore la Lune 🌙 ?
    → Pourra-t-on bientôt tout guérir grâce aux gènes 👩‍⚕️?
    → Comment nourrir le monde sans le détruire 🌍 ?
    → L’intelligence artificielle peut-elle devenir vraiment intelligente 🤖 ?
  4. #2
    matthias

    Re : formalisation mathématique d'un graphe

    Citation Envoyé par craz_rose
    L'axe des ordonnées contient les nombres entiers à traiter.
    L'axe des y correspond aux niveaux de l'élément.
    Pour être précis, l'axe des abcisses (x) contient les nombres entiers à traiter, et celui des ordonnées (y) leur niveau.

    Citation Envoyé par craz_rose
    5. tout ceci est récursif.
    C'est à dire que si X1 et x2 vérifient les 4 premières conditions, il faut encore que les 5 conditions soient réunies pour successeur de x1 et successeur de x2. J'ai bien compris ?

    Je vais regarder, j'ai pas l'impression qu'il ya ait besoin d'une échelle logarithmique, ça compliquerait plutôt. Utiliser la base 2 permet peut-être des astuces mais ne doit pas être indispensable d'un point de vue mathématique.

  5. #3
    martini_bird

    Re : formalisation mathématique d'un graphe

    Salut,

    je n'ai pas encore réfléchis au problème, mais il y a quelque chose qui me chiffonne quand tu dis
    Citation Envoyé par craz_rose
    Ce dont j'ai besoin en premier lieu, c'est le nombre d'éléments traversés pour arriver à N.
    En effet, si tu prends N=10 et en partant de n'importe quel nombre sauf 9 tu arrives à 8. Or 8 n'a plus de successeur de même niveau: comment fais-tu pour arriver à 10?
    Doit-on prendre N=2n?

    Car, clairement, partant d'un entier x, on tombera en quelques coups (dont je n'ai pas encore déterminé le nombre) sur la puissance de 2 suivante (disons 2m). Puis sur 2m+1, 2m+2, ...

    Cordialement.

  6. #4
    matthias

    Re : formalisation mathématique d'un graphe

    Il est assez facile de calculer le niveau maximal d'un entier et son successeur, mais je ne pense pas que ça fasse avancer le Shmilblick.

    pour n dans IN*, n = 2p.q avec q impair
    Log2(n) = p + Log2(q) où Log2(q) n'est pas un entier
    N(n) = p = E(Log2(n)) = niveau maximal de n

    S(n) = 2p.(q+1) = successeur de n
    S(n) = 2E(Log2(n)).(n/2E(Log2(n)) + 1)

    Ce qui est à mon avis inexploitable.

    Par contre, on voit que la suite des successeurs retombe inexorablement sur des puissances de 2, et qu'ensuite il est facile de les compter (le successeur dune puissance de 2 étant la puissance suivante). Le problème c'est de savoir en combien d'étapes on tombe sur une puissance de 2.

  7. A voir en vidéo sur Futura
  8. #5
    matthias

    Re : formalisation mathématique d'un graphe

    Martini, je pense que le successeur doit être le min du successeur naturel et de N. Ou alors imoser N = 2p bien sûr.

  9. #6
    matthias

    Re : formalisation mathématique d'un graphe

    Citation Envoyé par matthias
    pour n dans IN*, n = 2p.q avec q impair
    Log2(n) = p + Log2(q) où Log2(q) n'est pas un entier
    N(n) = p = E(Log2(n)) = niveau maximal de n
    ça sert à rien et en plus c'est faux
    Je vais dormir ...

  10. Publicité
  11. #7
    hedron

    Re : formalisation mathématique d'un graphe

    Bonjour.

    Essai : si t'as un nombre écrit en binaire 1001110110000.
    Alors ce que tu fais est mettre les zéros de droite de côté
    100111011:0000
    Puis tu ajoutes 1
    100111100:0000
    Puis tu recommences
    1001111:000000
    +1
    1010000:000000
    101:0000000000
    +1
    110:0000000000
    11:00000000000
    +1
    100:00000000000=2^13
    4 étapes.

    T'ajoutes 1 en fait à chaque zéro rencontré sauf pour les premiers.
    Conclusion : nb d'étapes = 1+n
    où n est le nb de zéros dans l'écriture binaire sans compter ceux de droite.

    J'ai bon ?

Discussions similaires

  1. Representation mathematique d'un oeuf
    Par Woos dans le forum Mathématiques du supérieur
    Réponses: 12
    Dernier message: 05/04/2007, 10h34
  2. formule mathématique d'un schéma
    Par hajar1 dans le forum Électronique
    Réponses: 25
    Dernier message: 30/01/2007, 11h48
  3. représentation mathématique d'un algorithme
    Par Seirios dans le forum Mathématiques du collège et du lycée
    Réponses: 0
    Dernier message: 03/09/2006, 16h56
  4. graphe
    Par sahdow dans le forum Logiciel - Software - Open Source
    Réponses: 0
    Dernier message: 02/06/2006, 11h37
  5. Recherche d'un aspect mathématique = TPE
    Par rob29 dans le forum TPE / TIPE et autres travaux
    Réponses: 0
    Dernier message: 09/10/2005, 14h36