[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

Tu peux donner l'algo pour couper en 2 ?
Je pourrai ptet m'en inspirer.

Bonsoir, je viens de trouver la solution. En fait c'est très simple, grâce à mon algo pour trouver la médiane d'un mot. La petite astuce est de le réutiliser récursivement jusqu'à que la longueur du mot soit égale à 1. Je m'explique avec un petit exemple.


#XXXXXXXXXX#
//1) je remplace le premier et le dernier X par des M (symbole de mediane)
#MXXXXXXXXM#
//2) dans la partie gauche(à la premiere étape il y a une seule partie),je cherche la médiane gauche (si le nombre est paire je prend celui de gauche)
#MXXXMXXXXM#
//3)dans la partie droite je cherche la mediane droite
#MXXXMXXMXM#
//je recommence à l'étape 2 tant qu'il y au moins un X entre les M
2)-->#MXXXMMXMXM#
3)--->#MXXXMMMMXM#
//ici je me deplace à droite et je remplace tout par C jusqu'au #
#MXXXMMMMXM#

merde ça ne marche plus ...
Je continue à chercher

PS: des je trouve je balance un rapport complet PDF (celui que je vais rendre) avec le fichier turing fonctionnant sous visual turing.
Voilà

C'est normal que çela ne marche pas..
Tu t'es planté dans la première médiane, ça doit donner : #MXXXMMXXXM#
Tu peux mettre ton algo complet de médiane stp ? je crois avoir une idée mais pas sur...

Folkene a écrit:
PS: des je trouve je balance un rapport complet PDF (celui que je vais rendre) avec le fichier turing fonctionnant sous visual turing.
Voilà

Intéressant !

Si tu veux que je l'ajoute sur mon site après, fais-moi signe.

Dès que je termine, il n'y aura pas de problème. Par contre tu as un site?

Oui et voici le lien direct où je mettrai ton pdf : http://julien.marmin.free.fr/forum/index.htm

Comment trouves-tu cette médiane en n log n ?

avec la technique pair/impaire qui consiste à prendre un element sur 2 (d'ou le Nlog(N)).
En fait on fait un premier parcours afin de savoir si le nombre de X est pair ou impaire. Si il est paire, on met un marqueur en fin de mot afin de rendre le mot restant impair (on se trouve tout à droite).

Ensuite en revenant, avec le changement d'état on identifie si le nombre de X restant est pair ou impair:
-si impaire on remplace un X sur 2 par un marqueur à partir du premier X
-si pair, on remplace un X sur 2 par un marqueuren partant du second X trouver.

A la fin on remplace tout les marqueur par X, et le X par un M (pour médiane ). Si on arrive au bout et que l'on trouve le premier marqueur (si nombre de X est pair) alors on revient jusqu'au M et on place un autre M juste à gauche.

Voilà l'algo dans les grandes lignes

Si je ne me trompe pas, voici le déroulement de ton algo sur un mot de longueur 5 :

#XXXXX# // nombre de 5 impair et la tête de lecture à droite
#TXTXT# // Je remplace un X sur 2 en commençant par le premier X (celui de droite)

Déjà à ce stade là, le milieu est remplacé par un marqueur alors qu'il fallait pas, c'est pour ça je n'ai pas continué.
Par contre ça marche pour un mot de longueur 7, il laisse un seul X à la fin qui est la bonne médiane.

Tu peux me dire si j'ai fait une erreur ?

Bonjour,
J'ai trouvé une solution bien moche mais qui fonctionne parfaitement bien et en Nlog(N). Vous allez voir c'est assez tordue.
je place un marqueur toutes les 3 cases en partant de la première.
ensuite je les comptes en binaires. Je stocke ce nombre après le mot.
puis je décompose ce nombre binaire dans le sens inverse.on trouve le nombre de C. On utilise l' algorithme de la médiane (énoncé avant). Ainsi la première médiane en partant de la droite correspond au premier B. Il nous reste plus qu'à faire un passage pour mettre les A et les B.

Conclusion:
Mettre un marqueur sur 3 O(N)
Compter en binaire 0(Nlog(N/3))
Transformer le binaire en C O(N(log(N/3))
mediane O(2N/3(log(2N/3))
Remplissage de A et de B O(2N/3)

soit la complexité de l'ensemble est en O(Nlog(N))

Je vais mettre à disposition les fichier .tur fonctionnant sous visual turing.
Merci encore à duche et à julien pour m'avoir aidé

Comment fais-tu pour faire le comptage binaire en O(n log n) ?
Comme tu as un nombre fini d'états, tu es bien obligé d'incrémenter ton compteur à la fin à chaque fois que tu rencontre un marqueur non ?
Et dans ce cas, pour au moins la moitié des marqueur tu devras parcourir au moins la moitié de ton mot initial, donc au moins (n/2)^2 pas...

en fait pour compter en binaire il suffit de prendre la propriété des nombres lorsque que tu le convertis:
en gros:
19 = 2^4 + 2^1 + 2^0.
pour réussir à faire cela, tu marques 1 element non marqué sur 2. Si tu es passé sur un nombre d'élément, tu ecris un 1, si le nombre est pair, sinon tu écris un 0.

exemple:
element non marqué: X
element marque: x
delimiteur de mot #

#XXXXXXXXX##########

//1er passage
#xXxXxXxXx#1######### //on ecrit un 1 car 9 X non marquer avant le passage
//2eme passage
#xxxXxxxXx#10########//0 car on est passé sur 4 X
//3eme passage
#xxxxxxxXx#100#######//0 car on est passé sur 2 X
//4eme passage
#xxxxxxxxx#1001######//1 car on est passé sur 1 X
//au retour c'est fini car plus aucun X
nous avons effectué 4 * 9 passages soit (N)log(N)
Je ne compte pas dans les passages l'écriture des nombres apres le # de fin de mot. car il correspond à la somme de (log(N))! quasiment faible. voilà

Moi je m'appelle Franck et je crois qu'avec la force de Dieu je peux t'aider. Pour cela il va falloir que tu me précises ce que tu entends n² et nlog(n)

ailedoiseau a écrit:Moi je m'appelle Franck et je crois qu'avec la force de Dieu je peux t'aider.

C'est une blague ?

ailedoiseau a écrit:Moi je m'appelle Franck et je crois qu'avec la force de Dieu je peux t'aider. Pour cela il va falloir que tu me précises ce que tu entends n² et nlog(n)

Ca risque d'être compliqué à expliquer malheureusement

lol trop fort franck