SUJET 0
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 effaç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/8
Partie I - Logique
Un footballeur affirme à la presse :
(i). Le jour où je marque un but, je suis content et je fais la fête.
(ii). Le jour où mon équipe gagne, ou bien je suis content, ou bien je fais la fête ou les deux.
(iii). Le jour où mon équipe perd, ou bien je ne suis pas content, ou bien j’ai marqué un but ou les
deux.
(iv). Le jour où je ne marque pas et je fais la fête, je suis content.
(v). Aujourd’hui, je ne suis pas content.
Q1. Définir les variables propositionnelles nécessaires à la modélisation de ce problème.
Q2. Modéliser chacune des assertions à l’aide de formules propositionnelles.
Q3. Mettre chacune de ces formules en forme normale conjonctive.
Q4. On souhaite savoir si le joueur a marqué, si son équipe a gagné et s’il a fait la fête. Donner la
formule F permettant de répondre à ces questions. À quel problème classique est-on confronté ?
On rappelle l’algorithme de Quine (algorithme 1) : en notant
- C l’ensemble des clauses de F,
- x une variable propositionnelle,
- C[x ← >] l’ensemble des clauses obtenues en supprimant de C toutes les clauses contenant x,
et en supprimant ¬x de toutes les clauses contenant cette négation,
- C[x ← ⊥] l’ensemble des clauses obtenues en supprimant de C toutes les clauses contenant ¬x,
et en supprimant x de toutes les clauses contenant cette variable.
l’algorithme s’écrit :
Algorithme 1 : Algorithme de Quine
Fonction Quine(C)
Entrées : C l’ensemble des clauses de F.
Sorties : Vrai si F est satisfsiable, Faux sinon.
début
si C = ∅ alors
retourner Vrai
si ⊥ ∈ C alors
retourner Faux
Choisir x apparaissant dans une clause de C
si Quine(C[x ← ⊥]) alors
retourner Vrai
sinon
retourner Quine(C[x ← >])
Q5. Appliquer cet algorithme et trouver une valuation qui rende F vraie.
2/8
Partie II - Bases de données
On considère la base de données décrite par le modèle entité-association suivant :
Ville Cinéma
1,n A 1,1 Code_Cine
Code_Postal Nom
Nom Adresse
1,n
1,1
Réalisateur Film Salle
Nom_Réal 1,n R ÉALISE 1,1 Code_Film 1,n P ROJETTE 1,n Code_Salle
Prénom_Réal Titre nb_Entrées Capacité
Age Durée 3D
Dans cette représentation, on lie des entités par des associations avec des cardinalités. Ainsi par
exemple
Ville 1,n A 1,1 Cinéma
peut se lire comme “Une ville a 1 à n cinéma(s)“ et “un cinéma est présent dans 1 et une seule ville“.
Parfois, l’association possède des propriétés (le nombre d’entrées d’un film projeté dans une salle par
exemple).
On suppose que le champ 3D de l’entité Salle est un entier, valant 0 si la salle n’est pas en 3D, et 1
sinon. On suppose de plus que la durée des films est en heures. Enfin, on affirme qu’une ville peut être
uniquement déterminée par son code postal et son nom.
Q6. Donner le schéma relationnel correspondant. Préciser les clés primaires et étrangères des rela-
tions. Les clés primaires peuvent être associées à plusieurs attributs.
Q7. Écrire les requêtes suivantes en langage SQL :
(i). Donner le titre des films durant moins de 2h.
(ii). Donner le nom et le prénom du réalisateur ayant réalisé le film “Matrix”.
(iii). Compter le nombre de cinémas à Nantes.
(iv). Donner l’adresse des cinémas contenant au moins une salle 3D.
(v). Donner le code des films projetés dans toutes les salles.
(vi). Donner la liste des titres des films projetés dans le cinéma “Le Rio”.
3/8
Partie III - Algorithmique - Problèmes de dominos
Cette partie comporte des questions de programmation qui seront abordées en utilisant exclusivement
le langage C. Les codes seront commentés de manière pertinente.
Dans toute la suite, on suppose disposer, via stdbool.h, d’un type bool avec deux constantes true et
false.
Dans ce problème, on s’intéresse à quatre problèmes basés sur les dominos.
Un domino D est une pièce rectangulaire contenant deux chiffres, de 0 à N, matérialisés par des points.
ss sss s s
Par exemple, s s s ou s s sont deux dominos, représentant les paires (3,5) et (4,0). Un domino
est donc représenté par une paire d’entiers (i, j), i, j ∈ [[0, N]].
III.1 - Structures de données
Dans cette section, on construit les structures de données utiles pour les deux premiers jeux.
On définit le type structuré Domino : typedef struct { int x; int y; } Domino;
On dispose d’un sac S contenant n dominos Di = (ik , jk ), k ∈ [[1, n]], ik , jk ∈ [[0, N]].
Définition 1 (Chaîne)
Une chaîne de dominos est une séquence de pièces telle que les chiffres voisins sur chaque paire de
dominos consécutifs coïncident.
Par exemple, pour le sac
s s s s s s s s ss sss
( sss s s, s s , s
, s ss , s s s )
la séquence suivante est une chaîne de 5 dominos.
s s s s s s s s s s s
s ss ss sss sss s s s s s
On souhaite gérer un sac et une chaîne comme une liste chaînée de dominos.
Q8. Définir en C un type element permettant de stocker un domino et un pointeur vers l’élément
suivant de la liste chaînée.
Q9. Définir alors un type chaîne.
On représente les sacs de la même manière : on construit donc le type sac par typedef chaine sac.
Q10. Écrire une fonction de prototype element *ajoutElement(element *l,Domino d) qui ajoute le
domino d à la chaîne ou au sac l. Cet ajout se fera en fin de la liste chaînée. Par hypothèse, le
domino n’est pas déjà dans la chaîne.
Q11. Écrire une fonction de prototype element *retireElement(element *l,Domino d) qui retire le
domino d de la chaîne ou du sac l.
Q12. Écrire une fonction de prototype bool rechercheElement(element *l, Domino d) qui re-
cherche si le domino d est déjà dans la chaîne ou le sac l. La fonction renvoie true si c’est
le cas, false sinon.
III.2 - Existence d’une chaîne de taille n
Dans ce premier problème, on cherche une permutation des n dominos du sac formant une chaîne, si
elle existe. Pour cela, on développe une approche de type retour sur trace (backtracking).
4/8
On suppose dans un premier temps que l’on ne peut pas effectuer de rotation des dominos. Ainsi,
ss sss s s s
s s s ne pourra pas représenter le domino s s s s s .
Q13. Écrire une fonction de prototype bool possible(int i,int j) qui teste s’il est possible de
placer Di à droite de D j . La fonction renvoie true si c’est le cas, false sinon.
ss s s
On suppose maintenant qu’il est possible d’effectuer une rotation des dominos. Ainsi, si Di = s s s et
s ss ss
D j= , il n’est pas possible de placer directement D j à droite de Di , mais si on le retourne on
s s s
obtient D = s s
j et le placement devient possible. On souhaite donc écrire une fonction de prototype
bool possibleAvecRotation(Domino Di,Domino *Dj).
Q14. Pourquoi passe-t-on un pointeur sur D j ?
Q15. Écrire la fonction possibleAvecRotation.
On définit une k-chaîne partielle comme une chaîne composée de k ∈ [[0, n]] dominos. Par convention,
la 0-chaîne est la chaîne vide.
Un algorithme de backtracking peut alors être construit pour résoudre le premier problème.
Q16. Comment passer d’une k-chaîne à une k + 1-chaîne ?
Q17. Proposer alors une stratégie, fondée sur un principe de backtracking, permettant de rechercher,
si elle existe, une chaîne qui utilise toutes les pièces.
Q18. Écrire l’algorithme correspondant en langage C.
Q19. Évaluer la complexité au pire des cas de votre algorithme.
III.3 - Nombre de chaînes de taille n
On souhaite ici compter le nombre de chaînes de taille n qu’il est possible de former à partir des
dominos présents dans un sac contenant n pièces.
On considère pour N ∈ N un sac de dominos SN , contenant tous les dominos (i, j), i, j ∈ [[0, N]] sans
ss sss sss ss
doublons (les dominos s s s et s s s sont les mêmes).
Q20. Combien de dominos contient SN ?
Dans la suite, on met les N + 1 doubles de côté et on cherche à réaliser les chaînes avec les n − N − 1
dominos restants (il suffit ensuite de rajouter les doubles à tous les emplacements possibles).
On construit un graphe non orienté KN+1 = (S , A) où S est l’ensemble des sommets numérotés de 0 à N
inclus et A est l’ensemble des arêtes, où ai j est l’arête reliant le sommet i au sommet j, et représentant
le domino (i, j). S contenant tous les dominos possibles, le graphe est complet.
Q21. Dessiner K3 .
Q22. Combien d’arêtes aboutissent à chaque sommet du graphe KN+1 ?
Réaliser une chaîne de dominos est équivalent à construire un chemin eulérien dans ce graphe.
Définition 2 (Chemin eulérien, cycle eulérien)
Un chemin eulérien dans un graphe non orienté est un chemin qui passe une fois et une seule par
toutes les arêtes du graphe. Si ce chemin revient au sommet de départ, on parle de cycle eulérien.
On rappelle que le degré d’un sommet s ∈ S dans un graphe est égal au nombre de sommets reliés à
s par une arête.
Q23. Montrer que le nombre de sommets de degré impair d’un graphe est pair.
Il n’existe donc aucun graphe ayant un seul sommet de degré impair.
Soit alors G un graphe connexe.
5/8
Q24. Montrer qu’un chemin eulérien dans G est impossible si G comporte plus de deux sommets de
degré impair.
On démontre maintenant qu’il suffit de montrer la condition réciproque sur un graphe dont tous les
sommets sont de degré pair pour le prouver pour un graphe ayant deux sommets de degré impair.
Supposons avoir montré qu’un graphe ayant tous ses sommets de degré pair admet au moins un
chemin eulérien, et soit G un graphe connexe dont deux sommets seulement s1 et s2 sont de degré
impair.
Q25. En construisant une arête entre s1 et s2 , montrer qu’il existe un chemin eulérien dans G.
Dans G, graphe dont tous les sommets sont de degré pair, on considère alors le plus grand chemin C
des arêtes de G, c’est-à-dire le chemin qui passe par le plus grand nombre d’arêtes du graphe. Si C
contient toutes les arêtes de G, alors on a un chemin ou un cycle eulérien. Sinon G contient au moins
une arête a non contenue dans C et deux cas sont possibles :
Q26. C est ouvert (ne forme pas une boucle). Démontrer par l’absurde que G ne contient pas une
telle arête a.
Q27. C est fermé. Démontrer de même par l’absurde que G ne contient pas une telle arête a.
Les résultats précédents permettent alors d’affirmer qu’il n’est possible d’effectuer un chemin eulérien
dans un graphe complet que si deux sommets au plus (donc 0 ou 2) sont de degré impair. Ils affirment
également que si N est impair, alors il n’existe pas de chemin eulérien. Enfin, si tous les sommets sont
pairs, on recherche des circuits, sinon des chemins.
Dans le reste des questions, N sera pair.
Q28. K7 possède-t-il des chemins eulériens ? des cycles eulériens ?
Q29. En utilisant les questions 20 et 22, et en notant E N+1 le nombre de! circuits eulériens de KN+1 ,
N+1
! N N+1
montrer le nombre de chaînes de taille n est égal à +N+1 E N+1 .
2 2
Il n’existe pas de formule connue donnant directement le nombre de circuits eulériens E N+1 . On trouve
assez facilement E5 = 264 ou encore E7 = 129976320. La valeur de E5 permet déjà d’apprécier que le
s s s s
nombre de chaînes des 15 dominos de à s s s s est égal à 126 730.
III.4 - Recherche de la plus longue sous-séquence.
Ici, on s’intéresse à la recherche de la plus longue sous-séquence de n dominos d’un sac S qui forme
une chaîne. Les dominos sont supposés ordonnés et ne peuvent être permutés. De plus, S ne contient
pas nécessairement tous les dominos possibles.
Par exemple, pour le sac
s s s s s s s s s s s ss ss
( sss s s, s s , s
, s s s , s s s )
la sous-séquence
sss s s s s
s s s s s s
est de taille maximale, égale à 2. Si on autorise les rotations de dominos, alors la plus longue sous-
séquence est de taille 3 :
sss s s s s s
s s s s s s
On aborde ce problème sous l’angle de la programmation dynamique. On suppose dans un premier
temps que les rotations de dominos sont interdites.
Soit l : N → N la fonction qui donne la longueur de la plus longue chaîne sous-séquence de D1 · · · Di ,
se terminant par le domino Di .
6/8
Q30. Donner une formule de récurrence sur i pour la fonction l.
Q31. En déduire un algorithme en pseudo-code pour calculer la fonction l sur [[1, n]].
On autorise maintenant la rotation des dominos. On note li j la longueur de la plus longue chaîne sous-
séquence de D1 · · · Di , se terminant par le domino Di , avec j = 1 si Di a subi une rotation, et j = 0
sinon.
Q32. Donner la valeur de l10 et l11 .
Il est nécessaire de garder trace de la rotation des dominos lors du parcours du sac S.
Q33. Proposer une modification du type structuré Domino permettant de prendre en compte cette
contrainte.
À l’étape i, on regarde alors si Di , tourné ou non, peut être accolé à Di−1 , lui aussi tourné ou non. Dans
le cas d’une réponse positive, alors la longueur de la sous-séquence est incrémentée de 1. Dans le
cas contraire elle est réinitialisée à 1. On retient finalement la valeur maximum entre les deux choix (Di
tourné ou non).
Q34. Proposer une formule de récurrence implémentant cette stratégie.
III.5 - Recherche du nombre de sous-séquences
Enfin, on souhaite compter le nombre de sous-séquences de taille quelconque que l’on peut former
avec les dominos inclus dans un sac S contenant n dominos Di = (ik , jk ), k ∈ [[1, n]]. Dans S, un même
domino (i, j) peut être présent plusieurs fois.
Définition 3 (matrice unitaire)
Pour i, j ∈ [[1, n]], on note :
- Mi j la matrice carrée de taille n dont le coefficient (i, j) vaut 1, les autres coefficients étant nuls.
- (∀i , j ∈ [[1, n]]) M̄i j = Mi j + M ji et M̄ii = Mii
Il est clair que B = { M̄i j , i, j ∈ [[1, n]]} forme une base des matrices réelles symétriques de taille n.
Définition 4 (Produit)
Pour A, B matrices carrées de taille n, on définit le produit A • B par A • B = AB + BA.
Q35.
Montrer que : (∀i, j, k, l ∈ [[1, n]]})
si i = k et j , l
M̄ jl
2 M̄ii + 2 M̄ j j si i = k et j = l et i , j
M̄i j • M̄kl =
2 M̄ii si i = j = k = l
si {i, j} ∩ {k, l} = ∅
0
Pour n ∈ N et S n l’ensemble des permutation de {1 · · · n}, on considère le polynôme
X
Pn (X1 · · · Xn ) = Xσ(1) · · · Xσ(n)
σ∈S n
En choisissant, pour tout k ∈ [[1, n]], M̄k = M̄ik jk on peut calculer
X Pn ( M̄1 · · · M̄n ) et on sait puisque B est
une base qu’il existe des réels αi j tels que Pn ( M̄1 · · · M̄n ) = αi j M̄i j .
i, j
Dans la suite, on modélise le domino (i, j) du sac S à l’aide de la matrice M̄i j .
Q36. Pour k ∈ [[1, n]], montrer par induction sur k que les dominos (i1 , j1 )(i2 , j2 ) · · · (ik , jk ) forment une
chaîne si et seulement si M̄i1 j1 • M̄i2 j2 • · · · • M̄ik jk , 0
Q37. En déduire qu’alors αik jk , 0 si et seulement si on peut construire une chaîne commençant en ik
et terminant en jk (ou vice-versa) en utilisant les dominos de S.
7/8
Étant donnés trois dominos (i1 , j1 ), (i2 , j2 ), (i3 , j3 ) formant une chaîne, on remarque qu’il est possible de
construire cette dernière de plusieurs manières : d’abord en posant (i1 , j1 ), puis (i2 , j2 ) à sa droite, et
enfin (i3 , j3 ) à droite ; ou alors (i2 , j2 ), puis (i1 , j1 ) à sa gauche et (i3 , j3 ) à sa droite... On note N(k) le
nombre de façons différentes de construire une même chaîne de longueur k.
Q38. Montrer que N(k) = 2k−1 .
αik jk
Q39. Déduire des questions précédentes que, étant donné S, il existe chaînes qui peuvent être
2n−1
construites démarrant de ik et terminant en jk (ou vice versa).
On reprend alors la modélisation de la sous-partie III.3 : à partir du sac S = {(ik , jk ), k ∈ [[1, n]]}, on
construit un graphe non orienté G = (S , A) où S est l’ensemble des sommets, un sommet par numéro
rencontré sur les faces des dominos de S et A est l’ensemble des arêtes, où ai j est l’arête reliant le
sommet i au sommet j, et représentant le domino (i, j) de S. Comme dans ce contexte, pour i et j
fixés, le domino (i, j) peut être présent plusieurs fois dans S, on s’autorise à faire de G = (S , A) un
multigraphe : A est un multi-ensemble d’arêtes. Ainsi, lorsque le domino (i, j) est présent plusieurs fois
dans S, l’arête correspondante apparait plusieurs fois dans le multi-ensemble A. Dans un dessin, on
représente plusieurs traits entre les sommets i et j.
Q40. Dessiner le graphe correspondant au sac
s s s s sss s s
s ss
s s
s ss
s s s ss s s
S= ( , , , , s s s , s s s )
X
Q41. Avec les notations précédentes, que représente M̄i j ?
(i, j)∈S
Q42. En utilisant la question 39, proposer alors un moyen de calculer le nombre de chemins eulériens
d’un graphe G commençant au sommet i et terminant au sommet j.
Q43. Sachant que
P6 ( M̄12 , M̄13 , M̄23 , M̄22 , M̄24 , M̄34 ) = 25 (12 M̄11 + 24 M̄22 + 24 M̄33 + 12 M̄44 )
donner le nombre de cycles eulériens du graphe de la question 40 commençant et terminant au
sommet 2.
FIN
8/8
