Banques MP et MPI inter-ENS – Session 2025

Rapport relatif à l’épreuve orale d’informatique

— Épreuve commune à toutes les ENS

— Coefficients (en pourcentage du total des points de chaque concours) :

École MP - Info MPI - Math MPI - Info Info

Paris 15% 16,7% 22,2% N.A.
Lyon 10,8% 10,4% 14,1% 14,1%
Paris-Saclay 23,1% 12,8% 12,8% N.A.
Rennes 23,1% N.A. 13,9% N.A.

— Membres du jury :
— Alexandre Debant
— Romain Demangeon
— Jérémy Dubut
— Brice Minaud
— Hugo Paquet
— André Schrottenloher
— Pierre Senellart

1
 L’épreuve orale d’informatique fondamentale décrite dans ce rapport est commune à toutes les Écoles
normales supérieures.
Cette année, le jury a interrogé :
— 104 candidat·e·s pour la filière MP. Les notes données s’échelonnent entre 4.8 et 20, avec une
médiane à 12.6, une moyenne à 12.65 et un écart-type de 2.84. La figure 1 présente l’histogramme
complet des notes.
— 149 candidat·e·s pour la filière MPI. Les notes données s’échelonnent entre 5 et 20, avec une
médiane à 14, une moyenne à 13.37 et un écart-type de 3.15. (La différence de moyenne avec la
filière MP est dûe davantage à une harmonisation avec des options différentes, qu’à une différence
de niveau.) La figure 2 présente l’histogramme complet des notes.

20

15

10

4 6 8 10 12 14 16 18 20

Figure 1 – Histogramme des notes de l’épreuve (filière MP). La colonne positionnée entre x et x + 1
comptabilise les notes comprises entre x exclus et x + 1 inclus.

20

15

10

0
4 6 8 10 12 14 16 18 20

Figure 2 – Histogramme des notes de l’épreuve (filière MPI). La colonne positionnée entre x et x + 1
comptabilise les notes comprises entre x exclu et x + 1 inclus.

2
 Après avoir reçu un sujet, les candidat·e·s disposent de 30 minutes de préparation, suivies de 28 minutes
d’interrogation devant un des examinateurs. En effet, deux minutes sont utilisées par l’examinateur pour
aller chercher la/le candidat·e en salle de préparation. Nous rappelons également que jusqu’à quatre
candidat·e·s peuvent passer l’épreuve à la suite sur le même sujet, auquel cas la première/le premier
d’entre eux est invité·e à patienter 30 minutes dans la salle de préparation à l’issue de son oral, afin de
garantir la confidentialité du sujet.
Le jury a proposé 20 sujets originaux (10 pour le concours MP et 10 pour le concours MPI), dont la
liste est donnée en annexe de ce document. Entre 12 et 16 candidat·e·s en moyenne ont été interrogé·e·s
sur chaque sujet.
Comme il a été rappelé en préambule des sujets distribués :
Le but de cette épreuve est d’évaluer la progression des candidates et candidats dans les
questions, mais aussi la qualité de leur exposé des solutions, ainsi que l’autonomie dont elles
ou ils font preuve pendant l’oral.
Chaque sujet débute par un énoncé qui présente un problème d’informatique et introduit ses notations,
puis comporte des questions de difficulté globalement croissante. Ainsi, les premières questions visent à
aider à la compréhension du sujet, et permettent aux candidat·e·s de s’approprier les définitions qui ont
été données. Les dernières questions d’un sujet sont souvent des questions d’ouverture plus difficiles. Pour
la plupart des sujets donnés, il n’est pas attendu que les candidat·e·s traitent l’intégralité des questions.
Les sujets proposés portent sur des thèmes variés de science informatique : langages, graphes, logique,
etc., en lien avec les programmes respectifs des filières MP et MPI. Ils nécessitent de s’approprier des
concepts nouveaux, démontrer des résultats théoriques et construire des solutions techniques telles que
des algorithmes. Bien que l’épreuve mette l’accent sur les concepts théoriques de l’informatique, on veille
à garder à l’esprit le sens des objets que l’on étudie, et un certain sens pratique (par exemple dans la
conception d’algorithmes ou l’estimation asymptotique de leur complexité) est apprécié.
Le jury tient à féliciter les candidates et candidats qui ont pour la plupart démontré des acquis très
solides, et fait preuve d’idées excellentes malgré les contraintes de temps inhérentes à l’épreuve. Même
celles et ceux ayant obtenu de moins bonnes notes ont montré des qualités certaines. En particulier, la
plupart des candidat·e·s affichent une bonne maı̂trise des concepts mathématiques essentiels (induction,
disjonction de cas) ainsi qu’une bonne initiative (par exemple le fait de tester un algorithme sur un petit
exemple avant d’en déduire le cas général).
Il est usuel que le jury engage une discussion sur certaines questions afin de guider les candidat·e·s
dans leur résolution du problème. Une attitude constructive et positive est appréciée lors de ces échanges.
Le jury adresse les conseils suivants aux futur·e·s candidat·e·s.

Concours et autres voies d’accès. Les Écoles normales supérieures sont destinées notamment aux
personnes intéressées par la recherche ou l’enseignement. Il peut être utile pour les candidat·e·s de
connaı̂tre les différentes voies d’accès à ces écoles, présentées sur la page suivante :
[Link]

Gestion du temps et de l’espace. Répéter ou recopier l’énoncé lors de l’oral est une perte de temps,
l’examinateur ayant lui aussi le sujet sous les yeux. Le jury déconseille aux candidat·e·s l’effacement du
tableau à la main, qui le rend rapidement illisible pour l’examinateur.

Raisonnements. Afin de démontrer leur maı̂trise du programme d’informatique de leur filière, mais
aussi leur compréhension des nouveaux concepts introduits par le sujet traité, le jury invite les candidat·e·s
à s’assurer de la cohérence de ce qu’ils décrivent.
Par exemple, si le jury demande un identifiant de variable OCaml, celui-ci ne peut pas, par définition,
être un mot clé du langage, ou une application de fonction. Des erreurs d’attention ou de compréhension
peuvent arriver, mais la répétition de ces erreurs de syntaxe ou de typage donne l’impression très négative
que la/le candidat·e n’a pas compris le sujet.
De manière générale, le jury conseille aux candidat·e·s d’utiliser les raisonnements par l’absurde uni-
quement lorsque ceux-ci sont nécessaires, et de préférer les inductions structurelles (par exemple sur un
arbre) aux récurrences sur un critère numérique (hauteur de l’arbre). Celles-ci sont usuellement plus
efficaces et / ou plus adaptées aux objets étudiés.

3
Pédagogie, intuition, formalisme. Si la situation le permet, il est souhaitable de décrire (en général
oralement ou/et par un dessin) une preuve dans les grandes lignes avant de se lancer dans la preuve
formelle. Cela permet à l’examinateur de s’assurer que la/le candidat·e a compris le principe de la preuve.
De même, il est souhaitable de décrire un algorithme dans les grandes lignes avant de se lancer dans
l’écriture du pseudo-code.
Si une question attend une réponse oui/non, il est conseillé d’annoncer cette réponse avant de se lancer
dans la preuve. De même, si une question contient plusieurs résultats à prouver, annoncer lequel sera
prouvé en premier, etc.
Certains sujets demandent d’absorber plusieurs notions nouvelles, parfois au moyen d’un formalisme
assez lourd. On attend alors des candidat·e·s une capacité à s’affranchir du formalisme pour se concentrer
sur la signification des objets. Cependant, si l’examinateur demande des précisions, la/le candidat·e doit
être en mesure de justifier formellement son raisonnement.

Langage OCaml, programmation fonctionnelle. Lorsqu’une fonction OCaml doit être décrite, le
jury suggère fortement aux candidat·e·s de réfléchir en premier abord à la signature de type de la fonction,
qui leur permettra de clarifier leurs idées avant de proposer une implémentation.
Pour la filière MPI, le jury a remarqué que les candidat·e·s voyaient difficilement le parallèle entre
variables libres en logique et dans des expressions OCaml.

Autres remarques.
— Les sujets comportent différents types de difficulté. Certains sujets, comme par exemple la plupart
de ceux qui portent sur les graphes, présentent des variantes d’objets familiers, mais peuvent poser
sur ces objets des questions difficiles. D’autres sujets introduisent au contraire des objets nouveaux,
parfois abstraits, que les candidat·e·s doivent d’abord assimiler, et sur lesquels ils doivent se former
rapidement une intuition ; quitte à ce que le sujet commence parfois par des questions plus simples,
pour aider à cette assimilation. Le jury a eu l’impression que les candidat·e·s sont généralement
plus performants sur le premier type de difficulté que sur le second.
— Le jury a été surpris qu’un certain nombre de candidat·e·s, tout en sachant bien répondre sur
d’autres questions, ne semblait pas maı̂triser l’algorithme du pivot de Gauss, ni arriver à justifier
sa complexité.
— De même, la notion de graphe de flot de contrôle, mentionnée dans le programme de l’option
informatique, ne semblait pas connue des candidat·e·s.
— Certain·e·s candidat·e·s ont eu des difficultés à écrire précisément des arguments simples comme
des récurrences ou raisonnements par l’absurde, en utilisant correctement les quantificateurs, et
en distinguant les implications des équivalences.

4
Annexe : sujets proposés pour la filière MP
Certains sujets sont accompagnés d’ébauches de solution.

5
 Tri externe polyphasé

Nous nous intéressons au problème suivant. Imaginons que nous voulions trier le contenu d’un fichier
dont la taille dépasse très largement la taille de la mémoire vive (où peuvent s’effectuer rapidement les
opérations de tri), mais que nous ayons accès à de la mémoire externe (ici des bandes magnétiques) pour
stocker les résultats des opérations de tri (partiels et finaux). Dans ce contexte, les coûts des opérations
sur la mémoire vive sont négligeables par rapport à celles de lecture, d’écriture et de déplacements de
la tête de lecture sur la mémoire externe.

Nous formalisons le problème de la manière suivante. Supposons que nous voulons trier N éléments.
Supposons que nous avons accès à T mémoires externes supposées infinies. Chaque mémoire externe
a une tête de lecture qui pointe sur une case donnée de la mémoire. Trois opérations peuvent être
effectuées sur cette mémoire :
1. écrire un élément de la mémoire vive sur la case pointée par la tête de lecture,
2. lire l’élément pointé par la tête de lecture pour le mettre sur la mémoire vive et l’enlever de la
mémoire externe,
3. déplacer la tête de lecture d’une case vers la gauche ou vers la droite.
Lorsque nous disons qu’une mémoire est vide, nous entendons que chacune de ses cases sont vides. Nous
représenterons une case vide par le symbole ∅.
Sur la mémoire vive, nous ne pouvons avoir qu’au plus K éléments simultanément. Sur la liste des
éléments sur la mémoire vive, il est possible d’appliquer tout algorithme par exemple pour la trier, y
trouver l’élément maximal, comparer des éléments, etc... En plus des éléments de la liste à trier, la
mémoire vive peut contenir des variables qui ne comptent pas dans le compte des K éléments, et qui
peuvent être utilisés dans les algorithmes à écrire. Toutes les opérations sur la mémoire vive n’entreront
pas dans le calcul de la complexité des algorithmes à écrire.
Le but est d’écrire la liste triée des N éléments sur l’une des mémoires externes.

Question 1. Supposons T = 3, N = 6 et K = 3. Montrez comment passer de la configuration :

1 : vide
2 : vide
3 : 6; 2; 4; 5; 3; 1

à la configuration :

1 : vide
2 : vide
3 : 1; 2; 3; 4; 5; 6

où dans les deux cas, les têtes de lecture sont toutes sur les premières cases des mémoires externes. Nous ne
chercherons pas une solution optimale, mais nous attendrons un calcul précis du nombre d’opérations sur les
mémoires externes.

Question 2. Supposons que T ≥ 3 et que N est un multiple de K, disons N = Kp. Fixons q ≤ p. Supposons
qu’initialement nous sommes dans la configuration suivante :

1 : vide
2 : vide
3 : L0

6
où L0 est la liste non triée des N éléments et où les têtes de lecture sont toutes sur la première case de chaque
mémoire. Décrire un algorithme en 6N opérations (écriture, lecture et déplacement) pour obtenir la configuration
suivante :

1 : B1 ; B2 ; . . . ; Bq
2 : Bq+1 ; Bq+2 ; . . . ; BN/K
3 : vide

où B1 , . . ., BN/K sont des blocs triés de K éléments et où les têtes de lecture sont sur les premières cases de chaque
mémoire.

Solution : Nous commençons par créer une variable X initialisée à 1 sur la mémoire vive. Puis, nous répétons les
étapes suivantes tant que la mémoire 3 n’est pas vide :
1. Nous effectuons K fois les opérations suivantes sur la mémoire 3 :
a) lire l’élément pointée par la tête de lecture,
b) déplacer la tête de lecture vers la droite.
2. Nous trions les K éléments présents sur la mémoire vive.
3. Pour chacun des K éléments dans l’ordre de la liste triée, nous effectuons les opérations suivantes, soit sur
la mémoire 1 si X ≤ q, soit sur la mémoire 2 sinon.
a) écrire l’élément sur la mémoire 1 ou 2,
b) déplacer la tête de lecture vers la droite.
4. ajouter 1 à X.
5. effacer tous les éléments sur la mémoire vive
Nous finissons par déplacer les trois têtes de lecture vers la gauche jusqu’à arriver à la première case de chaque
mémoire externe.
Comptons le nombre d’opérations sur la mémoire externe :
1.a) N lectures
1.b) N déplacements
3.a) N écritures
3.b) N déplacements
+ 2N déplacements pour remettre les têtes de lecture.
Soit un total de 6N opérations.

Question 3. Supposons que T = 4 et que N/K soit une puissance de 2, disons N = K2n avec n > 0. En
partant de la configuration finale de la question précédente avec q = N/2K = 2n−1 , écrivez un algorithme en
6nN opérations afin d’obtenir la configuration suivante (ou toute autre configuration à permutation des mémoires
externes près) :

1:L
2 : vide
3 : vide
4 : vide

où L est la liste triée de tous les éléments et toutes les têtes de lecture pointent vers la première case.

7
Solution : Nous allons effectuer 6N opérations pour aller d’une configuration :

1 : B1i ; B2i ; . . . ; B2i n−i

2 : B2i n−i +1 ; B2i n−i +2 ; . . . ; B2i n+1−i
3 : vide
4 : vide

vers une configuration :

1 : vide
2 : vide
3 : B1i+1 ; B2i+1 ; . . . ; B2i+1
n−i−1

4 : B2i+1 i+1 i+1

n−i−1 +1 ; B2n−i−1 +2 ; . . . ; B2n−i

où les Bjk sont des blocs triés de K2k−1 éléments et les têtes de lectures sont sur les premières cases. Observer
par exemple que la configuration initiale de cette question correspond à la première configuration avec i = 1, et la
configuration finale correspond à la seconde configuration avec i = n + 1 (à permutation près). Pour résoudre la
question, il sera donc suffisant de répéter n fois ces opérations, soit un total de 6nN opérations comme attendu.
Nous allons décrire ces opérations par blocs, c’est-à-dire, que nous allons décrire une suite de 4K · 2i opérations
pour aller de la configuration

1 : ∅ijK ; Bj+1
i
; . . . ; B2i n−i
2 : ∅ijK ; B2i n−i +j+1 ; . . . ; B2i n+1−i
3:L
4 : L′

où L et L′ sont des suites quelconques d’éléments, et les têtes de lectures pointent sur les premières cases non vides
des mémoires 1 et 2 et sur les premières cases vides des mémoires 3 et 4, vers une configuration :

1 : ∅i(j+1)K ; Bj+2
i
; . . . ; B2i n−i
2 : ∅i(j+1)K ; B2i n−i +j+2 ; . . . ; B2i n+1−i
i+1
3 : L; Bj+1
4 : L′
i+1
où Bj+1 est la liste triée obtenue en triant l’union des listes Bj+1
i et B2i n−i +j+1 et où les têtes des lectures sont
placées de la même façon sur les premières case non vides (resp. vides) des mémoires 1 et 2 (resp. 3 et 4). Pour
résoudre le problème précédent, il suffit de répéter ces opérations 2n−i fois (à permutation près, soit 4N opérations
au total), puis de faire revenir toutes les têtes de lecture vers la première case (2N déplacements au total). Soit un
total de 6N opérations comme attendu.
Ces opérations consistent à effectuer une fusion comme dans le tri fusion classique. Précisément, on commence par
créer deux variables entières X1 et X2 initialisées à 1. Nous lisons les mémoires 1 et 2 et déplaçons leurs tête de
lecture vers la droite. Nous répétons les opérations suivantes tant que X1 < K2i−1 ou X2 < K2i−1 :
1. Deux cas possibles :
(a) il n’y a qu’un élément sur la mémoire vive, alors on écrit cet élement sur la mémoire 3
(b) il y a deux élements sur la mémoire vive, alors on écrit le plus grand élément sur la mémoire 3
2. On incrémente de 1 la variable Xl où l est la mémoire de laquelle provient l’élément que l’on vient d’écrire.
3. On déplace la tête de lecture de la mémoire 3 vers la droite.
4. Si Xl < K2i−1 , on lit la mémoire l et bouge sa tête de lecture vers la droite.

8
Chaque itération demande :
1. 1 écriture
2. 0 opération
3. 1 déplacement
4. 1 écriture et 1 déplacement, sauf sur 2 itération (lorsque les deux listes deviennent vides), mais qui sont
compensées par les opérations effectuées initialement.
Nous répétons ces itérations K2i fois, soit un total de 4K · 2i opérations.

Nous avons donc trouvé un premier algorithme de tri externe en O(N log2 (N/K)) opérations sur les mé-
moires externes dans le cas où T = 4. Cet algorithme peut être adapté pour T = 2p en O(N logp (N/K)).
Nous nous intéressons maintenant au cas T = 3.

Question 4. En partant de la même configuration initiale que la question 3, adaptez le cas T = 4 de l’algorithme
au cas T = 3 en effectuant 9nN opérations.

Solution : Nous pouvons adapter l’algorithme pour passer de la configuration :

1 : B1i ; B2i ; . . . ; B2i n−i

2 : B2i n−i +1 ; B2i n−i +2 ; . . . ; B2i n+1−i
3 : vide

vers une configuration :

1 : vide
2 : vide
3 : B1i+1 ; B2i+1 ; . . . ; B2i+1
n−i

avec les changements suivants :

— au lieu d’écrire les blocs triés alternativement sur les mémoires 3 et 4, nous les écrivons tous sur la mémoire
3
— au lieu de faire revenir la tête de lecture de la mémoire 3 vers la première case, nous la faisons revenir au
milieu de la mémoire, c’est-à-dire, sur la première case de B2i+1
n−i−1 +1

Tout ceci se fait en 5N + N/2 opérations. Il faut alors effectuer 3N + N/2 opérations pour obtenir la configuration :

1 : vide
2 : B2i+1 i+1
n−i−1 +1 ; . . . ; B2n−i

3 : B1i+1 ; . . . ; B2i+1
n−i−1

qui consiste à répéter N/2 fois les opérations suivantes :

1. lire la mémoire 3
2. écrire cet élément sur la mémoire 2
3. déplacer les têtes de lecture des mémoires 2 et 3 vers la droite.
soit un total de 4 · N/2 = 2N opérations, puis de faire revenir les têtes de lecture des mémoires 2 et 3 vers la
première case, soit N + N/2 déplacements. Au total, cela requiert 9N opérations. En répétant, ces opérations n
fois comme dans la question précédente (à permutation près), nous obtenons un algorithme en 9nN opérations.

9
 Le problème du cas T = 3 avec une configuration initiale équilibrée est qu’il est nécessaire de copier une
partie du contenu d’une mémoire sur une autre mémoire sans réellement progresser dans la construction
de la liste triée.

Question 5. En partant d’une autre configuration initiale obtenue en question 2 bien choisie, adaptez l’algorithme
de la question 3 de façon à ne faire aucune de ces copies de mémoire. Vous pourrez supposer que N est de la forme
N = KFn pour une suite Fn bien choisie, dans quel cas vous pourriez montrer un algorithme en
n−1
X
3N + 6K Fn−i Fi
i=1

opérations.

Solution : Le problème de la question 3 est que lorsque les mémoires 1 et 2 sont fusionnées, elles sont complètement
vidées au même moment. L’idée est de faire en sorte que après la fusion des mémoires 1 et 2, uniquement la mémoire
1 est vide et la configuration de la mémoire 2 et 3 soit similaire à la configuration des mémoires 1 et 2 avant la fusion.
L’idée est donc de définir une suite croissante (Fn )n∈N telle que si (Fn−1 , Fn , 0) est la configuration avant fusion
(c’est-à-dire, avec Fn−1 blocks triés sur la mémoire 1, Fn sur la mémoire 2, et 0 sur la blocs 3), la configuration
après fusion soit (Fn−2 , Fn−1 , 0) à permutation près, ce qui permettrait d’itérer le processus de fusion. Si on
suppose la suite croissante, après la fusion, la configuration est de la forme (0, Fn − Fn−1 , Fn−1 ). Donc ce principe
fonctionnerait si Fn = Fn−1 + Fn−2 . De plus, à la fin de l’algorithme, nous souhaiterions une configuration (1, 0, 0)
à permutation près, donc que F0 = 0 et F1 = 1. Au total, la bonne suite à choisir est la suite de Fibonacci !
L’algorithme fonctionnerait de la façon suivante en supposant N = KFn avec n > 1. On applique la question 1
avec q = Fn−2 pour obtenir la configuration :

1 : B1 ; B2 ; . . . ; BFn−2
2 : B1′ ; B2′ ; . . . ; BF′ n−1
3 : vide

où tous les blocks sont de taille K et les têtes de lecture sont sur la première case. Après une phase de fusion des
mémoires 1 et 2 et écriture sur la mémoire 3, similaire à la question 2, nous nous retrouvons sur une configuration
de la forme :

1 : vide
2 : ∅KFn−2 ; B1 ; B2 ; . . . ; BFn−3
3 : B1′ ; B2′ ; . . . ; BF′ n−2

où les blocks de la mémoire 2 sont de taille K et ceux de la mémoire 3 sont de taille 2K. On fera en sorte que les
têtes de lecture des mémoire 1 et 3 soient sur la première case alors que celle de la mémoire 2 est sur la première
case de B1 . En analysant plus précisément le nombre d’opérations, il est nécessaire de faire :
— 2Fn−2 lectures sur les mémoires 1 et 2
— 2Fn−2 écritures sur la mémoire 3
— 4Fn−2 déplacements vers la droite sur toutes les mémoires
— 3Fn−2 déplacements vers la gauche sur les mémoires 1 et 3.
Soit un total de 11Fn−2 opérations. Définissons Ci pour 1 ≤ i < n comme (à permutation près) :

1 : B1 ; B2 ; . . . ; BFn−i
2 : ∅KFi−1 Fn−i ; B1′ ; B2′ ; . . . ; BF′ n−(i+1)
3 : vide

10
où les blocks Bi sont de tailles KFi et les blocks Bi′ sont de taille KFi−1 et où les têtes de lecture sont sur les
premières case des mémoires 1 et 3 et sur la première case du block B1′ de la mémoire 2. Observez en particulier
que la seconde configuration ci-dessus correspond à C2 .
En fusionnant les mémoires 1 et 2, et écrivant sur la mémoire 3, nous pouvons aller de la configuration Ci à la
configuration Ci+1 . Cela demande :
— KFn−(i+1) Fi lectures sur la mémoire 1
— KFn−(i+1) Fi déplacements vers la droite sur la mémoire 1
— KFn−(i+1) Fi−1 lectures sur la mémoire 2
— KFn−(i+1) Fi−1 déplacements vers la droite sur la mémoire 2
— KFn−(i−1) Fi−1 déplacements vers la gauche sur la mémoire 2
— KFn−(i+1) Fi+1 écritures sur la mémoire 3
— KFn−(i+1) Fi+1 déplacements vers la droite sur la mémoire 3
— KFn−(i+1) Fi+1 déplacements vers la gauche sur la mémoire 3
Observez en particulier que fusionner un block de la mémoire 1 (de taille KFi ) avec un block de la mémoire 2 (de
taille KFi−1 ) produit bien un block de taille KFi+1 comme souhaité.
Finalement, la configuration Cn−1 est presque la configuration finale, sauf que la tête de lecture de la mémoire 2
n’est pas sur la première case. Il est alors nécessaire de faire KFn−2 déplacements vers la gauche.
Au lieu de faire la somme de toutes ces opérations, nous pouvons observer que ces opérations consistent à opérer
sur des mémoires de la forme :
B1 ; B2 ; . . . ; BFn−i
où les blocks Bi sont de taille KFi . Sur ces mémoires, nous effectuons :
— au moment de l’écriture de cette mémoire :
— KFn−i Fi écritures
— KFn−i Fi déplacements vers la droite
— KFn−i Fi déplacements vers la gauche
— au moment de la fusion avec d’autres mémoires, qui se fait sur deux phases :
— KFn−i Fi lectures
— KFn−i Fi déplacements vers la droite
— KFn−i Fi déplacements vers la gauche (qui se fait uniquement lors de la deuxième phase).
Soit un total de 6KFn−i Fi opérations. A cela s’ajoute la lecture de la mémoire 3 lors de la phase d’initialisation
pour un total de 3N opérations. Comme pour un i tel que 1 ≤ i < n, il y a une unique telle mémoire au cours de
l’algorithme, cela fait un total de :
n−1
X
3N + 6K Fn−i Fi .
i=1

11
 Types à Gabarit

