CORRECTION DE L’EXAMEN

D’ALGORITHMIQUE ET COMPLEXITE
Master Informatique, première année, janvier 2015

TOUS VOS DOCUMENTS SUR PAPIER SONT AUTORISES.

COURRIEL ET TELEPHONE SONT INTERDITS.
REPONDEZ AUX QUESTIONS DANS L’ORDRE.
NUMEROTEZ VOS REPONSES.

1 Plus court chemin et programmation linéaire

Considérez le graphe ci-dessous :

a
1 2
4
0 b

Le coût (ou longueur) de l’arc 0a est 1, celui de l’arc ab est 2, celui de 0b est 4.
Exprimez le calcul des distances (longueurs des plus courts chemins) des
sommets a et b au sommet source 0 comme un problème de programmation
linéaire. Appelez a la distance du sommet a à la source. Appelez b la distance
du sommet b à la source. Nommez a′ , b′ , b′′ les variables d’écart. Résolvez par la
méthode du simplexe ce problème de programmation linéaire.
Réponse.
max : a + b
a ≤ 1 ⇒ a + a′ = 1
b ≤ 4 ⇒ b + b′ = 4
b ≤ a + 2 ⇒ b − a + b′′ = 2
Résolvons par la méthode du simplexe :
max : a + b max : 1 − a′ + b max : 4 − 2a′ − b′
a′ = 1 − a a = 1 − a′ a = 1 − a′
b′ = 4 − b b′ = 4 − b b = 3 − a ′ − b′
b′′ = 2 + a − b b′′ = 3 − a′ − b b′ = 1 + a′ + b′′

1
C’est terminé. On trouve bien les distances correctes : a = 1, b = 3.

2 Flot optimal et programmation linéaire

A
1 2
c
a
4
0 b B

Pour le même graphe que précédemment, considérez le calcul de la distance

de B au sommet source O comme un problème de flot de valeur 1 et de coût
minimal. Posez le problème de programmation linéaire. Résolvez par la méthode
du simplexe ce problème de programmation linéaire : seuls les tableaux initial
et final sont demandés.
Réponse.
a est le flot dans l’arc O → A ; il est aussi égal au flot c dans l’arc A → B. b
est le flot dans l’arc O → B. Le problème de PL est :
min : 3a + 4b ⇒ max : −3a − 4b
a+b=1
Le tableau initial et final est :
max : −3 − b
a=1−b
Interprétation. Le chemin le plus court entre O et B est O → A → B. L’arc
O → B est inutilisé.
Voici une seconde solution, moins expéditive. Soit c le flot dans l’arc A → B.
La règle de conservation du flot (en chaque sommet, la somme des flots entrants
égqle la somme des flots sortants, sauf au sommet source et au sommet puits)
au sommet A donne : a = c. Le problème de PL est :
min : a + 2c + 4b ⇒ max : −a − 2c − 4b
a=c
a+b=1
L’exemple est très simple, donc on trouve facilement un tableau initial et final :
max : −3 − b
c=1−b
a=1−b

Interprétation. a = c = 1 ; b = 0 ; le coût est 3.

2
3 Graphes et probabilités
Par définition, la somme de la probabilité de mort et de la probabilité de
survie pour un arc ou un chemin vaut 1. Dans le graphe suivant, chaque arc est
étiqueté avec la probabilité de mourir quand l’arc est emprunté. Quelles sont
les probabilités de survie des deux chemins 0, a, b et 0, b ? Quel est le chemin le
plus sûr ? Aucune justification n’est demandée, et le recours à la programmation
linéaire n’est pas requis.

a
1/4 1/4

1/2
0 b

Réponse. La probabilité de survie du chemin 0 → a → b est (1 − 1/4) ×

(1 − 1/4) = 9/16 = 0.5625. Celle du chemin 0 → b est 1 − 1/2 = 1/2. Donc le
chemin 0 → a → b a une probabilité de survie plus grande : il est plus sûr.
Commentaire : imaginez qu’il y a 16 personnes au sommet 0. Elles vont vers
le sommet a : un quart meurt, donc 12 arrivent en vie en a. Un quart de ces 12
personnes meurent entre a et b, donc 9 arrivent saines et sauves en b. Le taux
de survivants est donc 9/16.

