Remerciez-le!

Remerciez @Admin pour avoir partagé cet document gratuitement, de la manière la plus simple, en partageant sur les réseaux sociaux.

Problème I : Mots de Lukasiewicz Dans ce problème, les mots considérés sont pri

Problème I : Mots de Lukasiewicz Dans ce problème, les mots considérés sont pris sur l’alphabet {−1, 1}. On appelle mots de Lukasiewicz toute suite ﬁnie u = [u1, u2, . . . , un] à valeurs dans {−1, 1} qui vériﬁe les deux propriétés suivantes : p(u) = n X i=1 ui = −1 et k X i=1 ui ≥0 pour 1 ≤k ≤n −1. — On notera avec un point . la concaténation de deux mots, par exemple, a.b — Par la suite, les mots de Lukasiewicz seront représentés en python par le type ’list’, — On désigne par |u| la taille (longueur) d’un mots u. Quelques propriétés Question 1.1 Donner tous les mots de Lukasiewicz de longueur ≤3. Question 1.2 Prouver qu’il n’existe aucun mot de Lukasiewicz de taille paire. Indication : Utiliser un raisonnement par absurde. Question 1.3 Écrire une fonction estLukasiewicz qui renvoie True si un mot est de Lukasiewicz et puis donner sa complexité. Question 1.4 Montrer que si u et v sont des mots de Lukasiewicz, alors (+1).u.v est un mot de Lukasiewicz. 2 Question 1.5 Réciproquement, montrer que tout mot w de Lukasiewicz de longueur supérieure ou égale à 3 admet une décomposition unique de la forme (+1).u.v, où u et v sont des mots de Lukasiewicz. Indication : Justiﬁer que w = (+1).w0 et considérer u le plus petit préﬁxe strict de w0 vériﬁant p(u) = −1. Question 1.6 Écrire une fonction decompose qui associe ce couple (u, v) à un mot de Lukasiewicz de longueur supérieure ou égale à 3. On ne demande pas de traiter les cas où le mot fourni en entrée ne serait pas de Lukasiewicz. Question 1.7 En exploitant le résultat de la question 1.4, écrire une fonction récursive Luka_rec qui permet de renvoyer une liste de tous les mots de Lukasiewicz de taille n donné. Question 1.8 Justiﬁer pourquoi cette solution récursive imposerait un coût de calcul exponentiel ? Question 1.9 Proposer une autre solution plus eﬃcace que la précédente. Question 1.10 Soit u = [u1, u2, . . . , un] un mot tel que u1 + . . . + un = −1. Il existe un unique entier i ∈[|1, n|] tel que [ui+1, . . . , un, u1, . . . , ui−1, ui] soit un mot de Lukasiewicz. Ce mot est appelé le conjugué de u. ▶Écrire une fonction conjugue_1 qui calcule le conjugué d’un mot u. Question 1.11 Soit u = [u1, u2, . . . , un] un mot tel que u1 + . . . + un = −1 et soit i le plus petit des entiers i ∈[|1, n|] pour lesquels u1 + . . . + ui est minimal, alors le mot [ui+1, . . . , un, u1, . . . , ui−1, ui] est un mot de Lukasiewicz. ▶Écrire une fonction conjugue_2 qui calcule le conjugué d’un mot u en utilisant cette propriété sur l’entier i. Exemple : Soit u = [1, −1, −1, 1, −1], on a u1 + . . . + u5 = −1 i = 1 i = 2 i = 3 i = 4 i = 5 u1 = 1 u1 + u2 = 0 u1 + u2 + u3 = −1 u1 + u2 + u3 + u4 = 0 u1 + u2 + u3 + u4 + u5 = −1 Donc, le plus petit des entiers pour lesquels u1 + . . . + ui est minimal, est i = 3. D’où le conjugué de u est [1, −1, 1, −1, −1] et il est bien un mot de Lukasiewicz. Question 1.12 Comparer la complexité des deux fonctions précédentes conjugue_1 et conjugue_2, en déduisant la meilleure solution. 3 Capsule On appelle capsule d’un mot u tout facteur de u de la forme [+1, −1, −1]. On déﬁnit une fonction ρ dite de décapsulage : ρ(u) =              u, si u ne contient pas de capsule, [u1, . . . , ui−1, ui+2, . . . , un], si [ui, ui+1, ui+2] = [1, −1, −1] est la première capsule de u (1) On admet que la suite (ρn(u))n ∈N est constante au delà d’un certain rang. La valeur limite de cette suite sera notée ρ∗(u). On désigne par ρn(u) = ρ(ρn−1(u)) avec ρ0(u) = u. Question 1.13 Écrire une fonction rho qui calcule ρ(u). Question 1.14 Écrire une fonction rholim qui calcule ρ∗(u). Question 1.15 Montrer que tout mot de Lukasiewicz de longueur ≥3 contient au moins une capsule. Indication : Vous pouvez utiliser un raisonnement par récurrence en exploitant le résultat de la question 1.5, ou bien utiliser un raisonnement par absurde. Question 1.16 Montrer que u est un mot de Lukasiewicz si et seulement si ρ(u) est un mot de Lukasiewicz. Question 1.17 Démontrer enﬁn que u est un mot de Lukasiewicz si et seulement si ρ∗(u) = [−1]. Un peu de théorie du langage Question 1.18 Montrer que le langage L = {(+1)r(−1)r+1, r ∈N} n’est pas ra- tionnel. Rappel : Lemme de l’étoile (pumping lemma) : Si un langage L sur un alphabet Σ (L ⊂Σ∗) est rationnel, alors : — ∃n ∈N∗tel que : ∀u ∈L avec |u| ≥n, il existe une décomposition de u en trois parties u = fgh telle que : (i) : g ̸= ε, (ii) : |fg| ≤n et (iii) : ∀k ≥0, fgkh ∈L Question 1.19 Proposer une grammaire reconnaissant le langage L 4 Problème II : Codage de Huﬀman Le codage de Huﬀman est un algorithme de compression de données sans perte. Il utilise un code à longueur variable pour représenter un symbole de la source (par exemple un caractère dans un ﬁchier). Le principe du codage de Huﬀman repose sur la création d’une structure d’arbre com- posée de noeuds. On recherche tout d’abord le nombre d’occurrences de chaque caractère. Chaque caractère constitue une des feuilles de l’arbre à laquelle on associe un poids égal à son nombre d’occurrences. L’arbre sera créé suivant un principe simple : on associe à chaque fois les deux noeuds de plus faibles poids, pour donner un nouveau noeud dont le poids équivaut à la somme des poids de ses ﬁls. On réitère ce processus jusqu’à n’en avoir plus qu’un seul noeud( la racine). On associe ensuite par exemple le code 1 à chaque embranchement partant vers la gauche et le code 0 vers la droite. Pour obtenir le code binaire de chaque caractère, on remonte l’arbre à partir de la racine jusqu’aux feuilles en rajoutant à chaque fois au code un 0 ou un 1 selon la branche suivie. Exemple : Figure 1 – Construction d’un code de Huﬀman Question 2.1 Répondre aux questions suivantes : 1. Réaliser l’arbre de Huﬀman à partir de la table des fréquences suivante : a b c d e 5 4 2 8 1 5 2. Donner le code du mot ’bec’ : 3. Décoder la chaîne ’000010010’ : Dans ce qui suit, nous nous intéressons à l’implémentation d’un ensemble de fonc- tions qui permettent la manipulation de ce codage. Question 2.2 Réaliser une fonction fréquence(mot) qui retourne le nombre d’oc- currences de chaque caractère constituant le mot. Exemple : Pour le mot ’abracadabra’, le résultat à retourner est : TabFreq = [[′a′, 5], [′b′, 2], [′r′, 2], [′c′, 1], [′d′, 1]]. Question 2.3 Soit L une liste dont les éléments ont la forme suivante [nb, list]. On souhaite trier en ordre décroissant la liste L suivant la clé nb. Réaliser une fonction trierL(L) qui permet d’eﬀectuer ce genre de tri et puis donner sa complexité. Exemple : soit L = [[5, [′c′,′ 10′], [′d′,′ 11′]], [3, [′a′,′ 10′]], [4, []]]. La fonction trierL renvoie la liste [[5, [′c′,′ 10′], [′d′,′ 11′]], [4, []], [3, [′a′,′ 10′]]] Question 2.4 On souhaite réaliser une fonction ListeCodes(TabFreq) qui retourne un tableau contenant le code Huﬀman associé à chaque caractère. Exemple : Pour le mot ’abracadabra’, le résultat à retourner est : [[′a′,′ 1′], [′b′,′ 01′], [′r′,′ 000′], [′c′,′ 0010′], [′d′,′ 0011′]] Pour implémenter cette fonction, on procède de la manière suivante : — Au début on initialise la liste à partir du tableau des fréquences comme suit : L = [[5, [′a′,′′ ]], [2, [′b′,′′ ]], [2, [′r′,′′ ]], [1, [′c′,′′ ]], [1, [′d′,′′ ]] — Après, on trie cette liste par ordre décroissant selon le poids (dans cet exemple la liste L est déjà triée par coïncidence dès l’initialisation). 6 Question 2.4.1 Écrire une fonction initialiseL(TabFreq) qui permet d’initialiser la liste L comme décrit précédemment. — Ensuite, on retire les deux petits éléments de la liste L. C’est-à-dire [1, [′d′,′′ ]] et [1, [′c′,′′ ]], On ajoutera ′1′ comme préﬁxe à l’élément le plus petit et ′0′ comme préﬁxe au deuxième élément plus petit c-à-d [1, [′d′,′ 1′]] et [1, [′c′,′ 0′]] et on ajoutera à la liste L l’élément [2, [′c′,′ 0′], [′d′,′ 1′]] puis on triera à nouveau la uploads/S4/ epreuveif-copie.pdf