Centrale Informatique MP 2006

Thème de l'épreuve Un algorithme de compression de données. Problème de logique.
Principaux outils utilisés programmation, logique booléenne, automates, lois de De Morgan, circuits logiques

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


 

n__>_ e......___... ...:0F<ëoe0...ë aä.........

OEQQN UOE>OEQ3OE | ËOEbQOEÜ OEgBOQCOÜ

Les deux parties sont indépendantes et peuvent être traitées dans un ordre 
quelconque.

Partie I - Un algorithme de compression de
données

Dans cette partie, on appelle document une suite de symboles terminée par un
symbole particulier que l'on note SymboleFinal. On s'intéresse à la représen-
tation d'un document sous la forme la plus compacte possible.

I.A - Codage de longueurs de séquences

Une technique de réduction du nombre de symboles utilisés pour représenter un
document consiste à remplacer chaque séquence de symboles identiques par la
longueur de la séquence suivie du symbole. Il faut toutefois pouvoir distinguer
les longueurs de séquences des symboles originellement présents dans le docu-
ment. On utilise pour cela des délimiteurs spécifiques, ne figurant pas parmi 
les
symboles présents dans le document.

L'ensemble des symboles du document est un ensemble de caractères
qui contient les lettres minuscules et majuscules, les chiffres décimaux, les
caractères de ponctuation et divers caractères spéciaux : parenthèses, accola-
des, guillemets mais ne contient pas les crochets.

On choisit alors les crochets [ et '] comme délimiteurs des longueurs de 
séquences
et on peut ainsi coder, par exemple, le document suivant :
abcdefffffghiiiiiijkllllllllll

sous la forme :
abcde[5]fgh[6]ijk[lO]l

En fait, à chaque symbole est associé un entier que l'on appelle son code, qui 
le
représente dans le document codé. Ainsi le document ci--dessus sera-t--il codé 
en
réalité sous la forme :

a'b'c'd'e' [5]f'g'h' [6]i'j'k' [1011'
où a' est le code de a, b' est le code de b, etc.
On dispose des fonctions suivantes :

symbole_suivant rend l'entier correspondant au symbole suivant du docu-
ment, ou le code SymboleFinal lorsque la fin du document est atteinte ;

sortir_char prend en argument un caractère et le place en sortie du codeur
(cette sortie peut être l'écran ou un fichier) ;

sortir_code prend en argument un entier et place en sortie du codeur le sym-
bole (caractère) dont cet entier est le code ;

sort ir_int prend en argument un entier et place en sortie du codeur la suite
de symboles qui représente cet entier en base 10 ;

symbole prend en argument un entier et rend le symbole dont cet entier est le
code;

code prend en argument un symbole et rend son code.

Note: on rappelle que les délimiteurs ouvrant et fermant de longueur de
séquence [ et ] n'apparaissent pas dans le document initial à coder.

On définit une structure de données Encodeur permettant de représenter, sous
forme d'un enregistrement, l'état du codeur de longueurs de séquences. Cet état
correspond à la séquence de symboles qu'il est en train de lire et à la 
position à
laquelle il se trouve dans cette séquence.

en CAML en PASCAL
type Encodeur = Encodeur = record
{mutable code_symbole : int; code_symbole : integer;
mutable compte : int compte : integer
} end;

I.A.1) Écrire une fonction initialiser_codeur qui rend un Encodeur
représentant l'état initial d'un codeur (hors de toute séquence de symboles).

Écrire une fonction vider_codeur qui reçoit en argument un Encodeur et
place sur la sortie le résultat du codage de la séquence de symboles qui corres-
pondent à son état. Cette fonction rend le nouvel état du codeur.

I.A.2) Écrire une fonction coder qui reçoit en argument un entier et un
Encodeur et rend un Encodeur correspondant à l'état du codeur après traite-
ment du symbole dont l'entier est le code.

I.A.3) Quel est le résultat du codage du document aabbcc avec cet
algorithme ? Quel problème cela pose--t--il ? Que peut-on modifier pour 
l'('lll('(llt'l'
à ce problème '?

I.A.4) Écrire une fonction decoder qui, lorsqu'elle lit un document codé, affi-
che en sortie un document dans lequel les séquences compactées sous la forme
[compte ] code_symbole sont restaurées sous leur forme initiale.

