X/ENS Informatique B MP-PC-PSI 2017

Thème de l'épreuve Intersection de deux ensembles de points
Principaux outils utilisés listes, SQL
Mots clefs codage de Lebesgue, AQL

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


ÉCOLE POLYTECHNIQUE -- ÉCOLES NORMALES SUPÉRIEURES
ÉCOLE SUPÉRIEURE DE PHYSIQUE ET DE CHIMIE INDUSTRIELLES

CONCOURS D'ADMISSION 2017

FILIÈRES

MP HORS SPECIALITÉ INFO,
PC ET PSI

COMPOSITION D'INFORMATIQUE ­ B ­ (XELCR)
(Durée : 2 heures)
L'utilisation des calculatrices n'est pas autorisée pour cette épreuve.
Le langage de programmation sera obligatoirement Python.

Intersection de deux ensembles de points
Soit n un entier naturel. On note Dn l'ensemble des entiers naturels compris 
entre 0 et 2n - 1.
On appelle « point de Dn × Dn » tout couple d'entiers (x, y)  Dn × Dn . Soient 
P et Q deux
parties de Dn × Dn . On cherche à calculer efficacement l'intersection des 
ensembles de points P
et Q. La résolution de ce problème a des applications en simulation numérique, 
en robotique ou
encore dans l'implémentation d'interfaces utilisateurs.
Ce sujet est découpé en cinq parties. La partie I porte sur une solution naïve 
en Python, la
partie II sur une solution naïve en SQL. Les parties III, IV et V conduisent à 
la réalisation d'une
solution efficace en Python. La partie I et la partie II sont totalement 
indépendantes l'une de
l'autre et du reste du sujet. Les parties suivantes ne sont pas indépendantes.

Remarques préliminaires
Complexité. La complexité, ou le temps d'exécution, d'un programme P (fonction 
ou procédure) est le nombre d'opérations élémentaires (addition, 
multiplication, affectation, test, etc.)
nécessaires à l'exécution de P. Lorsque cette complexité dépend de plusieurs 
paramètres n et m,
on dira que P a une complexité en O((n, m)), lorsqu'il existe trois constantes 
A, n0 et m0 telles
que la complexité de P soit inférieure ou égale à A × (n, m), pour tout n > n0 
et m > m0 . Lorsqu'il est demandé de garantir une certaine complexité, le 
candidat devra justifier cette dernière
en raisonnant sur la structure du code.

1

Rappels de Python. Si a est une liste alors a[i] désigne le i-ième élément de 
cette liste
où l'entier i est supérieur ou égal à 0 et strictement plus petit que la 
longueur len(a) de la
liste. La commande a[i] = e affecte la valeur de l'expression e au i-ième 
élément de la liste a.
L'expression [] construit une liste vide. L'expression n * [k] construit une 
liste de longueur n
contenant n occurrences de k. La commande a = list(b) construit une copie de la 
liste b
et l'affecte à la variable a. La commande a.append(x) modifie la liste a en lui 
rajoutant un
nouvel élément final contenant la valeur de x. Important : Seules les 
opérations sur les listes
apparaissant dans ce paragraphe sont autorisées dans les réponses. Si une 
fonction Python
standard est nécessaire, elle devra être réécrite.
Nous attacherons la plus grande importance à la lisibilité du code produit par 
les candidats ;
aussi, nous encourageons les candidats à utiliser des commentaires et à 
introduire des procédures
ou des fonctions intermédiaires pour faciliter la compréhension du code.

Partie I. Une solution naïve en Python
Pour commencer, un point de coordonnées (x, y)  Dn × Dn est représenté en 
Python par
une liste de deux entiers naturels [x, y]. Un ensemble de points est représenté 
par une liste de
points sans répétition, donc comme une liste de listes d'entiers naturels de 
longueur 2.
Question 1. Écrire une fonction membre(p,q) qui renvoie True si le point p est 
dans l'ensemble
représenté par la liste q et qui renvoie False dans le cas contraire.
Question 2. Écrire une fonction intersection(p,q) qui renvoie une liste 
représentant l'intersection des ensembles représentés par p et q. On 
implémentera l'algorithme qui consiste à itérer
sur tous les points de p et à insérer dans le résultat seulement ceux qui sont 
aussi dans q.
Question 3. Si la comparaison entre entiers naturels est prise comme opération 
élémentaire,
quelle est la complexité de l'algorithme de la question précédente exprimée en 
fonction de la
longueur de p et q ?