4 Problème de la somme
n entiers naturels (donc non négatifs) ei , avec i ∈ 1..n, sont donnés, ainsi
qu’un entier naturel S.
a. Comment décider si S est la somme d’un des sous-ensembles des ei ?
Chaque entier ei ne peut être utilisé qu’une seule fois. Réduisez ce problème au
problème du sac à dos, que nous avons résolu par programmation dynamique.
P
P Réponse. Pour réduire au problème du sac à dos : max i xi ui avec
i xi pi ≤ S, xi ∈ {0, 1}, i ∈ {1, . . . n}, prendre les utilités ui et les poids
(ou volumes) pi égaux aux entiers ei : ui = pi = ei , ∀i.
Ci-dessous, une réponse plus détaillée, qui n’était pas demandée.
Dans le problème du sac à dos, un alpiniste doit choisir quels éléments
prendre dans son sac à dos. Chaque élément i a une utilité uiP≥ 0 ∈ R et un poids
pi ∈ N. L’alpiniste doit maximiser la somme des utilités xi ui (xP
i ∈ {0, 1})
des éléments du sac à dos, avec la contrainte que la somme des poids xi pi des
éléments du sac ne dépasse pas un poids maximal donné S. Si ei = ui = pi , alors

3
 P
ce problème est égal au problème de la somme : max :
P xi ei avec la contrainte
xi ei ≤ S, i = 1, . . . n, et xi ∈ {0, 1}.
Le problème de la somme peut être résolu avec l’algorithme par program-
mation dynamique (vu en TD et programmé en TP). Notons Ω(i, s) la somme
maximale plus petite ou égale à s ∈ N faisable avec les i premiers éléments (donc
i ∈ 1 . . . n). Alors

Ω(1, s) = si e1 ≤ s alors e1 sinon 0

Ω(i > 1, s) = si s − ei ≥ 0
alors max(Ω(i − 1, s), ei + Ω(i − 1, s − ei ))
sinon Ω(i − 1, s)

Les valeurs de Ω peuvent être stockées dans une table de hachage. Ceci
permet de ne les calculer qu’une seule fois, et seulement quand ceci est nécessaire.
Ceci simplifie aussi le programmation : il suffit de demander la valeur voulue de
Ω, sans que le programmeur ait se soucier de l’ordre des calculs.
b. La méthode fonctionne-t-elle pour des entiers relatifs (dans Z) ? On sup-
pose que S reste un entier positif.
Réponse. Non. Voici un exemple simple où la méthode précédente ne
fonctionne pas avec des ei entiers négatifs. Supposons i = 1, e1 < 0, et S ≥ 0,
alorsPle résultat de laPméthode est Ω(1, S) = e1 , mais le résultat correct (de
max xi ei avec max xi ei ≤ S) est 0.
NB. Cela ne prouve pas qu’aucune méthode de programmation dynamique
n’existe pour résoudre ce problème. Cela prouve seulement que la méthode pré-
cédente ne fonctionne pas.
Le problème de la somme (ou du sac à dos) peut aussi être résolu par re-
cherche arborescente (backtrack), avec élagage (branch and bound) avec des ei
réels et éventuellement négatifs.

5 Variante de la transformée de Fourier rapide

Arthur propose une variante de la transformée de Fourier rapide. Il considère
les racines 3k ièmes de l’unité (racines cubiques, 9 ième, 27 ième, etc) alors que
l’algorithme classique considère les racines 2k de l’unité. En conséquence, le
temps d’exécution de son algorithme vérifie les relations de récurrence : T (1) =
1, T (n = 3k ) = n + 3T (n/3).
a. Quelle est la complexité de la méthode d’Arthur ? La preuve par récurrence
n’est pas demandée.
Réponse. Il suffisait de répondre O(n log n).
Voici une réponse détaillée, qui n’était pas demandée. On devine sur le ta-

