Inscription / Connexion Nouveau Sujet
Sequence Debruijn
Bonjour,
Je suis étudiant en école d'informatique et mon sujet me demande de faire un programme en Haskell qui peut (entre autre) dire si oui ou non la séquence donnée par l'utilisateur est une séquence de De Bruijn (on a aussi comme informations l'ordre et l'alphabet)
Jusque là pas de problème.
Mais je rencontre un problème mathématique sans rapport avec la programmation
Si on me donne ordre n = 0 et k (taille de l'alphabet) = 4 que suis-je sensé faire ?
Car normalement la taille de la séquence de Debruijn est définie par kn
Ici on aurais donc 40 = 1
Mais mettons que l'alphabet soit "ABCD", les séquences A -- B -- C -- D ne sont elle pas correctes ?
Ensuite on considère l'algorithme suivant ("prefer-one" tiré de la page wikipédia) :
Commencer avec une suite de n zéros
Essayer d'ajouter un 1 à la suite. Si les n derniers bits n'ont pas été rencontrés auparavant, accepter et répéter l'étape 2, sinon passer à l'étape suivante.
Essayer d'ajouter un 0 à la suite. Si les n derniers bits n'ont pas été rencontrés auparavant, accepter et répéter l'étape 2; sinon arrêter.
Pour n = 3, cette méthode produit successivement les suites :
000
0001 (001 est nouveau)
00011 (011 est nouveau)
000111 (111 est nouveau)
0001110 (111 déjà vu, mais 110 est nouveau)
00011101 (101 est nouveau)
000111010 (011 déjà vu, mais 010 est nouveau)
0001110100 (100 est nouveau)
fin( 001 et 000 sont déjà vus).
Si l'ont remplace tout les N par zéro, l'algorithme ne fait plus aucun sens (pour moi en tout cas)
Et bien voilà c'est tout, je ne savais pas à qui poser ce genre de question (ne me demandez pas de la poser à mon équipe d'enseignant, c'est compliqué disons (epitech pour les curieux))
Merci à vous d'avance
Je viens de voir que j'ai fait une erreur dans le premier post, je n'ai pas trouvé d'option d'edition donc :
J'ai homis de dire que le nombre de séquence de De Bruijn est définie par le calcul en pièce jointe
le resultat de ce calcul pour n = 0 et k = 4 est d'environ 1.40 de mémoire
2.21Bonsoir,
je viens de regarder la définition des séquences de De Bruijn sur wikipédia.
Il me semble clair que pour n=0 la seule séquence possible est vide.
Bonjour,
Tout d'abord merci pour votre réponse.
Cela voudrait donc dire que n= 0 est un cas particulier ?
Car pour x 
0 , x^0 = 1
Et k^n est sensé nous donner la taille de la ou les séquences de debruijn d'ordre n et de K symboles
Je suppose que la phrase qui vous fait dire cela est la suivante :
toutes les suites de longueur n
Cependant je trouve étonnant que personne n'en parle nul part, je veux bien que les séquences de De Bruijn ne soient pas particulièrement connus mais tout de même.. J'ai l'impression de louper quelque chose
Annuler
connectez vous