Machine de Turing : problème du drapeau hollandais

Bonjour à tous!

Tout d'abord, merci à ceux qui prendront le temps de me lire

Je vous explique mon problème :

je dois réaliser une machine de turing (à un ruban, considéré comme infini des deux côtés) qui règle le problème dit du "Drapeau Hollandais", c'est à dire remplace par une série d'un caractère défini par un tiers de A, un tiers de B et un tiers de C, avec A <= B <= C

Par exemple :
xxx => ABC
xxxx => ABCC
xxxxx => ABBCC
xxxxxx => AABBCC
etc...

J'ai déjà trouvé deux solutions différentes :
* Faire une marque tous les trois caractères, remplacer le nombre de marques par des C a la fin, puis remplacer le reste en mettant un B à droite, un A à gauche, etc...
* Partir sur une base ABC, et à chaque nouveau caractère, ajouter la bonne lettre et décaler l'existant (par exemple, on remplace le premier B par un A, le premier C par un B, et le nouveau caractère par un C).

Si ces deux solutions donnent le résultat souhaité, elles ne sont pas assez performantes. En effet, leur complexité est de l'ordre de n² (avec n le nombre d'éléments à remplacer), et je cherche une solution en n.log(n)...

Je pense qu'il doit falloir sans doute commencer par remplacer les X de la manière suivante :
XXXXX -> CBACB
Puis les trier avec un algorithme efficace mais cela fait déjà 8 heures que je me casse la tête dessus et je n'ai toujours trouvé aucune solution améliorant ne serait ce qu'un peu la complexité... J'ai essayé d'adapter différents algorithme de tri connu en programmation mais les appliqués sur la machine de turing augmente énormément leur complexité.

Si quelqu'un a une idée, une piste, ou des questions... Merci à vous!

Bonjour,

Citation:

---

Envoyé par Chido42

J'ai déjà trouvé deux solutions différentes :
* Faire une marque tous les trois caractères, remplacer le nombre de marques par des C a la fin, puis remplacer le reste en mettant un B à droite, un A à gauche, etc...

---

Oui, mais pour cela, il faut maintenir un compteur, et ce n'est pas facile avec une machine de Turing. En plus, c'est très coûteux ! Mais le point de départ est le bon, je pense.

Citation:

---

* Partir sur une base ABC, et à chaque nouveau caractère, ajouter la bonne lettre et décaler l'existant (par exemple, on remplace le premier B par un A, le premier C par un B, et le nouveau caractère par un C).

Si ces deux solutions donnent le résultat souhaité, elles ne sont pas assez performantes. En effet, leur complexité est de l'ordre de n² (avec n le nombre d'éléments à remplacer), et je cherche une solution en n.log(n)...

---

Bon, je viens de faire la mienne à mon tour (en langage C) et elle fonctionne. J'utilise onze états, dont l'état final, et un état dédié au traitement du mot vide. L'idée consiste à faire du ping-pong entre les deux extrémités et à « attraper » un caractère au passage pour le déposer à la première place libre après le « rebond ».

Le nombre de cycles nécessaires vaut 4/9⋅n² C'est donc une complexité en n² mais qui vaut toujours 44 % de cette valeur. Sur les petites séquences, elle est plus proche de n.log(n) que de n².

Oui je l'ai aussi constaté car j'ai testé aussi cette solution malheureusement comme tu le dis la complexité reste en O(n²). J'ai pensé a une autre solution qui consiste à utiliser un compteur en O(nlog(n)) puis a le decrementer tout en le déplaçant. C'est beaucoup plus couteux sur les petits mots mais sur les grands il me semblent que la complexité serait peut être en O(nlog(n))

Je vais tester ça en tout cas merci pour ta réponse.

Citation:

---

Envoyé par Chido42

Je vais tester ça en tout cas merci pour ta réponse.

---

À ton service mais, du coup, ça m'intéresse beaucoup de savoir comment tu implémentes ton compteur avec ta machine de Turing. Même si l'on sait que le modèle permet d'implémenter, en principe, tout problème qui soit formulable par l'homme, la gestion du compteur n'est-elle pas, en elle-même, encore plus coûteuse ?

