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 :

Sujet concours entrée ENS, questions prise de tête


Sujet :

Algorithmes et structures de données

  1. #1
    Membre du Club
    Sujet concours entrée ENS, questions prise de tête
    Bonjour,
    je m'amuse à faire le sujet d'info pour le concours d'entrée à l'ENS (voir pièce jointe).
    C'est un sujet très intéressant sur les mots de langages formels et leurs sous-mots. Les questions 11 à 14 proposent une méthode pour détecter si oui ou non, un mot est un sous-mot accepté par une expression rationnelle.
    On utilise les résidus d'un langage L sur un mot u (voir explications avent la q. 11). La question 11 suggère d'utiliser la récursivité pour construire l'expression rationnelle <a>L(e) à partir de l'expression rationnelle L(e) (c'est la q. 14). Or les formules de la question 11 ne sont, en fait, pas des égalités mais des inclusions, ce qui interdit de construire (sous forme d'un arbre binaire) récursivement <a>L(e) à partir de L(e) (L(e) étant elle-même représentée par un arbre binaire). En effet il est nécessaire d'avoir les égalités dans les formules de la question 11.
    Si vous connaissez ce problème, si vous essayez de le faire, je serais ravi de discuter avec quelqu'un qui est intéressé.
    Si quelqu'un sait où trouver un corrigé, dites-le moi, j'aimerais bien avoir la solution à mon problème...
    Merci !

    Virgile le chat.

  2. #2
    Membre habitué
    Pour trouver des sous/sur mots, il faut un lexique, où est le lexique ?
    Savoir pour comprendre et vice versa.

  3. #3
    Membre actif
    Bonjour,
    Si vous connaissez ce problème, si vous essayez de le faire, je serais ravi de discuter avec quelqu'un qui est intéressé.
    c'est marrant j'ai eu ce sujet pendant mes concours (je t'avoue que sur le moment je n'ai pas pu apprécier toute la beauté de ce sujet mais passons)
    En théorie j'ai encore les connaissances pour t'aider d'autant plus qu'il me semble que je l'avais plutôt bien réussi(après tout est relatif avec les ENS)

    Si quelqu'un sait où trouver un corrigé, dites-le moi, j'aimerais bien avoir la solution à mon problème...
    J'ai envoyé un mail à mon ancien prof je te tiens au courant.

    Par contre je suis peut être fatigué mais je n'ai pas réellement compris quel est ton problème : c'est la question 14 que tu cherches à faire ?

    Valentin

    Mon corps d'athlète n'est qu'un splendide écrin pour l'énorme diamant qu'est mon cerveau(pour plus d'informations, voir mon avatar)

    Il ne savaient pas que c'était impossible, alors ils l'ont fait.

###raw>template_hook.ano_emploi###