20.4 Pour aller plus loin
275
20.3 Démonstration du cas uniforme
Nous sommes en mesure à présent de démontrer le théorème 20.1 dans le
cas où μ suit la loi uniforme sur le cube [0, 1]
d . Par le théorème 20.2 et le
lemme de Borel-Cantelli, p.s.
L n − E(L n ) =
⎧
⎨
⎩
O n→∞ (log(n))
si d = 2,
O n→∞ (n
(d−2)/(2d)
횿
log(n)) si d > 2
tandis que par le théorème 20.6 on a, pour un 0 < γ < ∞,
E(L n (X 1 , . . . , X n )) ∼ n→∞ γn
(d−1)/d .
20.4 Pour aller plus loin
Lorsque d = 2 et X 1 , . . . , X n sont i.i.d. uniforme sur [0, 1]
2 , on peut se
convaincre intuitivement que probablement L n (X 1 , . . . , X n ) est de l’ordre de
√ n lorsque n est grand en parcourant le carré par zigzags parallèles régulièrement espacés, par exemple horizontaux : il y a approximativement
√ n lignes
de longueur unité contenant chacune approximativement
√ n points. Plus rigoureusement, cela conduit à aborder le problème du voyageur de commerce
en dimension d = 2 en utilisant une courbe qui «remplit l’espace».
Le contenu de ce chapitre est directement inspiré du joli livre de Michael
Steele [Ste97]. On pourra également consulter sur ce thème le livre de Joseph Yukich [Yuk98] ainsi que le livre de Marc Mézard et Andrea Montanari [MM09]. L’inégalité de concentration d’Azuma-Hoeffding est étudiée par
Colin McDiarmid dans [McD89, McD98]. Le théorème 20.1 a été obtenu par
John Hammersley et ses élèves Jillian Beardwood et John Halton vers 1959
et peut être démontré par réduction au cas uniforme sur le cube [0, 1]
d . On
sait par ailleurs que γ 2 ≈ 0, 7 et que γ d ∼ d→∞
√
d2πe.
En théorie de la complexité algorithmique, la complexité d’un algorithme
est le coût d’exécution en fonction de la taille (n pour TSP) du problème.
Un algorithme polynomial est préférable à un algorithme exponentiel au-delà
d’une certaine taille. On dit qu’un problème est NP lorsqu’il est possible de
vérifier la validité d’une solution avec un algorithme polynomial. L’explosion
combinatoire fait qu’un problème NP n’est pas automatiquement résoluble
par un algorithme polynomial en testant toutes les solutions. On dit qu’un
problème est NP-complet lorsque le problème est au moins aussi difficile à
résoudre que tout autre problème NP, c’est-à-dire que tout problème NP se
réduit à celui-ci avec un algorithme polynomial. Les problèmes NP-complets
sont donc des problèmes clés. À l’heure actuelle, tous les algorithmes connus
pour résoudre les problèmes NP-complets sont exponentiels, ce qui les rend
assez rapidement inexploitables. La question ouverte la plus fameuse de l’informatique consiste à trouver un algorithme polynomial pour résoudre un
275
20.3 Démonstration du cas uniforme
Nous sommes en mesure à présent de démontrer le théorème 20.1 dans le
cas où μ suit la loi uniforme sur le cube [0, 1]
d . Par le théorème 20.2 et le
lemme de Borel-Cantelli, p.s.
L n − E(L n ) =
⎧
⎨
⎩
O n→∞ (log(n))
si d = 2,
O n→∞ (n
(d−2)/(2d)
횿
log(n)) si d > 2
tandis que par le théorème 20.6 on a, pour un 0 < γ < ∞,
E(L n (X 1 , . . . , X n )) ∼ n→∞ γn
(d−1)/d .
20.4 Pour aller plus loin
Lorsque d = 2 et X 1 , . . . , X n sont i.i.d. uniforme sur [0, 1]
2 , on peut se
convaincre intuitivement que probablement L n (X 1 , . . . , X n ) est de l’ordre de
√ n lorsque n est grand en parcourant le carré par zigzags parallèles régulièrement espacés, par exemple horizontaux : il y a approximativement
√ n lignes
de longueur unité contenant chacune approximativement
√ n points. Plus rigoureusement, cela conduit à aborder le problème du voyageur de commerce
en dimension d = 2 en utilisant une courbe qui «remplit l’espace».
Le contenu de ce chapitre est directement inspiré du joli livre de Michael
Steele [Ste97]. On pourra également consulter sur ce thème le livre de Joseph Yukich [Yuk98] ainsi que le livre de Marc Mézard et Andrea Montanari [MM09]. L’inégalité de concentration d’Azuma-Hoeffding est étudiée par
Colin McDiarmid dans [McD89, McD98]. Le théorème 20.1 a été obtenu par
John Hammersley et ses élèves Jillian Beardwood et John Halton vers 1959
et peut être démontré par réduction au cas uniforme sur le cube [0, 1]
d . On
sait par ailleurs que γ 2 ≈ 0, 7 et que γ d ∼ d→∞
√
d2πe.
En théorie de la complexité algorithmique, la complexité d’un algorithme
est le coût d’exécution en fonction de la taille (n pour TSP) du problème.
Un algorithme polynomial est préférable à un algorithme exponentiel au-delà
d’une certaine taille. On dit qu’un problème est NP lorsqu’il est possible de
vérifier la validité d’une solution avec un algorithme polynomial. L’explosion
combinatoire fait qu’un problème NP n’est pas automatiquement résoluble
par un algorithme polynomial en testant toutes les solutions. On dit qu’un
problème est NP-complet lorsque le problème est au moins aussi difficile à
résoudre que tout autre problème NP, c’est-à-dire que tout problème NP se
réduit à celui-ci avec un algorithme polynomial. Les problèmes NP-complets
sont donc des problèmes clés. À l’heure actuelle, tous les algorithmes connus
pour résoudre les problèmes NP-complets sont exponentiels, ce qui les rend
assez rapidement inexploitables. La question ouverte la plus fameuse de l’informatique consiste à trouver un algorithme polynomial pour résoudre un