On supposera que le document lu est correct, c'est-à--dire que toute occurrence
du symbole [ est suivie d'une suite de chiffres terminée par ], elle--même 
suivie
d'un entier, code d'un symbole.

On supposera de plus que les caractères 0 à 9 sont représentés par des entiers
consécutifs croissants.

Partie II - Problème logique et automate

Après l'évasion de Thésée, Minos décida de modifier le labyrinthe de Dédale afin
de l'utiliser pour tester les qualités de logicien des étrangers désireux 
d'intégrer
sa cour. Pour cela, il fit modifier le tracé afin que toute personne ayant 
retrouvé
son chemin passe dans un couloir fermé par trois portes devant impérativement
être ouvertes successivement. En cas d'échec, le candidat se retrouve projeté
dans une partie sans issue du labyrinthe. Chacune des trois portes est ouverte
par un système de trois leviers. Ils sont tous sur une position de départ neutre
et possèdent deux positions de fonctionnement 1 ou 0 , correspondant respecti-
vement aux VRAI et FAUX logiques, mais également àla numération en base 2 .
Ainsi, les neufs leviers (les trois de chaque porte) forment-ils un nombre 
écrit en
base 2 lorsque le candidat les a manipulés successivement (aucun levier ne peut
rester neutre). La position du levier 1 est le bit de plus haut poids, celle du
levier 9 est le bit de plus faible poids. En visite dans le labyrinthe, vous 
vous
retrouvez dans ce couloir et votre seule chance de survivre est de répondre 
cor--
rectement en respectant les règles propres à chaque porte et indiquées sur le
fronton. Ces règles de fonctionnement de chaque porte sont systématiquement
vérifiées (ce qui n'est bien sûr pas nécessairement le cas des énoncés relatifs 
aux
positions des leviers).

Sur le fronton de la première porte est écrit : « les trois énoncés associés 
aux trois
leviers sont tous vrais ou tous faux ».

Les trois énoncés sont notés respectivement El , E2 , E 3 . Les variables 
proposi--
tionnelles associées aux leviers de la première porte L| , L2 , L3 .

II.A - Représenter la règle sous la forme d'une formule du calcul des proposi-
tions dépendant de E| , E2' E3 .
Les énoncés suivants sont inscrits sur la porte :

° Le levier 2 ne peut pas être sur « 1 » seul, mais les trois ne sont pas sur « 
l ».

° Si le levier 3 est sur « 1 », ou si les leviers ! et 2 sont sur « 0 » alors 
le levier
3 est sur « 1 » et ce n'est pas le seul dans ce cas.

° Si le levier l est sur « l » alors le levier 3 y est aussi, et si le levier 1 
est sur
« 0 » alors c'est également le cas du levier 2.

KB - Exprimer El , E2 et E 3 sous la forme de formules du calcul des proposi-
tions dépendant de L| , L2 et L 3.

11.0 - En utilisant le calcul des propositions (résolution avec les formules de 
De
Morgan, ...), simplifier les énoncés pour les écrire sous forme de conjonction 
(ET)
de disjonctions (OU) de littéraux, un littéral étant une variable 
propositionnelle
ou sa négation.

II.D - En déduire la ou les valeurs possibles des variables propositionnelles 
Ll ,
L2 et L,.

La première porte s'ouvre, puis se referme après votre passage. Elle est suivie
par une deuxième porte sur le fronton de laquelle est écrit : « Une seule des 
affir--
mations est fausse ». Les trois énoncés sont notés respectivement E4 , E5 , E6.

Les variables propositionnelles associées aux leviers de la deuxième porte L 4 ,

Les énoncés suivants sont inscrits sur la porte :
° La valeur du levier 4 est le produit des valeurs des leviers 5 et 6.

° La valeur du levier 5 est la somme sans retenue (addition 1 bit) des valeurs
des leviers 4 et 6.

° La valeur du levier 6 est la retenue de la somme des valeurs des leviers 4 et 
5 .

ILE - Exprimer E 4 , E5 et E6 sous la forme de formules du calcul des proposi--
tions dépendant de L 4, L5 , L6.

II.F - En déduire la ou les valeurs possibles des variables propositionnelles L 
4 ,
L5 et L.,.

Les ingénieurs crétois avaient conçu des équivalents mécaniques de nos portes
logiques actuelles AND, OR et NOT.

A chaque porte est ainsi associé un circuit prenant en entrée les positions des
trois leviers et donnant en sortie VRAI ou FAUX respectivement pour ouvrir ou
non la porte.

II.G - Construire, en les justifiant, les circuits permettant de réaliser les 
opéra--
tions d'ouverture des portes, en fonction des réponses successives données.

Afin d'éviter que quelqu'un puisse réussir à sortir en testant successivement
toutes les possibilités, les ingénieurs ont installé un système qui fonctionne 
de
la manière suivante :

0 dès que les trois leviers de la première porte ont été positionnés, la porte
s'ouvre et les positions de ces trois leviers sont mémorisées, que ces positions
soient correctes ou non ;

0 la seconde porte ne s'ouvre que si les positions des six leviers sont 
correctes ;
sinon le candidat est orienté vers une voie définitivement sans issue.

Les crétois disposent à cette fin d'un circuit mémoire à deux entrées et une 
sortie

telle que le couple ( l, 0) enregistre la valeur VRAI (ou 1) et (O, 1 ) la 
valeur FAUX
(ou 0).

II.H - Proposer un circuit permettant de réaliser cette opération.

II.I - Utiliser ce circuit mémoire pour connecter les deux montages de la ques-
tion II.G et réaliser un circuit unique ouvrant dans tous les cas la première
porte, puis la seconde uniquement si toutes les réponses ont été correctes.

Après la réussite aux deux premières épreuves, le couloir débouche sur une troi-
sième porte, sur le fronton de laquelle est écrit : « la position des trois 
derniers
leviers, l'un au moins n'étant pas sur « 0 », permet au nombre, écrit en 
binaire,
formé par les neufs leviers d'être divisible par 7 ».

II.J - En déduire la ou les positions possibles des leviers L7 , L8 et L9.

Pour vérifier si la réponse donnée est acceptable, les ingénieurs utilisent un
automate fini. L'alphabet est A = {O, I } . Les mots sont les écritures 
binaires des

nombres, en commençant par le bit de poids fort. L'automate 32% est donc décrit
par la structure  où :

° Q est un ensemble non vide appelé ensemble des états de M ,

0 A est l'alphabet,

0 E est un sous-ensemble de Q x A x Q appelé ensemble des transitions de % ,
0 I est un sous-ensemble de Q appelé ensemble des états initiaux de % ,

° T est un sous-ensemble de Q appelé ensemble des états terminaux de 32% .

On représente graphiquement l'automate 52% de la façon suivante :

° un état p est figuré par un cercle marqué par p :

- le fait que p & I est représenté par une flèche sans origine entrant dans
le cercle marqué par p :

- le fait que p & T est représenté par un double cercle autour de p ;

° une transition ( p, a, q) E E est représentée par une flèche allant de l'état 
p
vers l'état q et étiquetée par la lettre a .

II.K - Si les écritures binaires de n et n' sont n : b,b2...bk et n' : 
b,b2...bkbk+l
(bl étant le bit de poids fort), déterminer le reste de la division de n'
par 7 connaissant le reste de la division de n par 7 .

II.L - Déterminer les différentes transitions possibles entre les différents 
états
de l'automate.

II.M - Construire, en justifiant avec soin, un automate testant la divisibilité
par 7 . On rappelle que les trois bits de plus faible poids ne peuvent pas être 
tous
les trois nuls.

II.N - Modifier l'automate précédent pour tester la conformité des solutions
proposées pour les leviers des trois portes.

ILO - Appliquer l'automate pour vérifier la solution proposée pour les leviers
des trois portes.

ooo FIN ooo

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



Centrale Informatique MP 2006 -- Corrigé
Ce corrigé est proposé par Samuel Mimram (ENS Lyon) ; il a été relu par 
Sattisvar
Tandabany (ENS Lyon) et Vincent Puyhaubert (Professeur en CPGE).

Le sujet est constitué de deux parties indépendantes.
· La première propose d'implémenter un algorithme de compression de données
en regroupant dans des documents des occurrences consécutives d'un même
caractère. L'écriture de fonctions (courtes) est demandée.
· La seconde partie, plus longue, introduit des problèmes de logique qu'un 
joueur,
enfermé dans un labyrinthe, doit résoudre pour pouvoir positionner des leviers
qui vont lui permettre de sortir du labyrinthe. Trois techniques principales 
sont
abordées. Il est tout d'abord proposé de résoudre les énigmes en les formalisant
sous forme de formules en logique booléenne. Les tables de vérité et les 
identités classiques sur les formules en logique booléenne (lois de De Morgan, 
etc.)
sont mises à contribution. On est ensuite amené à réaliser le circuit électrique
du labyrinthe à l'aide de portes logiques. Enfin, il est proposé de réaliser un
automate afin de vérifier les solutions du joueur au problème logique.
L'énoncé comporte principalement des questions pratiques et permet donc de
réviser la manipulation des outils classiques.

Indications
Partie I
I.A.1 Utiliser l'encodeur pour stocker le nombre d'occurrences consécutives 
déjà lues
du dernier caractère rencontré.
I.A.2 Mettre à jour l'encodeur en testant si le caractère en entrée est le même 
que le
dernier caractère lu.
I.A.3 S'intéresser à la longueur du codage.
I.A.4 Ne pas oublier que n est stocké sous la forme de son écriture décimale.

Partie II
II.D Dresser les tables de vérité des formules E1 , E2 et E3 .
II.E Dresser la table des valeurs possibles pour L4 , L5 et L6 pour chacune des 
trois
parties de l'énoncé.
II.F Idem.
II.G Donner des formules simples qui sont vraies si et seulement si les portes 
1 et 2
doivent s'ouvrir puis les implémenter en utilisant les portes logiques.
II.H Proposer un circuit contenant une boucle de rétroaction. Cette question 
est difficile et hors-programme, n'hésitez pas à passer directement à la 
question II.J.
II.I Utiliser le circuit mémoire de la question précédente pour stocker la 
validité
des positions des trois premiers leviers.
II.J En utilisant les valeurs précédemment trouvées pour L1 , . . ., L6 
énumérer les
valeurs des nombres ayant pour écriture binaire les leviers, suivant les 
différentes positions possibles des leviers L7 , L8 et L9 .
II.K Utiliser la relation b1 · · · bk+1 = 2 × b1 · · · bk + bk+1 .
II.L Appliquer le résultat de la question précédente.

I. Un algorithme de compression de données
Les identifiants en OCaml ne prennent pas de majuscules (sauf les noms
de modules et les constructeurs de types inductifs). Nous noterons donc
symbole_final le symbole qui termine un document et encodeur le type
des encodeurs afin que le code présenté soit valide à la fois en Caml Light et
en OCaml.
I.A.1 Nous allons utiliser les encodeurs (les enregistrements de type encodeur) 
de
la façon suivante. Le champ code_symbole contiendra le code du dernier symbole 
lu
et le champ compte contiendra le nombre d'occurrences consécutives déjà lues de 
ce
symbole.
La fonction initialiser_coder crée un nouvel encodeur. Son champ compte
contiendra 0 ­ aucun caractère n'a encore été lu ­ et un symbole quelconque dans
code_symbole ­ nous avons ici choisi symbole_final.
let initialiser_codeur () =
{
code_symbole = symbole_final;
compte = 0
}
;;
La fonction vider_codeur doit placer sur la sortie le symbole dont le code est
contenu dans le champ code_symbole, éventuellement précédé de [n] si le nombre n
d'occurrences de ce symbole (stocké dans le champ compte de l'encodeur) est 
strictement supérieur à 1. Si n est nul, il ne faut bien sûr rien placer du 
tout sur la
sortie. Une fois cette opération réalisée, il faut remettre le compteur 
d'occurrences
de l'encodeur à 0. En voici une implémentation possible :
let vider_codeur encodeur =
if encodeur.compte > 1 then
(
sortir_char '[';
sortir_int encodeur.compte;
sortir_char ']';
);
if encodeur.compte > 0 then
sortir_code encodeur.code_symbole;
encodeur.compte <- 0;
encodeur
;;
I.A.2 La fonction coder doit incrémenter le compteur d'occurrences (le champ
compte) de l'encodeur si le symbole donné en argument est le même que celui qui 
a été
précédemment lu et qui est stocké dans le champ code_symbole de l'encodeur. 
Sinon,
il faut placer sur la sortie le contenu de l'encodeur (grâce à la fonction 
vider_codeur),
puis stocker le symbole donné en argument en tant que symbole précédemment lu et
remettre le compteur d'occurrences à 1.

