[Machine de turing]Recherche meilleur Algorithme

Rappel du premier message :

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

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