On se place dans un langage de programmation minimal, fonctionnel pur, typé polymorphe qui contient
— des noms, des définitions de fonctions (anonymes et nommées),
— un opérateur de définition récursive d’expressions,
— des définitions récursives de types inductifs :
data D t1 . . . tp = C1 t1 | . . . | Ck Tk
où D est le constructeur de types que l’on définit, ti des variables de types, Ti des types (contenant
potentiellement le constructeur D et les variables tj ), et Ci des constructeurs de termes,
— un opérateur reconnaissance de motif permettant de décomposer les éléments d’un type inductif.
On définit les types inductifs Nat et Liste ainsi :
data Nat = Z | S (Nat).
data Liste A = Nil | Cons A (Liste A)
ainsi on peut définir longueur : Liste A → Nat avec
letrec longueur l = decomposer l :
cas Nil = Z
cas (Cons t q) = S (longueur q)
On note A1 → A2 → · · · → An → B le type d’une fonction n-aire qui prend, dans l’ordre, une entrée
de type A1 , . . . , une entrée de type An et qui produit un résultat de type B.
On identifiera un type avec l’ensemble de ses habitants (des entités qui ont ce type).

On note E[X/Y ] l’expression syntaxique E dans lequel toutes les occurrences de la sous expression Y
sont remplacées par l’expression X.
Si le type inductif D est défini par data D t1 . . . tp = C1 T1 | . . . | Ck Tk
alors, pour n ∈ N, Dn est la n-approximation de D, définie par :
D0 t1 . . . tp = ∅
Dn+1 t1 . . . tp = {C1 x | x ∈ T1′ } ∪ . . . ∪ {Ck x | x ∈ Tk′ }
avec Tj′ = Tj [Dn /D] pour tout j

Question 1. Décrire Natn et Listen A.

Soit S un ensemble de variables de taille, distinctes des noms du langage.

Un gabarit S est donné par la grammaire :
S ::= s | n | S + S | n × S avec n ∈ N et s ∈ S.
On ajoute au langage des types les annotations de gabarits pour les types inductifs, ainsi, si D t1 . . . tp
est un type, alors DS T1 . . . tp est un type, défini comme la S-approximation de D.

Question 2. Donner des définition et des types avec gabarits pour des fonctions calculant la somme de deux
entiers, leur produit et le quotient de la division euclidienne du premier par le deuxième.

Question 3. On suppose qu’on a une fonction moyenne : Nat2i → Nat2j → Nati+j

Donner la définition et le type avec gabarits d’une fonction lisse qui prend en entrée une liste d’entiers et renvoie
la liste des moyennes des éléments consécutifs de cette liste.

12
Question 4. Donner une condition utilisant les types à gabarits pour qu’une fonction définie récursivement soit
terminante.

On ajoute au langage une définition de types coinductifs :

codata D t1 . . . tp = C1 T1 | . . . | Ck Tk .
dans ce cas, D t1 . . . tp est le plus grand type (pour l’inclusion d’ensembles) qui vérifie l’équation
T = {C1 x | x ∈ T1′ } ∪ . . . ∪ {Ck x | x ∈ Tk′ } avec Tj′ = Tj [T /(D t1 . . . tp )] pour tout j

Question 5. Décrire les types suivants :

1. codata Flot A = FCons A (Flot A).

2. codata INat = Z | S INat.
3. codata IListe A = Nil | Cons A (IListe A)
4. data FFlot A = FCons A (FFlot A).

Question 6. Si C est l’ensemble des constructeurs du langage, X l’ensemble des noms du langage, on définit
l’univers U comme unique solution de l’équation
U = C ∪ X ∪ (U → U ) ∪ (U × U )
Décrire U.

Question 7. Soit D défini par codata D t1 . . . tp = C1 T1 | . . . | Ck Tk .

Définir Dn sa n-approximation. Puis décrire les n-approximations des types de la Question 5.

Question 8. Définir tete et queue, deux fonctions permettant de récupérer la tête et la queue d’un flot, et leur
donner des types avec gabarits.

Question 9. On définit ces objets du langage :

letrec zeros = FCons Z zeros
letrec zeros′ = FCons Z (queue zeros′ )
letrec filtre (FCons n1 (FCons n2 q)) = FCons (moyenne n1 n2 ) (filtre q)
letrec fadd (FCons n1 q1 ) (FCons n2 q2 ) = FCons (somme n1 n2 ) (fadd q1 q2 )
f s = fadd (filtre s) (filtre (filtre s))
Sont-ils utilisables ?
En induire une méthode pour définir proprement des objets manipulant des types co-inductifs.

Question 10. Trouver une condition sur les définitions de types pour que limn→∞ Dn = D
et limn→∞ Dn = D.

13
 Déclasser dans les Douze Chemins

On étudie, compte et range des classes d’équivalence de fonctions d’un ensemble fini N à n éléments
dans un ensemble fini X à k éléments.
On s’intéresse à quatre relations d’équivalence pour les fonctions :
— l’égalité, notée DD,
— l’égalité à permutation des éléments de N près, notée U D,
— l’égalité à permutation des éléments de X près, notée DU ,
— l’égalité à permutation des éléments de N et de X près, notée U U .
Lorsqu’on a une égalité à permutation près sur un ensemble, on peut considérer que les éléments de cet
ensemble sont "indistinguables" (Undistinguished ) pour la comparaison des fonctions, ce qui explique
les notations U et D.
En outre, on s’intéresse à trois caractéristiques des fonctions qu’on étudie :
— les fonctions arbitraires (notées A),
— les fonctions injectives (notées I),
— les fonctions surjectives (notées S).
Cela définit 12 (3 × 4) problèmes de dénombrement, appelés douze chemins (twelvefold way), ou douze
problèmes de Gian-Carlo Rota. Par exemple, le problème noté IDU consiste à dénombrer et décrire les
classes d’équivalence de fonctions injectives à permutation de X près.
Quand j ∈ N, on pourra utiliser J1; jK pour désigner {i ∈ N | 1 ≤ i ≤ j}.

Question 1. Dénombrer les classes des problèmes suivants :

1. ADD.
2. IDD
3. IU U
4. SU D

Question 2. Pourquoi la caractéristique bijective n’est-elle pas étudiée ?

Question 3. Les problèmes des douze chemins admettent chacun au moins une représentation naturelle de leurs
classes d’équivalence et un ordre lexicographique sur ces représentations.
Donner de telles représentations et ordres pour les problèmes de la question 1.

Un algorithme de déclassement pour un problème des douze chemins est un algorithme qui prend en
entrée un entier i et renvoie en sortie une représentation de la classe d’équivalence située à la i + 1-ème
place selon l’ordre lexicographique associée à ce problème.

Question 4. Donner des algorithmes de déclassement pour les problèmes de la question 1.

Dans la suite, on s’intéresse uniquement au problème SDU .

Question 5. Donner une relation de récurrence décrivant le dénombrement des fonctions de SDU .

14
 Soit A et B deux ensembles d’entiers naturels, on définit A ≺ B = (min A ≤ min B).
Soit A et B deux ensembles, on note A − B pour {x ∈ A | x ̸∈ B}.
Soit A et 
B deux ensembles d’entiers naturels, on définit :

 A=B

ou A ⊂ B et max A < min (B − A)
A◁B= .

 ou B ⊂ A et min (A − B) < max B

ou min (A − B) < min (B − A)

Question 6. Donner une représentation des classes de SDU , puis un ordre total sur ces classes.

Question 7. Donner les 10 premières fonctions, pour cet ordre, de SDU avec n = 5 et k = 3.

Question 8. Donner un algorithme de déclassement pour SDU .

15
 Partitions et listes

Ce sujet concerne une représentation des partitions de l’ensemble J1, KK := {1, . . . , K}, où K est un
entier supérieur ou égal à 1. On rappelle qu’une partition de J1, KK est un ensemble P = {B1 , . . . , Bn }
où
Sn les Bi sont des sous-ensembles non-vides de J1, KK appelés blocs, disjoints deux à deux et tels que
i=1 Bi = J1, KK.
Si i ∈ J1, KK, on appelle parent de i dans P l’élément minimal du bloc qui contient i, et cet élément
est dénoté parP (i).
On note J1, KKK l’ensemble des listes comprenant K éléments de J1, KK. Pour toute liste s ∈ J1, KKK ,
on écrit s = (s1 , . . . , sK ), où si désigne le i-ème élément de la liste.
On appelle liste K-incrémentale une liste s ∈ J1, KKK qui satisfait les propriétés suivantes pour tout
i ∈ {1, . . . , K} :
— si ≤ i
— si = ssi .
On suppose que l’entier K est fixé pour tout le sujet.

Question 1. Donner un exemple d’une liste s ∈ J1, KKK qui n’est pas K-incrémentale, et donner un exemple de
liste 4-incrémentale.

Solution : Pour une liste non-incrémentale, il faut au minimum K = 2. Les listes (2, 1) et (2, 2) ne sont pas
2-incrémentales.
Les listes 4-incrémentales sont : (1, 1, 1, 1), (1, 1, 1, 4), (1, 1, 3, 1), (1, 1, 3, 3), (1, 1, 3, 4), (1, 2, 1, 1), (1, 2, 1, 2), (1, 2, 1, 4),
(1, 2, 2, 1), (1, 2, 2, 2), (1, 2, 2, 4), (1, 2, 3, 1), (1, 2, 3, 2), (1, 2, 3, 3), (1, 2, 3, 4).

Question 2. Soit P = {B1 , . . . , Bn } une partition de J1, KK. Montrer que la liste (parP (1), . . . , parP (K)) est
K-incrémentale. Définir une bijection entre l’ensemble des listes K-incrémentales et l’ensemble des partitions de
J1, KK.

Solution : On vérifie les deux propriétés pour tout i ∈ J1, KK. Par définition si = parP (i) est l’élément minimal
du bloc de P qui contient i. Donc parP (i) ≤ i.
Par définition, parP (i) est l’élément minimal du bloc qui contient i, et parP (parP (i)) est l’élément minimal du bloc
qui contient parP (i). Puisque parP (i) et i sont dans le même bloc, ces deux éléments sont égaux.
Donc, pour toute partition P , on obtient une liste incrémentale qu’on note liste(P ). Réciproquement, étant donné
une liste incrémentale s, on peut définir une partition part(s) : pour cela on prend la partition qui correspond à la
relation d’équivalence i ∼ j ⇐⇒ si = sj . Plus explicitement, part(s) = {{k | sk = i} | i ∈ J1, KK} \ {∅}.
Il faut montrer que les fonctions liste(−) et part(−) sont inverses.
— Pour toute liste s qui est K-incrémentale, on veut montrer que liste(part(s)) = s. On montre que pour tout
indice i, (liste(part(s)))i = si .
L’élément (liste(part(s)))i est par définition parpart(s) (i), c’est-à-dire l’élément minimal du bloc qui contient i
dans part(s). Par définition, ce bloc est l’ensemble des indices où apparait la valeur si , c’est-à-dire l’ensemble
{j | sj = si }. On sait que ssi = si donc si est un élément du bloc, et c’est forcément le minimum, puisque
pour tout j du bloc on a si = sj ≤ j.
— Pour toute partition P , on veut montrer que part(liste(P )) = P . Deux éléments i, j sont dans le même bloc
de part(liste(P )) ssi (liste(P ))i = (liste(P ))j , c’est-à-dire pari P = parj P ; c’est vrai si et seulement si i et j
sont dans le même bloc de P .

16
Question 3. Montrer que si s est une liste K-incrémentale et i apparait dans s, alors si = i.

Solution : Preuve qui utilise la bijection : puisque si i apparait dans s alors i est un parent dans la partition P qui
correspond à s. Cela signifie que i est l’élément minimal du bloc dans lequel il apparait. En particulier parP (i) = i.
Preuve sans la bijection : si i apparait dans s alors on a sn = i pour un certain n. Donc si = ssn = sn = i.

Un croisement dans une partition P = {B1 , . . . , Bn } de J1, KK est un quadruplet d’entiers a, b, c, d ∈

J1, KK tels que a < b < c < d avec a, c ∈ Bi et b, d ∈ Bj pour i ̸= j. Par exemple, si K = 4, la partition
{{1, 3}, {2, 4}} contient un croisement alors que {{1, 4}, {2, 3}} n’en contient pas.
De la même manière, un croisement dans une liste s ∈ J1, KKK est un quadruplet d’entiers a, b, c, d ∈
J1, KK, tels que a < b < c < d, sa = sc et sb = sd .
Une partition (ou liste) non croisée est une partition (ou liste) sans croisement.

Question 4. Montrer que la bijection de la Question 1 se restreint à une bijection entre les listes K-incrémentales
non croisées et les partitions de J1, KK non croisées.

Solution : Soit s une liste incrémentale et P la partition correspondante. Si on a un croisement (a, b, c, d) dans
s, alors on a un croisement dans P .

On cherche à éliminer les croisements d’une partition tout en préservant la cardinalité et l’élément
minimal de chaque bloc. Pour cela, on définit une relation binaire “→” sur l’ensemble J1, KKK de la
manière suivante : pour toute paire de listes (s, t), on dit que s → t s’il existe un croisement (a, b, c, d)
dans s tel que sa < sb et, pour tout i ∈ J1, KK :

sc si i = d

ti = sd si i = c


si sinon.

Par exemple, (1, 2, 1, 3, 2) → (1, 2, 2, 3, 1).

Question 5. Montrer que, si s → t, alors t est strictement supérieur à s selon l’ordre lexicographique sur les listes
d’entiers.

Solution : Soit (a, b, c, d) le croisement dans s qui donne lieu à la réduction s → t. On remarque que s et t
coincident pour tous les indices < c, donc il suffit de montrer que sc < tc . Mais en combinant les hypothèses on a
sc = sa < sb = sd = tc .

Question 6. Montrer que si s est K-incrémentale et comprend un croisement, alors il existe une liste t telle que
s → t.

Solution : Il faut montrer que s’il existe un croisement (a, b, c, d) dans s alors il existe forcément un croisement
(a′ , b′ , c′ , d′ ) tel que sa′ < sb′ . La solution est de prendre (sb , sa , b, c). Les conditions pour un croisement sont
satisfaites : sb < sa , sa < b (puisque sa ≤ a < b), b < c, et sb = ssb et sc = sa = ssa .

17
Question 7. Montrer que si s est K-incrémentale et s → t, alors t est K-incrémentale.

Solution : Si la réduction concerne un croisement (a, b, c, d) avec sa < sb , alors t est incrémentale : pour i ̸= c, d,
ti ≤ i parce que si = ti et s est incrémentale ; pour i = c, ti = sd = sb < b < c ; et pour i = d, ti = sc = sa < a < d.
Ensuite on doit montrer que tti = ti . On remarque que c et d n’apparaissent pas dans s, car sinon on aurait
c = sc = sa ≤ a ou d = sd = sb ≤ b. Donc, pour tout i, tsi = ssi . Si i ̸= c, d, alors tti = tsi = ssi = si , et
ttc = tsd = ssd = sd = tc et symétriquement ttd = td .

Question 8. Montrer qu’une liste K-incrémentale se réduit en une liste K-incrémentale sans croisement en un
nombre fini d’étapes.

Solution : Il suffit de combiner les trois questions précédentes. L’ordre lexicographique sur un ensemble fini ne
peut pas avoir de chaine infinie et strictement croissante.

18
 Pomsets probabilistes

On fixe un ensemble L, dont les éléments sont vus comme des actions possibles d’un processus concur-
rent. On modélise un tel processus à l’aide d’ordres partiels étiquetés, comme suit.
Un pomset est un triplet (P, ≤P , ℓP ) où P est un ensemble fini, ≤P est un ordre partiel sur P , et
ℓP : P → L est une fonction.
Une trace d’un pomset (P, ≤P , ℓP ) est une paire (x, σ) où :
— x ⊆ P est un ensemble clos par le bas, c’est-à-dire que si p ∈ x et q ∈ P avec q ≤P p, alors q ∈ x.
La cardinalité de x est dénotée |x|.
— σ : x → {1, . . . , |x|} est une bijection telle que, pour tout p, q ∈ x, si p ≤P q alors σ(p) ≤ σ(q).
On désigne souvent le pomset (P, ≤P , ℓP ) simplement par P , et on appelle Traces(P ) l’ensemble de ses
traces.
On dit que deux traces (x, σ) et (x′ , σ ′ ) sont équivalentes s’il existe une bijection φ : x → x′ telle que,
pour tout p ∈ x, ℓP (p) = ℓP (φ(p)) et σ(p) = σ ′ (φ(p)).

Question 1. Soient a, b deux éléments distincts de L. Lister les traces du pomset à trois éléments P = {p1 , p2 , p3 },
où on a seulement pi ≤P pj si i = 1 et j = 2, ou si i = j, et ℓP (p1 ) = ℓP (p3 ) = a et ℓP (p2 ) = b. Indiquer les paires
de traces qui sont équivalentes.

Question 2. Pour un pomset (P, ≤P , ℓP ) arbitraire, définir une fonction mot : Traces(P ) → L∗ , où L∗ est
l’ensemble des mots définis à partir de l’alphabet L. La fonction doit satisfaire la condition suivante : deux traces
(x, σ) et (x′ , σ ′ ) de P sont équivalentes si et seulement si mot((x, σ)) = mot((x′ , σ ′ )).

On fixe un pomset P pour le reste du sujet, et on note D(P ) l’ensemble des sous-ensembles de P qui
sont clos par le bas. Une valuation probabiliste sur P est une fonction v : D(P ) → [0, 1] qui satisfait les
conditions suivantes :
— v(∅) = 1 ;
— Pour tout entier n ≥ 1, si x, y1 , . . . , yn ∈ D(P ) avec x ⊆ yi pour tout 1 ≤ i ≤ n, alors
!
X [
(−1)|S|+1 v yi ≤ v(x).
S⊆{1,...,n} i∈S
S̸=∅

Question 3. Montrer que, pour toute valuation probabiliste v sur P , si x, y ∈ D(P ) et x ⊆ y, alors v(x) ≥ v(y).
Donner un exemple de valuation probabiliste w pour le pomset P de la Question 1, telle que w(P ) < 1.

QuestionQ 4. Soit f : P → [0, 1] une fonction arbitraire. Montrer que la fonction vf : D(P ) → [0, 1] définie par
vf (x) = p∈x f (p) est une valuation probabiliste.

Si (x, σ), (y, τ ) ∈ Traces(P ), on écrit (x, σ) ⪯ (y, τ ) lorsque x ⊆ y et σ −1 (i) = τ −1 (i) pour tout
i ∈ {1, . . . , |x|}. On note ε ∈ Traces(P ) la seule trace de la forme (∅, σ).
Une valuation-traces sur P est une fonction vt : Traces(P ) → [0, 1] telle que vt(ε) = 1 et vt((x, σ)) ≥
vt((y, τ )) si (x, σ) ⪯ (y, τ ).

Question 5. Montrer que la relation ⪯ sur Traces(P ) est un ordre partiel.

19
Question 6. Montrer que, si v : D(P ) → [0, 1] est une valuation probabiliste, la fonction

vt : Traces(P ) → [0, 1]
v(x)
(x, σ)) 7→ .
# {σ | σ : x → {1, . . . , |x|} est une bijection et (x, σ) ∈ Traces(p)}

est une valuation-traces.

Question 7. Peut-on définir une valuation probabiliste à partir d’une valuation-traces ?

20
 Domination romaine des graphes

Soit G = (V, E) un graphe non orienté, où V est un ensemble de sommets et E un ensemble d’arêtes,
qui sont des couples de sommets distincts. Le degré de G est le nombre maximal de voisins d’un sommet
de G, noté ∆(G). Pour tout W ⊆ V , on note G[W ] le sous-graphe de G induit par W , dans lequel on
ne conserve que les sommets dans W et les arêtes entre eux.

Une fonction f : V → {0, 1, 2} est appelée une fonction de domination romaine (FDR) sur G si tout
sommet x pour lequel f (x) = 0 possède un voisin y pour lequel f (y) = 2 :

∀x ∈ V, f (x) = 0 =⇒ ∃y ∈ V, {x, y} ∈ E ∧ f (y) = 2 .

On dit alors que y protège x.

P
Le poids d’une FDR f est donné par : γ(f ) := v∈V f (v). On note F(G) l’ensemble des FDRs sur G.
On note γR (G) la valeur minimale du poids des FDRs sur G :

γR (G) = min γ(f ) .

f ∈F (G)

On dit que f est optimale ssi γ(f ) = γR (G).

On remarque qu’une FDR est définie par une partition de V . On utilisera l’abus de notation f =
(V0 , V1 , V2 ) où Vi est l’ensemble des sommets x tels que f (x) = i. De plus on note n0 , n1 , n2 les
cardinaux respectifs de V0 , V1 , V2 , et n le cardinal de V .

Question 1. L’empire Romain sous Constantin (IIIe siècle après J-C.) est modélisé par le graphe ci-dessous.
Chaque sommet représente une province, sur laquelle peuvent être stationnées zéro, une ou deux, armées, de sorte
que chaque province sans armée peut être défendue en déplaçant une armée d’une province voisine qui en comporte
deux. Combien d’armées suffisent-elles pour défendre l’empire romain ?

Solution : Quatre armées suffisent et de nombreuses méthodes sont possibles. L’une d’entre elles est de placer
deux armées à Rome, une en Grande-Bretagne et une en Asie mineure.

Question 2. Soit G un graphe et f = (V0 , V1 , V2 ) une FDR optimale sur G. Montrer que :
1. G[V1 ] a degré au plus 1.
2. Il n’existe pas d’arête entre V1 et V2 dans G.
3. Tout sommet de V0 est adjacent à au plus deux sommets de V1 .

21
Solution : 1. Supposons qu’il existe un sommet de degré 2 dans G[V1 ]. Alors on a trois sommets dans V1 , que
l’on va noter (x, y, z), tels que f (x) = f (y) = f (z) = 1 et (x, y), (x, z) ∈ E. La fonction f ′ telle que f ′ (x) = 2 et
f ′ (y) = f ′ (z) = 0 est toujours une FDR : les sommets y, z sont maintenant protégés par x, et ils ne protégeaient
aucun autre sommet. Mais f ′ est de poids strictement inférieur à f , c’est une contradiction.
2. Supposons qu’il existe x ∈ V1 et y ∈ V2 tels que (x, y) ∈ E. Soit f ′ telle que f ′ (x) = 0 et f ′ (y) = 2 ; alors f ′ est
toujours une FDR : x est protégé par y, et x ne protégeait aucun autre sommet. Mais f ′ est de poids strictement
inférieur à f , contradiction.
3. Supposons qu’il existe x ∈ V0 adjacent à trois sommets y, z, t de V1 . Alors on peut modifier la fonction en :
f ′ (x) = 2 et f ′ (y) = f ′ (z) = f ′ (t) = 1. Le poids est strictement inférieur et cette fonction est bien une FDR (y, z, t
sont maintenant protégés par x) ; contradiction.

Le voisinage d’un sommet v ∈ V , noté N (v) est l’ensemble des voisins {u ∈ V, {u, v} ∈ E}. Le voisinage
clos, noté C(v), est défini par C(v) := N (v) ∪ {v}. Cette définition s’étend naturellement à un ensemble
de sommets.

Soit S ⊆ V et v ∈ S. Le sommet u est appelé un voisin privé de v relativement à S ssi C(u) ∩ S = {v}.
Il est dit externe s’il appartient à V \S.

Question 3. Soit G un graphe et f une FDR optimale sur G. Soit H = G[V0 ∪ V2 ]. Montrer que :
1. Tout sommet v ∈ V2 a au moins deux voisins privés relativement à V2 dans H.
2. Si v ∈ V2 a exactement un voisin privé externe relativement à V2 dans H, que l’on note w ∈ V0 , alors w n’a
aucun voisin dans V1 .
Supposons de plus que f minimise n1 . Montrer que :
3. Tout sommet de V1 n’admet aucun voisin dans V1 .
4. Tout sommet de V0 est adjacent à au plus un sommet de V1 .
5. Soit v ∈ V2 avec exactement deux voisins privés externes relativement à V2 dans H, notés w1 , w2 ∈ V0 . Alors
il n’existe pas de sommets y1 , y2 ∈ V1 tels que (y1 , w1 , v, w2 , y2 ) forme un chemin dans G.

Solution : Comme indiqué dans la question, les voisins privés de v relativement à S sont les sommets du graphe
dont le seul voisin dans S est v. Noter que cela peut inclure v si v n’a pas d’autre voisin dans S. Les voisins privés
externes sont, de plus, extérieurs à S (et donc n’incluent jamais v). De nouveau on procède par l’absurde.
1. On se place dans le sous-graphe H. Les voisins privés de v relativement à V2 sont les sommets de H dont le
seul voisin dans V2 est v, ce qui inclut v s’il n’a pas de voisin dans V2 . Supposons que v n’a qu’un seul voisin privé
relativement à V2 . Il y a deux cas possibles :
— Soit ce voisin est v lui-même, ce qui signifie que v n’est pas protégé par un autre sommet de V2 , mais tout
voisin de v dans V0 est déjà protégé par un autre sommet de V2 . On peut donc changer la valeur en v à 1,
contradiction.
— Soit ce voisin n’est pas v. Cela signifie que v est lui-même protégé par un autre sommet de V2 , et qu’il n’est
« protecteur exclusif » que d’un seul sommet de V0 . On peut donc changer la valeur de ce sommet à 1, et la
valeur de v à 0.
2. On sait d’après le point précédent que v a au moins deux voisins privés relativement à V2 dans H. On doit donc
être dans un cas où l’un de ces voisins est v, ce qui signifie que v n’a pas de voisin dans V2 .
De plus v n’est protecteur exclusif que du seul sommet w ∈ V0 par hypothèse. On forme donc une nouvelle FDR
en changeant la valeur de v à 0, et la valeur de tous les voisins y ∈ N (w) ∩ V1 à 0. On change la valeur de f (w) à 2.
Si w avait au moins un voisin dans V1 , cette FDR est de poids strictement inférieur, contradiction (voir le schéma
ci-dessous).

