Les mots de Christoffel et les Math Discrètes

Dans ce billet, on va s'intéresser à un objet mathématique particulier : Les mots de Christoffel. Que sont-ils ? Quel est leur utilité ? Nous allons voir cela tout de suite.

  • Continu et discret
  • Rastérisation
  • La rastérisation de ligne
  • Christoffel à la rescousse!
  • Les mots de Christoffel et les probabilités
  • La probabilité exacte

Continue et discret

La géométrie traditionnelle est continue: On peux rapprocher deux points autant qu'on veux sans qu'ils ne soient jamais superposés, et les éloigner autant qu'on veux, sans limite. Autrement dit, la précision de notre espace est infinie. Cependant, en Informatique, les ordinateurs sont des machines discrètes : Une mémoire finie, un nombre de pixels fini, un nombre d'instructions par seconde finis... Cela veut dire que pour utiliser les outils mathématiques, il est nécessaire de "discrétiser" les objets que nous manipulons.

Rastérisation

Le procédé que nous allons étudier est la rastérisation. C'est une technique qui consiste à convertir une image vectorielle, une composition à base de formes purement géométriques définies mathématiquement, comme des lignes, des triangles, ou des cercles ; vers une image matricielle, qui est une grille discrète de points colorés de taille non nulle, dont l'utilisation principale est l'imagerie numérique, qui n'est qu'une grille finie de pixels.

Pour rastériser une image vectorielle, il faut pouvoir rastériser chaque forme géométrique indépendamment. La forme la plus commune est le triangle, car elle peut approximer toutes les autres, et pour des applications 3D, il est important que toutes les formes soient de la même nature. Une carte graphique, créée pour faire du rendu 3D, est en partie simplement une machine à rastériser !

La rastérisation de ligne

Nous allons ici étudier des lignes plutôt que des triangles. On définit simplement une droite par l'équation y = px + b, avec p la pente. Sur R², cette équation fonctionne sans problème. Par contre, si on cherche à se restreindre à une grille (un treillis d'entiers), un problème se pose: Si |p| > 1, alors il n'est plus du tout trivial de dessiner une droite! En effet, Si on applique simplement l'équation pour notre jeu de point x, on obtient une courbe très peu convaincante.

En plus d'être une mauvaise droite, le calcul de nombre flottants est une opération coûteuse pour un ordinateur; Si on utilisait cet algorithme pour rastériser des lignes, le résultat serait très décevant.

On va présenter une technique élégante qui permet de discrétiser le problème de la ligne: Les chemins de Christoffel.

Christoffel à la rescousse!

Les symboles de Christoffel sont des objets mathématiques très abstraits, qui permettent entre autre de manipuler des objets sur des espaces pseudo-riemanniens. Ici on va les utiliser pour discrétiser notre problème. On définit un chemin de Christoffel comme suit:

"L'espace entre la droite et le chemin ne contenant pas d'autre points Z² autre que celui du chemin."

On a deux chemins qui remplissent cette condition: Le chemin supérieur et le chemin inférieur. On va ici se limiter au chemin inférieur, mais le chemin supérieur est également une bonne approximation de droite.

Le chemin de Christoffel supérieur
Le chemin de Christoffel inférieur

​​

​​​​

⠀⠀⠀⠀

⠀⠀⠀⠀

En coloriant le pixel juste au dessus du chemin inférieur, on obtient une représentation discrète de notre ligne. C'est la base de la rastérisation.

Un autre objet qui découle des chemins de Christoffel, sont les mots de Christoffel. Cela permet de représenter la grille sous la forme d'un mot, composé des caractères x et y. Pour obtenir le mot de Christoffel d'un chemin, on va de gauche a droite, et à chaque fois que le chemin se déplace latéralement, on ajoute un "x" au mot, et si le chemin "monte" on ajoute un "y" au mot.

Le mot de Christoffel de ce chemin est "xxyxxyxxyxy"

Appliquons cet algorithme:

