IdentifiantMot de passe
Loading...
Mot de passe oublié ?Je m'inscris ! (gratuit)
Navigation

Inscrivez-vous gratuitement
pour pouvoir participer, suivre les réponses en temps réel, voter pour les messages, poser vos propres questions et recevoir la newsletter

Algorithmes et structures de données Discussion :

Machine de Turing : problème du drapeau hollandais


Sujet :

Algorithmes et structures de données

Vue hybride

Message précédent Message précédent   Message suivant Message suivant
  1. #1
    Membre régulier
    Inscrit en
    Décembre 2009
    Messages
    10
    Détails du profil
    Informations forums :
    Inscription : Décembre 2009
    Messages : 10
    Par défaut 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!

  2. #2
    Modérateur
    Avatar de Obsidian
    Homme Profil pro
    Chercheur d'emploi
    Inscrit en
    Septembre 2007
    Messages
    7 487
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 49
    Localisation : France, Essonne (Île de France)

    Informations professionnelles :
    Activité : Chercheur d'emploi
    Secteur : High Tech - Éditeur de logiciels

    Informations forums :
    Inscription : Septembre 2007
    Messages : 7 487
    Par défaut
    Bonjour,

    Citation Envoyé par Chido42 Voir le message
    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.

    * 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².

  3. #3
    Membre régulier
    Inscrit en
    Décembre 2009
    Messages
    10
    Détails du profil
    Informations forums :
    Inscription : Décembre 2009
    Messages : 10
    Par défaut
    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.

  4. #4
    Modérateur
    Avatar de Obsidian
    Homme Profil pro
    Chercheur d'emploi
    Inscrit en
    Septembre 2007
    Messages
    7 487
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 49
    Localisation : France, Essonne (Île de France)

    Informations professionnelles :
    Activité : Chercheur d'emploi
    Secteur : High Tech - Éditeur de logiciels

    Informations forums :
    Inscription : Septembre 2007
    Messages : 7 487
    Par défaut
    Citation Envoyé par Chido42 Voir le message
    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 ?

  5. #5
    Membre régulier
    Inscrit en
    Décembre 2009
    Messages
    10
    Détails du profil
    Informations forums :
    Inscription : Décembre 2009
    Messages : 10
    Par défaut
    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é.

  6. #6
    Modérateur
    Avatar de Obsidian
    Homme Profil pro
    Chercheur d'emploi
    Inscrit en
    Septembre 2007
    Messages
    7 487
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 49
    Localisation : France, Essonne (Île de France)

    Informations professionnelles :
    Activité : Chercheur d'emploi
    Secteur : High Tech - Éditeur de logiciels

    Informations forums :
    Inscription : Septembre 2007
    Messages : 7 487
    Par défaut
    Citation Envoyé par Chido42 Voir le message
    — 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 ?

    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.

Discussions similaires

  1. Machines de Turing, Complexité et "Drapeau Belge"
    Par Ourszor dans le forum Algorithmes et structures de données
    Réponses: 0
    Dernier message: 03/03/2009, 12h10
  2. Réponses: 4
    Dernier message: 30/01/2009, 15h47
  3. Machine de Turing
    Par Anakin8526 dans le forum Général Python
    Réponses: 3
    Dernier message: 10/12/2008, 18h39
  4. Machine de Turing fonction 2n
    Par patrick974 dans le forum Mathématiques
    Réponses: 4
    Dernier message: 11/09/2008, 18h48
  5. Machine de Turing: déplacement
    Par acacia dans le forum Algorithmes et structures de données
    Réponses: 7
    Dernier message: 24/04/2008, 19h43

Partager

Partager
  • Envoyer la discussion sur Viadeo
  • Envoyer la discussion sur Twitter
  • Envoyer la discussion sur Google
  • Envoyer la discussion sur Facebook
  • Envoyer la discussion sur Digg
  • Envoyer la discussion sur Delicious
  • Envoyer la discussion sur MySpace
  • Envoyer la discussion sur Yahoo