22
3. C’est trivial : on pourrait réduire le nombre de 1 en associant les poids 2-0 à ces deux sommets.
4. Si un sommet de V0 est adjacent à deux sommets de V1 , on peut remplacer ce sommet par 2 pour qu’il protège
les deux sommets. Le poids est inchangé, mais n1 diminue. Contradiction.
5. On suppose donc que v a exactement deux voisins w1 , w2 ∈ V0 dont le seul voisin dans V2 est v lui-même. Si un
chemin (y1 , w1 , v, w2 , y2 ) existe, alors les valeurs de f sur ce chemin sont (1, 0, 2, 0, 1). On change ces valeurs en
(0, 2, 0, 2, 0) ; il suffit de vérifier que la fonction modifiée est toujours une FDR. Cette nouvelle fonction a le même
poids et moins de 1, contradiction.

Question 4. Soit G un graphe sans sommet isolé, n son nombre de sommets, et f une FDR optimale qui minimise
n1 . Soit c = |{v ∈ V0 , |N (v) ∩ V2 | ≥ 2}|. Soit ai , i = 1, 2, . . . , ∆(G) le nombre de sommets de V2 qui ont exactement
i voisins privés externes relativement à V2 dans H. Montrer que :
∆(G)
X
n2 = aj (1)
j=1
 ∆(G)
X 
n0 = jaj +c (2)
j=1
 ∆(G)
X 
n1 ≤ a2 + jaj +c (3)
j=3

Solution : La première égalité (sur n2 ) est triviale : c’est par définition de n2 (et la somme est jusqu’à ∆(G) par
définition du degré du graphe).
Pour l’égalité sur n0 , on sépare d’abord les sommets de V0 en :
— Ceux qui n’ont qu’un seul voisin dans V2 , notés V0′
— Ceux qui ont deux ou plus voisins dans V2 , au nombre de c (par définition), notés V0′′
Chaque sommet de V0′ est voisin privé externe d’un sommet de V2 . Chaque sommet de V2 a au moins un voisin
privé externe dans V0 . En comptant le nombre de voisins privés externes des sommets de V2 , on énumère donc tous
les sommets de V0′ . Par définition de aj :  
∆(G)
X
n0 =  jaj  + c
j=1

Ce qui donne l’égalité sur n0 .

On prouve maintenant l’inégalité sur n1 . Par hypothèse, le graphe ne contient pas de sommets isolés. Tout sommet
de V1 admet donc au moins un voisin dans V0 (il n’en a pas dans V1 ni dans V2 d’après les questions précédentes).
Tout sommet de V0 est voisin d’au plus un sommet de V1 (cf. 3.3). On sépare les sommets de V1 en :
— Ceux qui ont (au moins) un voisin dans V0′ , notés V1′
— Ceux qui n’en ont pas, notés V1′′ (et qui ont donc un voisin dans V0′′ )
On a donc :
n1 = |V1′ | + |V1′′ | ≤ |V1′ | + c .
Comme tout sommet de V1′ admet un voisin dans V0′ , et tout sommet de V0′ est voisin privé externe d’un sommet
de V2 , on se ramène à un comptage sur V2 . Pour chaque sommet de V2 :

23
 — S’il a trois ou plus voisins privés externes, alors on obtient le même nombre (potentiellement) d’éléments
distincts de V1′
— S’il a deux voisins privés externes, alors d’après 3.5, l’un de ces sommets n’a pas de voisin dans V1 , donc on
obtient au plus un seul élément de V1′
— S’il a un seul voisin privé externe, alors d’après 3.2 ce voisin n’a aucun voisin dans V1 , et donc on obtient
zéro élément de V1′ .
On peut donc écrire :
∆(G)
X
n1 ≤ a2 + jaj + c .
j=3

Question 5. En reprenant les hypothèses de la Question 4, en déduire que n0 ≥ 3n/7. Donner un exemple de
graphe pour lequel cette inégalité est une égalité.

Solution : On va montrer que n1 + n2 ≤ 43 n0 (ce qui donne immédiatement le résultat).

∆(G) ∆(G)
X 4 X 4
n1 + n2 ≤ c + a1 + 2a2 + (j + 1)aj ≤ c + a1 + 2a2 + jaj ≤ n0 .
3 3
j=3 j=3

Pour atteindre la borne, prendre l’arbre suivant :

Il est facile de se convaincre que la FDR représentée ci-dessus est optimale et minimise le nombre de 1.

Question 6. Soit δ(G) le degré minimal de G, c’est-à-dire le nombre minimal de voisins des sommets de G. En
particulier, si le graphe n’est pas connexe, on pose δ(G) = 0.
Montrer que :
2 + ln((1 + δ(G))/2)
γR (G) ≤ n .
1 + δ(G)

Indication : on s’intéressera au poids moyen d’une famille de FDRs bien choisie.

Solution : Étant donné un graphe G, on sélectionne un ensemble de sommets A en prenant des sommets au hasard
avec probabilité p. La taille moyenne de A est np. Notons δ := δ(G). Nous allons utiliser A comme ensemble V2
pour une FDR, et utiliser la borne sur δ(G) pour borner le poids de cette fonction.
Soit B = V − N [A] l’ensemble des sommets non protégés par A. La fonction f = (V − (A ∪ B), B, A) est une FDR
pour G.
On calcule la taille moyenne de B. La probabilité que v soit dans B est égale à la probabilité que v ne soit pas dans
A et qu’aucun sommet de A ne soit voisin de v. C’est-à-dire : (1 − p)1+deg(v) . Comme deg(v) ≥ δ et e−x ≥ 1 − x,

24
on a : Pr(v ∈ B) ≤ e−p(1+δ) . Donc la taille moyenne de B est au plus ne−p(1+δ) , et le poids moyen de f est au plus
2np + ne−p(1+δ) . On a donc :
E(f (V )) ≤ 2np + ne−p(1+δ)
où l’espérance est sur le choix de A. On choisit la valeur de p qui minimise cette fonction :
 
1 1+δ
p= ln .
1+δ 2

Ce qui donne :
2 + ln((1 + δ(G))/2)
E(f (V )) ≤ n .
1 + δ(G)

Comme c’est le poids moyen de f , il existe au moins une FDR avec ce poids.

Question 7. Soit G un graphe sans sommet isolé. Montrer que : γR (G) ≥ ∆(G)+1 .
2n

Solution : Soit f = (V0 , V1 , V2 ) une FDR. Comme tout v ∈ V0 doit être adjacent à un sommet de V2 , on a :
n0 ≤ ∆n2 . De plus :
n = n0 + n1 + n2 ≤ n1 + (∆ + 1)n2
Par ailleurs :
γR (G) = n1 + 2n2
On a donc :

γR (G)(∆ + 1) = n1 (∆ + 1) + 2n2 (∆ + 1) ≥ 2n1 + 2(∆ + 1)n2

≥ 2n .

Notons qu’on a besoin de ∆(G) ≥ 1 ; ce n’est pas vrai si G est le graphe singleton de degré 0. (Mais tout graphe
avec au moins une arête fonctionne).

25
 Protocoles de calcul à base de cartes

On considère des cartes dont la face recto porte un symbole noté ♡ (blanc) ou ♠ (noir). Une carte
face verso affiche le symbole ? . Une séquence de cartes est un vecteur (α0 , . . . , αm−1 ) où αi est
(formellement) une paire indiquant le symbole de la carte (blanc ou noir) et son état (recto ou verso).
Dans la suite de l’énoncé on écrira simplement des séquences de cartes comme ? ? ♠ ♡ ♠ ♡ . . .

On définit l’encodage d’un Booléen de la manière suivante : 0 est encodé par ♠ ♡ et 1 par ♡ ♠ .
On généralise l’encodage à des n-uplets de Booléens en plaçant les encodages côte à côte. On écrit par
exemple ? ? ♠ ♡ ♠ ♡ pour une séquence de 6 cartes encodant (b, 0, 0).
| {z }
b

Soit f : {0, 1}n → {0, 1} une fonction Booléenne. Un protocole de calcul à cartes pour la fonction f
est un algorithme qui :
1. Prend en entrée une séquence de m = 2n + mb + mn cartes de la forme :

? ? ? ? ··· ? ? ♡ ♡ ··· ♡ ♠ ♠ ··· ♠ ,

| {z } | {z } | {z } | {z }| {z }
b0 b1 bn−1 mb cartes mn cartes

encodant un vecteur Booléen (b0 , . . . , bn−1 ) secret ainsi qu’un nombre fixé de cartes additionnelles face
visible.
2. Peut appliquer les opérations suivantes à la séquence de cartes :
— Permute(π) : on permute les cartes selon une permutation fixe π de {0, . . . , m − 1} :

(α0 , . . . , αm−1 ) → (απ(0) , . . . , απ(m−1) )