En remplissant le pixel au dessus (ou en dessous, pour le mot de Christoffel inférieur, on obtient une bonne représentation d'une ligne).

Le mot de Christoffel de la droite de pente 12/7 est : xxyxyxyxxyxyxyxy

On répète ce mot autant de fois que l'ont veut pour dessiner notre droite.

On voit donc directement l'utilité de cet objet mathématique en informatique. Maintenant, on va s'intéresser aux propriétés de cet objet mathématique.

Les mots de Christoffel et les probabilités

Une des pistes de réflexion est : "Quel est la borne supérieure qu'un mot au hasard de longueur n soit un mot de Christoffel ?".

Déjà, il faut énumérer quelques propriétés qu'on peut remarquer sur les mots de Christoffel.

Pour commencer, un mot de Christoffel (inférieur), commencera toujours par un x, et finira toujours par un y. On peut le remarquer en étudiant l'algorithme, ou simplement en considérant la définition du chemin inférieur de Christoffel. On a une chance sur deux que notre premier caractère soit un x, et une chance sur deux que notre dernier caractère soit un y. Donc a une chance sur 4, c'est à dire 25% en borne supérieure que notre mot soit un mot de Christoffel.

C'est une première approximation qui réduit la probabilité. Mais ce n'est pas la seule propriété d'un mot de Christoffel. En effet, si on a le sous-mot xxyy, on sait directement que le mot n'est pas un mot de Christoffel. En effet, on voit que c'est une mauvaise approximation d'une droite, peu importe la pente (on fait un détour).

La probabilité d'avoir xxyy au début de notre mot est 1/16 (ou 2^-4). La probabilité de ne pas avoir xxyy est donc 15/16. On "joue" au jeu d'avoir xxyy n-4 fois (soit on a xxyy en position 1, soit on a xxyy en position 2, etc jusqu'à n-4 puisque xxyy est de longueur 4). Donc la probabilité d'avoir au moins un xxyy et l'inverse de la probabilité de "perdre" le jeu n-4 fois. Donc notre probabilité est :

La probabilité qu'un mot de longueur n contienne au moins une fois le sous-mot "xxyy" (ou n'importe quel sous-mot de longueur 4).

Mais ce n'est pas le seul sous-mot qui est impossible dans un mot de Christoffel. On a également le sous mot yyxx. On a donc cette fois 14/16 de chance de perdre. Donc la chance d'avoir au moins un xxyy ou yyxx est :

La probabilité qu'un mot de longueur n contiennent le sous-mot xxyy ou yyxx.

Donc la probabilité qu'un mot ne contiennent ni xxyy ni yyxx (la borne supérieur qu'un mot de longueur n soit un mot de Christoffel) est donc l'inverse:

La probabilité exacte

On a trouvé une borne supérieure de la probabilité qu'un mot de longueur n soit un mot de Christoffel. Mais si on faisait mieux ? Tentons de trouver la probabilité exacte qu'un mot de longueur n soit un mot de Christoffel.

Déjà, on va mettre de côté les mots de Christoffel dans un premier temps, et considérer un autre objet, qu'on va appeler une phrase de Christoffel. Une phrase de Christoffel est l'unique mot qui approxime une droite partant de (0, 0) et allant vers (a, b) (avec a, b des entiers naturels). Bien entendu il existe beaucoup d'approximations qui conviendrait, mais l'algorithme de Christoffel est déterministe, donc la même droite sera produite pour un point (a,b).

Imaginons que x est le vecteur (1,0), et y le vecteur (0,1). Si on considère le mot comme une somme de ses deux vecteurs, on doit aboutir à (a,b). Autrement dit, Le nombre de x dans le mot est égale à a, et le nombre de y dans le mot est égale à y.

On cherche maintenant à dénombrer les phrases de Christoffel. Pour un mot de longueur n, il y a (n+1) "proportions" de x y : par exemple pour n = 4 on peut mettre 4 x et 0 y, 3 x et 1 y, 2 x et 2 y... Il y a beaucoup d'arrangements possibles de ces x et y dans le mot, mais un seul de ces arrangements est une phrase de Christoffel (il existe un unique mot par couple de a,b). Il y a donc n+1 phrases de Christoffel pour un mot de longueur n.

On a donc compté le nombre de phrases de Christoffel. Tout mot de Christoffel est une phrase de Christoffel, mais l'inverse n'est pas vrai: par définition, dans un mot de Christoffel, le nombre de x et le nombre de y doivent être premier entre eux. On modifie donc notre comptage:

Note sur cet formule: Nous avons créée un programme qui a lancé l'algorithme avec a allant de 0 à 10 000, et pour chaque a, a testé chaque b de 0 à 10 000. Nous avons fait tourner l'algorithme de Christoffel pour chacun de ces paramètres, et pour chaque mot généré, nous avons pris sa longueur, afin de voir combien de mots de Christoffel de longueur n nous trouvions. La formule ci-dessus a prédit parfaitement combien de mots on s'attendait à avoir pour une longueur n.

(On rappelle que le symbole de Kronecker vaut 0 quand le terme du haut n'est pas égale a celui du bas, et 1 sinon.)

On ainsi trouvé le nombre exact de mots de Christoffel de longueur n. La probabilité d'avoir un mot précis de longueur n avec un alphabet de 2 caractères est 2^n. On multiplie donc cette probabilité par le nombre de mots de Christoffel pour cette longueur n. On trouve donc que notre probabilité est :

La probabilité qu'un mot de longueur n soit un mot de Christoffel.

On a donc trouvé mieux qu'une borne supérieure : La probabilité exacte qu'un mot de longueur n soit un mot de Christoffel.

On voit bien la puissance des mathématiques discrètes et de la combinatoire!

421 Cliquer pour recommander cet article