informatique théorique – Le blog de Balise

TPA : Théorème de Ramsey

Publié le 27 septembre 201427 septembre 2014 par Balise2 commentaires

Je viens de me rendre compte que j’avais pas encore parlé de théorie de Ramsey dans ce blog, ce qui est profondément scandaleux, parce que c’est un sujet très rigolo. Donc, commençons – aujourd’hui, c’est TPA.

Supposons que nous ayons un graphe dit « complet », c’est-à-dire qu’on se donne un ensemble de sommets, et qu’on trace tous les arcs possibles entre tous les sommets. On dénote par $K_n$ le graphe complet sur n sommets - par exemple, je vous présente $K_5$  :

Maintenant, on va colorier les arcs du graphe en rouge et en bleu, de façon arbitraire. On peut par exemple colorier tous les arcs en bleus, tous les arcs en rouge, ou choisir d’autres coloriages :

Et avec ce coloriage, on se pose une première question : est-ce qu’il est possible d’avoir un coloriage tel qu’on ne puisse pas trouver dans la figure un triangle bleu ou un triangle rouge, c’est-à-dire trois sommets reliés uniquement par des arcs bleus ou rouges ? Les deux du haut ne fonctionnent clairement pas (puisque tous les sommets sont reliés par des arcs bleus et rouges respectivement). Le coloriage en bas à gauche ne fonctionne pas non plus : il a un triangle bleu et un triangle rouge (vous les voyez ?). Le coloriage en bas à droite n’a pas de triangle rouge, mais il a un triangle bleu.

Pour 5 points, ce n’est pas très difficile de finir par trouver un coloriage qui ne contient ni triangle bleu ni triangle rouge, et c’est celui-ci :

L’étape suivante est de se poser la même question non pas avec un graphe complet sur 5 sommets ( $K_5$ ) mais avec un graphe complet sur 6 sommets ( $K_6$ ), comme celui-ci :

Et la réponse est non, ce n’est pas possible : on ne peut pas colorier une $K_6$ avec deux couleurs en évitant d’avoir un triangle monochromatique (tout bleu ou tout rouge, donc). La première remarque qu’on peut faire, c’est que pour vérifier par force brute que c’est effectivement le cas, ça va prendre un petit peu de temps. Le graphe ci-dessus a 15 arcs, ce qui correspond à $2^{15}$ coloriages différents. Pour voir ça, on peut choisir un ordre pour les arcs (n’importe quel ordre) et commencer à colorier. Pour le premier arc, on peut choisir rouge ou bleu, ça fait deux choix. Pour le deuxième arc, idem – et on a déjà quatre choix avec deux arcs, puisqu’ils peuvent être tous les deux rouges, tous les deux bleus, rouge-bleu ou bleu-rouge. Le troisième choix multiplie encore ces choix par deux (puisque chaque choix peut correspondre à un troisième arc rouge ou bleu), et ainsi de suite pour les 15 arcs, soit 2×2×2×…×2 = $2^{15}$ . $2^{15}$ , ça fait 32768. À la main, ça va faire beaucoup de coloriages à vérifier, mais sur un ordinateur, ça reste encore nettement dans le domaine du faisable.

Avant de programmer le coloriage et de vérifier, on peut se demander s’il y aurait moyen de prouver qu’il y a toujours un triangle monochromatique dans une $K_6$ coloriée avec 2 couleurs. Donc, on prend un coloriage, n’importe lequel. On prend un sommet, n’importe lequel aussi. Ce sommet, il a 5 arcs qui y sont connectés, et parmi ces cinq arcs, il y en a au moins trois qui sont de la même couleur (parce que si j’ai au plus deux arcs bleus ET au plus deux arcs rouges, ben j’ai au plus 4 arcs). Pour faire simple, je vais supposer que les trois arcs qui sont de la même couleur sont bleus (je peux toujours faire ça, si ce n’est pas le cas il suffit de remplacer rouge par bleu et bleu par rouge dans ce qui suit). Maintenant on fait une petite figure avec des notations.

J’ai au moins trois arcs bleus qui partent de mon sommet initial, j’en choisis exactement trois (les deux autres peuvent être rouges ou bleus). Ces arcs définissent trois points sur le graphe, qui sont les autres extrémités des trois arcs ; je nomme ces points $u, v$ et $w$ . Et là, il peut se passer plusieurs choses. Si l’arc entre $u$ et $v$ est bleu, alors j’ai un triangle bleu. Si l’arc entre $v$ et $w$ est bleu, alors j’ai un triangle bleu. Si l’arc entre $u$ et $w$ est bleu, alors j’ai un triangle bleu. Et si rien de tout ça ne se passe…

ben l’arc entre $u$ et $v$ est rouge, l’arc entre $v$ et $w$ est rouge, et l’arc entre $w$ et $u$ est rouge aussi, donc le triangle défini par $u, v, w$ est tout rouge. Tout ce que j’ai raconté là s’applique à n’importe quel coloriage (même s’il faut éventuellement changer rouge en bleu et bleu en rouge), et donc on ne peut pas trouver de coloriage qui n’ait ni triangle bleu, ni triangle rouge.

La remarque suivante, c’est que n’importe quelle $K_n$ (c’est-à-dire un graphe complet sur $n$ sommets), pour $n \geq 6$ , contient une $K_6$ . Donc si on ne peut pas colorier une $K_6$ sans avoir de triangle monochromatique, on ne peut pas non plus colorier une $K_n, n\geq 6$ sans triangle monochromatique.

Donc, pour les triangles, on sait ce qu’il se passe : pour $n\leq 5$ , on peut trouver un coloriage tel qu’on ne trouve pas de triangle monochromatique, et pour $n \geq 6$ , on a prouvé qu’il n’existait pas.

La question suivante est : maintenant qu’on a des choses pour les triangles, est-ce qu’on peut avoir le même genre de résultat pour plus de points ? Plus spécifiquement, si je considère une $K_n$ , est-ce que je peux la colorier avec deux couleurs de manière à éviter d’y trouver une $K_4$ , $K_5$ , $K_6$ , $K_{42}$ de la même couleur (remarquons qu’un triangle est une $K_3$ 😉 )? Et ben, c’est une question compliquée. Pour être sûr de trouver une $K_4$ , il a été prouvé qu’on a besoin de 18 points. Ce qui veut dire qu’on peut colorier ce bidule-là avec 2 couleurs et ne pas y trouver de $K_4$ monochromatique:

Si on rajoute un sommet et qu’on le connecte à tous les autres, par contre, on est sûr de trouver une $K_4$ monochromatique si on colorie avec deux couleurs. Là, pour le coup, si on veut réellement vérifier tous les coloriages possibles, il va vraiment falloir faire des progrès sur la puissance informatique. Une $K_{18}$ (un graphe complet sur 18 sommets, donc) a 153 arcs, donc si on se mettait en tête de vérifier tous les coloriages, il faudrait en vérifier $2^{153}$ . Si on est capable de vérifier un coloriage par nanoseconde (ce qui n’est pas franchement réaliste), il faudrait plus de 3 000 000 000 000 000 000 000 000 000 (3 suivi de 27 zéros) SIÈCLES pour tout vérifier… on est pas rendu 🙂

Là où ça devient VRAIMENT amusant, c’est quand on se pose la question de trouver des $K_5$ et supérieur (qui soient monochromatiques, donc). Pour la $K_5$ , on sait que pour plus de 49 sommets, on la trouvera nécessairement. On sait aussi qu’on peut construire un coloriage sur 42 sommets sans $K_5$ monochromatique. Le lecteur attentif aura remarqué qu’on ne sait pas ce qu’il se passe entre 43 et 49 sommets… La situation est de moins en moins claire au fur et à mesure : pour la $K_{10}$ monochromatique, on sait que le seuil se situe quelque part entre 798 (pour 797 sommets on sait qu’on peut colorier sans avoir de $K_{10}$ monochromatique) et… 23556 (pour un graphe complet sur 23556 sommets colorié avec deux couleurs, on sait qu’on aura toujours une $K_{10}$ monochromatique).

