-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy path2015-05-15-reflexions-sur-la-complexite-algorithmique-chapitre-2.html
575 lines (530 loc) · 110 KB
/
2015-05-15-reflexions-sur-la-complexite-algorithmique-chapitre-2.html
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
<!DOCTYPE html>
<html lang="">
<head>
<link href='https://fonts.googleapis.com/css?family=Source+Sans+Pro:300,400,700,400italic' rel='stylesheet' type='text/css'>
<link href="https://fonts.googleapis.com/css?family=Roboto" rel="stylesheet">
<link rel="stylesheet" href="https://use.fontawesome.com/releases/v5.6.3/css/all.css" integrity="sha384-UHRtZLI+pbxtHCWp1t77Bi1L4ZtiqrqD80Kn4Z8NTSRyMA2Fd33n5dQ8lWUE00s/" crossorigin="anonymous">
<link rel="stylesheet" type="text/css" href="css/bootstrap.min.css" />
<link rel="stylesheet" type="text/css" href="css/main.css" />
<link rel="stylesheet" type="text/css" href="css/friendly.css" />
<meta charset="utf-8" />
<meta http-equiv="X-UA-Compatible" content="IE=edge" />
<meta name="HandheldFriendly" content="True" />
<meta name="viewport" content="width=device-width, initial-scale=1.0" />
<meta name="robots" content="" />
<script src="https://unpkg.com/[email protected]/dist/mermaid.min.js"></script>
<link rel="stylesheet" href="https://cdn.jsdelivr.net/npm/[email protected]/dist/katex.min.css" integrity="sha384-AfEj0r4/OFrOo5t7NnNe46zW/tFgW6x/bCJG8FqQCEo3+Aro6EYUG4+cU+KJWu/X" crossorigin="anonymous">
<!-- The loading of KaTeX is deferred to speed up page rendering -->
<script defer src="https://cdn.jsdelivr.net/npm/[email protected]/dist/katex.min.js" integrity="sha384-g7c+Jr9ZivxKLnZTDUhnkOnsh30B4H0rpLUpJ4jAIKs4fnJI+sEnkvrMWph2EDg4" crossorigin="anonymous"></script>
<!-- Global site tag (gtag.js) - Google Analytics -->
<script async src="https://www.googletagmanager.com/gtag/js?id=G-PWL24785Z6"></script>
<script>
window.dataLayer = window.dataLayer || [];
function gtag(){dataLayer.push(arguments);}
gtag('js', new Date());
gtag('config', 'G-PWL24785Z6');
</script>
<!-- To automatically render math in text elements, include the auto-render extension: -->
<script defer src="https://cdn.jsdelivr.net/npm/[email protected]/dist/contrib/auto-render.min.js" integrity="sha384-mll67QQFJfxn0IYznZYonOWZ644AWYC+Pt2cHqMaRhXVrursRwvLnLaebdGIlYNa" crossorigin="anonymous"
onload="renderMathInElement(document.body);"></script>
<meta name="author" content="" />
<meta name="description" content="" />
<title>Alexandre Quemy - Blog - Réflexions sur la complexité algorithmique, chapitre 2</title>
</head>
<body id="index" class="home">
<div class="wrapper">
<!-- Use icons from fontawesome when you are adding new item in the contact list -->
<div class="sidebar-wrapper">
<div class="profile-container">
<img class="profile-img" src="images/profile.jpeg" alt="profile picture" />
<h1 class="name">Alexandre Quemy</h1>
<h3 class="tagline">Tech Staff @ Proof.io</h3>
<h3 class="tagline">Freelance @ Hother.io</h3>
</div><!--//profile-container-->
<div class="contact-container container-block">
<ul class="list-unstyled contact-list">
<li class="email"><i class="fa fa-envelope"></i><a href="mailto: [email protected]">[email protected]</a></li>
<li class="linkedin"><i class="fab fa-linkedin"></i><a href="https://in.linkedin.com/in/aquemy" target="_blank">linkedin.com/in/aquemy</a></li>
<li class="github"><i class="fab fa-github"></i><a href="http://github.com/aquemy" target="_blank">github.com/aquemy</a></li>
<li class="twitter"><i class="fa fa-twitter"></i><a href="https://twitter.com/@alexandre_quemy" target="_blank">@alexandre_quemy</a></li>
<!--<li class="acclaim"><i class="fa fa-certificate"></i><a href="https://www.youracclaim.com/user/alexandre-quemy" target="_blank">alexandre-quemy</a></li>-->
<div itemscope itemtype="https://schema.org/Person"><a itemprop="sameAs" content="https://orcid.org/0000-0002-5865-6403" href="https://orcid.org/0000-0002-5865-6403" target="orcid.widget" rel="me noopener noreferrer" style="vertical-align:top;"><img src="https://orcid.org/sites/default/files/images/orcid_16x16.png" style="width:1em;margin-right:.5em;" alt="ORCID iD icon">0000-0002-5865-6403</a></div>
</ul>
</div>
</div><!--//sidebar-wrapper-->
<div class="top-menu">
<ul>
<li id="selected"><a href="./index.html">Home</a></li>
<li><a href="./research.html">Research</a></li>
<li><a href="./cv.html">CV</a></li>
<!-- <li><a href="./portfolio.html">Portfolio</a></li> -->
<!-- <li><a href="./passions.html">Passions</a></li> -->
<!-- <li><a href="./blog.html">Blog</a></li> -->
<li><a href="https://endomorphis.me" target="_blank">Blog</a></li>
</ul>
</div>
<div class="main-wrapper">
<div class="recent-post-header" id="top-menu-entry">
<p><a href="./blog.html">Back to entries</a></p>
</div>
<div class="blog_entry">
<h1 class="section-title">Réflexions sur la complexité algorithmique, chapitre 2</h1>
<div class="item">
<div class="meta">
<div class="upper-row">
<h3 class="job-title"><cite>2015-05-15</cite></h3>
<div class="time">#Mathématiques</div>
</div><!--//upper-row-->
</div><!--//meta-->
<div class="details">
</div>
</div>
<div class="toc">
<ul>
<li><a href="#avant-propos">Avant-propos</a></li>
<li><a href="#position-du-probleme">Position du problème</a><ul>
<li><a href="#le-probleme-doptimisation-lineaire">Le problème d’optimisation linéaire</a></li>
<li><a href="#quelques-notations-et-remarques-de-vocabulaire">Quelques notations et remarques de vocabulaire</a></li>
<li><a href="#probleme-dordre-total-pour-la-comparaison-dalgorithmes">Problème d’ordre total pour la comparaison d’algorithmes</a></li>
</ul>
</li>
<li><a href="#mesures-de-complexite-dun-algorithme">Mesures de complexité d’un algorithme</a><ul>
<li><a href="#remarques-preliminaires">Remarques préliminaires</a></li>
<li><a href="#pire-des-cas">Pire des cas</a></li>
<li><a href="#meilleur-des-cas">Meilleur des cas</a></li>
<li><a href="#etude-de-lencadrement-sur-exemple">Étude de l’encadrement sur exemple</a></li>
<li><a href="#complexite-en-moyenne">Complexité en moyenne</a></li>
<li><a href="#analyse-amortie">Analyse amortie</a></li>
<li><a href="#analyse-lisse">Analyse lisse</a></li>
<li><a href="#les-defauts-de-la-complexite-pour-la-comparaison-dalgorithmes">Les défauts de la complexité pour la comparaison d’algorithmes</a></li>
</ul>
</li>
<li><a href="#vers-des-criteres-de-difficulte-en-amont">Vers des critères de difficulté en amont</a><ul>
<li><a href="#des-problemes-de-decision-vers-loptimisation">Des problèmes de décision vers l’optimisation</a></li>
<li><a href="#linearite-versus-non-linearite">Linéarité versus non linéarité</a></li>
<li><a href="#quest-ce-quun-probleme-facile">Qu’est-ce qu’un problème facile ?</a></li>
<li><a href="#une-question-de-domaine">Une question de domaine</a></li>
<li><a href="#convexe-versus-non-convexe">Convexe versus non-convexe</a></li>
</ul>
</li>
<li><a href="#robustesse-theorique-et-empirique-dun-algorithme">Robustesse théorique et empirique d’un algorithme</a><ul>
<li><a href="#no-free-lunch">No Free Lunch</a></li>
<li><a href="#compromis-conception-exploitation">Compromis conception-exploitation</a></li>
</ul>
</li>
<li><a href="#conclusion">Conclusion</a></li>
<li><a href="#references">Références</a></li>
<li><a href="#credits-des-illustrations">Crédits des illustrations</a></li>
</ul>
</div>
<h3 id="avant-propos">Avant-propos<a class="headerlink" href="#avant-propos" title="Permanent link">¶</a></h3>
<p>La complexité algorithmique est l’étude du lien, souvent temporel, mais aussi spatial<sup id="fnref:memoire"><a class="footnote-ref" href="#fn:memoire">1</a></sup>, entre un problème et un algorithme particulier. Puis en élargissant, l’étude d’un problème par rapport à l’ensemble des algorithmes connus qui le résolvent.
Il s’agit donc de caractériser la difficulté d’un problème au travers des méthodes de résolution.</p>
<p>Une seconde approche plus récente, en tout cas dans ses résultats les plus novateurs, consiste à essayer d’établir la difficulté du problème par rapport à ses caractéristiques intrinsèques. Pour cela, il est évident qu’il faut pouvoir trouver un langage commun d’expression des problèmes, et ce langage est la mathématique et plus précisément la programmation mathématique, un domaine de la recherche opérationnelle.</p>
<p>Le terme « programmation » n’a ici rien à voir avec l’informatique, mais doit son origine, tout comme le terme « recherche opérationnelle » au vocabulaire militaire puisque la discipline est née durant la seconde guerre mondiale, notamment pour l’élaboration du plan optimal de gestion de certaines ressources, c’est-à-dire la recherche de la meilleure façon d’opérer. En cela, la programmation mathématique est en réalité ramenée à de l’optimisation.</p>
<p>Dans cet article nous tâcherons de montrer qu’une très vaste partie des problèmes peut se poser sous la forme d’un problème d’optimisation, notamment au travers ici de l’exemple de l’optimisation linéaire.
Par la suite nous expliquerons en quoi les études de complexité n’arrivent plus à caractériser pleinement la difficulté d’un problème, notamment au travers de l’évolution des attentes des performances des algorithmes, ainsi que des facteurs influençant la qualité empirique des algorithmes.
Fort de ce constat, nous expliciterons quelques propriétés en amont, c’est-à-dire du point de vue du problème, qui caractérisent un problème difficile, et donc sans disposer explicitement de méthode de résolution. Enfin, nous donnerons quelques pistes supplémentaires pour faire le lien avec des propriétés des algorithmes, notamment leur robustesse et leur paramétrisation.</p>
<p>L’enjeu ici est de montrer les difficultés à caractériser les performances d’un algorithme et donc à fortiori, la difficulté d’un problème par rapport aux algorithmes qui le résolvent.</p>
<h3 id="position-du-probleme">Position du problème<a class="headerlink" href="#position-du-probleme" title="Permanent link">¶</a></h3>
<h4 id="le-probleme-doptimisation-lineaire">Le problème d’optimisation linéaire<a class="headerlink" href="#le-probleme-doptimisation-lineaire" title="Permanent link">¶</a></h4>
<h5 id="definissons-le-probleme">Définissons le problème<a class="headerlink" href="#definissons-le-probleme" title="Permanent link">¶</a></h5>
<p>Commençons par un petit rappel :</p>
<div class="admonition def">
<p class="admonition-title">Définition (fonction linéaire):</p>
<p>Une fonction <span class="arithmatex">\(f\)</span> est linéaire si elle satisfait le principe de superposition, c’est-à-dire si <span class="arithmatex">\(\forall x,y,\alpha \in \mathbb{R}^3,~ f(x+\alpha y) = f(x) + \alpha f(y)\)</span>.</p>
</div>
<p>Le problème d’optimisation linéaire est un problème qui vise à minimiser (ou maximiser) une fonction linéaire <span class="arithmatex">\(f\)</span> tout en respectant des contraintes elles aussi linéaires.
Concrètement, <span class="arithmatex">\(f\)</span> est une combinaison linéaire d’un certain nombre <span class="arithmatex">\(n\)</span> de variables et peut donc s’écrire <span class="arithmatex">\(c^{\top }x\)</span>, avec <span class="arithmatex">\(c\in \mathbb{R}^n\)</span> et <span class="arithmatex">\(x\in \mathbb{R}^n\)</span>. Les <span class="arithmatex">\(n\)</span> variables dites de décisions, sont alors soumises à <span class="arithmatex">\(m\)</span> contraintes, de la forme <span class="arithmatex">\(a_i^{\top} x \leq b_i, \forall 1 \leq i \leq m\)</span>, avec <span class="arithmatex">\(a_i \in \mathbb{R}^n\)</span> et <span class="arithmatex">\(b_i \in \mathbb{R}\)</span>.</p>
<p>Pour plus de concision, on peut écrire cette formulation sous forme matricielle :</p>
<div class="arithmatex">\[(PL) \left\{ \begin{matrix}
\underset{x \in \mathbb{R}^n}{\text{min}}~c^{\top}x \\
Ax \leq b
\end{matrix}\right.\]</div>
<p>Avec <span class="arithmatex">\(A \in \mathbb{M}^{m \times n}(\mathbb{R})\)</span> et <span class="arithmatex">\(b \in \mathbb{R}^m\)</span>.</p>
<h5 id="un-exemple-concret-planifier-une-production">Un exemple concret : planifier une production<a class="headerlink" href="#un-exemple-concret-planifier-une-production" title="Permanent link">¶</a></h5>
<p>Un exemple « concret » de situation que ce genre de modèle capture serait le suivant. Nous sommes à la tête d’une armée, en guerre contre une nation. Nous prévoyons de produire 20 avions divisés en deux modèles. Selon le modèle, un avion est armé de <span class="arithmatex">\(b_j\)</span> bombes et <span class="arithmatex">\(m_j\)</span> missiles et il cause des dégâts estimés par <span class="arithmatex">\(c_j\)</span>. On résume tout cela dans le tableau suivant :</p>
<table>
<thead>
<tr>
<th></th>
<th>modèle A</th>
<th>modèle B</th>
</tr>
</thead>
<tbody>
<tr>
<td>bombes</td>
<td>3</td>
<td>15</td>
</tr>
<tr>
<td>missiles</td>
<td>5</td>
<td>10</td>
</tr>
<tr>
<td>dégâts</td>
<td>5</td>
<td>11</td>
</tr>
</tbody>
</table>
<p>On dispose au total de 225 bombes et 160 missiles. La question est la suivante : combien d’avions de chaque modèle doit-on produire pour maximiser les dégâts infligés à l’ennemi ?</p>
<h5 id="modelisons-cela-par-un-programme-doptimisation-lineaire">Modélisons cela par un programme d’optimisation linéaire<a class="headerlink" href="#modelisons-cela-par-un-programme-doptimisation-lineaire" title="Permanent link">¶</a></h5>
<p>Et voici la modélisation mathématique pour se ramener au problème d’optimisation linéaire. On appelle <span class="arithmatex">\(x_A\)</span> et <span class="arithmatex">\(x_B\)</span> les quantités d’avions à produire, respectivement du modèle A et du modèle B. Les dégâts totaux peuvent s’écrire comme <span class="arithmatex">\(5x_A + 11x_B\)</span>, et l’on cherche donc à maximiser <span class="arithmatex">\(f(x_A, x_B) = 5x_A + 11x_B\)</span>.
La première contrainte est évidemment l’ensemble des 20 avions que l’on peut produire. Ainsi <span class="arithmatex">\(x_A + x_B \leq 20\)</span>. De même, nous disposons de contraintes sur le nombre total de bombes et de missiles ce qui conduit à deux contraintes supplémentaires : <span class="arithmatex">\(3x_A + 15x_B \leq 225\)</span> et <span class="arithmatex">\(5x_A + 10x_B \leq 160\)</span>.
Enfin, il faut rajouter des contraintes logiques : les quantités d’avions à produire ne peuvent être que positives et donc <span class="arithmatex">\(x_A\)</span> et <span class="arithmatex">\(x_B\)</span> sont positifs.</p>
<p>Matriciellement, nous aurions <span class="arithmatex">\(c = \begin{pmatrix} 5 \\11 \end{pmatrix}\)</span>, <span class="arithmatex">\(A = \begin{pmatrix}1 & 1 \\ 3 & 15 \\5 & 10 \end{pmatrix}\)</span> et <span class="arithmatex">\(b = \begin{pmatrix} 20 \\ 225 \\ 160 \end{pmatrix}\)</span></p>
<h5 id="visualisons-notre-probleme">Visualisons notre problème<a class="headerlink" href="#visualisons-notre-probleme" title="Permanent link">¶</a></h5>
<p>Comme nous n’avons que deux variables de décision, il est possible de visualiser les contraintes comme montré sur la figure suivante. Chaque contrainte est représentée par une droite limitant les valeurs possibles pour <span class="arithmatex">\(x_A\)</span> et <span class="arithmatex">\(x_B\)</span>.
Par exemple, si l’on prend la première contrainte, en vert sur la figure, tout point dans la zone verte, sous la droite, est un point qui satisfait cette contrainte. Le domaine, dit admissible, des points satisfaisant toutes les contraintes à la fois est obtenu par l’intersection des domaines admissibles pour chaque contrainte prise individuellement. Il se peut donc que le domaine soit non borné, réduit à un point, voire vide, dans le cas où les contraintes sont antinomiques.</p>
<p><center><img alt="" src="images/2015-05-15-reflexions-sur-la-complexite-algorithmique-chapitre-2/simplexe.png" /></center></p>
<p>En l’occurrence, il est défini par le polyèdre délimité par les points noirs. Chaque point à l’intérieur de ce domaine satisfait toutes les contraintes et l’objectif du problème est donc de trouver le point qui maximise notre fonction de départ.
Par exemple, en prenant le point <span class="arithmatex">\((5,5)\)</span>, on obtient <span class="arithmatex">\(f(5,5) = 80\)</span> et l’on voit que l’on peut largement faire mieux avec <span class="arithmatex">\((7,7)\)</span> qui donne <span class="arithmatex">\(f(7,7) = 112\)</span>. Sans plus d’explications, la solution optimale est donnée par <span class="arithmatex">\((4,14)\)</span> pour des dégâts de <span class="arithmatex">\(174\)</span>. Notons au passage que pour faire un maximum de dégâts, il ne nous faut pas construire 20 avions mais seulement 18.</p>
<h5 id="quelques-pistes-pour-resoudre-et-lien-avec-la-complexite">Quelques pistes pour résoudre et lien avec la complexité<a class="headerlink" href="#quelques-pistes-pour-resoudre-et-lien-avec-la-complexite" title="Permanent link">¶</a></h5>
<p>Il existe plusieurs méthodes pour la résolution du problème d’optimisation linéaire et si nous renvoyons le lecteur à la littérature sur le sujet pour de plus amples détails, nous nous contenterons de les citer pour l’intérêt qu’elles présentent en terme de complexité.</p>
<p>Proposée par Dantzig en 1947, la <a href="https://fr.wikipedia.org/wiki/Algorithme_du_simplexe">méthode du Simplexe</a> est un algorithme qui possède une complexité dans le pire des cas qui est exponentielle, mais dont les performances empiriques sont excellentes, au point qu’il s’agit encore aujourd’hui d’une méthode très utilisée.
À contrario, la <a href="https://fr.wikipedia.org/wiki/Méthode_de_l'ellipsoïde">méthode des points intérieurs</a> proposée par Khachiyan en 1979 exhibe une complexité dans le pire des cas qui est polynomiale mais s’avère pourtant inefficace en pratique et la méthode du Simplexe est plus rapide sur l’immense majorité des instances. Enfin, Karmarkar propose en 1984 une <a href="https://fr.wikipedia.org/wiki/Algorithme_de_Karmarkar">variante</a> de la méthode des points intérieurs qui est à la fois efficace théoriquement et en pratique.</p>
<p>On va tenter d’expliquer les raisons qui font que l’on puisse obtenir de telles inconsistances entre les prédictions théoriques de la complexité (dans le pire des cas) et les résultats en pratique. Il s’agit notamment de rétablir ce qu’est exactement un comportement asymptotique, par rapport à ce qu’on essaye de lui faire dire habituellement, puis de présenter les différentes mesures de complexité qui existent et dont la création résulte de la volonté de combler les lacunes de la mesure précédente.</p>
<h4 id="quelques-notations-et-remarques-de-vocabulaire">Quelques notations et remarques de vocabulaire<a class="headerlink" href="#quelques-notations-et-remarques-de-vocabulaire" title="Permanent link">¶</a></h4>
<p>Pour un problème <span class="arithmatex">\(P\)</span>, on note <span class="arithmatex">\(\Pi\)</span> l’ensemble des instances possibles.
On note <span class="arithmatex">\(\Pi_n\)</span> l’ensemble des instances d’un problème dont la taille d’écriture est <span class="arithmatex">\(n\)</span>.
Le nombre d’opérations nécessaires à la résolution de l’instance <span class="arithmatex">\(\pi\)</span> par l’algorithme <span class="arithmatex">\(A\)</span> est noté <span class="arithmatex">\(T_A(\pi)\)</span>.</p>
<h4 id="probleme-dordre-total-pour-la-comparaison-dalgorithmes">Problème d’ordre total pour la comparaison d’algorithmes<a class="headerlink" href="#probleme-dordre-total-pour-la-comparaison-dalgorithmes" title="Permanent link">¶</a></h4>
<p>Nous nous donnons deux algorithmes, <span class="arithmatex">\(A\)</span> et <span class="arithmatex">\(B\)</span>, pour résoudre un problème <span class="arithmatex">\(P\)</span> dont l’ensemble des instances est <span class="arithmatex">\(\Pi\)</span>.
Dans le cas où <span class="arithmatex">\(\Pi\)</span> ne contient qu’une instance <span class="arithmatex">\(\pi\)</span>, on peut comparer simplement les algorithmes <span class="arithmatex">\(A\)</span> et <span class="arithmatex">\(B\)</span> sur le problème <span class="arithmatex">\(P\)</span> en observant le comportement sur <span class="arithmatex">\(\pi\)</span> : si <span class="arithmatex">\(T_A(\pi) \leq T_B(\pi)\)</span> alors <span class="arithmatex">\(A \underset{P}{\succ} B\)</span>, c’est-à-dire que <span class="arithmatex">\(A\)</span> est meilleur que <span class="arithmatex">\(B\)</span> pour la résolution du problème <span class="arithmatex">\(P\)</span>.</p>
<p>Dès lors que l’on introduit une seconde instance <span class="arithmatex">\(\pi’ \in \Pi\)</span>, les choses deviennent moins évidentes. En effet, il se peut que <span class="arithmatex">\(T_A(\pi) \leq T_B(\pi)\)</span> et <span class="arithmatex">\(T_A(\pi’) \geq T_B(\pi’)\)</span>, autrement dit que <span class="arithmatex">\(A\)</span> soit meilleur que <span class="arithmatex">\(B\)</span> pour l’instance <span class="arithmatex">\(\pi\)</span> mais moins bon pour <span class="arithmatex">\(\pi’\)</span>.</p>
<p>Ainsi, il est impossible a priori d’obtenir une <a href="https://fr.wikipedia.org/wiki/Ordre_total">relation d’ordre totale</a> sur les algorithmes <span class="arithmatex">\(A\)</span> et <span class="arithmatex">\(B\)</span> au regard du problème <span class="arithmatex">\(P\)</span>. Il est évident que plus l’ensemble des instances est large et plus la probabilité de pouvoir établir une telle relation tend vers 0.</p>
<p>Il faut malgré tout trouver une mesure d’efficacité pour les algorithmes afin de pouvoir les comparer. Une mesure qui s’est imposée est la mesure <a href="https://fr.wikipedia.org/wiki/Comparaison_asymptotique#.C3.89chelle_de_comparaison">asymptotique en fonction de la taille du problème</a>. Comme nous allons le voir, cela n’est pas sans poser quelques problèmes de première importance.</p>
<h3 id="mesures-de-complexite-dun-algorithme">Mesures de complexité d’un algorithme<a class="headerlink" href="#mesures-de-complexite-dun-algorithme" title="Permanent link">¶</a></h3>
<h4 id="remarques-preliminaires">Remarques préliminaires<a class="headerlink" href="#remarques-preliminaires" title="Permanent link">¶</a></h4>
<p>On définit la complexité d’un problème comme la complexité minimale d’un algorithme permettant de résoudre toutes les instances de ce problème<sup id="fnref:1"><a class="footnote-ref" href="#fn:1">2</a></sup>. Cependant, en disant cela, non seulement on manque de précision en omettant que nous prenons pour référence la complexité dans le pire des cas, mais en plus, on fait naître un tas de questions auxquelles cet indicateur uni-dimensionnel ne peut vraisemblablement répondre.</p>
<p>En effet, quelle est la répartition des instances par rapport à leur difficulté ? Quelle est la sensibilité de mon algorithme par rapport à la perturbation des instances ? Quelle est l’efficacité pratique de mon algorithme ? Pour répondre à ces questions, plusieurs mesures de la complexité algorithmique ont été développées.</p>
<h4 id="pire-des-cas">Pire des cas<a class="headerlink" href="#pire-des-cas" title="Permanent link">¶</a></h4>
<p>La mesure la plus fréquente est la mesure dans le pire des cas. Il s’agit de donner une borne supérieure du nombre d’étapes nécessaires à la terminaison de l’algorithme sur l’ensemble des instances du problème qu’il résout. De manière formelle, la complexité d’un algorithme dans le pire des cas est défini par : <span class="arithmatex">\(T_{\text{max}}(n) = \underset{\pi \in \Pi_n }{\text{max}}~T(\pi)\)</span>.</p>
<p>Il peut être difficile de trouver la valeur exacte en fonction de <span class="arithmatex">\(n\)</span>, et l’on utilise souvent la notation de Landeau <span class="arithmatex">\(\mathcal{O}\)</span> pour exprimer l’ordre de grandeur. Dire que l’algorithme <span class="arithmatex">\(\mathcal{A}\)</span> a une complexité dans le pire des cas de <span class="arithmatex">\(\mathcal{O}(n^2)\)</span> veut dire <span class="arithmatex">\(\exists a \in \mathbb{N}, ~\forall \pi \in \Pi_n,~ T(\pi) \leq a \times n^2\)</span>.</p>
<p>Il faut comprendre que si <span class="arithmatex">\(T_{\max}(.)\)</span> est le nombre exact du nombre d’opérations effectuées dans le pire des cas, <span class="arithmatex">\(\mathcal{O}(.)\)</span> ne représente qu’une approximation dont la précision grandit avec la taille du problème : on parle d’estimation asymptotique.</p>
<h4 id="meilleur-des-cas">Meilleur des cas<a class="headerlink" href="#meilleur-des-cas" title="Permanent link">¶</a></h4>
<p>La mesure de la complexité dans le meilleur des cas se définit symétriquement par rapport à la notion dans le pire des cas : <span class="arithmatex">\(T_{\text{min}}(n) = \underset{\pi \in \Pi_n}{min} ~ T(\pi)\)</span>, c’est-à-dire comme le minimum du nombre d’étapes pour résoudre une instance parmi toutes les instances.</p>
<p>De fait, nous obtenons un encadrement sur le nombre d’opérations nécessaires à la résolution d’un problème, c’est-à-dire indépendamment de l’instance choisie :</p>
<div class="arithmatex">\[\forall n\in \mathbb{N},~ \forall \pi \in \Pi_n, ~ T_{\text{min}}(n) \leq T(\pi) \leq T_{\text{max}}(n)\]</div>
<h4 id="etude-de-lencadrement-sur-exemple">Étude de l’encadrement sur exemple<a class="headerlink" href="#etude-de-lencadrement-sur-exemple" title="Permanent link">¶</a></h4>
<p>Imaginons que l’on dispose de trois algorithmes dont on a calculé la complexité dans le pire et le meilleur des cas et que l’on peut résumer par le tableau suivant :</p>
<table>
<thead>
<tr>
<th>Algorithme</th>
<th>Meilleur des cas</th>
<th>Pire des cas</th>
</tr>
</thead>
<tbody>
<tr>
<td><strong>A</strong></td>
<td><span class="arithmatex">\(f_{\text{min}}(n)=n^2\)</span></td>
<td><span class="arithmatex">\(f_{\text{max}}(n)=n^2 \times \frac{log(n)}{2}\)</span></td>
</tr>
<tr>
<td><strong>B</strong></td>
<td><span class="arithmatex">\(g_{\text{min}}(n)=0\)</span></td>
<td><span class="arithmatex">\(g_{\text{max}}(n)=n^2 + 2000 \times \mid cos(n)\mid\)</span></td>
</tr>
<tr>
<td><strong>C</strong></td>
<td><span class="arithmatex">\(h_{\text{min}}(n)=5000\)</span></td>
<td><span class="arithmatex">\(h_{\text{max}}(n)=n^{\frac 6 5} \times log(x^5 + 2x^3 + 7x^2) + 5000\)</span></td>
</tr>
</tbody>
</table>
<p>Sur la figure qui suit, on peut observer le domaine du nombre d’opérations pour chacun des trois algorithmes. Quelle que soit l’instance considérée, le nombre d’opérations sera toujours dans la zone colorée. Remarquons par exemple que l’algorithme <span class="arithmatex">\(A\)</span> possède un nombre minimal d’opérations qui dépend de la taille de l’instance tandis que l’algorithme <span class="arithmatex">\(C\)</span> possède un coût minimal fixe de <span class="arithmatex">\(5000\)</span>, qui correspond certainement à un pré-traitement indépendant de la taille de l’instance. Enfin, l’algorithme <span class="arithmatex">\(B\)</span> possède un comportement oscillant pour sa borne supérieure, malgré une tendance croissante. Si cette oscillation n’a que peu d’importance au fur et à mesure que les instances grandissent, elle peut cependant être importante pour des instances de petite taille.</p>
<p><center><img alt="" src="images/2015-05-15-reflexions-sur-la-complexite-algorithmique-chapitre-2/encadrement.png" /></center></p>
<p>Voyons maintenant les différences qu’il peut exister entre la complexité exacte et la complexité asymptotique. Les cinq images suivantes montrent le tracé de la complexité exacte et asymptotique en fonction de la taille des instances. Dans le cas de l’algorithme C, on dispose également de deux plages différentes de taille d’instances, ce qui nous permettra de visualiser certains défauts de la complexité asymptotique pour l’évaluation pratique de la performance des algorithmes.</p>
<p>Pour l’algorithme A, on constate sur la figure suivante que l’estimation asymptotique est une borne supérieure au nombre d’opérations, et ce, quel que soit la plage de valeurs de la taille des instances considérées.</p>
<p><center><img alt="" src="images/2015-05-15-reflexions-sur-la-complexite-algorithmique-chapitre-2/encadrement3.png" /></center></p>
<p>À contrario, dans le cas de l’algorithme <span class="arithmatex">\(B\)</span> l’ordre de grandeur asymptotique (OGA, sigle propre à cet article) de la complexité exacte est toujours majoré par la valeur exacte. Cependant, on pressent que pour de grandes valeurs de <span class="arithmatex">\(n\)</span>, cela est moins problématique, comme on le vérifiera par la suite.</p>
<p><center><img alt="" src="images/2015-05-15-reflexions-sur-la-complexite-algorithmique-chapitre-2/encadrement4.png" /></center></p>
<p>Le cas de l’algorithme <span class="arithmatex">\(C\)</span> est intéressant puisque le coût constant n’apparaît évidemment pas dans l’OGA et de ce fait, pour de petites valeurs de <span class="arithmatex">\(n\)</span>, l’OGA décrit un comportement qu’il n’est pas possible d’obtenir. Il est en effet impossible d’obtenir une instance de taille 40 qui ne nécessite que 500 opérations par exemple. On tombe ensuite exactement dans le cas de figure de l’algorithme <span class="arithmatex">\(B\)</span>, les oscillations en moins, c’est-à-dire que l’OGA sous-estime toujours la valeur exacte mais qu’à terme, cette différence est négligeable dans le nombre total exact d’opérations.</p>
<p><center><img alt="" src="images/2015-05-15-reflexions-sur-la-complexite-algorithmique-chapitre-2/encadrement5.png" /></center>
<center><img alt="" src="images/2015-05-15-reflexions-sur-la-complexite-algorithmique-chapitre-2/encadrement6.png" /></center></p>
<p>C’est ce que l’on peut observer sur les deux figures qui suivent et qui représentent l’écart relatif entre le nombre d’opérations exact et son OGA. Il y a plusieurs remarques à faire :</p>
<ol>
<li>
<p>Les algorithmes <span class="arithmatex">\(B\)</span> et <span class="arithmatex">\(C\)</span> présentent une convergence vers <span class="arithmatex">\(0\)</span> lorsque la taille <span class="arithmatex">\(n\)</span> tend vers l’infini. Ceci permet de relativiser le fait que l’OGA donne sur ces deux cas une valeur inférieure au nombre exact. Ceci permet de mettre en évidence la définition même de la complexité asymptotique : le nombre d’opérations de l’algorithme va se comporter comme son OGA au voisinage de l’infini, où l’infini est en pratique une notion qui dépend de l’algorithme et de l’utilisateur (c’est-à-dire de l’utilisation qu’il fait de l’algorithme et ce qu’il en attend). On remarque ainsi qu’on peut raisonnablement considérer que l’algorithme <span class="arithmatex">\(B\)</span> se comporte comme son OGA pour une taille environ égale à 400 tandis que pour l’algorithme <span class="arithmatex">\(C\)</span>, il faut attendre plus longtemps.
Et voici où la complexité asymptotique échoue : en supposant que l’utilisateur de l’algorithme <span class="arithmatex">\(B\)</span> ou <span class="arithmatex">\(C\)</span> ne va avoir à traiter en pratique que des instances de taille comprise entre 0 et 100, alors on peut voir que l’algorithme est très loin de se comporter comme le prédit la complexité asymptotique. C’est d’autant plus visible sur l’algorithme <span class="arithmatex">\(B\)</span> dont les oscillations sont prépondérantes pour ces valeurs. Or, à partir du moment où l’on n’indique pas les tailles pour lesquelles les algorithmes vont avoir une complexité qui va se comporter comme leur OGA, la prédiction d’un algorithme sur un jeu d’instances peut être largement faussée, tout comme la comparaison entre deux algorithmes à priori.</p>
</li>
<li>
<p>L’importance de la constante multiplicative du terme prépondérant, c’est-à-dire celle de l’OGA, est totalement passée sous silence. Or, on voit très bien que dans le cas de l’algorithme <span class="arithmatex">\(A\)</span>, l’écart entre la valeur donnée par l’asymptote et la valeur exacte ne va jamais tendre vers 0. Dans ce cas précis, l’OGA indique un nombre d’opérations deux fois supérieur au nombre exact et il ne s’agit pourtant que d’un petit facteur <span class="arithmatex">\(\frac 1 2\)</span>. On peut imaginer à quel point les prédictions sont faussées par des constantes énormes qui peuvent apparaitre dans le calcul exact mais pas dans l’OGA, avec pour effet de rendre la comparaison d’algorithmes impossible <em>à priori</em> comme nous le verrons par la suite.</p>
</li>
</ol>
<p><center><img alt="" src="images/2015-05-15-reflexions-sur-la-complexite-algorithmique-chapitre-2/ecart_asymptotique.png" /></center>
<center><img alt="" src="images/2015-05-15-reflexions-sur-la-complexite-algorithmique-chapitre-2/ecart_asymptotique_zoom.png" /></center></p>
<h4 id="complexite-en-moyenne">Complexité en moyenne<a class="headerlink" href="#complexite-en-moyenne" title="Permanent link">¶</a></h4>
<h5 id="vers-la-complexite-en-moyenne">Vers la complexité en moyenne<a class="headerlink" href="#vers-la-complexite-en-moyenne" title="Permanent link">¶</a></h5>
<p>L’encadrement donné plus haut atteint ses limites assez rapidement. Dans bien des problèmes un peu complexes, il est possible que notre algorithme ne soit pas capable de traiter un ensemble d’instances particulières ou que sa complexité dans le pire des cas soit telle qu’on puisse la considérer comme infinie même pour des instances de petite taille.</p>
<p>Malgré tout, on remarque très souvent qu’en pratique ces cas pathologiques n’arrivent que rarement si ce n’est jamais, et l’on peut munir l’espace <span class="arithmatex">\(\Pi\)</span> d’une <a href="https://fr.wikipedia.org/wiki/Problème_de_tournées_de_véhicules">distribution de probabilité</a>, décrivant la probabilité d’apparition d’une instance à traiter en pratique. On appelle par la suite, par commodité, l’ensemble des instances dont la probabilité d’apparition est strictement supérieure à 0 le « sous-ensemble des instances pratiques ».</p>
<p>Le sous-ensemble des instances pratiques dépend de la configuration de l’exploitation de l’algorithme. C’est-à-dire que d’une part pour un même algorithme utilisé par une entreprise A et une entreprise B, la plage de la taille possible des instances peut varier, et d’autre part, de par leurs activités différentes elles peuvent ne pas avoir les mêmes cas à traiter en règle générale.</p>
<p>Prenons un exemple concret, avec Amazon et un petit libraire qui utilisent tous deux le même algorithme de <a href="https://fr.wikipedia.org/wiki/Probl%C3%A8me_de_tourn%C3%A9es_de_v%C3%A9hicules">tournée de véhicules</a> afin de déterminer le plan pour les livraisons de leurs livres. Évidemment le libraire ne livre que dans son quartier et a moins de commandes à traiter qu’Amazon. De fait, si le domaine théorique pour le nombre de clients à livrer est <span class="arithmatex">\(\mathbb{N}\)</span>, en pratique il sera probablement <span class="arithmatex">\([a_1,a_2] \subset \mathbb{N}\)</span> pour Amazon et <span class="arithmatex">\([b_1,b_2] \subset \mathbb{N}\)</span> pour le libraire, avec à priori <span class="arithmatex">\(b_2 < a_2\)</span>, pour traduire le fait qu’Amazon peut recevoir bien plus de commandes. Mais ce n’est pas tout ! Avec ces mêmes considérations sur le nombre de clients, il est probable que le nombre de commandes du libraire soit bien plus variable au sein de sa plage que celui d’Amazon, par la force de la <a href="https://fr.wikipedia.org/wiki/Loi_des_grands_nombres">loi des grands nombres</a>. Ainsi, pour Amazon, la distribution du nombre de clients par jour suivra peut-être quelque chose qui ressemble à une <a href="https://fr.wikipedia.org/wiki/Loi_normale">loi normale</a>, centrée sur <span class="arithmatex">\(\frac{a_1+a_2}{2}\)</span>, tandis que dans le cas du libraire il se pourrait que le nombre de clients se modélise plutôt par une <a href="https://fr.wikipedia.org/wiki/Loi_uniforme_discrète">loi uniforme</a> sur <span class="arithmatex">\([b_1,b_2]\)</span>. Encore plus problématique, pour une même taille de problème, la configuration géographique des clients pourrait grandement influer sur le nombre d’opérations nécessaires à l’algorithme pour trouver la solution.</p>
<p>La complexité dans le meilleur et le pire des cas ne permettent pas de capter ces notions. C’est pourquoi d’autres approches, comme la <strong>complexité en moyenne</strong>, la <strong>complexité amortie</strong> ou la <strong>complexité lisse</strong>, tentent de combler ces lacunes.</p>
<p>Partant du principe que les instances pathologiques sont souvent exclues du sous-ensemble des instances pratiques ou suffisamment rares en son sein pour ne pas être considérées comme significatives, on s’intéresse à la complexité en moyenne d’un algorithme. Par cette approche on essaye de déterminer le comportement normal ou attendu d’un algorithme. Mais contrairement à l’idée reçue, il ne s’agit pas de simplement faire une moyenne du nombre d’opérations nécessaires à la résolution de chaque instance possible – ceci étant un cas particulier et par ailleurs plus proche de la complexité amortie –, mais d’émettre une hypothèse sur la distribution de probabilité d’apparition des instances possibles. Il s’agit donc avant toute chose d’une mesure vis-à-vis d’une situation d’exploitation plus ou moins concrète puisqu’elle présuppose de répondre en amont à la question de la distribution des instances.</p>
<h5 id="presentation-et-discussion-de-la-complexite-en-moyenne">Présentation et discussion de la complexité en moyenne<a class="headerlink" href="#presentation-et-discussion-de-la-complexite-en-moyenne" title="Permanent link">¶</a></h5>
<p>Supposons une mesure de probabilité <span class="arithmatex">\(\mu\)</span> sur l’ensemble des instances <span class="arithmatex">\(\Pi\)</span> . Alors la complexité moyenne est definie par <span class="arithmatex">\(\bar T(\Pi) = E_\mu[T(\Pi)]\)</span>, c’est-à-dire l’espérance par rapport à cette mesure.</p>
<p>Dans le cas où <span class="arithmatex">\(\Pi\)</span> est un ensemble discret, on a <span class="arithmatex">\(\bar T(\Pi) = E_\mu[T(\Pi)] = \underset{{\pi \in \Pi} }{\sum}\mu(\pi) T(\pi)\)</span>, et pour <span class="arithmatex">\(\Pi\)</span> continu <span class="arithmatex">\(\bar T(\Pi) = E_\mu[T(\Pi)] = \int_{\Pi} T(\pi) \mu(d\pi)\)</span>.</p>
<p>Remarquez que contrairement à la complexité dans le pire ou le meilleur des cas, les instances considérées ne sont pas nécessairement de la même taille. En pratique, le calcul exact de la complexité en moyenne est extrêmement difficile si ce n’est impossible car il suppose que l’on puisse obtenir le nombre exact d’opérations nécessaires à la résolution de chacune des instances de l’ensemble <span class="arithmatex">\(\Pi\)</span>.</p>
<p>En plus de cela, le calcul exact perd tout intérêt en sachant que la mesure de probabilité <span class="arithmatex">\(\mu\)</span> n’est jamais connue en pratique, si ce n’est pour des exemples artificiels. Par exemple si l’on génère de manière aléatoire des tableaux à trier de même taille, où chaque case sera remplie selon une même loi uniforme, alors toutes les instances auront même probabilité et l’on retrouvera un calcul de <a href="https://fr.wikipedia.org/wiki/Moyenne_arithmétique">moyenne arithmétique</a> habituelle (le cas particulier évoqué plus haut).</p>
<p>Comme le calcul exact est rendu impossible, on préférera une approche empirique : on mesure les performances moyennes de l’algorithme en phase d’exploitation, par exemple au niveau d’Amazon ou de notre petit libraire. Les résultats seront bien différents et le désavantage sera de ne pouvoir tirer de conclusion générale sur la difficulté du problème en tant que tel ou bien sur les capacités globales de l’algorithme sur le problème donné.</p>
<p>Cela rajoute un élément à l’objet dont on cherche à caractériser la difficulté. En effet, auparavant on avait la simple composante <span class="arithmatex">\((\text{algorithme})\)</span> et maintenant nous avons le couple <span class="arithmatex">\((\text{algorithme}, \text{utilisateur})\)</span>. Évidemment on pourrait faire une moyenne pour chacun des utilisateurs pour se ramener à une complexité moyenne de l’algorithme. C’est bien sûr impossible logistiquement parlant mais également pas tout à fait souhaitable à bien des égards, notamment parce que l’on cherche plutôt une caractérisation <em>à priori</em> de la difficulté d’un problème et non pas <em>à postériori</em> par l’efficacité pratique d’un algorithme.</p>
<p>Une remarque importante à faire est que pour l’évaluation empirique, on préférera utiliser la <a href="https://fr.wikipedia.org/wiki/Médiane_(statistiques)">valeur médiane</a> du nombre d’opérations car elle est moins sensible aux valeurs extrêmes. Pour compléter, l’étude de la différence entre la valeur médiane et la moyenne permet de confirmer ou d’infirmer l’hypothèse selon laquelle les instances difficiles apparaissent peu souvent. En réalité, un <a href="https://fr.wikipedia.org/wiki/Histogramme">histogramme</a> serait la solution la plus complète car il permet d’observer la distribution de la difficulté des instances et de mettre en place des <a href="https://fr.wikipedia.org/wiki/Test_(statistique)">tests statistiques</a> pour valider notre hypothèse initiale sur la distribution.</p>
<h4 id="analyse-amortie">Analyse amortie<a class="headerlink" href="#analyse-amortie" title="Permanent link">¶</a></h4>
<p>L’idée principale de l’analyse amortie est de considérer que certaines opérations coûteuses apportent un bénéfice à l’ensemble du flux d’instructions qui suit, amortissant ce (sur)coût.</p>
<p>L’exemple le plus simple serait la politique d’allocation d’un <a href="https://fr.wikipedia.org/wiki/Vecteur_(structure_de_données)">tableau dynamique</a>. Celui-ci est constitué d’une capacité mémoire <span class="arithmatex">\(c\)</span>, contiguë, et d’une taille <span class="arithmatex">\(t\)</span>, qui est le nombre d’éléments présents dans le tableau. Lorsque l’on ajoute un élément il peut se passer deux cas :</p>
<ul>
<li><span class="arithmatex">\(t < c\)</span> : il reste donc de la place en mémoire et on peut ajouter l’élément en temps constant, c’est-à-dire asymptotiquement en <span class="arithmatex">\(\mathcal{O}(1)\)</span>.</li>
<li><span class="arithmatex">\(t = c\)</span> : et donc il n’y a pas assez de place pour rajouter l’élément. Comme il faut conserver la propriété de continuité en mémoire, une nouvelle zone mémoire est allouée, plus grande, et les éléments déjà présents sont copiés de l’ancien emplacement au nouveau, puis le nouvel élément est inséré, ce qui se fait cette fois en <span class="arithmatex">\(\mathcal{O}(t)\)</span>.</li>
</ul>
<h5 id="lexemple-du-tableau-dynamique">L’exemple du tableau dynamique<a class="headerlink" href="#lexemple-du-tableau-dynamique" title="Permanent link">¶</a></h5>
<p>Quelle est la complexité dans le pire des cas de l’opération d’insertion pour un tableau dynamique ? La réponse est <span class="arithmatex">\(\mathcal{O}(t)\)</span> en considérant que l’on démarre avec une capacité de 0 et que l’on n’agrandit le tableau que d’une unité à chaque fois. Mais d’une part, on peut retarder le besoin d’une nouvelle allocation en initialisant notre tableau avec une capacité qui est la taille estimée nécessaire pour notre application ; et d’autre part, on peut se dire que dans tous les cas, n’augmenter la capacité que d’une unité n’est pas un bon pari pour l’avenir. Le travail de l’analyse amortie est donc de prendre en compte le fait que certaines opérations coûteuses permettent l’existence de multiples opérations non-coûteuses et que donc, dans la complexité, on peut « répartir » le coût de ces lourdes opérations sur toutes les opérations élémentaires engendrées.</p>
<p>Pour définir la complexité amortie, il faut définir le coût amorti de chaque opération, lors d’une série de <span class="arithmatex">\(n\)</span> opérations : <span class="arithmatex">\(T_{\text{amo}}(n) = \frac{T_{\text{max}}(n)}{n}\)</span> <sup id="fnref:2"><a class="footnote-ref" href="#fn:2">3</a></sup>.</p>
<p>Dans le cas du tableau dynamique, on remarque que pour insérer <span class="arithmatex">\(n\)</span> valeurs dans un tableau de taille <span class="arithmatex">\(n\)</span>, cela prend pour chaque opération un temps constant, sauf pour la dernière qui déclenche une réallocation en <span class="arithmatex">\(\mathcal{O}(n)\)</span>. Ainsi, la complexité amortie pour l’insertion est donnée par <span class="arithmatex">\(T_{\text{amo}}(n) = \frac{\mathcal{O}(n)}{n} = \mathcal{O}(1)\)</span>.</p>
<p>Les trois figures suivantes illustrent le nombre nécessaire d’opérations pour une série allant de 1 à 10 insertions en partant d’un tableau vide, avec l’évolution de la capacité disponible. La première politique consiste à simplement incrémenter la capacité lorsque cela est nécessaire, autrement dit à chaque insertion. La seconde politique se donne un peu plus de marge en ajoutant trois à la capacité. Enfin la dernière multiplie la taille de la capacité par deux chaque fois que cela est nécessaire. On a donc une progression exponentielle de la capacité dans ce cas.</p>
<p><center><img alt="" src="images/2015-05-15-reflexions-sur-la-complexite-algorithmique-chapitre-2/histogramme.png" /></center>
<center><img alt="" src="images/2015-05-15-reflexions-sur-la-complexite-algorithmique-chapitre-2/histogramme2.png" /></center>
<center><img alt="" src="images/2015-05-15-reflexions-sur-la-complexite-algorithmique-chapitre-2/histogramme3.png" /></center></p>
<p>Il est évident que la première politique est optimale en terme de capacité : aucun espace mémoire n’est jamais inutilisé. Par contre, elle possède un coût moyen important qui est même le pire des cas possibles. Rien que le fait d’ajouter trois unités au lieu d’une seule permet de faire tomber sensiblement le coût moyen de la série d’insertions à 2,8 mais augmente <em>de facto</em> la capacité moyenne, laquelle passe de 5,5 à 6,6. Enfin, la politique exponentielle permet de diminuer encore un peu le nombre moyen d’opération à 2,5 tout en augmenter légèrement la capacité moyenne.</p>
<p>En réalité, si l’on refaisait le tracé sur une série d’insertions plus longue, on s’apercevrait que les politiques additives sont peu <em>scalables</em> par rapport aux politiques exponentielles, c’est à dire qu’elles sont mal adaptées au changement d’ordre de grandeur de la taille des tableaux utilisés. Ceci explique qu’en pratique on n’utilise que ces dernières, puisqu’elles permettent un meilleur compromis entre la capacité inutilisée et le nombre moyen d’opérations à effectuer.</p>
<h5 id="discussion-sur-lanalyse-amortie">Discussion sur l’analyse amortie<a class="headerlink" href="#discussion-sur-lanalyse-amortie" title="Permanent link">¶</a></h5>
<p>Bien souvent, l’amélioration de l’analyse amortie se fait par des <a href="https://fr.wikipedia.org/wiki/Heuristique_(mathématiques)">heuristiques</a> qui font augmenter la complexité dans le pire des cas ou d’autres caractéristiques comme la complexité spatiale (par exemple, dans le cas du tableau dynamique, on a en pratique en permanence une occupation mémoire qui n’est pas nécessaire). Il est aussi possible que ces heuristiques rendent difficile l’étude de la complexité dans le pire des cas. Cependant, leur but est d’apporter plus de robustesse à l’algorithme, qui réagira mieux en limitant l’impact des opérations coûteuses sur la grande majorité des instances. Le réglage de ces heuristiques est un choix souvent lié à un compromis comme nous l’avons vu sur l’exemple précédent, et l’on abordera très rapidement cette question à la fin de cet article. Notons simplement que dans les cas simples comme celui d’un tableau dynamique, le choix <em>exact</em> des paramètres n’a guère d’influence et c’est ainsi qu’on conseille théoriquement de doubler la taille du tableau à chaque réallocation, mais que les listes en Python utilisent un facteur <span class="arithmatex">\(\frac{9}{8}\)</span><sup id="fnref:3"><a class="footnote-ref" href="#fn:3">4</a></sup> par exemple.</p>
<h5 id="lexemple-spectaculaire-dunion-find">L’exemple spectaculaire d’Union-Find<a class="headerlink" href="#lexemple-spectaculaire-dunion-find" title="Permanent link">¶</a></h5>
<p>Il me semble important de présenter l’une des applications les plus spectaculaires de la complexité amortie, à savoir le cas de la structure de données <a href="https://fr.wikipedia.org/wiki/Union-Find">Union-Find</a>, utilisée entre autre dans l’<a href="https://fr.wikipedia.org/wiki/Algorithme_de_Kruskal">algorithme de Kruskal</a> pour la recherche d’<a href="https://fr.wikipedia.org/wiki/Arbre_couvrant_de_poids_minimal">arbre couvrant de poids minimal</a>.
Union-Find est une structure de données utile pour maintenir une partition d’un ensemble en <a href="http://fr.wikipedia.org/wiki/Classe_(mathématiques)">classes</a> disjointes. Elle possède deux opérations :</p>
<ul>
<li>Find, qui détermine la classe à laquelle appartient d’un élément en renvoyant son « représentant » ;</li>
<li>Union, qui fusionne deux classes en une seule.</li>
</ul>
<p>Sans plus d’informations, l’implémentation peut se faire via l’utilisation de différentes structures de données sous-jacentes, mais va alors entrainer des complexités différentes. C’est ainsi qu’une implémentation triviale utilisant des <a href="https://fr.wikipedia.org/wiki/Liste_chaînée">listes chaînées</a> pour la représentation des classes aura une complexité amortie en <span class="arithmatex">\(\mathcal{O}(m+n\;\text{log}~n)\)</span> lorsque l’on effectue <span class="arithmatex">\(m\)</span> appels successifs à Union puis Find sur <span class="arithmatex">\(n\)</span> éléments.</p>
<p>Une solution est alors d’utiliser des <a href="https://fr.wikipedia.org/wiki/Arbre_enraciné">arbres</a> qui, combinés à une heuristique dite du <em>rang</em>, permettent de faire tomber la complexité amortie à <span class="arithmatex">\(\mathcal{O}(\text{log}~n)\)</span>. L’utilisation d’une seconde heuristique, la compression de chemin, permet de faire tomber la complexité en… <span class="arithmatex">\(\mathcal{O}(\alpha(n))\)</span> où <span class="arithmatex">\(\alpha\)</span> est l’inverse de la <a href="https://fr.wikipedia.org/wiki/Fonction_d'Ackermann">fonction d’Ackermann</a>.</p>
<p>La fonction d’Ackermann est une fonction qui croit tellement vite que l’on peut considérer que son inverse est inférieure ou égale à quatre quelle que soit la valeur de <span class="arithmatex">\(n\)</span>. En effet, la fonction d’Ackermann en <span class="arithmatex">\(4\)</span> est de l’ordre de <span class="arithmatex">\(10^{80}\)</span>, autrement dit l’ordre de grandeur du nombre d’atomes dans l’univers ! Et si l’on renvoie le lecteur à la littérature pour plus de renseignements sur Union-Find et la démonstration de la complexité amortie associée, l’exemple est donné pour prendre conscience de l’écart entre ce que prédit la complexité dans le pire des cas et le comportement <em>en pratique</em>, représenté par la complexité amortie.</p>
<p>Pire, on voit que de simples petites idées, comme les deux heuristiques utilisées par Union-Find, peuvent modifier drastiquement la complexité amortie tandis que la complexité dans le pire des cas reste la même voire augmente.</p>
<h5 id="insistons-sur-les-differences-avec-lanalyse-en-moyenne">Insistons sur les différences avec l’analyse en moyenne<a class="headerlink" href="#insistons-sur-les-differences-avec-lanalyse-en-moyenne" title="Permanent link">¶</a></h5>
<p>De prime abord, la différence entre l’analyse amortie et l’analyse en moyenne peut ne pas sembler flagrante. Je me permets donc d’insister sur les éléments distinctifs : le niveau de granularité étudié et surtout, la notion d’état. Dans le cas de l’analyse en moyenne, on étudie la répartition des instances difficiles en supposant (ou estimant) une distribution de probabilité sur l’ensemble des instances. En d’autres termes, on s’intéresse aux instances. Dans le cas de l’analyse amortie, on considère <span class="arithmatex">\(n\)</span> étapes au sein d’un algorithme et l’on s’intéresse à comment en moyenne les opérations coûteuses et non-coûteuses peuvent se compenser. On est à un niveau de granularité plus faible, ce qui est rendu possible par le fait que l’on considère des étapes d’un algorithme qui sont liées entre elles par la modification d’un état (par exemple la mémoire dans l’exemple du tableau dynamique).</p>
<p>Ainsi l’analyse amortie est particulièrement utile pour les structures de données et les algorithmes qui maintiennent un état en évolution tout au long de leur exécution. Les deux approches peuvent donc être complémentaires.</p>
<h4 id="analyse-lisse">Analyse lisse<a class="headerlink" href="#analyse-lisse" title="Permanent link">¶</a></h4>
<p>Si la complexité en moyenne a été introduite pour pallier certaines limitations de la complexité dans le pire des cas, la complexité lisse a pour but d’être une synthèse permettant d’outrepasser les limitations des mesures de complexité précédentes et notamment en expliquant pourquoi certains algorithmes restent efficaces en pratique contrairement aux études théoriques effectuées jusque-là.</p>
<p>Développée dans les années 2000, l’analyse lisse consiste à étudier le comportement d’un algorithme sur un ensemble d’instances en les perturbant légèrement de manière aléatoire.</p>
<p>Plus formellement, on suppose que l’on dispose d’un opérateur <span class="arithmatex">\(K\)</span> de perturbation aléatoire sur l’ensemble <span class="arithmatex">\(\Pi_n\)</span> des instances de taille <span class="arithmatex">\(n\)</span>. Cela permet de définir une espérance sur le nombre d’opérations, exprimée par <span class="arithmatex">\(\forall \pi \in \Pi_n, ~ \bar \pi = E[T(K\pi)]\)</span>.</p>
<p>Alors la complexité lisse d’un algorithme sur <span class="arithmatex">\(\Pi_n\)</span> est donnée par :</p>
<div class="arithmatex">\[T^K_{\text{lis}}(n) = \underset{\pi \in \Pi_n}{max}~ \bar \pi = \underset{\pi \in \Pi_n}{max}~ E[T(K\pi)]\]</div>
<p>Elle est donc relative à un opérateur de perturbation choisi.</p>
<p>Supposons que l’on puisse métriser l’espace <span class="arithmatex">\(\Pi_n\)</span> avec une distance <span class="arithmatex">\(d\)</span> et que notre opérateur de perturbation soit paramétré par une variance <span class="arithmatex">\(\sigma\)</span> qui mesure l’amplitude de perturbation. Autrement dit <span class="arithmatex">\(\forall ~ 0 \leq \sigma_1 \leq \sigma_2,~ d(K_{\sigma_1}\pi,\pi) \leq d(K_{\sigma_2}\pi, \pi)\)</span> <a href="https://fr.wikipedia.org/wiki/Ensemble_négligeable#.C2.AB_Presque_s.C3.BBrement_.C2.BB">presque sûrement</a><sup id="fnref:4"><a class="footnote-ref" href="#fn:4">5</a></sup>. Ainsi lorsque <span class="arithmatex">\(\sigma\)</span> tend vers 0, <span class="arithmatex">\(d(K_\sigma\pi,\pi)\)</span> tend vers <span class="arithmatex">\(0\)</span>, ce qui signifie alors que <span class="arithmatex">\(K\)</span> est équivalent à l’identité : <span class="arithmatex">\(K\pi = \pi\)</span>.</p>
<p>Alors, on remarque que lorsque <span class="arithmatex">\(\sigma\)</span> tend vers 0, on retrouve la complexité dans le pire des cas :</p>
<div class="arithmatex">\[T^K_{\text{lis}}(n) = \underset{\pi \in \Pi_n}{max}~ E[T(K\pi)] = \underset{\pi \in \Pi_n}{max}~ E[T(\pi)] = \underset{\pi \in \Pi_n}{max}~ T(K\pi) = T_{\text{max}}(n)\]</div>
<p>Dans le cas où <span class="arithmatex">\(\sigma\)</span> tend vers l’infini, on retrouve la complexité en moyenne.</p>
<div class="admonition example">
<p class="admonition-title">Exemple de perturbation:</p>
<p>Considérons que <span class="arithmatex">\(\Pi_n = \mathbb{R}^n\)</span> qui est un domaine très courant dans en simulation numérique, optimisation ou traitement du signal par exemple. L’opérateur de perturbation gaussien est défini comme <span class="arithmatex">\(K_{\sigma^2} : \mathbb{R}^n \to \mathbb{R}^n\)</span> avec <span class="arithmatex">\(K_{\sigma^2} : \pi \mapsto \pi + g\)</span> où <span class="arithmatex">\(g\)</span> est un vecteur gaussien centré de dimension <span class="arithmatex">\(n\)</span>.</p>
</div>
<p>Malheureusement, avec l’intervention de l’opérateur <span class="arithmatex">\(K\)</span> qui est lui-même paramétré, il faut changer quelque peu la définition de complexité polynomiale pour lui donner un sens au sein de l’analyse lisse.</p>
<div class="admonition def">
<p class="admonition-title">Définition (complexité lisse polynomiale)</p>
<p>L’algorithme <span class="arithmatex">\(A\)</span> a une complexité lisse polynomiale s’il existe des constantes <span class="arithmatex">\(n_0\)</span>, <span class="arithmatex">\(\sigma_0\)</span>, <span class="arithmatex">\(c\)</span>, <span class="arithmatex">\(k_1\)</span> et <span class="arithmatex">\(k_2\)</span> telles
que pour tout <span class="arithmatex">\(n > n_0\)</span> et <span class="arithmatex">\(0 \leq \sigma \leq \sigma_0,~ T^{K_{\sigma^2}}_{lis}(n) \leq c \frac{n^{k_1}}{\sigma^{k_2}}\)</span>.</p>
</div>
<p>L’intérêt d’une formulation probabiliste est que l’on peut faire intervenir les outils habituels et puissants de la théorie des probabilités. Par exemple, en appliquant l’inégalité de Markov<sup id="fnref:5"><a class="footnote-ref" href="#fn:5">6</a></sup> à un algorithme qui possède une complexité lisse polynomiale, on obtient pour tout <span class="arithmatex">\(\delta\)</span> appartenant à <span class="arithmatex">\([0,1]\)</span> :</p>
<div class="arithmatex">\[\underset{\pi \in \Pi_n}{\text{max}} ~ \mathbb{P}[T(K\pi) \leq \frac{T(n,\sigma^{-1})}{\delta}] \geq 1 - \delta\]</div>
<p>Autrement dit, si <span class="arithmatex">\(A\)</span> a une complexité lisse polynomiale, alors il peut résoudre n’importe quelle instance perturbée en temps polynomial en <span class="arithmatex">\(n\)</span>, <span class="arithmatex">\(\frac 1 \sigma\)</span> et <span class="arithmatex">\(\frac 1 \delta\)</span>, avec une probabilité d’au moins <span class="arithmatex">\(1 - \delta\)</span>.</p>
<p>L’intérêt d’une modélisation mathématique des problèmes prend alors tout son sens. Il peut être difficile dans des problèmes peu structurés ou non analytiques de faire ressortir une distance entre deux instances, et de fait, il devient alors impossible d’utiliser l’analyse lisse. À contrario, les problèmes utilisant des modèles mathématiques font souvent appel à des espaces <em>classiques</em> bénéficiant de métriques naturelles, et l’on peut définir la notion de <a href="https://fr.wikipedia.org/wiki/Problème_bien_posé">problème <em>bien posé</em></a>. On verra un peu plus tard la nécessité d’une modélisation mathématique du problème pour l’étude de la difficulté du problème en amont.</p>
<p>Notons par ailleurs que l’algorithme du Simplexe a une complexité lisse polynomiale, ce qui montre que l’analyse lisse est capable de prédire les comportements des algorithmes de manière plus précise que les autres mesures évoquées.</p>
<h4 id="les-defauts-de-la-complexite-pour-la-comparaison-dalgorithmes">Les défauts de la complexité pour la comparaison d’algorithmes<a class="headerlink" href="#les-defauts-de-la-complexite-pour-la-comparaison-dalgorithmes" title="Permanent link">¶</a></h4>
<p>La complexité algorithmique asymptotique possède un certain nombre de défauts comme nous l’avons vu. Notamment, elle ne permet pas, sauf étude précise, une comparaison fiable entre deux algorithmes au sein d’une même classe de complexité (et parfois même en dehors), car elle masque des constantes qui vont avoir un impact pratique important. Le corollaire de cette remarque est qu’il peut être très difficile si ce n’est impossible de prédire le comportement réel de deux algorithmes sur un jeu d’instances d’un problème particulier.</p>
<h5 id="les-pieges-classiques">Les pièges classiques<a class="headerlink" href="#les-pieges-classiques" title="Permanent link">¶</a></h5>
<p>Prenons l’exemple d’un algorithme <span class="arithmatex">\(A\)</span> et <span class="arithmatex">\(B\)</span>, de complexité dans le pire des cas <span class="arithmatex">\(T_A(n) = 50n^2+50n+5000\)</span> et <span class="arithmatex">\(T_B(n) = n^3\)</span>, avec pour complexité asymptotique dans le pire des cas <span class="arithmatex">\(\mathcal{O}(n^2)\)</span> et <span class="arithmatex">\(\mathcal{O}(n^3)\)</span>.</p>
<p>La figure suivante présente le tracé des deux complexités exactes en fonction de la taille du problème, ainsi que la courbe de la différence d’opérations nécessaires à la résolution du pire des cas. Si l’OGA indique que <span class="arithmatex">\(A\)</span> est meilleur que <span class="arithmatex">\(B\)</span>, la réalité n’est pas tout à fait aussi claire. Si dans la partie précédente nous avons mis en avant le fait qu’il existe un point avant lequel l’algorithme ne se comporte pas comme son OGA, ici l’on montre qu’un algorithme peut être meilleur qu’un autre sur une plage de taille d’instance relativement grande malgré un OGA moins bon. Là encore, le « relativement » se définit par rapport à l’utilisation que l’on va faire de l’algorithme et de la taille des instances que l’on peut rencontrer en pratique.</p>
<p><center><img alt="" src="images/2015-05-15-reflexions-sur-la-complexite-algorithmique-chapitre-2/comparaison.png" /></center></p>
<p>Il est clair que sur l’exemple précédent, jusqu’à des tailles d’instance environ égales à 53, l’algorithme <span class="arithmatex">\(B\)</span> est meilleur que l’algorithme <span class="arithmatex">\(A\)</span> et que si je sais à priori que la majorité des instances que je vais rencontrer vont être de taille inférieure à cette borne, alors j’ai tout intérêt à choisir l’algorithme <span class="arithmatex">\(B\)</span>. Malheureusement, cette information n’est pas contenue dans l’OGA car ce n’est pas son rôle<sup id="fnref:6"><a class="footnote-ref" href="#fn:6">7</a></sup>.</p>
<h5 id="lexemple-de-la-multiplication-matricielle">L’exemple de la multiplication matricielle<a class="headerlink" href="#lexemple-de-la-multiplication-matricielle" title="Permanent link">¶</a></h5>
<p>Un second exemple, non artificiel cette fois, est le problème de la multiplication matricielle. Si l’algorithme de Coppersmith-Winograd a une complexité en <span class="arithmatex">\(\mathcal{O}(n^{2.376})\)</span>, l’algorithme de Strassen possède lui une borne asymptotique donnée par <span class="arithmatex">\(\mathcal{O}(n^{2.807})\)</span>. On pourrait donc s’attendre à ce que Strassen soit plus lent en pratique que <a href="https://fr.wikipedia.org/wiki/Algorithme_de_Coppersmith-Winograd">Coppersmith-Winograd</a>. En réalité, c’est le contraire qui se produit car, pour ce dernier, des constantes multiplicatives et des termes d’ordres inférieurs fortement pondérés interviennent et augmentent la limite inférieure à partir de laquelle on peut considérer que l’algorithme est en régime aymptotique. Et ces termes sont tellement importants qu’en pratique la dimension des matrices telles que Coppersmith-Winograd est plus intéressant que Strassen est telle que personne n’en a d’utilité <em>aujourd’hui</em><sup id="fnref:7"><a class="footnote-ref" href="#fn:7">8</a></sup>.</p>
<p>Pire, même une étude précise pourra être mise en défaut par l’évaluation empirique, et ce d’autant plus facilement que les deux algorithmes comparés offrent une complexité proche. Les facteurs qui propagent un peu plus cette incertitude sont bien évidemment l’abstraction matérielle, l’abstraction des implémentations de briques logicielles d’un niveau de granularité plus faible, comme des opérations sur les structures de données voire les structures de données elles-mêmes dont on ne dispose pas toujours de l’implémentation, et évidemment, les optimisations matérielles et logicielles qui vont réarranger les opérations voire les remplacer par d’autres pour des gains généralement variables d’une implémentation à l’autre et plus encore d’une implémentation d’un algorithme A à l’implémentation d’un algorithme B.</p>
<p>Ces détails font qu’il faut relativiser très grandement la complexité d’un algorithme dans la pratique vis-à-vis de la prédiction du temps qu’elle peut fournir. Plus les systèmes deviennent complexes, de même que les algorithmes ou les problèmes qu’ils résolvent et plus du bruit s’ajoute par la force des choses à l’étude théorique de la complexité algorithmique. Et ce bruit n’arrive pas à être capté et explicité par cette notion comme en témoigne l’exemple typique de l’algorithme du Simplexe et des points intérieurs évoqués en introduction. À sa décharge, ce n’est pas le but de la complexité algorithmique que de pouvoir donner une prédiction précise du temps de calcul.</p>
<h3 id="vers-des-criteres-de-difficulte-en-amont">Vers des critères de difficulté en amont<a class="headerlink" href="#vers-des-criteres-de-difficulte-en-amont" title="Permanent link">¶</a></h3>
<p>Est-il possible de caractériser la difficulté d’un problème sans avoir d’algorithme pour le résoudre ? Peut-on prédire le comportement d’algorithmes types sur un problème donné en amont ? Je propose ici quelques concepts et idées qui permettent de répondre par l’affirmative à ces questions sur des catégories de problèmes particuliers. La démarche est donc en général de transformer l’énoncé d’un problème en formulation mathématique, puis de se ramener à un autre problème type dont a déjà étudié les caractéristiques ou donné des preuves sur le comportement attendu d’un certain nombre de méthodes de résolution.</p>
<h4 id="des-problemes-de-decision-vers-loptimisation">Des problèmes de décision vers l’optimisation<a class="headerlink" href="#des-problemes-de-decision-vers-loptimisation" title="Permanent link">¶</a></h4>
<p>Présentons une version plus générale du plus problème d’optimisation, dont nous avons abordé le cas particulier qu’est le problème d’optimisation linéaire.</p>
<p>Soit <span class="arithmatex">\(\Omega\)</span>, un espace dit des variables de décision, <span class="arithmatex">\(X \subset \Omega\)</span> une partie de l’espace de décision souvent appelé espace admissible, et <span class="arithmatex">\(Y\)</span> un espace totalement ordonné appelé espace objectif, souvent <span class="arithmatex">\(\mathbb{R}\)</span>. Soit <span class="arithmatex">\(f:\Omega \to Y\)</span>, alors le problème de minimisation consiste à minimiser <span class="arithmatex">\(f\)</span> sur <span class="arithmatex">\(X\)</span>, c’est-à-dire trouver <span class="arithmatex">\(f^{*} = \underset{x \in X}{\text{min}}~f(x)\)</span> (sous réserve d’existence de cette valeur) et éventuellement l’ensemble des éléments permettant de réaliser cette valeur optimale, c’est-à-dire <span class="arithmatex">\(S = \{ x \in X ; f(x) = f^{*} \}\)</span>.</p>
<p>L’intérêt de ce problème est qu’il est toujours possible en pratique de ce ramener à cette formulation, même de manière artificielle. S’il est évident que pour des problèmes classiques du type trier un tableau, le problème a été étudié spécifiquement et des algorithmes très spécifiques ont vu le jour, l’étude d’une formulation sous forme d’optimisation peut parfois aider à l’élaboration de nouveaux algorithmes ou à une meilleure compréhension du problème.</p>
<p>Un <a href="https://fr.wikipedia.org/wiki/Problème_de_décision">problème de décision</a> est un problème dont la réponse est soit « oui » soit « non ». Pour chaque problème de cette catégorie, on peut montrer qu’il existe au moins un problème d’optimisation associé. Par exemple, pour le problème de décision « le tableau <span class="arithmatex">\(T\)</span> est-il trié ? » <span class="arithmatex">\((PD)\)</span>, une formulation sous forme d’un problème d’optimisation pourrait être « maximiser la séquence d’éléments triés au sein de <span class="arithmatex">\(T\)</span> » <span class="arithmatex">\((PO)\)</span>. Dès lors, lorsque l’on atteint le maximum de <span class="arithmatex">\((PO)\)</span> cela équivaut à répondre « oui » à <span class="arithmatex">\((PD)\)</span> et si le minimum n’est pas atteint, alors la répondre à <span class="arithmatex">\((PD)\)</span> est « non ». Autrement dit, on résolvant <span class="arithmatex">\((PO)\)</span> on résout exactement <span class="arithmatex">\((PD)\)</span>.</p>
<p>Évidemment, le problème initial peut éventuellement se mettre directement sous forme d’un problème d’optimisation, de même que pour un problème de décision, il peut exister plusieurs formulations d’optimisation dont certaines peuvent être plus aisées à manipuler ou proposer des propriétés intrinsèques plus intéressantes. C’est là qu’intervient le travail de modélisation du mathématicien ou de l’ingénieur en mathématique dont les choix de modélisation proviennent principalement de la connaissance des problèmes récurrents. L’important est plutôt de saisir l’infinité des problèmes qui peuvent se formuler <em>in fine</em> comme un problème d’optimisation et donc l’importance que revêt cette branche des mathématiques pour les applications aussi bien en informatique qu’en physique ou en science sociale.</p>
<h4 id="linearite-versus-non-linearite">Linéarité <em>versus</em> non linéarité<a class="headerlink" href="#linearite-versus-non-linearite" title="Permanent link">¶</a></h4>
<p>En premier lieu, rappelons la définition de la linéarité d’une fonction. Une fonction <span class="arithmatex">\(f\)</span> est linéaire si elle satisfait le principe de superposition, c’est-à-dire si <span class="arithmatex">\(\forall x,y,\alpha \in \mathbb{R},~ f(x+\alpha y) = f(x) + \alpha f(y)\)</span>.</p>
<p>L’ensemble admissible <span class="arithmatex">\(X\)</span> est obtenu par l’application de contraintes sur <span class="arithmatex">\(\Omega\)</span> (et si aucune contrainte ne s’applique, <span class="arithmatex">\(X = \Omega\)</span>). Par exemple, dans le cas de l’optimisation linéaire évoqué plus haut, c’est l’intersection d’<a href="https://fr.wikipedia.org/wiki/Hyperplan">hyperplans</a> (qui, en dimension 2, sont des droites) qui délimite et caractérise <span class="arithmatex">\(X\)</span> au sein de l’ensemble <span class="arithmatex">\(\Omega\)</span>.</p>
<p>Mais l’on peut imaginer contraindre <span class="arithmatex">\(\Omega\)</span> par d’autres types de fonctions. Imaginons que <span class="arithmatex">\(\Omega\)</span> soit un jardin, carré, dont la longueur d’un côté est <span class="arithmatex">\(L\)</span>, et qu’au centre soit attaché à un pilier un chien au bout d’une laisse de longueur <span class="arithmatex">\(l \leq L\)</span>. L’ensemble des positions que le chien peut adopter, c’est-à-dire l’ensemble <span class="arithmatex">\(X\)</span>, est défini par les points de coordonnées <span class="arithmatex">\(x^2 + y^2 \leq l\)</span>, autrement dit le disque de rayon <span class="arithmatex">\(l\)</span> et de centre le pilier. Par ailleurs, la contrainte de la laisse attachée au pilier sur la position du chien est non linéaire. Un exemple de fonction que l’on voudrait maximiser serait <span class="arithmatex">\(f(.,.)\)</span> définie comme la distance entre le chien et le pilier central. Il est évident que le maximum est atteint en tout point du cercle <span class="arithmatex">\(x^2 + y^2 = l\)</span>.</p>
<p>On dira qu’un problème d’optimisation est linéaire lorsque toutes les contraintes qui s’appliquent à <span class="arithmatex">\(\Omega\)</span> pour obtenir <span class="arithmatex">\(X\)</span> sont linéaires et que la fonction <span class="arithmatex">\(f\)</span> à optimiser est linéaire. L’optimisation linéaire est donc un cas très particulier d’optimisation.</p>
<h4 id="quest-ce-quun-probleme-facile">Qu’est-ce qu’un problème facile ?<a class="headerlink" href="#quest-ce-quun-probleme-facile" title="Permanent link">¶</a></h4>
<p>La facilité d’un problème comme caractéristique n’est pas une notion qui trouve un formalisme rigoureux. On se contente de qualifier un problème de facile lorsqu’il répond à certaines caractéristiques mathématiques. La notion de facilité n’est donc pas tout à fait binaire – facile ou difficile – mais plutôt un agrégat de propriétés intéressantes dont on cite quelques-unes des plus importantes :</p>
<ul>
<li>
<p><strong>Existence de solution</strong> : le problème admet-il une solution ? La question peut faire sourire, mais il existe bien des problèmes où l’existence même d’une solution n’est pas facilement démontrable ! Un problème facile aura une preuve d’existence de solution sans condition<sup id="fnref:8"><a class="footnote-ref" href="#fn:8">9</a></sup> et des algorithmes rapides pour tester si la solution existe. C’est le cas de l’optimisation linéaire. Au contraire, des problèmes difficiles n’auront pas ces preuves d’existence, ou alors sous des conditions qui en limitent l’application. Tester l’existence de solutions peut dès lors requérir un temps exponentiel.</p>
</li>
<li>
<p><strong>Problème multi-modal</strong> : le problème possède-t-il plusieurs solutions (appelées modes) ? Il est en effet possible que plusieurs éléments de <span class="arithmatex">\(X\)</span> donnent la valeur optimale pour <span class="arithmatex">\(f\)</span>. C’est le cas de la simple fonction <em>valeur absolue</em> où le maximum sur <span class="arithmatex">\([-5,5]\)</span> par exemple, est obtenu autant par <span class="arithmatex">\(x=5\)</span> que <span class="arithmatex">\(x=-5\)</span>. La résolution de problèmes multi-modaux avec pour critère l’obtention de toutes les solutions réalisant le minimum est en général un problème très difficile que seules les méthodes d’intelligence calculatoire de type <a href="https://fr.wikipedia.org/wiki/Algorithme_évolutionniste">algorithmes évolutionnaires</a> arrivent à résoudre de manière efficace.
Ainsi, l’existence de plusieurs <em>modes</em> est caractéristique de problèmes plus difficiles que les problèmes n’ayant qu’un mode.
Ne parlons alors pas des <a href="https://fr.wikipedia.org/wiki/Optimisation_multiobjectif">problèmes multi-objectifs</a> qui sont <em>de facto</em> multi-modaux puisqu’il n’existe pas en général une solution mais un ensemble de solutions, réalisant un équilibre ou compromis, appelé l’<a href="https://fr.wikipedia.org/wiki/Optimum_de_Pareto">ensemble de Pareto</a>. On comprendra dès lors que les méthodes les plus efficaces pour ces problèmes sont une fois encore des techniques de type <a href="https://fr.wikipedia.org/wiki/Algorithme_génétique">algorithmes génétiques</a>, sauf cas particuliers.</p>
</li>
</ul>
<p>En général les méthodes adoptées pour résoudre ces problèmes sont basées sur des suites itératives <span class="arithmatex">\((x_n)\)</span>. Il s’agit de suites qui vont se rapprocher itération après itération de l’extremum (on parle de suite <em>minimisante</em> ou <em>maximisante</em> et par définition de l’extremum une telle suite existe) et dont on espère beaucoup de propriétés pour résoudre le problème d’optimisation :</p>
<ul>
<li>
<p><strong>Convergence vers un minimum</strong> : la suite minimisante <span class="arithmatex">\(x_n\)</span> converge vers un infimum mais le minimum est-il atteint ?</p>
</li>
<li>
<p><strong>Conditions de convergence</strong> : la suite converge-t-elle sans condition ?</p>
</li>
<li>
<p><strong>Convergence finie ou infinie</strong> : converge-t-on nécessairement en un nombre fini d’étapes ?</p>
</li>
<li>
<p><strong>Vitesse de convergence</strong> : à quelle vitesse va-t-on obtenir la solution, pour une précision donnée ? Il s’agit alors d’essayer de trouver le majorant le plus fin possible de <span class="arithmatex">\(d(x_{n+1}, x^*)\)</span> en fonction de <span class="arithmatex">\(d(x_{n}, x^*)\)</span>. Par exemple, dans le cas de la <a href="https://fr.wikipedia.org/wiki/Méthode_de_Newton">méthode de Newton</a>, sous réserve que l’on puisse appliquer la méthode, on peut montrer que <span class="arithmatex">\(d(x_{n+1}, x^*) \leq Cd(x_n, x^*)^2\)</span>, autrement dit la vitesse est quadratique.</p>
</li>
</ul>
<p>Notons que les réponses à ces questions relèvent autant de la construction de la suite que de des propriétés de l’espace <span class="arithmatex">\(X\)</span>. Par exemple, le minimum est atteint lorsque l’on travaille sur des ensembles fermés bornés en dimension finie car ceux-ci sont alors compacts, tandis que d’autres propriétés sont requises en dimensions infinie, notamment… la convexité de <span class="arithmatex">\(X\)</span>. On renvoie le lecteur désireux d’en savoir plus sur ce passionnant sujet à des cours d’optimisation qui fourmillent sur Internet. On pourra recommander « Analyse numérique et optimisation » de Grégoire Allaire dont une version amoindrie des illustrations est disponible pour l’usage personnel sur le site de l’auteur donné en référence.</p>
<p>La partie algorithmique n’est finalement <em>que</em> la partie qui consiste à construire une telle suite. Le <em>que</em> est à modérer par le fait que généralement, les résultats donnés mathématiquement sont rarement constructifs, c’est-à-dire qu’ils ne permettent pas de construire une telle suite. Il reste donc un travail à faire pour appliquer ces résultats de manière informatique dans bien des cas.</p>
<h4 id="une-question-de-domaine">Une question de domaine<a class="headerlink" href="#une-question-de-domaine" title="Permanent link">¶</a></h4>
<p>Durant des années on a pensé que la difficulté intrinsèque d’un problème était liée majoritairement à la propriété de linéarité, les problèmes linéaires étant les problèmes faciles à résoudre. Cependant, au fur et à mesure que les résultats théoriques apparaissent, notamment dans le domaine de l’<a href="https://fr.wikipedia.org/wiki/Analyse_fonctionnelle_(mathématiques)">analyse fonctionnelle</a> (en particulier, voir <em>Analyse fonctionnelle : théorie et applications</em> de Haïm Brezis), il est devenu de plus en plus clair que ce qui caractérisait la difficulté du problème était la nature de <span class="arithmatex">\(X\)</span> plus que les contraintes s’appliquant à <span class="arithmatex">\(\Omega\)</span> dont <span class="arithmatex">\(X\)</span> résulte.</p>
<p>Clarifions : l’exemple du programme d’optimisation linéaire permet d’obtenir un domaine <span class="arithmatex">\(X\)</span> sous la forme d’un polyèdre, donc convexe par définition. Dans l’exemple du chien et de la laisse, le domaine <span class="arithmatex">\(X\)</span> est un disque, qui reste un domaine convexe. L’un est obtenu à partir uniquement de fonctions linéaires, tandis que le second uniquement à partir de contraintes quadratiques ; et pourtant ces deux problèmes sont simples : ce n’est donc pas la propriété de linéarité qui implique la simplicité mais une autre propriété commune à ces problèmes, à savoir, la convexité.</p>
<p>La fonction <span class="arithmatex">\(f\)</span> étant agnostique aux contraintes s’appliquant sur <span class="arithmatex">\(\Omega\)</span> pour obtenir <span class="arithmatex">\(X\)</span>, ce n’est donc pas en étudiant la linéarité que l’on peut caractériser la difficulté d’un problème mais en étudiant la topologie du domaine <span class="arithmatex">\(X\)</span>, couplée aux propriétés de <span class="arithmatex">\(f\)</span> (il convient cependant de rester prudent puisque l’étude des contraintes est loin d’être inutile). C’est ainsi que les frontières de l’optimisation se sont redessinées au sein de la recherche. Par le passé, l’optimisation linéaire était séparée artificiellement de l’optimisation non-linéaire, mais aujourd’hui, malgré le fait que l’on enseigne toujours en premier lieu et de manière assez séparée l’optimisation linéaire, la frontière serait plutôt l’optimisation convexe et l’optimisation non-convexe<sup id="fnref:9"><a class="footnote-ref" href="#fn:9">10</a></sup>.</p>
<p><center><img alt="" src="images/2015-05-15-reflexions-sur-la-complexite-algorithmique-chapitre-2/convex.png" /></center>
<center><img alt="" src="images/2015-05-15-reflexions-sur-la-complexite-algorithmique-chapitre-2/concave.png" /></center></p>
<blockquote>
<p>”…in fact, the great watershed in optimization isn’t between linearity and nonlinearity, but convexity and nonconvexity.” – R. Tyrrell Rockafellar, in SIAM Review, 1993</p>
</blockquote>
<p>La chose remarquable qu’il faut constater, c’est qu’il est mathématiquement bien plus facile de résoudre les problèmes sur des domaines convexes car ils possèdent maintes propriétés très intéressantes, dont certaines citées plus haut telles que l’existence d’une solution. Si en plus d’être convexe, le domaine est un polyèdre alors on peut montrer que la solution est unique et appartient à l’enveloppe convexe, qui est dans ce cas un <a href="https://fr.wikipedia.org/wiki/Polytope">polytope</a>, pour citer une autre propriété bien connue.</p>
<p>À contrario, les problèmes non-convexes sont fondamentalement difficiles, c’est-à-dire fondamentalement inextricables (de l’anglais <em>untractable</em>), ce qui signifie qu’il n’existe pas d’algorithme qui puisse les résoudre en temps polynomial. Pour ces problèmes, le temps minimal nécessaire à la résolution pour <em>tout</em> algorithme <em>possible</em> (et non connu) est une fonction qui croit plus vite qu’un polynôme. Par abus de langage, un problème est inextricable si le meilleur algorithme connu à ce jour a une complexité en temps exponentiel.</p>
<p>Le <a href="https://fr.wikipedia.org/wiki/Tours_de_Hanoï">problème de la tour de Hanoï</a> a été prouvé comme étant inextricable<sup id="fnref:10"><a class="footnote-ref" href="#fn:10">11</a></sup>, tandis que l’on suppose que le <a href="https://fr.wikipedia.org/wiki/Problème_du_voyageur_de_commerce">problème du voyageur de commerce</a> est inextricable, mais l’on ne dispose pas de preuve pour cela.</p>
<p>Inutile de dire que la plupart des applications pratiques sont des problèmes non-convexes et donc majoritairement inextricables.</p>
<h4 id="convexe-versus-non-convexe">Convexe <em>versus</em> non-convexe<a class="headerlink" href="#convexe-versus-non-convexe" title="Permanent link">¶</a></h4>
<p>Remarquez que l’on parle en général d’optimisation non-convexe et non pas d’optimisation concave car la plupart des problèmes non-convexes ne sont pas concaves et sont tout aussi difficiles à résoudre que ces derniers.</p>
<p>La question qui se pose est alors : pourquoi les problèmes convexes sont faciles ? La réponse tient dans les outils mathématiques dont on dispose et qui permettent l’élaboration de méthodes efficaces dans tous les cas.</p>
<p>Le point de départ pour expliquer tient dans l’unique théorème de Hahn-Banach sur la séparation des convexes.</p>
<div class="admonition theorem">
<p class="admonition-title">Théorème:</p>
<p>Soit <span class="arithmatex">\(E\)</span> un espace normé, <span class="arithmatex">\(A\)</span> et <span class="arithmatex">\(B\)</span> deux convexes de <span class="arithmatex">\(E\)</span> non vides et disjoints. On suppose <span class="arithmatex">\(A\)</span> ouvert. Alors il existe un hyperplan fermé séparant <span class="arithmatex">\(A\)</span> et <span class="arithmatex">\(B\)</span>.</p>
</div>
<p><center><img alt="" src="images/2015-05-15-reflexions-sur-la-complexite-algorithmique-chapitre-2/separation.png" /></center></p>
<p>Une version plus faible, ne supposant pas l’ouverture de A, permet d’obtenir le même résultat de séparation, mais par un hyperplan qui n’est pas nécessairement fermé. En particulier, il est possible de séparer un <a href="https://fr.wikipedia.org/wiki/Singleton_(mathématiques)">singleton</a> de la frontière d’un convexe avec le reste du convexe.</p>
<p><center><img alt="" src="images/2015-05-15-reflexions-sur-la-complexite-algorithmique-chapitre-2/hyperplane_convexe.png" /></center></p>
<p>Dès lors, on peut définir la notion d’<a href="https://fr.wikipedia.org/wiki/Hyperplan_d'appui">hyperplan d’appui</a> et, de fil en aiguille, définir le <a href="https://fr.wikipedia.org/wiki/Sous-différentiel">sous-différentiel</a> en un point de la frontière du convexe comme l’ensemble des coefficients des pentes des hyperplans d’appui en ce point. Il ne s’agit pas d’entrer plus dans les détails, cet article concernant avant tout la complexité algorithmique, mais plutôt de donner quelques pistes de recherche pour le lecteur désireux d’en savoir plus.</p>
<p><center><img alt="" src="images/2015-05-15-reflexions-sur-la-complexite-algorithmique-chapitre-2/hyperplane_convexe_2.png" /></center>
<center><img alt="" src="images/2015-05-15-reflexions-sur-la-complexite-algorithmique-chapitre-2/sousdiff.png" /></center></p>
<p>Au contraire, sur des espaces non-convexes, on peut trouver des points de la frontière pour lesquels le sous-différentiel n’existe pas, tout simplement car il n’existe pas d’hyperplan d’appui, comme illustré sur la figure ci-dessous.</p>
<p><center><img alt="" src="images/2015-05-15-reflexions-sur-la-complexite-algorithmique-chapitre-2/hyperplane_concave.png" /></center></p>
<p>Pour illustrer la difficulté que l’on peut rencontrer sur les problèmes dont le domaine possède des parties concaves, l’optimisation multi-objectif est particulièrement parlante. Dans un tel cas, la particularité est que l’on cherche l’ensemble des points de la frontière du domaine, qui tous, réalisent un équilibre de Pareto. Sur l’animation suivante, il s’agit de toute la frontière visible de l’espace objectif.</p>
<p>Une technique naïve utilisée est d’<a href="https://fr.wikipedia.org/wiki/Méthode_mathématique_d'analyse_multicritère#Agr.C3.A9gation_a_priori_de_crit.C3.A8res_en_un_crit.C3.A8re_unique">agréger</a> les objectifs pour former une nouvelle fonction objective scalaire, ce qui permet d’utiliser les méthodes « classiques » des problèmes mono-objectifs. Toujours naïvement, on utilise souvent une combinaison linéaire des objectifs, c’est-à-dire que si l’on dispose de deux objectifs à notre problème que sont <span class="arithmatex">\(f_1\)</span> et <span class="arithmatex">\(f_2\)</span> alors la fonction que l’on utilisera sera <span class="arithmatex">\(f = \omega_1f_1 + \omega_2 f_2\)</span> avec <span class="arithmatex">\(\omega_1 + \omega_2 = 1\)</span>. Or, l’illustration suivante montre qu’en utilisant une fonction d’agrégation qui est une combinaison linéaire des objectifs, il est <em>impossible</em> d’atteindre la partie concave du front<sup id="fnref:11"><a class="footnote-ref" href="#fn:11">12</a></sup>.</p>
<p><center><img alt="" src="images/2015-05-15-reflexions-sur-la-complexite-algorithmique-chapitre-2/NonConvex.gif" /></center></p>
<p>De manière plus générale, un domaine non-convexe va impliquer possiblement de nombreux optimums locaux dans lesquels les algorithmes habituels vont être piégés, comme c’est le cas de l’algorithme de Newton. Détecter si un optimum n’est pas local est un problème inextricable dans le cas non-convexe. Bref, les propriétés pour qualifier un problème de facile sont toutes mises à défaut beaucoup plus facilement que pour le cas convexe.</p>
<p><center><img alt="" src="images/2015-05-15-reflexions-sur-la-complexite-algorithmique-chapitre-2/newton3.png" /></center></p>
<p>Sur la figure ci-dessus, représentant une fonction multimodale, selon le point de départ de la méthode de Newton, celle-ci va converger vers un des quatre optimums possibles du domaine, mais seul l’un d’entre eux est un optimum global. Il existe une zone autour de chacun de ces points que l’on nomme <a href="https://en.wikipedia.org/wiki/Attractor#Basins_of_attraction"><em>bassin d’attraction</em></a> (lien anglais) et qui « capture » la suite qui s’aventure en son sein.</p>
<h3 id="robustesse-theorique-et-empirique-dun-algorithme">Robustesse théorique et empirique d’un algorithme<a class="headerlink" href="#robustesse-theorique-et-empirique-dun-algorithme" title="Permanent link">¶</a></h3>
<p>Comme nous l’avons vu, la notion pertinente pour caractériser la difficulté d’un problème est la notion de convexité, et non pas celle de complexité des algorithmes pour le résoudre, qui en est généralement une conséquence. Cependant, comme suggéré, on peut tout de même raffiner en étudiant les caractéristiques du domaine de notre problème, en sus de la convexité.</p>
<p>Par exemple, si l’optimisation continue est en générale plus facile que l’optimisation combinatoire c’est parce que l’on possède le concept de <a href="https://fr.wikipedia.org/wiki/Dérivée">dérivée</a> ou plus precisément de <a href="https://fr.wikipedia.org/wiki/Gradient">gradient</a>. Mais même en optimisation continue, si le domaine de notre instance possède trop d’irrégularités ou un certain nombre de pathologies, les méthodes habituellement efficaces peuvent connaître des difficultés allant d’un temps empirique bien plus grand qu’en moyenne jusqu’à l’impossibilité d’être appliquées (nécessite l’existence d’une dérivée d’ordre supérieur par exemple). Des exemples de domaines pathologiques peuvent être visualisés <a href="https://fr.wikipedia.org/wiki/Fonction_de_Rosenbrock">ici</a>, <a href="https://fr.wikipedia.org/wiki/Fonction_de_Himmelblau">ici</a> ou encore <a href="https://fr.wikipedia.org/wiki/Fonction_de_Rastrigin">ici</a>.</p>
<p>On aimerait donc caractériser la robustesse d’un algorithme par rapport au problème qu’il résout, en fonction de sa capacité à ne pas varier de manière trop significative en fonction des instances du problème. On entend principalement donner des résultats empiriques temporels qui varient peu quelles que soient les instances de tailles similaires que l’algorithme résout, autrement dit, une variance faible sur le temps de résolution.</p>
<p>Les pistes de recherche actuelles semblent indiquer que cette robustesse est obtenue par des propriétés d’<a href="https://fr.wikipedia.org/wiki/Invariant">invariance</a> possédées par l’algorithme. Dans le cas de l’optimisation, on peut citer quelques exemples :</p>
<ul>
<li><strong>Invariance par une transformation de la fonction objectif</strong> : plus la transformation préservant l’invariance a des propriétés générales et plus l’algorithme sera robuste. Par exemple, une translation est une transformation plus stricte que la transformation par une fonction strictement monotone et donc un algorithme qui n’a pour invariant que la translation est moins robuste qu’un algorithme invariant pour la transformation de la fonction objectif par une fonction strictement monotone.</li>
<li><strong>Invariance par transformation de l’espace de recherche</strong> : il s’agit typiquement de rotations, réflexions, translations ou une composition de celles-ci.</li>
</ul>
<p>On comprendra donc que ces propriétés d’invariance offertes par les algorithmes sont hautement désirables puisqu’elles permettent d’obtenir une généralisation des résultats empiriques à toutes les instances de la même classe par rapport à la relation d’invariance. Pour donner un exemple, si un algorithme supporte une propriété d’invariance par translation de la fonction objectif, alors cela veut dire que cet algorithme aura des performances équivalentes sur la fonction <span class="arithmatex">\(f\)</span> et les fonctions <span class="arithmatex">\(f_a\)</span> définies par <span class="arithmatex">\(f_a(x) = f(x) + a\)</span> quel que soit <span class="arithmatex">\(a \in \mathbb{R}\)</span>.</p>
<p>Notez que cette notion d’invariance est une indication théorique permettant de caractériser les performances empiriques là où la complexité échoue généralement au passage à l’empirique comme le montre le contre-exemple de l’algorithme du Simplexe.</p>
<p>En réalité il y a bien une notion de complexité qui se rapproche de la robustesse par invariance et c’est l’analyse lisse d’algorithmes. En effet, on peut considérer que l’opérateur de perturbation est une transformation particulière, aléatoire notamment.</p>
<p>Il s’agit non pas d’une étude de transformation générale mais de l’étude d’une classe de transformation particulière que l’on peut qualifier de perturbation locale, souvent gaussienne. La différence est que dans l’analyse lisse on s’intéresse au pire des cas obtenu par perturbation tandis que dans l’étude d’invariance on étudie des classes d’équivalence pour la transformation considérée, non aléatoire, sans tenir compte de la complexité.</p>
<p>Une deuxième piste pour caractériser la robustesse d’un algorithme est sa capacité à être paramétré rapidemment (et donc plus ou moins, de manière corrélée, à proposer peu de paramètres et des paramètres à domaine restreint).</p>
<h4 id="no-free-lunch">No Free Lunch<a class="headerlink" href="#no-free-lunch" title="Permanent link">¶</a></h4>
<p>Si l’on se place à une échelle un peu plus large, de nombreuses méthodes ont été conçues pour appréhender de nombreux problèmes différents. On parle alors de « <a href="https://fr.wikipedia.org/wiki/Métaheuristique">métaheuristiques</a> ». « Méta » pour la variété des problèmes que ces méthodes peuvent traiter, et « heuristiques » car elles n’offrent, en général, pas de garantie de performance et se contentent d’une solution approchée. Malgré cela, et la complexité exponentielle d’un grand nombre de ces méthodes, elles permettent d’obtenir de très bons résultats pour les applications pratiques, sur des problèmes en général intraitables par les méthodes classiques. Ce sont par exemple les méthodes de prédilection pour l’optimisation non-lisse, c’est-à-dire les problèmes d’optimisation sur des domaines très irréguliers mettant en défaut des méthodes plus classiques.</p>
<p>On est alors en droit de se demander s’il existe une méthode qui permet d’obtenir de meilleurs résultats pour tous les problèmes d’un ensemble de problèmes donnés, auquel cas les autres méthodes deviendraient obsolètes. La réponse est non et est apportée par le célèbre théorème du <a href="https://en.wikipedia.org/wiki/No_free_lunch_in_search_and_optimization"><em>No Free Lunch</em></a> (lien anglais) qui affirme qu’à moins d’exploiter l’information disponible au niveau d’un problème particulier, il n’existe pas de métaheuristique qui soit intrinsèquement meilleure qu’une autre.</p>
<p><center><img alt="" src="images/2015-05-15-reflexions-sur-la-complexite-algorithmique-chapitre-2/nofreelunch.png" /></center></p>
<p>Le corollaire est que l’exploitation de l’information inscrite dans le problème ou dans ses instances est nécessaire pour « optimiser » un algorithme sur un problème ou un jeu d’instances donné. Par ailleurs, les métaheuristiques étant des méthodes approchées, elles sont souvent réglées empiriquement par un nombre important de paramètres qui constituent un obstacle pour l’utilisateur final.</p>
<p>Dès lors, ce sont de bons candidats pour un domaine qui se développe de plus en plus, à savoir la méta-optimisation.</p>
<h4 id="compromis-conception-exploitation">Compromis conception-exploitation<a class="headerlink" href="#compromis-conception-exploitation" title="Permanent link">¶</a></h4>
<p>Ce qui n’est pris en compte par aucune notion de complexité algorithmique c’est le temps nécessaire au réglage de l’algorithme. Un algorithme évolutionnaire possède souvent un nombre très important de paramètres. Parmi les plus généraux et que l’on retrouve sur presque toutes les méthodes : la taille de la population, les probabilités de mutation et de croisement, etc.</p>
<p>Dès lors, pour en tirer le meilleur sur une situation pratique (la phase d’exploitation) il faut calibrer l’algorithme (la phase de conception). Et l’on se retrouve de fait avec un compromis à faire : le temps accordé à la recherche des meilleurs paramètres <em>versus</em> la qualité des paramètres trouvés. Si l’on reprend l’exemple des paramètres de taille de population et des deux probabilités, en considérant des tailles de population qui varient de 10 à 100 individus, et une discrétisation par pas de 0.1 pour les probabilités, on obtient déjà un espace de configuration de taille <span class="arithmatex">\(90 \times 11 \times 11 = 10890\)</span>, que l’on devrait multiplier par le nombre d’instances possibles du problème, possiblement discrétisées dans le cas continue. Il est donc impossible, même lorsqu’il y a peu de paramètres, d’explorer explicitement toutes les configurations.</p>
<p>La <a href="https://en.wikipedia.org/wiki/Meta-optimization">méta-optimisation</a> (lien anglais) consiste donc à élaborer des méthodes pour rapidement trouver des paramètres de bonne qualité. On parle également plus généralement de <em>parameter tuning</em> en anglais. Comme il ne s’agit pas de l’objet de cet article, on n’entrera pas plus dans les détails sur les diverses techniques d’optimisation de paramètres, mais l’on se contentera de faire la remarque suivante : un algorithme est d’autant plus robuste qu’il est d’une part rapide à optimiser et, d’autre part, que ses paramètres sont peu sensibles, c’est-à-dire vont jouer un rôle limité dans les résultats obtenus.</p>
<p>La facilité à être optimisé provient surtout des invariances évoquées plus haut puisque si un algorithme donne de bons résultats sur une instance avec une configuration donnée, toutes les instances résultantes par invariance donneront les mêmes résultats pour cette même configuration. Dès lors, les invariances font diminuer l’espace de recherche des algorithmes de méta-optimisation. La facilité provient également d’un faible nombre de paramètres à optimiser. Une technique de réduction du nombre de paramètres consiste en des méthodes qui optimisent le paramètre en même temps que l’algorithme recherche la solution au problème : on parle de méthode <em>en ligne</em> (<em>online</em> en anglais). Dès lors, l’utilisateur final n’a plus à se soucier de ce paramètre qui va s’auto-calibrer sans l’aide de personne. Ou presque… puisque la plupart des méthodes en ligne font apparaître de nouveaux paramètres, souvent plus nombreux. L’intérêt est alors que ces méta-paramètres sont moins sensibles que leurs homologues de premier ordre, c’est-à-dire que leur modification entraine de plus petites variations en moyenne dans les résultats que l’on peut espérer obtenir.</p>
<p>Signalons au lecteur l’existence de logiciels dédiés à l’optimisation de paramètres comme <a href="http://www.cs.ubc.ca/labs/beta/Projects/ParamILS/">ParamILS</a>.</p>
<h3 id="conclusion">Conclusion<a class="headerlink" href="#conclusion" title="Permanent link">¶</a></h3>
<p>Que peut-on tirer comme leçon de cet article ? Tout d’abord, son but premier était de montrer que la notion de complexité la plus courante, celle dans le pire des cas, est très facilement mise à défaut et que c’est normal ! Elle ne cherche pas à permettre de comparer deux algorithmes mais à donner une indication sur la capacité de l’algorithme à évoluer avec la taille des problèmes. On ne peut pas en tirer beaucoup plus d’informations que la classe de complexité d’un algorithme, et ainsi les conséquences sur la <em>dynamique</em> des performances en fonction de la taille du problème. J’insiste sur le mot dynamique comme pour dire qu’il s’agit d’une caractéristique qualitative plus que quantitative : la complexité dans le pire des cas ne permet pas de faire des prévisions efficaces mais simplement de prédire la <a href="https://fr.wikipedia.org/wiki/Scalability">scalabilité</a>.</p>
<p>Il existe cependant d’autres notions de complexité, développées pour combler les lacunes de leur prédécesseur sur sa capacité à faire le lien entre théorie et application. Si chacune possède également des défauts, elles sont un pas en avant vers une meilleure caractérisation en amont de la capacité des algorithmes à bien se comporter en pratique.</p>
<p>Cependant, une caractérisation encore plus en amont, au niveau des problèmes, est souvent souhaitable car cela permet d’anticiper les capacités des algorithmes qui vont résoudre ces problèmes. La caractéristique principale pour qualifier un problème de facile est la convexité de celui-ci. À contrario, les problèmes non-convexes seront généralement très difficiles et les algorithmes non efficaces, voire dans le pire des cas, aucun algorithme <em>efficace</em> ne peut exister.</p>
<p>Enfin, avec la multiplication des problèmes non-convexes, des techniques satisfaisantes en pratique ont vu le jour, mais celles-ci ont un besoin de calibration qui n’est pas retranscrit par la complexité algorithmique. En réalité, les besoins dans beaucoup de domaines pratiques ne sont plus les mêmes qu’il y a 50 ans, et la complexification des problèmes, du matériel sur lequel va être exécuté un algorithme, et des algorithmes eux-mêmes, ont fait émerger de nouveaux besoins et critères de qualité et de robustesse.</p>
<p>La complexité algorithmique n’est plus alors qu’une métrique parmi d’autres et ne devrait plus, dans bien des cas, être considérée comme un facteur décisif pour définir la qualité d’un algorithme ou d’une méthode. Les progrès en mathématiques ont également permis de déplacer l’étude de l’efficacité du couple problème-méthode de la méthode vers le problème. Pas entièrement, mais suffisamment pour que cela soit d’un intérêt pour le plus grand nombre de connaitre à minima les avancées de ces travaux et la classification des problèmes faciles selon ces nouveaux critères.</p>
<h3 id="references">Références<a class="headerlink" href="#references" title="Permanent link">¶</a></h3>
<ul>
<li><a href="http://cs-www.cs.yale.edu/homes/spielman/Research/cacmSmooth.pdf">Smoothed Analysis: An Attempt to Explain the Behavior of Algorithms in Practice</a></li>
<li><a href="http://www.cs.yale.edu/homes/spielman/SmoothedAnalysis/index.html">Smooth Analysis Homepage</a></li>
<li>
<p><a href="http://arxiv.org/pdf/cs/0111050.pdf">Smooth Analysis of Algorithms: Why the Simplex Algorithm Usually Takes Polynomial Time</a></p>
</li>
<li>
<p><a href="http://www.cmap.polytechnique.fr/~allaire/livre2.html">Analyse numérique et optimisation</a></p>
</li>
<li><a href="https://hal.inria.fr/inria-00583669/document">Impacts of Invariance in Search: When CMA-ES and PSO Face Ill-Conditioned and Non-Separable Problems</a></li>
<li><a href="http://ti.arc.nasa.gov/m/profile/dhw/papers/78.pdf">No Free Lunch Theorems for Optimization</a></li>
<li><a href="https://hal.inria.fr/inria-00140549/file/param-final.pdf">Parameter Control in Evolutionary Algorithms</a></li>
<li><a href="http://www.cs.ubc.ca/~hutter/papers/aaai07_param_ils.pdf">Automatic Algorithm Configuration based on Local Search</a></li>
</ul>
<h3 id="credits-des-illustrations">Crédits des illustrations<a class="headerlink" href="#credits-des-illustrations" title="Permanent link">¶</a></h3>
<ul>
<li>L’ensemble des images jusqu’à « Une question de domaine » et l’illustration de la fonction de Hölder ont été créés pour les besoins de cet article et placés dans le domaine public.</li>
<li>Les illustrations de la partie « Une question de domaine » et celles de la section « Convexe <em>versus</em> non-convexe » représentant la séparation par hyperplan sont réalisées par Oleg Alexandrov et placées dans le domaine public.</li>
<li>L’illustration du sous-différentiel d’une fonction convexe est réalisée par Maksim et est placée dans le domaine public.</li>
<li>L’animation de la section « Convexe <em>versus</em> non-convexe » a été réalisée par Guillaume Jacquenot et est placée sous licence <a href="https://creativecommons.org/licenses/by-sa/3.0/">CC BY-SA 3.0</a>. Aucune modification n’a été effectuée sur l’oeuvre.</li>
<li>L’illustration du No Free Lunch Theorem a été réalisée par Johann Dréo et est placée sous licence <a href="https://creativecommons.org/licenses/by-sa/3.0/">CC BY-SA 3.0</a>. Aucune modification n’a été effectuée sur l’oeuvre.</li>
</ul>
<div class="footnote">
<hr />
<ol>
<li id="fn:memoire">
<p>c’est à dire la quantité de mémoire nécessaire pour résoudre le problème avec l’algorithme <a class="footnote-backref" href="#fnref:memoire" title="Jump back to footnote 1 in the text">↩</a></p>
</li>
<li id="fn:1">
<p>Pour une définition plus formelle, on renvoie à la première partie des <a href="http://endomorphis.me/blog/2013/03/14/reflexions-sur-la-complexite-algorithmique/">Réflexions sur la complexité algorithmique</a>. <a class="footnote-backref" href="#fnref:1" title="Jump back to footnote 2 in the text">↩</a></p>
</li>
<li id="fn:2">
<p>Parfois on utilise non pas <span class="arithmatex">\(T_{\text{max}}\)</span> mais <span class="arithmatex">\(\bar T\)</span> et l’on parlera alors de coût moyen amorti. Cela doit vous faire sentir qu’il ne s’agit pas tout à fait de la même chose. <a class="footnote-backref" href="#fnref:2" title="Jump back to footnote 3 in the text">↩</a></p>
</li>
<li id="fn:3">
<p><a href="http://svn.python.org/projects/python/trunk/Objects/listobject.c">Code source de listobject</a> <a class="footnote-backref" href="#fnref:3" title="Jump back to footnote 4 in the text">↩</a></p>
</li>
<li id="fn:4">
<p>En réalité on a besoin que de la convergence en loi qui est bien plus faible. <a class="footnote-backref" href="#fnref:4" title="Jump back to footnote 5 in the text">↩</a></p>
</li>
<li id="fn:5">
<p>Soit <span class="arithmatex">\(X\)</span> une variable aléatoire réelle, presque surement positive, alors <span class="arithmatex">\(\forall a > 0, ~ P(X \geq a) \leq \frac{E(X)}{a}\)</span>. <a class="footnote-backref" href="#fnref:5" title="Jump back to footnote 6 in the text">↩</a></p>
</li>
<li id="fn:6">
<p>Comme expliqué <a href="https://rjlipton.wordpress.com/2015/03/24/is-it-new/">ici</a>, Donald Knuth était favorable à l’utilisation d’un équivalent asymptotique et non un ordre de grandeur asymptotique pour exhiber l’influence de la constante multiplicative. <a class="footnote-backref" href="#fnref:6" title="Jump back to footnote 7 in the text">↩</a></p>
</li>
<li id="fn:7">
<p>Il est clair qu’étant donnée la taille croissante des instances de problèmes à résoudre, des algorithmes non-efficaces en pratique aujourd’hui mais asymptotiquement intéressants (typiquement polynomiaux) pourront trouver leur utilité dans un futur plus ou moins proche. <a class="footnote-backref" href="#fnref:7" title="Jump back to footnote 8 in the text">↩</a></p>
</li>
<li id="fn:8">
<p>Attention, cela ne veut pas dire que la solution existe toujours, mais que les critères sont indépendants de l’instance du problème. <a class="footnote-backref" href="#fnref:8" title="Jump back to footnote 9 in the text">↩</a></p>
</li>
<li id="fn:9">
<p>Il ne faut cependant pas trop prêter attention à ces séparations. Les seules séparations valables sont celles qui séparent deux catégories de problèmes par rapport aux outils disponibles pour les résoudre et ainsi, en fonction du temps ces frontières changent, ou plus précisemment reculent. Le travail de la recherche étant d’étendre les outils déjà existants à des problèmes plus difficiles, d’en proposer de nouveaux, ce qui permet d’unifier des domaines. <a class="footnote-backref" href="#fnref:9" title="Jump back to footnote 10 in the text">↩</a></p>
</li>
<li id="fn:10">
<p>Ce problème n’appartient pas à <span class="arithmatex">\(NP\)</span> et donc ne peut pas être <span class="arithmatex">\(NP\)</span>-Complet. De fait, savoir qu’il n’existe pas d’algorithme polynomial pour ce problème n’a aucune incidence sur le problème ouvert <span class="arithmatex">\(P=NP\)</span>. <a class="footnote-backref" href="#fnref:10" title="Jump back to footnote 11 in the text">↩</a></p>
</li>
<li id="fn:11">
<p>Il existe cependant un tas de raffinements qui permettent d’atteindre ces zones, avec plus ou moins de difficultés mais nous n’entrons pas dans les détails ici et renvoyons à un cours sur l’optimisation multi-objective. <a class="footnote-backref" href="#fnref:11" title="Jump back to footnote 12 in the text">↩</a></p>
</li>
</ol>
</div>
</div>
</div><!--//main-body-->
</div>
<footer class="footer">
</footer><!--//footer-->
<script type="text/javascript" src="js/jquery-1.11.3.min.js"></script>
<script type="text/javascript" src="js/bootstrap.min.js"></script>
<script type="text/javascript" src="js/main.js"></script>
</body>
</html>