Partie II. Une solution naïve en SQL
On suppose maintenant que l'on représente les points du problème à l'aide d'une 
base de
données. Cette base de données comporte deux tables. La table POINTS contient 
trois colonnes :
-- id (clé primaire) qui est un entier naturel unique représentant le point ;
-- x qui est un entier naturel représentant son abscisse ;
-- y qui est un entier naturel représentant son ordonnée.
On suppose qu'il n'existe pas deux points d'identifiants distincts et de mêmes 
coordonnées.
La relation d'appartenance d'un point à un ensemble de points est représentée 
par la table
MEMBRE à deux colonnes :
-- idpoint, un entier naturel qui identifie un point ;
-- idensemble, un entier naturel qui identifie un ensemble de points.

2

Question 4. Écrire une requête SQL qui renvoie les identifiants des ensembles 
auxquels appartient le point de coordonnées (a, b).
Question 5. Écrire une requête SQL qui renvoie les coordonnées des points qui 
appartiennent
à l'intersection des ensembles d'identifiants i et j.
Question 6. Écrire une requête SQL qui renvoie les identifiants des points 
appartenant à au
moins un des ensembles auxquels appartient le point de coordonnées (a, b).

Partie III. Codage de Lebesgue
On souhaite implémenter en Python une solution efficace au problème du calcul 
de l'intersection entre deux ensembles de points. La solution proposée s'appuie 
sur une structure de
données appelée AQL. Cette structure de données suppose que les coordonnées des 
points sont
représentées par leur codage de Lebesgue.
Le codage de Lebesgue d'un point de coordonnées (x, y)  Dn × Dn s'obtient par 
entrelacement des bits des représentations binaires de x et y en commençant par 
les bits de x. On
suppose que les bits de poids forts sont situés à gauche dans les 
représentations binaires des
entiers naturels.
2

2

Par exemple, si n vaut 3, si x vaut 6 (donc 110 en binaire), et si y vaut 3 
(donc 011 en
2
binaire) alors le codage de Lebesgue du point de coordonnées (x, y) est 101101 
, c'est-à-dire 45.
Le codage de Lebesgue d'un point peut être vu comme un nombre écrit dans la 
base formée
2
2
2
2
2
2
des chiffres 00 , 01 , 10 et 11 . Ainsi, si n = 3, le point (6, 3) = (110 , 011 
) est codé par le
2
2
2
nombre 10 11 01 .
2

2

De plus, on utilisera la notation décimale 0, 1, 2 et 3 pour représenter les 
chiffres 00 , 01 ,
2
2
10 et 11 , et on notera cn-1 . . . c0  la représentation en base 4 du codage de 
Lebesgue d'un point

de Dn × Dn . Par exemple, pour n = 3, le codage de Lebesgue du point (6, 3) 
sera écrit 231 .
En Python, la séquence des chiffres d'un codage de Lebesgue d'un point de Dn × 
Dn est
stockée dans une liste de longueur n triée par poids décroissants : le chiffre 
de poids le plus fort
se trouve en première position, le chiffre de poids le plus faible en dernière 
position. Ainsi, si
n = 3, le codage de Lebesgue du point (6, 3) est représenté en Python par la 
liste [2,3,1].
Question 7. Soit n = 3, quelle liste Python représente le codage de Lebesgue du 
point (1, 6) ?
Question 8. On suppose que l'on dispose d'une fonction bits(x,k), qui prend en 
arguments
deux entiers naturels x et k, et qui renvoie la valeur du bit de coefficient 2k 
dans la représentation
binaire de x.

3

Écrire une fonction code(n,p) qui prend en arguments un entier strictement 
positif n et un
point p représenté par une liste de longueur 2 dont les deux coordonnées sont 
prises dans Dn .
Cette fonction renvoie le codage de Lebesgue de p représenté sous la forme 
d'une liste Python.

Partie IV. Représentation d'un ensemble de points
On utilise l'ordre lexicographique (autrement dit, l'ordre du dictionnaire) 
pour trier les co
dages. Soient c = cn-1 . . . c0  et d = dn-1 . . . d0 deux codages de Lebesgue 
de points de Dn × Dn .
On note c < d pour « c est strictement plus petit que d » si

