Mines Informatique MP 2006

Thème de l'épreuve Circuit logique. Arbres et codage de Huffman.
Principaux outils utilisés circuits logiques, propriétés des arbres

Corrigé

(c'est payant, sauf le début): - - - - - - - - - - - - - - - - - - - - - - - - -

Extrait gratuit du corrigé

(télécharger le PDF)
           

Énoncé complet

(télécharger le PDF)
                             

Rapport du jury

(télécharger le PDF)
        

Énoncé obtenu par reconnaissance optique des caractères


ÉCOLE NATIONALE DES PONTS ET CHAUSSÉES, ÉCOLES NATIONALES SUPÉRIEURES DE L'AÉRONAUTIQUE ET DE L'ESPACE, DE TECHNIQUES AVANCÉES, DES TÉLÉCOMMUNICATIONS, DES MINES DE PARIS, DES MINES DE SAINT--ÉTIENNE, DES MINES DE NANCY, DES TÉLÉCOMMUNICATIONS DE BRETAGNE, ÉCOLE POLYTECHNIQUE (FILIÈRE TSI) CONCOURS D'ADMISSION 2006 ÉPREUVE D'INFORMATIQUE Filière MP (Durée de l'épreuve : 3 heures) L'usage de calculettes est autorisé. L'utilisation d'un ordinateur est interdite. Sujet mis à disposition des concours : ENSAE (Statistique), EN STIM, TPE--EIVP, Cycle international Les candidats sont priés de mentionner de façon apparente sur la première page de la copie : INFORMATIQUE - MP L 'énoncé de cette épreuve comporte 1 0 pages. RECOMMANDATIONS AUX CANDIDATS - Si, au cours de l'épreuve, un candidat repère ce qui lui semble être une erreur d'énoncé, il le signale sur sa copie et poursuit sa composition en expliquant les raisons des initiatives qu'il est amené à prendre. 0 Tout résultat fourni dans l'énoncé peut être utilisé pour les questions ultérieures même s'il n'a pas été démontré. - 0 Il ne faut pas hésiter à formuler les commentaires qui semblent pertinents même lorsque l'énoncé ne le demande pas explicitement. COMPOSITION DE L'ÉPREUVE L'épreuve comporte deux parties indépendantes : 0 un problème de logique, pages 2 et 3 0 un problème d'algorithmique et programmation, pages 4 à 10 1. Problème de logique On considère l'algèbre de Boole, c'est-à-dire l'ensemble 3 = {O, 1} muni des opérations booléennes v et A définies par les deux tables suivantes : Pourxe OE,ondéfinit ; par: ; = ] six=0, ; =Osix= l. Les portes logiques élémentaires sont la porte OU à deux entrées, la porte ET à deux entrées et la porte NON à une entrée ; elles sont décrites dans les figures ci-dessous. x x OU xVy y ET xAV Y Une fonction logique f de n variables est une application de CB " dans $. La synthèse d'une telle fonction consiste à réaliser un circuit logique ayant 11 entrées pouvant recevoir des valeurs booléennes xl, x2, ..., x,, et une sortie r vérifiant r = f(x1, x2, . .., x"). Un circuit pourra utiliser des noeuds dits noeuds x x duplicateurs qui permettent de dupliquer une valeur entrante en deux valeurs sortantes égales à la valeur d'entrée selon le schéma représenté ci--contre. x Par exemple, le circuit dessiné ci--contre réalise la synthèse de la fonction constante définie sur 3 par x x l---> 0. Dans un tel circuit, les signaux se propagent en suivant le sens des flèches ; le signal initial venant de ET x est d'abord dupliqué par un noeud duplicateur puis les signaux sont traités par les deux portes comme NON l'indique le schéma. Début de l'énoncé du problème de logique Cl 1-- Synthétiser la fonction constante définie sur 23 par x l---->l en utilisant deux portes logiques élémentaires et un noeud duplicateur. Soit n un entier strictement positif. Un concentrateur « 1 parmi 2" », noté M... est un circuit logique comportant : 0 2" entrées booléennes notées d,;, 0 S i < 2", dites entrées de données, 0 71 entrées booléennes notées sj, 0 S j < n, dites entrées de sélection, 0 une sortie r. Son fonctionnement est décrit par la règle suivante : si les entrées so, s;, ..., s,, -] valent respectivement x0, xl, ..., x,,_1, la sortie r vaut alors dk, où k ---- 2250 .La sortie d un tel circuit est donc égale à l'entrée de données dont le numéro est indiqué en binaire par les entrées de sélection. Ces circuits interviennent par exemple dans les mémoires des ordinateurs, en téléphonie numérique, en cryptographie. .. Un concentrateur M,, est représenté ci--contre. Dans les questions [] 2 et Cl 3, on se place dans le cas n = l et on étudie un concentrateur M,. Cl 2 -- Exprimer l'équation logique du concentrateur M,, c'est--à--dire expliciter r en fonction de do, d, et S,, au moyen des opérations booléennes. [] 3 -- Faire la synthèse de l'équation logique obtenue dans la question D 2 au moyen de portes logiques élémentaires et, si nécessaire, de noeuds duplicateurs, obtenant ainsi un circuit logique qui réalise un concentrateur M,. On dessinera le circuit en plaçant les entrées à gauche et la sortie à droite. On suppose dans toutes les questions suivantes qu'on dispose des constantes 0 et 1 ; autrement dit, certaines entrées d'un circuit logique, dites fixées, peuvent avoir une valeur constante égale à 0 ou l. Les variables booléennes x,, x2, ._.., x,, d'une fonction flx,, x2, ..., x,,) synthétisée par un circuit logique correspondent aux entrées non fixées de ce circuit. D 4--On s'intéresse à la fonction logique des variables booléennes x et y synthétisée par le dispositif représenté ci-contre. Donner la table de vérité de cette fonction et indiquer de quelle fonction classique il s'agit. [! 5 --Montrer qu'on peut synthétiser la fonction logique de la question précédente en utilisant un concentrateur M,, une porte logique élémentaire et un noeud duplicateur. [| 6 --- Montrer qu'on peut réaliser la fonction logique définie sur 32 par (x, y) i--->x v y à l'aide d'un concentrateur M2. Peut-on réaliser cette fonction avec un seul concentrateur M, en n'ajoutant aucune porte ? Cl 7 -- Montrer qu'on peut réaliser la fonction logique définie sur OEf' par (x, y, z) l--> (x v y) /\ 2 avec un concentrateur M3. Cl 8 --- Montrer que la synthèse d'une fonction logique quelconque f de n variables booléennes peut être réalisée au moyen d'un concentrateur M,,. Dans les deux questions suivantes, on s'intéresse à la construction d'un concentrateur M,, (n 2 2) effectuée en assemblant deux concentrateurs M,, -,, un concentrateur M, et des noeuds duplicateurs. D 9 ---- Expliquer, dessin à l'appui, comment on peut réaliser ce montage. Justifier la réponse. On notera, d'une part, M? le concentrateur M, et, d'autre part, M},_, et M%_, les deux concentrateurs M,,_1 ;les noms des entrées et des sorties de ces concentrateurs pourront s'appuyer sur cette notation (par exemple, pour M},_, : dÊ, , ci,1 , ..., sË, , ..., rl). On mettra en évidence les correspondances entre les entrées et les sorties des différents concentrateurs. Pour 11 Z 1, on note et,, le nombre de portes logiques élémentaires qui composent le circuit M... On suppose que le concentrateur M, est construit en utilisant le circuit obtenu dans la question Cl 3 et que le concentrateur M,, est construit selon le montage ci--dessus. D 10 -- Donner une formule exprimant cc,, en fonction de Ot,,- ,. En déduire une expression de 0t,, en fonction de n. FIN DU PROBLÈME DE LOGIQUE 2. Problème d'algorithmique et programmation L'ensemble du problème est consacré à l'algorithme de Huffman qui permet de coder un texte caractère par caractère à l'aide d'une chaîne binaire en minimisant la longueur totale de la chaîne obtenue ; cet algorithme permet de faire de la compression de données. Les parties 1 et 2 du problème sont des parties préparatoires, le codage d'un texte sera abordé dans la troisième partie. Préliminaire concernant la programmation : il faudra écrire des fonctions ou des procédures à l'aide d'un langage de programmation qui pourra être soit Caml, soit Pascal, tout autre langage étant exclu. Indiquer en début de problème le langage de programmation choisi ; il est interdit de modifier ce choix au cours de l'épreuve. Certaines questions du problème sont formulées différemment selon le langage de programmation ; cela est indiqué chaque fois que cela est nécessaire. Par ailleurs, pour écrire une fonction ou une procédure en langage de programmation, le candidat pourra définir des fonctions ou des procédures auxiliaires qu'il explicitera ou faire appel à d'autres fonctions ou procédures définies dans les questions précédentes. Dans l'énoncé du problème, un même identificateur écrit dans deux polices de caractères différentes désigne la même entité, mais du point de vue mathématique pour la police écrite en italique (par exemple : nb_arbres) et du point de vue informatique pour celle écrite en romain (par exemple : nb_arbres). Pour écrire une valeur de type caractère, on représente celle-ci entre apostrophes (par exemple, 'a' pour le caractère a). Dans tout le problème, on utilise des arbres binaires. Pour un arbre, les termes de noeud et de sommet sont synonymes ; c'est le terme de noeud qui est retenu dans ce problème. Un noeud qui n'a pas de fils est appelé feuille alors qu'un noeud qui a au moins un fils est appelé un noeud interne. Chaque noeud 71 des arbres binaires de ce problème contient, outre les indications concernant ses éventuels fils gauche et droit (voir plus bas), un caractère appelé lettre du noeud et noté lettre(n) et un entier strictement positif appelé poids du noeud et noté poids(n). Ces arbres binaires sont appelés H_arbres. Une forêt est dans ce sujet une collection de H_arbres. Une forêt est représentée en mémoire par : ° le nombre de H_arbres de la forêt, noté nb__arbres ; ° le nombre total de noeuds, noté nb__noeuds ; 0 un tableau (ou vecteur) de noeuds appelé table ; dans tout le problème, ce tableau est supposé suffisamment grand pour contenir les noeuds de tous les H--arbres de la forêt considérée ; les noeuds sont rangés dans le tableau entre les indices O et nb_næuds --- l ; ATTENTION: les noeuds qui sont les racines des H_arbres de la forêt se trouvent nécessairement au début du tableau table, c'est--à-dire entre les indices 0 et nb_arbres -- l. Pour un noeud donné, les fils gauche et droit sont indiqués par leurs indices dans le tableau table des noeuds ; lorsqu'un fils gauche ou droit n'existe pas, cela est indiqué par une valeur d'indice égale à ---1. Le fils gauche d'un noeud n sera noté fg(n) et le fils droit sera noté fd(n). Exemple introductif (notée F_ex) : a Pour la forêt F_ex, on a : nb_arbres = 3, nb_noeuds = 7 ; plusieurs tables peuvent correspondre à F_ex, une possibilité est : -fl-----fl -...flflflfl ...-fl ... ---u------- Dans cette table, on voit que le noeud d'indice 3 contient la lettre 'e' et le poids 9, que son fils gauche se trouve à l'indice 5 de la table et qu'il n'a pas de fils droit. table : Indications pour la programmation Caml : On définit les identificateurs et les types suivants type Noeud : { lettre : char; poids : int; fg : int; fd : int; };; ' let noeud_vide : {lettre = '\000'; poids = O; fg = --l; fd = --l};; type Foret : { mutable nb_arbres : int; mutable nb_noeuds : int; table : Noeud vect; };; let MAX = 100;; ' \ O 0 0 ' représente le caractère de valeur nulle (caractère qui est différent du caractère ' 0 ' ). La valeur MAX donne un majorant du nombre total de noeuds des forêts considérées ; c'est la dimension donnée au champ table d'une valeur de type Foret. Les types Noeud et Foret sont des types pour des enregistrements (un tel type est aussi appelé type produit). Un enregistrement contient des champs (aussi appelés composantes ou étiquettes). Une valeur de type Noeud contient les champs lettre, poids, fg et fd ; une valeur de type Foret contient les champs nb_arbres, nb_noeuds et table. La forêt F_ex de l'exemple introduCtif peut être définie par : let F_ex : let table_F_ex : make_vect MAX noeud_vide in table_F_ex.(0) <-- {lettre : 'g'; poids : 10; fg : --1; fd : 6}; table_F_ex.(l) <-- {lettre : 'a'; poids : 20; fg : 4; fd : 3}; table_F_ex.(2) <-- {lettre : 'b'; poids : 13; fg : --1; fd : --1}; table_F_ex.(3) <-- {lettre : 'e'; poids : 9; fg : 5; fd : --1}; table_F_ex.(4) <-- {lettre : 'f'; poids : 15; fg : --1; fd : --1}; table_F_ex.(5) <-- {lettre : 'c'; poids : 12; fg : -1; fd : --1}; table_F_ex.(6) <-- {lettre : 'd'- poids : 8- fg : --1; fd : --1}; = 3 table : table_F_ex};; Il \] {nb_arbres nb_noeuds \. Un champ d'un enregistrement peut être ou non mutable ; si un champ est mutable, sa valeur peut être modifiée ; pour qu'un champ d'un enregistrement soit mutable, il faut l'indiquer au moment de la déclaration du type enregistrement; c'est ce qui est fait ici pour les champs nb_arbres et nb_noeuds d'un enregistrement de type Foret. On peut accéder à la valeur d'un champ quelconque de type enregistrement en faisant suivre le nom de cette valeur d'un point puis du nom du champ considéré; par exemple, pour la forêt définie ci--dessus, F_ex.nb_arbres vaut 3 et F__ex. table. (0) .poids vaut 10. ATTENTION: la modification d'un champ mutable se fait à l'aide du signe <-- ; on pourra par exemple écrire: F_ex.nb_arbres <--- 2; pour indiquer que cette forêt contient dorénavant deux H_arbres. Fin des indications pour Caml Pascal : Dans tout le problème, on supposera qu'on écrit les différentes fonctions ou procédures dans un fichier contenant les définitions suivantes : const MAX : 100; type Noeud : RECORD lettre : Char; poids : Integer; fg : Integer; fd : Integer; end; type T_Noeuds = array[0..MAX -- 1] of Noeud; type Foret : RECORD nb_arbres : Integer; nb_noeuds : Integer; table : T_Noeuds; end; Les types Noeud et Foret sont des types pour des enregistrements (RECORD). Un enregistrement contient des champs (quelquefois aussi appelés des membres); par exemple, une variable de type Noeud contient les champs lettre, poids, fg et fd ; on peut accéder à un champ d'une variable de type enregistrement en faisant suivre le nom de cette variable d'un point puis du nom du champ considéré, comme dans la définition de F_ex ci--dessous. Les variables de type enregistrement se manipulent comme toute autre variable : on peut définir des variables de type enregistrement, on peut affecter à une variable de type enregistrement la valeur d'une autre variable du même type, les variables de type enregistrement peuvent servir de paramètres à des fonctions ou procédures et peuvent être renvoyées par des fonctions ; en revanche, il est interdit de les comparer directement. Ainsi, la forêt F_ex de l'exemple introductif est définie par : F_ex.nb_arbres := 3; F_ex.nb_noeuds := 7; F_ex.table[0l.lettre := 'g'; F_ex.table[0].poids : 10; F_ex.table[0].fg := --1; F_ex.table[0].fd := 6; F_ex.table[ll.lettre := 'a'; F_ex.table[l].poids : 20; F_ex.tab1e[ll.fg := 4; F_ex.table[1l.fd := 3; F_ex.table[2].lettre := 'b'; F_ex.table[2].poids : 13; F_ex.table[2].fg := --1; F_ex.table[2].fd := --1; F_ex.table[3].lettre := 'e'; F_ex.table[3].poids = 9; F_ex.table[3l.fg := 5; F_ex.table[3l.fd .: --1; F_ex.table[4].lettre := 'f'; F_ex.table[4].poids = 15; F_ex.table[4].fg := --1; F_ex.table[4].fd := --1; F_ex.table[5].lettre := 'c'; F_ex.table[5].poids : 12; F_ex.table[5].fg := --1; F_ex.table[5].fd := --1; F_ex.table[6l.lettre := 'd'; F_ex.table[6l.poids = 8; F_ex.table[6l.fg := --1; F_ex.table[6l.fd := --1; Fin des indications pour Pascal Première partie : fonctions de base pour l'algorithme de Huffman [] ll -- On considère une forêt contenant nb_noeuds noeuds et un entier k vérifiant 1 S k 5 nb_næuds ; il s'agit d'écrire une fonction déterminant l'indice du noeud dont le poids est le plus petit parmi les k premiers noeuds de la table de la forêt, c'est--à-dire parmi les noeuds qui se trouvent entre les indices 0 et k-- l de cette table. S'il y a plusieurs noeuds de plus petit poids dans l'intervalle indiqué, la fonction renverra le plus petit indice de ceux-ci. Caml : Écrire en Caml une fonction indice_du_min telle que si F est une valeur de type Foret et k une valeur entière strictement positive ne dépassant pas F . nb_noeuds, alors indice_du_min F k renvoie l'indice recherché. ' Pascal : Écrire en Pascal une fonction indice_du_min telle que si F est une variable de type Foret et k une variable de type Integer strictement positive et ne dépassant pas F.nb_noeuds, alors indice_du_min(F, k) renvoie l'indice recherché. [| 12 -- On considère une forêt F constitué d'au moins deux H_arbres. Il s'agit de faire en sorte que, dans la table de F, les deux racines de plus petits poids soient les deux dernières racines dans la partie de la table consacrée aux racines de la forêt. Autrement dit, il s'agit d'examiner les racines de F (c'est--à--dire les noeuds qui se trouvent entre les indices 0 et nb_arbres -- l de la table) pour mettre, par des échanges, les deux racines de plus petits poids aux indices nb_arbres -- 2 et nb_arbres -- l ; plus précisément, on mettra la racine de plus petit poids à l'indice nb_arbres -- l et la racine « d'avant--dernier » plus petit poids à l'indice nb_arbres -- 2. Par exemple, après ce traitement, la table décrivant F_ex devient : Indice du noeud ..." "......" fable = "......" ... ... S'il y a des égalités entre les poids qui conduisent à plusieurs couples possibles de racines de plus petits poids, on choisira alors les deux racines de plus petits indices. On utilisera la fonction définie dans la question D 11. Caml : Écrire en Caml une fonction deux_plus_petits telle que si F est une valeur de type Foret vérifiant F.nb_arbres Z 2, alors deux_plus_petits F transforme le champ table de F de façon à obtenir l'ordre cherché. Pascal : Écrire en Pascal une procédure deux_plus_petits telle que si F est une variable de type Foret vérifiant F . nb_arbres _>_ 2, alors deux_plus_petits (F) transforme le champ table de F de façon à obtenir l'ordre cherché. D 13 -- On considère une forêt F possédant au moins deux H_arbres. On définit une transformation de F nommée assemblage de F. Soient rl et r2 deux racines de plus petits poids ; on suppose que le poids de rl est inférieur ou égal à celui de Q. L'assemblage de F consiste à ajouter à F un noeud dont : o le poids est la somme des poids des noeuds r; et r2 ; o le fils gauche est rl ; ° le fils droit est r2. Le noeud ajouté est donc la racine d'un H_arbre de la forêt obtenue par l'assemblage et le nombre total de H_arbres de la forêt a diminué de l. La lettre contenue par ce nouveau noeud n'a pas d'importance et n'est pas spécifiée. On ne cherche pas à ce que, après assemblage, les racines des H_arbres respectent l'ordre de la question D 12. Si on applique cette transformation à la forêt F_ex, celle-ci devient la forêt ci--dessous, dans laquelle on n'a pas précisé de valeur pour la lettre du noeud ajouté : Pour cette forêt, nb_arbres = 2, nb_noeuds = 8 et la table peut être : ......" _...EEE ......" ... ... Caml: Écrire en Caml une fonction assemblage telle que, si F est une valeur de type Foret vérifiant F.nb_arbres 2 2, alors as semblage F transforme F selon les indications fournies ci-- dessus. On utilisera la fonction deux_plus_petits définie dans la question précédente. table : Pascal : Écrire en Pascal une procédure assemblage telle que, si F est une variable de type Foret vérifiant F . nb_arbres 2 2, alors assemblage (F) transforme F selon les indications fournies ci-- dessus. On utilisera la fonction deux_plus_petits définie dans la question précédente. Deuxième partie : propriétés pour l'algorithme de Huffman Remarque: dans les illustrations de cette partie, lorsqu'un champ n'est pas précisé dans un noeud, cela signifie que sa valeur n'intervient pas. La hauteur d'un noeud d'un arbre est définie de la façon suivante : 0 la hauteur de la racine vaut 0 ; 0 la hauteur d'un noeud autre que la racine vaut un de plus que la hauteur de son père. La hauteur d'un noeud n est notée h(n). On dit dans un arbre qu'un noeud n est de hauteur maximum s'il n'existe pas de noeud de hauteur strictement plus grande que h(n) dans cet arbre ; un noeud de hauteur maximum est nécessairement une feuille. Deux feuilles d'un arbre sont dites soeurs si elles ont le même noeud pour père. Étant donné un H_arbre A, on appelle évaluation de A la quantité : e(A) = 2 h(fl.poids(f) . fe{feuilles de A} Pour le H_arbre A_ex ci-dessous, on a : e(A_ex) = 1 >< 10 + 3 >< 8 + 3 >< 15 = 79. On rappelle que les poids des noeuds sont des entiers strictement positifs. On dit que deux H_arbres ont mêmes feuilles s'ils ont le même nombre de feuilles et que les contenus des feuilles de l'un sont les mêmes que les contenus des feuilles de l'autre. On dira par exemple que les deux H_arbres A_ex et A '_ex ci--dessous ont mêmes feuilles. Le H_arbre A_ex ' Le H_arbre A '_ax On dit qu'un H_arbre A est optimal s'il n'existe pas d'autre H_arbre ayant les mêmes feuilles et ayant une évaluation strictement inférieure à celle de A. D 14 --- Montrer que, si un H_arbre A est optimal, alors tout noeud interne de A admet deux fils. Après avoir montré ce résultat, transformer le H_arbre A_ex en un H_arbre B_ex de mêmes feuilles que A_ex et d'évaluation inférieure en s'appuyant sur l'argument de la preuve ; on indiquera pour cet exemple le gain d'évaluation obtenu. D 15 -- Soient fl et f2 deux feuilles d'un H_arbre A optimal vérifiant la relation 110EUR) > h(f2) ; montrer qu'alors on a poids(fi) S poidsfi). Après avoir montré ce résultat, transformer le H_arbre B_ex obtenu à la question D 14 en un H_arbre C_ex de mêmes feuilles et d'évaluation inférieure à celle de B_ex en s'appuyant sur l'argument de la preuve ; on indiquera le gain d'évaluation obtenu. D 16 -- On considère un H_arbre A et deux feuilles fl et fi_ de A de plus petits poids. Montrer qu'il existe un H_arbre optimal de mêmes feuilles que A dans lequel fl et 13 sont de hauteur maximum. 13 17 ---- On considère un H_arbre A et deux feuilles fl et f; de A de plus petits poids. Montrer qu'il existe un H_arbre optimal de mêmes feuilles que A dans lequel fl et f; sont soeurs. On considère un H_arbre A et deux feuilles fl et f2 qui sont soeurs dans A ; on note pl et 192 les poids respectifs de ces feuilles. On note 71 le père (commun) de f1 et fz et on considère la transformation suivante : . poids(n) devient égal à pl + p2 ; 0 on supprime fl et f2 ; n devient donc une feuille. Le champ lettre(n) n'a pas d'importance et n'est donc pas spécifié. On note B le H_arbre ainsi obtenu. On dit qu'on a obtenu B en simplifiant A par coupe de fl et f2. 13 18 ---- Établir une relation entre e(A), e(B), pl et m. D 19 -- On considère maintenant un H_arbre A et deux feuilles f1 et f2 qui sont soeurs dans A et de plus petits poids. On simplifie A par coupe de fl et f2 et on obtient ainsi un H_arbre B. Montrer que A est optimal si et seulement si B est optimal. Troisième partie : l'algorithme de Huffman On appelle chaîne binaire une suite composée de 0 et de 1. On considère dans toute cette partie un texte T écrit avec un alphabet Z possédant au moins deux caractères. On souhaite coder ce texte avec une chaîne binaire. Pour cela, on décide d'associer une chaîne binaire à chaque caractère de l'alphabet Z ; la chaîne associée à un caractère est appelée mot de code ; l'ensemble des mots de code est le codage de l'alphabet. On peut alors coder le texte caractère par caractère en mettant bout à bout successivement les mots de code de tous les caractères de T ; on obtient alors le texte codé qui sera noté C(T). L'objectif est de choisir les mots de code pour que le décodage du texte soit possible et que la chaîne binaire C(T) soit la plus courte possible. [] 20 --- On considère l'alphabet Z_ex = {'a', 'b', 'c', 'd', 'e', 'f'}. Un codage de Z_ex est indiqué dans le tableau ci--contre. On suppose que le texte codé C(T) est 1000011011 ; déterminer le texte T. On dit qu'un mot de code u est préfixe d'un autre mot de code v si la chaîne v commence par u; par exemple, u = 01 est préfixe de v = 0110. On dit que le codage d'un alphabet est préfixe si aucun mot de code n'est préfixe d'un autre mot de code. Cl 21 -- Indiquer si le codage de l'alphabet Z_ex donné en exemple dans la question D 20 est ou non préfixe. Dire pourquoi il est utile que le codage de l'alphabet soit préfixe. On considérera par la suite un texte T __ex écrit avec l'alphabet Z_ex; les nombres d'occurrences des caractères de Z_ex dans T __ex sont donnés par le tableau ci--contre. On représente un codage préfixe de l'alphabet Z par un H_arbre dont les feuilles contiennent les caractères de l'alphabet comme champ lettre et le nombre d'occurrences de ce caractère dans le texte T comme champ poids. Les champs lettre et poids des noeuds internes n'ont pas d'importance. Ce H_arbre est construit de sorte que le mot de code d'un caractère 6 corresponde au chemin de la racine du H_arbre à la feuille contenant c. Plus précisément, pour retrouver un caractère de Z connaissant son mot de code, on part de la racine du H_arbre ; on lit le mot de code et, au fur et à mesure, on descend dans le H_arbre ; lorsqu'on rencontre un 0, on descend à gauche, lorsqu'on rencontre un 1, on descend à droite. Le H_arbre associé au codage de Z_ex indiqué dans la question [| 20 est représenté ci-contre. Par exemple, pour aller de la racine au noeud contenant la lettre 'e' de mot de code 011, on descend une fois à gauche puis deux fois à droite. Cl 22 -- Indiquer une relation entre l'évaluation du H_arbre représentant un codage préfixe de l'alphabet et la longueur du texte codé C(T) si T est codé en utilisant ce codage préfixe. On appelle codage optimal de Z pour T un codage préfixe de 2 minimisant la longueur de C(T). Pour chercher un codage optimal, on cherche un H_arbre d'évaluation minimum et dont les feuilles correspondent aux caractères de l'alphabet 27 munis de leurs nombres d'occurrences. Pour cela, on utilise l'algorithme de Huffman. Cet algorithme est initialisé avec une forêt F de H_arbres tous réduits à un noeud et contenant chacun, comme lettre, un caractère de l'alphabet Z et, comme poids, le nombre d'occurrences dans T de ce caractère. Tous les caractères de 2 figurent une fois et une seule parmi ces noeuds. Le nombre de noeuds de cette forêt initiale F est donc égal au nombre de H_arbres et encore égal au nombre de caractères dans 2. On applique ensuite à F la boucle suivante : tant que F possède au moins deux H_arbres, faire assemblage(F) ce qui termine l'algorithme de Huffman. [| 23 --Prouver que, lorsque l'algorithme décrit ci-dessus est terminé, l'unique H_arbre de la forêt correspond à un codage optimal de Z pour T. E] 24 -- Les nombres d'occurrences des caractères de l'alphabet Z_ex dans le texte T _ex étant ceux donnés entre les questions C] 21 et D 22, déterminer, en utilisant l'algorithme de Huffman, un codage optimal de Z_ex pour T __ex. On dessinera le H_arbre obtenu par l'algorithme et on exploitera ce H_arbre pour donner explicitement les mots de code des caractères de Z_ex. FIN D U PROBLÈME D 'AL GORI T HM] Q UE ET PROGRAMMA TION

