X/ENS Informatique B MP-PC 2016

ECOLE POLYTECHNIQUE -- ECOLES NORMALES SUPERIEURES
ECOLE SUPERIEURE DE PHYSIQUE ET DE CHIMIE INDUSTRIELLES

CONCOURS D'ADMISSION 2016

FILIERES

MP HORS SPECIALITE INFO
FILIERES PC

COMPOSITION D'INFORMATIQUE ­ B ­ (XELCR)
(Duree : 2 heures)
L'utilisation des calculatrices n'est pas autorisee pour cette epreuve.
Le langage de programmation sera obligatoirement Python.

Ce sujet est decoupe en deux parties totalement independantes toutes deux 
portant sur
l'etude de reseaux sociaux : la premiere porte sur de la programmation en 
Python ; la seconde
porte sur l'interrogation de base de donnees a l'aide de requetes en SQL.

A - Programmation en Python
Notations.

On designera par [[n]] l'ensemble des entiers de 0 a n - 1 : [[n]] = {0, . . . 
, n - 1}.

Objectif. Le but de cette partie est de regrouper des personnes par affinite 
dans un reseau
social. Pour cela, on cherche a repartir les personnes en deux groupes de sorte 
a minimiser le
nombre de liens d'amitie entre les deux groupes. Une telle partition s'appelle 
une coupe minimale
du reseau.

Complexite. La complexite, ou le temps d'execution, d'un programme P (fonction 
ou
procedure) est le nombre d'operations elementaires (addition, multiplication, 
affectation, test,
etc...) necessaires a l'execution de P . Lorsque cette complexite depend de 
plusieurs parametres
n et m, on dira que P a une complexite en O((n, m)), lorsqu'il existe trois 
constantes A, n0
et m0 telles que la complexite de P soit inferieure ou egale a A × (n, m), pour 
tout n > n0 et
m > m0 .
1

Lorsqu'il est demande de donner une certaine complexite, le candidat devra 
justifier cette
derniere si elle ne se deduit pas directement de la lecture du code.

Implementation.

Dans ce sujet, nous adopterons la syntaxe du langage Python.

On rappelle qu'en Python, on dispose des operations suivantes, qui ont toutes 
une complexite
constante (car en Python, les listes sont en fait des tableaux de taille 
dynamique) :
· [] cree une liste vide (c.-a-d. ne contenant aucun element)
· [x]*n qui cree une liste (ou un tableau) a n elements contenant tous la 
valeur contenue
dans x. Par exemple, [1]*3 renvoie le tableau (ou la liste) [1,1,1] a 3 cases 
contenant
toutes la meme valeur 1.
· len(liste) renvoie la longueur de la liste liste
· liste[i] designe le (i + 1)-eme element de la liste liste s'il existe et 
produit une erreur
sinon (noter que le premier element de la liste est liste[0]).
· liste.append(x) ajoute le contenu de x a la fin de la liste liste qui 
s'allonge ainsi
d'un element. Par exemple, apres l'execution de la suite d'instructions " liste 
= [];
liste.append(2); liste.append([1,3]);", la variable liste a pour valeur la liste
[2, [1, 3]]. Si ensuite on fait l'instruction liste[1].append([7,5]);, la 
variable
liste a pour valeur la liste [2, [1, 3, [7,5]]].
· liste.pop() renvoie la valeur du dernier element de la liste liste et 
l'elimine de
la liste. Ainsi, apres l'execution de la suite d'instructions " listeA = 
[1,[2,3]];
listeB = listeA.pop(); c = listeB.pop(); ", les trois variables listeA, listeB 
et
c ont pour valeurs respectives [1], [2] et 3.
· random.randint(a,b) renvoie un entier tire (pseudo)aleatoirement et 
uniformement
dans l'ensemble {a, a + 1, . . . , b - 1, b}.
· True et False sont les deux valeurs booleennes Vrai et Faux.
Important : L'usage de toute autre fonction sur les listes telle que 
liste.insert(i,x),
liste.remove(x), liste.index(x), ou encore liste.sort(x) est rigoureusement 
interdit
(ces fonctions devront etre programmees explicitement si necessaire).
Dans la suite, nous distinguerons fonction et procedure : les fonctions 
renvoient une valeur
(un entier, une liste,...) tandis que les procedures ne renvoient aucune valeur.
Nous attacherons la plus grande importance a la lisibilite du code produit par 
les candidats ;
aussi, nous encourageons les candidats a introduire des procedures ou fonctions 
intermediaires
lorsque cela simplifie l'ecriture.