Le théorème de Ramsey qui donne son nom à ce billet de blog dit que quelque soit $r$ , on peut trouver un $n$ tel que tout coloriage avec deux couleurs d’une $K_n$ contienne nécessairement une $K_r$ monochromatique. Ledit théorème est plus général que ça : il dit que pour tout $r_1, r_2, r_3... r_\ell$ on peut trouver un $n$ tel que tout coloriage de $K_n$ avec $\ell$ couleurs $c_1, c_2,..., c_\ell$ contient ou bien une $K_{r_1}$ de couleur $c_1$ , ou bien une $K_{r_2}$ de couleur $c_2$ , …, ou bien une $K_{r_\ell}$ de couleur $c_\ell$ . Et on dénote $n$ par $R(r_1, r_2,..., r_\ell)$ . (Pour rattacher aux trucs précédents, j’ai démontré que $R(3,3) = 6$ , et j’ai indiqué que $R(4,4) = 18$ , $43 \leq R(5,5) \leq 49$ et que $798 \leq R(10,10) \leq 23556$ .

On peut exprimer ça de façon plus « philosophique » en disant qu’une structure suffisamment grande aura toujours un peu d’ordre local quelque part. Ce que je trouve personnellement assez fascinant.

Le mot de la fin revient à Joel Spencer: « Erdős nous a demandé d’imaginer une force d’extraterrestres, beaucoup plus puissante que nous, qui atterrit sur Terre et nous demande la valeur de R(5,5), ou bien ils détruisent la planète. Dans ce cas, dit-il, nous devrions combiner la puissance de tous nos ordinateurs et de tous nos mathématiciens pour tenter de trouver la valeur. Mais supposons qu’ils demandent R(6,6). Dans ce cas, il pense qu’il faudrait détruire les extraterrestres. » (traduction personnelle).

Les algorithmes PPZ et PPSZ

Publié le 28 juin 2014 par Balise2 commentaires

Aujourd’hui, on va causer 3-SAT, et on va en particulier causer de deux algorithmes très voisins, les algorithmes PPZ et son petit frère PPSZ.

Il est plus que temps que je m’attaque à ce billet que j’aurais dû écrire depuis longtemps déjà. C’est un billet qui me tient à cœur parce que ça fait un an et demi que je fais des trucs autour de ces algorithmes, et que je commence à en avoir une assez bonne idée 🙂

Rappelons un peu de formalisme, histoire qu’on sache tous de quoi on est en train de parler. Pour une intro avec un peu plus de détails, voir mon billet sur SAT. J’ai $n$ variables $x_1,..., x_n$ , et j’ai des formules qui sont de ce type:

$(x_1 \vee \bar x_2 \vee x_3) \wedge (x_1 \vee \bar x_3 \vee x_4) \wedge (x_6 \vee x_7 \vee x_8) \wedge ...$

et je veux déterminer si, étant donné une telle formule, il existe des valeurs pour les variables $x_1$ à $x_n$ (on parle d’une affectation) qui permettent d’évaluer la formule à 1 (on dit alors que la formule est satisfaite). Dans le cas général, c’est un problème NP-complet ; on a donc peu de chance de trouver un algorithme efficace qui marche à tous les coups. C’est bien le « à tous les coups » qui m’intéresse ici : je me demande ce que je peux garantir pour mon algorithme, même si je tombe sur la formule la plus difficile du monde. Le « record » actuel pour ce type de garantie est actuellement pour l’algorithme PPSZ, qui est un algorithme aléatoire, et qui est le sujet de ce billet. Comme je parle d’algorithme aléatoire, il me paraît un poil plus intuitif de parler de probabilité de succès que de temps d’exécution même si, on l’a vu, les deux notions sont liées – puisqu’il suffit de répéter un algorithme aléatoire avec une probabilité de succès donnée suffisamment de fois pour être raisonnablement sûr qu’il réussisse. Ça fait un peu Shadok, mais passons. Je vais aussi, dans ce qui suit, supposer que j’ai une formule pour laquelle je sais qu’il existe un ensemble de valeurs qui la satisfont, et que je veux « juste » trouver les valeurs en question. En pratique, les deux problèmes sont liés aussi : je peux supposer que si mon algorithme trouve ces valeurs, ben c’est qu’elles existent, et que si je cherche suffisamment longtemps sans les trouver, ça serait quand même pas de bol qu’elles existent et que je les aie ratées.

L’algorithme aléatoire le plus simple auquel on peut penser est de prendre des valeurs au hasard, de vérifier si elles satisfont la formule, et de recommencer si c’est pas le cas. Toutes les affectations possibles ont la même probabilité (si je les choisis au hasard comme ça) – et j’en ai $2^n$ – parce que pour chaque variable, j’ai deux possibilités, 0 ou 1. Donc la probabilité de succès de cet algorithme, si j’ai $\ell$ affectations qui satisfont ma formule, est de $\ell / 2^n$  : parmi les $2^n$ choix que je peux faire, j’en ai $\ell$ qui marchent.

Après, il y a moyen de faire les choses de manière un peu plus intelligente. Plutôt que d’affecter les variables toutes en même temps, je vais les affecter une à une. Qu’est-ce que ça change ? Ça change que si j’ai un truc qui est trivialement idiot à faire, je peux éviter de le faire. Ce qui veut dire qu’il faut que j’explique ce que ça veut dire « trivialement idiot ». Supposons que j’aie une formule très simple qui soit juste $(x_1 \vee x_2 \vee x_3)$ . Si j’ai choisi pour $x_1$ la valeur 0 et pour $x_2$ la valeur 0, il est « trivialement idiot » de choisir 0 pour $x_3$ puisque je n’ai alors aucune chance de satisfaire la formule. Donc par « trivialement idiot », je veux dire qu’il y a une clause qu’il n’y a plus qu’une seule chance de satisfaire, c’est-à-dire qu’on a déjà affecté des valeurs à deux variables sur les trois de la clause, et que la clause n’est toujours pas satisfaite. Si j’utilise mon algorithme précédent, j’ai une probabilité 7/8 de trouver une affectation satisfaisante (parce qu’avec probabilité 1/8 je tombe sur 000 pour mes variables et ma formule n’est pas satisfaite). Si j’essaie d’éviter les trucs trivialement idiots… ben déroulons le truc. Je commence par $x_1$ , il n’y a pas de truc trivialement idiot à éviter, donc je prends une valeur au hasard. Je continue par $x_2$  ; là encore, il n’y a pas de truc trivialement idiot à éviter, donc je prends une valeur au hasard. J’arrive à $x_3$ , et là j’ai deux possibilités. Si $x_1$ et $x_2$ ont été mis tous les deux à 0, j’ai un truc trivialement idiot à éviter, c’est de mettre $x_3$ à 0, donc j’évite ça, je mets $x_3$ à 1, et ma formule est satisfaite. Si $x_1$ ou $x_2$ a été mis à 1, quoi que je fasse sur $x_3$ sera valide, donc je ne peux pas me tromper. Sur ce cas spécifique, rien qu’en évitant les trucs trivialement idiots, mon algorithme passe à une probabilité de succès de 1.

C’est pas toujours aussi idyllique, évidemment – là les choses se passent bien parce que j’ai une seule clause, beaucoup d’affectations valides, et qu’on est contents. Maintenant, un cas un peu plus sioux : considérons la formule

$(x_1 \vee x_2 \vee x_3) \wedge (x_1 \vee x_2 \vee \bar x_3) \wedge (x_1 \vee \bar x_2 \vee x_3) \wedge (x_1 \vee \bar x_2 \vee \bar x_3) \wedge (\bar x_1 \vee x_2 \vee x_3) \wedge (\bar x_1 \vee x_2 \vee \bar x_3)$

Deux affectations satisfont cette formule : $x_1 = 1, x_2 = 1, x_3 = 0$ et $x_1 = 1, x_2 = 1, x_3 = 1$ . Avec mon algorithme « simple », la probabilité de succès est de 2/8 = 1/4. Avec mon algorithme qui cherche à éviter les trucs « trivialement idiots »… aussi, dans certaines conditions. Si je commence par la variable $x_1$ et que je la mets à 0, je n’ai aucune chance d’obtenir une affectation satisfaisant la formule. Si je continue par la variable $x_2$ et que je la mets à 0, idem. Donc il faut que je mette $x_1$ et $x_2$ à 1 tous les deux, ce qui arrive avec une probabilité 1/4 ; $x_3$ peut être mis à n’importe quelle valeur, donc si on n’a pas fait d’erreur jusqu’ici on n’en fera pas non plus à la dernière étape. Dans ce cas, donc, la probabilité de succès avec ou sans la détection de trucs « trivialement idiots » est la même. Sauf que… si on traite les variables non pas dans cet ordre là mais, par exemple, dans l’ordre $x_3 x_2 x_1$ … Pour la première variable, $x_3$ , on ne peut pas faire d’erreur, quelle que soit la valeur d’affectation. Pour $x_2$ , on ne peut pas détecter de truc trivialement idiot, donc on la met à la bonne valeur avec une probabilité 1/2. Mais si cela arrive, la clause $(x_1 \vee \bar x_2 \vee \bar x_3)$ ou la clause $(x_1 \vee \bar x_2 \vee x_3)$ (selon la valeur affectée à $x_3$ ) indiquera à l’algorithme que mettre $x_1$ à 0 est trivialement idiot, ce qu’il faut éviter. Avec cet ordre de variables, la probabilité de succès de notre algorithme amélioré passe à 1/2. Il y a donc de « bons » ordres de variables et de « mauvais » ordres de variables (on parle de permutations). Comme il est difficile de savoir avant de commencer si une permutation est bonne ou mauvaise (ou comment trouver une bonne permutation), on fait comme d’habitude : on prend une permutation au hasard et on espère qu’en moyenne ça marche bien.

C’est exactement ce que fait l’algorithme PPZ (nommé d’après ses trois auteurs, Ramamohan Paturi, Pavel Pudlák et Francis Zane, dans un papier intitulé Satisfiability Coding Lemma) :

On part d’une formule $F$ sur $n$ variables, et on commence avec une affectation vide (on n’affecte aucune valeur aux variables pour l’instant).
On choisit un ordre aléatoire pour les variables, et on les traite une par une dans cet ordre :
- Pour la variable courante $x_i$ , si $x_i = 0$ est trivialement idiot, on affecte 1 à $x_i$
- Sinon, si $x_i = 1$ est trivialement idiot, on affecte 0 à $x_i$
- Sinon, on affecte une valeur aléatoire à $x_i$
- Et on passe à la variable suivante.
Si l’affectation qu’on trouve satisfait la formule, c’est terminé ! Sinon, on recommence au départ.

L’analyse de la probabilité de succès de l’algorithme est relativement simple. Sans rentrer dans les détails, l’idée c’est que si je n’ai pas le choix pour une variable (c’est-à-dire si la mettre à 0 ou à 1 fait que l’affectation ne peut pas être satisfaisante), alors j’ai au moins une clause qui rend ce choix trivialement idiot dans au moins une permutation sur trois (parce que dans un cas sur trois, la variable en question arrivera en dernier dans la clause en question). J’ai toujours des choix aléatoires pour certaines variables, donc l’algorithme peut toujours se vautrer lamentablement, mais la probabilité de ne pas se vautrer est meilleure que si on prend juste une affectation au hasard.

Après, le lecteur attentif se sera peut-être dit « ouiiii mais si j’assigne $x_1$ à 1, j’ai à la fois une clause $(\bar x_1, x_2, x_3)$ et une clause $(\bar x_1, x_2, \bar x_3)$ , donc quelque part c’est AUSSI trivialement idiot de mettre $x_2$ à 0… ». Le lecteur attentif est un petit malin. Et c’est aussi, quelque part, ce que fait l’algorithme PPSZ (nommé d’après les trois auteurs précédents + Michael Saks, dans un papier intitulé An Improved Exponential-Time Algorithm for $k$ -SAT) : plutôt que de regarder les clauses une à une pour voir si par hasard on peut éliminer un choix trivialement idiot, on en regarde beaucoup à la fois (typiquement $\log \log n$ , où $n$ est le nombre de variables de la formule) pour tenter d’en tirer les mêmes conclusions. il y a un nombre sous-exponentiel d’ensembles de $\log \log n$ clauses, et examiner chacun d’entre eux peut se faire en temps sous-exponentiel aussi (on peut se contenter de regarder toutes les valeurs possible pour le sous-ensemble de variables qui interviennent dans ce sous-ensemble de clauses). Les mauvais choix ne peuvent plus nécessairement être qualifiés de « trivialement idiots » mais peut-être de « manifestement idiots » ; le résultat est le même : si on peut les détecter, autant les éviter. Pour le coup, l’analyse de la probabilité de succès de cet algorithme est (beaucoup) plus complexe ; pour la petite histoire, lorsque l’article original a été publié, les auteurs n’avaient établi la probabilité de succès que dans le cas où la formule n’avait qu’une seule affectation satisfaisante (l’analyse du cas général n’arrivait à prouver qu’une probabilité de succès plus basse). La preuve plus générale a été établie par Timon Hertli (3-SAT Faster and Simpler – Unique-SAT Bounds for PPSZ Hold in General), mais il s’est passé plus de dix ans entre l’introduction de l’algorithme et la preuve en question. Une version « lisible » (pour une certaine définition de « lisible, admettons-le) de la preuve en question est disponible dans ma thèse de semestre (chapitre 2) – elle est difficile à résumer en moins de, mettons, 8 pages (heu, déjà 8 pages, c’est challenge, en fait.)

J’ai travaillé autour de ces algorithmes depuis un an et demi (pas complètement par hasard, Timon dont je parle précédemment étant doctorant à l’ETH… et mon superviseur sur tout ce que j’ai fait), et pour le coup c’est probablement LE sujet sur lequel je me sens prête à répondre à BEAUCOUP de questions 🙂

Algorithmes aléatoires et conflits sur l’échiquier

Publié le 26 janvier 2014 par Balise1 commentaire

J’avais dit que je ferais un billet sur les algorithmes aléatoires, et je ne l’ai toujours pas fait. Une petite part de flemme, et une grosse part d’infusion – mais je viens enfin de trouver l’exemple raisonnablement rigolo et abordable que je cherchais depuis longtemps…

Le principe de l’algorithme aléatoire, c’est essentiellement « boah, on va faire n’importe quoi, et puis si on fait n’importe quoi suffisamment de fois, on finira bien par tomber sur une solution qui marche ». Le « n’importe quoi » consiste à faire un choix au hasard quand on ne sait pas quoi faire, et le « suffisamment de fois » dépend du « n’importe quoi ». L’idée, c’est que quand on fait les choses au hasard, on a normalement au moins une chance, même infime, de tomber sur une solution. Mais si j’ai, par exemple, une chance sur 1000 de tomber sur la solution à mon problème, si j’exécute la même procédure aléatoire indépendamment 1000 fois, j’ai de bonnes chance de tomber sur ce que je veux. Je ne peux pas garantir à 100% que je vais trouver la solution, mais… Tiens, d’ailleurs, quelle est la probabilité que ça marche en faisant 1000 essais ? C’est un petit exercice assez facile, peut-être qu’un petit rappel de probabilités peut être utile (voir la partie 1 et la partie 2)… Je vais tout de même donner la solution. La probabilité que l’algorithme retourne le bon résultat est 0.001. La probabilité qu’après 1000 fois ça ait réussi au moins une fois, c’est 1 – la probabilité que ça ait échoué toutes les fois. La probabilité que ça échoue, c’est 0.999. Comme mes exécutions sont indépendantes, je peux multiplier les probabilités de tous ces essais entre elles : ça fait 0.999^1000, c’est à dire environ 0.368. Donc, la probabilité que ça ait réussi après 1000 essais est de 0.623. Ce qui peut paraître assez faible, ça fait moins de trois chances sur quatre. Mais si je répète, non pas 1000 fois, mais 3000 fois, j’obtiens une probabilité de succès de 1 – 0.999^3000, soit environ 0.95… Et on peut continuer à répéter pour avoir la probabilité de succès que l’on souhaite obtenir, même avec des probabilités de succès initiales très faibles. Si l’algorithme lui-même n’est pas trop violent en terme de calculs, n’importe quel ordinateur est tout à fait capable d’exécuter ça en un temps correct. Et les algorithmes aléatoires peuvent souvent se permettre d’être très simples – plutôt que de calculer un machin compliqué à calculer, pouf, on met une valeur au hasard et on espère que ça marche.

Ça peut paraître un peu fou comme approche, mais comme j’ai essayé de l’expliquer dans le paragraphe qui précède, on peut en fait faire des choses tout à fait rigoureuses dans le domaine. On prend un algorithme, on calcule la probabilité qu’il renvoie une réponse correcte, de là on déduit combien de fois il faudra le répéter pour avoir une probabilité de succès qui convient, et on est content. Et de là, il y a deux grosses difficultés. La première, c’est d’arriver à un algorithme qui ne soit pas complètement débile. Si l’espace de solutions est immense et qu’on se contente de prendre un élément de l’espace de solutions au pif, ça va rarement donner des choses intéressantes. Par contre, si on arrive à avoir une approche semi-intelligente, ça permet souvent d’avoir des algorithmes qui ont une espérance de temps d’exécution meilleure que les algorithmes déterministes pour un problème donné. La deuxième grosse difficulté, c’est parfois de calculer/prouver la probabilité de succès d’un algorithme (ce qui permet d’avoir une idée du nombre de répétitions à prévoir et donc du temps d’exécution). Il y a une troisième difficulté, qui n’est pas vraiment liée directement à l’algorithme aléatoire lui-même. On ne sait pas, à l’heure qu’il est, si l’ajout d’une composante aléatoire permet toujours d’avoir des algorithmes plus performants. Il existe des gens (j’en fais partie en ce moment) qui s’intéressent à la question de savoir si un algorithme aléatoire donné peut être transformé de façon magique en un algorithme déterministe (sans hasard, donc) en gardant des performances équivalentes. Il y a aussi des gens qui s’intéressent à la question générale de savoir si l’aléatoire peut apporter quelque chose, ou si la classe des problèmes qui se résolvent « facilement » avec des éléments aléatoires est la même que celle des problèmes qui se résolvent « facilement » de façon déterministe – pour une certaine définition de facilement. (Notons d’ailleurs que les deux questions n’ont pas le même sens, en dehors de la distinction « un algorithme donné / une classe de problèmes » – dans le premier cas on cherche à avoir les mêmes performances, dans le second cas, on est plus souples et on pourrait par exemple se contenter d’un « si je peux résoudre un problème en temps t avec de l’aléatoire, je peux le résoudre en temps t³ sans aléatoire »).

Après ces longs paragraphes introductifs et vaguement philosophiques, je vais donner un exemple à partir d’un problème connu, celui des 8 reines. Ça rappellera sans doute des choses à ceux qui ont joué à The 7th Guest il y a 20 ans. On suppose qu’on dispose d’un échiquier – donc une grille 8×8 – et de 8 pions qui peuvent se déplacer comme une reine aux échecs, c’est-à-dire en ligne horizontale ou verticale, et en diagonale, d’un nombre arbitraire de cases. On dit que deux reines sont en conflit lorsqu’elles peuvent s’attaquer - c’est-à-dire qu’elles sont sur la même ligne horizontale, verticale ou diagonale. On veut placer huit reines sur l’échiquier de façon à ce qu’aucune d’elles ne soit en conflit avec aucune autre. C’est pas complètement trivial comme problème, comme on peut s’en rendre compte en essayant de le résoudre à la main (ça se fait, mais c’est pas immédiat). Là, le problème reste relativement simple, au sens où la grille reste assez petite. Faire le même genre de choses avec 50 reines sur un échiquier 50×50, il y a de bonnes chances de ne pas s’en sortir à la main. Et puis construire un algorithme déterministe pour ce machin, c’est pénible, ça backtracke dans tous les sens, et moi le backtracking ça me fout mal au crâne (c’est pas complètement vrai, il y a un algorithme récursif qui existe aussi, mais bon). Donc, voyons ce qu’on peut faire de manière aléatoire. Je vais me limiter dans certains cas aux 8 reines, parce que ça fait des nombres « gérables ». Et je vais tricher un peu, je vais dégainer la Wikipedia sur le sujet Problème des huit dames, et je vais affirmer qu’il existe 92 solutions au problème – ça me sera utile pour donner certains nombres.

On peut prendre une approche vraiment bourrine – on numérote les cases de l’échiquier de 1 à 64, on tire huit numéros de 1 à 64, et on place une reine sur chaque case. Si ça marche, ben on a fini ; si ça marche pas, on reprend les reines de l’échiquier et on recommence. La probabilité de succès de cet algorithme, elle est pas bien élevée – il y a 4 426 165 368 manières de choisir 8 chiffres parmi 64, ce qui nous donne une probabilité de succès d’environ 2.07 × 10^-8. C’est peu.

Donc, on regarde d’un peu plus près le problème, et on fait une observation facile : si je veux avoir la moindre chance qu’une solution marche, une chose est sûre, c’est que je n’aurai qu’une seule reine par colonne de mon échiquier. Donc, plutôt que de prendre huit numéros de 1 à 64, je prends, pour chaque reine, un nombre au hasard de 1 à 8, et je place la reine numéro k sur la colonne k et sur la ligne correspondant au nombre qu’on a pris au hasard. C’est sensiblement meilleur – ça correspond à 8^8 = 16 777 216 possibilités, soit une probabilité de succès qui tourne autour de 5.48 × 10^-6. C’est mieux, mais c’est toujours pas top.

On fait alors l’observation facile suivante : je n’aurai aussi qu’une seule reine par ligne de mon échiquier. Bon, d’accord, j’aurais probablement pu faire l’observation en même temps que la précédente, mais faut pas me brusquer, on est dimanche matin et j’ai mangé de la raclette hier soir. Donc, plutôt que de prendre un nombre au hasard de 1 à 8 pour chaque reine, je prends une permutation au hasard (c’est à dire que je prends un nombre de huit chiffres dans lequel tous les chiffres de 1 à 8 apparaissent), et je pose mes reines en fonction de cette permutation (la première reine sur la ligne du premier chiffre, la deuxième sur la ligne du deuxième, et ainsi de suite). Ça améliore encore un peu les choses – il y a 8! = 40 320 permutations possibles, soit une probabilité de succès de 2.28×10^-3, soit 0.02%. Ça commence à rentrer dans la catégorie des machins « faisables »… mais uniquement pour des petites valeurs de la taille de l’échiquier. Si on monte, mettons, ne serait-ce qu’à 16 reines sur un échiquier de 16×16 cases, la séquence OEIS kivabien nous permet d’évaluer la probabilité de succès à 14 772 512/16!, soit environ 7.06×10^-7. Le problème, c’est que la factorielle, là, ben elle est quand même encore très moche.

On peut encore améliorer les choses. Il y a trois sources de conflits pour les reines sur l’échiquier : les lignes horizontales, les lignes verticales, et les diagonales. L’approche par permutations permet de gérer les deux premières, mais y ajouter la gestion des diagonales commence à filer VRAIMENT mal au crâne (on se retrouve à faire des machins du genre « si j’ai deux chiffres qui sont dans des positions qui diffèrent de k, ils ne peuvent pas différer eux-mêmes de k », et c’est imbitable). Par contre, ce qu’on peut faire assez facilement, c’est générer la permutation petit à petit. L’idée, c’est qu’on place les reines une par une au hasard dans une colonne, en supprimant toutes les lignes qui sont en conflit avec une reine placée précédemment. Donc, on place la première reine au hasard sur la première colonne, la deuxième reine au hasard, mais de façon à ce qu’elle ne soit pas sur la ligne de la première ni sur ses diagonales, et ainsi de suite. Et si on ne peut pas trouver une position sans conflit dans la colonne, c’est que la solution courante ne marche pas – on vire tout et on recommence du début. Je n’ai pas trouvé d’analyse rigoureuse de ce machin, et j’ai la flemme de la tenter moi-même (je soupçonne accessoirement ne pas être capable de m’en sortir, du moins pas dans un temps qui me permette de publier ce billet rapidement), mais il y a au moins une implémentation qui a été testée sur 1000 reines avec des temps d’exécution raisonnables (variant apparemment de 39 secondes à 25 minutes). L’idée, cela dit, c’est qu’on élimine beaucoup de permutations de l’espace de recherche : par exemple, on supprime toutes celles qui commencent par « 12 » – ce qui correspond, pour un problème de 8 reines, à 720 permutations, ce qui n’est pas énorme, mais si on multiplie ça par 14 (parce qu’on supprime aussi celles qui commencent par « 23 », « 34 »,…, « 78 », « 21 », « 32 »,…,« 87 »), à 10 080 permutations, soit déjà un quart de l’espace de recherche ! Plus l’échiquier est grand, moins ces deux premières étapes seront significatives (et plus le « un quart » va tendre vers 0, si vous me passez l’expression), mais l’idée reste la même : on réduit l’espace de recherche, et la probabilité de succès augmente.

Toutes ces approches ont la même base : on recherche une combinaison qui fonctionne dans tout l’ensemble des combinaisons, en essayant de supprimer les combinaisons qui ne marchent pas le plus tôt possible. Il existe un autre type d’approche, qui est celle de la « réparation ». L’idée, c’est que pour une permutation donnée, on n’est peut-être pas loin d’une solution qui marche. Donc, plutôt que d’explorer l’espace de combinaisons entier, on peut peut-être explorer autour d’une permutation en essayant de se rapprocher d’une solution. Une solution, par définition, c’est une combinaison qui a zéro conflit. Donc, on peut supposer qu’on se « rapproche » d’une solution quand on diminue le nombre de conflits. C’est l’idée du dernier algorithme que je vais présenter dans ce billet. On commence par prendre une permutation aléatoire qui « a une bonne tête » en utilisant l’algorithme précédent et, au lieu de s’arrêter lorsqu’on rencontre un conflit, en plaçant une reine au hasard sur l’une des cases présentant le nombre minimum de conflits de la colonne. Si elle marche, tant mieux, on a fini. Sinon, on choisit une colonne au hasard, et on compte, pour chaque case, le nombre de conflits auquel elle correspond, en ne comptant qu’un seul conflit si plusieurs reines génèrent ce conflit (parce de toute façon elles sont alors en conflit entre elles, et il faudra gérer ça). S’il existe une case pour laquelle la reine de la colonne courante aurait moins de conflits, on la déplace (en choisissant au hasard la case si plusieurs d’entre elles ont le même nombre de conflits). Et on recommence. Il n’y a en revanche pas de garantie que cet algorithme va toujours renvoyer une solution : si on n’a pas de chance, on peut se retrouver dans un minimum local, ne pouvoir améliorer le nombre de conflits sur aucune colonne, et boucler infiniment. Il faut prendre ce genre de cas en compte, et arrêter/recommencer l’algorithme si le nombre d’étapes commence à exploser vraiment trop violemment. Là, vraiment, je sais que l’analyse de cet algorithme va au-delà de ce que je veux présenter sur ce blog (j’avoue ne pas l’avoir lue, surtout qu’il manque des figures sur le papier). Le papier qui présente la méthode indique que le nombre de conflit réparés reste à peu près constant quel que soit la taille de la grille, et qu’ils arrivent à résoudre le problème sur un échiquier d’un million de cases de côté en 4 minutes. Sur une SPARCstation 1, en 1991.

Bref, les algorithmes aléatoires, c’est rigolo et utile. Je pense qu’un prochain billet discutera des algorithmes aléatoires pour SAT, parce que c’est quand même ce sur quoi je passe beaucoup de temps en ce moment. J’ai quand même passé un truc assez fondamental sous le tapis, c’est que générer des nombres aléatoires, c’est hautement non-trivial. En pratique, ce que j’ai présenté ici fonctionne aussi avec des nombres « à peu près aléatoires » tels qu’un ordinateur est capable de les générer. Mais ceci est une autre histoire, que nous vous raconterons une prochaine fois… ou pas, parce que là, j’ai pas le niveau 😛

« Le méta pue », ou Crédibilité des preuves

Publié le 30 juin 20139 novembre 2013 par Balise1 commentaire

Il y a quelque temps, une soumission à arXiv a fait pas mal de bruit. arXiv, pour ceux qui ne connaissent pas, est une archive d’articles scientifiques – les auteurs y soumettent en général des versions préliminaires d’articles publiés ailleurs. arXiv fait un peu de modération pour éviter le spam et les trucs vraiment délirants, mais, si je comprends bien, tant que ça a à peu près une tronche d’article scientifique dans les domaines gérés par arXiv, ça passe la modération.

Et, donc, le 26 mai, ya un article intitulé A Polynomial Time Algorithm for the Hamilton Circuit Problem, par Xinwen Jiang, qui est apparu sur arXiv. Dans la description de l’article, il y a une petite phrase : « Our result implies NP=P », c’est à dire « Notre résultat implique que P=NP ». Pour un petit rappel sur le problème en question, il se trouve que j’ai causé à ce sujet dans le billet intitulé, fort logiquement, Le problème « P est-il égal à NP ? ».

J’avoue que je ne comprends pas bien pourquoi, spécifiquement, ce papier a fait du bruit. Et par « faire du bruit », j’entends qu’il est passé plusieurs fois sur mon radar, par plusieurs sources différentes. Je ne comprends pas pourquoi, parce que des papiers qui prouvent que P = NP ou que P ≠ NP, il y en a au moins une dizaine par an – voir par exemple The P-versus-NP Page qui vise à tous les recenser. Et qu’on ne fait pas tout un pataquès tous les mois à ce sujet.

C’est bizarre, parce qu’il y a tout un tas de choses qui font que ce papier est peu crédible. Scott Aaronson a écrit des choses sur la crédibilité des articles scientifiques « révolutionnaires » : je citerai ici Ten Signs a Claimed Mathematical Breakthrough is Wrong et Eight Signs A Claimed P is not NP Proof Is Wrong. Aaronson s’intéresse plutôt aux preuves P ≠ NP, mais certains arguments sont aussi valides dans le cas des preuves P = NP.

J’avoue humblement que je n’ai pas lu le papier de Xinwen Jiang. Je ne sais pas non plus si quelqu’un (n’importe qui) a lu le papier de façon sérieuse. Je n’ai trouvé aucun article ou billet de blog disant « la preuve de Xinwen Jiang est fausse et voici pourquoi », ni d’article « meeeeerde, ça marche, son truc ». La discussion la plus fournie que j’ai vu passer est celle de Hacker News dans ce fil de discussion.

Personnellement, la raison principale pour laquelle j’ai abandonné la lecture du papier va sembler extrêmement snob. Mais le papier n’est pas écrit en $\LaTeX$ . Du coup… ben j’ai pas eu le courage, bêtement. La mise en page est immonde, les maths sont illisibles. Je regarde ce truc et j’ai mal au crâne. Un petit morceau de moi se dit que si le type en face n’a pas pris la peine de faire en sorte que son machin soit lisible, je vois pas pourquoi je prendrais la peine de tenter de le lire. Évidemment, c’est hyper-fallacieux, comme argument. Parce que si jamais quelqu’un arrive avec une preuve qui marche, il a moyen de troller une communauté complète rien qu’en publiant sa preuve en Word 😀 Après, je peux argumenter sur le fait que j’ai jamais réussi à utiliser l’éditeur d’équations de Word de façon raisonnablement déterministe, alors que $\LaTeX$ se comporte plutôt mieux de ce point de vue, et que j’ai donc plus confiance dans le fait qu’un papier en $\LaTeX$ reflète effectivement ce que l’auteur voulait dire. Mais ça touche probablement à la mauvaise foi aussi.

Dans les arguments un demi-chouille plus « sérieux », mais qui touchent toujours au méta : l’auteur est tout seul, et il ne remercie aucun collègue, aucun relecteur. Sur un résultat de cette ampleur, c’est un peu bizarre. Évidemment, le concept de génie solitaire qui résout tout seul un problème qui a échappé à des milliers de chercheurs est extrêmement romantique. Mais il est aussi extrêmement peu crédible.

Troisième point : les références bibliographiques. Il y a 12 références bibliographiques dans cet article. Dix d’entre elles sont des auto-références (l’auteur fait référence à des travaux personnels précédents). La première de la liste est un bouquin très classique, genre bouquin de cours sur le sujet. Là encore, c’est douteux.

Pour finir, l’article se termine par « Until now, since 2010.10.06, more than 52 millions of instances have been generated randomly, each of which has 100 vertices. Some instances contain a simple path while others (it is the majority in all the generated instances) do not. All the results show that our polynomial time algorithm can get the same answer as the backtracking algorithm does. No exception. », ce qui se traduit par « Jusqu’à présent, depuis le 6 juin 2010, nous avons généré aléatoirement plus de 52 millions d’instances sur 100 sommets chacunes. Certaines instances contiennent un chemin simple tandis que d’autres (la majorité des instances générées) non. Tous les résultats montrent que notre algorithme polynomial ont le même résultat que l’algorithme de backtracking. Aucune exception. ». Ça pourrait sembler être un argument en faveur de la preuve. Mais il y a plusieurs choses qui sont discutables sur cet argument. Déjà, il se peut que le générateur aléatoire d’instances soit biaisé, et se trouve louper les instances pour lesquelles ça ne marche pas. D’autre part, le nombre de sommets considéré est relativement bas. Si ça se trouve, ça plante pour 1000 sommets. Ou pour 101. Tertio, il se peut que les instances « difficiles » du problème soient rares. Ça fait partie des choses qu’on ne sait pas, d’ailleurs : si P ≠ NP, les instances d’un problème NP donné pour lesquelles c’est effectivement un facteur (c’est-à-dire qui n’ont pas de caractéristique permettant de résoudre l’instance par un algorithme rapide) sont-elles rares ou fréquentes ? Quatro, l’argument « ça fait un moment que je cherche et j’ai toujours pas trouvé de truc qui fait que ça marche pas »… j’ai essayé, hein, ben souvent les gens qui corrigent mes copies sont pas pour 😀

Bref, comme dit précédemment, c’est un peu des arguments fallacieux, tout ça, parce que ça serait facile de transformer n’importe quel papier « crédible » en papier « absolument pas crédible », et là j’aurai l’air très très bête. Je ne sais pas exactement ce que je veux dire, en fait. Dans un sens, ça me gène de recourir à ce genre d’argument pour décider que « ça sent pas bon, son truc », parce qu’il y a toujours le doute, dans un coin de neurone, du « oui, mais si les apparences étaient trompeuses ? ». D’un autre côté, comme dit Aaronson, il y a suffisamment de papiers sur le sujet pour que des heuristiques de crédibilité soient nécessaires. Quelque part, c’est peut-être à relier au processus de recrutement d’un candidat. Un candidat à un job doit souvent passer par des « formes obligées » qui démontrent sa crédibilité. Et il y a probablement un certain nombre de « faux négatifs » dans tout ce processus de formes obligées. On peut le déplorer. Et, dans le cas d’une preuve P = NP, un faux négatif serait… intéressant 😀

Mais dans le cas d’une preuve P = NP, je soupçonne qu’il faille redoubler d’attention à la crédibilité du papier. L’immense majorité de la communauté scientifique est raisonnablement convaincue que P ≠ NP. Du coup, arriver en affirmant l’inverse… ben ça part pas bien, déjà. Et si « le méta pue », il y a peu de chance que quiconque prenne la peine d’examiner le papier.

Et peut-être que demain je vais me prendre une grosse baffe dans la figure parce qu’un papier dont « le méta pue » va démontrer correctement un résultat que personne n’attend. Je crois que P ≠ NP. Et quand je dis « je crois », c’est vraiment exactement ça : une croyance, peut-être même une foi. N’empêche que j’adorerais avoir tort. Ça serait profondément drôle.. Si ça se trouve, on va trouver demain un algorithme pour SAT en n¹⁰⁰⁰⁰. Ben on sera bien avancés avec ça. Les années qui suivront seraient probablement super marrantes – parce que probablement on se tirerait tous la bourre pour faire descendre ce fichu 10000, et ça finirait probablement par arriver. Ça serait marrant.

Probabilités – partie 1

Publié le 11 mars 201310 février 2019 par Balise12 commentaires

This blog post has been translated to English here: Intro to probability theory – part 1

Pouf pouf. Donc, j’ai trois personnes qui ont répondu à mon petit sondage et je les remercie. Yoogx m’a réclamé des algos aléatoires, donc je vais faire des algos aléatoires, mais avant je vais faire un peu de probas, histoire d’être sûre que tout le monde parle de la même chose. Évidemment, pour ledit Yoogx, ça va probablement pas être super utile ce que je raconte, mais espérons qu’il n’y aura pas que lui que la question des algos aléatoires intéresse, et sinon il est encore temps de s’exprimer 😉

Bon, donc, les probas. Les probas, c’est un peu pénible, parce que c’est des trucs qu’on utilise relativement souvent dans la vie… j’ai envie de dire « quotidienne », ça serait peut-être un peu exagéré, et en même temps ça arrive a être étonnamment contre-intuitif quand ça s’y met. Ça, ou alors l’être humain est nul en probas, ce qui est possible aussi.

J’ai pas super envie de définir formellement le concept de probabilité (« étant donné un univers $\Omega$ , des événements blah…. » ouais, bon, vraiment pas envie), ce que je vais probablement regretter, mais on va essayer de rester sur les démos « avec les mains » (mais correctes, parce que bon). Et je vais espérer que ce que je raconte va rester suffisamment simple pour pouvoir me passer du formalisme en question. Sinon on verra 😛

Je suppose, pour éviter les petits malins, que je suis dans des conditions « correctes » : mon dé n’est pas pipé, ma pièce est une vraie pièce, etc.

On commence classique. Je lance une pièce, quelle est la probabilité qu’elle tombe sur le côté pile ? La réponse est 1/2 ; j’ai deux événements possibles (la pièce peut tomber côté pile ou côté face), et ils ont tous les deux la même probabilité de se produire. Idem si je lance un dé à six faces : la probabilité qu’il fasse un 4 est 1/6 ; j’ai six événements possibles qui ont tous la même probabilité de se produire. De manière générale, je vais me permettre de dire que si je fais une expérience (lancer un dé, lancer une pièce) qui a k résultats possibles, et que tous ces résultats possibles ont la même probabilité (« chance d’arriver »), alors la probabilité de chacun de ces résultats est 1/k.

Il se peut que tous les événements n’aient pas la même probabilité, mais il y a quelques règles immuables. Une probabilité est toujours comprise entre 0 et 1. Un événement qui n’arrive jamais a une probabilité 0 ; un événement qui arrive toujours a une probabilité 1. Si quelqu’un met dans mon porte-monnaie une pièce qui n’a que deux côté pile, si je la lance, elle tombe côté pile avec une probabilité 1 et côté face avec une probabilité 0. D’autre part, la somme de toutes les probabilités de tous les événements possibles de mon expérience est égale à 1. Dans le cas où j’ai k événements qui ont la même probabilité, ça fait effectivement k*1/k = 1. Si j’ai un dé qui a trois faces 1, 2 faces 2 et une face 3, la probabilité qu’il fasse 1 est 3/6 = 1/2, la probabilité qu’il fasse 2 est 2/6 = 1/3 et la probabilité qu’il fasse 3 est 1/6 ; la somme est 1/2 + 1/3 + 1/6 = 1.

Bon, maintenant, les trucs auxquels il faut faire un peu attention. Quelle est la probabilité que le dé (à six faces, normal) fasse 3 ou 5 ? Facile : la probabilité qu’il fasse 3, c’est 1/6, la probabilité qu’il fasse 5, c’est 1/6, 1/6+1/6 = 1/3. Ça, ça marche si les événements sont disjoints, c’est à dire si quand l’un est vrai, l’autre ne peut pas l’être : si j’ai fait un 5, alors je ne peux pas avoir fait un 3, et vice versa.

Ça ne marche pas si les événements peuvent se produire en même temps. Par exemple, je lance une pièce et un dé, et je m’intéresse à la probabilité que la pièce tombe sur pile, ou que le dé tombe sur 6. Je ne peux PAS dire que c’est égal à la probabilité que la pièce tombe sur pile (1/2), plus la probabilité que le dé tombe sur 6 (1/6), pour un total de 2/3. Une manière de voir ça, c’est de modifier un peu l’expérience pour voir que ça ne marche pas à tous les coups. Par exemple, la probabilité que le dé fasse 1, 2, 3 ou 4 est de 4/6 = 2/3. La probabilité que la pièce fasse pile est de 1/2. Ce n’est pas possible que la probabilité que l’un ou l’autre arrive fasse la somme de ces deux probabilités = 2/3 + 1/2 = 7/6… ce qui est supérieur à 1 ! (Et une probabilité est toujours inférieure ou égale à 1).

Un truc qui est toujours vrai, par contre, c’est que si j’ai deux événements A et B, alors

$\Pr(A \cup B) \leq \Pr(A) + \Pr(B)$

c’est à dire que la probabilité de l’union de deux événements (événement A ou événement B) est toujours inférieure à la somme de la probabilité des deux événements. On peut étendre ça à plusieurs événements : la probabilité de l’union de plusieurs événements est inférieure à la somme de la probabilité de tous les événements. Ça peut paraître tout con et pas très intéressant, mais en pratique c’est très utilisé. En anglais, ça s’appelle l’union bound (la « borne de l’union » ?), en français l’inégalité de Boole. Cette inégalité n’est pas toujours très utile. Dans le cas « mon dé fait 1, 2, 3 ou 4, ou ma pièce fait pile », elle borne la probabilité à 7/6… ce qu’on savait déjà, puisque 7/6 est plus grand que 1. Elle est déjà un peu plus utile pour borner la probabilité que le dé fasse 6 ou que la pièce tombe sur pile, on sait que cette probabilité est inférieure à 2/3. En pratique, dans le contexte des algorithmes aléatoires, elle est très utilisée : les probabilités qu’on considère sont toutes petites, et on peut en ajouter beaucoup avant que la borne n’ait plus de sens. Elle n’est pas toujours suffisante non plus, mais c’est un outil à garder précieusement.

Dans le cas qui nous intéresse ici, cependant, l’outil le plus utile c’est le principe d’inclusion-exclusion. Pour deux événements A et B, il s’énonce comme ça :

$\Pr(A \cup B) = \Pr(A) + \Pr(B) - \Pr(A \cap B)$

c’est-à-dire que la probabilité que l’événement A ou l’événement B arrive est égal à la somme des probabilités des deux événements, moins la probabilité que les deux événements arrivent en même temps. L’idée, c’est que si les deux événements peuvent arriver en même temps, on compte cette probabilité là « deux fois » si on fait la somme. Ça se voit sans doute mieux avec des patates (diagramme de Venn, on dit, quand on est distingué) :

Si je considère tout ce qui est contenu dans le hachuré vert, et tout ce qui est contenu dans le hachuré rose, je compte deux fois ce qui est hachuré vert et hachuré rose, donc je retire une fois ce qui est hachuré vert et hachuré rose pour retomber sur mes pattes.

Bon, évidemment, ça pose la question de savoir comment calculer la probabilité que deux événements arrivent. Il y a le cas facile, et le cas compliqué. Dans le cas facile, les événements sont dits indépendants : la probabilité de l’un n’a aucune influence sur la probabilité de l’autre. C’est une notion qui est à peu près claire (bien que pas forcément intuitive) si on considère des dés et des pièces, mais c’est une notion à laquelle il faut généralement faire super attention quand on veut l’appliquer. Prouver que deux événements sont indépendants peut s’avérer compliqué, et s’en sortir quand ils ne le sont pas… aussi.

Quand deux événements sont indépendants, on a

$\Pr(A \cap B) = \Pr(A) \times \Pr(B)$

c’est-à-dire que la probabilité que les deux événements arrivent est égale au produit de la probabilité des deux événements. Si je lance une pièce et un dé, le fait que la pièce tombe sur pile et le fait que le dé fasse 6 sont indépendants : l’un n’a aucune influence sur l’autre. La probabilité que les deux arrivent est donc 1/2 × 1/6 = 1/12. Remarquons que cette probabilité conjointe est plus petite que 1/2 et plus petite que 1/6. C’est « évident » au sens où une probabilité est inférieure à 1, et donc quand on multiplie deux probabilités entre elles le résultat est inférieur aux deux. Une autre manière de voir ça c’est que le fait que les deux événements indépendants se produisent, ben c’est moins probable que le fait que seulement l’un des deux se produise.

Pour des exemples d’événements qui ne sont pas indépendants, on peut par exemple considérer l’événement A « le dé fait 1 » et l’événement B « le dé fait un nombre impair ». Dans ce cas là, les deux événements ne sont pas indépendants, puisque si le dé fait 1, alors le dé fait un nombre impair ; et si le dé fait 2, alors il ne peut pas faire un nombre impair en même temps. Dans ce cas précis, l’événement A est inclus dans l’événement B, donc c’est facile : l’intersection des deux événements, c’est l’événement le plus petit : l’événement $A \cap B$ est égal à l’événement A. On peut faire des trucs plus subtils ; par exemple on peut définir pour l’événement A « le dé fait 1, 4 ou 6 » et garder l’événement B « le dé fait un nombre impair », auquel cas les deux événements ne sont pas non plus indépendants. La probabilité que A et B soient valides correspond exactement à la probabilité que le dé fasse 1 (parce que c’est le seul cas qui soit à la fois dans l’ensemble {1, 4, 6} et impair), c’est à dire 1/6 ; si on multiplie les probabilités de A (1/2) et de B (1/2) sans faire plus attention que ça, on a 1/4 et on s’est vautré.

Bon, et maintenant, une dernière pour la route : il me reste à parler de probabilités conditionnelles. Les probabilités conditionnelles, c’est justement une manière de gérer les dépendances entre des événements. On note les probabilités conditionnelles Pr(A | B), et on lit ça « probabilité de A sachant B », et on comprend ça comme « probabilité de A sachant que B arrive/est arrivé ». Si A et B sont indépendants, alors Pr(A | B) = Pr(A) – savoir que B se passe n’a aucune influence sur la probabilité de A. Pour le cas précédent, où A est l’événement « le dé fait 1 » et B est l’événement « le dé fait un nombre impair », on peut voir le « sachant B » comme une restriction de l’ensemble des événements possibles. Le dé a fait un nombre impair, on le sait ; avec la même probabilité il a donc fait 1, 3 ou 5, mais la probabilité, sachant qu’il ait fait un nombre impair, qu’il ait fait 2, 4 ou 6 est 0. Donc on a Pr(A | B) = 1/3.

Il y a une formule « générale » pour les probabilités conditionnelles :

$\Pr(A \mid B) = \frac{\Pr(A \cap B)}{\Pr(B)}$

On peut re-dériver, à partir de cette formule, le fait que si A et B sont indépendants, alors Pr(A | B) = Pr(A), parce qu’alors

$\Pr(A \mid B) = \frac{\Pr(A) \times \Pr(B)}{\Pr(B)} = \Pr(A)$

Elle est aussi très utilisée dans l’autre sens :

$\Pr(A \cap B) = \Pr(A \mid B) \times \Pr(B) = \Pr(B \mid A) \times \Pr(A)$

parce qu’il arrive qu’il soit plus facile de comprendre ce qu’il se passe dans le contexte des probabilités conditionnelles que dans le contexte de deux événements qui arrivent en même temps de façon non indépendante. Et il faudrait techniquement que je parle de la loi des probabilités totales ici, mais je crois que ça va allonger un peu trop un billet qui est déjà pas court, donc je ferai ça plus tard.

Dans le billet prochain, on parlera de variables aléatoires, parce que c’est pareil, ça va pas rentrer dans un billet de taille raisonnable d’en parler ici 🙂

Bon, je fais quoi maintenant ?

Publié le 4 mars 20139 novembre 2013 par Balise6 commentaires

Bon bon bon. Je commence à avoir fait un peu le tour de ce que je dont je voulais absolument parler. Pour récapituler un peu :

un article d’introduction à l’informatique théorique
quelques notions de complexité algorithmique, partie 1, et de complexité algorithmique, partie 2, pour lesquelles j’ai aussi eu besoin de parler de logarithmes
la question P est-il égal à NP, un petit détour par le problème SAT, et la notion de problèmes NP-complets
deux billets « méta » sur l’intuition mathématique et la compréhension mathématique (j’en ai un troisième de prévu à l’occasion sur la créativité, mais il infuse encore un peu)

Maintenant, qu’est-ce que vous voulez ? J’ai plusieurs pistes, mais c’est des pistes assez différentes, alors je sais pas trop 🙂 du coup, je me dis que je peux aussi vous demander votre avis. Dans l’ordre dans lequel ça me vient à l’idée :

Je peux faire un peu de théorie des graphes. Un truc que j’avais en tête était d’expliquer comment chercher un plus court chemin dans un graphe, par exemple.
Je peux continuer sur les problèmes NP-complets. Dans les trucs que j’ai en tête, expliquer la réduction pour prouver que la 3-colorabilité est NP-complète.
Je peux parler de SAT. Là j’ai deux trucs faisables : je peux parler des algorithmes pour 2-SAT (qui sont simples, choupis et polynomiaux) ou d’algorithmes pour 3-SAT (et plus) qui peuvent être aussi simples à expliquer, mais moins choupis et vachement moins polynomiaux. Je reste sur le côté théorique de la question, par contre, parce que j’ai pas la moindre idée de ce qui se fait côté pratique et que je vais dire des conneries.
Si je parle d’algos 3-SAT, je peux probablement étendre sur ce que je fais en ce moment ; ça risque d’être vachement poilu cependant.
Je peux causer géométrie algorithmique, aussi, la géométrie c’est cool. Je peux parler de triangulations et de Voronoï, par exemple.
On peut faire des probas, dans la série des trucs cools ; si je traite le point suivant je commencerai probablement par ça.
Je peux causer algorithmes aléatoires, à quoi ça sert, comment ça marche, tout ça.
Je peux causer de problèmes « classiques » difficiles et parler d’approximation (par exemple, je suis un voleur dans un musée, je cherche à remplir mon sac à dos avec des objets de taille et de valeur variées, comment je fais pour maximiser la valeur totale de ce que j’embarque pour que ça tienne dans mon sac à dos ?)

Heu, voilà, ce sont quelques suggestions. Si vous en avez d’autres, n’hésitez pas non plus ; je ne garantis rien parce qu’écrire sur un sujet que je ne connais pas prend nécessairement beaucoup, beaucoup plus de temps et que je croule pas sous le temps ces temps-ci ; mais il est toujours possible que j’aie oublié des trucs dans ce que je pourrais traiter sans trop de problème :)