j, j > i  cj = dj
i, 0  i < n tel que
c i < N di
où  0 alors le chemin est de la forme d1 · d2 · · · dk . Dans ce cas, le 
quadrant atteint
par d1 · d2 · · · dk dans Dn × Dn est l'ensemble des points de Dn × Dn dont le 
codage de

Lebesgue est de la forme d1 d2 . . . dk cn-k-1 . . . c0 pour cn-k-1 , . . . , 
c0  {0, 1, 2, 3}.
Question 11. On pose pour cette question n = 2. Donner la représentation sous 
forme de
codage de Lebesgue compacté trié par ordre lexicographique de l'ensemble de 
points S1 valant
{(0, 0), (3, 3), (3, 2), (1, 1), (1, 2), (2, 2), (2, 3)}.

Partie V. Calcul efficace de l'intersection d'ensembles de points
Compaction par codage des quadrants. Soit S un ensemble de points de Dn × Dn 
représenté par la liste L triée par ordre lexicographique des codages de 
Lebesgue de ses points
(comme dans la partie précédente). En se dotant d'un symbole supplémentaire, 
notons-le 4, on
compacte la liste L en représentant chaque sous-séquence (maximale) L 
correspondant à un

quadrant de chemin d1 · · · dk par l'unique mot d1 · · · dk · 4 · · · 4 (dans 
lequel on a rajouté (n - k)
fois le symbole 4).
Notons qu'un codage de Lebesgue compacté représente un ensemble de points et 
non un
unique point comme c'est le cas avec les codages de Lebesgue non compactés. 
Notons aussi que
la liste des codages reste triée pour l'ordre lexicographique.
Par exemple, l'ensemble de points S0 est compactable en [[0, 4], [2, 2], [3, 
0]]. Le
codage [0,4] représente le quadrant 0 situé en bas à gauche de la figure 1. 
Enfin, pour illustrer
un cas où n > 2, la figure 3 décrit le codage compacté d'un ensemble de points 
de D3 × D3 .
5

est compacté en

{000 , 003 , 030 , 033 , 114 , 124 , 244 , 334 }
Figure 3 ­ Un ensemble de points de D3 × D3 et sa représentation compactée.
Structure de données d'AQL. On appelle « AQL de l'ensemble de points S » la 
liste triée
et compactée des codages de Lebesgue des points de l'ensemble S.
Question 12. Donner l'AQL de l'ensemble S1 de la question 11.
Question 13. Écrire une fonction ksuffixe(n, k, q) qui prend en arguments un 
entier n
strictement positif, une liste q représentant le codage de Lebesgue compacté 
d'un quadrant
de Dn × Dn et un entier naturel k inférieur strictement à n. Si les k derniers 
chiffres de la liste q
ont pour valeur 4, cette fonction renvoie une nouvelle liste semblable à la 
liste q mais dont les
k + 1 derniers chiffres valent 4. Sinon, cette fonction renvoie q inchangée.
Ainsi, ksuffixe(4, 2, [0,1,4,4]) renvoie [0,4,4,4], et ksuffixe(4, 2, [0,1,2,4])
renvoie [0,1,2,4].
Question 14. L'algorithme de compaction d'une liste triée de codages de 
Lebesgue consiste à
parcourir n fois la liste représentant l'ensemble de points. L'itération k vise 
à remplacer quatre
codages successifs formant un quadrant complet de côté 2k+1 par la 
représentation compactée
de ce quadrant.
Écrire une fonction compacte(n,s) qui prend en arguments un entier strictement 
positif n
et un ensemble de points P de Dn × Dn représenté par la liste triée s des 
codages de Lebesgue
de ses points. Cette fonction renvoie l'AQL de l'ensemble de points P .
Question 15. On remarque que l'ordre lexicographique < défini plus haut 
s'adapte sans changement aux codages de Lebesgue compactés. Cependant, on 
souhaite comparer deux codages de
Lebesgue compactés en termes des relations d'inclusion et d'exclusion des 
ensembles de points
qu'ils représentent.
Écrire une fonction compare_ccodes(n,p,q) qui prend en arguments un entier 
strictement
positif n, une liste p contenant le codage de Lebesgue compacté d'un quadrant P 
de Dn × Dn
et une liste q contenant le codage de Lebesgue compacté d'un quadrant Q de Dn × 
Dn . Cinq
valeurs de retour sont possibles :
-- l'entier 0 si les quadrants sont égaux ;
-- l'entier 1 si les quadrants P et Q sont disjoints et p < q ;
-- l'entier -1 si les quadrants P et Q sont disjoints et q < p ;
-- l'entier 2 si P  Q ;
-- l'entier -2 si Q  P .