Partie I. Reseaux sociaux
Structure de donnees. Nous supposerons que les individus sont numerotes de 0 a 
n - 1 ou
n est le nombre total d'individus. Nous representerons chaque lien d'amitie 
entre deux individus
i et j par une liste contenant leurs deux numeros dans un ordre quelconque, 
c.-a-d. par la liste
[i,j] ou par la liste [j,i] indifferemment.

2

Un reseau social R entre n individus sera represente par une liste reseau a 
deux elements
ou :
· reseau[0] = n contient le nombre d'individus appartenant au reseau
· reseau[1] = la liste non-ordonnee (et potentiellement vide) des liens 
d'amitie declares
entre les individus
La figure 1 donne l'exemple d'un reseau social et d'une representation possible 
sous la forme de
liste. Chaque lien d'amitie entre deux personnes est represente par un trait 
entre elles.
0

2

4

6

1

3

5

7

reseau = [ 8,
[ [0,1], [1,3], [3,2], [2,0], [0,3], [2,1], [4,5],
[5,7], [7,6], [6,4], [7,4], [6,5], [2,4], [5,3] ]
]
Figure 1 ­ Un reseau a 8 individus ayant 14 liens d'amitie declares et une de 
ses representations
possibles en memoire sous forme d'une liste [ Nombre d'individus, liste des 
liens d'amitie ].
Question 1. Donner une representation sous forme de listes pour chacun des deux 
reseaux
sociaux ci-dessous :
0

1

2

2
3

0
4

1

4
3

Reseau A

Reseau B

Question 2. Ecrire une fonction creerReseauVide(n) qui cree, initialise et 
renvoie la
representation sous forme de liste du reseau a n individus n'ayant aucun lien 
d'amitie declare
entre eux.
Question 3. Ecrire une fonction estUnLienEntre(paire,i,j) ou paire est une 
liste a deux
elements et i et j sont deux entiers, et qui renvoie True si les deux elements 
contenus dans
paire sont i et j dans un ordre quelconque ; et renvoie False sinon.
Question 4. Ecrire une fonction sontAmis(reseau,i,j) qui renvoie True s'il 
existe un lien
d'amitie entre les individus i et j dans le reseau reseau ; et renvoie False 
sinon.
Quelle est la complexite en temps de votre fonction dans le pire cas en 
fonction du nombre
m de liens d'amitie declares dans le reseau ?
Question 5. Ecrire une procedure declareAmis(reseau,i,j) qui modifie le reseau 
reseau
pour y ajouter le lien d'amitie entre les individus i et j si ce lien n'y 
figure pas deja.

3

Quelle est la complexite en temps de votre procedure dans le pire cas en 
fonction du nombre
m de liens d'amitie declares dans le reseau ?
Question 6. Ecrire une fonction listeDesAmisDe(reseau,i) qui renvoie la liste 
des amis de
i dans le reseau reseau.
Quelle est la complexite en temps de votre fonction dans le pire cas en 
fonction du nombre
m de liens d'amitie declares dans le reseau ?

