[INFO/MATHS] Calcul de BITES.

Salut les kheys

Je vais parler de graphes, mais je ne pense pas que résoudre problème nécessite vraiment de connaissances sur les graphes.
Je considère un graphe G, c'est à dire une figure géométrique qui possède n sommets et m arêtes (une arête c'est une ligne qui relie deux sommets)
Il s'agit d'un graphe orienté, c'est à dire qu'e les arêtes sont en fait des flèches, on ne peut les parcourir que dans un certain sens à chaque fois.

Je considère une fonction f : {arêtes de mon graphe } ---> N\{0} ^d, où d est un entier >= 2.
Donc à chaque arête j'ai associé un certain vecteur de taille d, ne contenant que des entiers strictement positifs.
Enfin, je pose A = [ratio entre la plus grande valeur prise par une coordonnée de f sur une arête quelconque et la plus petite valeur prise].

Je lis un document qui affirme la chose suivante :

Si B désigne le nombre de bits nécessaires pour représenter les différentes valeurs que prend ma fonction f, alors :
B = O (log(nA)). (Nb : Je rappelle que n désigne le nombre de sommets du graphe. )

Comment on fait pour le prouver ?

Perso je me dis :

Au total il y a m arêtes et d coordonnées pour ma fonction, donc le nombre de valeurs à encoder est m*d.
Maintenant on imagine qu'on code avec un unique bit la valeur la plus petite prise par la fonction.
Alors effectivement le nombre de bits pour coder la plus grande valeur de la fonction ça sera log(plus grande valeur prise par la fonction/plus petite valeur prise) ce qui donne donc log(A).
Et vu qu'il y a m arêtes et d coordonnées, au pire (je majore), le nombre de bits requis sera m*d*log(A).

Donc je tombe plutôt sur du O (m*d*log(A)), et non pas sur du O(log(nA))

En fait juste au cas où ce soit un problème de compréhension de ma part, je cite (en anglais) la définition de A :

" Let A denote the ratio of the maximum to the minimum edge cost (in any dimension)"

2 connectés
Le dernier khey, sur lequel tout repose

T'inquiète, je viens d'attirer le renfort !

Je laisse bider mais je reviendrai régulièrement jeter un oeil, n'hésitez pas à poster même longtemps après ce post si vous trouvez la réponse

Le 23 mai 2021 à 23:37:51 :
Perso je me dis :

Au total il y a m arêtes et d coordonnées pour ma fonction, donc le nombre de valeurs à encoder est m*d.
Maintenant on imagine qu'on code avec un unique bit la valeur la plus petite prise par la fonction.
Alors effectivement le nombre de bits pour coder la plus grande valeur de la fonction ça sera log(plus grande valeur prise par la fonction/plus petite valeur prise) ce qui donne donc log(A).
Et vu qu'il y a m arêtes et d coordonnées, au pire (je majore), le nombre de bits requis sera m*d*log(A).

Donc je tombe plutôt sur du O (m*d*log(A)), et non pas sur du O(log(nA))

Ca me semble même pire que ça Déjà, pourquoi un unique bit pour encoder la plus petite valeur de f ? Elle n'est a priori pas fixée, ni même bornée, donc on peut avoir besoin d'un nombre arbitrairement grand de bit pour l'encoder.

De plus, admettons par exemple qu'on ne compte pas les bits pour encoder la valeur min, et prenons A=2. On ne peut pas encoder un entier entre min et 2*min avec O(log A)=O(1) bits, car on va avoir besoin de log_2(min) bit au moins.
Ca serait possible de coder les autres valeurs de f en O(log A) si les autres valeurs prises par f sont des multiples entiers de la valeur min.