— Coupe(i, 2j) : dans la sous-séquence des cartes αi , . . . , αi+2j−1 , on applique une coupe aléatoire :
(
(αi , . . . , αi+j−1 , αi+j , . . . , αi+2j−1 )
(αi , . . . , αi+j−1 , αi+j , . . . , αi+2j−1 ) →
(αi+j , . . . , αi+2j−1 , αi , . . . , αi+j−1 )

où chaque cas arrive avec probabilité 1/2. En particulier, en appliquant une coupe sur des cartes
face cachée, il est impossible de dire quel cas s’est produit.
— Retourne(i) : on retourne la carte à la position i, qui passe donc de recto à verso ou inversement.
3. Est tel qu’à la fin du protocole, les deux premières cartes de la séquence, face verso, encodent
f (b0 , . . . , bn−1 ). Les autres cartes peuvent être dans un état quelconque.
Les actions effectuées peuvent dépendre des symboles observés sur les cartes retournées. De plus, on
exige que le protocole ne révèle aucune information sur les entrées b0 , . . . , bn−1 . On pourra justifier cette
propriété de manière informelle.

Question 1. Donner un protocole calculant la fonction NOT sans révéler la valeur de son entrée : ? ? → ? ?
| {z } | {z }
b b

Solution : Le protocole consiste en un échange des deux cartes. Par définition, le résultat est un encodage de
la négation du Booléen b. On remarque qu’aucune carte n’a été retournée au cours du protocole, donc aucune
information sur la valeur de b n’a pu être obtenue.

Question 2. Sur l’entrée : ? ? ? ? ♠ ♡ on effectue les opérations suivantes :

| {z } | {z } | {z }
a b 0

26
 — Retourner les deux cartes visibles face verso
1 2 3 4 5 6 1 3 5 2 4 6
— Appliquer la permutation suivante : ? ? ? ? ? ? → ? ? ? ? ? ?
| {z } | {z } | {z }
a b 0
1 2 3 4 5 6 4 5 6 1 2 3
— Appliquer une coupe (avec probabilité 1/2) : ? ? ? ? ? ? → ? ? ? ? ? ?
1 2 3 4 5 6 1 4 2 5 3 6
— Appliquer la permutation suivante : ? ? ? ? ? ? → ? ? ? ? ? ?
Montrer que la séquence de cartes obtenue est un encodage de : (a ⊕ r, b ⊕ r, r), où ⊕ est le OU exclusif, et r vaut
0 ou 1 avec probabilité 1/2.

Solution : Calculons déjà le résultat de la permutation, en notant a0 a1 et b0 b1 les encodages de a et b.

Avec probabilité 1/2, la coupe laisse la séquence inchangée. La composition des deux permutations donne :
a0 a1 b0 b1 ♠ ♡ → a0 b0 ♠ a1 b1 ♡ → a0 a1 b0 b1 ♠ ♡

c’est-à-dire qu’en fait, on n’a rien fait. On est dans le cas r = 0.

Avec probabilité 1/2, la coupe échange les deux moitiés de la séquence. Alors :
a0 a1 b0 b1 ♠ ♡ → a0 b0 ♠ a1 b1 ♡ → a1 b1 ♡ a0 b0 ♠ → a1 a0 b1 b0 ♡ ♠

On a donc interverti les cartes de a, b et du bit auxiliaire. On est dans le cas r = 1.

Dans les deux cas on a bien obtenu (a ⊕ r, b ⊕ r, r).

Question 3. En déduire :
1. Un protocole pour l’opération COPY, qui sur l’entrée : ? ? ♠ ♡ ♠ ♡ renvoie ? ? ? ? ♠ ♡
| {z } | {z } | {z } | {z } | {z } | {z }
a 0 0 a a 0
2. Un protocole pour l’opération XOR, qui sur l’entrée : ? ? ? ? ♠ ♡ , renvoie ? ? ? ? ♠ ♡
| {z } | {z } | {z } | {z } | {z } | {z }
a b 0 a a⊕b 0
Justifier que ces protocoles ne révèlent aucune information sur a et b.
Indication : si A et R sont des variables aléatoires indépendantes à valeurs dans {0, 1}, et Pr(R = 0) = 2,
1

montrer que Pr(A ⊕ R = 0) = 21 .

Solution : Le protocole COPY est un cas particulier du protocole XOR.

Une fois appliqué le protocole de la question 2, il faut révéler certaines cartes. Révéler r ne nous avance en rien.
On va plutôt révéler les deux premières cartes : on obtient la valeur de (a ⊕ r).
Si a ⊕ r = 0 alors on sait que les cartes face cachée encodent b ⊕ a, a. Il suffit de les permuter pour obtenir les
encodages de (a, a ⊕ b) aux positions voulues.
Si a ⊕ r = 1 alors les cartes face cachée encodent b ⊕ a, a. On applique deux fois un NOT (échanger les cartes), et
on effectue la même permutation.
La seule valeur observée au cours du protocole est a ⊕ r. Or on a :

Pr(A ⊕ R = 0) = Pr(R = 0 ∧ A = 0) + Pr(R = 1 ∧ A = 1)

1 1 1
= Pr(A = 0) + Pr(A = 1) = .
2 2 2
Par indépendance de R. On peut même en déduire que Pr(A = 0|A ⊕ R = 0) = Pr(A = 0|A ⊕ R = 1) = Pr(A = 0).
Ce qui formalise le fait que « observer a ⊕ r ne donne aucune information sur la valeur de a » (ici a est une variable
aléatoire Booléenne, et r une variable aléatoire Booléenne uniforme indépendante de a).
Enfin, il en est de même pour b, puisque le bit observé est indépendant de b.

27
Question 4. Sur une entrée ? ? ♠ ♡ ? ? encodant deux bits (a, b) et deux cartes additionnelles ♠ ♡ , on
| {z } | {z }
a b
effectue les opérations suivantes :
— Retourner les cartes visibles : on obtient alors ? ? ? ? ? ?
| {z } | {z } | {z }
a 0 b
1 2 3 4 5 6 1 3 4 2 5 6
— Effectuer la permutation suivante : ? ? ? ? ? ? → ? ? ? ? ? ?
1 2 3 4 5 6 4 5 6 1 2 3
— Effectuer une coupe (avec probabilité 1/2) : ? ? ? ? ? ? → ? ? ? ? ? ?
1 2 3 4 5 6 1 4 2 3 5 6
— Effectuer la permutation suivante : ? ? ? ? ? ? → ? ? ? ? ? ?
Compléter ce protocole et montrer qu’il permet de renvoyer a ∧ b.

Solution : On procède comme à la question précédente.

Dans le cas où la coupe a lieu :

a0 a1 ♠ ♡ b0 b1 → a0 ♠ ♡ a1 b0 b1 → a1 b0 b1 a0 ♠ ♡ → a1 a0 b0 b1 ♠ ♡
| {z } | {z } | {z }
a⊕1 b 0

Dans le cas où elle n’a pas lieu :

a0 a1 ♠ ♡ b0 b1 → a0 ♠ ♡ a1 b0 b1 → a0 a1 ♠ ♡ b0 b1
| {z } | {z } | {z }
a 0 b

On remarque que les quatre cartes de droite encodent b ∧ r, b ∧ r où r est un bit aléatoire uniforme, qui vaut 1 dans
le premier cas et 0 dans le deuxième. Dans le cas général, on a donc produit un encodage de : a ⊕ r, r ∧ b, r ∧ b.
Pour la suite du protocole, on retourne les deux premières cartes. Si on lit 0, alors on a obtenu 0|a ∧ b|a ∧ b, et
a ∧ b se trouve dans les cartes 3 et 4. Si on lit 1, alors a ∧ b se trouve dans les cartes 5 et 6. On permute donc en
fonction pour que le résultat soit toujours au même endroit. Comme précédemment, on n’observe que a ⊕ r, qui
est indépendant de a, et on ne révèle donc aucune information sur a ni b.

Question 5. Compléter le protocole précédent pour qu’il renvoie : ♠ ♡ ? ? ? ?

| {z } | {z }
b a∧b

Solution : À la fin du protocole AND précédent on a : ♠ ♡ ? ? ? ? . Maintenant le problème est de retrans-

| {z } | {z } | {z }
0 a∧b a∧b
former a ∧ b en b.
Pour ce faire, on applique un XOR, qui va XORer la valeur a ∧ b dans la valeur a ∧ b. On a bien : (a ∧ b) ⊕ (a ∧ b) =
(a ⊕ a) ∧ b = 1 ∧ b = b.

Question 6. Montrer que pour toute fonction booléenne f : {0, 1}n → {0, 1} il existe un protocole permettant
de la calculer. De combien de cartes auxiliaires a-t-on besoin ?

Solution : Toute fonction Booléenne peut s’écrire sous la forme d’une conjonction de clauses. Notons donc :

f (b0 , . . . , bn−1 ) = c1 (b0 , . . . , bn−1 ) ∧ . . . ∧ c2n (b0 , . . . , bn−1 )

où chaque ci est une disjonction contenant les bi ou leur négation.

28
Pour commencer, notons qu’on peut construire un protocole pour OR en adaptant notre protocole pour AND (il
suffit de composer avec des NOT en entrée et en sortie). On peut donc calculer :


 ? ? ? ? ♠ ♡ → ? ? ? ? ♠ ♡

| {z } | {z } | {z } | {z }
a b a b∧a

 ? ? ? ? ♠ ♡ → ? ? ? ? ♠ ♡

| {z } | {z } | {z } | {z }
a b a b∨a

Un début de solution est de remarquer qu’il existe bien un tel protocole obtenu en copiant autant de fois que
nécessaire les entrées, et en appliquant une série de AND et de OR. Il faut maintenant minimiser le nombre de
cartes auxiliaires.
On commence par montrer comment calculer une clause ci (b0 , . . . , bn−1 ) en utilisant quatre cartes auxiliaires (dont
deux pour la sortie, et deux qu’on récupère ensuite) : on commence par faire une copie de b0 dans la sortie, et
ensuite une séquence de OR avec les valeurs de bi ou bi dont on a besoin.
On ajoute deux cartes auxiliaires supplémentaires pour stocker la sortie de f . Pour chaque clause, on calcule
séparément sa valeur, ensuite on applique un protocole AND avec cette valeur et la sortie de f . Enfin, étape très
importante, il faut effacer la valeur de la clause que l’on vient de calculer (afin de pouvoir réutiliser ces cartes).
Pour ce faire, différentes méthodes sont possibles. On peut par exemple faire un OR avec la négation d’un des
littéraux de la clause. Ou bien, approche assez élégante, appliquer une coupe aléatoire qui va échanger les deux
cartes, avant de retourner celles-ci face visible.
À la fin du protocole, non seulement on récupère la sortie de f , mais aussi les b0 , . . . , bn−1 inchangés, et les 4 cartes
utilisées durant le calcul. Le protocole utilise 2n + 6 cartes au total. Il ne révèle aucune information sur les bits
d’entrée, car c’est le cas de tous les protocoles intermédiaires pour AND / OR / NOT / effacement.

Question 7. Donner un protocole de « random flip » qui sur une entrée (b0 , . . . , bn−1 ) (face verso), renvoie (b0 ⊕
r, . . . , bn−1 ⊕ r) où r est une valeur aléatoire uniforme (face verso). En déduire un protocole à 2n cartes calculant
la fonction « égalité » : (
1 si b0 = b1 . . . = bn−1
f (b0 , . . . , bn−1 ) = (1)
0 sinon

Solution : Le protocole de random flip est simplement une permutation qui regroupe les indices impairs (resp.
pairs), suivie d’une coupe en deux paquets de n cartes, suivie de la même permutation. Dans un cas toutes les
paires de cartes sont permutées localement (d’où le flip), dans l’autre cas toutes les paires sont laissées inchangées.
Sur l’entrée (b0 , . . . , bn−1 ) on applique le random flip. On retourne les deux premières cartes, et on observe ainsi
b0 ⊕ r.
V
Si b0 ⊕ r = 0 alors f (b0 , . . . , bn−1 ) = 1 ⇐⇒ ∀i ≥ 1, bi ⊕ r = 0 ⇐⇒ bi ⊕ r = 1. Il suffit donc d’appliquer un
NOT aux bits restants et de calculer leur AND (à l’aide des deux cartes révélées comme auxiliaires).
V
Si b0 ⊕ r = 1 alors f (b0 , . . . , bn−1 ) = 1 ⇐⇒ ∀i ≥ 1, bi ⊕ r = 1 ⇐⇒ bi ⊕ r = 1. On utilise le même principe,
mais sans les NOTs.

Une fonction Booléenne est dite symétrique si f (π(b0 , . . . , bn−1 )) = f (b0 , . . . , bn−1 ) pour toute permu-
tation π de {0, . . . , n − 1}.

P
Question 8. Donner un protocole calculant sur l’entrée (b0 , . . . , bn−1 ), un encodage de bi .
En déduire un protocole pour les fonctions symétriques avec seulement 2 cartes additionnelles pour n ≥ 4.

29
 P P
Solution : On va utiliser le fait qu’une fonction symétrique est de la forme : f (b0 , . . . , bn−1 ) = g( bi ) où bi est
un entier naturel, que l’on peut interpréter comme un vecteur Booléen de taille ⌈log2 n⌉, et g est une autre fonction
Booléenne. En effet, si (b0 , . . . , bn−1 ) et (b′0 , . . . , b′n−1 ) sont deux vecteurs ayant le même nombre de “1” (donc la
même somme), il existe une permutation π qui transforme l’un en l’autre, donc f (b0 , . . . , bn−1 ) = f (b′0 , . . . , b′n−1 ).
P
On réduit donc le problème à l’implémentation d’un protocole de somme (qui produit l’encodage de bi ), suivi
du protocole pour g. D’après la question 6, le protocole pour g n’a besoin que de 6 cartes additionnelles. Comme
n ≥ 4, on a n − ⌈log2 n⌉ ≥ 2, et par conséquent après avoir calculé la somme, on pourra récupérer au moins 4
cartes supplémentaires, ce qui garantit qu’on peut calculer g.
Pour le protocole de somme : il faut implémenter un additionneur. Il suffit pour cela de faire un « half adder » qui
de deux bits a, b, calcule (a ∧ b, a ⊕ b). En effet, supposons qu’on ait un registre qui encode un entier i sur m bits,
suivi d’un Booléen a. Sur cette entrée im−1 . . . i0 a où i0 est le bit de poids faible de i, on exécute :

im−1 . . . i0 a → im−1 . . . i1 (i0 ⊕ a)(a ∧ i0 )

et ensuite on additionne a ∧ i0 (la retenue) à im−1 . . . i1 , de manière récursive, pour obtenir les bits suivants. Ceci
nous donne l’addition d’un bit à un entier. On peut donc ensuite ajouter tous les bits un par un à notre registre
de résultat. Ce n’est pas la méthode la plus efficace en nombre d’étapes, mais elle suffit largement dans la mesure
où on s’intéresse surtout au nombre de cartes.
Le « half adder » peut être implémenté en utilisant deux cartes auxiliaires, et en composant des protocoles XOR
et AND. On peut remarquer que ce n’est pas difficile avec quatre cartes auxiliaires. Nous montrons ci-dessous
comment se restreindre à deux cartes.
Dans une première étape on calcule (a ∧ b, a ∧ b, 0) (sur les 6 cartes d’entrée). Pour ce faire :
XOR
(a, b, 0) 7−−−→ (a, a ⊕ b, 0) →
7− (a, a ⊕ b, 0)

Puis :
AND (partiel)
(a, a ⊕ b, 0) 7−−−−−−−−→ (a ∧ a ⊕ b, a ∧ a ⊕ b, 0)
On montre ensuite que a ∧ a ⊕ b = a ∧ b et a ∧ a ⊕ b = a ∧ b.
Enfin :
XOR NOT
(a ∧ b, a ∧ b, 0) 7−−−→ ((a ∧ b) ⊕ (a ∧ b), (a ∧ b), 0) = (a ⊕ b, a ∧ b, 0) 7−−−→ (a ⊕ b, a ∧ b, 0)

Ce qui termine le protocole.

30
 Graphes décomposables en cycles

On note Ja, bK = {a, a + 1, . . . , b} un intervalle entier, et [a, b] un intervalle réel (fermé).

On note |S| la cardinalité d’un ensemble S.
Graphe. Dans tout l’énoncé, on considère des graphes orientés. Formellement, un graphe est une paire
(V, E) où V est un ensemble non vide de sommets, et E ⊆ V × V est un ensemble d’arêtes orientées.
Un sommet v peut avoir une arête (v, v) de lui-même vers lui-même, qu’on appelle une boucle.
Sous-graphe. G = (V, E) est un sous-graphe de G′ = (V ′ , E ′ ) si et seulement si V = V ′ et E ⊆ E ′ .
Voisinage. Soit G = (V, E) un graphe, et U ⊆ V . On appelle voisinage de U l’ensemble vG (U ) des
sommets atteignables depuis U en suivant une arête de E : vG (U ) = {v ∈ V : ∃u ∈ U, (u, v) ∈ E}.
Graphe ouvert. Un graphe G = (V, E) est dit ouvert si ∀U ⊆ V, |vG (U )| ≥ |U |.
Cycle. Un cycle d’un graphe (V, E) est une suite de sommets deux à deux distincts (v1 , . . . , vk ) telle
que ∀i ∈ J1, k − 1K, (vi , vi+1 ) ∈ E, et (vk , v1 ) ∈ E. On note v1 → v2 → · · · → vk → v1 . Le cas k = 1
correspond à une boucle, qui est considérée comme un cycle.
Graphe cyclique. Un graphe G est cyclique s’il consiste en un unique cycle qui passe par tous les
sommets : G est de la forme ({v1 , . . . , vn }, {(v1 , v2 ), (v2 , v3 ), . . . , (vn−1 , vn ), (vn , v1 )}).
Décomposition en cycles. Soit G = (V, E) un graphe. Une décomposition en cycles de G est un
sous-graphe G′ de G tel que toutes les composantes connexes de G′ sont cycliques.

Question 1. Montrer que tout graphe ouvert contient au moins un cycle.

Solution : Comme le graphe est ouvert, en particulier tout sommet v a un degré sortant au moins 1 (car
|vG ({v})| ≥ |{v}| = 1). Il suffit de partir d’un sommet quelconque, et de suivre une arête sortante jusqu’au
sommet suivant, puis réitérer. Lorsqu’on finit par repasser par un sommet déjà visité, on a parcouru un cycle.

Question 2. Montrer que tout graphe qui admet une décomposition en cycles est ouvert.

Solution : Soit G un graphe et G′ sa décomposition en cycles. Sur G′ = (V, E ′ ), on peut observer que E ′ définit
une relation bijective V → V , puisque chaque sommet a un prédécesseur et un successeur. En particulier, dans G′ ,
|vG′ (U )| = |U | pour tout U ⊆ V . Or le voisinage dans G contient le voisinage dans G′ . Donc dans G, |vG (U )| ≥ |U |
pour tout U ⊆ V .

Question 3.
1. Soit G = (V, E) un graphe. Montrer que la fonction U 7→ |vG (U )| est sous-modulaire, c’est-à-dire :

∀X ⊆ V, ∀Y ⊆ V, |vG (X)| + |vG (Y )| ≥ |vG (X ∪ Y )| + |vG (X ∩ Y )|.

2. On dit que X ⊆ V est étroit si |vG (X)| = |X|. Supposons que G est ouvert. Déduire de l’inégalité précédente
que si X et Y sont étroits, alors X ∪ Y et X ∩ Y le sont aussi.

Solution :
1. Le résultat se montre bien en considérant chaque cas pour v ∈ V :
— Si v est voisin de X (i.e. v ∈ vG (X)) mais pas voisin de Y , alors il est compté une fois à gauche et une
fois à droite dans l’inégalité de la question.
— De même si v est voisin de Y mais pas de X.
— Si v est voisin de X ∩ Y , il est compté deux fois de chaque côté.

31
 — Si v est voisin de X et de Y mais pas de X ∩ Y , il est compté deux fois à gauche mais une seule fois à
droite.
— Si v n’est voisin ni de X ni de Y il est compté zéro fois de chaque côté.
Alternativement, une manière plus abstraite d’écrire la preuve est d’observer :

vG (X ∪ Y ) = vG (X) ∪ vG (Y )
vG (X ∩ Y ) ⊆ vG (X) ∩ vG (Y )

L’inégalité en bas vient de ce qu’il peut y avoir des voisins communs à X et à Y sans qu’ils soient voisins de
X ∩ Y , comme précédemment. De là, on déduit :

|vG (X)| + |vG (Y )| = |vG (X) ∪ vG (Y )| + |vG (X) ∩ vG (Y )|

≥ |vG (X ∪ Y )| + |vG (X ∩ Y )|.

2. En utilisant successivement le caractère étroit de X et Y , puis la sous-modularité de |vG (·)|, puis le caractère
ouvert de G, on a :

|X| + |Y | = |vG (X)| + |vG (Y )| ≥ |vG (X ∪ Y )| + |vG (X ∩ Y )| ≥ |X ∪ Y | + |X ∩ Y | = |X| + |Y |.

Toutes les inégalités sont donc des égalités, ce qui force |vG (X ∪ Y )| = |X ∪ Y | et |vG (X ∩ Y )| = |X ∩ Y |.

Question 4. Soit G = (V, E) un graphe ouvert avec un sommet v ∈ V qui a un degré sortant 2 : c’est-à-dire qu’il
existe x ̸= y ∈ V tels que (v, x) ∈ E et (v, y) ∈ E. Montrer qu’au moins un des graphes Gx = (V, E \ {(v, x)}) ou
Gy = (V, E \ {(v, y)}) est ouvert.

Solution : Il peut être difficile de trouver le « bon » ensemble sur lequel raisonner. Supposons par l’absurde que
ni Gx ni Gy n’est ouvert. Alors il existe X ⊆ V tel que |vGx (X)| < |X|.
— Première observation : v ∈ X, sinon X aurait le même voisinage dans G que dans Gx , et serait donc un
contre-exemple au caractère ouvert de G.
— Deuxième observation : v est le seul prédécesseur de x dans X (i.e. le seul sommet w de X tel que (w, x) ∈ E).
Sinon, à nouveau, X aurait le même voisinage dans G que dans Gx .
— Troisième observation : X est étroit (dans G) puisqu’il a au plus un voisin de plus dans G que dans Gx .
Symétriquement, il existe Y ⊆ V avec les trois mêmes propriétés (en remplaçant x par y et X par Y ci-dessus).
Par la question 3, X ∩ Y est étroit. Si on enlève v de X ∩ Y , sa cardinalité diminue de 1 ; mais, par les observations
précédentes, ni x ni y ne peuvent être dans vG (X ∩ Y \ {v}), donc :

|vG (X ∩ Y \ {v})| ≤ |vG (X ∩ Y )| − 2 = |X ∩ Y | − 2 < |X ∩ Y | − 1 = |(X ∩ Y ) \ {v}|.

L’ensemble X ∩ Y \ {v} témoigne du fait que G n’est pas ouvert, une contradiction.

Question 5. En déduire la réciproque de la question 2 : tout graphe ouvert admet une décomposition en cycles.

Solution : Soit G = (V, E) un graphe ouvert. Par la question précédente, tant que G possède un sommet de
degré sortant au moins 2, on peut supprimer une arête en restant ouvert. On continue jusqu’à ce qu’il n’y ait plus
de sommet de degré sortant 2. On arrive finalement à un sous-graphe ouvert G′ = (V, E ′ ) dont tous les sommets
sont de degré sortant 1. (Variante équivalente : on prend pour G′ un élément minimal pour l’ordre partiel « A est
sous-graphe de B », parmi les sous-graphes ouverts de G.)
Soit v ∈ V , et A = {a ∈ V : (a, v) ∈ E ′ } ses prédécesseurs dans G′ . Puisque les degrés sortants sont tous 1,
vG′ (A) = {v}, donc comme G′ est ouvert, |A| ≤ 1. Donc tous les degrés entrants dans G′ sont au plus 1. Comme

32
les sommes des degrés entrants et des degrés sortants sur V entier doivent être égales, on déduit que tous les degrés
entrants sont en fait exactement 1.
Il reste à observer qu’un graphe dont tous les degrés entrants et sortants sont égaux à 1 est en fait une union
disjointe de cycles (autrement dit, ses composantes connexes sont cycliques). En effet, en partant d’un sommet
arbitraire et en suivant successivement les arêtes sortantes, la seule possibilité est qu’on finit par revenir au sommet
de départ. On conclut que G′ est une décomposition en cycles de G.

Matrice de diffusion. Une matrice M = (mi,j )i,j∈J1,nK ∈ [0, 1]n×n est dite matrice de diffusion si la
somme de ses entrées sur chaque ligne et chaque colonne est égale à 1 :
X X
∀i ∈ J1, nK, mi,j = mj,i = 1.
j∈J1,nK j∈J1,nK

Question 6. Soit M une matrice de diffusion. Montrer qu’il existe une permutation π de J1, nK telle que ∀i ∈
J1, nK, mi,π(i) > 0.

Solution : Soit V = J1, nK, et E = {(i, j) : mi,j > 0}. On considère le graphe G = (V, E).
Pour utiliser la question 5, montrons que G est ouvert. Soit U ≤ V . Soit U ′ = vG (U ). Par construction, pour i ∈ U
et j ∈ V \ U ′ , mi,j = 0. L’idée est que si on regarde la sous-matrice avec indices dans U × U ′ , en sommant toutes
ses entrées horizontalement, c’est-à-dire ligne par ligne, on trouve |U | (parce que les entrées hors des colonnes U ′
sur les lignes U sont nulles) ; et en sommant verticalement on trouve au plus |U ′ | (parce qu’on somme une matrice
de diffusion sur quelque chose d’inclus dans |U ′ | colonnes). Comme les deux sommes doivent être égales, |U | ≤ |U ′ |.
Version formelle de la même chose :
XX X X
mi,j = mi,j = |U | · 1 = |U |
i∈U j∈U ′ i∈U j∈J1,nK
XX X X
mi,j ≤ mi,j = |U ′ | · 1 = |U ′ |.
j∈U ′ i∈U j∈U ′ i∈J1,nK

L’égalité entre les premiers termes de chaque ligne donne |U | ≤ |U ′ |.

Puisque G est ouvert, par la question 5, il contient un sous-graphe (V, E ′ ) dont toutes les composantes connexes
sont cycliques. Comme observé dans la question 2, E ′ peut être vu comme le graphe fonctionnel d’une bijection
π : V → V , en posant E ′ = {(v, π(v)) : v ∈ V }. (Les cycles de E ′ correspondent d’ailleurs à la décomposition en
cycles de π.) Par définition de E, mi,j > 0 pour tout (i, j) ∈ E ⊇ E ′ , en particulier mi,π(i) > 0 pour tout i.

P Soit M une matrice de diffusion. Montrer qu’il existe un entier k ∈ NP, un vecteur (λ1 , . . . , λk ) ∈
Question 7. ∗

[0, 1] avec i∈J1,kK λi = 1, et des matrices de permutation P1 , . . . , Pk , tels que M = i∈J1,kK λi Pi .

k

Solution : Posons M1 = M . Par la question précédente, il existe une permutation π telle que mi,π(i) > 0 pour
tout i. Soit λ1 = mini∈J1,nK mi,π(i) . Soit P1 la matrice de permutation associée à π.
Si λ1 = 1, nécessairement M1 = P1 , et on a fini. Sinon, on pose M2 = M1 − λ1 P1 . Remarquons que M2 est à valeur
dans R+ , et ses lignes et colonnes se somment toutes à 1 − λ1 . À une constante 1 − λ1 près, c’est donc une matrice
de diffusion, et on peut de nouveau appliquer la question 6. (Alternativement, on peut poser M2′ = 1/(1 − λ1 )M2
pour se ramener vraiment à une matrice de diffusion, mais ce n’est pas nécessaire, et implique de garder trace
des constantes multiplicatives pour les compenser à la fin.) On répète le même processus en partant de M2 , pour
construire λ2 , P2 etc.

33
Cet algorithme termine en O(n2 ) étapes, parce que M2 contient au moins une entrée nulle de plus que M1 : celle de
coordonnée P(j, π(j)) pour j = argmini∈J1,nK mi,π(i) . Lorsque l’algorithme termine, on a obtenu les λi et Pi souhaités.
Le fait que λi = 1 peut se montrer via un invariant adéquat le long de P la récurrence, maisPc’est aussi impliqué
de toute façon par le fait que la somme le long d’une ligne ou colonne de λi Pi est égale à λi .

Dans toute la suite de l’énoncé, on fixe 0 < m ≤ n deux entiers, et :

X
S = {(s1 , . . . , sn ) ∈ [0, 1]n : si = m} ŝ = (1, . . . , 1, 0, . . . , 0) ∈ S.
| {z } | {z }
i∈J1,nK m n−m

Question 8. Montrer que pour tout s ∈ S, il existe une matrice de diffusion M telle que s = M ŝ.

Solution : On peut se contenter d’au plus deux valeurs distinctes sur chaque ligne de M .
Pour la i-ième ligne de M , on prend la ligne dont les m premières entrées sont si /m, et (si n > m) les n − m
dernières entrées sont (1 − si )/(n − m). On voit que M ŝ = s, et que chaque ligne de M se somme à 1.
P
Il reste à montrer que les colonnes se somment à 1. Pour jP ≤ m, la j-ième colonne se somme à si /m = 1. Si
n > m, pour n − m < j ≤ n, la j-ième colonne se somme à (1 − si )/(n − m) = (n − m)/(n − m) = 1.

Convexité. Une fonction f : Rn → R est convexe P si pour tout k-uplet w1 , . . . , wk de vecteurs dans
Rn , et pour tout (λ1 , . . . , λk ) ∈ [0, 1]k tel que i∈J1,kK λi = 1 :
 X  X
f λi wi ≤ λi f (wi ).
i∈J1,kK i∈J1,kK

Symétrie. Une fonction f : Rn → R est symétrique si pour tout vecteur (v1 , . . . , vn ) ∈ Rn , et pour
toute permutation π de J1, nK :

f (vπ(1) , . . . , vπ(n) ) = f (v1 , . . . , vn ).

Question 9. Déduire des questions précédentes que pour toute fonction f : Rn → R symétrique et convexe :
max f (s) = f (ŝ).
s∈S

Solution : Soit s ∈ S et M P tel que s = M ŝ. Par la question 6, il existe une combinaison convexe de matrices de
permutations telle que M = λi Pi . En utilisant la convexité puis la symétrie de f , on a :
 X  X X
f (s) = f (M ŝ) = f λi Pi ŝ ≤ λi f (Pi ŝ) = λi f (ŝ) = f (ŝ).
i∈J1,nK i∈J1,nK i∈J1,nK

Question 10. Si on assigne m objets dans m zones mémoires, en tirant la zone choisie uniformément aléatoirement
et indépendamment pour chaque objet, un résultat classique (utilisé dans des constructions de tables de hachage),
est que l’espérance du nombre d’objets contenus dans la zone mémoire qui reçoit le plus d’objets est O(log m).
Supposons maintenant qu’on assigne n ≥ m objets ayant chacun une taille ti ∈ [0, 1] pour i ∈ J1, nK, toujours en
envoyant chaque objet dans une zone mémoire parmi P m, choisie de manière uniforme et indépendante pour chaque
objet. On suppose que la taille totale assignée est i∈J1,nK ti = m. À chaque zone mémoire i, on associe sa charge
Xi , qui est la somme des tailles des objets assignés à la zone i.
Montrer (sans faire de calcul) que l’espérance de la charge maximale X = maxi∈J1,mK Xi est O(log m).
Indication : on admettra que f : (v1 , . . . , vn ) 7→ E(X) est convexe.

34
 P
Solution : Les vecteurs (t1 , . . . , tn ) sont dans [0, 1]n et doivent satisfaire ti = m, donc ils vivent dans S. D’autre
part, on admet que f est convexe, et elle est clairement symétrique, donc on peut appliquer la question précédente
pour déduire que f atteint son maximum en ŝ. Or le cas (t1 , . . . , tn ) = ŝ revient à assigner m objets de même
taille 1 dans m zones mémoire : ce qui est exactement le cas classique non pondéré, pour lequel l’énoncé dit que
l’espérance de la charge maximale est O(log m). C’est tout : on a conclu.
Montrer que f : (v1 , . . . , vn ) 7→ E(X) est convexe est hors-sujet. Cela peut se montrer par des règles de préservation
de fonctions convexes (par somme, et composition par une fonction convexe croissante), en observant qu’une
espérance sur un ensemble fini n’est pas autre chose qu’une somme, à multiplication par un scalaire près.

35
 Fibrations de graphes

Dans ce sujet, on appelle graphe un tuple (S, A, cible, source) où S et A sont des ensembles finis et
cible : A → S et source : A → S sont des applications. Les éléments de S sont les sommets du graphe,
et les éléments de A sont les arcs. On note qu’il peut y avoir plusieurs arcs entre deux sommets.
Si G = (S, A, cible, source) et G′ = (S ′ , A′ , cible′ , source′ ) sont des graphes, un homomorphisme f :
G → G′ est une paire de fonctions f0 : S → S ′ et f1 : A → A′ satisfaisant les deux propriétés suivantes
pour tout arc a ∈ A :

cible′ (f1 (a)) = f0 (cible(a)) et source′ (f1 (a)) = f0 (source(a)).

Un arc entrant d’un sommet x ∈ S est un arc a ∈ A telle que cible(a) = x. On dit qu’un homomorphisme
f : G → G′ est une fibration si, pour tout x ∈ S et pour tout arc entrant a′ de f0 (x), il existe un unique
arc entrant a de x telle que f1 (a) = a′ .

Question 1. Donner un exemple d’homomorphisme de graphes qui n’est pas une fibration.

Solution : L’exemple le plus simple : l’inclusion du graphe {b} (un seul sommet, pas d’arête) dans le graphe
{a → b} (deux sommets, une arête).

Question 2. Donner un exemple de fibration f : G → G′ où G est le graphe ci-dessous et G′ n’est pas isomorphe
à G.
x

t y

Solution : Deux possibilités (parmi d’autres) :

— on peut faire l’union disjointe de G avec n’importe quel autre graphe H et regarder l’inclusion G → G + H.
— on peut regarder une fonction qui replie G vers un graphe plus petit, attention que la propriété de fibration
soit bien respectée (chaque flèche entrante vers l’image d’un sommet a un unique relèvement).

Question 3. Soit f : G → G′ une fibration, où G = (S, A, cible, source). Soient x, y ∈ S des sommets de G qui
ont la même image dans G′ : f0 (x) = f0 (y).
Montrer qu’il existe une bijection φ de l’ensemble A→x des arcs entrants de x vers l’ensemble A→y des arcs entrants
de y, telle que, pour tout a ∈ A→x , f0 (source(a)) = f0 (source(φ(a))).

Solution : Il y a une fonction A→x → A→f (x) donnée par l’action de l’homomorphisme f . La propriété de fibration
dit exactement que cette fonction a une inverse.
Puisque f (x) = f (y), on a juste à composer les deux bijections, pour obtenir A→x ∼
= A→f (x) = A→f (y) ∼
= A→y .

36
 On modélise un réseau distribué à l’aide d’un graphe (S, A, cible, source). Les sommets représentent les
agents du réseau. On fixe un ensemble Q et un état initial q0 (x) pour chaque sommet x ∈ S. Chaque
a
arc x −
→ y représente un canal par lequel un agent x communique son état à l’agent y.
Tous les agents sont régis par la même fonction d’évolution δ : Q × M(Q) → Q, qui met à jour l’état
d’un agent en fonction du multi-ensemble d’états qu’il reçoit. On a noté ici M(Q) l’ensemble des multi-
ensembles finis d’éléments de Q.
(Pour rappel, un multi-ensemble est une collection non-ordonnée où un même élément peut apparaitre
plusieurs fois. On utilise la notation {| · |} pour les multi-ensembles : par exemple, {|1, 1, 2|} est le multi-
ensemble qui contient deux copies de 1 et une copie de 2.)
Étant donné un état initial q0 (x) ∈ Q pour chaque sommet x ∈ S, on définit l’état qn (x) de x à l’étape
n ≥ 1 comme suit :
qn (x) = δ(qn−1 (x), {|qn−1 (source(a)) | a ∈ A→x |}).
Dans le reste du sujet, on fixe Q = {0, 1}.

Question 4. Soit G le graphe représenté ci-dessous :

Pour q0 (x) = q0 (y) = 0 et δ : Q × M(Q) → Q la fonction définie par


0 si q = 1, m = {|1|}

δ(q, m) = 1 si q = 0, m = {|0|}


0 sinon,

donner les trois premières étapes d’évolution du réseau.

Solution : On commence avec q0 (x) = q0 (y) = 0. Ensuite on a q1 (x) = δ(0, {|0|}) = 1 et de la même manière
q1 (y) = 1. Ensuite q2 (x) = q2 (y) = 0, et on voit que ça boucle : q3 (x) = q3 (y) = 1, etc.

Pour un graphe G, on appelle fonction d’élection une fonction δ : Q × M(Q) → Q avec la propriété
suivante : pour tout choix q0 : S → Q d’états initiaux, il existe n ∈ N et x ∈ S tel que qn (x) = 1 et
qn (y) = 0 pour tout y ̸= x.

Question 5. Donnez une fonction d’élection pour le graphe ci-dessous.

Solution : La fonction
(
1 si m est un multi-ensemble à deux éléments
δ(q, m) =
0 sinon

donne toujours y élu en une étape.

37
Question 6. Soient G = (S, A, cible, source) et G′ = (S ′ , A′ , cible′ , source′ ) des graphes, et soit f : G → G′ une
fibration propre, c’est-à-dire que pour tout x ∈ S ′ , la fibre f0−1 {x} n’est pas un singleton. Montrer qu’il ne peut
pas exister de fonction d’élection pour G.

Solution : On regarde le cas où q0 (x) = 0 pour tout x ∈ S et on montre que, quelle que soit la fonction de
transition δ, alors pour tout n ∈ N, si deux sommets x, y de G ont la même image dans G′ , alors qn (x) = qn (y).
Preuve par induction sur n : le cas de base est donné en hypothèse.
Cas inductif pour n ≥ 1. On a qn−1 (x) = qn−1 (x′ ) par l’hypothèse d’induction, et on montre que {|qn−1 (source(a)) |
a ∈ A→x |} = {|qn−1 (source(a)) | a ∈ A→x′ |}. On rappelle qu’il existe une bijection φ : A→x → A→x′ telle que
f0 (source(φ(a)) = f0 (source(a)). On applique l’hypothèse d’induction à source(a) et source(φ(a)), pour en déduire
que qn−1 (source(a)) = qn−1 (source(φ(a))).
Maintenant, s’il y avait une fonction d’élection pour G, alors pour un certain n on aurait un seul x élu avec
qn (x) = 1 et qn (y) = 0 pour y ̸= x. C’est une contradiction parce que x doit avoir le même état que tous les
éléments de sa fibre, et par hypothèse les fibres ne sont pas des singletons.

On considère un modèle d’exécution alternatif dans lequel les agents sont mis à jour un par un, et dans
un ordre choisi de manière non-déterministe..
On fixe un état initial q0 (x) pour tout x ∈ S et, pour tout n ≥ 1, un ordre total <n sur l’ensemble
S des sommets. Pour une fonction de transition δ : Q × M(Q) → Q, l’exécution est donnée par
qn (x) = δ(qn−1 (x), m), où

m = {|qn (source(a)) | a ∈ A→x et source(a) <n x|} ∪ {|qn−1 (source(a)) | a ∈ A→x et source(a) ≥n x|}

Dans ce nouveau modèle, on dit que δ est une fonction d’élection si l’exécution atteint toujours un état
d’élection (où il existe x avec qn (x) = 1 et qn (y) = 0 pour tout y ̸= x) en temps n fini, quels que soient
les états initiaux et les ordres <n .

Question 7. Montrer que, si f : G → G′ est une fibration propre, et si pour tout x ∈ S ′ le graphe G restreint à
la fibre f0−1 {x} est acyclique, alors il ne peut pas exister de fonction d’élection pour G.

Solution : On commence par choisir n’importe quel ordre <′ sur les sommets de G′ . Ensuite, on choisit un ordre
< sur les sommets de G tel que :
— si f (x) <′ f (y) alors x < y.
— si f (x) = f (y) (i.e. x et y sont dans la même fibre) et il y a une arête x → y, alors x > y.
On pose <n := < pour tout n ≥ 1.
Ensuite, on fait exactement la même induction que la question précédente, pour montrer que deux sommets dans
la même fibre ont forcément toujours le même état à chaque étape.

38
 Multiplication scalaire - forme non-adjacente

Soit (G, +) un groupe abélien. Dans ce sujet, nous nous intéressons à calculer efficacement k · P
où k ∈ Z et P ∈ G. Nous évaluerons la complexité de nos algorithmes selon deux paramètres : le
nombre d’additions dans G et le nombre de doublements, i.e., 2 · P . Le calcul d’un inverse est supposé
négligeable.
Un algorithme nécessitant m additions et n doublements aura une complexité notée mA + nD. Nous
supposerons que A est significativement plus coûteux que D.

Pour ce faire, nous ne représenterons pas les entiers k sous leur forme binaire, mais sous leur forme
NAF (non-adjacent form).
Définition. Une forme non-adjacente (NAF) de longueur ℓ d’un entier positif k est une expression
k = Σℓ−1
i=0 ki 2 où :
i

— (1) ki ∈ {−1, 0, 1},

— (2) kℓ−1 ̸= 0,
— (3) pour tout i ∈ {0, . . . , ℓ − 1}, ki ̸= 0 ⇒ ki+1 = 0, i.e., il n’y a pas deux chiffres consécutifs
non-nuls.
Lorsque cela n’ajoute pas d’ambiguité, nous pourrons écrire : k = ⟨kℓ−1 , . . . , k0 ⟩.

Question 1. Donner la forme NAF des entiers 3, 9, 23.

Question 2. Soit k un entier positif. Montrer que :

a. k a une unique forme NAF, notée N AF (k).
b. la longueur de N AF (k) est égale à la longueur de la représentation de k en binaire plus-ou-moins 1.
On admettra :
c. Soit k tiré selon une distribution de probabilité uniforme dans [0, 2n ]. Notons N AF (k) = ⟨kℓ−1 , . . . , k0 ⟩. Nous
avons Σℓ−1
i=0 |ki | est en moyenne (sur tous les tirages possibles) égale à ℓ/3.

Question 3. Soit k un entier positif.

Donner un algorithme permettant de calculer sa forme NAF et donner sa complexité.

Question 4. Soit k ∈ Z/2m Z et P ∈ G. Donner un algorithme exploitant la forme NAF et permettant de calculer
k · P . On évaluera également sa complexité en moyenne.

Nous souhaitons maintenant généraliser la forme NAF en considérant des "chiffres" ki ne vivant plus
nécessairement dans {−1, 0, 1}, mais dans un ensemble plus grand.
Définition. Une w-forme non-adjacente (w-NAF) de longueur ℓ d’un entier positif k, notée N AFw (k),
est une expression k = Σℓ−1
i=0 ki 2 où :
i

— (1) |ki | < 2w−1 et, si non-nul, ki est impair,

— (2) kℓ−1 ̸= 0,
— (3) pour toute suite de w coefficients consécutifs, i.e., ki , . . . , ki+w−1 , au plus l’un est non-nul.
On notera que N AF (k) = N AF2 (k).

Nous supposerons que les propriétés énoncées en Question 2. sont toujours vraies pour N AFw (k). De
plus, la propriété c. peut être reformulée en : le nombre moyen de "chiffres" non-nuls est égal à l/(w+1).

39
Question 5. Soit k ∈ Z/2m Z et P ∈ G. Donner un algorithme exploitant la forme w-NAF et permettant de
calculer k · P . On évaluera également sa complexité.

Question 6. Soit t = (tℓ−1 , . . . , t0 ). Nous notons w(t) le poids de Hamming de t, i.e., le nombre d’éléments non-
nuls de t.

Soit k un entier positif.

Soit (kℓ−1
′ , . . . , k0′ ) un encodage arbitraire de k tel que k = Σℓ−1
i=0 ki 2 , et ki < 2
′ i ′ w−1 , et, si non-nul, est impair.

Montrer que w((kℓ−1 ′ , . . . , k0′ )) ≥ w(N AFw (k)).

Question 7. Jusqu’à maintenant, nous nous sommes intéressés à optimiser le calcul de k · P . Dans de nombreuses
applications, ce sont des calculs de i · P + j · Q pour différentes valeurs de i et j (à P et Q fixés) qui sont nécessaires.
En nous autorisant à stocker au plus 22w points lors d’un pré-calcul, donner un algorithme qui permet de calculer
i · P + j · Q en environ ⌈m/w⌉A + ⌈m/w⌉wD (hors pré-calcul).
a. donner l’algorithme et justifier sa complexité
b. donner un algorithme permettant d’effectuer de manière efficace le pré-calcul
Note : nous pourrons considérer que i et j sont tous deux représentés par m bits. Le plus petit des deux pourra
donc avoir les premiers bits de poids fort à 0.

40
Annexe : sujets proposés pour la filière MPI
Certains sujets sont accompagnés d’ébauches de solution.

41
 Systèmes bien structurés

Un ordre partiel est un ensemble S équipé d’une relation ≤ qui est réflexive, transitive et anti-
symmétrique. On dit qu’un ordre partiel est beau si pour toute suite infinie

s0 , . . . , sn , . . . ,

de S, il existe une paire croissante : i < j et si ≤ sj . Dans un ordre partiel (S, ≤), un élément s est
dit minimal dans S ′ ⊆ S si pour tout s′ ∈ S ′ \ {s}, s′ ̸≤ s. On note min(S ′ ), l’ensemble des éléments
minimaux de S ′ . Un sous-ensemble S ′ de S est dit clos par le haut si pour tout s1 ∈ S ′ et pour tout
s2 ∈ S tel que s1 ≤ s2 , s2 ∈ S ′ . La clôture par le haut d’un sous-ensemble S ′ de S, dénoté par ↑ S ′ est
le plus petit sous-ensemble clos par le haut contenant S ′ . Il correspondant à :

↑ S ′ = s2 | ∃ s1 ∈ S ′ . s1 ≤ s2 .

Dans la suite, on suppose que (S, ≤) est un bel ordre partiel.

Question 1. Montrez les propriétés suivantes sur les beaux ordres partiels :
1. Un sous-ensemble S ′ ⊆ S a un nombre fini d’éléments minimaux.
2. Un ensemble S ′ clos par le haut est égal à la clôture par le haut de l’ensemble de ses éléments minimaux,
c’est-à-dire
S ′ = ↑ min(S ′ ).

3. Toute suite S0 ⊆ S1 ⊆ . . . ⊆ Sn ⊆ . . . de sous-ensembles de S clos par le haut est stationaire, c’est-à-dire

qu’il exists N tel que pour tout n ≥ N , SN = Sn .

Solution : 1. Supposons que nous avons un sous-ensemble S ′ avec un nombre infini d’éléments minimaux. On
a donc au moins une suite infinie
s0 , . . . , s n , . . .

d’éléments minimaux de S ′ deux à deux distincts. Comme ≤ est beau, il existe une paire croissante i < j et
si ≤ sj . Comme sj est minimal, on obtient une contradiction.
2. Soient min(S ′ ) = {s1 , . . . , sn } Par définition, s1 , ..., sn appartiennent à S ′ . Comme S ′ est clos par le haut
et ↑ {s1 , . . . , sn } est le plus petit clos par le haut contenant s1 , ..., sn , alors ↑ {s1 , . . . , sn } ⊆ S ′ . Dans
l’autre sens, il suffit de montrer que pour tout s ∈ S ′ , il existe un élément minimal s′ de S ′ tel que s′ ≤ s.
Supposons que cela ne soit pas le cas et que l’on a un élément s ∈ S qui ne soit pas au-dessus d’un élément
minimal. En particulier, s n’est pas minimal. On contruit alors une suite strictement décroissante d’éléments
non-minimaux dans S ′ par récurrence. On commence par définir s0 = s. Si on suppose s0 , ..., sn construite,
comme sn n’est pas minimal, il existe sn+1 ∈ S ′ \ {sn } tel que sn+1 ≤ sn . Si sn+1 était minimal, alors s
serait au-dessus d’un élément minimal, ce qui est impossible par hypothèse. Maintenant, comme ≤ est beau,
il existe une paire croissante ce qui contredit la décroissance stricte.
3. Supposons que nous ayons une suite non-stationnaire. Nous ponvons en extraire une suite strictement crois-
sante d’ensembles clos par le haut S0 ⊂ S1 ⊂ . . . ⊂ Sn ⊂ . . ..
Pour tout n, il existe donc sn ∈ Sn+1 \ Sn . Comme ≤ est beau, il existe toutefois une paire croissante, i < j
et si ≤ sj . Comme si ∈ Si+1 et Si+1 est clos par le haut, sj ∈ Si+1 . Comme sj ∈
/ Sj et Si+1 ⊆ Sj (car i < j),
/ Si+1 . Contradiction.
sj ∈

42
 Un système de transition est un couple (S, →) où S est un ensemble (d’états) et →⊆ S × S est
une relation (de transition). Nous noterons s1 → s2 pour (s1 , s2 ) ∈→. Nous noterons →∗ pour la
clôture reflexive et transitive de →, c’est-à-dire, s →∗ s′ si et seulement s’il existe une suite finie
s = s0 → s1 → . . . → sn = s′ pour un n ≥ 0. Un système de transition bien structuré est un
triplet (S, →, ≤) où (S, →) est un sytème de transition et (S, ≤) est un bel ordre partiel, satisfaisant la
condition de compatibilité : si s1 → s2 et s1 ≤ s3 , alors il existe s4 tel que s2 ≤ s4 et s3 → s4 .

Question 2. Nous appelons système d’addition de vecteurs avec états un quadruplet (d, V, Q, E) avec d ∈ N∗ ,
V ⊆ Zd et (Q, E) un graphe dirigé fini avec nœuds Q et arêtes E. Étant donné un tel quadruplet (d, V, Q, E),
montrez que la donnée de (S, →, ≤) avec :
— S = Q × Nd ,
— (q, u) → (p, v) si (q, p) ∈ E et v − u ∈ V ,
— (q, u) ≤ (p, v) si q = p et u ≤ v pour l’ordre produit, c’est-à-dire si u = (u1 , . . . , ud ) et v = (v1 , . . . , vd ), u ≤ v
si pour tout i, ui ≤ vi ,
est un système de transition bien structuré.

Solution : On vérifie toutes les propriétés de la définition :

— ≤ est un ordre partiel : parce que l’égalité sur les états et l’ordre produit sur les vecteurs sont des ordres
partiels.
— ≤ est un bel ordre partiel : suppose une suite infinie

(q0 , u0 ), . . . , (qn , un ), . . .

Par le principe des tiroirs, comme Q est fini, il existe q et une sous-suite infinie de la forme

(q, v0 ), . . . , (q, vn ), . . .

Donc il suffit de montrer que l’ordre produit sur les vecteurs est un beau quasi-ordre, par induction sur d > 0.
— d = 1 : si on supppose une suite infinie d’entiers naturels i0 , . . . , in , . . .. On peut en réalité montrer
qu’il y a une sous-suite infinie croissante. Soit la suite est bornée et par le principe des tiroirs il y a une
sous-suite constante. Soit la suite est non-bornée et on peut construire une sous-suite inifinie strictement
croissante par induction. En effet, définissons une fonction φ : N → N strictement croissante telle que
pour tout j < k, iφ(j) < iφ(k) , par récurrence forte : φ(0) = 0 ; supposons que φ est définie sur {0, . . . , j}
comme la suite des in est non-bornée, il existe un élément de la liste strictement plus grand que iφ(j) .
On définit φ(j + 1) comme l’indice de cet élément.
— d + 1 : On suppose une suite infinie de Nd+1 , vue comme une suite de Nd × N :

(u0 , i0 ), . . . , (un , in ), . . .

Par le cas précédent, on a une sous-suite infinie

(uφ(0) , iφ(0) ), . . . , (uφ(n) , iφ(n) ), . . .

telle que
iφ(0) , . . . , iφ(n) , . . .
la deuxième composante est strictement croissante. En appliquant l’hypothèse de récurrence sur

uφ(0) , . . . , uφ(n) , . . .

on obtient une paire croissante j < k et uφ(j) ≤ uφ(k) et donc (uφ(j) , iφ(j) ) ≤ (uφ(k) , iφ(k) ).

43
 — si (q, u) → (p, v) et (q, u) ≤ (r, w), alors q = r et v − u ∈ V . Montrons que (p, w + (v − u)) convient :
— (r, w) → (p, w + (v − u)) : comme q = r et (q, p) ∈ E, (r, p) ∈ E. De plus, w + (v − u) − w = v − u ∈ V .
— (p, v) ≤ (p, w + (v − u)) : On a
v = u + (v − u) ≤ w + (v − u)
parce que u ≤ w. Au passage, cela prouve que w + (v − u) ∈ Nd et donc est un état valide.

Étant donné un sous-ensemble S ′ de l’ensemble des états S d’un système de transition bien structuré,
on définit

Pred S ′ = s ∈ S | ∃ t ∈ S ′ . s → t

Question 3. Montrez que pour tout S ′ ⊆ S, ↑ Pred (S ′ ) ⊆ Pred ( ↑ S ′ ). Donnez un contre-exemple à l’inclusion
inverse.

Solution : Soit s′ ∈ ↑ Pred (S ′ ). Cela signifie qu’il existe s ∈ Pred (S ′ ) avec s ≤ s′ , et donc qu’il existe t ∈ S ′
avec s → t. Comme le système est bien structuré, il existe t′ tel que t ≤ t′ et s′ → t′ . C’est-à-dire t′ ∈ ↑ S ′ et
s′ ∈ Pred ( ↑ S ′ ).
Pour le contre-exemple, construisons un système d’addition de vecteurs avec un état (donc on va l’ignorer). Choi-
sissons d = 1, V = {−1} et S ′ = {0}. Dans ce cas, ↑ S ′ = Pred ( ↑ S ′ ) = N et Pred (S ′ ) = ↑ Pred (S ′ ) = ∅.

Question 4. En utilisant justicieusement les questions 1 et 3, donner un algorithme pour résoudre le problème
de décision suivant (problème de couvrement).
Entrées : (S, →, ≤) un système bien structuré, s, t deux états
Question : existe-t-il t′ tel que s →∗ t′ et t′ ≥ t ?
Nous ne supposerons pas que S est fini, et vous devrez donc faire particulièrement attention à la représentation
des sous-ensembles à manipuler. Vous pourrez néanmoins supposer par exemple que la relation ≤ est calculable,
c’est-à-dire qu’elle est donnée par un algorithme de la forme :
Entrées : s, t deux états
Question : s ≤ t ?
Suivant cette idée, quelles hypothèses devez-vous ajouter à (S, →, ≤) pour faire fonctionner l’algorithme ?

Solution : Par les questions 1.1 et 1.2, on observe que l’on peut représenter de manière canonique un ensemble
clos par le haut par un sous-ensemble fini de S. En effet, la question 1.2. montre que l’ensemble de ses éléments
minimaux (qui est fini par la question 1.) caractérise de manière unique un ensemble clos par le haut.

L’idée de l’algorithme est de construire la suite Sk = s′ | ∃t′ ≥ t. s′ →k t′ . Pour cela, on montre que Sk est clos
par le haut par récurrence sur k.
— k = 0 : S0 est précisément la clôture par le haut de t.
— Supposons Sk est clos par le haut. Par définition, Sk+1 = Pred (Sk ) qui est clos par le haut par la question 5.
S
Maintenant, les ensembles Tk = ki=0 Si forment une suite croissante de clos par le haut, et par la question 1.3.,
S SN
cette suite est stationnaire. De plus, le problème de couvrement se traduit comme s ∈ +∞ k=0 Sk = k=0 Sk pour
un certain N .
Cela amène à l’Algorithme 1.
Maintenant, pour rendre cet algorithme faisable, il est nécessaire de représenter de manière finie les ensembles Sk
et Tk à l’aide des éléments minimaux. Initialement, min(T0 ) = min(S0 ) = {t}.

44
Algorithme 1 Squelette de l’algorithme
Argument : (S, →, ≤) un système bien structuré, s, t deux états
Ensure: existe-t-il t′ tel que s →∗ t′ et t′ ≥ t ?
1: T0 ← ↑ {t}
2: S1 ← Pred ( ↑ {t})
3: tant que Sk+1 ̸⊆ Tk faire
4: Tk+1 ← Tk ∪ Sk+1
5: Sk+2 ← Pred (Sk+1 )
6: fin tant que
7: renvoyer s ∈ T∞ ? ▷ T∞ est le dernier Tk après la boucle while.

Supposons que nous puissions calculer min(Tk ) et min(Sk ).

Supposons tout d’abord que nous savons calculer min(Sk+1 ). Comme Tk+1 = Tk ∪Sk+1 , min(Tk+1 ) = min(min(Tk )∪
min(Sk+1 )). Comme nous savons calculer min(Tk ) et min(Sk+1 ) et que ceux-ci sont des ensembles finis, il suffit de
savoir calculer les éléments minimaux d’ensembles finis. Ceci demande qu’un nombre fini de comparaisons, et cela
est possible dès que ≤ est décidable, c’est-à-dire que nous avons algorithme qui décide le problème :
Entrées : deux états s et t
Question : s ≤ t ?
C’est la première hypothèse que nous ajoutons.
S  S
Maintenant, comme Sk+1 = Pred (Sk ) = Pred ( ↑ min(Sk )) = Pred s′ ∈min(Sk ) ↑ {s′ } = s′ ∈min(Sk ) Pred ( ↑ {s′ }),
et que min(Sk ) est fini, il suffit de pouvoir calculer min(Pred ( ↑ {s′ })) pour chaque s′ , c’est-à-dire d’avoir un algo-
rithme PredClot(s′ ) résolvant le problème suivant :
Entrées : un état s′
Sortie : min(Pred ( ↑ {s′ })).
Ceci est la deuxième hypothèse à ajouter.
Enfin, il faut vérifier que les tests des lignes 3 et 7 soient décidables avec ces représentation. Tout d’abord, le test
de la ligne 3, demande de tester l’inclusion d’un clos par le haut dans un autre. Cela peut se faire avec un nombre
fini de comparaisons : il suffit de vérifier si tous les éléments minimaux de Sk+1 sont plus grands qu’au moins un
élément minimal de Tk . Ceci est décidable par la première hypothèse. Le test de la ligne 7 demande à décider si
s ∈ TN . Pour cela, il suffit de vérifier qu’il existe s′ ∈ min(TN ) tel que s′ ≤ s, ce qui demande qu’un nombre fini
de comparaisons ce qui est décidable par la première hypothèse. Ceci donne donc l’Algorithme 2.

Question 5. Vérifiez que les systèmes d’addition de vecteurs avec états tels que V est fini satisfont les conditions
supplémentaires de la question précédente.

Solution : La première hypothèse est évidente. Pour la deuxième hypothèse, fixons (q, u) ∈ Q × Nd . Démontrons
que n o
Pred ( ↑ {(q, u)}) = (p, v) ∈ Q × Nd | (p, q) ∈ E ∧ ∃w ∈ V. u − w ≤ v .

En effet, (p, v) ∈ Pred ( ↑ {(q, u)}) si et seulement si (p, q) ∈ E et il existe u′ tel que u′ − v ∈ V et u ≤ u′ . En
prenant w = u′ − v, ceci est vrai si et seulement si il existe w ∈ V et que u ≤ w + v, c’est-à-dire u − w ≤ v.
Pour calculer les éléments minimaux de cet ensemble, il faut toutefois être attentif : étant donné w ∈ V , u − w
n’appartient pas forcément à Nd . Définissons u ⊖ w ∈ Nd tel que si u = (u1 , . . . , ud ) et w = (w1 , . . . , wd ), u ⊖ w =
(max(u1 − w1 , 0), . . . , max(ud − wd , 0)). Par l’égalité précédente, on a alors :

Pred ( ↑ {(q, u)}) = ↑ {(p, u ⊖ w) | (p, q) ∈ E ∧ w ∈ V }

et donc
min(Pred ( ↑ {(q, u)})) = min({(p, u ⊖ w) | (p, q) ∈ E ∧ w ∈ V }).

45
Algorithme 2 Algorithme plus précis
Argument : (S, →, ≤) un système bien structuré, s, t deux états
Ensure: existe-t-il t′ tel que s →∗ t′ et t′ ≥ t ?
fonction NonInclusion(A, B) ▷ Prend A et B ensembles finis et retourne ↑ A ̸⊆ ↑ B ?
pour x ∈ A faire
pour y ∈ B faire
si y ̸≤ x alors
renvoyer Vrai
fin si
fin pour
fin pour
renvoyer Faux
fin fonction
fonction Appartient(A) ▷ Prend A ensemble fini et retourne s ∈ ↑ A ?
pour x ∈ A faire
si x ≤ s alors
renvoyer Vrai
fin si
fin pour
renvoyer Faux
fin fonction S
fonction Union(L) ▷ Prend L liste d’ensembles finis et retourne min A∈L A
si L = [] alors
renvoyer {}
fin si
A ← hd(L)
M ← Union(tl(L))
pour x ∈ A faire
nonDansClotM ← Vrai
pour y ∈ M faire
si y ≤ x alors
nonDansClotM ← Faux
Break
fin si
si x ≤ y alors
Retirer y de M
fin si
fin pour
si nonDansClotM alors
Ajouter x à M
fin si
fin pour
renvoyer M
fin fonction
fonction Converture
T ← {t}
S ← PredClot(t)
tant que NonInclusion(S, T ) faire
T ← Union([T, S])
S ← Union([PredClot(s′ ) pour s′ ∈ S])
fin tant que
renvoyer Appartient(T ) ?
fin fonction

46
Comme l’ensemble {(p, u ⊖ w) | (p, q) ∈ E ∧ w ∈ V } est fini, on peut calculer son ensemble des éléments minimaux
par un nombre fini de comparaisons.

Fixons un état s ∈ S. L’arbre fini d’accessibilité depuis s est l’arbre T défini par les propriétés suivantes :
— Chaque nœud de cet arbre est étiqueté par un état s′ ∈ S.
— La racine est étiquetée par s.
— Si un nœud étiqueté par s′ est subsumé, c’est-à-dire, s’il existe un ancêtre s′′ dans cet arbre tel
que s′′ ≤ s′ , alors ce nœud est une feuille.
— Sinon, un nœud étiqueté par s′ a un enfant étiqueté par s′′ pour chaque s′ → s′′ .
Jusqu’à la fin de ce sujet, nous supposerons que l’ensemble

Post (s) = s′ | s → s′

est fini pour tout s ∈ S.

Finalement, nous pourrons utiliser sans justification le théorème de König : un arbre a un nombre fini
de nœuds si et seulement si chacun de ses nœuds a un nombre fini d’enfants et si toutes ses branches
sont de longueur finie.

Question 6. Montrez que cet arbre est fini.

Solution : On utilise le théorème de König. Le branchement fini est par hypothèse. Montrons que toute branche
est finie. En effet, si cet arbre a une branche inifinie, alors nous avons une suite infinie :

s = s0 → s1 → . . . → sn → . . .

avec pour tout i < j, si ̸≤ sj (sinon sj est subsumé et n’aurait pas d’enfant). Cela contredit le fait que (S, ≤) est
un beau ordre partiel.

Nous supposerons que le système bien structuré est strictement compatible, c’est-à-dire, que si s1 → s2
et s1 < s3 alors il existe s4 tel que s2 < s4 et s3 → s4 .

Question 7. Dans le même esprit que la question 4, donnez un algorithme pour résoudre le problème de décision
suivant (problème de bornitude) :
Entrées : (S, →, ≤) un système bien structuré avec compatibilité stricte, s un état
Question : L’ensemble Post∗ (s) = {s′ | s →∗ s′ } est-t-il fini ?

Solution : Il faut d’abord décrire un algorithme pour calculer l’arbre fini d’accessibilité, voir 3. Cet algorithme
termine pour les raisons suivantes :
— La boucle "pour" (lignes 14-18) termine par branchement fini.
— La boucle "tant que" interne (lignes 8-10) termine parce que tout noœud n’a qu’un nombre fini d’ancêtres.
— La boucle "tant que" externe (lignes 3-19) termine parce que chaque itération soit ajoute un nœud dans T ,
soit n’ajoute pas de nœud dans T et enlève un élément de L et comme l’arbre fini d’accessibilité est fini par
la question précédente.

47
Algorithme 3 Algorithme pour l’arbre d’accessibilité
Argument : (S, →, ≤) un système bien structuré, s un état
Ensure: T arbre fini d’accessibilité depuis s
1: T = arbre avec un noeud étiqueté par s et sans enfant
2: L = [T ] liste contenant que la racine
3: tant que L n’est pas vide faire
4: T ′ = hd(L)
5: s′ = étiquette de T ′
6: L = tl(L)
7: T ′′ = parent de T ′
8: tant que T ′′ n’est pas la racine et T ′′ ne subsume pas T ′ faire
9: T ′′ = parent de T ′′
10: fin tant que
11: si T ′′ n’est pas la racine alors
12: Continue ▷ T ′ est subsumé et donc n’a pas d’enfant
13: fin si
14: pour s′′ tel que s′ → s′′ faire
15: T ′′ = arbre avec un nœud étiqueté par s′′ et sans enfant
16: Ajoute T ′′ à L
17: Ajoute T ′′ aux enfants de T ′
18: fin pour
19: fin tant que
20: renvoyer T

De plus, pour écrire cet algorithme, il est nécessaire que 1) il existe un algorithme pour décider ≤, 2) un algorithme
qui, étant donné un état s′ , liste les éléments de Post (s′ ).
Maintenant, la bornitude peut se voir sur l’arbre d’accessibilité de la manière suivante. L’ensemble Post∗ (s) =
{s′ | s →∗ s′ } est infini si et seulement si il existe une feuille étiquetée par s′ qui soit subsumée par un nœud
étiqueté par s′′ avec s′′ < s′ .
En effet, supposons qu’il existe une telle feuille s′ et un nœud s′′ qui le subsume strictement. On définit une
suite infinie d’états de la façon suivante. Soit s′′ = s0 → s1 → . . . → sn = s′ le chemin de s′′ à s′ dans l’arbre
d’accessibilité. Comme s′′ < s′ , n > 0. Nous étendons cela en une suite (si )i∈N telle que :
— pour tout i, si → si+1 ,
— pour tout i, si < si+n
par récurrence forte. Tout d’abord, nous observons que ces deux propriétés sont vraies pour 0 ≤ i < n. Supposons
maitenant que si est défini pour 0 ≤ i ≤ p pour p ≥ n. Par hypothèse de récurrence, sp−n → sp−n+1 et sp−n < sp .
Par compatibilité stricte, il existe sp+1 tel que sp−n+1 < sp+1 et sp → sp+1 comme voulu. Par conséquent,
l’ensemble {sin | i ∈ N} est un sous-ensemble infini de Post∗ (s).
Dans l’autre sens, supposons que Post∗ (s) est infini. Définissons l’arbre suivant :
— ses nœuds sont les séquences finies s = s0 → s1 → . . . sn telles que si ̸= sj pour i ̸= j,
— la racine est s,
— le parent de s = s0 → s1 → . . . sn pour n > 0 est s0 → s1 . . . → sn−1 .
Comme Post∗ (s) est infini, cet arbre a un nombre infini de nœuds. Par le théorème de König, comme cet arbre est
à branchement fini, il a une branche infinie. Cette branche infinie correspond à une suite infinie :

s = s0 → s1 → . . . sn → . . .

où tous les sn sont deux-à-deux différents. Par définition de l’arbre d’accessibilité, il y a un préfixe maximal de
cette suite
s = s0 → s1 → . . . si

48
qui est un chemin dans l’arbre d’accessibilité. Comme ce chemin est maximal, cela signifie que si est une feuille de
l’arbre d’accessibilité. Comme si → si+1 , par définition de l’arbre d’accessibilité, cela signifie qu’il existe j < i tel
que sj ≤ si . Comme sj ̸= si , sj < si comme annoncé.
Finalement, cette caractérisation de la bornitude en terme de feuilles de l’arbre d’accessibilité se teste par un
nombre fini de comparaisons.

49
 Réseaux booléens et leurs points fixes

Un réseau booléen à n composantes est une fonction f : {0, 1}n → {0, 1}n . Une configuration de f est
un n-uplet x ∈ {0, 1}n . La i-ème composante de x est notée xi . Pour 1 ≤ i ≤ n, la i-ème composante
de f (x) est notée fi (x), où fi est une fonction de {0, 1}n dans {0, 1}. On note également ej le n-uplet
ne comportant qu’un seul “1” en position j.
L’ensemble des configurations est muni de la relation d’ordre partielle : x ≤ y ⇐⇒ ∀i, xi ≤ yi . Si x et
y sont deux configurations, on note x + y l’addition modulo 2 composante à composante.
Un graphe signé est un couple G = (V, E) où E ⊆ V × V × {−1, 1}. V est l’ensemble des sommets, E
l’ensemble des arcs, qui peuvent être positifs (signe 1) ou négatifs (signe -1). Il est possible d’avoir à la
fois un arc positif et un arc négatif d’un sommet vers un autre. On note |G| le graphe orienté obtenu
en ignorant les signes. On étend la notion de signe à tout chemin de G en faisant le produit des signes
des arcs.
Le graphe d’interaction d’un réseau booléen f est le graphe signé G(f ) défini comme suit. L’ensemble
des sommets est V = {1, . . . , n}. Pour tout i, j ∈ V , il existe un arc positif (resp. négatif) j → i si et
seulement si il existe une configuration x telle que xj = 0 et fi (x + ej ) − fi (x) est strictement positif
(resp. négatif). En d’autres termes, un arc j → i signifie que fi dépend de la j-ème variable. Si l’arc
est positif, on dit que j est un activateur de i. Si l’arc est négatif, on dit que j est un inhibiteur de i.

Question 1. Soit le réseau booléen à 3 composantes suivant :

f1 (x) := x3 ∧ (¬x1 ∨ ¬x2 )

f2 (x) := x3 ∧ x1
f3 (x) := x2

Calculer la sortie de f sur chaque entrée possible et donner le graphe G(f ).

On note : x ≤G i y si et seulement si xj ≤ yj pour tous les activateurs j de i, et xj ≥ yj pour tous les

inhibiteurs j de i.
Pour deux configurations x, y, on note ∆(x, y) ⊆ {1, . . . , n} l’ensemble des positions où elles diffèrent,
et la distance de Hamming entre x et y est |∆(x, y)|.

Question 2. Soit f un réseau Booléen et G son graphe d’interactions. Soit x ̸= y tels que x ≤G
i y.
1. Supposons qu’il existe j tel que xj < yj . Montrer que x + ej ≤G
i y et fi (x + ej ) ≥ fi (x).
2. Supposons qu’il existe j tel que yj < xj . Montrer que x ≤i y + ej et fi (y + ej ) ≤ fi (y).
G

Dans les questions suivantes on considère un graphe signé à n sommets {1, . . . , n} noté G, et on note
F (G) l’ensemble des réseaux booléens qui ont G pour graphe d’interactions.

Question 3. Montrer que si f ∈ F (G), alors pour tout 1 ≤ i ≤ n et toutes configurations x, y :

x ≤G
i y =⇒ fi (x) ≤ fi (y)

On procédera par induction sur la distance de Hamming entre x et y.

50
 Pour un réseau booléen f , un point fixe de f est une configuration x telle que f (x) = x.
De plus, pour un graphe G on note G[U ] le sous-graphe induit par le sous-ensemble de sommets U ,
c’est-à-dire en retirant les sommets hors de U et les arcs attachés.

Question 4. Soit f ∈ F (G) avec deux points fixes distincts x et y. Montrer qu’il existe deux sommets i, j (pas
nécessairement distincts) tels que G a un arc j → i de signe (yj − xj )(yi − xi ).

Question 5. Montrer que si f ∈ F (G) a deux points fixes distincts x et y, alors G[∆(x, y)] possède un cycle
positif.

On admet le théorème suivant.

Si G est fortement connexe et sans cycle négatif, alors il existe une partition de ses
sommets en deux ensembles A et B telle qu’un arc (u, v) de G est positif si et seulement si
u et v sont dans la même partie.
Un réseau est dit monotone si pour toutes configurations x, y :

x ≤ y =⇒ f (x) ≤ f (y)

Question 6. Montrer que si G est fortement connexe et sans cycle négatif, alors il existe une configuration z telle
que, pour tout f ∈ F (G), le réseau h(x) := f (x + z) + z est monotone.
Montrer que le graphe d’interactions de h s’obtient à partir de celui de G en rendant positifs tous les arcs.
Indice : Commencer avec une partition des sommets A, B donnée par le théorème. Définir z par zi = 1 si i ∈ A
et zi = 0 sinon.

Question 7. Montrer que si G est fortement connexe et sans cycle négatif, alors tout f ∈ F (G) a au moins deux
points fixes.

Question 8. Montrer que si G n’a pas de cycle négatif, alors tout f ∈ F (G) a au moins un point fixe.

51
 Tri parallélisable

Dans tout l’énoncé, on note Ja, bK l’intervalle entier {a, a + 1, . . . , b}.

Soit n ≥ 2 un entier.
Comparateur. Soit i, j ∈ J1, nK deux entiers distincts. Le comparateur de i vers j, noté i •→ j, est défini
sur les suites d’entiers (u1 , . . . , un ) par i •→ j(u1 , . . . , un ) = (v1 , . . . , vn ) avec :

vi = min(ui , uj ), vj = max(ui , uj ), et ∀k ̸∈ {i, j}, vk = uk .

Exemple. 2 •→ 3(10, 7, 5, 20) = (10, 5, 7, 20).

Multicomparateur. Un multicomparateur est un ensemble de comparateurs {a1 •→ a2 , . . . , a2ℓ−1 •→ a2ℓ }
tel que les ak sont deux à deux distincts. En tant que fonction, un multicomparateur est interprété
comme la composition des comparateurs qu’il contient (l’ordre de composition n’a pas d’importance).
Exemple. {1 •→ 2, 3 •→ 4} est un multicomparateur, mais pas {1 •→ 2, 2 •→ 3}.
Réseau. Un réseau est une suite de multicomparateurs. En tant que fonction, un réseau est interprété
comme la composition des multicomparateurs qu’il contient, dans l’ordre de la suite (premier multi-
comparateur en premier). La profondeur du réseau est la longueur de la suite qui le définit.
Exemple. ({1 •→ 2, 4 •→ 3}, {2 •→ 3}) est un réseau de profondeur 2, qu’on peut représenter comme suit.
1 2 3 4

Réseau de tri. Un réseau de tri est un réseau R avec la propriété que pour toute suite d’entiers
(u1 , . . . , un ) en entrée, R(u1 , . . . , un ) renvoie la suite triée par ordre croissant.
Exemple. ({1 •→ 2}, {1 •→ 3}, {2 •→ 3}) est un réseau de tri de profondeur 3 sur n = 3 éléments.

Question 1. Construire un réseau de tri de profondeur 3 pour n = 4.

Solution : Une solution est ({1 •→ 2, 3 •→ 4}, {1 •→ 3, 2 •→ 4}, {2 •→ 3}).

1 2 3 4

Une manière de le justifier : ({1 •→ 2, 3 •→ 4}, {2 •→ 4}) garantit que l’élément maximal arrive en position 4. Symétrique-
ment ({1 •→ 2, 3 •→ 4}, {1 •→ 3}) garantit que l’élément minimal arrive en position 1. Donc, après ({1 •→ 2, 3 •→ 4}, {1 •→ 3, 2 •→ 4}),
seuls les éléments en position 2 et 3 peuvent être potentiellement en mauvaise place. Le dernier comparateur 2 •→ 3
s’assure que leur position est correcte.

Question 2. Montrer qu’un réseau de tri sur n éléments doit être de profondeur au moins log2 (n).
Remarque : on préférera si possible un raisonnement sans calculs lourds, et qui donne la borne log2 (n) exactement,
plutôt que de l’obtenir à une constante près.

Solution : Indication : partir de l’élément en position 1 (par exemple), et regarder dans combien de positions
différentes l’élément peut se retrouver après les k premiers multicomparateurs du réseau.

52
On voit facilement que c’est borné par 2k , parce que dans un multicomparateur, chaque position ne peut être
envoyée que sur deux positions possibles. Or si le réseau trie correctement toutes les suites d’entiers, l’élément en
position 1 doit nécessairement pouvoir être envoyé à terme sur toutes les n positions possibles. Il s’ensuit que la
profondeur p du réseau doit satisfaire 2p ≥ n, ce qui conclut la question.
Remarque. Cette approche est déconseillée, mais un certain nombre de candidats connaissent probablement le
résultat qu’un algorithme de tri reposant sur des comparaisons doit effectuer Ω(n log n) comparaisons. En effet un tel
algorithme induit une injection des permutations à n éléments vers la suite binaire des résultats des comparaisons.
Le nombre c de comparaisons satisfait donc 2c ≥ n!. Il pourrait être tentant de s’y ramener en remarquant qu’un
multicomparateur contient au plus n/2 comparateurs, puisque tous les entiers intervenant dans les comparateurs
sont deux à deux distincts. Il s’ensuit immédiatement qu’il doit y avoir Ω(log n) multicomparateurs dans un réseau
de tri. Mais cela ne donne pas immédiatement la forme simple log2 (n) demandée. Obtenir cette forme revient à
montrer log2 (n!) > n/2 · log2 (n), i.e. n! > nn/2 . Pour n pair, cela peut se voir par l’observation i · (n + 1 − i) ≥ n
pour 1 ≤ i ≤ n/2, qui découpe le produit n! en n/2 sous-produits de deux termes, chaque sous-produit étant ≥
n.
n
Le cas n impair se déduit aisément. (Pour montrer log2 (n!) > n/2 · log2 (n), l’utilisation de Stirling ou n! > ne
est aussi possible, mais découragée.)

Question 3. Pour n ≥ 2 quelconque, construire un réseau de tri de profondeur O(n).

Solution : Un point de départ est de remarquer que le tri bulle se traduit naturellement en un réseau :

({1 •→ 2}, {2 •→ 3}, . . . , {n − 1 •→ n},

{1 •→ 2}, {2 •→ 3}, . . . , {n − 2 •→ n − 1},
...,
{1 •→ 2}).

Ce réseau est de profondeur O(n2 ).

Pour obtenir un circuit de profondeur O(n), on peut grouper judicieusement les comparateurs en multicompara-
teurs. Par exemple : on prend chaque comparateur i •→ j, dans l’ordre du réseau, et on le fait « remonter » le plus
haut possible tant qu’il ne croise pas un comparateur où i ou j apparaît. On obtient :

({1 •→ 2},
{2 •→ 3},
{1 •→ 2, 3 •→ 4},
{2 •→ 3, 4 •→ 5},
{1 •→ 2, 3 •→ 4, 5 •→ 6},
{2 •→ 3, 4 •→ 5, 6 •→ 7},
. . .).

Visuellement, si on écrit chaque remontée de bulle sur une ligne, cela revient à grouper les comparateurs suivant
les droites de pente 1/2. Sur le dessin suivant, les comparateurs traversés par la même ligne sont groupés en un
multicomparateur ; les multicomparateurs du réseau correspondent aux lignes qu’on traverse en partant en haut à
gauche et en descendant.

53
 1 •→ 2 2 •→ 3 3 •→ 4 4 •→ 5 ... n − 1 •→ n − 2 n − 2 •→ n − 3 n − 3 •→ n − 4 n − 4 •→ n − 5

1 •→ 2 2 •→ 3 3 •→ 4 4 •→ 5 ... n − 1 •→ n − 2 n − 2 •→ n − 3 n − 3 •→ n − 4

1 •→ 2 2 •→ 3 3 •→ 4 4 •→ 5 ... n − 1 •→ n − 2 n − 2 •→ n − 3

1 •→ 2 2 •→ 3 3 •→ 4 4 •→ 5 ... n − 1 •→ n − 2

.. .. .. .. .
. . . . ..

Autre solution : si n est pair (le cas impair est similaire), on peut aussi répéter n fois la suite de deux multicom-
parateurs
({1 •→ 2, 3 •→ 4, . . . , n − 1 •→ n}, {2 •→ 3, 4 •→ 5, . . . , n − 2 •→ n − 1})
Ceci donne essentiellement un « sur-réseau » du réseau de la solution précédente, dans le sens où le k-ième multi-
comparateur de la première solution est inclus dans le k-ième multicomparateur de la seconde solution.

Rotation. Une suite (u1 , . . . , un ) est une rotation de (v1 , . . . , vn ) s’il existe k ∈ J1, nK tel que

(u1 , . . . , un ) = (vk , vk+1 , . . . , vn , v1 , v2 , . . . , vk−1 ).

Suite vallonnée. Une suite (u1 , . . . , un ) est croissante (resp. décroissante) si pour tout i ∈ J1, n − 1K,
ui ≤ ui+1 (resp. ui ≥ ui+1 ). Une suite (u1 , . . . , un ) est croissante-décroissante s’il existe k ∈ J1, nK tel
que (u1 , . . . , uk ) est croissante et (uk , . . . , un ) est décroissante. Une suite (u1 , . . . , un ) est vallonnée si
elle est une rotation d’une suite croissante-décroissante.

Question 4. Soit n = 2m avec m ≥ 1. Soit M le multicomparateur {1 •→ m + 1, 2 •→ m + 2, . . . , m •→ 2m}. Soit

(u1 , . . . , un ) une suite vallonnée, et soit (v1 , . . . , vn ) = M (u1 , . . . , un ).
a. Montrer que (v1 , . . . , vm ) et (vm+1 , . . . , v2m ) sont vallonnées.
b. Montrer ∀x ∈ {v1 , . . . , vm }, ∀y ∈ {vm+1 , . . . , v2m }, x ≤ y.
Indication : pour ces deux questions, il peut être utile de voir (u1 , . . . , un ) non pas comme une suite quelconque
indexée par J1, nK, mais comme une suite périodique de période n indexée par Z. De même, on peut voir (v1 , . . . , vm )
et (vm+1 , . . . , v2m ) comme deux suites périodiques de période m = n/2. Essayer de construire ces deux dernières
à partir de la première.

Solution :
Indication 2 : en plus de la suite périodique correspondant à (u1 , . . . , un ), considérer aussi la même suite translatée
d’une demi-période (n/2 positions).
Soit (Ui )i∈Z la suite périodique de période n définie par i = j mod n =⇒ Ui = uj , pour i ∈ Z et j ∈ J1, nK.
Soit (Ui′ )i∈Z la suite Ui décalée de n/2 : c’est-à-dire Ui′ = Ui+n/2 . On peut définir (Mi+ )i∈Z et (Mi− )i∈Z par
Mi+ = max(Ui , Ui′ ) et Mi− = min(Ui , Ui′ ) pour i ∈ Z.
Une première observation est que M + et M − sont de période m = n/2. Une deuxième observation est que M − est
constituée d’une répétition de (v1 , . . . , vm ) ; de même M + est une répétition de (vm+1 , . . . , v2m ). Les deux questions
de l’énoncé se traduisent donc en deux questions sur M − et M + , à savoir :
a. Il existe k tel que (Mk− , . . . , Mk+m−1
−
) est croissante-décroissante ; de même pour M + .
b. Tous les éléments de M − sont inférieurs à tous les éléments de M + .

54
Les deux propriétés qu’on souhaite montrer sont clairement invariantes par translation de U , donc sans perte de
généralité on peut supposer que U0 est le minimum de U . Soit r ∈ J1, n−1K minimal tel que que Ur est le maximum
de U . Sans perte de généralité, r < m (quitte à remplacer U par V avec Vi = U−i , qui préserve toutes le propriétés
étudiées). Les deux propriétés demandées sont immédiates sur un dessin.

U′ M+

U M−

i: 0 c r m n 2n 3n

Les propriétés « se voient sur le dessin », mais pour faire plus proprement, on peut raisonner comme suit. Sur
l’intervalle J0, rK, U est croissante, tandis que U ′ est décroissante, nécessairement à valeurs dans JU0 , Ur K (puisque
U0 et Ur sont les minimum et maximum de U ). Il s’ensuit que les deux suites se « croisent », au sens suivant : il
existe c ∈ J1, r − 1K tel que Ui ≤ Ui′ pour i ∈ J0, cK, et Ui′ ≤ Ui pour i ∈ Jc + 1, rK.
— Sur l’intervalle J0, cK, Mi− = Ui , en particulier M − est croissante sur cet intervalle.
— Sur l’intervalle Jc + 1, rK, Mi− = Ui′ , en particulier M − est décroissante sur cet intervalle.
— Sur l’intervalle Jr, m − 1K, M − est le minimum de deux suites décroissantes, donc décroissante.
On conclut que M − est croissante-décroissante sur J0, m − 1K ; noter que les deux intervalles où la suite décroît ont
un point en commun, de sorte que tout se recolle bien. On procède de même pour M + . (Alternativement, on peut
ramener le cas de M + au cas M − déjà traité en remplaçant U par −U .) Le raisonnement précédent montre aussi
que M − est inférieur ou égal à Uc partout ; symétriquement M + est supérieur ou égal à Uc partout ; ce qui donne
la seconde propriété demandée.

Question 5.
a. Soit n = 2k une puissance de 2. Construire un réseau R de profondeur O(log n) tel que pour toute suite
vallonnée (u1 , . . . , un ), R(u1 , . . . , un ) renvoie la suite triée par ordre croissant.
b. Soit n = 2k une puissance de 2. Construire un réseau de tri sur n éléments de profondeur O(log2 n).
c. Même question pour n ≥ 2 quelconque.
Indication. Le lemme suivant est-il vrai ? Sinon, essayer de trouver une condition sur R qui le rende vrai.
Lemme. Étant donné m < n, si on part d’un réseau de tri R sur n éléments et qu’on supprime les compa-
rateurs qui font intervenir des positions > m, on obtient un réseau de tri sur m éléments.

Solution :
a. La question précédente fait tout le travail. En reprenant les notations de cette question, on voit que le
multicomparateur M envoie une suite vallonnée quelconque (u1 , . . . , un ) sur une suite (v1 , . . . , vn ) telle que
tous les éléments de (vm+1 , . . . , v2m ) sont plus grands que tous les éléments de (v1 , . . . , vm ), par la propriété
(a). Il s’ensuit que pour trier (v1 , . . . , vn ) en ordre croissant, il suffit de trier séparément la moitié gauche et
droite. Or par la propriété (b), ces sous-suites gauches et droites sont elles-mêmes vallonnées, donc on s’est
ramené du problème de trier une suite vallonnée de longueur n, au problème de trier deux suites vallonnées
de longueur n/2. Pour initier la récurrence, on remarque qu’il est trivial de trier une suite de longueur 2,
avec un comparateur.
Dans cette construction inductive, lorsqu’on applique un réseau distinct aux moitiés gauche et droite des
positions, ils agissent sur des positions deux à deux distinctes. La profondeur de deux réseaux appliqué en
parallèle est le maximum de la profondeur des deux réseaux. Il s’ensuit dans notre cas que la profondeur du

55
 réseau est exactement k, puisque le « réseau » qui sert dans l’induction est juste un multicomparateur, et
qu’il y a k niveaux d’induction.

b. Supposons qu’on dispose d’une réseau de tri sur n/2 éléments. Pour trier n éléments, on applique notre
réseau sur les n/2 premiers éléments, et le même réseau dans le sens inverse sur les n/2 derniers éléments.
En sortie, on obtient nécessairement une suite croissante sur les n/2 premières positions, puis décroissante
sur les suivantes ; en particulier on obtient une suite vallonnée. Il reste à appliquer le réseau qui trie les suites
vallonnées, qu’on a construit précédemment, pour obtenir un réseau de tri sur n éléments. (A posteriori, le
réseau qu’on a construit dans la question précédente permet de réaliser une fusion au sens du tri fusion,
quitte à trier la seconde suite dans le sens décroissant.)
On obtient ainsi une construction inductive. Chaque niveau d’induction fait intervenir la construction de
tri pour les suites vallonnées, qui a une profondeur O(log n). Il y a log2 n niveaux de récursion : on obtient
finalement une construction de profondeur O(log2 n).
c. Question difficile. Le lemme de l’indication est faux tel quel. Un contre-exemple est le réseau de tri :

({1 •→ 3, 3 •→ 2, 1 •→ 3, 2 •→ 3}).

Pour voir que c’est un réseau de tri, on peut remarquer que les trois premiers comparateurs placent l’élément
minimal en position 1 (en fait, c’est un tri bulle, mais qui intervertit les deux dernières positions) ; ensuite le
comparateur 2 •→ 3 ordonne les deux éléments restants. Maintenant, si on supprime les comparateurs qui font
intervenir la position 3 en espérant obtenir un réseau de tri sur 2 éléments, la déception est inévitable, parce
qu’on obtient en fait le réseau vide.
La condition suivante suffit à rendre le lemme vrai : tous les comparateurs qui interviennent dans le réseau
sont orientés « vers la droite », c’est-à-dire qu’ils sont de la forme i •→ j avec i < j. En effet, dans ce cas, le
réseau « tronqué » à m positions agit sur une suite en entrée (u1 , . . . , um ) exactement comme le réseau de
départ agit sur la suite (u1 , . . . , um , +∞, . . . , +∞) de longueur n. En effet c’est vrai pour chaque comparateur
qui compose le réseau. On conclut qu’on obtient en sortie la suite triée.
Avec cette condition, on s’est ramené à la question suivante : trouver une variante de la construction qu’on
a faite jusqu’ici, où tous les comparateurs vont « vers la droite ».
Dans la construction de la question précédente, on a des comparateurs vers la gauche à cause du fait qu’on
applique un réseau de tri à l’envers sur la moitié droite de l’état, lors de la construction inductive. Cela
venait du fait que le multicomparateur M attendait en entrée une suite croissante-décroissante (ou plus
généralement, vallonnée). On serait sauvé si le multicomparateur M avait le même comportement, avec
en entrée une suite qu’on peut appeler demi-croissante, qui est croissante sur chaque moitié des positions
(J1, n/2K et Jn/2 + 1, nK). Avec ça, on pourrait faire la même récurrence qu’avant sans avoir besoin d’inverser
le tri dans l’induction, et donc sans jamais générer de comparateurs vers la gauche.
On s’est ainsi ramené à devoir créer un réseau qui trie correctement les suites demi-croissantes. Or si on
applique une permutation « miroir » sur la moitié droite de l’état, une suite demi-croissante devient une
suite croissante-décroissante, donc vallonnée. Si on prend le multicomparateur M , et qu’on le compose en
entrée avec une permutation miroir sur sa moitié droite, alors on obtient un multicomparateur qui prend en
entrée une suite demi-croissante, et donne une sortie qui a exactement les même propriétés que M sur une
suite vallonnée. Pour justifier ce point plus en détail : si on applique une permutation de J1, nK à toutes les
positions intervenant dans un multicomparateur (ou dans un réseau), et qu’on applique la même permutation
sur la suite en entrée, on obtient la même sortie que dans le multicomparateur (ou réseau) d’origine avec la

56
 suite d’origine, composé en sortie avec la même permutation. C’est immédiat par composition en vérifiant sur
un comparateur. De plus, les deux propriétés (a) et (b) de la question 4 sont invariantes par la permutation
miroir sur la moitié droite de l’état, qu’on applique ici. Donc en composant M avec cette permutation, on a
bien ce qu’on veut.
Le comparateur obtenu s’écrit explicitement : M ′ = {1 •→ 2m, 2 •→ 2m−1, . . . , m •→ m+1}. On voit qu’il n’utilise
que des comparateurs vers la droite.

=⇒

En conclusion, si on prend le réseau qui trie les suites vallonnées, et qu’on remplace le tout premier multi-
comparateur M par M ′ , on obtient un réseau qui trie les suites demi-croissantes. En utilisant ce réseau dans
la construction inductive, on n’a plus besoin d’inverser le tri sur la moitié droite, et on obtient un réseau
qu’on peut tronquer à volonté comme dans le lemme.

Réseaux équivalents. On dit que deux réseaux sont équivalents s’il est possible de passer de l’un à
l’autre en effectuant uniquement des opérations du type : insérer ou supprimer un multicomparateur
vide ; ou bien, choisir un comparateur dans un des multicomparateurs constituant le réseau, et le
déplacer dans le multicomparateur immédiatement avant ou après. (Cette opération n’est autorisée que
si le multicomparateur d’arrivée reste valide au regard de la définition de multicomparateur.)
Chemins. Soit R un réseau sur n éléments, de profondeur k. Un chemin de R est une suite (c1 , . . . , ck+1 )
de positions (éléments de J1, nK) telle que pour tout i ∈ J1, kK, soit ci+1 = ci , soit ci •→ ci+1 ou ci+1 •→ ci
apparaît dans le i-ième multicomparateur de R (les deux cas ne sont pas exclusifs). La distance du
chemin est le nombre d’indices i ∈ J1, kK tels que le second cas est vrai ; autrement dit, c’est le nombre
de comparateurs par lesquels passe le chemin.

Question 6. Soit R un réseau quelconque. On se pose la question de trouver un réseau de profondeur p minimale
parmi les réseaux équivalents à R.
a. Montrer que p est égale à la distance maximale parmi les chemins de R.
b. Proposer un algorithme en temps polynomial qui prend en entrée un réseau, et renvoie un réseau équivalent
de profondeur minimale.

Solution : La question 6 est juste là pour occuper des candidats exceptionnels au cas où.

a. La question peut se traduire dans le langage des ordres partiels. Étant donné un réseau R fixé, on prend
l’ensemble E de ses comparateurs comme ensemble de base. On définit l’ordre partiel ≤ sur E par a < b
s’il existe un chemin de R qui passe par a puis b, dans cet ordre. L’observation clé est qu’un chemin est une
chaîne maximale pour cet ordre partiel, et réciproquement. De plus, découper le réseau en multicomparateurs
revient exactement à partitionner E en antichaînes. La question qui est posée est donc un corollaire du lemme
de Mirsky :
Lemme de Mirsky. Soit (E, ≤) un ordre partiel. La cardinalité minimale d’une partition de E en antichaînes
est égale à la longueur maximale d’une chaîne de E.
Preuve. Si on a une partition en antichaînes, chaque élément d’une chaîne donnée doit appartenir à une et
une seule antichaîne de la partition. On déduit que la cardinalité de la partition doit être supérieure ou égale

57
 à la longueur de n’importe quelle chaîne. Réciproquement, soit ℓ la longueur de la plus longue chaîne, et soit
1 ≤ k ≤ ℓ. On peut grouper ensemble les éléments de E tels que la plus longue chaîne qui part de l’élément
est de longueur k. On obtient une partition de E en ℓ classes. Or ces classes sont des antichaînes. En effet,
si a, b ∈ E sont tels que la plus longue chaîne qui part de a (resp. b) est de longueur k, a ≤ b serait une
contradiction parce que a serait le début d’une chaîne de longueur k + 1.
b. Vu la réponse à la question précédente, cela revient à calculer, étant donné un ordre partiel, la longueur
f (c) de la plus longue chaîne qui part d’un élément donné c. On peut supposer que l’ordre est donné sous
la forme de l’ensemble R des paires (a, b) de E 2 telles que a < b. En effet, on peut facilement calculer cette
information en temps polynomial à partir du réseau.
Il suffit ensuite de remonter l’ordre par la fin. On prend les éléments a tels que (a, ∗) n’apparaît pas dans R
(qui correspondent aux extrémités de chaînes maximales au sens de l’inclusion). Pour ces éléments, f = 0.
On retire ensuite toutes les paires (∗, a) de R, pour les éléments a obtenus précédemment. On peut calculer
f sur l’ensemble restant par récurrence ; et on lui ajoute 1 partout (parce qu’on a retiré un élément de toutes
les chaînes maximales de l’ensemble d’origine).
(On peut trouver ce processus sans jamais parler d’ordre partiel, mais c’est un langage commode pour le
présenter.)

58
 Raffinement d’évènements

On se place dans un langage récursif, purement fonctionnel, avec des définitions de types inductifs et
un système de types polymorphes similaires à ceux d’OCaml. On pourra utiliser indifféremment du
pseudocode fonctionnel ou de la syntaxe OCaml.
On suppose l’existence :
— de types de bases usuels, comme Bool le type des booléens, Int le type des entiers, String le
type des chaînes de caractères, et Unit le type de l’unique élément ().
— de définitions de types paramétrés avec des constructeurs, comme :
type ArbreB A = Feuille | Noeud A (ArbreB A) (ArbreB A)
— de types enregistrements {a1 : T1 , . . . , an : Tn } qui permettent de définir, par exemple, les points
du plan avec type Point = P {abscisse : Int, ordonnee : Int} qu’on peut utiliser avec, par
exemple, origine = P {abscisse = 0, ordonnee = 0}}.
— de types listes natifs [A] avec les fonctions de manipulation usuelles (construction, longueur, tête,
queue, . . . ).

Un type de machine est un type abstrait, qui représente l’état d’un système. On utilisera M pour
représenter un tel type et m pour représenter des éléments de ce type, appelés machines. L’invariant
d’une machine est un prédicat sur un type de machine, de type M → Bool qui décrit les propriétés
qu’on attend d’un élément de M ; on supposera qu’il est unique (pour chaque type M, on définit un
unique invariant inv_M).
Un évènement d’un type de machine M d’entrée A et de sortie B est la donnée d’un prédicat sur les
machines et les entrées, appelé garde, et d’une fonction des entrées et des machines dans les sorties et
les machines :
type Evenement M A B = E {
garde : A → M → Bool
action : A → M → (B, M)
}

L’idée est qu’étant donnée une machine, un évènement et une entrée, si la garde de l’évènement est
vraie pour la machine et l’entrée, on peut appliquer l’action de l’évènement à la machine et l’entrée et
récupérer une nouvelle machine (la machine dans un nouvel état) et une sortie.
Un évènement est sûr quand l’implication suivante est vraie : "Si l’invariant de la machine est vrai, et
la garde est vraie pour la machine et l’entrée, alors l’invariant de la nouvelle machine obtenue après
l’action est vrai".

Question 1. On considère comme premier type de machine, les compteurs bornés. Un compteur borné est composé
de deux entiers : une valeur maximale, fixe et positive, et une valeur actuelle, comprise entre 0 et la valeur maximale.
Donner une définition des compteurs bornés, de leur invariant, et d’évènements d’incrémentation et de décrémen-
tation. Prouver leur sûreté.

Un raffinement R entre les types de machine M1 et M2 est une relation entre les éléments de M1 et M2
telle que si (m1 , m2 ) ∈ R et l’invariant de m2 est vrai, alors l’invariant de m1 est vrai.

59
Question 2. On dispose d’une fonction lift : M2 → M1 . Quelle condition sur lift permet de construire un
raffinement (non-trivial) entre M1 et M2 ?
L’inverse est-il vrai ?

Question 3. Donner un type de machine représentant les piles de taille bornée, puis exhiber un raffinement entre
les compteurs bornés et ces piles bornées.

Soit un raffinement R entre M1 et M2 .

Soit deux évènements e1 : Evenement M1 A1 B1 et e2 : Evenement M2 A2 B2 .
On dit que e2 raffine e1 vis-à-vis de R (ou simplement e2 raffine e1 quand il est clair de quel raffinement
R on parle) quand il existe deux fonctions
lift_in : A2 → A1
lift_out : B2 → B1
qui vérifient :
— Renforcement : Pour tout x, m1 , m2 tels que m1 R m2 , si e2 .garde x m2 , alors
e1 .garde (lift_in x) m1 .
— Simulation : Pour tout x, m1 , m2 tels que m1 R m2 et e2 .garde x m2 ,
si (b2 , m′2 ) = e2 .action x m2
et (b1 , m′1 ) = e1 .action x m1 ,
alors m′1 R m′2 et b1 = lift_out b2 .

Question 4. Montrer que si e2 raffine e1 et e1 est sûr, alors e2 est sûr.

Question 5. Donner deux évènements pour les piles bornées qui raffinent les évènements des compteurs bornés
vis-à-vis du raffinement de la Question 3.

On définit le type Mealy A B = M {run : A → (B, Mealy A B)}.

Question 6. Le type Mealy A B est-il un type inductif ?

Question 7. Exprimer la définition de l’empilage dans une pile bornée en utilisant le type Mealy A B (pour un A
et un B bien choisis).

Question 8. Tenter d’en induire une fonction evt_vers_Mealy qui prend un évènement et le transforme en
machine de Mealy (en une entité qui utilise un type Mealy A B).

60
 Résolution efficace de systèmes linéaires creux

Notation. Soit K = Z/2Z le corps à deux éléments. On note deg(P ) le degré d’un polynôme P ∈ K[X].
Étant donné P, Q ∈ K[X], on note P rmod Q le reste dans la division euclidienne de P par Q. Un
vecteur x ∈ Kn est implicitement vu commes un vecteur colonne ; sa transposée xt est un vecteur ligne.
La cardinalité d’un ensemble E est notée |E|.
Poids de Hamming. Le poids de Hamming d’un vecteur v ∈ Kn , noté H(v), est le nombre de coor-
données non-nulles du vecteur. De même, le poids de Hamming d’une matrice est le nombre d’entrées
non-nulles de la matrice.
Problème de résolution linéaire. Le problème de résolution linéaire prend en entrée une matrice
M ∈ Kn×n , et un vecteur b ∈ Kn . Il demande de trouver un vecteur x ∈ Kn tel que M x = b, si un tel
x existe, ou de renvoyer ⊥ sinon.
Représentation par indice. Soit M = (mi,j ) ∈ Km×n une matrice. La représentation par indice de
M est l’ensemble {(i, j) : mi,j = 1}. Noter que pour m et n fixés, cette représentation définit la matrice
de manière unique, en utilisant O(H(M )) entiers.
Dans tout l’énoncé, on supposera que la matrice M en entrée du problème de résolution
linéaire est donnée sous forme de sa représentation par indice.

Question 1. Esquisser sans détailler un algorithme en temps O(n3 ) pour résoudre le problème de résolution
linéaire.

Question 2. Soit G = (V, E) un graphe formé d’un ensemble de sommets V , et un ensemble d’arêtes E. Les
arêtes de E sont des paires non-ordonnées {v, w} d’éléments de V , avec v ̸= w. (On suppose que E est implémenté
sous forme d’une liste de paires.) Proposer un algorithme en temps O(|V | + |E|) qui calcule la partition de V en
composantes connexes.
Indication : on pourra d’abord créer un dictionnaire qui à chaque sommet associe la liste de ses voisins.

Question 3.

a. Soit M ∈ Kn×n une matrice telle que chaque ligne de M a un poids de Hamming au plus 2. Proposer un
algorithme qui résout le problème de résolution linéaire pour une telle matrice M , en temps O(n).
b. Même question si chaque colonne de M , et non plus chaque ligne, a un poids de Hamming au plus 2.

Indication : Dans les deux cas, il peut être utile de définir un graphe bien choisi (pas nécessairement le même), et
de chercher d’abord un algorithme en temps O(n2 ), avant de raffiner en temps linéaire.

Polynôme minimalPd’une matrice. Étant donné une matrice M ∈ Kn×n , sonPpolynôme minimal
est le polynôme P = di=0 λi X i ∈ K[X] de degré d ≤ n minimal tel que P (M ) = di=0 λi M i = 0.

Question 4. Proposer un algorithme qui résout le problème de résolution linéaire en temps O(n2 + nH(M )),
lorsque la matrice M en entrée du problème est inversible, et que son polynôme minimal est connu.
Indication : trouver une expression de M −1 sous forme d’un polynôme en M .

61
 Matrice de Hankel. Soit (a0 , . . . , a2n−1 ) une suite d’éléments de K. La matrice de Hankel générée
par cette suite est la matrice M = (mi,j ) ∈ Kn×(n+1) , avec n lignes et n + 1 colonnes, telle que
∀i, j, mi,j = ai+j (on numérote en partant de 0).
 
a0 a1 a2 . . . an
 a1 a2 a3 . . . an+1 
 
 a2 a3 a4 . . . an+2 
M = 
 .. .. .. .. .. 
 . . . . . 
an−1 an an+1 . . . a2n−1

Problème de Hankel. Le problème de Hankel prend en entrée une suite (a0 , . . . , a2n−1 ) d’éléments
de K. Il demande de trouver un vecteur v ∈ Kn+1 non nul tel que M v = 0, où M est la matrice de
Hankel générée par la suite (a0 , . . . , a2n−1 ).
Problème de réduction polynomiale. Le problème de réduction polynomiale prend en entrée une
suite (a0 , . . . , a2n−1 ) d’éléments de K. Il demande dePtrouver un polynôme V ∈ K[X] non nul de degré
2n−1
au plus n tel que deg(V A rmod X 2n ) < n, où A = i=0 ai X i ∈ K[X].

Question 5. Montrer que si on considère le problème de Hankel et le problème de réduction polynomiale tous les
deux avec en entrée
P la même suite (a0 , . . . , a2n−1 ), alors v = (v0 , . . . , vn ) est solution du problème de Hankel si et
seulement si V = ni=0 vi X n−i est solution du problème de réduction polynomiale.

Polynôme minimal d’une suite. Étant donné Pdune suite (v0 , . . . , vm ) d’éléments de K, le polynôme
minimal de cette suite est le polynôme P = i=0 λi X ∈ K[X] de degré d ≤ m minimal tel que
i
P
∀k ≤ m − d, di=0 λi uk+i = 0.

Question 6. Supposons qu’on sait résoudre le problème de réduction polynomiale en temps O(n2 ). On souhaite
maintenant résoudre efficacement le problème de résolution linéaire pour les matrices de faible poids de Hamming.
Pour cela, on introduit deux hypothèses simplificatrices.
— M est inversible, et son polynôme minimal est de degré n.
— Si u, v sont deux vecteurs tirés uniformément et indépendamment dans Kn , alors avec probabilité au moins
2n−1
1/4, le polynôme minimal de la suite (ut M i v)i=0 est de degré n.

a. Montrer qu’avec probabilité au moins 1/4, le polynôme minimal de la suite (ut M i v)2n−1
i=0 ∈ K
2n est égal au

polynôme minimal de M .
b. En déduire un algorithme qui résout le problème de résolution linéaire pour de telles matrices M en temps
O(n2 + nH(M )) en espérance.

Question 7. Donner un algorithme qui résout le problème de réduction polynomiale en temps O(n2 ).

62
 Complexité arithmétique de la factorisation

Dans cet exercice, on s’intéresse à la complexité arithmétique des algorithmes. On utilise les opérations
de base suivantes sur des entiers relatifs : addition, soustraction, multiplication, division euclidienne.
Le coût de chacune de ces opérations est 1, quelle que soit la taille des entiers en entrée et en sortie.
Pour écrire les algorithmes, on se contentera d’un pseudocode simple permettant de compter facilement
ces opérations.
On s’intéresse au problème de la factorisation d’un entier :
Entrée : N = P × Q de taille n bits (c’est-à-dire N < 2n ) où P et Q sont deux nombres premiers
Sortie : P, Q
Notre objectif est de démontrer le résultat suivant :
Il existe un algorithme de factorisation utilisant O(n) opérations arithmétiques.

Question 1. Donner un algorithme pour calculer l’exponentielle en O(n) opérations arithmétiques :

Entrée : N, K de taille n bits
Sortie : N K

Solution : Il s’agit de l’algorithme d’exponentiation rapide.

Question 2. Donner un algorithme pour calculer le PGCD en O(n) opérations arithmétiques :

Entrée : N, M de taille n bits
Sortie : P GCD(N, M )

Solution : Il s’agit de l’algorithme d’Euclide. Nous démontrons qu’il termine en O(n) opérations.
Pour se faire il suffit de noter qu’après deux itérations, les nombres sont réduits de moitié au moins. En effet, si on
suppose que N ≤ M : P GCD(N, M ) = P GCD(M mod N, N ) où M mod N ≤ N , et min(N, M mod N ) ≤ M/2
tandis que max(N, M mod N ) ≤ N . La première inégalité n’est pas triviale, elle se déduit de N +(M mod N ) ≤ M
(car N ≤ M ) et donc que le plus petit des deux est inférieur à M/2.
Par conséquent la somme des tailles des deux nombres décroît d’au moins 1 par itération de l’algorithme, et on
termine (i.e., atteindre 0) en O(n) étapes. Chaque étape coûte O(1) opérations arithmétiques.

Question 3. En supposant qu’il existe un algorithme de calcul de la factorielle :

Entrée : N de taille n bits
Sortie : N !
en F (n) opérations arithmétiques, montrer qu’il existe un algorithme de factorisation de complexité O(n × F (n))
(une preuve de sa correction n’est pas exigée, on se concentrera sur sa description).

Solution : On recherche le plus petit i tel que i! mod N = 0. On aura alors i = max(P, Q).
Pour calculer si i! mod N = 0, il suffit de calculer un reste dans la division euclidienne par N , qui ne coûte qu’une
opération arithmétique par hypothèse de l’énoncé.
Soit i0 = max(P, Q) la valeur que l’on recherche. On effectue une recherche dichotomique de i0 sur l’intervalle [1; N ].
À chaque étape, on regarde si i! mod N = 0 pour le milieu de l’intervalle, si oui on réduit la borne supérieure,
sinon on augmente la borne inférieure.

63
Comme l’intervalle de départ est de taille N , on a O(log N ) = O(n) étapes de calcul. Chacune requiert un calcul
de factorielle et une opération arithmétique.
Notons que l’algorithme ainsi obtenu ne suffit pas à résoudre

le problème de l’énoncé, car même avec un calcul de
la factorielle en O(n) opérations, on obtiendrait O n2 opérations.

Question 4. Dans cette question, on s’intéresse au calcul d’un coefficient binomial.

Entrée : N, M de taille n bits, M ≤ N
N


Sortie : M
Montrer que ce calcul peut être fait en O(n) opérations arithmétiques. On pourra utiliser l’identité suivante :
k  
X
ℓ k ℓj
k
∀k, ℓ ∈ N, (2 + 1) = 2
j
j=0

Solution : On va commencer par implémenter l’opération de sélection :

Entrée : N de taille n bits, deux indices m0 ≤ m1 ≤ n
Sortie : l’entier obtenu en écrivant les bits de N situés entre m0 et m1
L’opération en elle-même est : (N mod 2m1 − N mod 2m0 )/2m0 . Pour simplifier l’exercice, il est raisonnable
d’admettre dans un premier temps que la sélection est toujours en temps O(1). Cependant, on a besoin de connaître
2m0 et 2m1 . Il faudra donc vérifier par la suite que tous les indices nécessaires aux sélections peuvent être précalculés
efficacement.
Pour résoudre le problème il suffit maintenant de :
1. Choisir une valeur de ℓ suffisamment grande : il suffit d’avoir ℓ ≥ k dans l’identité, donc on peut prendre
ℓ = k = N . On a donc :
XN  
N N N Nj
(2 + 1) = 2
j
j=0

On veut donc sélectionner les bits des positions N M à N M + N .

2. Calculer 2N + 1 en O(n) opérations arithmétiques par exponentiation rapide.
3. Calculer (2N + 1)N en O(n) opérations arithmétiques par exponentiation rapide.
4. Calculer 2N M et 2N M +N à l’aide de plusieurs exponentiations rapides (d’abord 2N , puis (2N )M ).
5. Effectuer l’opération de sélection.

Question 5. En utilisant la question précédente, montrer qu’on peut calculer la factorielle en O(n) opérations
arithmétiques.

Solution : On utilise le fait que pour tout entier pair N :

 
N
N! = ((N/2)!)2 .
N/2

Pour commencer on peut décrire un algorithme récursif trivial pour calculer K! :

— Si K est impair, calculer K! = K × (K − 1)!
K

K


— Si K est pair, calculer K/2 avec l’identité de la question 4, et renvoyer K! = K/2 ((K/2)!)2 .


Comme le calcul du coefficient binomial prend O(n) opérations, l’algorithme complet prend O n2 opérations.
Cependant, dans le calcul du coefficient binomial, la complexité est dominée par l’exponentiation (ainsi que les
puissances de 2 pour la sélection). On va donc modifier notre algorithme récursif pour qu’il calcule en même temps
l’exponentiation et la factorielle.

64
Construisons donc un algorithme récursif qui calcule à la fois K!, (2N + 1)K et 2KN . Notons ici que N est devenu
un paramètre fixe, et l’algorithme fonctionne pour K ≤ N . On l’appellera ensuite avec K = N .
En précalcul, on commence par calculer 2N et 2N + 1 en O(n) opérations, dont on aura besoin pour la suite.
Ensuite :
1. Si K est impair, on a K! = K × (K − 1)! et (2N + 1)K = (2N + 1)K−1 (2N + 1), et 2KN = 2(K−1)N 2N , et on
utilise un appel récursif.
2. Si K est pair, on utilise :
 
K
K! = ((K/2)!)2 et (2N + 1)K = ((2N + 1)K/2 )2 et 2N K = (2N (K/2) )2
K/2

— On utilise un appel récursif pour calculer (2N + 1)K/2 et (K/2)! et 2N (K/2)

— On utilise deux opérations arithmétiques pour calculer (2N + 1)K et ((K/2)!)2 et 2N K
K


— On calcule K/2 à l’aide d’une sélection dans les bits de (2N + 1)K (on sélectionne les bits des positions
(K/2)N à (K/2)N + N )
— On en déduit K! par une multiplication

Question 6. Est-ce optimal ?

Solution : Il faut remarquer que si les nombres donnés en entrée sont plus petits que 2n , alors tout algorithme
c
effectuant c opérations arithmétiques ne peut calculer que des nombres plus petits que (2n )2 . En effet, chaque
opération ne peut au maximum que doubler la taille des nombres actuellement en mémoire.
√ n−1 n−1
Prenons 2n > N ≥ 2n−1 . On a asymptotiquement N ! = Θ( 2n−1 2(n−1)2 e−2 ) d’après la formule de Stirling.
Tout algorithme de calcul de la factorielle nécessite donc au moins O(n) opérations arithmétiques. À constante
près, notre algorithme est donc optimal.

Question 7. En adaptant l’algorithme de la question 5, montrer qu’on peut calculer le plus petit entier i tel que
(2i )! ̸= 0 mod N et (2i+1 )! = 0 mod N (sur une entrée N de taille n bits) en O(n) opérations arithmétiques.

Solution : Soit i le plus petit entier tel que 2i > N .

On effectue un appel à la fonction récursive de la question 5 pour calculer (2i )!, avec la modification suivante : à
chaque appel récursif, on mémoise la valeur de sortie. On va donc calculer toutes les factorielles (2j )! pour 1 ≤ j ≤ i.
Pour chacune d’entre elles, on calcule une division euclidienne par N et on trouve le résultat.

Question 8. Donner un algorithme de factorisation utilisant O(n) opérations arithmétiques.

Solution : On commence par utiliser la question précédente. Soit i0 tel que (2i0 )! ̸= 0 mod N et (2i0 +1 )! = 0
mod N . Nous voulons utiliser la même méthode que la question 3 : trouver le plus petit i tel que i! mod N = 0.
Pour rendre le problème un peu plus facile, nous allons trouver le plus petit entier pair satisfaisant cette relation ;
il suffira ensuite de tester i et i − 1.
Nous avons donc un intervalle [2i0 , 2i0 +1 ] à chercher dichotomiquement. On commence par éliminer le cas où
P GCD((2i0 )!, N ) > 1. En effet, si c’est le cas, comme N ne divise pas (2i0 )!, la valeur P GCD((2i0 )!, N ) nous
donnerait un facteur non trivial de N , ce qui termine l’algorithme.
Dans la suite on considère donc : P GCD((2i0 )!, N ) = 1.
Soit I pair dans l’intervalle [2i0 ; 2i0 +1 ]. On a :
 
I
I! = ((I/2)!)2
I/2

65
On sait que P GCD(N, (I/2)!)
= 1, en effet I/2 < 2 et P GCD((2 )!, N ) = 1 par hypothèse. Donc N divise I! si
i0 i0
I
et seulement si N divise I/2 .
Au cours de notre recherche

dichotomique dans l’intervalle [2i0 ; 2i0 +1 ], nous allons donc calculer un certain nombre
I
de coefficients I/2 . Il faut montrer que tous ces coefficients peuvent être calculés en O(n) opérations. Comme
précédemment, on va utiliser la sélection dans le nombre (2N +1)I , et comme précédemment, il faut principalement
vérifier qu’on peut amortir le coût de l’exponentiation (cela vaut à la fois pour (2N + 1)I et pour 2N I , nous écrivons
seulement le premier dans la suite).
La recherche dichotomique va produire O(n) valeurs de I, chacune différant de la précédente par une puissance
j
de 2 qui va en se réduisant. En ayant précalculé les puissances (2N + 1)2 pour tous j, on peut donc obtenir la
nouvelle valeur (2N + 1)I en une seule opération arithmétique, et calculer ensuite le coefficient binomial suivant
par sélection.
Voici l’algorithme complet :
Entrée : i0
Sortie : I ∈ [2i0 ; 2i0 +1 ] tel que I mod N = 0 et I − 2 mod N ̸= 0.
1: Calculer 2N + 1
j
2: Pour j = 1 à i0 , calculer X2j = (2N + 1)2
3: L, R ← 2i0 , 2i0 +1
4: I ← (L + R)/2 ▷ Invariant : I reste pair
5: Calculer X := (2N + 1)I
6: tant que R − L
≥ 4 faire ▷ Invariant : R − L est une puissance de 2
I
7: Calculer I/2 par sélection sur X
I


8: si I/2 mod N = 0 alors
9: R′ ← I ▷ On déplace R vers I
10: I ′ ← I + (R − L)/4
11: X ′ ← X × X(R−L)/4
12: R, I, X ← R′ , I ′ , X ′
13: sinon
14: L′ ← I ▷ On déplace L vers I
15: I ′ ← I − (R − L)/4
16: X ′ ← X/X(R−L)/4
17: L, I, X ← L′ , I ′ , X ′
18: fin si
19: fin tant que

66
 Graphes d’influence

On note Ja, bK l’intervalle entier {a, a + 1, . . . , b}. On note |S| la cardinalité d’un ensemble S.
Graphe simple. Dans tout l’énoncé, on considère des graphes simples : c’est-à-dire qu’ils sont définis
par un ensemble de sommets V , et un ensemble d’arêtes E, et chaque arête est une paire non ordonnée
{i, j} d’éléments distincts de V .
Isomorphisme de graphe. Deux graphes G = (V, E) et G′ = (V ′ , E ′ ) sont dits isomorphes s’il existe
une bijection φ : V → V ′ telle que E ′ = {{φ(i), φ(j)} : {i, j} ∈ E}.
Graphe d’influence. Soit ⃗v = (v1 , . . . , vn ) ∈ Rn . Au vecteur ⃗v , on associe le graphe Infl(⃗v ) = (V, E)
avec pour sommets V = J1, nK, et pour arêtes E = {{i, j} : |vi − vj | < 1}. Un graphe G = (V, E) est
un graphe d’influence s’il existe ⃗v ∈ R|V | tel que G est isomorphe à Infl(v).

Informellement, on peut penser aux sommets i d’un graphe d’influence comme étant des agents ; vi est l’opinion
du i-ième agent ; et un agent influence un autre agent si leurs opinions sont suffisamment proches.

Question 1. Donner un exemple simple de famille infinie de graphes d’influence (deux à deux non isomorphes).
Donner une exemple de graphe qui n’est pas un graphe d’influence.

Question 2.
1. Montrer que tout graphe d’influence G = (V, E) est un graphe d’incomparabilité : c’est-à-dire qu’il existe un
ordre partiel ⪯ sur V tel que {i, j} ∈ E si et seulement si i ̸⪯ j et j ̸⪯ i.
2. Montrer que tout graphe d’influence G = (V, E) est cordal : c’est-à-dire que pour toute suite de sommets
k1 , . . . , km formant un cycle de longueur m > 3, il existe i, j ∈ J1, mK tels que |j − i| =
̸ 1 mod m et
{ki , kj } ∈ E.

Pour G = (V, E) un graphe et i ∈ V , on note G[i] = {j ∈ V : {i, j} ∈ E} ∪ {i} le voisinage de i.

Soit : f : Rn → Rn
P !
j∈Infl(⃗v )[i] vj
(vi )i∈J1,nK 7→ .
|Infl(⃗v )[i]|
i∈J1,nK

Autrement dit, f remplace l’opinion de chaque agent par la moyenne des opinions des agents qui
l’influencent (lui-même compris).
Chaîne d’influence. Une chaîne d’influence est une suite de vecteurs ⃗v k ∈ Rn telle que pour tout
i ∈ N, ⃗v k+1 = f (⃗v k ).
Dans toute la suite, on supposera que le vecteur initial ⃗v 0 d’une chaîne d’influence est
ordonné par ordre croissant : v10 ≤ v20 ≤ · · · ≤ vn0 .

Question 3. Soit (⃗v k )k∈N une chaîne d’influence.

1. Montrer que pour tout k ∈ N, v1k ≤ v2k ≤ · · · ≤ vnk .
2. Montrer que (v1k )k∈N est croissante, et (vnk )k∈N est décroissante.

Question 4. Soit (⃗v k )k∈N une chaîne d’influence. Pour i ∈ J1, nK fixé, on définit la suite uk par uk = 1 si l’arête
{i, i + 1} existe dans Infl(⃗v k ), et uk = 0 sinon. Montrer que (uk )k∈N est stationnaire.
Rappel. Une suite (ak )k∈N est dite stationnaire s’il existe b ∈ N tel que ∀k ≥ b, ak = ab .

Question 5. Montrer que pour toute chaîne d’influence, après un nombre fini d’itérations de f , plus aucun agent
ne change d’opinion. (Autrement dit, toute chaîne d’influence est stationnaire.)

67
Question 6. Donner un algorithme qui, étant donné en entrée une suite stationnaire de graphes (Gi )i∈N (repré-
sentée par un segment initial au-delà duquel la suite reste constante) :
— termine et renvoie VRAI dans le cas où il existe ⃗v 0 ∈ Rn tel que (Gi )i∈N est la suite des graphes d’influence
de la chaîne d’influence initiée par ⃗v 0 ;
— renvoie FAUX ou ne termine pas dans le cas contraire.

Question 7. Montrer que pour tout n ∈ N, il existe un nombre fini de suites de graphes qui sont les graphes
d’influence successifs d’une chaîne d’influence dans Rn .

68
 Calcul de l’arbre de dominance

Dans ce sujet, nous nous intéressons à des graphes orientés enracinés, i.e., G = (V, E, r) où V est
l’ensemble fini des sommets, E l’ensemble des arêtes orientées, r le sommet racine. Nous supposerons
que pour tout sommet v ∈ V il existe un chemin de r à v, noté r →∗ v.
Définition. Étant donné un graphe G = (V, E, r), on dit que x ∈ V domine y ∈ V , noté x > y, si,
x ̸= y et pour tout chemin r = s0 → s1 → . . . → sn = y dans G, il existe i tel que si = x.
On dit que x est un dominant immédiat de y, noté idom(y), si x > y et pour tout z ∈ V tel que z > y
et z ̸= x, on a z > x.
Définition. Étant donné un graphe G = (V, E, r). On note A(G) = (V, Ed , r) où Ed = {x → y | x, y ∈
V et x = idom(y)}.
A(G) est appelé l’arbre de dominance de G.
L’objectif de ce sujet est de calculer efficacement A(G).

Question 1. Donner l’arbre de dominance du graphe donné en Figure 1.

Figure 1 – Graphe de la question 1

Question 2. Montrer que A(G) est bien défini, i.e., idom(x) est bien défini pour tout x ̸= r et A(G) forme un
arbre enraciné en r.

Question 3. a. Donner un algorithme basé uniquement sur des parcours, permettant de calculer A(G).
b. Quelle est sa complexité ?

Soit G = (V, E, r) un graphe. Pour chaque sommet x ∈ V , nous notons i(x) l’indice de visite lors d’un
parcours en profondeur issu de r. Nous notons T (G) l’arbre couvrant obtenu à la fin du parcours, i.e.,
le graphe (V, ET , r) où ET est composé des arcs de liaisons durant le parcours.

Définition. Soit w ̸= r. On note sdom(w) = argminv {i(v) | il existe un chemin v = v0 → . . . → vk =

w dans G tel que i(vj ) > i(w) pour 1 ≤ j ≤ k − 1}.

Question 4.
a. Donner l’arbre couvrant ainsi que les indices de visite obtenus via un parcours en profondeur depuis r dans
le graphe donné en Figure 1.
b. Préciser pour chaque sommet w, le sdom(w) correspondant.

Question 5. Soient x, y ∈ V tels que i(x) ≤ i(y). Montrer que tout chemin x →∗ y dans G contient un sommet
a qui est un ancêtre commun à x et y dans T (G).

69
Question 6. Montrer que pour tout w ̸= r, sdom(w) est un ancêtre de w dans T (G).

Question 7. Montrer que :

sdom(w) = argmin( {i(v) | (v, w) ∈ E and i(v) < i(w)}

∪{i(sdom(u)) | i(u) > i(w) and ∃(v → w) ∈ E tel que u →∗ v dans T (G)} )

Axiome. soit w ̸= r et u = argminu {i(sdom(u)) | sdom(w) →+ u →∗ w dans T(G)}. On a

(
sdom(w) si sdom(w) = sdom(u)
idom(w) =
idom(u) sinon

Question 8. a. Donner un algorithme qui permet de calculer idom(w) pour tout w ̸= r.

Conseil : nous pourrons envisager de re-construire T (G) en partant d’une forêt de sommets et en les fusionnant
lors d’un parcours des sommets dans un ordre décroissant de leur index.
b. Étudier la complexité de l’algorithme. Nous tiendrons compte de la structure de données utilisée pour mani-
puler la forêt.

70
 Forme SSA – placement optimal des fonctions de jointure

Nous considérons le petit langage de programmation composé des commandes suivantes :

Commandes :
P, Q := return exprint Expressions d’entiers :
| x := exprint où x ∈ X exprint := n ∈ Z
| P;Q | x∈X
| if exprbool then P else Q endif | exprint + exprint
| repeat P until exprbool | exprint ∗ exprint
| exprint / exprint
Expressions : | exprint % exprint
exprbool := exprint ◦ exprint avec ◦ ∈ {==, <, ≤}
Définition. Étant donné un programme, son graphe de flot de contrôle (CFG – control flow graph)
est le graphe orienté G = (V, E) tel que V est l’ensemble des points de contrôle du programme (c.-à-d.,
les commandes) et s1 → s2 ∈ E si s2 peut suivre s1 lors de l’exécution du programme.

Définition. Un graphe de flot de contrôle G = (V, E) est sous forme SSA (single-assignment form) si,
pour toute variable x ∈ X , il existe au plus une affectation de x, c.-à-d., au plus un sommet s ∈ V de
la forme x := expr.
Nous supposerons l’existence d’un sommet Entry relié à l’ensemble des points d’entrées du programme.

Une façon classique de mettre un CFG quelconque sous forme SSA est de dupliquer les variables
utilisées plusieurs fois. Une difficulté peut alors apparaître après les boucles repeat ... until ou les
conditionnelles if-then-else ; comment savoir quelle variable utiliser ?
Pour résoudre ce problème, il est habituel d’ajouter au CFG une fonction de jointure, qui prend la
forme d’une affectation xi := φ(xi1 , . . . , xin ) où φ(·) représente une fonction abstraite (c.-à-d., sans
sémantique fixée) lorsque nécessaire. L’arité de la fonction φ(·) dans un sommet s du CFG dépend du
nombre d’affectations de x dont dépend s, c.-à-d., du nombre de sommets s′ contenant une affectation
de x et tel que s est accessible depuis s′ dans le CFG.

L’objectif de ce sujet est de trouver un placement optimal des fonctions de jointure afin d’en réduire le
nombre.

Question 1. a. Donner le CFG correspondant au programme décrit en Figure 1.

b. Mettre ce CFG sous forme SSA.

x := 42;
i := 1;
repeat
if x%2 == 0 then
y := x/2
else y := 3 ∗ x + 1
endif ;
x := y;
i := i + 1;
until i < 10;
return x
Figure 1 – Programme calculant le 10ième terme de la suite de Syracuse commençant à 42.

71
 Étant donné un CFG G = (V, E), on dit que X ∈ V domine Y ∈ V , noté X ≥ Y , si, pour tout chemin
Entry = s0 → s1 → . . . → sn = Y dans G, il existe i tel que si = X.
On dit que X domine strictement Y , noté X > Y , si X domine Y et X ̸= Y .
On note X ̸> Y si X ne domine pas strictement Y .
On note idom(Y ) le plus proche dominant strict de Y .

Question 2. a. Montrer que la relation de domination est une relation réflexive transitive.
b. Montrer que si X →∗ Y est un chemin simple (c.-à-d., sans cycle) et X > Y alors X > Z pour tout Z
appartenant au chemin (et différent de X).
c. En déduire que idom(X) est bien définie pour tout X ̸= Entry.

Soit G = (V, E) un CFG et Gd = (V, Ed ) son arbre de dominance associé, c.-à-d., Ed = {X →

Y | X, Y ∈ V et X = idom(Y )}.
On note :
— DF (X) = {Y | ∃P ∈ V. (P → Y ) ∈ E ∧ X ≥ P ∧ X ̸> Y }
— DF local (X) = {Y | (X → Y ) ∈ E ∧ X ̸> Y }
— DF up (Z) = {Y ∈ DF (Z) | idom(Z) ̸> Y }

S
Question 3. Montrer que DF (X) = DF local (X) ∪ (X→Z)∈Ed DF up (Z).

Question 4. En déduire un algorithme permettant de calculer DF (X) ainsi que sa complexité. Nous supposerons
que nous avons déjà pré-calculé l’arbre de dominance.

Soient p : X0 →+ Xnp et q : Y0 →+ Ynq deux chemins non-nuls dans un CFG. On dit que p et q
convergent vers Z si : (1) X0 ̸= Y0 , (2) Xnp = Ynq = Z, et (3) (Xi = Yj ) ⇒ (i = np ou j = nq ).

Nous notons J(S) = {Z | ∃p : X0 →+ Xnp , q : Y0 →+ Ynq tel que p et q convergent vers Z

et X0 , Y0 ∈ S}.

Question 5. Définir, à partir de la fonction J(·), l’ensemble des sommets où il est nécessaire de placer une fonction
φ(·). Nous supposerons que toutes les variables sont initialisées (avec donc une affectation à ces variables) dans
Entry.
S
Question 6. Nous notons DF (S) = X∈S DF (X) et définissons DF + (S) = limi→+∞ DFi (S) où DF1 (S) =
DF (S) et DFi+1 (S) = DF (S ∪ DFi (S)).
Montrer que pour toute variable x ∈ X , DF + (A(x)) est égal à l’ensemble des positions où nous souhaitons
positionner des fonctions φ(·), avec A(x) = {Z | il y a une affectation de x dans Z}.

Question 7. En déduire un algorithme qui permet de définir les positions où ajouter les fonctions φ. Donner sa
complexité.

72
 Théorème de Hennessy-Milner

Un système de transition étiqueté dans l’alphabet A est un triplet (S, i, ∆) avec S un ensemble (d’états),
a
i ∈ S (état initial) et ∆ un sous-ensemble de S × A × S (transitions). On notera s −−→ s′ pour
(s, a, s′ ) ∈ ∆.
Nous nous intéresserons à une logique pour ces systèmes appelée la logique d’Hennessy-Milner. Ses
formules sont générées par la grammaire :

φ, ψ ::= ⊤ | ¬φ | φ ∧ ψ | ⟨a⟩ φ

avec a ∈ A. Nous disons qu’un état s de (S, i, ∆) satisfait une formule φ et nous notons s ⊨ φ, par
récurrence sur φ :
— s ⊨ ⊤, c’est-à-dire, tout état satifait la formule vraie,
— s ⊨ ¬φ si et seulement si s ̸⊨ φ,
— s ⊨ φ ∧ ψ si et seulement si s ⊨ φ et s ⊨ ψ,
a
— s ⊨ ⟨a⟩ φ si et seulement s’il existe s′ tel que s −−→ s′ et s′ ⊨ φ.
Nous disons qu’un système (S, i, ∆) satisfait une formule φ si i ⊨ φ.

Question 1. Donnez des exemples de formules satisfaites et non satisfaites par le système suivant :

2
b
a
0 1
c
3

La flèche entrante en 0 indique qu’il s’agit de l’état initial.

Solution : Quelques exemples de formules satisfaites :

— ⊤
— ⟨a⟩ ⊤
— ⟨a⟩ ⟨b⟩ ⊤
— ⟨a⟩ ⟨c⟩ ⊤
— ⟨a⟩ (⟨b⟩ ⊤ ∧ ⟨c⟩ ⊤)
— ⟨a⟩ ⟨b⟩ ⊤ ∧ ⟨a⟩ ⟨c⟩ ⊤
— ⟨a⟩ ¬⟨a⟩ ⊤
Quelques exemples de formules non satisfaites :
— ¬⊤
— ¬⟨a⟩ ⊤
— ⟨b⟩ ⊤
— ⟨a⟩ ⟨a⟩ ⊤
— ⟨a⟩ ¬⟨c⟩ ⊤

Question 2. Soient φ = ⟨a⟩ (⟨b⟩ ⊤ ∧ ⟨c⟩ ⊤) et ψ = ⟨a⟩ ⟨b⟩ ⊤ ∧ ⟨a⟩ ⟨c⟩ ⊤. Montrez que φ implique ψ mais pas
inversement, c’est-à-dire, montrez 1) que tout système qui satisfait φ satisfait ψ, mais 2) qu’il existe un système
qui satisfait ψ mais pas φ.

