IREM | Autour de l’arbre de Stern-Brocot

Résumé

La petite histoire raconte que Dieu créa les fractions 0=0/1, infini=1/0 et, dans sa grande sagesse, permit, à partir des fractions a/b, c/d, l'engendrement de la fraction (a+b)/(c+d) .

Et bien lui en prit, car toutes les fractions (positives) sont ainsi engendrées !
Mais qui pourrait vérifier une telle histoire ?
Toujours est-il que c'est là le point de départ de notre exposé.
Mais de quoi s'agit-il plus précisément ?

Réaliser une courte excursion d'une heure dans les domaines de l'arithmétique élémentaire, mathématiques discrètes et algorithmique algébrique.
Le nombre rationnel positif est au cœur du débat.
Nous montrerons en particulier en quoi l'arbre de Stern-Brocot permet un codage binaire de Q+, via le monoïde {G,D}+ à deux générateurs.
L'arbre de Stern-Brocot débouche également sur un certain nombre d'autres notions : citons par exemple les réduites d'une fraction, les fractions continues, les polynômes continuants, le groupe SL2(Z) (constitué des matrices 2x2 à coefficients entiers de déterminant 1), les homographies ......
Nous n'hésiterons pas à fournir des programmes en Maple pour permettre d'illustrer notre discours.

Aucune connaissance particulière n'est requise pour cet exposé.