CCINP Informatique optionnelle MP 2020

SESSION 2020 C MP7IN

CONCOURS
COMMUN
INP

ÉPREUVE MUTUALISÉE AVEC E3A-POLYTECH

ÉPREUVE SPÉCIFIQUE - FILIÈRE MP

INFORMATIQUE

Jeudi 7 mai:8h-12h

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.

RAPPEL DES CONSIGNES

«_ Utiliser uniquement un stylo noir ou bleu foncé non efjaçable pour la 
rédaction de votre composition ; d'autres
couleurs, excepté le vert, peuvent être utilisées, mais exclusivement pour les 
schémas et la mise en évidence

des résultats.
° Ne pas utiliser de correcteur.
«_ Écrire le mot FIN à la fin de votre composition.

Les calculatrices sont interdites

Le sujet est composé de trois parties, toutes indépendantes.

1/10
Partie I - Logique et calcul des propositions

Dans la suite, les variables propositionnelles seront notées x;,x2... Les 
connecteurs propositionnels A
(conjonction), V (disjonction), = (implication) et & (équivalence) seront 
classiquement utilisés.

De même, la négation d'une variable propositionnelle x; (respectivement d'une 
formule F ) sera notée
x; (resp. 7).

I.1 - Définitions

Définition 1 (Minterme, maxterme).
Soit (x; : :: x,) un ensemble de n variables propositionnelles.

- On appelle minterme toute formule de la forme y; À y A +++ y, où pour touti 
EUR {1,--- ,n} y; estun
élément de {x;, =x;}.
- On appelle maxterme toute formule de la forme y, V y V :--y, où pour tout i 
EUR {1,-:: ,n} y; est

un élément de {x;, -x;}.