Extrait du corrigé obtenu par reconnaissance optique des caractères


 Mines Informatique MP 2006 -- Corrigé Ce corrigé est proposé par Sattisvar Tandabany (ENS Lyon) ; il a été relu par Samuel Mimram (ENS Lyon) et Jean-Baptiste Rouquier (ENS Lyon). Cette épreuve comporte deux parties hétérogènes en longueur et en difficulté. · La première est constituée d'un problème de logique faisant intervenir des circuits. Il ne présente aucune difficulté majeure. On y démontre un résultat fort qui est la possibilité de simuler toute fonction booléenne à n variables par un circuit. Les circuits classiques pour démontrer ce résultat sont construits récursivement, ce sont des « multiplexeurs ». · La seconde traite de l'algorithme de Huffman, qui permet de compresser des données. Ce problème est plus long que le premier et nécessite souvent de poser le crayon pour bien réfléchir. L'enchaînement des questions aide beaucoup à la résolution. Il comporte plusieurs parties de natures différentes. Une partie réservée à la programmation manipule des arbres. L'implémentation utilisée pour les stocker n'est pas celle habituelle, mais elle a l'avantage, une fois comprise, de simplifier l'écriture des programmes demandés. Une partie, plus difficile, démontre des propriétés sur les arbres. Enfin, une dernière partie rassemble les résultats des questions précédentes pour prouver l'algorithme de Huffman et l'essayer sur un exemple. L'épreuve est assez classique. Le premier problème constitue un bon exercice pour la manipulation des portes logiques, le multiplexeur étant un circuit qu'il faut avoir vu au moins une fois. Le codage de Huffman est aussi un standard. L'étude faite ici stocke les arbres d'une manière originale qui permet de mener sur eux une étude théorique, tout en demandant de programmer sur des tableaux. Cette épreuve est idéale pour couvrir en une fois plusieurs notions du programme. Indications Problème 1 1 S'inspirer du circuit de l'énoncé pour la fonction constante définie sur B par x 7 0. 2 Écrire la table de vérité de la fonction puis essayer de la formuler en français en distinguant selon les valeurs de r. 5 Faire la synthèse de l'équation logique de la fonction et essayer de reconnaître au mieux l'équation logique de M1 . 6 Pour réaliser la fonction logique avec seulement M1 , il faut chercher des constantes dans la table de vérité. S'inspirer du circuit donné par l'énoncé à la question 4. 8 Fixer chacun des di à une constante. Pour un i donné la constante choisie aura certainement un lien avec la fonction. 9 Étudier deux cas suivant la valeur du bit sn-1 . 10 Introduire n = n + 4. Problème 2 11 Programmer une fonction récursive. Le cas d'arrêt sera k = 1. 12 Penser à utiliser une variable auxiliaire pour l'échange de deux éléments du tableau. Programmer une fonction auxiliaire pour faire l'échange. 14 Prouver la contraposée. 15 Prouver la contraposée et calculer la différence e(B) - e(A). 16 Transformer un arbre optimal quelconque ayant les mêmes feuilles que A de façon à ce qu'il respecte les contraintes de l'énoncé. 17 Partir d'un arbre optimal vérifiant les propriétés de la question précédente et échanger des feuilles. 19 Montrer par l'absurde que si A est optimal alors B l'est, puis montrer que si A n'est pas optimal alors B ne l'est pas non plus en exhibant un arbre d'évaluation plus petite que B, construit à partir d'un arbre d'évaluation plus petite que A. Se servir des deux questions précédentes à bon escient. 20 Parcourir le code de gauche à droite et découvrir la première lettre. 22 Faire un parallèle entre la hauteur d'un noeud et la longueur de son mot de code. 23 Faire des coupes successives de l'arbre final en utilisant la question 19. 1. Problème de logique 1 Le circuit demandé ici doit modéliser la fonction constante définie sur B par x 7 1, qui n'est autre que la négation de la fonction constante définie sur B par x 7 0 donnée en exemple dans l'énoncé. Les lois de De Morgan donnent x x = x x, on obtient le circuit suivant : x OU NON 2 On étudie le concentrateur M1 . Il y a deux valeurs possibles pour l'entrée s0 , l'équation logique peut donc être écrite sous la forme d'une disjonction. Si s0 = 1 alors r = d1 , sinon (c'est-à-dire si s0 = 0) r = d0 . On en déduit l'équation suivante pour r : r = (s0 d1 ) (s0 d0 ) Les circuits Mn sont aussi appelés multiplexeurs ou sélecteurs. 3 De l'équation obtenue à la question précédente, on déduit le circuit logique : d0 d1 ET OU s0 ET NON 4 D'après la définition de M2 , la table de vérité de la fonction r = f (x, y) se lit directement sur les entrées di . D'où x\y 0 1 0 1 0 1 1 0 On reconnaît ici le « OU exclusif » que l'on note par le symbole et qui peut être défini par l'équation logique suivante : x y = (x y) (x y) 5 En écrivant l'équation logique du OU exclusif, on remarque sa similarité avec la fonction logique réalisée par le circuit M1 . Il suffit pour obtenir le OU exclusif d'utiliser M1 avec d0 = y, d1 = y et s0 = x. On obtient donc le circuit suivant : d0 y d1 NON M1 s0 x 6 Pour réaliser la fonction OU à l'aide d'un concentrateur M2 , il suffit de fixer les entrées comme suit : d0 = 0, d1 = 1, d2 = 1 et d3 = 1, et de fournir x et y aux entrées s0 et s1 . En regardant attentivement la table de vérité de la fonction OU ci-dessous, on constate que la première colonne (quand y = 0) représente la fonction identité x 7 x, tandis que la deuxième colonne (quand y = 1) représente la fonction constante x 7 1. y 0 x 0 0 1 1 1 1 1 Pour construire la même fonction avec un simple concentrateur M1 , il suffit ainsi de fournir y à l'entrée s0 , de fournir x à d0 et de fixer d1 à 1. On a donc le circuit : x d0 1 d1 y s0 M1 7 Commençons par écrire la table de vérité de la fonction logique définie par (x, y, z) 7 (x y) z. s0 = x s1 = y s2 = z xy (x y) z 0 0 0 0 1 1 1 1 0 0 1 1 0 0 1 1 0 1 0 1 0 1 0 1 0 0 1 1 1 1 1 1 0 = d0 0 = d1 0 = d2 1 = d3 0 = d4 1 = d5 0 = d6 1 = d7 Par conséquent, si l'on fournit x, y, z, respectivement aux entrées s0 , s1 , s2 , il suffit de fixer les di comme indiqué dans la table.