4
bleau suivant que T (n = 3k ) = (k + 1)n = O(n log n) :

k n = 3k T (n) (k + 1)n
0 1 1 1
1 3 6 6
2 9 27 27
3 27 108 108

Prouvons-le par récurrence. On sait que T (n) = (k + 1)n pour n = 3k pour

′
de petites valeurs de n. Prouvons que la propriété est vraie pour n′ = 3n = 3k
avec k ′ = k + 1 :

T (n′ ) = T (3n) = 3n + 3T (n) = 3n + 3(k + 1)n = (k + 2)(3n) = (k ′ + 1)n′

CQFD.
Est-elle meilleure que celle de la méthode classique ? Donnez la complexité
de la méthode classique.
Réponse. La méthode classique est elle aussi en O(n log n). La méthode
classique et celle d’Arthur ont la même complexité.

6 Un graphe non orienté est-il un arbre ?

Rappel : En théorie des graphes, un arbre est un graphe non orienté, acy-
clique et connexe.
Soit A le nombre d’arêtes de G et S le nombre de sommets de G.
a. Quelle relation lie A et S quand G est un arbre ?
Réponse. S = A + 1. Remarque : l’arbre doit être non vide (S > 0).
b. Quelle relation lie A, S, T quand G est une forêt avec T arbres ?
Réponse. S = A + T . Ce coup-ci, la formule fonctionne même si S = 0.
c. Citez un des (au moins trois) algorithmes vus en cours permettant de
décider que G est connexe. Vous pouvez supposer que la relation de (a) est
vérifiée.
Réponse. 1, par gestion des classes d’équivalence (union find). 2 : les
parcours (ou traversées) d’un graphe (en largeur ou en profondeur) permettent
de construire une forêt couvrante (ici un arbre couvrant) en temps linéaire avec
la taille du graphe (nombre de sommets + nombre d’arcs ou arêtes). Le livre
"Introduction à l’algorithmique" de Cormen et al présentent ces deux méthodes.
La première a été vue en CM. La seconde a été vue en TD.
d. On suppose que G est non orienté, acyclique et connexe (c’est un arbre).
Proposez en 5 lignes au plus un algorithme calculant tous les plus courts chemins
(et leurs longueurs) depuis un sommet donné. Votre algorithme doit être plus
efficace que celui de Dijkstra.

5
 Réponse. Par un parcours en profondeur à partir du sommet source ω,
calculer un arbre couvrant : ceci oriente les arêtes de la source ω vers tous les
autres sommets. Il suffit ensuite de propager : D(ω) = 0, D(s) = soit p =
father(s) dans D(p) + L(ps). Le tableau D contient la distance à la source, et
L(ps) est la longueur de l’arc p → s. Le temps est en O(A + S) = O(A) = O(S),
meilleur que la méthode de Dijkstra (qui est plus générale).
Un algorithme par programmation dynamique (comme celui utilisé pour les
dates au plus tôt et au plus tard) fonctionne aussi, avec les mêmes performances,
ssi les arêtes sont orientées de ω vers tous les autres sommets ; cette bonne
orientation est indispensable : si les arêtes donnent deux arcs opposés, il y a des
cycles et l’algorithme boucle.
Remarque : les algorithmes de Prim ou Kruskal calculent un arbre couvrant
optimal, et donc calculent bien un arbre couvrant, mais leur complexité n’est
pas linéaire.
Remarque : les algorithmes fonctionnent si des coûts sont négatifs et donnent
les longueurs des chemins simples (sans répétition) les plus courts. Il n’y a qu’un
seul chemin simple dans un arbre entre deux sommets : c’est donc le plus court.
On rappelle que la longueur d’un chemin non simple peut être aussi petite que
l’on veut s’il y a une arête de coût négatif dans le graphe : il suffit d’aller et
venir suffisamment le long de l’arête de coût négatif.

7 Cryptographie asymétrique et bon sens

