Mots de De Bruijn
Présentation
Chaînes circulaires, les plus courtes possibles, contenant tous les mots de longueur n d'un alphabet A.
Ces mots peuvent être, par exemple, des codes d'accès de portes d'immeubles ...
On a un alphabet A de p = |A| lettres et on cherche une chaîne circulaire contenant tous les mots de n lettres écrits dans cet alphabet.
Soit G le graphe orienté dont les sommets sont les pn-1 mots de n-1 lettres et dont les arcs sont les pn mots de n lettres, l'arc d'origine aX et d'extrémité Xb étant de la forme aXb.
Trouver une suite de de Bruijn revient à trouver un circuit eulérien. Pour tout sommet s, les degrés d-(s) et d+(s), nombres d'arcs entrants et sortants, sont égaux (par symétrie !) et donc un circuit eulérien existe.
Ces mots peuvent être, par exemple, des codes d'accès de portes d'immeubles ...
On a un alphabet A de p = |A| lettres et on cherche une chaîne circulaire contenant tous les mots de n lettres écrits dans cet alphabet.
Soit G le graphe orienté dont les sommets sont les pn-1 mots de n-1 lettres et dont les arcs sont les pn mots de n lettres, l'arc d'origine aX et d'extrémité Xb étant de la forme aXb.
Trouver une suite de de Bruijn revient à trouver un circuit eulérien. Pour tout sommet s, les degrés d-(s) et d+(s), nombres d'arcs entrants et sortants, sont égaux (par symétrie !) et donc un circuit eulérien existe.
Exemple 1
Les 25 mots de 2 lettres utilisant les cinq chiffres de 0 à 4 inclus, sont contenus dans la chaîne circulaire
0102030411213142232433440
(00 est obtenu en refermant la chaîne sur elle-même ...3440<->01020...)
(00 est obtenu en refermant la chaîne sur elle-même ...3440<->01020...)
Exemple 2
L'alphabet est {0, 1}, tous les mots de longueur 5 sont contenus dans la
chaîne (circulaire) 01000110010100111010110111110000
Cette chaîne permet de trouver sur le graphe ci-dessous un circuit eulérien de sommets 0100, 1000, 0001, 0011 ... et d'arcs 01000, 10001, 00011, 00110 ...
Cette chaîne permet de trouver sur le graphe ci-dessous un circuit eulérien de sommets 0100, 1000, 0001, 0011 ... et d'arcs 01000, 10001, 00011, 00110 ...
Recherche des chaînes
Le programme JavaScript utilisé ci-dessous arrête sa recherche à la 10ième chaîne solution.
Chaque solution est écrite sur une ligne différente.
Gardez une taille raisonnable à l'alphabet et évitez les longs mots.
Essayez aussi le parcours eulérien ou mieux, compilez le programme C.
Gardez une taille raisonnable à l'alphabet et évitez les longs mots.
Essayez aussi le parcours eulérien ou mieux, compilez le programme C.
Liens
Wikipédia Nicolaas Govert de Bruijn (né le 9 juillet 1918, mort le 17 février 2012). Mathématicien hollandais.
Mots de de Bruijn Recherche de circuit eulérien
debruijn.c Programme en C de recherche des mots de de Bruijn
Page de liens sur les mathématiques
Page de liens sur les mots et les chaînes
Page de liens sur les polynômes cyclotomiques
Page de liens sur la combinatoire
de Bruijn Sequence MathWorld
String MathWorld
Un problème de digicode par Thomas Chomette CultureMATH Accompagnement et Culture Mathématiques.
Pour un premier contact, [utilisez ce formulaire] ou utilisez l'adresse de messagerie qui y figure. Merci d'indiquer la page précise du site "http//jm.davalan.org/...", cela m'aidera beaucoup. Ne joignez aucun document à votre message.
Jeux-et-Mathématiques n'est pas un site commercial. Aucun des liens placés sur ce site n'est rémunéré, ni non plus aucune des informations données.
Important : Si votre question a un quelconque rapport avec un travail personnel (Devoir TIPE Master...) , vous devez absolument me le préciser dès votre premier message et m'indiquer très précisément les limites des informations demandées. Vous devez aussi avertir la personne qui dirige éventuellement votre travail ou le corrige de cette communication et lui montrer les documents fournis.
© (Copyright) Jean-Paul Davalan 2002-2014Important : Si votre question a un quelconque rapport avec un travail personnel (Devoir TIPE Master...) , vous devez absolument me le préciser dès votre premier message et m'indiquer très précisément les limites des informations demandées. Vous devez aussi avertir la personne qui dirige éventuellement votre travail ou le corrige de cette communication et lui montrer les documents fournis.
J'essaie de répondre aux questions posées, mais ne lis pas les documents mathématiques amateurs, pas plus que je ne donne mon avis sur les démonstrations des conjectures de Collatz ou autres. Je ne lis pas les documents word, je ne corrige pas les programmes informatiques et depuis des années je n'utilise plus de tableur.