Niveau autre

analyse numérique,nombre de successeurs dans skipListe binaire

Posté par crazy_rose (invité) 09-03-05 à 12:52

Bonjour,
je suis en fait informaticienne, mais j'ai un problème mathématique à résoudre dans le cadre de ma thèse. J'espèe pouvoir être assez claire:

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, 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.

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.

Posté par re : analyse numérique,nombre de successeurs dans skipListe bina 09-03-05 à 15:37

Pour autant que j'aie bien saisi le problème.

Il me semble qu'on ne peut atteindre N que si N est de la forme 2^n

Où alors N est n'importe quoi, mais on considère que N est atteint lorsqu'il est soit réellement atteint ou bien alors qu'il est dépassé.

Si N est bien de la forme 2^n (ou sinon, on prend N' = la valeur de 2^n immédiatement supérieure à N pour faire le calcul).

Le nombre de pas est égal au nombre de 1 qu'il faut pour écrire le nombre (N' - x) en binaire (+ 1 si on compte le nombre x comme étape).

exemple:
N = 1 000 000 en décimal
N' = 1 048 576 en décimal (c'est 2^n juste au dessus de 1 000 000)

x = 317 (décimal)
N'-317 = 1 048 576-317 = 1 048 259 (décimal)
On écrit ce résultat en binaire -> 11111111111011000011
Dans ce nombre il y a 15 fois le chiffre 1.
Il faut donc 15 + 1 = 16 étapes (si on compte le 317 de départ).
La 16 ème étape dépasse le nombre N.
-----
Je n'y ai pas réfléchi longtemps et cela mérite alors d'être vérifié, je me suis peut-être mis le doigt dans l'oeil.

Posté par crazy_rose (invité)toujours à propos des skip listes 09-03-05 à 18:37

Bonjour,
Merci pour votre attention. C'est la réponse qu'il me fallait.
Mais maintenant j'ai un autre probleme, si vous pouvez m'aider (désolée d'abuser )
Alors voilà, en fait 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.

J'ai créé un programme qui me fait tous ces tests (bon je ne suis pas allée au delà de 1000000, et le test n'est pas vraiment exhaustif, mais juskelà ces hypothèses sont correctes). Mais je voudrais pouvoir expliquer tout ceci formellement, voir le démontrer mathématiquement.
Pouvez vous me guider?

Je suis entrain de modifier les tests et de faire qu'ils soient exhaustifs.
Merci pour votre aide et la suite que vous avez donné (et j'espère que vous donnerez ) à mon problème.

Posté par re : analyse numérique,nombre de successeurs dans skipListe bina 10-03-05 à 09:32

Je n'ai probablement pas compris cette seconde question.

Si on prend par exemple x1 = 11 et x2 = 13 et N >= 16

Le point 1 est OK (x1 est différent de x2)
Le point 2 est OK (x1 et x2 sont tous deux au niveau 0)
Le point 3 est OK (le niveau de la liste est 3, imposé par x=8 aussi bien à l'introduction de x1=11 que de x2=13)

Or la liste des successeurs est:
11 -> 12 -> 16 -> ...
et
13 -> 14 -> 16 -> ...

Et alors le nombre de successeurs de 11 et 13 semble égal, ce qui devrait être impossible.
-----

Posté par crazy_rose (invité)re : analyse numérique,nombre de successeurs dans skipListe bina 10-03-05 à 10:11

Bonjour:
non vous avez trés bien compris la kestion, mais c'est moi qui ai mal expliqué la condition 4 (plutot oublié d'exprimer une autre contrainte).

C'est que chaque élément de la liste des succeurs doit avoir le meme nombre de niveaux. J'explique:

11 a pour successeurs 12 et 16
13 a pour successeurs 14 et 16
Je compare les niveaux de 12 et 14 ( 0,1 et 2 pour 12; et 0 et 1 pour 14) dc ca ne colle pas.

En fait ce ke je veux dire, c'est ke les conditions sont récursives autrement dit, x1 prend ensuite la valeur du premier élément de la liste de ses successeurs et on fait de même pour x2.

J'espère m'etre fait comprendre? encore merci pour tt.
A plus j'espère

Posté par crazy_rose (invité)re : analyse numérique,nombre de successeurs dans skipListe bina 10-03-05 à 11:11

je voulais juste clarifier un peu plus ce que je viens de dire,
la récursivité peut se limiter au fait que le nombre de niveaux des successeurs dans les deux liste soit le même pour les éléments pris deux à deux (puiske le reste normalement ne devrait pas changer):
par exemple 12 et 14 ( ce n'est pas le cas mais c juste pour illustrer)
ensuite les prochains jusk'à ce que les listes de succeurs se rejoignent (élément 16 pour nous)

Merci encore