[Machine de turing]Recherche meilleur Algorithme

Bonjour,
Je ne me suis pas présenté, je m'appelle wally je suis étudiant et dans le cadre d'un projet sur la machine de turing, je dois réaliser le meilleur algorithme pour l'exercice suivant:

Remplacer une suite de X par une suite de A suivie de suite de B suivie d'une suite de C avec |A| <= |B| <= |C| <= |A| + 1

voilà des exemples:

X = C
XX = BC
XXX = ABC
XXXX = ABCC
XXXXX = ABBCC
XXXXXX = AABBCC

Un premier algorithme en n² (avec n le nombre de X) est déja creer, et j'aimerai que vous m'aidez a en trouver en nlog(n)

J'espere que quelqu'un pourra m'aider rapidement , à très bientot

Salut et bienvenue sur le forum !

Tu pourrais écrire l'algo en n² s'il-te-plaît ?

Et tu as le droit à combien de rubans ?

Alors, on a droit qu'à un seul ruban et mon algo est le suivant.
En gros j'utilise un marqueur que je position tout les 3 X en partant de la fin, Chaque Marqueur correspond à un C
Ensuite il me suffit de découper en 2 le reste

1)on remplace un X par un C tout à droite
2)on se déplace de 3 vers la gauche et on place un marqueur (Y pour moi)
2) b) si on arrive à la fin du mot avant les déplacement vas à 9)
3)droite tant que ce n'est pas un C
4)gauche quand on voit un C
5) on remplace le X par un C
6) gauche tant que ce n'est pas mon marqueur(Y)
7) on remplace le marqueur par un X
recommence à 2)

9)Droite tant que je n'est pas un C ou un B
10) Gauche
11) je remplace le X par B, si A ou marqueur fin de mot alors fin du programme
12) Gauche tant que c'est un X
13) droite (on a un A ou un marqueur fin de mot)
14) remplace le X par un A
15) faire 9)

Voilà c'est très lourd en terme de temps avec le simulateur que j'utilise
Merci d'avoir réagit aussi vite à mon problème

edit1= correction des erreurs aux étapes 3 et 4 gauche et droite

OK. Pour X, XX et XXX, c'est bon.

Par contre après, je vois pas trop comment ça fonctionne...

Si je déroule l'algo sur XXXX, ça donne quoi étape par étape ?
Parce que moi je trouve ça :
XXXX
XXXC
YXXXC
YAXXC
YAABC

Où c'est que je me trompe ?

ça donne
#XXXX#
#XXXC#
#XXXC#
#XXXC#
#YXXC#
#YXXC#
#YXXC#
#YXXC#
#YXCC#
#XXCC#
#XXCC#
#XXCC#
#XXCC#
#XBCC#
#XBCC#
#XBCC#
#ABCC#
#ABCC# A Gauche du B il y a un A donc terminer

Voilà

edit1= erreur de soulignage
edit2= tu avais raison à l'étape 3 c'est droite et pas gauche désoler

Ah en effet, je vois mieux le truc à présent...

Ca marche pas ça ? (c'est un peu plus court mais ce n'est pas encore du n*log(n) et ce n'est peut-être pas juste... surtout que c'est que sur un exemple.)

#XXXX#
#XXXC#
#XXBC#
#XABC#
#AABC#
#AABC#
#AABC#
#AABC#
#AACC#
#ABCC#

Bonsoir,
Sur cette exemple ça fonctionnerai, seulement il y a deux probleme. Le premier est de faire un algo de cela, et le second est de voir si l'algo est vraiment en nlog(n). Ici il y a que 4 lettres donc l'aller/retour de la tête de lecture se fait rapidement. Maintenant sur un exemple à N X, au premier parcour on fait 3 puis l'aller/retour jusqu'a premier C et ainsi de suite. La complexité d'un tel algorithme est de n² et plus de nlog(n).
Je pense que pour bien démarrer, il faudrait trouver un algo en nlog(n) d'un partitionnement en 3, c'est à dire trouver le C qui sera le plus à gauche. Si je trouve quelque chose je post
Bonne soirée

OK. Et t'as le droit qu'à une seule tête de lecture ?

oui, une seule