73
Solution : Commençons par 1). En déroulant la définition, il y a équivalence entre tous les énoncés suivants :
— un système (S, i, ∆) satisfait φ,
— i ⊨ φ,
a
— il existe s1 tel que i −−→ s1 et s ⊨ ⟨b⟩ ⊤ ∧ ⟨c⟩ ⊤,
a b c
— il existe s1 , s2 et s3 tels que i −−→ s1 , s1 −−→ s2 et s1 −−→ s3 .
Similairement, il y a équivalence entre :
— un système (S, i, ∆) satisfait ψ,
— i ⊨ ψ,
— i ⊨ ⟨a⟩ ⟨b⟩ ⊤ et i ⊨ ⟨a⟩ ⟨c⟩ ⊤,
a a b c
— il existe t1 , t2 , t3 et t4 tels que i −−→ t1 , i −−→ t2 , t1 −−→ t3 et t2 −−→ t4 .
En prenant t1 = t2 = s1 , t3 = s2 et t4 = s3 , nous remarquons que si un système satisfait φ, il satisfait aussi ψ. Par
contre, le système suivant :

b
1 3
a
0
a
2 c 4

satisfait ψ (prendre ti = i), mais ne satisfait pas φ. En effet, nous avons deux choix : soit s1 = 1, soit s1 = 2.
Dans le premier cas, il n’y a pas de c-transition et s3 ne peut pas être défini. Dans le deuxième, il n’y a pas de
b-transition et s2 ne peut pas être défini.