Quant aux gentils lecteurs qui auraient des idées sur certaines questions qui compléteraient mes idées à moi, ya toujours moyen de négocier si ça vous dit de venir en parler ici 😉

Donc, qu’est-ce que vous voulez ? (Et il me serait agréable que vous répondiez à cette question et que vous ne me colliez pas un vent phénoménal, merciiiii 😉 ).

Problèmes NP-complets

Publié le 1 mars 20139 novembre 2013 par Balise5 commentaires

Dans un billet précédent, j’ai tenté d’expliquer avec brio (je vous laisse choisir le verbe qualifié par « avec brio ») le problème « P = NP ». J’y ai donné une définition de la classe NP, que je répète ici : NP est la classe des problèmes pour lesquels, pour chaque instance de type « oui », on peut me convaincre en temps polynomial que la réponse est « oui » en me fournissant une preuve que c’est effectivement le cas. Et en fin de billet, j’ai vaguement mentionné la notion de problème NP-complet.

La définition usuelle de problème NP-complet, c’est un problème qui est « dans NP » et « NP-difficile ». Je vais donc expliquer ce que veut dire NP-difficile 🙂 De façon informelle, c’est un problème qui est au moins aussi difficile que tous les problèmes de la classe NP. Une autre façon informelle de dire ça, c’est qu’il est aussi difficile qu’un autre problème NP-difficile. Le problème de cette définition, c’est qu’il faut bien commencer quelque part, et avoir un premier problème NP-difficile pour le comparer aux autres.

