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)
                             

É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.