Les mintermes (respectivement maxtermes) y, À y2 À -:-y, et y, A y, A -:-y" 
(resp y1 V y2 V --: y, et
y, Vy, V:--y") sont considérés identiques si les ensembles {y;, 1 < i < n} et {y;, 1 < i < n} le sont. Q1. Donner l'ensemble des mintermes et des maxtermes sur l'ensemble (x;, x). Définition 2 (Formes normales conjonctives et disjonctives). Soit F une formule propositionnelle qui s'écrit à l'aide de n variables propositionnelles (x; : :: x,). - On appelle forme normale conjonctive de F toute conjonction de maxtermes logiquement équi- valente à TF.. - On appelle forme normale disjonctive de F toute disjonction de mintermes logiquement équiva- lente à Définition 3 (Système complet). Un ensemble de connecteurs logiques C est un système complet si toute formule propositionnelle est équivalente à une formule n'utilisant que les connecteurs de C. Par définition, C = {-, V,A,=, 8} est un système complet. L.2 - Le connecteur de Sheffer On définit le connecteur de Sheïfer, ou d'incompatibilité, par x19x2 = 1x1 V x. Q2. Construire la table de vérité du connecteur de Sheffer. Q3. Exprimer ce connecteur en fonction de - et A. Q4. Vérifier que -x;, = x19x1. Q5. En déduire une expression des connecteurs A, V et = en fonction du connecteur de Sheïfer. Justifier en utilisant des équivalences avec les formules propositionnelles classiques. Q6. Donner une forme normale conjonctive de la formule x; 0x2. Q7. Donner de même une forme normale disjonctive de la formule x;,°x. QS. Démontrer par induction sur les formules propositionnelles que l'ensemble de connecteurs C = {+} est un système complet. 2/10 Q9. Application : soit F la formule propositionnelle x; V (-x> A x3). Donner 
une forme logiquement
équivalente de F utilisant uniquement le connecteur de Sheïfer.

Partie II - Le problème de Freudenthal (Informatique pour tous)

L'objectif de cette partie est de proposer une implémentation en langage Python 
d'une solution au pro-
blème de Freudenthal.

Hans Freudenthal (1905-1990), mathématicien allemand naturalisé néerlandais, 
spécialiste de topologie
algébrique, est connu pour ses contributions à l'enseignement des 
mathématiques. En 1969, il soumet à
une revue mathématique le problème suivant :

Un professeur dit à ses deux étudiants Sophie et Pierre : "J'ai choisi deux 
entiers x et y, tels que
I, le produit xy est dans la liste précédente.

Q12. Soitunentier S < n. Écrire une fonction Prod(S ,n) qui renvoie, pour l'ensemble des (x, y) EUR N, tels que x + y = S, la liste des entiers P = xy. Par exemple, Prod(8, 9) retourne [12,15] puisque 8=6+2=3+S5. Q13. Pour S < n, en déduire une fonction Candidat_S(n) qui renvoie la liste des entiers S tels que la liste Prod(S ,n) est incluse dans la liste CoupleProd(n). Pierre peut maintenant déduire la valeur de X du fait qu'elle appartient à la liste retournée par la fonction Candidat_S(n). Plus précisément, le produit IT n'apparaît dans la liste Prod(S ,n) que pour une seule valeur de $S de la liste Candidat_S(n). Pour déterminer cet unique S, on recherche tout d'abord les produits P pour lesquels : - 1l existe deux sommes S, et S, dans la liste Candidat_S (n) telles que S;, < S;; - _P apparaît dans les listes Prod(S, ,n) et Prod(S>,n).

3/10
Q14. Écrire une fonction Double_P(n) qui renvoie la liste des produits P 
satisfaisant ces deux condi-
tions.

Il reste à construire une fonction Reste_S(n) permettant de ne retenir que les 
sommes S de la liste
Candidat_S(n) pour lesquelles 1l existe un unique élément en commun entre les 
listes Prod(S ,n) et
Double_P(n).

Q15. Écrire une fonction Reste_S(n) qui renvoie la liste de ces sommes.

Pour que Pierre conclue, il faut que la liste Reste_S(n) soit réduite à un 
singleton. Pour que Sophie
conclue également, 1l lui suffit de rechercher les éléments de la liste Prod(S 
,n) qui ne sont pas dans
Double_P(n).

Q16. Pour S < n, écrire une fonction Reste_P(S,n) qui renvoie la liste de ces produits. Les deux étudiants connaissent maintenant Y et II. Q17. Pour S < n, écrire une fonction Solution(P,S,n) qui retourne le couple (x, y) recherché. Partie III - Mots de Lyndon et de de Bruijn Cette partie comporte des questions nécessitant un code Caml. Pour ces questions, les réponses ne feront pas appel aux fonctionnalités impératives de langage (en particulier pas de boucles, pas de références). On considère 1c1 un alphabet totalement ordonné de k symboles, noté X. IIL.1 - Mots de Lyndon III.1.1 - Définitions Définition 4 (Mot). Un mot est une suite finie de longueur n de symboles m = m::-m,_\ où pour tout i, m;, E Zetn > lest
la longueur de m. On notera n = |m|.

On note ©" l'ensemble des mots de longueur n construits sur Z et ZX" l'ensemble 
des mots de longueur
quelconque construits sur Z. On note enfin EUR le mot vide.

Le type Caml choisi pour représenter un mot est une chaîne de caractères 
(string). Les éléments de ZX
sont représentés par le type char.

Dans toute la suite, les seules fonctions/méthodes Caml sur les chaînes de 
caractères qui peuvent être
utilisées sont :

S'.[i] (valeur du 5 caractère)

l'opérateur de concaténation "

la fonction String.length : string -> int

String.length s retourne la longueur des.

la fonction String.sub : string -> int -> int -> string.

String.sub s start 1 retourne une chaîne de longueur L contenant la sous-chaîne 
de s qui
commence en start.

4/10
Définition 5 (Préfixe, suffixe).
Soient M = Mo: - M1 EUR P = Po: Pip-1 deux mots de X :
= MP = Mo: * M1 Po" * Pip1 EUR Z"*Vlest le concaténé de m et p.
- m est un préfixe de p si [m| < {pl et m; = p; pour 0 < i < |m] -- 1. - m est un suffixe de p si |[m| < [pl ef m; = p}}-m+i pOur 0  string -> comparaison telle que
ordre m pest l'ordre relatif des mots m et p.

Définition 6 (Ordre lexicographique).
La relation définie par : m < p si et seulement si m = p ou m < p est appelée ordre lexicographique sur »". Définition 7 (Conjugué). Soit m EUR Z". Un conjugué de m est un mot de la forme m;:--m,_1Mo:::m; 1, pour i EUR [0,n -- 1]. Par convention, le conjugué de m pour i = 0 est le mot m lui-même. Q19. Écrire une fonction Caml conjugue : string -> int -> string telle que 
conjugue m 1
retourne le conjugué de m débutant par le i caractère de m, 0 < i < [m|-1. La notion de conjugaison induit une relation C définie sur Z" par mC p si et seulement si p est un conjugué de m. Q20. Montrer que C est une relation d'équivalence. Définition 8 (Collier). Un collier est le plus petit mot dans l'ordre lexicographique d'une classe de mots équivalents par la relation C. Un collier d'ordre n est dit périodique s'il peut s'écrire m,oùmeX,r>2etl>l.Ilest dit apério-
dique sinon, autrement dit si deux conjugaisons non triviales des membres de sa 
classe d'équivalence
ne sont jamais égales.

l

Définition 9 (Mot de Lyndon).
Un mot m EUR ©" est un mot de Lyndon si c'est un collier apériodigue.

Q21. On suppose 0 bool telle que Lyndon m 
renvoie true si m
est un mot de Lyndon. Cette fonction fera appel à une fonction récursive.

5/10
IIL.1.2 - Génération de mots de Lyndon

Soit m EUR X" un mot de Lyndon. Pour générer à partir de m un mot de Lyndon q 
de longueur au plus
n > |m]| sur », on utilise l'algorithme 1.

Algorithme 1 : Algorithme de génération d'un mot de Lyndon

Données : m EUR Z" un mot de Lyndon, n > |m|

Résultat : q le mot de Lyndon généré à partir de m.

Concaténer le mot m à lui même jusqu'à obtenir un mot q de longueur n. La 
dernière occurrence de
m pourra être tronquée pour arriver à un mot de longueur exactement n.

tant que /e dernier symbole de q est le plus grand symbole de Y faire
| Ôter ce symbole de q.

Remplacer le dernier symbole de q par le symbole qui suit dans X.

retourner q.

Q23. Donner l'indice dans m de la s° lettre de q en fonction de i et |m|.

Q24. Pour 2 = {0,1}, on donne le mot de Lyndon m = 00111 et n = 9. Donner le 
mot de Lyndon
généré par l'algorithme, en déroulant les différentes étapes produites par 
l'algorithme permettant
d'aboutir au mot de Lyndon.

L'algorithme 1 peut être utilisé pour générer tous les mots de Lyndon de 
longueur au plus n. Pour ce
faire, on part du plus petit symbole de X et on 1tère les trois étapes (1-2-3) 
de l'algorithme jusqu'à arriver
au mot vide.

Q25. Partant de m = 0 et toujours pour 2 = {0, 1}, construire par l'algorithme 
tous les mots de Lyndon
de longueur au plus 4.

Q26. Donner la complexité de l'algorithme 1 au pire des cas en nombre d'ajouts 
ou de suppressions
de caractères.

IIL.1.3 - Factorisation de mots de Lyndon

Définition 10 (Factorisation de Lyndon).
Soit m EUR Z". Une factorisation de m est une suite m;,...m, de mots de Lyndon 
telle que m = m:; ---m,
avec m, >= M:::> M.

On admet le résultat suivant :

Théorème 1 (Factorisation d'un mot).
Tout mot m EUR Z° admet une unique factorisation de Lyndon.

L'algorithme 2 propose une méthode de factorisation d'un mot m (on ne demande 
pas de le justifier).
Le principe est d'itérer sur la chaîne des symboles de m pour trouver le plus 
grand mot de Lyndon
possible. Lorsqu'un tel mot est trouvé, 1l est ajouté à la liste Z des facteurs 
de m et la recherche est
poursuivie sur la sous-chaîne restante.

Q27. En utilisant l'algorithme 2, écrire une fonction factorisation m qui 
réalise la factorisation
d'un mot m donné. Cette fonction fera appel à une ou des fonction(s) 
récursive(s).

6/10

Algorithme 2 : Algorithme de factorisation d'un mot de Lyndon

Données : m EUR Z" un mot de Lyndon.
Résultat : la liste £ des mots de Lyndon décroissants de la factorisation de m.
Le
j--l
k-- 0
tant que j < [m!| faire si 7j = [m| ou m, > m; alors
P = Mo M;_x-1
Ajouter p à L
Supprimer p de m
k-- 0
Ljei

sinon

sim, = m; alors
k--k+I

Lie J+i

sinon
k--0

Li-ji+i

retourner /.

III.2 - Mots de de Bruijn

III.2.1 - Définition

Définition 11 (Mot de de Bruijn).
Un mot de de Bruijn d'ordre n sur X est un collier qui contient tous les mots 
de Z" une et une seule fois.

Par exemple, pour Z = {a, b,c} et n = 2, m = abacbbcca est un mot de de Bruijn 
puisqu'il contient une
unique fois chaque mot de longueur 2 sur », le mot 'aa' étant obtenu par 
circularité de m.

Q28. Donner la longueur d'un mot de de Bruijn en fonction de n et du nombre k 
de symboles de X.
IIL.2.2 - Graphe de de Bruijn

Définition 12 (Graphe de de Bruijn).
Le graphe de de Bruijn d'ordre n sur X est le graphe orienté B(k, n) = (V, E) 
où :

- V=X" est l'ensemble des sommets du graphe ;

- E={(am,mb), a, bEe>,me DS est l'ensemble des arcs orientés du graphe.
On value les arcs E par le dernier symbole du noeud terminal de chaque arc : 
ainsi (am, mb) EUR E est
étiqueté par b.
Dans ce graphe, certains arcs ont pour sommet initial et terminal un même 
sommet de V. Ces arcs sont
appelés des boucles (figure 1).

Q29. Donner l'ensemble des mots de longueur 3 sur Z = {0,1}. En déduire de 
graphe de de Bruijn
B(2, 3) associé.

Q30. Montrer que le degré entrant et le degré sortant de chaque sommet est égal 
à K.

Q31. En déduire le nombre d'arcs orientés |E| en fonction de k et n.

7/10
Figure 1 - Exemple de graphe avec boucle sur le sommet A.

Définition 13 (Successeur, prédécesseur).

Soit G = (V, E) un graphe orienté. v EUR V est un successeur (respectivement 
prédécesseur) de u EUR V si
(u,v)e E (resp. (v,u) EUR E).

Q32. Soient B(K, n) = (V,E) et m EUR V. Montrer que tous les prédécesseurs de m 
ont le même ensemble
de successeurs.

Q33. Soit p = (po: ::p} 1) EUR V. Donner l'ensemble des sommets m tels que (p, 
m) EUR E.

On suppose disposer de B(k, n) et on souhaite construire 8(K, n + 1) à partir 
de ce graphe.
Q34. Proposer une méthode pour construire les sommets de B(K, n + 1) à partir 
des arcs de BK, n).
Donner le sommet créé dans B(2, 4) à partir de l'arc (001,010) de (2, 3).

On dit que deux arcs e,,e: EUR E sont adjacents dans B(Kk, n) si ces deux arcs 
s'écrivent e; = (mi, p) et
EURe2 -- (P; q) pour mn, P, q EUR V.

Q35. Proposer de même une construction des arcs de S(k,n + 1) en fonction des 
arcs adjacents de
B(Kk, n). Donner l'arc de B(2, 4) créé par les arcs adjacents de B(2, 3) 
(001,011) et (011,110).

IIL.2.3 - Construction des mots de de Bruijn
On propose 1c1 trois algorithmes de construction de mots de de Bruijn.
IIL.2.3.1 - Construction à l'aide de 8(K, n)
Les mots de de Bruijn d'ordre n sur Z peuvent être construits en parcourant 
B(K, n).

Définition 14 (Circuit eulérien).
Soit G un graphe orienté. Un circuit eulérien est un chemin dont l'origine et 
l'extrémité coïncident et
passant une fois et une seule par chaque arête de G.

Q36. Construire (2, 2) et trouver dans ce graphe un circuit eulérien. Vérifier 
que la concaténation des
étiquettes lues au fil de ce circuit donne un représentant d'un mot de de 
Bruijn et donner son
ordre sur {0, 1}.

8/10
On admet les résultats suivants :

QG). un graphe G = (V, E) possède un circuit eulérien si et seulement s1 1l est 
connexe et si, pour tout
v EUR V, le degré entrant de v et le degré sortant de v sont égaux.

(1). un circuit eulérien dans le graphe B(K, n) correspond à un mot de de 
Bruijn.

Q37. En déduire qu'il existe au moins un mot de de Bruijn pour tout alphabet X 
et tout n.

Ainsi, la concaténation des étiquettes lues au fl d'un circuit eulérien de B(k, 
n) donne un représentant
d'un mot de de Bruiyn d'ordre n + 1 sur k symboles.

IIL.2.3.2 - Construction à l'aide de l'algorithme Prefer One

Pour construire les mots de de Bruiyn d'ordre n sur Z = {0, 1}, on peut 
également utiliser l'algorithme 3,
dit algorithme Prefer One.

Algorithme 3 : Algorithme Prefer One
Données : n. >

Résultat : m mot de de Bruijn de longueur n sur X.
m -<-- suite de ñn zeros STOP- false tant que STOP=false faire Etape I Ajouter un 1 à la fin de m. si les n derniers symboles de m n'ont pas été rencontrés auparavant alors | Répeter Etape 1 sinon Retirer le 1 ajouté à la fin de m. | Passer à Etape 2 Etape 2 Ajouter un 0 à la fin de m. si les n derniers symboles de m n'ont pas été rencontrés auparavant alors |_ Aller à l''Etape 1 sinon _ LL STOP true retourner m. Dans cet algorithme, "les n derniers symboles de m n'ont pas été rencontrés auparavant" Signifñie que le mot composé des n derniers symboles de m n'est pas un sous-mot de m, situé entre le premier et le ([m| -- 1)° symbole de m. Q38. Appliquer l'algorithme au cas n = 3 et Z = {0,1}. Écrire les valeurs successives de m au cours de l'exécution. IIL.2.3.3 - Construction à l'aide de la relation aux mots de Lyndon La troisième construction utilise les notions de collier et de mots de Lyndon. Q39. Donner, pour k = 2 et n = 4, les classes d'équivalence de tous les mots binaires de longueur 4 pour la relation C. En déduire les colliers correspondants. Q40. En déduire les mots de Lyndon de longueur 4 pour 2 = {0, 1}. Plus généralement, les mots de de Brun et de Lyndon sont étroitement liés. On peut montrer que si l'on concatène, dans l'ordre lexicographique, les mots de Lyndon sur £ symboles dont la longueur divise un 9/10 entier ñn, alors on obtient le mot de de Bruijn le plus petit, pour l'ordre lexicographique, de tous les mots de de Bruijn de longueur n sur k symboles. Q41. Déduire de la question précédente le plus petit mot de de Bruijn pour n = 4 et Z = {0, 1}. III.2.4 - Application La soirée a été longue, vous rentrez chez vous mais, au pied de votre immeuble, vous vous trouvez confronté à un sérieux problème : vous avez complètement oublié le code d'entrée à n chiffres de la porte. On suppose que le digicode de l'appartement est composé de 1 < k < 10 chiffres 0, 1,...k-- Î, qui constituent l'alphabet ZX. Le digicode fonctionne de la façon suivante : vous tapez successivement sur les chiffres afin de composer un mot. À chaque nouveau symbole entré à partir du n-ième, le digicode teste le mot constitué par les n derniers chiffres pour voir s'il correspond au code secret. Ainsi, par exemple pour ñn = 4, si vous tapez la séquence 021201, le digicode teste successivement 0212, 2120 et 1201. Étant pressé de regagner votre lit, vous cherchez à taper un minimum de touches pour ouvrir la porte. On note ñ la longueur de la plus petite séquence de frappe de touches qui vous permet de rentrer dans l'immeuble. Q42. Donner un encadrement de à : - pour la borne supérieure, on considèrera que l'on met bout à bout tous les mots possibles de n chiffres construits sur >:
- pour la borne inférieure, on cherchera un mot sans redondance, c'est-à-dire 
qui contient
une et une seule fois chaque mot de n chiffres.

Q43. Expliquer en une phrase en quoi les mots de de Bruijn peuvent vous aider. 
En vous inspirant de
l'algorithme 3, donner une séquence la plus courte de chiffres à taper pour 
ouvrir à coup sûr la
porte de votre immeuble, lorsque n = 2 et k = 4.

Q44. Comparer alors le nombre maximum de frappes de touches du digicode à 
effectuer en utilisant
les mots de de Bruin, avec celui calculé par la méthode brute. Calculer ces 
nombres pour :
- k=4etn = 2.
- k=10etn=4.

Que conclure quant à l'efficacité de votre stratégie ?

FIN

10/10