L’archétype des problèmes NP-difficiles (et donc NP-complets, parce que SAT est dans NP), c’est le problème SAT, dont j’ai parlé dans le billet précédent. C’est pas évident, a priori, que SAT est NP-difficile. Mais on peut montrer que même 3-SAT est NP-difficile : 3-SAT représente les instances de SAT où toutes les clauses ont exactement trois littéraux ((Les avis diffèrent sur la terminologie exacte. De nombreux auteurs définissent 3-SAT comme les instances de SAT où toutes les clauses ont au plus deux littéraux. J’appelle ça (sur la suggestion de mon prof de SAT) <=3-SAT. Dans le cas présent ça m’arrange de définir sur exactement 3 littéraux, donc je fais ça, OK ?)). Je ne vais en pas expliquer la preuve, parce que ça impliquerait que je passe pas mal de temps à expliquer des choses que j’ai pas fondamentalement envie d’expliquer. Pour les gens intéressés par la question, ça a été démontré en 1971 et c’est connu sous le nom de Théorème de Cook-Levin.

Maintenant qu’on en a un, on peut en trouver d’autres par réduction. On réduit un problème NP-difficile (par exemple SAT) à un autre problème qu’on veut prouver NP-difficile, appelons le A. Pour faire ça, on démontre que si on peut résoudre A efficacement, c’est-à-dire en temps polynomial, alors on peut résoudre SAT efficacement.