Partie II. Partitions
Une partition en k groupes d'un ensemble A a n elements consiste en k 
sous-ensembles
disjoints non-vides A1 , . . . , Ak de A dont l'union est A, c.-a-d. tels que 
A1  · · ·  Ak = A
et pour tout i 6= j, Ai  Aj = . Par exemple A1 = {1, 3}, A2 = {0, 4, 5}, A3 = 
{2} est une
partition en trois groupes de A = [[6]]. Dans cette partie, nous implementons 
une structure de
donnees tres efficace pour coder des partitions de [[n]].
Le principe de cette structure de donnees est que les elements de chaque groupe 
sont structures par une relation filiale : chaque element a un (unique) parent 
choisi dans le groupe et
l'unique element du groupe qui est son propre parent est appele le representant 
du groupe. On
s'assure par construction que chaque element i du groupe a bien pour ancetre le 
representant
du groupe, c.-a-d. que le representant du groupe est bien le parent du parent 
du parent etc.
(autant de fois que necessaire) du parent de l'element i. La relation filiale 
est symbolisee par
une fleche allant de l'enfant au parent dans la figure 2 qui presente un 
exemple de cette structure
de donnees. Dans l'exemple de cette figure, 14 a pour parent 11 qui a pour 
parent 1 qui a pour
parent 9 qui est son propre parent. Ainsi, 9 est le representant du groupe 
auquel appartiennent
14, 11, 1 et 9. Notons que ce groupe contient egalement 8, 13 et 15.
A noter que la representation n'est pas unique (si l'on choisit un autre 
representant pour un
groupe et une autre relation filiale, on aura une autre representation du 
groupe).

9
15

3

13

1
8

4
11

10
2

12

5
7

6
0

14

Figure 2 ­ Une representation filiale de la partition suivante de [[16]] en 
quatre groupes :
{1, 8, 9, 11, 13, 14, 15}, {2, 3, 4, 12}, {10} et {0, 5, 6, 7} dont les 
representants respectifs sont 9, 3,
10 et 5.
Pour coder cette structure, on utilise un tableau parent a n elements ou la 
case parent[i]
contient le numero du parent de i. Par exemple, les valeurs du tableau parent 
encodant la
representation filiale donnee dans la figure 2 sont :

4

i:
parent[i] :

0
6

1
9

2
3

3
3

4
3

5
5

6
5

7
5

8
1

9
9

10
10

11
1

12
4

13
9

14
11

15
9

Question 7. Donner les valeurs du tableau parent encodant les representations 
filiales des
deux partitions de [[10]] ci-dessous, et preciser les representants de chaque 
groupe :
5
0

7

4
8

1
6

3

9

2

1

9

8

Representation filiale A

7
4

5

3
0

6

2

Representation filiale B

Initialement, chaque element de [[n]] est son propre representant et la 
partition initiale consiste
en n groupes contenant chacun un individu. Ainsi, initialement, parent[i] = i 
pour tout i  [[n]].
Question 8. Ecrire une fonction creerPartitionEnSingletons(n) qui cree et 
renvoie un
tableau parent a n elements dont les valeurs sont initialisees de sorte a 
encoder la partition de
[[n]] en n groupes d'un seul element.
Nous sommes interesses par deux operations sur les partitions :
· Determiner si deux elements appartiennent au meme groupe dans la partition.
· Fusionner deux groupes pour n'en faire plus qu'un. Par exemple, la fusion des 
groupes
A1 = {1, 3} et A3 = {2} dans la partition de [[6]] donnee en exemple au tout 
debut de
cette partie donnera la partition en deux groupes A2 = {0, 4, 5} et A4 ou A4 = 
A1  A3 =
{1, 2, 3}.
Question 9. Ecrire une fonction representant(parent,i) qui utilise le tableau 
parent pour
trouver et renvoyer l'indice du representant du groupe auquel appartient i dans 
la partition
encodee par le tableau parent.
Quelle est la complexite dans le pire cas de votre fonction en fonction du 
nombre total n
d'elements ? Donnez un exemple de tableau parent a n elements qui atteigne 
cette complexite
dans le pire cas.
Pour realiser la fusion de deux groupes designes par l'un de leurs elements i 
et j respectivement, on applique l'algorithme suivant :
1. Calculer les representants p et q des deux groupes contenant i et j 
respectivement.
2. Faire parent[p] = q.
La figure 3 presente la structure filiale obtenue apres la fusion des groupes 
contenant respectivement 6 et 14 de la figure 2.
Question 10. Ecrire une procedure fusion(parent,i,j) qui modifie le tableau 
parent pour
fusionner les deux groupes contenant i et j respectivement.
5