Une bisimulation entre deux systèmes (S, i, ∆) et (S ′ , i′ , ∆′ ) est une relation R ⊆ S × S ′ entre leurs
états qui satifait les propriétés suivantes :
— (i, i′ ) ∈ R,
a a
— si (s, s′ ) ∈ R et si s −−→ t, alors il existe t′ tel que (t, t′ ) ∈ R et s′ −−→ t′ ,
a a
— si (s, s′ ) ∈ R et si s′ −−→ t′ , alors il existe t tel que (t, t′ ) ∈ R et s −−→ t.
Quand une telle bisimulation existe, nous disons que les systèmes sont bisimilaires.

Question 3. Montrez que les deux systèmes suivants sont bisimilaires :

1 c 1
a a
0 0 c c
b b
2 c 2

Solution : Une bisimulation est donnée par R = {(0, 0), (1, 1), (1, 2), (2, 1), (2, 2)}.

Question 4. Montrez que la bisimilarité (le fait pour deux systèmes d’être bisimilaires) est une relation d’équi-
valence. Vous montrerez en détail le cas de la transitivité.

74
Solution : — reflexivité : la diagonale {(s, s) | s ∈ S} est une bisimulation entre (S, i, ∆) et lui-même.
— symmétrie : si R est une bisimulation entre (S, i, ∆) et (S ′ , i′ , ∆′ ), alors la relation converse R† = {(s′ , s) |
(s, s′ ) ∈ R} est une bisimulation entre (S ′ , i′ , ∆′ ) et (S, i, ∆).
— transitivité : si R est une bisimulation entre (S, i, ∆) et (S ′ , i′ , ∆′ ), et si Q est une bisimulation entre (S ′ , i′ , ∆′ )
et (S ′′ , i′′ , ∆′′ ), alors la relation composite