L’idée générale de ce genre de preuve, c’est qu’on prend une instance quelconque du problème NP-difficile, et on la transforme, en temps polynomial, en instance du problème A qui permette de conclure sur l’instance originale. Maintenant, supposons qu’on sache résoudre le problème A (c’est-à-dire n’importe quelle instance du problème A) en temps polynomial. Alors on peut prendre n’importe quelle instance de SAT, la transformer en une instance du problème A, résoudre l’instance du problème A, et conclure. La transformation se fait en temps polynomial, la résolution de A se fait en temps polynomial, la somme des deux est polynomiale, donc on sait résoudre n’importe quelle instance de SAT en temps polynomial, donc on sait résoudre SAT en temps polynomial. Facile.

Les problèmes NP-complets sont donc, en quelque sorte, « équivalents » en terme de complexité : si on sait en résoudre un en temps polynomial, alors on peut résoudre tous les autres en temps polynomial aussi, et on peut résoudre tous les problèmes de NP en temps polynomial (puisqu’ils sont aussi difficiles que tous les problèmes de la classe NP). Donc, si on trouve un moyen de résoudre en temps polynomial toutes les instances d’un problème NP-complet… on a démontré que P = NP. Et gagné un million de dollars. Et surpris beaucoup, beaucoup de monde.

Il y a toute une série de problèmes pour lesquels on sait qu’ils sont NP-difficiles, ou NP-complets si en plus ils sont dans NP. Il y a des gens qui s’intéressent à des problèmes… exotiques, dirons-nous ; je vais juste laisser quelques liens pour les gens intéressés et que ça fera rigoler :

The Hardness of the Lemmings Game, or Oh no, more NP-Completeness Proofs – un papier qui parle du caractère NP-complet de Lemmings
A Survey of NP-Complete Puzzles – un papier qui recense tout un tas de résultats sur le sujet
Gaming is a hard job, but someone has to do it! – qui parle de jeux vidéo, dont Boulder Dash, Doom et Lode Runner. Et Puzzle Bobble.

Passé cet interlude amusant, je vais donner un exemple de réduction pour prouver que le problème CLIQUE est NP-complet. C’est probablement l’exemple bateau que tout le monde donne quand il parle de ce genre de chose, mais il doit y avoir une raison à ça (la raison en est que le problème est raisonnablement facile à décrire et que la réduction est relativement simple par rapport à ce qu’on peut voir ailleurs). Le truc que j’explique ici est largement repompé du CLRS, c’est-à-dire le Cormen, Leiserson, Rivest & Stein, c’est-à-dire Introduction to Algorithms, traduit en français sous le nom Algorithmique (je ne sais pas ce que vaut cette traduction) – c’est le bouquin de référence de BEAUCOUP de cours d’algorithmique.

Donc, le problème CLIQUE est le suivant : étant donné un graphe (un ensemble de sommets et d’arcs) G, contient-il une clique de taille k ? Une clique de taille k, c’est un ensemble de k sommets qui sont tous reliés les uns aux autres. Par exemple (vous m’excuserez, je recycle mes figures), ce machin-là est est une clique de taille 8. Notons au passage qu’il contient également une clique de taille 1 (un seul sommet), 2 (un arc), 3 (un triangle), 4, 5, 6 et 7, puisqu’on peut trouver des ensembles de sommets de cette taille qui sont tous reliés les uns aux autres.

On veut réduire 3-SAT à ce problème ; comme 3-SAT est NP-difficile, CLIQUE est NP-difficile aussi. CLIQUE est dans NP, parce que si je donne k sommets, c’est facile de vérifier que ces k sommets sont effectivement tous reliés les uns aux autres. Donc, si CLIQUE est NP-difficile, CLIQUE est NP-complet.

Pour attaquer ma réduction, je prends une formule 3-SAT. Je prends une formule 3-SAT CNF (j’ai expliqué ce que ça veut dire dans mon article sur SAT), c’est-à-dire une formule qui a cette tête là :

$(x_1 \vee x_2 \vee x_3) \wedge (\bar x_2 \vee x_4 \vee \bar x_5) \wedge (x_1 \vee \bar x_2 \vee \bar x_3) \wedge ...$

c’est-à-dire un ensemble de m clauses composées d’au plus 3 littéraux reliés par des OU, et les clauses étant reliées par des ET.

À partir de là, on crée un graphe contenant 3*m sommets. Chacun de ces sommets correspond à un littéral de la formule, éventuellement dupliqué. Pour visualiser les choses plus facilement, ça peut peut-être aider de grouper les sommets en groupes de trois. Dans l’exemple de la formule ci-dessus, ça donne les sommets suivants :

$x_1, x_2, x_3~;\bar x_2, x_4, \bar x_5~; x_1, \bar x_2, \bar x_3$

Ensuite, on ajoute des arcs partout. Enfin, presque partout. On n’ajoute pas d’arcs dans les « groupes » correspondant aux clauses. On n’ajoute pas non plus d’arcs entre les littéraux qui ne sont pas « compatibles », c’est-à-dire l’inverse l’un de l’autre. Si j’ai deux littéraux $x_1$ et $\bar x_1$ , je ne crée pas d’arc entre eux. Pour ma mini-formule au-dessus, voilà ce que donne le graphe en question :

et voilà les arcs qui ne sont PAS dans le graphe précédent :

Et maintenant qu’on a ce graphe là, l’idée, c’est que la formule SAT peut être satisfaite si et seulement si le graphe (le premier) a une clique de taille m (m étant le nombre de clauses de la formule SAT). J’ai donc deux choses à prouver :

si la formule peut être satisfaite, alors le graphe a une clique de taille m
si le graphe a une clique de taille m, la formule peut être satisfaite.

On va commencer par le premier point. Supposons que la formule puisse être satisfaite. Donc, on peut affecter une valeur à toutes les variables de sorte que la formule soit satisfaite. Par conséquent, toutes les clauses peuvent être satisfaites par cette affectation. Donc, dans chaque clause, il existe un littéral qui a pour valeur 1 (le littéral « positif », par exemple $x_1$ si la variable a la valeur 1, le littéral « négatif », par exemple $\bar x_1$ si la variable a la valeur 0). On considère, dans chaque « groupe » de sommets du graphe défini précédemment, le sommet correspondant à ce littéral (si plusieurs littéraux ont la valeur 1, on en prend un au pif). Comme on prend un sommet par groupe, et qu’on a m groupes, on arrive à m sommets. On veut maintenant montrer qu’il y a un arc entre toutes les paires de sommets de cet ensemble de sommets. Or, les deux raisons pour lesquelles on pourrait ne pas en avoir, c’est soit que les sommets sont dans le même groupe, soit qu’ils sont incompatibles. On ne peut pas avoir choisi deux sommets dans le même groupe, puisqu’on en a choisi exactement un par groupe. Et on ne peut pas avoir choisi deux sommets incompatibles, parce qu’ils correspondraient à des littéraux $x_i$ et $\bar x_i$ , qu’on n’a choisi que des littéraux qui ont la valeur 1, et qu’on ne peut pas avoir en même temps $x_i = 1$ et $\bar x_i = 1$ . Donc, toutes les paires dans les m sommets sont connectées entre elles, donc on a une clique de taille m, ce qu’on voulait démontrer.

