X/ENS Informatique B (MP/PC) 2016

Thème de l'épreuve Structure union-find et coupure minimale
Principaux outils utilisés programmation impérative

Corrigé

(c'est payant, sauf le début): - - - - - - - - - - - - - - - - - - -

Extrait gratuit du corrigé

(télécharger le PDF)
           

Énoncé complet

(télécharger le PDF)
                             

Énoncé obtenu par reconnaissance optique des caractères


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

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



X/ENS Informatique B (MP/PC) 2016 -- Corrigé
Ce corrigé est proposé par Vincent Puyhaubert (Professeur en CPGE) ; il a été
relu par Cyril Ravat (Professeur en CPGE) et Julien Dumont (Professeur en CPGE).

Dans cette épreuve, on s'intéresse au problème de la coupe minimale, présenté
sous la forme d'un problème de répartition d'individus par affinités. Plus 
précisément, il s'agit de répartir un ensemble de n personnes en deux groupes 
de manière
à minimiser le nombre de liens d'amitiés entre membres de groupes opposés. Il 
est
composé de quatre parties. La troisième partie utilise les fonctions des deux 
parties
qui la précèdent, mais on peut très bien la traiter sans avoir réussi à 
implémenter les
fonctions en question.
· La première partie présente une notion de réseau social et demande l'écriture
de fonctions pour manipuler cette structure de données. Elle est utilisée pour
modéliser les liens d'amitiés entre les individus. Sous des termes imagés, il 
s'agit
ni plus ni moins d'algorithmique de graphes non orientés, et les questions sont
relativement élémentaires.
· La deuxième partie implémente une structure pour représenter une partition
de l'ensemble [[ 1 ; n ]]. Il s'agit d'une implémentation bien connue qui porte 
le
nom d'union-find. L'énoncé l'utilise pour modéliser les groupes d'amis au sein
du réseau social. Les fonctions demandées permettent de déterminer si des
individus sont amis et de fusionner des groupes d'amis.
· La troisième partie utilise les deux structures de données précédentes pour 
écrire
un algorithme qui calcule une coupe du réseau social, avec une forte probabilité
que celle-ci soit minimale. L'énoncé décrit lui-même l'algorithme, si bien qu'il
ne s'agit plus que de traduire le pseudo-code en langage Python.
· Enfin, la dernière partie, totalement indépendante du reste du sujet, pose
quelques questions sur les bases de données.
Comme bien souvent, cette épreuve est de grande qualité. La problématique est
intéressante et présentée de façon simple et attrayante. L'énoncé est clair et 
précis,
la difficulté des questions est très bien dosée pour une épreuve de deux 
heures. Il s'agit
donc d'un sujet à traiter en priorité parmi toutes les épreuves d'informatique 
qui
peuvent tomber aux différents concours.

Indications
3 Il suffit de tester si la paire en question est égale à [i,j] ou [j,i].
4 Passer en revue tous les liens du réseau pour déterminer si l'un d'entre eux 
est
un lien entre i et j.
5 Il suffit d'ajouter une liste [i,j] au deuxième élément de la liste reseau.
6 Éviter d'utiliser sontAmis. Pour une complexité efficace, passer en revue 
tous les
liens du réseau et vérifier si l'un des individus du lien est i.
8 Dans une partition en singletons, chaque individu est son propre représentant.
9 On pourra utiliser la programmation récursive, en sachant que le représentant
d'un élément est lui-même s'il est son propre parent, sinon le représentant de 
son
père. La recherche peut également être rédigée en style impératif à l'aide d'une
variable qui prend les valeurs des parents successifs de l'individu de départ.
11 Considérer les instructions fusion(parent,0,i) pour i allant de 1 à n - 1.
12 En récursif, il suffit de rajouter une modification de tableau au programme 
de la
question 9. En impératif, on pourra commencer par établir la liste des parents
successifs de l'individu de départ, puis modifier le parent de chacun d'entre 
eux
une fois la liste terminée.
13 Utiliser une liste de n listes initialement vides (une pour chaque 
individu). Ajouter
alors l'indice de chaque individu dans la liste associée à son représentant, 
puis
éliminer les listes vides.
14 L'algorithme est entièrement décrit par l'énoncé. On pourra prévoir pour 
simplifier l'écriture une fonction d'échange d'éléments dans une liste, une 
fonction pour
faire les fusions exigées à l'étape 5 de l'énoncé, et utiliser des variables 
locales
mises à jour régulièrement pour compter le nombre de groupes et le nombre de
liens non marqués.
15 Pour chaque lien, comparer les représentants des deux individus du lien et 
incrémenter un compteur en conséquence.
17 Utiliser une jointure entre les deux tables basée sur la correspondance 
entre id
et id2.
18 On peut utiliser une jointure entre une sélection du type de celle de la 
question
16 et la table LIENS.

I. Réseaux sociaux
1 Proposons les représentations reseauA et reseauB pour les réseaux A et B :
reseauA = [5, [[0,1], [0,2], [0,3], [1,2], [2,3]]]
reseauB = [5, [[0,1], [1,2], [1,3], [2,3], [2,4], [3,4]]]
Dans ces deux représentations, les listes représentant les liens d'amitiés sont
triées par ordre lexicographique croissant. C'est essentiellement pour vérifier
que l'on n'oublie personne, mais l'énoncé précise clairement que ce n'est pas
une obligation. Ainsi, n'importe quel ordre serait accepté dans la liste et dans
chaque couple (les listes [0,1] et [1,0] représentent le même lien).
2 S'il n'y a aucune relation d'amitié dans le réseau, c'est que la seconde 
liste de la
représentation est vide. Il suffit donc d'écrire la fonction suivante.
def creerReseauVide(n):
return [n,[]]
3 Cette fonction peut s'écrire de la façon suivante :
def estUnLienEntre(paire,i,j):
return (paire[0] == i and paire[1] == j) or \
(paire[0] == j and paire[1] == i)
Le test peut s'écrire un peu plus rapidement à l'aide de l'opérateur ==
qui fonctionne aussi pour tester l'égalité de deux listes. On peut donc écrire
def estUnLienEntre(paire,i,j):
return (paire == [i,j]) or (paire == [j,i])
Les paragraphes de la forme
if un_test:
return True
else:
return False
sont maladroits et à proscrire. Il n'y a rien d'incorrect en terme de syntaxe,
mais cela revient au même d'écrire en une ligne return un_test .
4 Il suffit de passer en revue toutes les paires de la seconde liste du réseau 
et de
vérifier s'il s'agit d'un lien entre i et j. Si c'est le cas au moins une fois, 
on termine
immédiatement l'exécution en renvoyant True, sinon on renvoie False à la fin de 
la
boucle. Cela peut s'écrire de la manière suivante :
def sontAmis(reseau,i,j):
for lien in reseau[1]:
if estUnLienEntre(lien,i,j):
return True
return False
Dans le pire des cas, il n'y a pas de lien entre i et j et il faut alors 
parcourir
toute la liste reseau[1] avant de conclure. Chaque étape de la boucle nécessite 
une
application de estUnLienEntre qui s'exécute en temps constant. Par conséquent,
La fonction sontAmis s'exécute en O(m) opérations élémentaires.

La syntaxe « x in L » s'évalue en un booléen qui vaut True si et seulement
si l'élément x apparaît dans la liste L. On aurait pu envisager d'écrire
def sontAmis(reseau,i,j):
return ([i,j] in reseau[1]) or ([j,i] in reseau[1])
ce qui serait plus court et plus élégant en terme d'écriture. Toutefois, il y a 
de
grandes chances que cette écriture soit sanctionnée car ne respectant pas les
conditions de l'énoncé (qui donne une liste précise des intructions utilisables
sur les listes et interdit les autres).
5 Pour écrire cette procédure, on commence par vérifier s'il existe un lien 
entre i
et j. Si ce n'est pas le cas, il suffit d'ajouter [i,j] à la liste reseau[1].
def declareAmis(reseau,i,j):
if not sontAmis(reseau,i,j):
reseau[1].append([i,j])
L'utilisation de sontAmis nécessite dans le pire cas O(m) opérations 
élémentaires.
Le test est éventuellement suivi de l'ajout d'un élément dans une liste qui est 
une
opération de coût constant. Au final,
La procédure declareAmis s'exécute en O(m) opérations élémentaires.
6 L'utilisation de la fonction sontAmis pour chaque valeur de j dans [[ 1 ; n 
]] est
coûteuse car elle nécessite de parcourir plusieurs fois la même liste 
reseau[1]. La solution suivante est plus efficace car elle ne nécessite qu'un 
parcours :
· pour chaque élément de reseau[1], on cherche si l'un des deux éléments de la
liste est i ;
· lorsque c'est le cas, on ajoute l'autre élément à une liste initialement vide.
Cette fonction nécessite qu'il n'y ait qu'une seule liste représentant chaque
lien d'amitié dans reseau[1], ce qui semble être une hypothèse implicite
de l'énoncé. Sinon, on court le risque d'avoir des occurrences multiples d'un
même ami j dans la liste renvoyée.
La fonction décrite ci-dessus s'écrit de la façon suivante :
def listeDesAmisDe(reseau,i):
amis=[]
for lien in reseau[1]:
if lien[0]==i:
amis.append(l[1])
elif lien[1]==i:
amis.append(l[0])
return amis
Cette fonction parcourt une fois la liste reseau[1] et exécute pour chacun 
d'entre
eux au plus quatre opérations élémentaires. Par suite,
La fonction listeDesAmisDe s'exécute en O(m) opérations élémentaires.
Si l'on utilise la solution décrite initialement (vers laquelle les questions 
précédentes ont tendance à orienter le candidat), on utilise n - 1 fois la 
fonction
sontAmis de coût O(m). On obtient une solution de coût O(m n), ce qui est
moins efficace que la solution proposée et serait certainement sanctionné.