R; Q = {(s, s′′ ) | ∃ s′ . (s, s′ ) ∈ R ∧ (s′ , s′′ ) ∈ Q}

est une bisimulation entre (S, i, ∆) et (S ′′ , i′′ , ∆′′ ). En effet :

— comme (i, i′ ) ∈ R et (i′ , i′′ ) ∈ Q, alors (i, i′′ ) ∈ R; Q.
a
— Suppose (s, s′′ ) ∈ R; Q et s −−→ t. Par définition de R; Q, il existe s′ tel que (s, s′ ) ∈ R et (s′ , s′′ ) ∈ Q.
a
Comme R est une bisimulation, il existe t′ tel que s′ −−→ t′ et (t, t′ ) ∈ R. Comme Q est une bisimulation,
a
il existe t′′ tel que s′′ −−→ t′′ et (t′ , t′′ ) ∈ Q. Par définition de R; Q, (t, t′′ ) ∈ R; Q.
— La dernière condition est similaire.

Question 5. Montrez que si deux systèmes sont bisimilaires, alors ils satisfont les mêmes formules.

Solution : Supposons donnée une bisimulation R entre (S, i, ∆) et (S ′ , i′ , ∆′ ). Il faut ici faire un peu attention à
la formulation de la récurrence à prouver. Nous allons prouver que pour toute formule φ, pour toute paire d’états
(s, s′ ) ∈ R, s ⊨ φ si et seulement si s′ ⊨ φ, par récurrence sur la formule φ.
— φ ≡ ⊤ : évident.
— φ ≡ ¬ψ : on a les équivalences suivantes
— s⊨φ
— s ̸⊨ ψ (définition de ⊨)
— s′ ̸⊨ ψ (hypothèse d’induction)
— s′ ⊨ φ (définition de ⊨)
— φ ≡ φ1 ∧ φ2 : similaire.
— φ ≡ ⟨a⟩ ψ : on a les implications suivantes
— s⊨φ
a
— il existe t tel que s −−→ t et t ⊨ ψ (definition de ⊨)
a
— il existe t′ tel que s′ −−→ t′ , (t, t′ ) ∈ R et t ⊨ ψ (R est une bisimulation)
a
— il existe t′ tel que s′ −−→ t′ et t′ ⊨ ψ (hypothèse de récurrence)
— s ⊨ φ (définition de ⊨)
L’implication dans l’autre sens est similaire. En utilisant cette propriété sur toute formule φ et sur (i, i′ )
(comme (i, i′ ) ∈ R par définition d’une bisimulation), pour toute formule φ, i ⊨ φ si et seulement si i′ ⊨ φ.
Donc (S, i, ∆) et (S ′ , i′ , ∆′ ) satisfont les mêmes formules.