Donc, on peut passer au deuxième point : si le graphe a une clique de taille m, la formule peut être satisfaite. Supposons, donc, que le graphe ait une clique de taille m. Comme les sommets d’un même groupe ne sont pas connectés entre eux, les sommets sont forcément dans des groupes différents. Si on a une clique de taille m, ça veut dire qu’on a un sommet dans chaque groupe de sommets. On peut donner à tous ces sommets la valeur 1. On ne peut pas avoir de clique qui contienne des sommets $x_i$ et $\bar x_i$ , puisqu’il n’y a pas d’arc entre deux sommets de ce type et que, par définition d’une clique, il faut que tous les arcs soient présents. Donc, si une clique de taille m existe, ça veut dire qu’on a trouvé un littéral par clause qui peut valoir 1, et que tous ces littéraux sont compatibles entre eux. Et donc qu’on peut satisfaire la formule correspondant au graphe, ce qu’on voulait démontrer aussi.

Donc, si on peut résoudre CLIQUE en temps polynomial, alors on peut résoudre SAT en temps polynomial ; SAT étant NP-difficile, CLIQUE l’est aussi, et donc CLIQUE est NP-complet, ce qui termine la preuve.

Le caractère NP-complet d’un problème est, quelque part, une « preuve » de la difficulté du problème en question, mais il faut atténuer ça largement. Déjà, ça ne présume en rien de la difficulté d’une instance donnée du problème. Ça ne présume en rien de la difficulté sur une certaine classe d’instances non plus. J’explique. Dire que CLIQUE est difficile, ça ne veut pas dire que, par exemple, décider si un triangle (qui est une clique de taille 3) est dans un graphe, même un gros graphe, est difficile. Parce que je peux prendre tous les ensembles de trois sommets, regarder s’ils forment un triangle, et conclure. Les ensembles de trois sommets, il y en a à peu près n³ dans un graphe à n sommets (plus exactement, il y en a n(n-1)(n-2)/6, mais, bon, à peu près n³), du coup je peux décider ça en temps polynomial (je fais n³ opérations qui vont pas prendre des plombes, c’est-à-dire vérifier si trois arcs donnés sont effectivement dans le graphe). Du coup, je peux décider 3-CLIQUE en temps polynomial. Bon, c’est pas pour ça que je vais être millionnaire, hein. Parce que le problème CLIQUE, il se limite pas à 3. Cela dit, si je veux, je peux aussi décider 1000-CLIQUE (clique de taille 1000) en temps polynomial. Bon, c’est un polynôme de degré 1000, mais on s’en fout 🙂

Par contre, dans le cas général, je ne peux pas décider si un graphe sur n sommets contient une clique de n/2 sommets, ou n/10000 sommets, ou même log n sommets en temps polynomial avec cet algorithme qui regarde tous les groupes de taille k (donc ici k = n/2, n/10000 ou log n) et qui regarde les arcs dans le groupe, parce que ça impliquerait de faire respectivement à peu près $n^{n/2}, n^{n/10000}$ et $n^{\log n}$ opérations, et que dans tous les cas c’est pas polynomial. Et, de manière générale, personne ne sait si c’est possible de faire ça en temps polynomial, puisque CLIQUE est NP-complet et qu’on ne sait pas si P est égal à NP. Beaucoup de gens supposent que non, mais personne ne sait.

Même là, ça ne présume en rien de la difficulté d’une instance donnée d’un problème. Supposons qu’on me file un graphe qui se trouve contenir n(n-1)/2 arcs pour n sommets. Alors je peux décider, sans trop de problème, que oui, ce graphe contient une clique de taille n/2, n/10000 et log n. Parce qu’un graphe de n(n-1)/2 arcs pour n sommets, ben il contient tous les arcs possibles pour le graphe : c’est un graphe complet (une clique sur n sommets), et comme une clique sur k sommets est un sous-graphe d’une clique sur n sommets… ben c’est pas bien difficile de répondre à la question. Idem si on me file un graphe avec 0 arcs et n sommets, je vais pas avoir beaucoup de mal à répondre que non, il ne contient pas de clique de taille n/2.

Dans le cas de SAT, on n’a aucun problème à résoudre les instances de 2-SAT (où toutes les clauses contiennent deux littéraux) en temps polynomial (et même linéaire). Il y a aussi des instances de SAT qui sont « faciles », par exemple celles où il y a peu de dépendances entre les clauses : on sait qu’on peut les résoudre, et on sait même comment (et, pour les gens intéressés, par « peu de dépendances », j’entends « qui tombent dans le cas du Lovász local lemma, dont l’application à SAT n’est pas évidente d’après la définition de la Wikipedia, mais qui devrait être plus claire ici).

De manière générale, il peut même être non trivial de créer des instances de problèmes NP-complets qu’on ne sait pas résoudre en temps polynomial. Notons au passage que c’est pas facile de prouver qu’on ne sait pas résoudre une instance donnée en temps polynomial. On peut exhiber des instances de problèmes qui sont difficiles (i.e. exponentielles) pour un algorithme donné, et triviales pour d’autres algorithmes…

Et c’est un peu ce qui se passe en pratique : on a des instances de problèmes pour lesquels on sait que le cas général est NP-complet (ou pire), et qu’on résout pourtant tous les jours en pratique. Une des raisons peut être que le problème est « petit » (c’est pas un drame de coller un algorithme exponentiel sur un problème de taille 4, quoi), mais ça peut aussi être parce que le problème fait partie d’une sous-classe d’instances sur laquelle le problème est facile. Donc, conclure qu’une instance de problème est difficile parce que le problème général l’est et abandonner (parce qu’on saura pas faire), c’est pas forcément une bonne idée, parce qu’il se peut qu’on n’ait pas considéré qu’on se trouve dans une restriction facile du problème !

Bref, comme d’habitude, « c’est pas aussi simple que ça ». En ce moment, je fais de la théorie, et du coup je m’intéresse plutôt aux problèmes eux-mêmes plutôt qu’à des instances données. Mais c’est parfois salutaire de se souvenir que des trucs « difficiles en théorie » peuvent s’avérer « faciles en pratique », ça change des trucs faciles en théorie qu’on sait pas faire en pratique… 🙂

Le problème SAT

Publié le 25 février 20139 novembre 2013 par Balise15 commentaires

Je vais expliquer un peu ce qu’est le problème SAT, parce que j’aurai l’occasion d’en reparler plus en détail bientôt (pour une certaine définition de bientôt dépendant de ma charge scolaire 🙂 ). C’est aussi une des briques fondamentales liées à la question « P = NP » ; j’avais commencé à écrire ce billet dans un prochain billet à propos de problèmes NP-complets, mais je crois que je peux faire un billet complet sur le sujet, ça m’évitera d’avoir la tentation de « faire vite ». L’autre raison pour laquelle je veux pas faire vite, c’est que je fais en ce moment un « projet de semestre » sur un sujet très très très voisin, et comme j’ai aussi l’intention de faire un billet sur ce que je fais plus précisément, ben ça ça sera fait.

SAT est une abréviation pour « boolean satisfiability problem », ou en français « problème de satisfaisabilité booléenne ». L’idée, c’est qu’on a une formule booléenne, ou formule SAT, et qu’on cherche à décider si on peut la résoudre ou pas.

Une formule SAT peut, par exemple, avoir cette tête là :

$(x \vee y \vee z) \wedge (\bar x \vee \bar y) \wedge (\bar x \vee y \vee z)$

Il y a plusieurs éléments dans ce machin. Le premier élément, ce sont les variables – ici, x, y, z. On peut les voir comme les « inconnues » d’une équation : on veut ici savoir si on peut trouver des valeurs pour x, y et z. En plus de ça, on est dans un univers un peu bizarre, l’univers booléen : x, y et z ne peuvent prendre que la valeur 0 ou la valeur 1.

Après, il y a des symboles bizarres. $\vee$ , ça veut dire « ou », et $\wedge$ , ça veut dire « et ». Les petites barres au-dessus de certaines lettres indiquent un négation. Les symboles se lisent comme ça :

$\begin{array}{|c|c||c|c|c|c|} \hline x & y & \bar x &\bar y & x \vee y & x \wedge y \\ \hline 0 & 0 & 1 & 1 & 0 & 0 \\ \hline 0 & 1 & 1 & 0 & 1 & 0 \\ \hline 1 & 0 & 0 & 1 & 1 & 0 \\ \hline 1 & 1 & 0 & 0 & 1 & 1 \\ \hline \end{array}$

Ou, si j’écris ça en toutes lettres :

si x = 1, alors $\bar x = 0$ , sinon $\bar x = 1$ ( $\bar x$ prend la valeur inverse de x)
si x = 1, alors $x \vee y = 1$  ; si y = 1 alors $x \vee y = 1$  ; si x = 0 et y = 0, alors $x \vee y = 0$ (« x OU y vaut 1 »). Il faut préciser que quand on dit « ou » dans ce contexte, ce n’est pas dans le même sens que « fromage ou dessert » : si on prend du fromage et du dessert, alors on prend du fromage ou du dessert (puisqu’on prend au moins l’un des deux).
si x = 1 et y = 1, alors $x \wedge y = 1$ , sinon $x \wedge y = 0$ (« x ET y valent tous les deux 1 »).

On peut combiner tous ces machins de la manière qu’on veut pour obtenir des formules booléennes. On s’intéresse en particulier aux formules du type que j’ai donné précédemment, qui sont appelées des formules « CNF » (pour « conjunctive normal form »). Ce type de formule est défini comme un ensemble de clauses, toutes reliées entre elles par des symboles $\wedge$ (« et »). Une clause se compose d’un ou plusieurs littéraux (un littéral, des littéraux), qui sont soit une variable (par exemple x), soit sa négation (par exemple $bar x$ ) tous reliés entre eux par des symboles $\vee$ (« ou »). On veut donc que toutes les clauses aient comme valeur 1 (parce qu’on veut que la première ET la deuxième ET la troisième ET toutes les suivantes aient la valeur 1). Et le fait que chaque clause ait la valeur 1, ça se traduit par le fait qu’au moins un des littéraux de la formule ait la valeur 1 (parce qu’on veut que le premier littéral OU le deuxième OU le troisième OU… ait la valeur 1). Même remarque que précédemment, il peut arriver que tous les littéraux aient la valeur 1, ça renvoie quand même toujours 1.

La question posée par une instance de SAT, c’est « est-ce que je peux trouver des valeurs pour toutes les variables de manière à ce que la formule complète ait pour valeur 1 ? ».

Reprenons l’exemple précédent, et nommons la formule F:

$F = (x \vee y \vee z) \wedge (\bar x \vee \bar y) \wedge (\bar x \vee y \vee z)$

Si je veux regarder s’il existe des valeurs pour x, y et z qui font que la formule F vaut 1 (c’est-à-dire pour que la formule soit satisfaite), je peux toutes les énumérer et regarder ce qu’il se passe.

$\begin{array}{|c|c|c||c|c|c||c|} \hline x & y & z & x \vee y \vee z & \bar x \vee \bar y & \bar x \vee y \vee z & F \\ \hline 0 & 0 & 0 & 0 & 1 & 1 & 0 \\ \hline 0 & 0 & 1 & 1 & 1 & 1 & 1 \\ \hline 0 & 1 & 0 & 1 & 1 & 1 & 1\\ \hline 0 & 1 & 1 & 1 & 1 & 1 & 1\\ \hline 1 & 0 & 0 & 1 & 1 & 0 & 0 \\ \hline 1 & 0 & 1 & 1 & 1 & 1 & 1 \\ \hline 1 & 1 & 0 & 1 & 0 & 1 & 0\\ \hline 1 & 1 & 1 & 1 & 0 & 1 & 0\\ \hline \end{array}$

Mon petit tableau répond à la question « est-ce qu’il existe des valeurs pour x, y et z de sorte à ce que la formule F vaille 1 » (la réponse est oui), et il va même plus loin en donnant lesdites valeurs (par exemple, x = 1, y = 0, z = 1 sont des valeurs valides pour satisfaire la formule).

Le problème, c’est que c’est pas vraiment gérable dès qu’on commence à avoir beaucoup de variables. La raison, c’est que pour chaque variable, il faut que je regarde ce qu’il se passe pour sa valeur 0 et pour sa valeur 1. Donc j’ai deux choix pour la première variable ; deux choix pour la deuxième variable ; deux choix pour la troisième variable, etc. Les choix en question se multiplient : on voit ça dans le tableau au-dessus, il faut que je fasse une ligne pour toutes les combinaisons possibles de valeurs de variables. Donc, pour 3 variables, 2*2*2 = 2³ = 8 lignes. Pour 5 variables, on est déjà à 2*2*2*2*2 = 2⁵ = 32 lignes, et ça commence à être relou à faire à la main. Pour 20 variables, on est à 2²⁰ = 1.048.576 lignes, et ça commence à ne pas être vraiment instantané à calculer. Et ça augmente de plus en plus vite : les joies de la fonction puissance.

Pour ceux qui ont suivi les explications précédentes, ce n’est PAS un algorithme en temps polynomial ; c’est un algorithme en temps exponentiel. D’autant plus que je ne considère là que l’énumération de tous les cas et que je ne regarde même pas combien de temps il me faut pour conclure dans chacun des cas.