Rappel. Avec la cryptographie asymétrique, tout le monde peut crypter un
message (un grand entier) m : cela revient à calculer m′ = C(m), ce qui se fait
en temps polynomial avec log m. Par contre, seul le destinataire peut décrypter
m′ , autrement dit calculer C −1 (m′ ).
Un étudiant programme une de ces méthodes (par exemple RSA). Il crypte
chaque bit du message, et concatène les résultats, pour obtenir le message crypté.
a. Où est l’erreur ?
Réponse. L’espion calcule C(0) et C(1), et regarde si le message crypté
commence par C(0) ou C(1). Il trouve ainsi le premier bit, sans connaître la clef
secrète. Il itère sur la suite du message crypté.
b. Si l’étudiant encrypte chaque octet, est-ce mieux ?
Réponse. L’espion calcule les 256 valeurs C(0), . . . C(255), puis utilise la
même méthode que précédemment. Ce n’est donc pas meilleur : 28 est trop
petit.

8 Réseau
Rappels. On note N l’ensemble des entiers naturels : 0, 1, 2, 3 . . .. On note Z
l’ensemble des entiers relatifs : . . . , −3, −2, −1, 0, 1, 2, 3 . . .. Q est l’ensemble des
rationnels.

6
 Le dessin suivant montre une partie d’un réseau R généré par deux vecteurs
A = (5, 3) et B = (4, 1). R est l’ensemble des points (les disques noirs sur le
dessin) aA + bB avec a ∈ Z, et b ∈ Z. R est aussi généré par I = (1, 2) et
J = (−3, 1), qui sont plus courts que A et B. Il n’existe pas de base strictement
plus courte que ±I, ±J.
q Rappels. La longueur, ou norme euclidienne, de A = (Ax , Ay ) est ||A|| =
A2x + A2y . L’aire du parallélogramme généré par A, B est la valeur abosolue
du déterminant  
 Ax Ay 
 Bx By  = Ax By − Ay Bx
 

Propriété : toutes les bases d’un même réseau génèrent des parallélogrammes de
même aire (au signe près).

I (1, 2)
J (−3, 1)

A (5,3)

B (4, 1)

a. Deux vecteurs 2d indépendants à coordonnées dans Z : A = (Ax , Ay )

et B = (Bx , By ), sont donnés. Proposez un test (utilisant un nombre constant
d’opérations dans Z) pour décider qu’il n’existe pas de vecteurs strictement
plus courts que ±A, ±B engendrant le même réseau. Vous pouvez supposer
||A|| ≥ ||B||. Répondre en une ligne au plus.
Réponse. Supposons ||A|| ≥ ||B||. Si ni A + B ni A − B n’est strictement
plus court que A, alors (±A, ±B) est la base la plus courte.
b. Déduisez-en un algorithme de calcul de la base la plus courte. Quel est
son coût ?
Réponse. On peut échanger A et B pour que A ne soit pas plus court que
B. Soit C le vecteur le plus court dans {A+B, A−B}. Si C est plus court que A,
itérer sur la base (C, B) sinon (A, B) est la base la plus courte. Cette méthode
n’est pas en temps polynomial : considérer B = (1, 0) et A = (α ∈ N, 1).

