MP/MP*: Option Informatique
Devoir surveillé du samedi 9 février 2008

Une relation de réécriture;
représentants minimaux pour l'ordre lexicographique;
encore une transformation conservant le caractère rationnel;
un système de numération exotique



Le premier problème part d'un exercice posé à l'oral d'une grande école, et reproduit dans la Revue de mathématiques spéciales (volume 117, numéro 3). On propose l'étude d'une relation de réécriture, ainsi que des classes modulo cette relation; on montre que l'ensemble des représentants de ces classes est un langage rationnel; on demande la programmation de deux fonctions; enfin, on établit un résultat plus général, lié à l'ordre lexicographique.

À côté de la numération de position en base 10 ou en base 2, il existe bien d'autres systèmes de numération exotiques: numération redondante (avec les chifres 0, 1 et -1); numération en base de Fibonacci (système de Zeckendorf); numération en base complexe. Le deuxième problème présente un système utilisant une base fractionnaire; vous serez à nouveau amené à écrire des fonctions en Caml. Ce problème a déjà été posé en 2005 (cliquez ici).

Un très grand merci à Jean-François Husson pour son aide précieuse.