Du point de vue « classe de complexité », SAT fait partie des problèmes de la classe NP. Si on me donne une formule et des valeurs pour toutes les variables de la formule, je peux vérifier efficacement que, effectivement, ça marche : je peux vérifier qu’une formule peut être satisfaite si on m’en fournit la preuve.

Par contre, on ne sait pas s’il fait partie des problèmes de la classe P : on ne sait pas s’il existe un algorithme polynomial permettant de décider si, oui ou non, une formule peut être satisfaite ou non. On ne sait pas non plus s’il est en dehors des problèmes de la classe P : on ne sait pas s’il faut nécessairement un algorithme « plus puissant » qu’un algorithme polynomial pour le résoudre. Et répondre à cette question (et le prouver correctement) permettrait de répondre à la question « est-ce que P = NP ? » – mais pour ça, il faut que je parle de problèmes NP-complets, et je ferai ça dans le prochain billet 🙂

EDIT : bon, je re-précise un ou deux trucs, parce que tripa a pas COMPLÈTEMENT tort dans les commentaires. Quand je dis « on ne sait pas si », je veux parler du cas général, c’est-à-dire de n’importe quelle formule SAT. Après, il y a des cas où c’est « facile », c’est-à-dire qu’on peut conclure très vite. C’est par exemple le cas si on se restreint à des clauses avec deux littéraux (2-SAT) : dans ce cas précis, il y a un algorithme qui permet de conclure en temps linéaire (c’est-à-dire, en gros, qu’on lit la formule, et qu’on sait.) La difficulté intrinsèque du problème général ne donne pas vraiment d’indication sur les instances individuelles. C’est plutôt un point que je traiterai dans le billet suivant, parce que c’est aussi important de s’en souvenir, mais, bon. Tout ça pour dire que SAT c’est dur, mais qu’il y a des instances du problème qui sont faciles, et qu’il faut éventuellement se poser les bonnes questions avant de conclure qu’on n’a aucune chance de résoudre une formule donnée 🙂

Le problème « P est-il égal à NP ? »

Publié le 15 février 20139 novembre 2013 par Balise21 commentaires

Bon, je crois que j’ai tout ce qu’il me faut maintenant que j’ai parlé un petit peu de complexité (partie 1 et partie 2) pour attaquer un morceau sympa, qui est d’expliquer ce qu’il y a derrière la question « P est-il égal à NP ? », que je vais abréger par « P = NP » (de façon assez ironique, on verra pourquoi plus tard). C’est vendredi, vous aurez le week-end pour lire (et peut-être un peu plus parce que je retourne en cours lundi 😉 ).

Le problème P = NP est un des problèmes ouverts (c’est-à-dire non résolu) les plus célèbres, sinon le plus célèbre. Il fait d’ailleurs partie des problèmes du prix du millénaire, une série de 7 problèmes énoncés en 2000 et dont la résolution correcte permettrait à son auteur de toucher un million de dollars. Un seul de ces 7 problèmes a été résolu, la conjecture de Poincaré ; Grigori Perelman l’a démontrée, ce qui lui a valu la médaille Fields (c’est l’équivalent du Nobel pour les maths) et, donc, le million de dollars en question ; il a refusé les deux.

Bon, assez de contexte, maintenant parlons de la bête. P et NP sont ce qu’on appelle des « classes de complexité ». Les classes de complexité sont des ensembles de problèmes qui ont des propriétés communes. L’idée, c’est de prendre des problèmes (par exemple : « est-ce que je peux aller d’un point A à un point B sur mon graphe en moins de 15 étapes ? ») et de les ranger dans des petites cases en fonction de leurs propriétés, en particulier de leur complexité en temps (le temps qu’il faut pour les résoudre) et en espace (la quantité de mémoire qu’il faut pour les résoudre). On s’intéresse ici à la complexité « dans le pire des cas ».

J’ai expliqué dans les billets sur la complexité algorithmique ce que ça voulait dire pour un algorithme de s’exécuter dans un temps donné. Dire qu’un problème se résout en un temps donné, c’est dire qu’on sait le résoudre dans ce temps, c’est-à-dire qu’on a un algorithme qui s’exécute dans ce temps et qui renvoie la bonne solution. Pour reprendre les exemples précédents, on a vu qu’on pouvait trier un ensemble d’éléments (livres… ou autres) en temps n² et en temps n log n. Il se trouve que, dans les modèles de calcul classiques, on ne peut pas faire « mieux » que ce n log n (c’est prouvé). On dit que la complexité du tri est n log n, et on peut dire qu’on peut trier des éléments en temps polynomial.

Un algorithme en temps polynomial est un algorithme qui se termine en un nombre d’étapes inférieur à $n^k$ , avec n représentant la taille de l’entrée, et k représentant un nombre quelconque (y compris de très grands nombres, tant qu’ils ne dépendent pas de n lui-même). Le nom vient du fait que les fonctions de type $x \mapsto x$ , $x \mapsto x^2$ , $x \mapsto x^{10} + 15x^5$ et $x \mapsto x^k$ s’appellent des fonctions polynomiales. Comme je peux trier des éléments en temps n² (et même n log n, ce qui est « mieux »), le tri est résolu en temps polynomial. Ça marcherait aussi si je pouvais trier des éléments en temps n⁴⁷⁹, ça serait aussi polynomial. L’énorme avantage des polynômes, c’est que ça se combine vachement bien. Si je fais deux opérations polynomiales, je reste en temps polynomial. Si je fais un nombre polynomial d’opérations polynomiales, je reste en temps polynomial. Mon polynôme « grossit » (il passe par exemple de n² à n⁵), mais il reste un polynôme.

Bon, et là il va falloir que j’explique la différence entre problème et instance du problème, sinon je vais dire des bêtises (et j’aime pas dire des bêtises). En gros, un problème regroupe toutes les instances d’un problème. Si je dis « je veux trier ma bibliothèque », c’est une instance du problème « je veux trier une bibliothèque quelconque ». Si je m’intéresse au plus court chemin entre deux points sur un graphe donné (par exemple la carte du métro), c’est une instance du problème « plus court chemin dans un graphe », où on considère tous les graphes arbitraires de taille également arbitraire. Le problème est le « concept général », l’instance est « un exemple concret du problème général ».

La classe de complexité P regroupe tous les problèmes dits « de décision » qu’on peut résoudre en temps polynomial. Un problème de décision, c’est un problème qui appelle une réponse de type oui/non. Ça peut paraître une restriction énorme ; en pratique, pas tant que ça. Plutôt que de demander le « plus court chemin », on peut par exemple demander s’il existe « un chemin de distance inférieur à X », et faire varier X jusqu’à trouver le X « limite ». On peut faire ça avec un nombre de requêtes polynomial, donc, si on peut résoudre le problème de décision en temps polynomial, on peut aussi résoudre le problème « numérique » en temps polynomial (Je simplifie salement ici, je crois que ça ne serait pas vrai en général et qu’il me faut des conditions supplémentaires pour que ça marche.) Et une instance de ce problème décisionnel de taille de chemins, ça peut par exemple être « considérant la carte du métro parisien, existe-t-il un chemin allant le La Motte Piquet Grenelle à Belleville en moins de 20 stations, sans prendre en compte les correspondances » (la réponse est oui) ou « en moins de 10 stations » (j’ai pas vérifié complètement, mais je crois que la réponse est non).

Un autre « type » de problème de décision est celui qui regroupe les problèmes de colorabilité de graphes. J’aime bien ce genre d’exemple parce que je peux faire des petits dessins et c’est, je crois, facile à expliquer 🙂 (Bon, c’est pas très daltonien-friendly par contre. Si ya des daltoniens, râlez, je referai les figures avec des numéros pour les couleurs, mais là j’ai la flemme.) On prend un graphe, c’est-à-dire un ensemble de sommets reliés par des arcs, et on veut colorier les sommets de façon à ce que deux sommets n’aient pas la même couleur s’ils sont reliés par un arc. Les questions de colorabilité sont des questions de type « est-ce que je peux colorer mon graphe avec 2, 3, 5, 12 couleurs ». Le problème « non-décisionnel » est celui qui demande quel est le nombre minimal de couleurs nécessaires pour colorer le graphe avec la contrainte exprimée ci-dessus.

Bon, quelques exemples – des instances du problème, donc 🙂

Un graphe « triangle » (trois sommets reliés par trois arcs) ne peut pas être coloré avec seulement deux couleurs, il m’en faut 3 :

Par contre, un graphe « carré » (trois sommets reliés en carré par quatre arcs) peut être coloré avec deux couleurs seulement :

Je peux avoir des graphes avec un nombre de sommets (et d’arcs) très élevé qui peuvent être colorés avec deux couleurs seulement, pour autant qu’ils suivent ce genre de structure :

Et je peux avoir des graphes qui demandent un grand nombre de couleurs – une par sommet ! – si tous les sommets sont reliés les uns aux autres, comme sur celui-ci :

Bon, et c’est là que ça devient intéressant (à mon avis). On sait répondre en temps polynomial à la question « est-ce que ce graphe est colorable avec deux couleurs ? » pour n’importe quel graphe (le « polynomial » ici est en fonction du nombre de sommets du graphe). Pour décider ça, on commence par colorer un sommet, n’importe lequel, du graphe, en bleu. On colorie tous ses voisins, c’est-à-dire tous les sommets qui lui sont reliés par un arc, en rouge (parce que vu que le premier est bleu, tous ses voisins doivent être rouges, sinon on contredit la contrainte qu’on a définie). On essaye de colorier tous les voisins des sommets rouges en bleu, et ainsi de suite. Si on arrive à tout colorier avec cet algorithme, le graphe peut être coloré avec deux couleurs (parce qu’on vient précisément de le faire !). Sinon, c’est qu’un sommet a une contrainte qui l’oblige à être rouge (un voisin bleu) et une contrainte qui l’oblige à être bleu (un voisin rouge). C’est pas complètement évident de voir que ça veut dire que le graphe ne peut pas être coloré avec deux couleurs, mais il se trouve que c’est le cas. L’algorithme se contente, en gros, de parcourir tous les sommets dans un certain ordre et de colorer au fur et à mesure ; on ne visite les sommets qu’une fois ; on vérifie au pire tous les autres sommets (s’ils sont tous connectés) avant de colorier ; si pour chaque sommet je fais au pire une comparaison pour tous les autres sommets et que j’ai n sommets, je pense qu’on peut se convaincre, sans rentrer dans les détails, qu’on fait au pire n*(n-1) opérations, et que l’algorithme est polynomial. (Je ne rentre pas dans les détails ici parce que ça dériverait vilement du sujet ; mais si vous voulez plus de détails, râlez en commentaire et j’essaierai de développer plus).

Par contre, pour la question « est-ce que le graphe est colorable avec trois couleurs ? », ben… on n’a pas encore trouvé d’algorithme en temps polynomial pour répondre à la question pour n’importe quelle instance du problème, c’est à dire pour n’importe quel graphe. Et, pour des raisons que je vais expliquer, genre, dans un prochain billet, si vous trouvez un algorithme (correct !) qui permette de répondre à la question en temps polynomial, il y a de bonnes chances que ça vous fasse gagner une certaine célébrité, possiblement une certaine haine de la part des gens qui font de la cryptographie, et un million de dollars. Intéressant, non ?

L’autre truc intéressant, c’est que si je vous donne un graphe déjà coloré, et que je vous dit « j’ai coloré ce graphe avec 3 couleurs », vous pouvez vérifier, en temps polynomial aussi, que je n’essaie pas de vous enfumer. Il suffit de regarder tous les arcs l’un après l’autre et de vérifier que les deux sommets de l’arc sont colorés avec des couleurs différentes. Facile. Et polynomial.

Ce genre de problème « facilement vérifiable » constitue la classe de complexité NP. Sans partir dans la définition formelle, voilà une idée du machin : un problème décisionnel fait partie de la classe NP si, pour toutes les instances auxquelles je peux répondre « oui », j’ai une « preuve » qui me permet de le vérifier en temps polynomial. Cette « preuve » me permet, en quelque sorte, de répondre à l’interjection « même pas cap ! », ce à quoi je réponds, dans le cas de la colorabilité, par « ben si, tu vois, si je colore comme ça, ça marche, ça prouve bien que je peux le faire avec trois couleurs ». Notez ici que je ne dis rien sur ce qu’il se passe quand je dois répondre « non » à l’instance. Une des raisons, c’est que c’est souvent « plus difficile » de prouver qu’un truc n’est pas faisable que de prouver qu’il l’est. Je peux prouver qu’un truc est faisable en le faisant ; si j’arrive pas à faire un truc, tout ce que ça prouve c’est que j’arrive pas à le faire.

Donc, pour récapituler :

P est la classe des problèmes auxquels j’arrive à répondre par « oui » ou par « non » en temps polynomial
NP est la classe des problèmes pour lesquels, pour chaque instance de type « oui », on peut me convaincre en temps polynomial que la réponse est « oui » en me fournissant une preuve que c’est effectivement le cas.

La remarque suivante, c’est que les problèmes qui sont dans P sont aussi dans NP, parce que si j’arrive à répondre moi-même à la question « oui » ou « non » en temps polynomial, je peux être convaincue en temps polynomial que la réponse est « oui » si c’est effectivement le cas (il me suffit d’exécuter l’algorithme polynomial qui me répond « oui » ou « non », et de vérifier qu’il répond « oui »).

La question à, littéralement, un million de dollars, c’est de savoir si tous les problèmes qui sont dans NP sont aussi dans P. Informellement, est-ce que le fait de pouvoir « voir facilement » (c’est à dire en temps polynomial) si un problème a une réponse « oui », pour peu qu’on me fournisse une preuve, veut aussi dire qu’on peut le « résoudre facilement ». Si c’est le cas, alors tous les problèmes de P sont dans NP, tous les problèmes de NP sont dans P, et donc la classe P et la classe NP contiennent exactement les mêmes problèmes, c’est à dire P = NP. Si ce n’est pas le cas, alors il y a des problèmes de NP qui ne sont pas dans P, et donc P ≠ NP.