6

Par exemple, compare_ccodes(3, [1,4,4], [2,4,4]) renvoie 1 et compare_ccodes(3,
[1,2,4], [1,4,4]) renvoie 2.
Question 16. Pour calculer efficacement l'intersection de deux ensembles de 
points représentés
par leur AQL respectif, on fusionne les deux listes triées qui leur 
correspondent.
En utilisant compare_ccodes, écrire une fonction intersection2(n,p,q) qui prend 
en arguments un entier strictement positif n ainsi que deux AQL p et q 
représentant respectivement
deux ensembles P et Q de points de Dn ×Dn . Cette fonction renvoie un AQL 
représentant P Q.
Le nombre d'appels à la fonction compare_ccode effectués par 
intersection2(n,p,q) doit être
en O(len(p) + len(q)).

7

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



X/ENS Informatique B (MP/PC) 2017 -- Corrigé
Ce corrigé est proposé par Josselin Giet (ENS Ulm) ; il a été relu par Virgile
Andreani (ENS Ulm) et Vincent Puyhaubert (professeur en CPGE).

Ce sujet présente une solution optimisée à la recherche d'intersection 
d'ensembles
de points à coordonnées entières.
· La première partie permet de définir le problème et d'en donner une solution
naïve et guidée, dans le langage Python. Comme toute résolution naïve, elle
permet de constater la nécessité de trouver une optimisation.
· La deuxième partie relie cette problématique à l'utilisation d'une base de 
données. Elle permet d'écrire des exemples de requêtes SQL afin de résoudre le
problème.
· La troisième partie introduit la notion de codage de Lebesgue d'un point à
coordonnées entières. Il s'agit d'une autre manière de représenter un point en
entrelaçant l'écriture binaire de ses coordonnées.
· La quatrième partie introduit la notion d'ordre lexicographique appliquée aux
codages de Lebesgue de points ainsi qu'une interprétation visuelle du codage
de Lebesgue sous forme de « chemin » pour trouver la position du point.
· La dernière partie définit le codage de Lebesgue compacté d'un ensemble de
points et utilise ce procédé pour résoudre le problème du calcul de 
l'intersection
d'ensembles de points de manière optimisée.
Cet énoncé permet d'aborder un problème d'algorithmique original et intéressant.
Les remarques tout au long de l'énoncé ainsi que les questions « exemple » 
permettent
de bien comprendre les nouvelles notions introduites. La remarque en début 
d'énoncé,
à propos des opérations sur les listes, interdit d'utiliser un grand nombre 
d'opérations
qui sont rapides à écrire en Python, comme la compréhension de liste.

Indications
Partie I
2 Utiliser la fonction de la question précédente.
Partie II
4 Faire une jointure entre les tables POINTS et MEMBRE.
5 Utiliser l'opérateur INTERSECT.
6 Faire une jointure dont un des arguments est une autre requête complète 
adéquate.
Partie III
8 On peut remarquer que chaque élément de la liste peut être calculé 
indépendamment des autres.
Partie IV
9 Lire la remarque sur l'ordre lexicographique, ce qui permet de mieux 
comprendre
la définition.
11 Il y a une coquille dans cette question : Il ne faut pas lire le mot « 
compacte ».
Partie V
13 Faire attention au cas k == 0.
14 Utiliser la fonction de la question précédente.
15 Expliciter ce que signifie une inclusion stricte de deux ensembles au niveau 
de
leur codage de Lebesgue.
16 Utiliser l'ordre lexicographique pour parcourir une seule fois les deux AQL 
en
parallèle.