Non, il me semble que j'ai enfin réussi à avoir quelque chose en O(nlog(n)) mais sans doute avec un facteur assez important devant, donc ta méthode en O(n²) sera sans aucun doute plus efficace pour de petits nombres.

J'explique le principe de mon algorithme :

— Tout d'abord je remplace 1 X sur trois par, alternativement et dans cet ordre, un R, un J, un N ;
— Ensuite avec un compteur en nlog(n), je compte le nombre de R et N en même temps (en prenant un R sur deux et un N sur deux et, avec la parité, en ajoutant soit un 1 soit un 0 à mon compteur binaire) ;
— Puis, je décrémente le compteur binaire d'abord pour les R, ensuite pour les N. En le décalant à chaque décrémentation en mettant un invariant (pouvant prendre la valeur 0 ou 1) en fonction de la position du compteur afin de déterminer les limites de la zone de X. Je pense que cette décrémentation ce fait en O(R(log R)) avec R le nombre de R donc globalement N/3 ;
— Et enfin en un passage je remplace les différents 0 et autres caractères par ceux appropriés.

Voila. Si jamais quelqu'un voit une erreur dans mon calcul de complexité, je suis très intéressé. En tout cas, merci pour les réponses en espérant que cela puisse aider quelqu'un dans le futur !

Je pourrais éventuellement poster ma machine créée avec Visual Turing V1.0 après ce mercredi si tu es intéressé.

Citation:

---

Envoyé par Chido42

— Tout d'abord je remplace 1 X sur trois par, alternativement et dans cet ordre, un R, un J, un N ;
— Ensuite avec un compteur en nlog(n), je compte le nombre de R et N en même temps (en prenant un R sur deux et un N sur deux et, avec la parité, en ajoutant soit un 1 soit un 0 à mon compteur binaire) ;

---

D'accord mais comment maintiens-tu ce compteur binaire ?

Si c'est ta machine de Turing qui s'en charge, et que tu l'as mis sur ta bande à côté de ta série de « X », alors à chaque incrémentation, il faudra aller chercher le compteur, l'incrémenter, puis regagner ta dernière position. Comme tu pars depuis le début et que tu vas jusqu'à la fin, ça fait en moyenne n÷2 éléments à parcourir, comme tu fais l'aller-retour, ça fait n, et comme tu le fais pour un R sur 2 et un N sur 2, ça fait n÷3 itérations. Donc, au final, 1∕3⋅n² cycles consacrés à aller chercher le compteur, plus n⋅log(n) pour le mettre à jour.

Ai-je manqué quelque chose ?

Citation:

---

Voila. Si jamais quelqu'un voit une erreur dans mon calcul de complexité, je suis très intéressé. En tout cas, merci pour les réponses en espérant que cela puisse aider quelqu'un dans le futur !

Je pourrais éventuellement poster ma machine créée avec Visual Turing V1.0 après ce mercredi si tu es intéressé.

---

Avec grand plaisir ! Ce sera profitable à beaucoup de monde, et le problème m'intéresse effectivement beaucoup.

Bon je sais que je suis un peu à la bourre mais voici la solution que j'ai trouvé. Je pense avoir juste en disant qu'elle est bien en O(N*log(N)) mais je n'ai pas encore eu la note alors ^^.

Je met le tout sur megaupload pour les interesser il y a aussi le setup de la version que j'ai utiliser de Visual Turing.

En espérant que ça aide ^^

MEGAUPLOAD - The leading online storage and file delivery service@@AMEPARAM@@Filename:</font> <font style="font-family:arial; color:#FF6700; font-size:18px; font-weight:bold;">Turing_Drapeau_Hollandais.zip@@AMEPARAM@@Turing_Drapeau_Hollandais.zip

Grand merci pour ton partage d'expérience ! Malheureusement, je n'arrive pas à télécharger ton fichier…

Je relance ce sujet car je trouve cela intéressant. Quelqu'un aurait-il d'autres informations sur un moyen de résoudre le problème du drapeau hollandais avec une machine de turing à une bande?

C'est-à-dire qu'on a résolu le sujet en lui-même, ici. Le problème portait sur la complexité de la solution.