L’immense majorité des gens qui font des maths pensent que P ≠ NP, mais personne n’a encore réussi à le prouver. Et beaucoup de gens ont essayé 🙂

Ça serait très, très, très surprenant pour tout le monde qu’on arrive à prouver que P = NP. Ça aurait probablement de grosses conséquences, parce que ça indiquerait qu’on a une chance de résoudre des problèmes actuellement considérés comme « difficiles » dans des temps « acceptables ». Une bonne partie de la cryptographie actuelle se base sur le fait non pas qu’il est « impossible » de faire certaines opérations, mais que c’est « difficile » de les faire, c’est à dire qu’on ne connaît pas d’algorithme rapide pour les faire. Ça ne casserait probablement pas immédiatement tout (parce que ça serait probablement difficile à appliquer directement et que ça prendrait du temps), mais il faudrait sans doute se dépêcher de trouver autre chose avant que ça arrive.

Et le dernier truc rigolo, c’est que pour prouver que P = NP, il « suffit » de trouver un algorithme en temps polynomial pour un des problèmes dits « NP-complets » – ce dont je parlerai dans un prochain billet, parce que celui-ci commence à tirer en longueur. La colorabilité à trois couleurs fait partie de ces problèmes NP-complets.

Personnellement, je trouve ça absolument fascinant qu’un problème aussi « facile » à conceptualiser ait de telles implications quant à sa résolution. Et j’espère qu’après avoir lu ce que je viens d’écrire, vous pouvez au moins comprendre ma fascination, à défaut peut-être de la partager 😉

Compréhension mathématique

Publié le 14 février 20139 novembre 2013 par Balise10 commentaires

Allez, après les billets un peu velus qu’étaient Introduction à la complexité algorithmique, 1/2 et Introduction à la complexité algorithmique, 2/2, un billet un peu plus light et un peu plus « méta », probablement. Et qui part dans le n’importe quoi, probablement aussi. Il est probable également qu’à la fin de la lecture de cet article vous soyez convaincu que je suis, dans le meilleur des cas, très exigeante avec moi-même, et dans le pire des cas que vous soyez tentés de me passer un chouette pyjama blanc qui s’attache dans le dos 🙂

Je suis assez fascinée par le fonctionnement du cerveau humain. Pas par la manière dont il fonctionne, ça j’en sais rien, mais par le fait même qu’il fonctionne. Le concept de lire, par exemple, ça continue à m’émerveiller. J’y reviendrai sans doute à l’occasion 🙂 (parce que ça touche probablement plus à l’apprentissage qu’à la compréhension, et que c’est deux sujets connexes, mais différents). (Enfin je crois.)

Bref, je passe pas mal de temps à réfléchir à la manière dont je réfléchis, et à la manière d’améliorer la manière dont je réfléchis, ou à tenter optimiser ce que je fais pour que ça corresponde à ma manière de réfléchir. Et dans cette réflexion, j’ai en particulier redéfini ce que j’entendais par « compréhension ».

Je me limite ici explicitement à un type de compréhension bien particulier, que j’appellerai « compréhension mathématique » à défaut d’un terme plus adéquat. Je sais même pas si je peux exactement définir le terme ; alors je vais essayer d’expliquer l’impression que ça fait. Ça peut paraître bizarre de relier la compréhension aux impressions, mais en ce qui me concerne j’ai, peut-être paradoxalement, appris à faire confiance à mon ressenti pour évaluer ma compréhension des choses.

Il m’arrive fréquemment de me lamenter que je ne comprends plus aussi vite qu’avant ; je me demande dans quelle mesure ça ne vient pas du fait que je suis plus exigeante envers moi-même. Il fut une époque où ma définition de « compréhension » était au niveau de « ce que tu racontes a l’air logique, et je vois l’enchaînement logique de ce que tu fais au tableau, et je vois en gros ce que tu fais ». J’ai aussi un souvenir assez cuisant d’incidents du genre :

« Tiens, tu devrais lire cet article.
— OK.
<quelques heures plus tard>
— J’ai finiiiii !
— Déjà ?
— Bin, ouais… je lis vite…
— Et t’as tout compris ?
— Bin… ouais…
— Y compris pourquoi <point obscur mais potentiellement crucial du papier> ?
<gros blanc, soupir et explications> » (pas de mon fait, les explications.)

Évidemment, c’était complètement de la bonne foi de mon côté. J’étais persuadée d’avoir effectivement compris, avant qu’on ne me démontre que j’avais raté pas mal de choses.

Depuis, j’ai appris plusieurs choses. La première est que « comprendre vaguement » n’est pas « comprendre », du moins pas à mon propre niveau (actuel) d’exigence. C’en est la première étape. Ça peut aussi en être la dernière étape, si c’est un sujet sur lequel je peux/veux me contenter de connaissances « de surface ». J’ai probablement gagné pas mal en modestie et je dis probablement beaucoup plus souvent que je n’ai qu’une vague idée de certains sujets.

La deuxième chose, c’est que oui, comprendre, ça prend du temps. Aujourd’hui, j’estime que je commence à avoir une compréhension « correcte » (encore une fois, à mon niveau d’exigence, qui est probablement élevé) à la troisième ou quatrième lecture d’un article de recherche. En-dessous de ça, j’ai « une vague idée de ce que raconte le papier ».

La troisième chose, et ça pourtant c’est une citation qui revenait souvent à la maison, c’est que « la répétition est l’âme de l’enseignement bien compris ». Ça aide beaucoup d’avoir au moins une exposition aux notions avant de commencer quelque chose de nouveau et velu. La première exposition est une grande baffe dans la gueule, la deuxième commence à aller mieux, au bout de la troisième on commence à se trouver en terrain connu.

La quatrième chose est probablement reliée à la deuxième – « ça prend du temps ». J’ai une ode à faire à la craie et au tableau noir. Les nouvelles technologies nous ont apporté tout un tas de machins vachement chiadés, des vidéoprojecteurs, des tableaux numériques, et je crois que je vais même mettre le tableau blanc et les Velleda dans le lot. Au risque de passer pour une vilaine réactionnaire, tout ça ne vaut pas la craie et le tableau noir. Bon, OK, vert, le tableau, je concède ça. C’est plus long d’écrire une preuve au tableau que de sortir un Powerpoint (ou des slides Beamer, je suis pas sectaire dans mon rejet 😉 ) avec la preuve dessus. Donc ouais, on avance moins vite dans le cours, probablement. Mais ça laisse aussi le temps de suivre. Et, c’est très con, mais ça laisse aussi le temps de prendre des notes. Beaucoup de mes collègues de classe me disent qu’ils « préfèrent écouter que noter » (surtout que souvent, pour les cours au tableau, on a des polys qui sont en général d’excellente qualité). Pour moi, noter aide à rester concentrée, et au final à mieux écouter. Je griffonne aussi au crayon certains points de raisonnement qui seraient pas forcément évidents à la relecture. Bon, des fois, je me laisse des blagues pour les révisions, aussi – j’ai trouvé l’autre jour un joli « It’s a circle, OK? » à côté d’une figure de patatoïde. Ça m’a beaucoup fait rire. Ah, et quant au fait que ma hargne s’étende aux tableaux blancs : déjà, les feutres Velleda, ça marche jamais. En plus, des fois, ya un marqueur permanent qui vient se paumer dans le porte-feutres (et après on passe un temps dingue à repasser au feutre effaçable pour effacer). Et en plus, ça s’efface plus vite. J’ai appris à apprécier la pause induite par le nettoyage du tableau noir – la méthode « courante » chez nous est de faire deux passes, une avec un machin humide et une avec une raclette. Ça m’a vachement impressionnée la première fois que j’ai vu ça 😉 (oui, je suis très impressionnable) et depuis, je profite de la minute ou deux que ça prend pour relire ce qu’on vient de faire. Je trouve ça salutaire. Bref, le tableau et la craie, c’est la vie.

Et j’ai aussi appris à lire un article scientifique, du moins avec une méthode qui me convient à moi. En général, je fais une première passe très rapide pour avoir une idée de la structure de l’article, de quoi il parle, de la manière dont s’enchaîne la preuve principale, et j’essaie de voir s’il y a des trucs qui vont m’agacer - je commence à avoir des idées assez arrêtées sur les structures qui me facilitent ou pas la vie dans un article, et quand ça en dévie je râle un peu, même si je suppose que ces structures sont pas les mêmes pour tous. (Bon, il y a aussi des articles intrinsèquement pénibles à lire, il faut l’admettre.) Par « très rapide », j’entends entre une demi-heure et une heure pour un article d’une dizaine de pages.

Ma deuxième lecture est une lecture « d’annotations ». Je lis un peu plus en détail, et je mets des questions partout. Les questions sont en général de l’ordre du « pourquoi ? »  ou du « comment ? », sur des éléments de langage tels que « it follows that » (il suit de ce qui précède que), « obviously » (il est évident que), ou tous les trucs genre « par une simple application du théorème de Machin ». C’est aussi « relativement » rapide, parce qu’il y a beaucoup de signaux auxquels se raccrocher, et que je ne cherche pas encore à avoir une compréhension de tous les détails, mais à identifier les détails qui nécessitent que j’y passe un peu de temps pour les comprendre. Je note aussi les points qui me « gênent », c’est à dire les points où je ressens une espèce d’inconfort. C’est un peu difficile à expliquer, parce que c’est vraiment un « gut feeling », une intuition qui me dit « mmmh, là, ya un truc qui coince. Je sais pas quoi, mais ya un truc qui coince. » J’aime pas trop le terme d’intuition pour traduire « gut feeling », parce que c’est littéralement ça. Une espèce de malaise dans l’abdomen qui traduit l’inconfort.

Pendant la troisième lecture, qui est la plus longue, je m’attache à répondre aux questions de la deuxième lecture et à reprendre les calculs. Et à me convaincre, bien souvent, que oui, ce machin est bien une typo, et pas une erreur dans mon raisonnement ou mes calculs à moi. La quatrième lecture et les lectures suivantes continuent sur le même mode pour les questions auxquelles je n’ai pas répondu pendant la troisième lecture (et qui peuvent peut-être s’éclaircir entre temps).

J’estime que j’ai compris un papier quand j’ai répondu à l’immense majorité des questions posées en deuxième phase. (Et je me débrouille en général pour trouver quelqu’un de plus malin que moi pour celles qui restent en suspens). Mais même là… je sais que bien souvent, c’est pas encore parfait.

Le test ultime, c’est de préparer une présentation à propos du papier. Dans la série faites ce que je dis, pas ce que je fais, quand je fais ça, je prépare… des slides pour vidéoprojecteur. Parce que j’ai beau préférer, en tant qu’étudiante, un cours au tableau, je me rends bien compte que c’est beaucoup de boulot, et que faire une (bonne) présentation au tableau, c’est difficile. Un jour, j’essaierai – peut-être. Une fois que j’ai des slides (qui, en général, me permettent de re-débusquer quelques points obscurs), je tente de faire une présentation. Et là, on revient au « gut feeling ». Si ça bafouille, s’il y a des slides qui n’ont pas de sens, si la présentation ne se passe pas comme sur des roulettes, c’est qu’il y a probablement encore quelque chose derrière qui nécessite que j’y passe du temps.

Quand tout, finalement, finit par sembler « bien », le sentiment qui prévaut, c’est une espèce de soulagement mêlé de victoire. Je sais pas trop à quoi comparer ça. Peut-être aux gens qui font des dominos. Tu passes un temps dingue à mettre tes petits dominos l’un après l’autre, et je pense qu’au moment où le dernier tombe sans que le truc soit interrompu, ça doit être à peu près ce sentiment-là.

Évidemment, je peux pas me permettre de faire ça avec tout ce que je lis, ça prendrait trop de temps. Je sais pas s’il y a moyen d’accélérer le processus mais je pense pas que ce soit possible, au moins pour moi, de façon significative. Parce que j’ai aussi besoin de « laisser décanter » les choses. Il y a d’ailleurs pas mal d’hypothèses « fortes » sur le fait que le sommeil ait un impact important sur l’apprentissage et la mémoire ; je ne sais pas dans quelle mesure on peut étendre ça à mes histoires de compréhension, mais ça m’étonnerait pas que le cerveau en profite pour ranger et faire les connexions qui vont bien.

Du coup, c’est parfois assez frustrant de laisser les choses à un état de « compréhension partielle », surtout quand on ne sait pas exactement ce qui coince. Le « gut feeling » est là (et pas seulement à la veille de l’examen 🙂 ). C’est parfois ce qui me ferait tout laisser tomber : à quoi bon comprendre les choses à moitié ? Mais peut-être que la moitié, c’est mieux que rien du tout, quand on sait qu’il reste la moitié du chemin à parcourir. Et, parfois, quand on s’entête un peu, tout finit par cliquer ensemble. Et c’est un sentiment d’accomplissement que pas grand chose d’autre n’arrive à égaler.

	Ja dans Y’a encore des gens sur…
	Balise dans Y’a encore des gens sur…
	Natacha dans Y’a encore des gens sur…
	Balise dans Y’a encore des gens sur…
	krysztophe dans Y’a encore des gens sur…

Flattr:

WordPress:

Flattr:

WordPress:

Flattr:

WordPress:

Flattr:

WordPress:

Flattr:

WordPress:

Flattr:

WordPress:

Flattr:

WordPress:

Flattr:

WordPress:

Flattr:

WordPress:

Flattr:

WordPress: