Code préfixe/Injection


  • D

    Bonjour,
    J'espère que vous avez passé un bon noël.
    Je refais mes TD de maths discrètes pour préparer l'examen de janvier. Mais je refais exactement la même erreur que lorsque j'étais en TD.
    L'exercice est le suivant:
    On considère deux codes bianaires alphabétiques sur l'alphabet {a,b}.
    Le code de f est défini par f(a)=0, f(b)=10
    Le code g est défini par g(a)=0 et g(b)=01

    1. Calculer f(aab) et f(epsilon). est ce que f est un code préfixe? est ce que la fonction est injective?
    2. même question avec g(aab) et g(bb)

    1)f(aab)=0010
    f(epsilon)=epsilon
    je disais que ce n'étais pas un code préfixe car f(a)=0 et f(b)=10 f(b) ne commence pas par un 0.

    1. g(aab)=0001
      g(bb)=0101
      donc dans ce cas je pensais que c'etait un code préfixe car g(a)=0 et g(b) commence ausi par 0.

    Merci pour votre aide


  • mtschoon

    Bonjour Dut,

    Je vois que tes vacances sont studieuses.

    Ta question n'est pas une question de "Mathématiques générales" mais de "Codage de l'information"...
    Je n'ai aucun cours sur ce sujet !
    Il faut que tu consultes ton cours pour connaître la définition relative au codage préfixe.

    Je regarde ce que dit le web sur ce "codage préfixe"
    Apparemment (?), pour avoir un "codage préfixe" aucun "mot codé" ne doit être préfixe d'aucun autre "mot codé"
    Est-ce-que ton cours dit pareil ?

    Pour f, tu as considéré seulement a et b
    Pour ces deux termes , effectivement, 0 et 10 ne sont pas préfixes l'un de l'autre.
    Mais je suppose que la propriété doit s'appliquer à tous les mots construits avec l'alphabet {a,b} (Vérifie sur ton cours)
    Par exemple
    f(a)=0
    f(aab)=0010
    0 est préfixe de 0010
    La réponse pour f serait donc NON

    Pour savoir si f est injective, il faut savoir si tout "mot codé" a un seul antécédent par f (c'est à dire est l'image d'un seul mot)

    Tout mot codé est composé de "10" et de" 0"
    exemple : 0001000010
    les "10" sont des "b" et les autre "0" des "a"
    Le mot est donc aaabaaab

    f est injective.

    même idée pour g


  • D

    Bonsoir Mtschoon,
    Je préfère travailler je ne me sens tellement pas prêt pour les examens de la rentrée que sacrifier une partie des vacances ne me pose pas de problème.

    Merci beaucoup oui j'ai l'impression que vos explications sont cohérentes avec mon cours.

    Je vous reposerai des questions plus mathématiques, j'ai quelques soucis avec les relations.

    Bonne soirée


  • mtschoon

    C'est tant mieux s'il y a conformité avec ton cours !

    Bon travail et bonne soirée .


Se connecter pour répondre