I. Une solution naïve en Python
1 L'algorithme consiste à regarder tous les éléments de q, un par un, et à 
tester si
l'un d'entre eux est égal à p.
def membre(p,q):
for i in range(len(q)):
q_i = q[i]
if p[0] == q_i[0] and p[1] == q_i[1]:
return True
return False
Cet algorithme s'arrête quand on a trouvé un élément dans la liste égal
à p (ce qui correspond au return True ligne 5) ou quand on a fini d'énumérer
les éléments de q (ce qui correspond au return False ligne 6).
Le test de la ligne 4 peut s'écrire de nombreuses manières. Par exemple,
en remarquant que q est en réalité une matrice de taille len(p)×2, on peut
enlever la ligne 4 et remplacer q_i[0] (resp. q_i[1]) par q[i][0] (resp.
q[i][1]), ce qui sera toujours le cas dans la suite.
Enfin, il est possible d'écrire une version purement itérative de cet 
algorithme (i.e. en ne faisant pas de return dans une boucle for ou while).
Il faut savoir le faire, car de nombreux langages ne permettent pas de renvoyer 
le résultat en plein milieu d'une boucle for. Pour cela, on utilise une
boucle while dont le test dépend du nombre d'éléments de q testés, ainsi que
d'une variable qui dit si un élément de q égal à p a été trouvé.
def membre(p,q):
res , i = False , 0
while (i < len(q)) and not res:
if p[0] == q[i][0] and p[1] = q[i][1]:
res = True
else
i += 1
return res
2 En suivant l'algorithme donné dans l'énoncé, on obtient la fonction 
ci-dessous.
def intersection(p,q):
res = []
for i in range(len(p)):
if membre(p[i],q):
res.append(p[i])
return res
3 Notons |p| (resp. |q|) la taille de p (resp. de q). À chaque passage dans la 
boucle
for de la fonction membre, on fait deux comparaisons. Ainsi, la complexité d'un 
appel
de la fonction membre est 2 · |q|. Or, on fait |p| appels à la fonction membre 
dans la
fonction intersection. Par conséquent,
La complexité de l'algorithme est O(|p| · |q|)

II. Une solution naïve en SQL
4 Cette requête peut s'écrire en utilisant une jointure.
SELECT idensemble
FROM POINTS JOIN MEMBRE ON id = idpoint
WHERE x = a AND y = b
Cette jointure peut aussi s'écrire comme un simple produit cartésien en
déplaçant la condition de jointure à la condition de sélection.
SELECT idensemble
FROM POINTS JOIN MEMBRE
WHERE id = idpoint AND x = a AND y = b
Il faut toutefois noter que cette manière de procéder, bien que parfaitement 
correcte, est fortement déconseillée, car elle construit toute la table
alors que la jointure sélectionne les entrées puis fait les tests de la ligne 
WHERE.
Dès lors, dans le premier cas, la requête est généralement plus rapide. Dans
la suite, nous utiliserons systématiquement une jointure sur une clé primaire
avant de faire des tests.
5 Cette requête peut se faire au moyen d'une intersection.
(

SELECT idpoint
FROM MEMBRE
WHERE idensemble = i)
INTERSECT
(
SELECT idpoint
FROM MEMBRE
WHERE idensemble = j)
Cette requête n'est pas la seule réponse possible. On peut aussi bien faire
une jointure sur la table MEMBRE, comme dans l'exemple suivant :
SELECT t1.idpoint
FROM MEMBRE AS t1 JOIN MEMBRE AS t2
ON t1.idpoint = t2.idpoint
WHERE t1.idensemble = i AND t2.idensemble = j
Cette requête crée, en effet, une table relationnelle contenant
(t1.idpoint, t1.ensemble, t2.idpoint, t2.ensemble)
mais comme t1.idpoint = t2.idpoint, chaque entrée de cette table correspond à 
un point et à un couple d'ensembles qui contiennent ce point (ce
couple peut être deux fois le même ensemble et on retrouve deux fois la même
entrée en échangeant t1.idensemble et t2.idensemble).
On peut écrire la requête plus lisiblement que dans l'exemple précédent
en utilisant l'opérateur IN (qui n'est pas explicitement au programme).
SELECT x,y
FROM POINTS JOIN MEMBRE ON id = idpoint
WHERE idensemble = i AND idpoint IN
(SELECT idpoint
FROM MEMBRE
WHERE idensemble = j)