9
15

3

13

1
8

5
11

7

14

4
6

10
2

12

0

Figure 3 ­ Representation filiale obtenue apres la fusion des groupes contenant 
respectivement
6 et 14 de la figure 2.
Pour l'instant, la structure de donnees n'est pas tres efficace comme le montre 
la question
suivante.
Question 11. Proposer une suite de (n - 1) fusions dont l'execution a partir de 
la partition en
n singletons de [[n]], necessite de l'ordre de n2 operations elementaires.
Pour remedier a cette mauvaise performance, une astuce consiste a compresser la 
relation filiale apres chaque appel a la fonction representant(parent,i). 
L'operation de compression consiste a faire la chose suivante : si p est le 
resultat de l'appel a la fonction
representant(parent,i), modifier le tableau parent de facon a ce que chaque 
ancetre (c.a-d. parent de parent . . . de parent) de i, i y compris, ait pour 
parent direct p. Noter bien
que meme si un appel a representant(parent,i) renvoie le representant de i elle 
modifie
egalement le tableau parent. Si l'on reprend l'exemple de la figure 2, le 
resultat de l'appel
representant(parent,14) est 9, que l'on a calcule en remontant les ancetres 
successifs de 14 :
11, 1 puis 9. L'operation de compression consiste alors a donner la valeur 9 
aux cases d'indices
14, 11, et 1 du tableau parent. La structure filiale obtenue apres l'operation 
de compression
menee depuis 14 est illustree dans la figure 4.

9
15

13

1
8

3
11

14

4
12

10
2

5
7

6
0

Figure 4 ­ Resultat de la compression depuis 14 dans la representation filiale 
de la figure 2.
Question 12. Modifier votre fonction representant(parent,i) pour qu'elle 
modifie le tableau
parent pour faire pointer directement tous les ancetres de i vers le 
representant de i une fois
qu'il a ete trouve.
En quoi cette optimisation de la structure filiale peut-elle etre consideree 
comme "gratuite"
du point de vue de la complexite ?

6

Afin d'afficher de maniere lisible la partition codee par un tableau parent, on 
souhaite
calculer a partir du tableau parent la liste des listes des elements des 
differents groupes. Une
sortie possible pour le tableau parent correspondant a la figure 2 serait :
[ [
[
[
[

15, 8, 1, 9, 11, 13, 14 ],
4, 3, 2, 12 ],
7, 5, 6, 0 ],
10 ] ]

Question 13. Ecrire une fonction listeDesGroupes(parent) qui renvoie la liste 
des differents
groupes codes par le tableau parent sous la forme d'une liste des listes des 
elements des differents
groupes.

Partie III. Algorithme randomise pour la coupe minimum
Revenons a present a notre objectif principal : Trouver une partition des 
individus d'un
reseau social en deux groupes qui minimise le nombre de liens d'amities entre 
les deux groupes.
Pour resoudre ce probleme nous allons utiliser l'algorithme randomise suivant :
Entree : un reseau social a n individus
1. Creer une partition P en n singletons de [[n]]
2. Initialement aucun lien d'amitie n'est marque
3. Tant que la partition P contient au moins trois groupes et qu'il reste des 
liens d'amitie
non-marques dans le reseau faire :
(a) Choisir un lien uniformement au hasard parmi les liens non-marques du 
reseau,
notons-le [i,j].
(b) Si i et j n'appartiennent pas au meme groupe dans la partition P , 
fusionner les deux
groupes correspondants
(c) Marquer le lien [i,j].
4. Si P contient k > 3 groupes, faire k - 1 fusions pour obtenir deux groupes.
5. Renvoyer la partition P .
La figure 5 presente une execution possible de cet algorithme randomise sur le 
reseau de la
figure 1.
Question 14. Ecrire une fonction coupeMinimumRandomisee(reseau) qui renvoie le 
tableau
parent correspondant a la partition calculee par l'algorithme ci-dessus.
Indication. Au lieu de marquer explicitement les liens deja vus, on pourra 
avantageusement les
positionner a la fin de la liste non-ordonnee des liens du reseau et ainsi 
pouvoir tirer simplement
les liens au hasard parmi ceux places au debut de la liste.