let coder encodeur symb =
if symb = encodeur.code_symbole then
encodeur.compte <- encodeur.compte + 1
else
(
vider_codeur encodeur;
encodeur.code_symbole <- symb;
encodeur.compte <- 1;
);
encodeur
;;
Le sujet ne précise pas ce qu'il faut faire si le symbole donné en argument
est symbole_final. Nous n'avons pas géré ce cas ici, mais il était par exemple
envisageable de lever une exception.
Le sujet précise que les fonctions vider_codeur et coder doivent renvoyer les 
nouveaux états des encodeurs. Ceci est inutile car les champs des
encodeurs sont modifiables (ce qui est déclaré par le mot clé mutable).
I.A.3 Le résultat du codage du document aabbcc avec ce algorithme est
[2]a'[2]b'[2]c'.
On constate qu'il est plus long (en nombre de caractères) que l'original ! Pour 
remédier à ce problème, il suffit de ne mettre une séquence cn , contenant n 
caractères
consécutifs c, sous la forme [n]c que si n est supérieur à 4. En effet, en deçà 
le codage
produit une séquence plus longue que l'originale.
Pour tester nos fonctions, supposons que le code d'un caractère est son code
ASCII (l'un des systèmes de codage les plus utilisés). On peut définir les
fonctions de l'énoncé de la façon suivante :
let symbole_final = 0;;
let code = int_of_char;;
let symbole = char_of_int;;
let sortir_char = print_char;;
let sortir_code c = sortir_char (symbole c);;
let sortir_int = print_int;;
Par convention, nous avons supposé que le code du symbole final est 0, ce qui
correspond au caractère spécial '\000'. La fonction symbole_suivant peut
être simulée par la fonction suivante. Elle renvoie un à un les caractères de
la chaîne de caractères document_test qui contient l'exemple aabbcc de la
question I.A.3 et se termine par le caractère '\000'.
let document_test = "aabbcc\000";;
let i = ref (-1);;