Inscription / Connexion Nouveau Sujet
Niveau algorithmique
Partager :

Sequence Debruijn

Posté par
mathis01250
03-05-18 à 22:50

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) :  

Citation :
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

Posté par
mathis01250
re : Sequence Debruijn 03-05-18 à 23:22

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

Sequence Debruijn

Posté par
mathis01250
re : Sequence Debruijn 03-05-18 à 23:30

Décidément ! le résultat est plutot 2.21

Posté par
verdurin
re : Sequence Debruijn 04-05-18 à 01:08

Bonsoir,
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.

Posté par
mathis01250
re : Sequence Debruijn 04-05-18 à 04:14

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 :

Citation :
toutes les suites de longueur n
et il est vrai que je la comprends comme vous
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

Posté par
verdurin
re : Sequence Debruijn 06-05-18 à 19:09

Je pense que le cas n=0 est particulièrement inintéressant.
Et c'est sans doute pour cette raison qu'il n'est pas pris en compte dans la formule.

En mathématiques appliquées, j'ai cru remarquer que les cas triviaux étaient facilement négligés.



Vous devez être membre accéder à ce service...

Pas encore inscrit ?

1 compte par personne, multi-compte interdit !

Ou identifiez-vous :


Rester sur la page

Désolé, votre version d'Internet Explorer est plus que périmée ! Merci de le mettre à jour ou de télécharger Firefox ou Google Chrome pour utiliser le site. Votre ordinateur vous remerciera !