7

Étape 0

Étape 1

0

2

4

6

1

3

5

7

1

2

4

6

3

5

7

0

Étape 2
1

2

0
3

Étape 3
6

4

1

2

0

5

7

3

Étape 4
1

2

3

4
7

5

Étape 6
1

2

0

3

6

7

6

7

5

Étape 5
6

0

4

1

2

0

3

4

5

Résultat final

4
6

7

5

1

2

0

3

4
6

7

5

Figure 5 ­ Une execution de l'algorithme randomise sur le reseau de la figure 1 
ou les liens
selectionnes aleatoirement sont dans l'ordre : [2,1], [4,5], [6,5], [0,3], 
[2,0], [3,2] et
[5,7]. Les liens representes en noir epais sont les liens selectionnes au 
hasard a l'etape courante ;
les liens epais et grises sont les liens marques par l'algorithme ; les ronds 
representent la partition
a l'etape courante.

8

Quelle est la complexite de votre procedure en fonction de n, m et (n), ou m 
est le nombre
de liens d'amitie declares dans le reseau et ou (n) designe la complexite d'un 
appel a la fonction
representant ?
Question 15. Ecrire une fonction tailleCoupe(reseau, parent) qui calcule le 
nombre de
liens entre les differents groupes de la partition representee par parent dans 
le reseau reseau.
On peut demontrer que cet algorithme renvoie une coupe de taille minimum avec 
une probabilite superieure a 1/n, ce qui fait que la meilleure parmi n 
executions independantes de cet
algorithme est effectivement minimum avec probabilite superieure a 1/e  
0.36787....
La structure de donnees filiale avec compression pour les partitions est 
particulierement
efficace aussi bien en pratique qu'en theorie. En effet, la complexite de k 
operations est de
O(k(k)) operations elementaires ou (k) est l'inverse de la fonction 
d'Ackermann, une fonction
qui croit extremement lentement vers l'infini (par exemple (1080 ) = 5).

B - Programmation SQL
Une representation simplifiee, reduite a deux tables, de la base de donnees 
d'un reseau social
est donnee dans la figure 6.
LIENS

INDIVIDUS
id
1
2
..
.

nom
Potter
Granger
..
.

prenom
Harry
Hermione
..
.

id1
1
2
..
.

id2
2
1
..
.

Figure 6 ­ Schema de la base de donnees du reseau social
La table INDIVIDUS repertorie les individus et contient les colonnes
· id (cle primaire), un entier identifiant chaque individu ;
· nom, une chaine de caracteres donnant le nom de famille de l'individu ;
· prenom, une chaine de caracteres donnant le prenom de l'individu.
La table LIENS repertorie les liens d'amities entre individus et contient les 
colonnes
· id1, entier identifiant le premier individu du lien d'amitie ;
· id2, entier identifiant le second individu du lien d'amitie.

9

On supposera par ailleurs que pour tout couple (x,y) dans la table LIENS, le 
couple (y,x) est
egalement present dans la table (contrairement a la partie precedente de cet 
enonce).
Question 16. Ecrire une requete SQL qui renvoie les identifiants des amis de 
l'individu d'identifiant x.
Question 17. Ecrire une requete SQL qui renvoie les (noms,prenoms) des amis de 
l'individu
d'identifiant x.
Question 18. Ecrire une requete SQL qui renvoie les identifiants des individus 
qui sont amis
avec au moins un ami de l'individu d'identifiant x.

10