Ho ce problème est intéressant.
C'est encore d'actualité ? J'ai un algo sympa:

On a l'entrée
XXXXXXXXXXXXX
La tête de lecture commence par se mettre tout à droite et revient vers la gauche en écrivant des séquences C B A C B A ...
Elle finit tout à droite avec:
CABCABCABCABC

On a le nombre de caractères de chaque sorte nécessaire. Il ne reste plus qu'à trier le vecteur.
Je ne sais pas s'il existe un algo de tri en moins de n^2 sur machine de turing. En tout cas il existe un algo tout simple dans ce cas ci:
La tête part de la gauche et cherche un C, lorsqu'elle en a trouvé un elle le permute pour l'amener tout à droite.
La tête part de la droite et cherche un A, lorsqu'elle en trouve un, elle le permute pour l'amener tout à gauche.
On ajoute à cela un test: lorsuqu'elle trouve un C elle fait d'abord un aller retour à droite pour voir s'il y a encore des B ou des A derrière, s'il n'y en a plus, elle n'a plus à classer les C. Idem pour les A. Quand elle n'a plus rien à déplacer, le vecteur est trié
AAAABBBBCCCCC

La tête parcourt tout le vecteur pour chaque C et chaque A, c'est à dire à peu près 2n/3 fois.
C'est donc un algo en n^2, mais beaucoup plus élégant que le tien :-)

C'est certainement plus beau mais le swap n'existe pas sur une machine
de turing à 1 seul bande sauf si on parcourt 2 fois la distance en
mettant un marqueur pour identifiant la lettre retour.
Merci de ta réponse, j'apprécie beaucoup le fait que tu as cherché à m'aider

Comment ça le swap n'existe pas ? 0_o
Il suffit de jouer avec les états !

Voici l'algo au complet:

Alphabet: { # , A , B , C , X }
Etat initial: E0
Etat acceptant: E18

Situation initiale:
###[X]XXXXXXXXXXXXXXX###

Fonction de transition:

/* Etat initial et progression vers la droite */
f(E0,X) = (E0,X,R)
/* Retour vers la gauche en écrivant C B A C B A C B A */
f(E0,#) = (E1,#,L)
f(E1,X) = (E2,C,L)
f(E2,X) = (E3,B,L)
f(E3,X) = (E1,A,L)
/* Détection de l'arrivée au bout du ruban */
f(E1,#) = (E4,#,R)
f(E2,#) = (E4,#,R)
f(E3,#) = (E4,#,R)
/* Recherche d'un A */
f(E4,B) = (E4,B,R)
f(E4,C) = (E4,C,R)
f(E4,A) = (E5,A,R)
/* Swap du A avec son voisin de droite */
f(E5,B) = (E6,A,L) /* ecrit un A et revient en arrière pour ecrire B */
f(E6,A) = (E4,B,R) /* ecrit le B et revient sur le A dans l'etat initial de swap */
f(E5,C) = (E7,A,L) /* même principe pour C et A */
f(E7,A) = (E4,C,R)
f(E5,A) = (E8,A,L)
f(E8,A) = (E4,A,R)
/* Détection de fin de swap de A */
f(E5,#) = (E9,#,L)
/* Recherche d'un C */
f(E9,A) = (E9,A,L)
f(E9,B) = (E9,B,L)
f(E9,C) = (E10,C,L)
/* Swap du C avec son voisin de gauche */
f(E10,B) = (E11,C,R)
f(E11,C) = (E9,B,L)
f(E10,A) = (E12,C,R)
f(E12,C) = (E9,A,L)
f(E10,C) = (E13,C,R)
f(E13,C) = (E9,C,L)
/* Détection de fin de swap de C */
f(E10,#) = (E14,#,R)
/* Test de finalité */
f(E14,A) = (E14,A,R)
f(E14,B) = (E15,B,R)
f(E14,C) = (E17,C,L)
f(E15,A) = (E17,A,L)
f(E15,B) = (E15,B,R)
f(E15,C) = (E16,C,R)
f(E16,A) = (E17,A,L)
f(E16,B) = (E17,A,L)
f(E16,C) = (E16,C,R)
f(E16,#) = (E18,#,R)
f(E17,A) = (E17,A,L)
f(E17,B) = (E17,B,L)
f(E17,C) = (E17,C,L)
f(E17,#) = (E4,#,R)


Avant de critiquer les réponses de gens chez qui tu es venu les chercher, il faudrait peut-être réfléchir un petit peu... et envisager qu'il y a des personnes qui en savent plus que toi sur le sujet !

Duche a écrit:Avant de critiquer les réponses de gens chez qui tu es venu les chercher, il faudrait peut-être réfléchir un petit peu... et envisager qu'il y a des personnes qui en savent plus que toi sur le sujet !

Je ne pense pas qu'il critiquait d'après ceci :

Folkene a écrit:Merci de ta réponse, j'apprécie beaucoup le fait que tu as cherché à m'aider

J'ai trouvé ça très hautain, peut-être que je me trompe.

En tout cas, le swap d'éléments adjacents sur une machine à alphabet fini se fait bien en temps constant.

Non non je ne critiquais pas, autrement, j'essaie juste de faire des réponses constructives pour le problème posé. Maintenant si je me trompe (et je me suis trompé), n'hésitez pas à me le dire. En tout cas en aucun cas je me permettrais de mettre en doute vos connaissances, sinon pourquoi aurais je postais sur ce forum? Voilà.

Ok, alors tout va bien :-)

Sinon pour un algo en N log N j'ai des doutes. Tout simplement car un algo dont la complexité contient un log est généralement récursif, ce qui ne me semble pas possible avec une machine de turing ( à première vue puisqu'on ne peut pas se rentre à un endroit précis du ruban en temps constant ).

Connais-tu la complexité optimale de ce problème ? Ou espère-tu seulement qu'elle est meilleure que N^2 ?

Encore, si on avait le droit à plusieurs rubans ou plusieurs têtes de lecture, on pourrait faire du récursif, mais là, moi aussi je ne vois pas comment faire.

Pour faire du récursif il faudrait un nombre non borné de ruban. Ce serait comme utiliser un alphabet infini, ce ne serait plus une machine de turing ;-)

La meilleure solution est en N log(N), et d'apres notre prof, il fait entre 20 et 30 états. Bon au pire des cas j'aurais la solution vendredi, je la posterais immédiatement

Si je sais qu'il y a qqch a chercher alors je vais y réfléchir :-)

Bonsoir,
J'ai trouver une petite solution toujours en n² mais qui est beaucoup plus rapide.
Le principe est simple je mets tout à droite abc et à chaque tour je deplace de 3 vers la droite le a, de 2 le b et de 1 le c.
A la fin on obtient un mot du genre
#AX...XXBX..XXCXX.XX#
il nous reste plus qu'à remplacer les X par tant qu'on a pas trouver de C. Ensuite on remplace des X par les B tant qu'on a pas de B et pour finir des X tant qu'on a pas de A. A la fin c'est fini.

Déso pour les faute d'orthographe et bonne soirée

Comment décides-tu quand t'arrêter ?
Sachant que tu n'a pas nécessairement un multiple de 3 de X ?

Sinon c'est une bien belle idée.
Je suis en train de me demander s'il n'y a pas moyen de déterminer ce B et ce C en temps N log N

je m'arrete lorsque que je trouve un # apres le A.
En fait il y a 3 possibilité:
- la premiere est lorsque je trouve immédiatement le # apres le A dans ce cas, je reviens, je replace le A
-le deuxieme est lorsque je trouve un # apres un X quand je deplace le A. Dans ce cas je remplace le dernier X par le A et je deplace le B et C d'une case vers la gauche également
- le troisieme est lorsque je trouve le # apres 2 X quand je deplace le A. Dans ce cas je remplace le dernier X par le A et je deplace le B de 2 cases et le C d'une case vers la gauche.
Ensuite je fini en remplaçant les X par ce qui convient.

Mon idée est de trouver le dernier en C en N log(N). Ensuite le dernier B sera beaucoup plus simple car c'est juste faire coupé en deux le mot.

Tu ne peux pas "couper en deux" si facilement... si ?

Pour couper en deux je peux le faire en Nlog(N), du coup c'est juste le tiers qui me casse les couilles. L'astuce consiste a prendre un element sur 2 voilà. en tout cas ça marche