-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy path2013-03-14-reflexions-sur-la-complexite-algorithmique.html
270 lines (225 loc) · 28.8 KB
/
2013-03-14-reflexions-sur-la-complexite-algorithmique.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
<!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</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</h1>
<div class="item">
<div class="meta">
<div class="upper-row">
<h3 class="job-title"><cite>2013-07-26</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="#introduction">Introduction</a></li>
<li><a href="#rappels-sur-la-complexite-temporelle">Rappels sur la complexité temporelle</a><ul>
<li><a href="#complexite-en-temps">Complexité en temps</a></li>
<li><a href="#reduction-polynomiale-et-classes-dequivalence">Réduction polynomiale et classes d’équivalence</a></li>
<li><a href="#en-resume">En résumé</a></li>
</ul>
</li>
<li><a href="#erreur-1-evaluation-de-la-complexite-dun-algorithme">Erreur 1 : Évaluation de la complexité d’un algorithme</a><ul>
<li><a href="#le-propos">Le propos</a></li>
<li><a href="#exemple-nombre-compose">Exemple : Nombre composé</a></li>
<li><a href="#en-resume_1">En résumé</a></li>
</ul>
</li>
<li><a href="#erreur-2-erreur-sur-la-classe-dun-probleme">Erreur 2 : Erreur sur la classe d’un problème</a><ul>
<li><a href="#le-propos_1">Le propos</a></li>
<li><a href="#exemple-sat">Exemple : SAT</a></li>
<li><a href="#exemple-arbre-couvrant-de-poids-minimal">Exemple : Arbre couvrant de poids minimal</a></li>
</ul>
</li>
<li><a href="#conclusion">Conclusion</a></li>
</ul>
</div>
<h3 id="introduction">Introduction<a class="headerlink" href="#introduction" title="Permanent link">¶</a></h3>
<p>L’article qui suit présuppose quelques notions basiques d’algorithmique et de calcul de complexité (temporelle). Il vise à aborder deux grandes erreurs commises par les novices dans ces domaines et à en constater les effets.</p>
<p>Une première partie sera dédiée à une erreur classique d’évaluation de la classe de complexité d’un problème à partir de la complexité calculée d’un algorithme, ce qui aura des conséquences désastreuses en termes de performances. La seconde partie présentera une erreur liée à l’erreur d’évaluation directe de la classe de complexité d’un problème, qui va cette fois avoir des conséquences sur la manière d’aborder un problème pour tenter de le résoudre.</p>
<p>Les notions utiles à la compréhension de cet article seront expliquées dans une première partie et la totalité des démonstrations sera omise (mais on peut évidemment grassement payer l’auteur pour qu’il les fasse sur le forum).</p>
<h3 id="rappels-sur-la-complexite-temporelle">Rappels sur la complexité temporelle<a class="headerlink" href="#rappels-sur-la-complexite-temporelle" title="Permanent link">¶</a></h3>
<h4 id="complexite-en-temps">Complexité en temps<a class="headerlink" href="#complexite-en-temps" title="Permanent link">¶</a></h4>
<p>Il est coutume que de manière informelle, on enseigne aux novices de l’algorithmique que la complexité d’un algorithme correspond au nombre d’étapes (élémentaires) de l’algorithme, qui est fonction de la taille des données du problème. Cette définition a l’avantage d’être très facile à appliquer, facilement compréhensible et de donner une borne assez fidèle dans la plupart des applications.</p>
<p>Cependant, cette définition est problématique, comme nous allons le voir, lorsque l’on donne la définition formelle des classes d’équivalence de complexité algorithmique. On présente souvent les classes de complexité principales : <span class="arithmatex">\(P\)</span> et <span class="arithmatex">\(NP\)</span>, respectivement pour <em>Polynomial</em> et <em>Non-<strong>Déterministe</strong> Polynomial</em>. Le terme « non déterministe » est important puisqu’à l’heure actuelle, nous ne savons pas si <span class="arithmatex">\(P = NP\)</span> (et pour l’anecdote, il s’agit d’un des problèmes du prix du millénaire, récompensé par la coquette somme d’un million de dollars par le <em>Clay Mathematical Institute</em>).</p>
<p>De manière formelle, un algorithme <span class="arithmatex">\(A\)</span> de <strong>machine de Turing déterministe</strong> est polynomial s’il existe un polynôme <span class="arithmatex">\(p_A\)</span> tel que <span class="arithmatex">\(\forall x \in \Sigma^*, |x|=n, t_A(x) \leq p_A(n)\)</span> où <span class="arithmatex">\(x\)</span> est un mot de l’alphabet <span class="arithmatex">\(\Sigma\)</span> (ensemble des symboles différents pour coder l’entrée), <span class="arithmatex">\(t_A(x)\)</span> le nombre de pas jusqu’à l’arrêt de <span class="arithmatex">\(A\)</span> et <span class="arithmatex">\(n\)</span>, la longueur de l’entrée, qui est arbitrairement fixée.</p>
<p>On appelle complexité en temps de <span class="arithmatex">\(A\)</span>, le maximum des <span class="arithmatex">\(t_A(x)\)</span> pour un <span class="arithmatex">\(n=|x|\)</span> fixé. On comprend donc aisément qu’un algorithme est polynomial si sa complexité temporelle est bornée par un polynôme. Par extension, on dira qu’un problème <span class="arithmatex">\(\Pi\)</span> est polynomial s’il existe un algorithme <span class="arithmatex">\(A\)</span> polynomial qui résout <span class="arithmatex">\(\Pi\)</span>.</p>
<p>Cette définition est excessivement formelle et oblige à recourir aux machines de Turing. Cependant, il existe toujours des fonctions permettant de passer d’un formalisme en machine de Turing à un formalisme utilisant nos ordinateurs modernes, le tout, évidemment, en temps polynomial. Ainsi, par la suite, on ne reviendra jamais aux machines de Turing pour calculer des complexités, et heureusement !</p>
<p>Est-ce qu’un algorithme qui n’est pas dans <span class="arithmatex">\(P\)</span> est dans <span class="arithmatex">\(NP\)</span> ? C’est une question que l’on retrouve assez souvent et la réponse est évidemment non. Il suffit de se référer à la définition formelle d’un algorithme non-déterministe polynomial. Pour cela, nous devons introduire la notion de <strong>certificat</strong> et de <strong>vérification</strong>.</p>
<p>Un certificat est une aide permettant, pour une entrée donnée, de déterminer si <span class="arithmatex">\(x\)</span> est reconnu par un algorithme <span class="arithmatex">\(A\)</span>. De manière conceptuelle, il peut être vu comme une intervention divine ou une indication, comme en donnerait un professeur lors d’un examen, pour guider l’étudiant à démontrer un résultat difficile. La vérification est un algorithme permettant de savoir si l’entrée est reconnue sachant le certificat.</p>
<p>On dira qu’un algorithme <span class="arithmatex">\(A\)</span> est non-déterministe polynomial s’il existe un polynôme <span class="arithmatex">\(p_A\)</span> tel que <span class="arithmatex">\(\forall x \in \Sigma^n\)</span>, <span class="arithmatex">\(t_A(x) \leq p_A(n)\)</span> où <span class="arithmatex">\(t_A(x)\)</span> est le temps de reconnaissance de <span class="arithmatex">\(x\)</span> (c’est-à-dire le temps minimal de reconnaissance de <span class="arithmatex">\(x\)</span> parmi l’ensemble des temps de reconnaissance de <span class="arithmatex">\(x\)</span>, qui peuvent varier selon le certificat).</p>
<p>De même, un problème <span class="arithmatex">\(\Pi\)</span> est non-déterministe polynomial s’il existe un algorithme <span class="arithmatex">\(A\)</span> non-déterministe polynomial qui résout <span class="arithmatex">\(\Pi\)</span>.</p>
<h4 id="reduction-polynomiale-et-classes-dequivalence">Réduction polynomiale et classes d’équivalence<a class="headerlink" href="#reduction-polynomiale-et-classes-dequivalence" title="Permanent link">¶</a></h4>
<p>Une dernière partie théorique permettant d’introduire la notion de <strong>réduction polynomiale</strong> et ainsi la notion de <strong>classes de complexité</strong>, de manière plus formelle.</p>
<p>Soit <span class="arithmatex">\(\Pi_1\)</span> et <span class="arithmatex">\(\Pi_2\)</span>, deux problèmes de décision. On dit que <span class="arithmatex">\(\Pi_1\)</span> se réduit polynomialement en <span class="arithmatex">\(\Pi_2\)</span> noté <span class="arithmatex">\(\Pi_1 \propto \Pi_2\)</span> s’il existe une fonction <span class="arithmatex">\(f:D_{\Pi_1} \rightarrow D_{\Pi_2}\)</span> telle que : </p>
<ul>
<li><span class="arithmatex">\(f\)</span> est calculable polynomialement</li>
<li><span class="arithmatex">\(I\in Y_{\Pi_1} \Leftrightarrow f(I)\in Y_{\Pi_2}\)</span></li>
</ul>
<p>Où <span class="arithmatex">\(D_{\Pi_1}\)</span> et <span class="arithmatex">\(D_{\Pi_2}\)</span> sont, respectivement, les instances possibles (entrées possibles) pour le problème <span class="arithmatex">\(\Pi_1\)</span> et <span class="arithmatex">\(\Pi_2\)</span> et <span class="arithmatex">\(Y_{\Pi_1}\)</span>, l’ensemble des instances de <span class="arithmatex">\(\Pi_1\)</span> renvoyant <em>VRAI</em> au problème de décision.</p>
<p>Par exemple, on peut considérer le problème de savoir si un entier <span class="arithmatex">\(n\)</span> donné est pair. L’ensemble des données possibles en entrée est l’ensemble des entiers. L’ensemble renvoyant <em>VRAI</em> est, évidemment, l’ensemble des nombres pairs.</p>
<p>Cette relation possède quelques propriétés intéressantes, mais ce n’est pas le propos de cet article. Par contre, il s’agit d’une relation d’ordre partiel sur l’ensemble des problèmes de décision, à laquelle on peut ajouter une notion de <em>symétrie</em> permettant de construire une relation d’équivalence, et par là même, définir des classes d’équivalence au sens de cette relation.</p>
<p>La classe <span class="arithmatex">\(P\)</span> est la plus petite classe au sens de cette relation et la classe <span class="arithmatex">\(NP\)</span>-complet est la plus grande.</p>
<p>Enfin, pour éclaircir le vocabulaire, on parle de problème <span class="arithmatex">\(NP\)</span>-difficile dans le cadre des problèmes de décision. Cela signifie qu’un problème est aussi difficile que les problèmes de la classe <span class="arithmatex">\(NP\)</span>-complet.</p>
<h4 id="en-resume">En résumé<a class="headerlink" href="#en-resume" title="Permanent link">¶</a></h4>
<p>Que faut-il retenir de cette introduction très formelle ?</p>
<ul>
<li>Un problème <span class="arithmatex">\(\Pi\)</span> est polynomial s’il existe un algorithme <span class="arithmatex">\(A\)</span> polynomial qui résout <span class="arithmatex">\(\Pi\)</span>.</li>
<li>un problème <span class="arithmatex">\(\Pi\)</span> est non-déterministe polynomial s’il existe un algorithme <span class="arithmatex">\(A\)</span> non-déterministe polynomial qui résout <span class="arithmatex">\(\Pi\)</span>.</li>
<li><span class="arithmatex">\(P \subseteq NP\)</span>.</li>
<li>Tous les problèmes d’une classe donnée sont équivalents (au sens de la réduction polynomiale).</li>
</ul>
<h3 id="erreur-1-evaluation-de-la-complexite-dun-algorithme">Erreur 1 : Évaluation de la complexité d’un algorithme<a class="headerlink" href="#erreur-1-evaluation-de-la-complexite-dun-algorithme" title="Permanent link">¶</a></h3>
<h4 id="le-propos">Le propos<a class="headerlink" href="#le-propos" title="Permanent link">¶</a></h4>
<p>Rappelez-vous de la définition formelle de la complexité temporelle. Que ce soit pour l’ensemble <span class="arithmatex">\(P\)</span> ou <span class="arithmatex">\(NP\)</span> nous avons l’inégalité suivante :
<span class="arithmatex">\(t_A(x) \leq p_A(n)\)</span> où <span class="arithmatex">\(x\)</span> est un mot de l’alphabet <span class="arithmatex">\(\Sigma\)</span> (ensemble des symboles en pour coder l’entrée), <span class="arithmatex">\(t_A(x)\)</span> le nombre de pas jusqu’à l’arrêt de <span class="arithmatex">\(A\)</span>, <span class="arithmatex">\(n\)</span>, longueur de l’entrée est arbitrairement fixé et <span class="arithmatex">\(p_A(n)\)</span>, un polynôme fonction de <span class="arithmatex">\(n\)</span>.</p>
<p>C’est bien ici qu’est le propos de cette première erreur : le polynôme qui borne le temps d’exécution n’est pas fonction de l’entrée mais de la taille de codage ou d’écriture du problème. Quelle différence ? Voyons sur un exemple très simple.</p>
<h4 id="exemple-nombre-compose">Exemple : Nombre composé<a class="headerlink" href="#exemple-nombre-compose" title="Permanent link">¶</a></h4>
<p>Un nombre est composé s’il n’est pas premier.
Donnons nous le problème de décision suivant : <em>Soit un entier n. Est-il composé ?</em></p>
<p>Un algorithme naïf serait le suivant : </p>
<div class="highlight"><table class="highlighttable"><tr><td class="linenos"><div class="linenodiv"><pre><span></span><span class="normal">1</span>
<span class="normal">2</span>
<span class="normal">3</span>
<span class="normal">4</span>
<span class="normal">5</span></pre></div></td><td class="code"><div><pre><span></span><code>Pour i = 2 à racine(n) faire
Si n % i = 0 alors
Retourner Vrai
Fin pour
Retourne Faux
</code></pre></div></td></tr></table></div>
<p>La question à se poser est : <em>quelle est la complexité de cet algorithme ?</em></p>
<p>Au premier coup d’œil, nous parcourons une boucle dans laquelle nous effectuons une opération plus ou moins élémentaire. Bref, il semblerait que cet algorithme soit en <span class="arithmatex">\(O(n)\)</span> voire <span class="arithmatex">\(O(n^{\frac{1}{2}})\)</span> si nous voulions être plus précis. Dans les deux cas, un joli polynôme. Notre problème est donc un problème polynomial.</p>
<p>Ce calcul est évidemment bon mais la conclusion est fausse, pour la raison évoquée : elle ne tient pas compte de la taille d’écriture du problème.</p>
<p>Quelle est donc la taille d’écriture de ce problème ?</p>
<p>Nous avons un entier <span class="arithmatex">\(n\)</span> quelconque. Quelle que soit la base <span class="arithmatex">\(b\)</span> dans laquelle il est exprimé, sa longueur d’écriture est <span class="arithmatex">\(\left\lfloor{\text{log}_b\;n}\right\rfloor + 1\)</span>, c’est-à-dire partie entière inférieure du logarithme en base <span class="arithmatex">\(b\)</span> de <span class="arithmatex">\(n\)</span> plus une unité.</p>
<p>Ainsi, le polynôme cherché est un polynôme fonction de <span class="arithmatex">\(O(\text{log}\;n)\)</span>. <span class="arithmatex">\(O(n^{\frac{1}{2}})\)</span> n’est pas borné par un polynôme en <span class="arithmatex">\(O(\text{log}\;n)\)</span>, ce qui fait que notre algorithme n’est <strong>PAS</strong> polynomial.</p>
<p>Attention toutefois, cela n’exclut pas que le problème soit polynomial (qu’il existe un algorithme polynomial pour le résoudre), mais ce ne sera pas celui-ci. Une bonne pratique consiste à vérifier qu’il est au moins dans la classe <span class="arithmatex">\(NP\)</span> et ensuite d’essayer de montrer qu’il est dans <span class="arithmatex">\(P\)</span> … s’il est dans <span class="arithmatex">\(P\)</span>.</p>
<p>Au vu de la définition formelle de la section précédente, il suffit de trouver un bon certificat qui permet de trouver un algorithme en temps polynomial en fonction de la taille d’écriture du problème. On peut simplement prendre deux entiers <span class="arithmatex">\(a\)</span> et <span class="arithmatex">\(b\)</span> comme certificat et cet algorithme de vérification : </p>
<div class="highlight"><table class="highlighttable"><tr><td class="linenos"><div class="linenodiv"><pre><span></span><span class="normal">1</span>
<span class="normal">2</span></pre></div></td><td class="code"><div><pre><span></span><code>Si a * b = n alors
Retourner Vrai
</code></pre></div></td></tr></table></div>
<p>Dans la vérification, on ne s’intéresse qu’à savoir si <span class="arithmatex">\(x\)</span> est vérifié, comme son nom l’indique. Nous avons bien un algorithme dont la complexité est cette fois borné par un polynôme et notre problème admet donc un algorithme de la classe <span class="arithmatex">\(NP\)</span> qui le résout. Il s’agit donc d’un problème <span class="arithmatex">\(NP\)</span>.</p>
<p>Pour la petite histoire, ce problème est effectivement dans la classe <span class="arithmatex">\(P\)</span>. Le co-problème associé est le test de primalité, dont la preuve de l’appartenance à la classe <span class="arithmatex">\(P\)</span> n’a été trouvée qu’en 2002, avec les algorithmes AKS (au pluriel, car de nombreuses variantes se sont développées).</p>
<h4 id="en-resume_1">En résumé<a class="headerlink" href="#en-resume_1" title="Permanent link">¶</a></h4>
<p>Ainsi s’achève cette première partie qui consistait à pointer du doigt un piège courant de l’évaluation de la classe de complexité d’un algorithme. La conclusion à en tirer est que la notion de complexité est certes relative au nombre d’étapes d’un algorithme, mais elle représente surtout la garantie que le temps de calcul n’explose pas lorsque la taille du problème augmente.</p>
<h3 id="erreur-2-erreur-sur-la-classe-dun-probleme">Erreur 2 : Erreur sur la classe d’un problème<a class="headerlink" href="#erreur-2-erreur-sur-la-classe-dun-probleme" title="Permanent link">¶</a></h3>
<h4 id="le-propos_1">Le propos<a class="headerlink" href="#le-propos_1" title="Permanent link">¶</a></h4>
<p>Lorsque l’on fait face à un problème d’optimisation combinatoire ou de décision (les deux ensembles de problèmes sont équivalents), on procède généralement de la sorte : </p>
<ul>
<li>Trouver un modèle mathématique du problème (hypothèses, données, limites du modèle)</li>
<li>Déterminer à quelle famille se rattache ce problème.</li>
<li>Déterminer ou concevoir un algorithme de résolution du problème.</li>
</ul>
<p>Une technique usuelle est de se ramener à un problème modèle, dont on connait d’une part la classe mais d’autre part des algorithmes de résolution plus ou moins efficaces.</p>
<p>Une erreur classique est de confondre énoncé et donnée. Cette distinction est parfois peu perceptible du fait que la formulation du problème va très peu changer, pouvant induire en erreur sur la nature du problème (et potentiellement sa classe de complexité).</p>
<h4 id="exemple-sat">Exemple : SAT<a class="headerlink" href="#exemple-sat" title="Permanent link">¶</a></h4>
<p>Nous allons à présent parler d’un problème historique de décision. Il s’agit du problème SAT pour <strong>Satisfaction de Contraintes Logiques</strong>. Voici son énoncé formel : </p>
<p><strong>Données</strong> : </p>
<ul>
<li><span class="arithmatex">\(n\)</span> variables logiques <span class="arithmatex">\(x_i\)</span> pour <span class="arithmatex">\(0 \leq 1 \leq n\)</span></li>
<li>On appelle <span class="arithmatex">\(x_i\)</span> et <span class="arithmatex">\(\overline{x_i}\)</span> des littéraux.</li>
<li>On dispose également de <span class="arithmatex">\(p\)</span> clauses qui sont un ensemble de littéraux.</li>
</ul>
<p><strong>Exemple de clause :</strong> <span class="arithmatex">\(\{x_1,\overline{x_3},x_8\}\)</span>.</p>
<p>La question est la suivante : <em>existe-t-il une fonction de vérité (c’est à dire une fonction qui à tout <span class="arithmatex">\(x_i\)</span> va associer une valeur VRAI ou FAUX) telles que les <span class="arithmatex">\(p\)</span> clauses soient vérifiées ?</em></p>
<p>C’est <strong>Cook</strong> qui, en <strong>1972</strong> fit une démonstration directe de la <span class="arithmatex">\(NP\)</span>-Complétude de ce problème.</p>
<p>Il existe un ensemble de sous-problèmes à SAT qui sont 1-SAT, 2-SAT, 3-SAT, etc. Ainsi pour 1-SAT nous avons le problème SAT avec des clauses à un littéral, pour 2-SAT des clauses à deux littéraux, etc.</p>
<p>On pourrait penser que tous ces problèmes sont <span class="arithmatex">\(NP\)</span>-complets sans appartenir à <span class="arithmatex">\(P\)</span> puisque leur énoncé est quasiment le même. On se rend vite compte que ce n’est pas le cas : </p>
<ul>
<li>1-SAT peut être résolu de manière triviale, en temps linéaire. Il suffit de parcourir l’ensemble des clauses et de retourner FAUX si l’on en rencontre une qui est fausse (cela correspond à regarder un simple booléen par clause).</li>
<li>2-SAT peut être résolu en temps polynomial. Je vous laisse chercher l’algorithme qui n’est guère compliqué.</li>
<li>3-SAT est <span class="arithmatex">\(NP\)</span>-complet.</li>
</ul>
<p>On peut par ailleurs montrer que SAT <span class="arithmatex">\(\propto\)</span> 3-SAT pour montrer que 3-SAT est <span class="arithmatex">\(NP\)</span>-complet.</p>
<h4 id="exemple-arbre-couvrant-de-poids-minimal">Exemple : Arbre couvrant de poids minimal<a class="headerlink" href="#exemple-arbre-couvrant-de-poids-minimal" title="Permanent link">¶</a></h4>
<p>Pour clore cet article sur une touche moins technique, on peut citer un second problème dont la modification d’un petit élément d’énoncé peut changer la classe du problème.</p>
<p>Le problème de l’arbre couvrant de poids minimal est un problème que l’on peut formuler de la manière suivante : étant donné un graphe valué, trouver l’arbre contenant l’ensemble des sommets, pour lequel, la somme des valeurs des arcs est minimale.</p>
<p>Il s’agit d’un problème avec de nombreuses applications concrètes. On peut citer par exemple l’optimisation de la longueur de câblage dans un avion ou tout autre appareil.</p>
<p>Ce problème peut être résolu par l’algorithme de <strong>Prim</strong> ou de <strong>Kruskal</strong> en temps polynomial (on utilisera l’un ou l’autre selon la structure du graphe).</p>
<p>Voici une variante de ce problème : étant donné un graphe valué, trouver un arbre couvrant de poids minimal dont le degré des sommets de l’arbre est borné par <span class="arithmatex">\(k\)</span> fixé (c’est-à-dire que pour chaque sommet, il ne peut arriver ou partir que <span class="arithmatex">\(k\)</span> arcs).</p>
<p>Cette variante peut modéliser une situation réelle, dans le cas du câblage d’un établissement où les différents commutateurs réseaux ne disposent que de <span class="arithmatex">\(k\)</span> ports.</p>
<p>Cela peut paraître étonnant, mais ce problème n’est plus polynomial, ce qui va entrainer de lourdes répercussions sur le temps de calcul qui va très certainement exploser avec la taille du problème si l’on se contente d’un des algorithmes cités ci-dessus.</p>
<h3 id="conclusion">Conclusion<a class="headerlink" href="#conclusion" title="Permanent link">¶</a></h3>
<p>J’espère que cet article vous aura convaincu de l’intérêt de posséder des notions basiques sur le calcul de complexité algorithmique et surtout sur la connaissance des différentes classes de complexité qui conditionnent le choix des méthodes de résolution d’un problème (et également ses performances).</p>
<p>Un algorithme d’apparence polynomiale n’en est pas forcément un, et un problème apparent à un autre problème par son énoncé n’est pas forcément dans la même classe de complexité. Seule une étude formelle de la taille d’écriture permet de répondre au premier piège et quelques techniques permettent de s’assurer que l’on peut réduire un problème à un autre (réduction polynomiale ou notion de sous-problème) afin de se prémunir du second.</p>
</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>