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 :

Automate


Sujet :

Algorithmes et structures de données

Vue hybride

Message précédent Message précédent   Message suivant Message suivant
  1. #1
    Membre confirmé
    Profil pro
    Inscrit en
    Mai 2005
    Messages
    62
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Mai 2005
    Messages : 62
    Par défaut Automate
    Bonjour,
    J'aurais besoin d'aide concernant la manipulation de chaine de caractère dans un automate déterministe.
    L'automate comprend des état et des transitions entre les états qui ont pour valeur une lettre.
    Mon automate est représenté par une matrice avec les dimensions suivantes :
    [nombre d'états] [26] (pour les 26 lettres de l'alphabet ).
    La matrice est initialisée à -1 et les lettres sont les transitions entre états. Par exemple si matrice[1][3]=2 alors on sait que l'état 2 est accessible depuis l'état 1avec le caractère 'c'.
    L'état initial de l'automate est l'état 0 et plusieurs états pevent être finaux. (j'espère que j'ai été assez clair, c'est compliqué à expliquer ^^).
    J'ai fait une fonction qui vérifie si un mot est disponible dans l'automate mais je dois maintenant faire une fonction qui me renvoie tous les mots de longueur inférieur à n pouvant être constitués avec l'automate. Je pense qu'il faut la faire en récursif mais je ne vois vraiment pas comment.
    Si quelqu'un à une idée elle est la bienvenue !

  2. #2
    Expert confirmé Avatar de Graffito
    Profil pro
    Inscrit en
    Janvier 2006
    Messages
    5 993
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Janvier 2006
    Messages : 5 993
    Par défaut
    Bonjour,

    Pour faciliter l'implémentation, il faut définir un état 0 pour l'état initial et un état F pour l'état final.

    On travaillera sur une liste de chaines de caractères avec comme info associée à chaque mot sa longueur(Length) et l'état atteint au dernier caractère.

    On peut alors créer une procédure qui traite un élément X de la liste pour ajouter à la liste tous les mots possibles de longueur Length(X)+1 :
    Si Length(X)=N, on ne fait pas d'ajout,
    Si Length(X)=N-1, on ajoute si l'état aprés transition est l'état final,
    Sinon, on ajoute si cet état est différent de l'état final.

    Après avoir créé le premier élément avec état initial 0 et longueur 0, il suffit d'appeler cette procedure successivement pour chaque élément rencontré dans la liste, ceci tant que toute la liste n'a pas été traitée.

    La fin de la liste (qui est classée en ordre croissant de longueur) donnera tous les mots de longueur N possibles.

  3. #3
    Rédacteur/Modérateur
    Avatar de Trap D
    Profil pro
    Inscrit en
    Septembre 2003
    Messages
    4 942
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Septembre 2003
    Messages : 4 942
    Par défaut
    Je pense que tu dois pouvoir résoudre ce problème avec une file, ayant comme élément une structure contenant la suite des lettres déjà rencontrées et l'état courant.
    Tu initialises ta file avec l'état initial et 0 lettres lues.
    Ensuite, tant que la file n'est pas vide, tu dépiles un élément, tu crées un nouvel élément copie de l'élément courant, et en fonction de l'état où tu es, tu ajoutes une lettre accessible et l'état obtenu, si c'est un état final tu t'arrètes et tu mémorises le mot, sinon si tu n'as pas atteint la longueur maximale n, tu mets l'élément dans la file.
    "La haine seule fait des choix" - Koan Zen
    "Il ne faut pas être meilleur que les autres, il faut être meilleur que soi." Albert Jacquard
    "Ceux qui savent où ils ont posé leur parapluie ne sont pas alcooliques." - pgibonne.
    Faites du Prolog, ça vous changera les idées !
    Ma page Prolog
    Mes codes sources commentés

    Mon avatar : La Madeleine à la veilleuse de Georges de La Tour

  4. #4
    Rédacteur

    Avatar de Matthieu Brucher
    Profil pro
    Développeur HPC
    Inscrit en
    Juillet 2005
    Messages
    9 810
    Détails du profil
    Informations personnelles :
    Âge : 43
    Localisation : France, Pyrénées Atlantiques (Aquitaine)

    Informations professionnelles :
    Activité : Développeur HPC
    Secteur : Industrie

    Informations forums :
    Inscription : Juillet 2005
    Messages : 9 810
    Par défaut
    Je me rappelle d'un sujet d'examen d'info de Polytechnique où on devait implémenter une automate qui reconnaissait si la chaîne correspondait à l'expression en entrée. C'était un truc tout simple avec gestion des * et des ? pour éviter potentiellement un caractère.

  5. #5
    Expert confirmé

    Inscrit en
    Novembre 2005
    Messages
    5 145
    Détails du profil
    Informations forums :
    Inscription : Novembre 2005
    Messages : 5 145
    Par défaut
    Citation Envoyé par zapatta
    J'ai fait une fonction qui vérifie si un mot est disponible dans l'automate mais je dois maintenant faire une fonction qui me renvoie tous les mots de longueur inférieur à n pouvant être constitués avec l'automate.
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    allwords: proc (size: int, prefix: string, state: state) is
       for c in character loop
          new_state: state = transition(state, c)
          if valid(new_state) then
             if accepting(new_state) then
                print_line prefix+c
             end
             if size > 1 then
                allwords size-1, prefix+c, new_state
             end
          end
       end

  6. #6
    Membre confirmé
    Profil pro
    Inscrit en
    Mai 2005
    Messages
    62
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Mai 2005
    Messages : 62
    Par défaut
    C'est bon g réussi merci à tous !

  7. #7
    Rédacteur/Modérateur
    Avatar de Trap D
    Profil pro
    Inscrit en
    Septembre 2003
    Messages
    4 942
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Septembre 2003
    Messages : 4 942
    Par défaut
    Et quelle solution as-tu prise ?
    "La haine seule fait des choix" - Koan Zen
    "Il ne faut pas être meilleur que les autres, il faut être meilleur que soi." Albert Jacquard
    "Ceux qui savent où ils ont posé leur parapluie ne sont pas alcooliques." - pgibonne.
    Faites du Prolog, ça vous changera les idées !
    Ma page Prolog
    Mes codes sources commentés

    Mon avatar : La Madeleine à la veilleuse de Georges de La Tour

+ Répondre à la discussion
Cette discussion est résolue.

Discussions similaires

  1. Automation Word
    Par afan dans le forum MFC
    Réponses: 8
    Dernier message: 12/11/2003, 14h50
  2. Automation Excel
    Par cgo dans le forum API, COM et SDKs
    Réponses: 4
    Dernier message: 19/03/2003, 15h03
  3. [AUTOMATION WORD]Pilotage Word par Delphi
    Par Sunny dans le forum API, COM et SDKs
    Réponses: 5
    Dernier message: 05/12/2002, 17h09
  4. [VBA-W] [AUTOMATION]Liste Fonctions/Paramètres
    Par Sunny dans le forum VBA Word
    Réponses: 2
    Dernier message: 05/12/2002, 16h35
  5. Accès à une application ouverte (OLE Automation ?)
    Par PascalB dans le forum C++Builder
    Réponses: 6
    Dernier message: 17/06/2002, 14h39

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