7
Alors la base la plus courte est I = (1, 0), J = (0, 1) mais O(α) réductions
sont nécessaires, ce qui est exponentiel dans la taille des données (la taille des
données est log α).
La suite n’était pas demandée.
Voici une méthode plus efficace.
Soit P = qB la projection orthogonale de A sur B (avec q ∈ R ; alors A − qB
et B sont perpendiculaires :
A.B
(A − qB) . B = 0 ⇒ q =
B .B

A
R

B
−1B −2B −3B −4B −5B
Rappel : A . B est le produit scalaire de A et B. Il vaut Ax Bx + Ay By .
Soit qe = ⌊q⌋ ou bien qe = ⌊q⌉ l’entier le plus proche de q (arrondir arbi-
trairement si q ∈ Z/2). Alors soit le "reste" R = A − qe B ; dans la base (A, B),
A est remplacé par le vecteur le plus court dans {A, R} ; la méthode termine
quand R n’est pas strictement plus court que A.
Chaque étape de réduction de la base s’exprime matriciellement :
        
Bx By 0 1 Ax Ay A.B A.B
= avec qe = ou
Rx Ry 1 −qe Bx By B .B B .B

ou bien, si on préfère :
        
qe 1 Bx By Ax Ay A.B A.B
= avec qe = ou
1 0 Rx Ry Bx By B .B B .B

et la matrice contenant qe a comme déterminant -1. Elle est unimodulaire, ce

qui prouve que toutes les bases ont même déterminant (au signe près) que la
base initiale (A, B). Cette formulation matricielle fonctionne aussi quand B est
plus court que A, et dans ce cas, qe est nul et la réduction échange A et B ; ce
cas ne peut se produire deux fois de suite, et il n’influence donc pas l’ordre de
grandeur du nombre de réductions.
Soulignons l’analogie avec l’algorithme d’Euclide étendu, qui calcule le PGCD
g de deux nombres a et b, et les coefficients de Bézout x et y tels que ax+by = g.
Cet algorithme pose : a = qb + r (nous utilisons des minuscules pour éviter les

8
confusions) avec q = ⌊a/b⌋ (utiliser q = ⌊a/b⌉ comme Gauss le faisait est correct
aussi) et se formule matriciellement de la même façon :
     jam jak
b 0 1 a
= avec q = ou
r 1 −q b b b
ou bien, si on préfère :
     jam jak
q 1 b a
= avec q = ou
1 0 r b b b
Pour que tous les qe soient positifs, comme les q = ⌊a/b⌋ de l’algorithme
classique d’Euclide, il suffit d’intercaler des phases qui remplacent le vecteur B
par −B quand A . B est négatif ; ce changement de signe ne peut pas se produire
deux fois de suite ; il ne modifie donc pas la complexité (le nombre d’étapes) et
accentue la similitude entre les deux méthodes.
Cette similitude entre la réduction de la base d’un réseau 2D et l’algorithme
d’Euclide nous permet de réutiliser l’étude de la complexité de l’algorithme
d’Euclide (théorème de Lamé) :
Dans le cas qui nécessite le plus de réductions, que ce soit pour la méthode
d’Euclide ou pour la réduction de base, tous les q, ou qe , valent 1. Pour la
méthode d’Euclide, cela se produit quand a et b sont deux nombres de Fibonacci
consécutifs, comme l’a remarqué Lamé. D’ailleurs, on reconnaît alors dans la
matrice contenant qe ou q la "matrice de Fibonacci" (ou son inverse) : celle
dont la puissance permet de calculer les termes de la suite de Fibonacci. La
matrice de Fibonacci est F :
   
1 1 φ 0
F = = R−1 R
1 0 0 φ′
avec    
φ φ′ −1 1 1 −φ′
R= et R =√
1 1 5 −1 φ

√ La valeur propre la plus grande de la matrice de Fibonacci F est φ = (1 +

5)/2 ≈ 1.618. φ est racine de

det(F − λI2 ) = λ2 − λ − 1 = 0, où I2 est la matrice identité 2 par 2

√
La valeur propre conjuguée est φ′ = 1 − φ = (1 − 5)/2 ≈ −0.618.
Par l’argument habituel, on en déduit que le nombre de réductions, ou ité-
rations, pour les deux algorithmes est en O(logφ (N ), où N est la norme des
vecteurs initiaux de base A et B, ou bien la valeur absolue de a et b ; le nombre
de réductions ou d’itérations est donc proportionnel à la taille du problème,
dans le pire des cas. Le théorème de Lamé précise la constante du O(log N ). Le
plus souvent, le nombre d’itérations est moindre ; ce nombre d’itérations est une
question importante en théorie des nombres.
Attention : chaque réduction effectue une quantité constante d’opérations
dans Z ou Q, mais les opérations dans Z ou Q (avec la librairie nums.cma de
ocaml par exemple) ne se font pas en temps constant.

9
 c. Le caractère entier relatif des coordonnées de A et B est-il indispensable ?
Réponse. Non. Ce qui importe est que ces coordonnées sont calculables
(par exemple elles sont dans Q, ou algébriques), que le réseau est l’ensemble
des aA + bB avec a ∈ Z, b ∈ Z. Cela implique que, dans un disque de rayon
fini (par exemple max(||A||, ||B||)) ou un carré, le réseau ne peut avoir qu’un
nombre fini de points 1 . En passant, un théorème de Minkowski sur les réseaux
quantifie cela. Il n’y a donc qu’un nombre fini de bases à envisager.
En haute dimension, le calcul du vecteur le plus court d’un réseau, le calcul
de la base la plus courte (ou raisonnablement courte), le calcul du nombre de
points d’un réseau dans un convexe sont des problèmes difficiles. Ces problèmes
se posent en cryptographie, en cryptanalyse, en combinatoire, en optimisation
discrète, en théorie des nombres.

9 Rectangle pavé par des carrés

Ce rectangle est pavé par des carrés. Exprimez c1 , c2 , c3 , c4 en fonction de
c0 . Que constatez vous ? Vous pouvez poser c0 = 1.

c1
c2
c0
c4
c3

Réponse. c1 = c0 . Puis c2 = c0 + c1 = 2c0 . Puis c3 = c1 + c2 = 3c0 . Puis

c4 = c2 + c3 = 5c0 . On devine que ck = ck−2 + ck−1 . On reconnaît la suite de
Fibonacci.

10 Rectangle pavé par des carrés tous différents

Le dessin suivant montre un rectangle pavé par des carrés ; il est faux, mais
la topologie est correcte.
1. Note. Il ne suffit pas que le réseau soit discret (discontinu) pour cela. Par exemple,
l’ensemble discret 1/i pour i ∈ N − {0} contient une quantité infinie de points dans l’intervalle
[0, 1] de longueur 1.

10
 c6 c7

c3 c2
c4
a
c5

c1 b

a. Exprimez les longueurs des côtés en fonction de a et b. Pour commencer :

c1 = a + b et a + c2 = b ⇒ c2 = b − a. Pour vous aider, les carrés sont numérotés
dans le "bon" ordre. Déduisez-en une relation entre a et b. Déduisez-en les
longueurs entières les plus petites (non nulles) de tous les carrés.
Réponse.
c1 =a+b
c2 =b−a
c3 = c2 − a = b − 2a
c4 = c1 − c3 + a = 4a
c5 = c1 + c4 = 5a + b
c6 = c4 + c5 = 9a + b
c7 = −c3 + c4 + c6 = 15a
c7 = c2 + c3 = 2b − 3a
Donc 15a = 2b − 3a ⇒ 9a = b. Posons a = 1. Alors b = 9, c1 = 10, c2 = 8, c3 =
7, c4 = 4, c5 = 14, c6 = 18, c7 = 15.

11
 c7=15
c6=18

c3=7 c2=8
c4=4
a=1
c5=14

c1=10 b=9

Remarquez que, de façon plus générale, chaque trait intérieur maximal donne
une équation linéaire, par exemple c4 + c6 = c3 + c7 pour le trait vertical en
haut presque au milieu. On admettra qu’il y a toujours une équation de moins
que d’inconnues.
b. Le dessin d’un pavage d’un rectangle en carrés est donné ; il faut calculer
les longueurs entières minimales (non nulles) des carrés. Proposez en trois lignes
au plus le principe d’une méthode, ou bien identifiez le problème mathématique
sous-jacent.
Réponse. Une des longueurs est initialisée à 1. Nous admettons que le
système linéaire a alors autant d’équations que d’inconnues. Il est résolu dans les
rationnels (Q). Soit C le vecteur rationnel solution ; soit p le PPCM (plus petit
commun multiple) des dénominateurs des Ci ; alors pC est, algébriquement, la
solution entière non nulle la plus petite du système linéaire ; mais il faut vérifier
que pC est géométriquement réalisable, autrement dit que toutes les longueurs
pCi ∈ Z sont positives.
Ceci suggère une méthode pour trouver les pavages de rectangles par des
carrés : générer toutes les topologies possibles, puis résoudre. C’est un sujet
possible pour les projets.

12