Question 6. Utilisez ce résultat pour montrer que les deux systèmes suivants ne sont pas bisimilaires :

a a a
0 0 1
b c
1 2 c

Solution : Par contraposé, pour montrer que ces systèmes ne sont pas bisimilaires, il suffit d’exhiber une formule
satisfaite par l’un, mais pas par l’autre. Par ce que nous avons vu à la question 2., nous pouvons choisir ⟨a⟩ (⟨b⟩ ⊤ ∧
⟨c⟩ ⊤) qui est satisfaite par le système de droite mais pas celui de gauche.

75
Question 7. Montrer que ces deux systèmes ne sont pas bisimilaires, mais satisfont les mêmes formules :
— (S, 0, ∆) avec :
— S = {0} ∪ {(i, n) | 1 ≤ i ≤ n},
a
— 0 −−→ (1, n) pour tout n ≥ 1,
a
— (i, n) −−→ (i + 1, n) pour tout 1 ≤ i < n.
— (S ′ , 0, ∆′ ) avec :
— S ′ = {0} ∪ {(i, n) | 1 ≤ i ≤ n} ∪ {(i, ∞) | 1 ≤ i},
a
— 0 −−→ (1, n) pour tout n ≥ 1,
a
— 0 −−→ (1, ∞),
a
— (i, n) −−→ (i + 1, n) pour tout 1 ≤ i < n,
a
— (i, ∞) −−→ (i + 1, ∞) pour tout 1 ≤ i.

Solution : Supposons qu’ils soient bisimilaires, et que donc nous avons une bisimulation R entre eux. En parti-
a
culier, (0, 0) ∈ R. Comme 0 −−→ (1, ∞) dans le second système, alors il doit exister n tel que ((1, n), (1, ∞)) ∈ R.
a
Par récurrence, nous pouvons alors déduire que ((n, n), (n, ∞)) ∈ R. Comme (n, ∞) −−→ (n + 1, ∞) dans le second
système mais qu’il n’y a pas de transition sortante de (n, n) dans le premier, nous arrivons à la conclusion que R
ne peut pas être une bisimulation.
Pour la seconde partie, commençons par montrer par récurrence sur φ que pour tout i, si l’ensemble {n | (i, n) ⊨ φ}
est infini alors (i, ∞) ⊨ φ et si l’ensemble {n | (i, n) ̸⊨ φ} est infini alors (i, ∞) ̸⊨ φ
— φ ≡ ⊤ : évident.
— φ ≡ ¬ψ : Si {n | (i, n) ⊨ φ} est infini alors par définition de ⊨, {n | (i, n) ̸⊨ ψ} est infini. Par hypothèse de
récurrence, cela implique que (i, ∞) ̸⊨ ψ et que donc (i, ∞) ⊨ φ. L’autre partie de l’énoncé est similaire.
— φ ≡ φ1 ∧ φ2 : Si {n | (i, n) ⊨ φ} est infini, alors {n | (i, n) ⊨ φj } est infini pour j ∈ {1, 2}. Par hypothèse
de récurrence, cela implique que (i, ∞) ⊨ φj pour j ∈ {1, 2} et que (i, ∞) ⊨ φ1 ∧ φ2 . Si {n | (i, n) ̸⊨ φ}
est infini, alors par le principe des tiroirs, au moins l’un des {n | (i, n) ̸⊨ φj } est infini. Par l’hypothèse de
récurrence, cela implique que (1, ∞) ne satisfait pas au moins l’un des φj . Cela signifie que (i, ∞) ̸⊨ φ.
— φ ≡ ⟨b⟩ ψ avec b ̸= a : évident car aucun des (i, n) et des (i, ∞) ne peut satisfaire cette formule.
— φ ≡ ⟨a⟩ ψ : Si {n | (i, n) ⊨ φ} est infini, alors {n | (i + 1, n) ⊨ ψ} est infini. Par hypothèse de récurrence,
cela implique que (i + 1, ∞) ⊨ ψ et que donc (i, ∞) ⊨ φ. L’autre partie de l’énoncé est similaire.
Nous utilisons ce résultat pour montrer que par récurrence sur la formule φ que 0 ⊨ φ dans le premier système si
et seulement si 0 ⊨ φ dans le second. Le seul cas intéressant est quand φ ≡ ⟨a⟩ ψ. Deux cas possibles :
— soit (1, n) ⊨ ψ pour un certain n, alors 0 ⊨ φ dans les deux systèmes.
— soit (1, n) ̸⊨ ψ pour tout n. Dans ce cas, par ce qui précède, (1, ∞) ̸⊨ ψ. Alors dans ce cas, 0 ̸⊨ φ dans les
deux systèmes.

Nous dirons qu’un système (S, i, ∆) est à image finie si pour tout état s et lettre a, l’ensemble {s′ |
a
s −−→ s′ } est fini.

Question 8. Montrez que si deux systèmes à image finie satisfont les mêmes formules, alors ils sont bisimilaires.

Solution : Nous montrons que la relation suivante :

R = {(s, s′ ) | ∀φ. s ⊨ φ ⇔ s′ ⊨ φ}

est une bisimulation.

76
— (i, i′ ) ∈ R par hypothèse que les systèmes satisfont les mêmes formules.
a
— Supposons (s, s′ ) ∈ R et s −−→ t. Cela signifie que s ⊨ ⟨a⟩ ⊤. Donc par hypothèse, s′ ⊨ ⟨a⟩ ⊤, donc il existe
a
au moins un t tel que s −−→ t′ . Supposons par l’absurde qu’aucun des tels t′ soit tel que (t, t′ ) ∈ R. Cela
′ ′

signifie que pour chaque t′ , il existe une formule φt′ telle que t ⊨ φt′ et t′ ̸⊨ φt′ . Nous considérons la formule
suivante : ^
φ = ⟨a⟩ φt′
a
t′ |s′ −
−→t′
qui est bien définie carVles systèmes sont à image finie. Maintenant, nous observons que s ⊨Vφ car t est tel
a a
que s −−→ t et t ⊨ φt′ . Par contre, s′ ̸⊨ φ car pour tout t′ tel que s′ −−→ t′ , t′ ̸⊨ φt′ , ce qui
a a
t′ |s′ −
−→t′ t′ |s′ −
−→t′
a
contredit l’hypothèse que (s, s′ ) ∈ R. Nous concluons donc qu’il existe t′ tel que s′ −−→ t′ et (t, t′ ) ∈ R.
a
— Le cas (s, s′ ) ∈ R et s′ −−→ t′ est similaire.

77