Version interactive avec LaTeX compilé
ÉPREUVE SPÉCIFIQUE - FILIÈRE MP
INFORMATIQUE
Jeudi 3 mai : 14 h - 18 h
N.B. : le candidat attachera la plus grande importance à la clarté, à la précision et à la concision de la rédaction. Si un candidat est amené à repérer ce qui peut lui sembler être une erreur d'énoncé, il le signalera sur sa copie et devra poursuivre sa composition en expliquant les raisons des initiatives qu'il a été amené à prendre.
N.B. : le candidat attachera la plus grande importance à la clarté, à la précision et à la concision de la rédaction. Si un candidat est amené à repérer ce qui peut lui sembler être une erreur d'énoncé, il le signalera sur sa copie et devra poursuivre sa composition en expliquant les raisons des initiatives qu'il a été amené à prendre.
Les calculatrices sont interdites
Le sujet est composé de trois parties, toutes indépendantes.
Partie I - Logique et calcul des propositions
Vous avez été sélectionné(e) pour participer au jeu "Cherchez les Clés du Paradis (CCP)". Le jeu se déroule en trois épreuves, au cours desquelles vous devez collecter des clés vertes. À l'issue de chacune d'entre elles, vous passez à l'épreuve suivante en cas de succès et êtes éliminé(e) en cas d'échec.
I. 1 - Première épreuve
Jean-Pierre Pendule, le célèbre animateur, vous accueille pour la première épreuve. Il vous explique la règle du jeu. Devant vous, deux boîtes et sur chacune d'entre elles une inscription. Chacune des boîtes contient soit une clé verte, soit une clé rouge. Vous devez choisir l'une des boîtes : si le résultat est une clé rouge, alors vous quittez le jeu, si c'est une clé verte vous êtes qualifié(e) pour l'épreuve suivante.
Jean-Pierre Pendule dévoile les inscriptions sur chacune des boîtes et vous affirme qu'elles sont soit vraies toutes les deux, soit fausses toutes les deux :
Jean-Pierre Pendule dévoile les inscriptions sur chacune des boîtes et vous affirme qu'elles sont soit vraies toutes les deux, soit fausses toutes les deux :
- sur la boîte 1, il est écrit : "Une au moins des deux boîtes contient une clé verte" ;
- sur la boîte 2, il est écrit : "Il y a une clé rouge dans l'autre boîte".
Dans toute cette partie, on note
Q1. Donner une formule de la logique des propositions représentant la phrase écrite sur la boîte 1.
Q2. Donner de même une formule de la logique des propositions pour l'inscription de la boîte 2.
Q3. Donner une formule représentant l'affirmation de l'animateur. Simplifier cette formule de sorte à n'obtenir qu'une seule occurrence de chaque
Q4. Quel choix devez-vous faire pour continuer le jeu à coup sûr?
Q1. Donner une formule de la logique des propositions représentant la phrase écrite sur la boîte 1.
Q2. Donner de même une formule de la logique des propositions pour l'inscription de la boîte 2.
Q3. Donner une formule représentant l'affirmation de l'animateur. Simplifier cette formule de sorte à n'obtenir qu'une seule occurrence de chaque
Q4. Quel choix devez-vous faire pour continuer le jeu à coup sûr?
I. 2 - Deuxième épreuve
Bravo, vous avez obtenu la première clé verte. Jean-Pierre Pendule vous félicite et vous annonce que cette première épreuve n'était qu'une mise en jambe. Avec les mêmes règles du jeu, l'animateur vous propose alors deux nouvelles boîtes portant les inscriptions suivantes :
- sur la boîte 1, il est écrit : "Il y a une clé rouge dans cette boîte, ou bien il y a une clé verte dans la boîte 2";
- sur la boîte 2, il est écrit : "Il y a une clé verte dans la boîte 1 ".
Q5. Donner une formule de la logique des propositions pour chaque affirmation.
Q6. Sachant qu'encore une fois les deux affirmations sont soit vraies toutes les deux, soit fausses toutes les deux, donner le contenu de chaque boîte. En déduire votre choix pour remporter la deuxième clé verte.
Q6. Sachant qu'encore une fois les deux affirmations sont soit vraies toutes les deux, soit fausses toutes les deux, donner le contenu de chaque boîte. En déduire votre choix pour remporter la deuxième clé verte.
I. 3 - Troisième épreuve
Le suspens est à son comble, vous voici arrivé(e) à la dernière épreuve. À votre grande surprise, Jean-Pierre Pendule vous dévoile une troisième boîte et vous explique les règles du jeu. Dans une des boîtes se cache la clé verte qui vous permet de remporter la victoire finale. Dans une autre boîte se cache une clé rouge qui vous fait tout perdre. La dernière boîte est vide. Encore une fois, chacune des boîtes porte une inscription :
- sur la boîte 1, il est écrit : "La boîte 3 est vide" ;
- sur la boîte 2, il est écrit : "La clé rouge est dans la boîte 1" ;
— sur la boîte 3, il est écrit : "Cette boîte est vide".
L'animateur affirme que l'inscription portée sur la boîte contenant la clé verte est vraie, celle portée par la boîte contenant la clé rouge est fausse. L'inscription affichée sur la boîte vide est aussi vraie.
Q7. Donner une formule de logique des propositions pour chaque inscription.
Q8. Donner une formule de logique des propositions synthétisant l'information que vous a apportée l'animateur.
Q9. En supposant que la clé verte est dans la boîte 2, montrer par l'absurde que l'on aboutit à une incohérence.
Q10. Donner alors la composition des trois boîtes.
Q8. Donner une formule de logique des propositions synthétisant l'information que vous a apportée l'animateur.
Q9. En supposant que la clé verte est dans la boîte 2, montrer par l'absurde que l'on aboutit à une incohérence.
Q10. Donner alors la composition des trois boîtes.
Partie II - Automates
Un langage est régulier si et seulement si il est accepté par un automate fini (en particulier déterministe). Cependant, plusieurs automates peuvent accepter le même langage. L'objectif de cette partie est de montrer que tout langage reconnaissable
II. 1 - Définitions
Définition 1. Automate déterministe
Un automate déterministe
Un automate déterministe
-
un ensemble d'états,
un alphabet, -
l'état initial, -
un ensemble d'états finaux, -
une application de transition définie sur tout entier.
Définition 2. Soit
Définition 3. Résiduel d'un langage par rapport à un mot
Soient
Soient
Q11. Pour
Définissons alors une relation
Définissons alors une relation
Q12. Montrer que
Q13. Posons
(i).
(ii).
(iii). abbaba et aaa.
Q13. Posons
(i).
(ii).
(iii). abbaba et aaa.
Définition 4. Soit
-
.
Définition 5. Soit
Une relation d'équivalence
Si
Définition 6. Automate minimal
Soit
Soit
-
, -
, -
,
.
On admettra qu'un automate minimal définit bien un automate.
Q14. Montrer que l'automate minimal d'un langage régulierest un automate fini, c'est-à-dire un automate possédant un nombre fini d'états.
Définition 7. Automate accessible
Un automate déterministe
Un automate déterministe
Définition 8. Automate réduit
Un automate déterministe
Un automate déterministe
Pour
II. 2 - Construction de l'automate minimal
Soit
En particulier,
L'algorithme 1 est un algorithme de réduction d'un automate
L'algorithme 1 est un algorithme de réduction d'un automate
Algorithme 1: Algorithme de recherche des états équivalents
Entrée : un automate déterministe $A=\left(Q, \Sigma, q_{0}, F, \delta\right)$
Sortie : les ensembles d'états équivalents
$k \leftarrow 0$
************ Initialisation ************
$N_{0} \leftarrow \emptyset$
pour tous $p \in F$ et $q \in Q \backslash F$ faire
***La paire (p,q) est distinguée.***
$N_{0} \leftarrow N_{0} \cup\{(p, q)\}$
tant que $N_{k} \neq \emptyset$ faire
****Construction de $N_{k+1}{ }^{* * * *}$
$N_{k+1} \leftarrow \emptyset$
pour chaque paire $(p, q) \in N_{k}$ faire
pour chaque a $\in \Sigma$ faire
pour chaque $(r, s) \in Q^{2}$ tel que $\delta(r, a)=p, \delta(s, a)=q$ faire
si $(r, s) \notin \bigcup_{i=0}^{k} N_{i}$ alors
i
$N_{k+1} \leftarrow N_{k+1} \cup\{(r, s),(s, r)\}$
$k \leftarrow k+1$
Q15. Montrer pourquoi, dans la phase d'initialisation, la paire (
Q16. Montrer pourquoi, si
Soit alors
Q16. Montrer pourquoi, si
Soit alors
|
|
|
|
|
|
|
|
|
|
2 | 4 | 6 | 5 | 1 | 6 |
|
|
1 | 3 | 2 | 1 | 6 | 2 |
où
Q17. Représenter graphiquement l'automate
Q17. Représenter graphiquement l'automate
- les états sont des cercles, le nom de l'état est écrit à l'intérieur du cercle ;
- les transitions sont représentées par des flèches partant de l'état de départ et pointant sur l'état d'arrivée. Le symbole définissant la transition est indiqué au milieu de la flèche ;
- l'état initial est signalé par une flèche sans étiquette pointant sur cet état;
- les états finaux sont entourés d'un deuxième cercle, externe au premier.
Q18. Appliquer l'algorithme 1 pour trouver l'ensemble des états équivalents. Pour chaque itération
Un théorème, non détaillé ici, permet alors de projeter
Q19. Représenter graphiquement l'automate minimal de la question précédente, avec ses états et ses transitions.
Q19. Représenter graphiquement l'automate minimal de la question précédente, avec ses états et ses transitions.
Partie III - Algorithmique et programmation
Nous proposons dans cette partie d'étudier une méthode de compression de données. L'algorithme proposé ici implémente plusieurs couches d'arrangement de données et de compression successives, utilisées dans l'ordre suivant pour la compression et l'ordre inverse pour la décompression :
(i). Transformation de Burrows-Wheeler (BWT),
(ii). Codage par plages (RLE),
(iii). Codage de Huffman.
(i). Transformation de Burrows-Wheeler (BWT),
(ii). Codage par plages (RLE),
(iii). Codage de Huffman.
Définition 9. Soit
Pour
Dans toute cette partie, lorsqu'il s' agira de coder une fonction CAML, un mot
Pour
Dans toute cette partie, lorsqu'il s' agira de coder une fonction CAML, un mot
Les paragraphes suivants étudient les algorithmes et propriétés de ces phases, chacun d'entre eux pouvant être abordé de manière indépendante.
III. 1 - Transformation de Burrows-Wheeler (BWT)
Soit
Dans la suite, nous étudions le codage et le décodage d'un mot transformé par cette opération.
Dans la suite, nous étudions le codage et le décodage d'un mot transformé par cette opération.
- Phase de codage -
On rajoute à la fin de
Q20. Pour
Q21. Écrire une fonction récursive CAML circulaire : 'a list -> 'a list qui réalise une permutation à droite d'un mot
Q22. Écrire une fonction CAML matrice_mot : 'a list -> 'a list list qui construit la matrice
Une permutation des lignes de
Q23. Donner les matrices
Pour construire la matrice de permutation
Q24. Écrire une fonction récursive CAML tri : 'a list -> 'a list qui réalise le tri par insertion d'une liste d'éléments.
Q25. En déduire une fonction matrice_mot_triee : 'a list -> 'a list list qui construit
Q26. Pour
Q27. En déduire la complexité dans le pire des cas pour le tri des
La transformation BWT consiste alors à coder le mot
Q28. Écrire alors une fonction codageBWT : char list -> char list qui encode un mot passé en entrée. On utilisera une fonction récursive permettant de récupérer le dernier symbole de chacun des mots de
Q21. Écrire une fonction récursive CAML circulaire : 'a list -> 'a list qui réalise une permutation à droite d'un mot
Q22. Écrire une fonction CAML matrice_mot : 'a list -> 'a list list qui construit la matrice
Une permutation des lignes de
Q23. Donner les matrices
Pour construire la matrice de permutation
Q24. Écrire une fonction récursive CAML tri : 'a list -> 'a list qui réalise le tri par insertion d'une liste d'éléments.
Q25. En déduire une fonction matrice_mot_triee : 'a list -> 'a list list qui construit
Q26. Pour
Q27. En déduire la complexité dans le pire des cas pour le tri des
La transformation BWT consiste alors à coder le mot
Q28. Écrire alors une fonction codageBWT : char list -> char list qui encode un mot passé en entrée. On utilisera une fonction récursive permettant de récupérer le dernier symbole de chacun des mots de
- Phase de décodage -
Pour décoder un mot codé par BWT, il est nécessaire de reconstruire itérativement
On pose ici comme exemple
Q29. Construire, à partir de la seule donnée de
La dernière et la première colonne de
Q30. Proposer un algorithme permettant d'obtenir la deuxième colonne de
Q31. On dispose à l'itération
Q32. En déduire un algorithme itératif permettant de reconstruire
Q33. Quel décodage obtient-on pour le mot
On pose ici comme exemple
Q29. Construire, à partir de la seule donnée de
La dernière et la première colonne de
Q30. Proposer un algorithme permettant d'obtenir la deuxième colonne de
Q31. On dispose à l'itération
Q32. En déduire un algorithme itératif permettant de reconstruire
Q33. Quel décodage obtient-on pour le mot
III. 2 - Codage par plages RLE [Informatique pour tous]
Le codage RLE (Run Length Coding), ou codage par plages, est une méthode de compression dont le principe est de remplacer dans une chaîne de symboles une sous-chaîne de symboles identiques par le
couple constitué du nombre de symboles identiques et du symbole lui－même．Par exemple，la chaîne ＂aaababb＂est compressée en［（3，＇a＇），（1，＇b＇），（1，＇a＇），（2，＇b＇）］．
Q34．Proposer un type naturel Python pour la compression RLE，qui permet de représenter le résultat comme indiqué précédemment．
couple constitué du nombre de symboles identiques et du symbole lui－même．Par exemple，la chaîne ＂aaababb＂est compressée en［（3，＇a＇），（1，＇b＇），（1，＇a＇），（2，＇b＇）］．
Q34．Proposer un type naturel Python pour la compression RLE，qui permet de représenter le résultat comme indiqué précédemment．
－Phase de codage－
On s＇intéresse tout d＇abord au codage RLE d＇un mot．
Q35．Écrire une fonction itérative en Python def RLE（mot）：qui code un mot passé en entrée par codage RLE．
Q35．Écrire une fonction itérative en Python def RLE（mot）：qui code un mot passé en entrée par codage RLE．
－Phase de décodage－
On s＇intéresse maintenant au décodage d＇une liste．
Q36．Écrire une fonction itérative en Python def decodeRLE（codeRLE）：qui décode une listecodeRLE issue du codage RLE d＇un mot．
Q36．Écrire une fonction itérative en Python def decodeRLE（codeRLE）：qui décode une listecodeRLE issue du codage RLE d＇un mot．
III． 3 －Codage de Huffman［Informatique pour tous］
La dernière étape de l＇algorithme proposé implémente le codage de Huffman，qui utilise la structure d＇arbre binaire．Le principe est de coder un symbole de manière d＇autant plus courte que son nombre d＇occurrences dans le mot est élevé．L＇arbre de Huffman se construit à l＇aide de l＇algorithme 2.
Algorithme 2: Codage de Huffman
Entrée : $\mu$ un mot de taille $|\mu|$
Sortie : $\operatorname{Huffman}(\mu)$ le codage de Huffman de $\mu$
pour $a \in \Sigma$ faire
si $|\mu|_{a}>0$ alors
créer un noeud $\left(a,|\mu|_{a}\right)$
$\mathcal{L} \leftarrow$ liste des noeuds dans l'ordre croissant des poids
$\mathcal{A} \leftarrow$ liste vide
tant que $($ longueur $(\mathcal{L})+$ longueur $(\mathcal{A})>1)$ faire
$(g, d) \leftarrow$ deux noeuds de plus faible poids parmi les 2 premiers noeuds de $\mathcal{L}$ et les 2 premiers
noeuds de $\mathcal{A}$
Créer un noeud $t$
$n_{t} \leftarrow n_{g}+n_{d}$
gauche $(t) \leftarrow g$
Coder la branche de $t$ à $g$ par 0
droite $(t) \leftarrow d$
Coder la branche de $t$ à $d$ par 1
Insérer $t$ à la fin de $\mathcal{A}$
Retirer $g$ et $d$ de $\mathcal{L}$ ou de $\mathcal{A}$
$\underline{\operatorname{Huffman}}(\mu) \leftarrow \mathcal{A}$
Q37．Construire le codage de Huffman du mot
Q38．Quelle est la forme de l＇arbre de Huffman dans un mot où tous les symboles ont le même nombre d＇occurrences ？
Q38．Quelle est la forme de l＇arbre de Huffman dans un mot où tous les symboles ont le même nombre d＇occurrences ？