février 2013 – Le blog de Balise

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.

Introduction à la complexité algorithmique – 2/2

Publié le 11 février 20139 novembre 2013 par Balise8 commentaires

Dans l’épisode précédent, j’ai expliqué deux manières de trier des livres et j’ai tenté de justifier combien de temps, en nombre d’opérations élémentaires, ça me prenait de faire ça, et j’ai évalué le nombre maximum d’opérations en fonction du nombre de livres que j’avais à trier.

Je suis arrivée aux conclusions suivantes :

pour le « premier » tri, celui où je regarde à chaque étape où je dois mettre le livre suivant en parcourant tous les livres que j’ai mis jusqu’ici, j’ai, dans le meilleur des cas, 2n – 1 opérations, dans le pire des cas (n² + n)/2 opérations, et dans le cas moyen (n²+9n)/4 opérations.
pour le « deuxième » tri, celui où je combine mes ensembles de livres deux par deux, j’ai, dans tous les cas, 2*n*log(n) opérations.

Je vais me permettre une petite courbe ici parce que les courbes c’est joli.

Au cas où j’aurais des daltoniens parmi mes lecteurs, les courbes sont, de haut en bas, dans l’ordre de la légende.

Cette histoire de « meilleur cas, pire cas, cas moyen » est très utilisée pour parler de la complexité des algorithmes. On ne s’intéresse en général que peu au « meilleur cas », parce qu’en général, Murphy aidant, c’est rarement le cas qui arrive. (Même si on peut éventuellement se poser la question de « comment faire pour avoir le meilleur cas plus souvent ? » si ça peut faire une différence pour l’algorithme.) En général, on s’intéresse plutôt au cas moyen et au pire cas.

L’avantage de s’intéresser au pire cas, c’est que c’est le seul qui fournit des garanties. Si je dis que mon algorithme, dans le pire cas, s’exécute en tant de temps, je garantis qu’il ne sera jamais plus long que ça, même s’il lui arrive d’être plus rapide. Dans certains cas, on a besoin de ce genre de garanties. En particulier, on s’intéresse parfois (dans le domaine de la cryptographie en particulier) à ce qu’il se passe si un « adversaire » me fournit les données comme il veut, et de préférence de manière à compliquer ma vie le plus possible. Et on veut des garanties sur le fait que ce qu’on fait fonctionne comme on veut que ça fonctionne, même quand on a un adversaire en face qui fait tout pour nous pourrir la vie. L’inconvénient, c’est qu’on surestime souvent le temps d’exécution « usuel » si on prend en compte le pire cas, et qu’on peut se retrouver à le surestimer de beaucoup.

L’avantage de s’intéresser au cas moyen, c’est justement qu’on a une idée de ce qui se passe « normalement ». (Je fais beaucoup de raccourcis et je dis probablement des choses qui ne sont pas vraies dans le cas général, mais dans l’idée c’est pas si délirant que ça). Ça donne aussi une idée de ce qui se passe si on répète l’algorithme plusieurs fois sur des données indépendantes ; le temps moyen d’une exécution sera quelque part entre le meilleur cas et le pire cas. L’autre avantage de s’intéresser au cas moyen, c’est qu’il y a parfois des manières « simples » d’éviter au maximum le pire cas. Par exemple, si j’ai un adversaire qui me donne les livres dans un ordre qui me pourrit mon algorithme, je peux « compenser » ça par le fait de mélanger moi-même les livres au début pour que la probabilité d’être dans un « mauvais » cas soit faible (et ne dépende pas de ce que me fournit mon adversaire). L’inconvénient, c’est évidemment qu’on n’a aucune garantie sur le temps « maximum » que prend un algorithme.

Évidemment, ce qu’on fait au final dépend de ce qu’on veut faire (fou, non ?).

Ceci étant posé, les complexités, en nombre d’opérations, que j’ai données précédemment (2n-1, (n²+n)/2, (n²+9n)/4, 2n log(n)) ne sont pas celles qu’on utilise en général. Si on me demande les résultats précédents, je réponds que les complexités sont, respectivement, « n » (ou « linéaire »), « n² » (ou « quadratique »), « n² » et « n log n ». Ça peut paraître extrêmement approximatif et peu précis et tout ce genre de choses, et je dois dire que les premières fois que j’ai vu ce genre d’approximations, ça m’a agacée au plus haut point. Bon, le fait que c’était en cours de physique avait probablement un rapport avec ça, mais, bon. Depuis, je trouve que c’est drôlement pratique et même que ça a du sens. Il faut savoir, déjà, que le fait que « ça a du sens » a une justification mathématique solide. Je ne vais pas la donner ici, parce que c’est très nettement au-dessus du niveau du billet que je suis en train de vouloir écrire. Pour les gens intéressés, qui lisent l’anglais, et qui ont pas peur des trucs du genre « limite en plus l’infini de blah », il y a http://en.wikipedia.org/wiki/Big_O_notation (ou son pendant en français, http://fr.wikipedia.org/wiki/Comparaison_asymptotique, mais je trouve la version anglaise plus claire).

Bon, sinon, j’ai au moins deux trucs à tenter de justifier ici. Attention, ce que je vais faire ici est très, très peu rigoureux. La première question est celle de ce qui arrive aux « petits » termes. L’idée, c’est que je ne garde que ce qui « compte » dans le fait que mon nombre d’opérations augmente avec le nombre d’éléments à trier. Par exemple, si j’ai 750 livres à trier, et que je veux faire ça avec mon premier algorithme, dans le cas « moyen », j’ai (n²+9n)/4 opérations, c’est à dire n²/4 + 9n/4. Pour 750 livres, ces deux « morceaux » valent, respectivement, 140625 et… 1687. Si j’ai 1000 livres à trier, je monte à 250000 et 2250. Le premier « morceau » de l’expression est beaucoup plus gros, et il grandit beaucoup plus vite. Si je veux estimer le temps que ça me prend, sans avoir besoin de trop de précision, je peux prendre le n²/4 et laisser tomber le 9n/4 – déjà pour 1000 livres, le nombre d’opérations du 9n/4 correspond à moins de 1% du total.

La deuxième question est plus compliqué (à mon sens) : pourquoi est-ce que je considère identiques « n² » et « n²/4 », « 2 n log n » et « n log n » ? Encore une fois, il y a une justification mathématique derrière tout ça, que je vais tenter d’éviter de vous infliger. Mais on peut tenter de le justifier aussi en faisant de grands moulinets. (Je ne suis pas très satisfaite de mes explications ici, mais je ne trouve pas mieux. Si un Gentil Lecteur a mieux, qu’il n’hésite pas à expliquer dans les commentaires 🙂 ).

L’idée, c’est qu’on ne s’intéresse pas nécessairement à un algorithme « tout seul », mais à comparer différents algorithmes. Et, en particulier, on s’intéresse à la comparaison dite « asymptotique », c’est à dire à ce qu’il se passe quand on a un très grand nombre d’éléments en entrée de l’algorithme (par exemple un très grand nombre de livres à trier). Et si j’ai un très grand nombre de livres à trier, j’aimerais autant que ça me prenne le moins de temps possible, et donc je cherche le « meilleur » algorithme, celui qui va le plus vite.

Pour que ça me prenne le moins de temps possible, j’ai deux solutions. Ou bien je réduis le temps que chaque opération prend, ou bien je réduis le nombre d’opérations lui-même. Je prends mon algorithme 1, qui fait n²/4 opérations, et mon algorithme 2, qui fait 2 n log n opérations pour n éléments. Supposons que j’aie un ordinateur qui fait une opération en une seconde, et que je veuille trier 100 éléments. Avec le premier algorithme, ça lui prendra environ 2500 secondes. Avec le deuxième algorithme, ça lui prendra environ 1328 secondes (parce que 2*100*log(100) est environ égal à 1328). Maintenant, supposons que j’aie un ordinateur vachement plus rapide sur lequel faire fonctionner mon premier algorithme. Au lieu de prendre une seconde, cet ordinateur est cinq fois plus rapide et il peut effectuer une opération en un cinquième de seconde (0.2 seconde). Du coup, je peux trier mes 100 éléments en 0.2*100²/4 = 500 secondes, ce qui est plus rapide que ce que je peux faire avec l’autre ordinateur. Youpi. Mais il y a évidemment deux bémols à ça. Le premier bémol, c’est que si je mets mon deuxième algorithme sur le deuxième ordinateur aussi, je peux trier mes éléments en 0.2*2*100*log(100) = 265 secondes. Bon, supposons que pour une raison bizarre le deuxième algorithme ne fonctionne pas sur le deuxième ordinateur et qu’il faille que je le garde sur le premier ordinateur. Mais le deuxième bémol, c’est que si j’ai maintenant 1000 éléments à trier et non plus 100, ça va me prendre, avec le premier algorithme sur l’ordinateur vachement plus rapide, 0.2*1000²/4 = 50000 secondes, et avec le deuxième algorithme sur l’ordinateur vachement plus lent, 2*1000*log(1000) = 19931 secondes.

Et c’est un peu l’idée qu’il y a derrière la suppression des « nombres multiplicateurs » dans mon évaluation de complexité. Si j’ai un algorithme qui s’exécute avec une complexité « dans les n² » et un algorithme qui s’exécute avec une complexité « dans les n log n », je peux mettre l’ordinateur le plus puissant que je veux derrière le premier algorithme, il y aura toujours un nombre d’éléments pour lequel mon deuxième algorithme, même sur une machine très lente, ira plus vite que le premier. Le nombre d’éléments peut être très grand si la première machine est très rapide et la deuxième très lente, mais, comme je m’intéresse à ce qu’il se passe avec de très grands nombres d’éléments, c’est pas très grave.

Donc, quand je parle de comparer deux algorithmes, il est beaucoup plus intéressant de voir que j’en ai un dont le temps d’exécution est en n log n et un en n², que de pinailler sur la constante (le nombre) qui va devant le n log n ou le n².

Évidemment, pour deux algorithmes en n², on peut se poser la question de la constante qui va devant. En pratique, ça se fait assez peu, parce qu’à moins d’avoir des choses extrêmement simples et carrées (et encore), suivant la manière dont on implémente les choses (avec un langage de programmation), déterminer ladite constante devient très difficile. Il faut aussi se poser la question, exactement, de ce qu’est une opération. Il y a des modèles « classiques » qui permettent de définir tout ça, mais relier ces modèles aux langages de programmation actuels doit tenir à peu près de l’utopie.

Bon, et en tant que « gens qui font de l’algorithme », qu’est-ce qui nous plaît bien, qu’est-ce qui commence à nous faire grimacer, et qu’est-ce qui nous fait courir à toute vitesse dans l’autre sens ? Je donne tout ça en fonction de la « taille » de l’entrée, n ; pour mon exemple de tri, c’est le nombre d’éléments à trier. Si je fais des opérations sur des graphes, la taille de l’entrée va typiquement être le nombre de sommets du graphe, parfois le nombre d’arcs.

Les algorithmes « en temps constant » et « logarithmiques » (donc avec soit un nombre d’opérations constant, soit un nombre d’opération de type log n) sont relativement rares, parce qu’avec log n opérations (ou un nombre constant d’opérations), on n’a même pas le temps de regarder tout ce qu’on a en entrée. Donc, quand on trouve un algorithme de ce type, on est très très content. Un exemple « classique » d’algorithme qui fonctionne en temps logarithmique, c’est celui de chercher un élément dans une liste triée. Quand la liste est triée, on n’a pas besoin de lire toute la liste pour trouver l’élément qu’on cherche. On peut commencer par regarder s’il est avant ou après le milieu, regarder s’il est avant ou après le milieu de l’intervalle qu’on vient de redéfinir, et ainsi de suite. Je pourrais refaire une belle explication avec un arbre si ça vous intéresse, mais je vais pas faire ça maintenant.

On est aussi en général très content quand on trouve un algorithme linéaire (« n »). Ça veut dire, quelque part, qu’on lit tout ce qu’on a en entrée, on fait quelques opérations par élément, et paf c’est fini. n log n est aussi généralement considéré comme « acceptable ». C’est une borne importante, parce qu’on peut prouver que, dans les modèles algorithmiques courants (qui reviennent plus ou moins à compter des opérations « basiques »), on ne peut pas trier n éléments plus rapidement qu’en n log n opérations dans le cas général, c’est-à-dire sans rien savoir sur les éléments en question (Parce que si je sais qu’ils sont triés, ou dans l’ordre inverse, je peux les trier en temps linéaire). Du coup, il y a un certain nombre d’algorithmes qui s’appuient, à un moment ou un autre, sur un tri ; si on ne peut pas se débarrasser du tri, on ne peut pas non plus descendre en-dessous de n log n.

On commence à grommeler un peu à partir de n², n³, et à grommeler beaucoup sur les puissances supérieures de n. Les algorithmes qui peuvent s’exécuter en un temps $n^k$ , pour une valeur quelconque de k (y compris 1000000) sont appelés « polynomiaux ». L’idée, c’est que, de la même manière qu’un algorithme en n log n finira par être plus efficace qu’un algorithme en n², en prenant un entrée suffisamment grande, un algorithme polynomial, quel que soit k, finira par être plus efficace qu’un algorithme en $2^n$ . Ou même en $1.308^n$ . Ou même en $1.01^n$ .

Évidemment, en pratique, ce genre de raisonnement a ses limites aussi. J’ai un exemple qui m’amuse personnellement beaucoup, et j’espère qu’il vous amusera aussi. Considérons le problème de la multiplication de deux matrices entre elles. (Pour les gens qui n’ont pas jamais vu de matrices, on peut voir une matrice comme un tableau de nombres – et il se trouve qu’on peut multiplier ces tableaux de nombres. C’est un peu plus compliqué que de multiplier les nombres un par un, mais guère.) (Dit la fille qui savait pas comment multiplier deux matrices avant la 3e année d’école d’ingénieur, mais c’est une autre histoire.)

L’algorithme qu’on apprend à l’école permet de multiplier deux matrices en un temps n³, où on considère des matrices de taille n*n (pour les gens pas familiers des matrices : on trace un tableau de n lignes et n colonnes, et on met des nombres dedans). En se forçant un peu, on peut trouver un algorithme (algorithme de Strassen, de son petit nom), pas trop compliqué, qui fonctionne en un temps $n^{2.807}$ (ce qui est meilleur que le n³). Et en se forçant beaucoup, il existe un algorithme qui fonctionne en temps $n^{2.3727}$ (Coppersmith–Winograd et ses dérivés). C’est, je crois, le seul algorithme pour lequel j’ai entendu PLUSIEURS personnes faisant de la théorie dire que « oui, mais vraiment, la constante est vraiment dégueulasse » - en parlant du nombre par lequel on multiplie ce $n^{2.3727}$ pour avoir le temps d’exécution « réel ». Pour les raisons données précédemment, on ne connaît pas vraiment la constante en question, on sait juste qu’elle est dégueulasse. En pratique, de ce que je sais (peut-être que certains de mes lecteurs ont des avis plus tranchés sur la question), les algorithmes « rapides » de multiplication de matrice utilisent celui de Strassen (ou une variante), parce qu’à cause de la constante en question, les tailles de matrices pour lesquelles Coppersmith-Winograd serait « rentable » sont énormes, et peu utiles en pratique.

Voilà, sur cette anecdote amusante, je vais arrêter là pour ce billet. J’espère que c’était approximativement compréhensible, ce dont je ne suis pas vraiment sûre. N’hésitez pas à poser des questions, faire des remarques et tout ce genre de choses 🙂

Introduction à la complexité algorithmique – 1/2

Publié le 9 février 20139 novembre 2013 par Balise9 commentaires

Bon, ça y est, j’ai fini les deux billets qui savaient à peu près où ils allaient (un billet général sur l’informatique théorique, et un billet pour expliquer ce qu’est un logarithme parce que c’est toujours utile). Et après on a fait une petite pause, parce que bon. Donc maintenant je vais rentrer dans les choses un peu plus compliquées, et qui me sont plus difficiles à expliquer aussi. Donc j’écris, et puis on verra bien ce que ça donne à la fin. Ajoutons à cela que je veux essayer d’expliquer les choses en évitant au maximum le formalisme mathématique qui m’est maintenant « naturel » (mais croyez-moi, il a fallu me le rentrer dans le crâne à coups de marteau) : je sais vraiment pas ce que ça va donner. J’ai aussi décidé de couper ce billet en deux, parce qu’il est déjà fort long comme ça. Je pense que le deuxième sera plus court.

J’ai déjà défini un algorithme comme étant une suite bien définie d’opérations qui permettent d’arriver à un résultat. Je ne vais pas aller beaucoup plus loin dans la définition formelle, parce que je pense que ce n’est pas utile - du moins pas pour le moment. Et je vais définir, également de façon très peu formelle, la complexité algorithmique comme la quantité de ressources qu’il me faut pour exécuter mon algorithme. Par ressources, j’entendrai le plus souvent « le temps », c’est-à-dire le temps qu’il me faut pour exécuter un algorithme, parfois « l’espace », c’est à dire la quantité de mémoire (pensez-y comme à de la mémoire vive ou du disque dur) qu’il me faut pour exécuter mon algorithme.

Je vais prendre un exemple très classique pour illustrer mon propos, qui est celui du tri. Et pour donner un exemple concret de cet exemple classique, supposons que j’aie une bibliothèque pleine de livres. (Une supposition absolument et complètement folle.) Et qu’il me vienne l’idée sotte et complètement grenue de vouloir les trier, disons par ordre alphabétique de nom d’auteur (et de titre à nom d’auteur égal). Je dis qu’un livre A est « plus petit » qu’un autre livre B s’il doit être rangé avant dans la bibliothèque, et qu’il est « plus grand » s’il doit être rangé après. Avec cette définition, les bouquins d’Asimov sont plus petits que les bouquins de Clarke qui sont plus petits que les bouquins de Pratchett. Je vais garder cet exemple pendant tout le billet et je vais faire le parallèle avec les notions algorithmiques correspondantes.

Je commence donc par définir ce dont je parle. L’algorithme que j’étudie, c’est l’algorithme de tri ; c’est celui qui me permet de passer d’une bibliothèque en bordel à une bibliothèque rangée dans l’ordre alphabétique. En « entrée » de mon algorithme, c’est-à-dire les données que je donne à traiter à mon algorithme, j’ai une bibliothèque en bordel. En « sortie » de mon algorithme, j’ai les données traitées par mon algorithme, c’est-à-dire une bibliothèque rangée.

La première chose qu’on peut remarquer, c’est que plus on a de livres, plus c’est long à trier. Ça vient de deux choses. La première, c’est que si on considère une opération « élémentaire » du tri (par exemple, mettre le livre dans la bibliothèque), c’est plus long de faire ça 100 fois que 10 fois. La deuxième, c’est que si on considère tout ce qu’on fait pour chaque livre, plus il y a de livres, plus c’est long à faire. C’est plus long de chercher quel est le bon emplacement pour un livre parmi 100 que parmi 10.

Et voilà ce à quoi on s’intéresse ici : la manière dont le temps nécessaire à obtenir une bibliothèque rangée évolue en fonction du nombre de livres ou, de façon plus générale, la manière dont le temps nécessaire à obtenir une séquence triée d’éléments dépend du nombre d’éléments à trier.

Ce temps dépend de la méthode de tri qu’on utilise. Par exemple, on peut choisir une méthode de tri très très longue : tant que la bibliothèque n’est pas triée, on remet tout par terre et on met les livres dans un ordre aléatoire dans la bibliothèque. Pas trié ? On recommence. Ça, typiquement, ça va être très long. À l’autre bout du spectre, on a Mary Poppins : un Supercalifragilistic, et paf, la bibliothèque est rangée. La méthode Mary Poppins a d’ailleurs une particularité : elle ne dépend pas du nombre de livres à ranger. On dit que Mary Poppins s’exécute en « temps constant » : quel que soit le nombre de livres à ranger, ils seront rangés dans la seconde. En pratique, il y a bien une raison pour laquelle la méthode Mary Poppins fait rêver, c’est bien que c’est magique et difficilement réalisable en réalité.

Revenons, donc, à la réalité, et aux algorithmes de tri autres que Mary Poppins. Pour analyser la manière dont mon tri marche, je considère trois opérations élémentaires dont je peux avoir besoin pendant que je range :

comparer deux livres pour savoir si l’un se range avant ou après l’autre
mettre le livre dans la bibliothèque
et, en supposant que mes livres en bordel soient en bordel sur une table, le déplacement d’un livre sur la table.

Et je vais supposer aussi que ces trois opérations prennent le même temps, disons une seconde. Ça ne serait pas très efficace pour un ordinateur, mais je pense que c’est plutôt efficace pour un humain, et ça donne une idée. Je vais aussi supposer que ma bibliothèque est un peu magique, c’est-à-dire que ses rayonnages s’adaptent tous seuls et que les livres s’y placent sans avoir de problème de « rha, j’ai plus de place sur cette étagère, il faut que je descende des bouquins sur celle d’en-dessous, qui est pleine aussi, et là c’est le drame ». Pareil, ma table est magique, et déplacer un livre où je veux ne pose pas de problème. En pratique, il faudrait se poser ce genre de questions, y compris d’un point de vue algorithmique (quelle est la pénalité d’avoir à faire ça, est-ce que je peux l’éviter en étant malin). Mais comme je ne suis pas en train d’écrire un billet sur les tris mais sur la complexité algorithmique, je simplifie. (Et pour ceux qui savent de quoi je parle, oui, je sais que mon modèle est discutable. C’est un modèle, c’est mon modèle, je fais ce que je veux avec, et les explications restent valides dans mon modèle même s’il est discutable).

Un premier tri

Voici maintenant une première manière de trier. Je suppose que j’ai vidé ma bibliothèque en bordel sur ma table, et que je veux ranger les bouquins un par un. Le scénario suivant est assez peu réaliste pour un humain qui, probablement, se souviendrait approximativement de l’endroit où mettre le livre, mais essayez d’imaginer la situation suivante.

Je prends mon premier bouquin, je le mets dans la bibliothèque.
Je prends un deuxième bouquin, je compare avec le premier : s’il doit être rangé avant, je le mets devant, s’il doit être rangé après, je le mets après.
Je prends le troisième bouquin, je compare avec le premier. S’il doit être rangé avant, je le mets en première position. S’il doit être rangé après, je compare avec le deuxième bouquin que j’ai rangé. S’il doit être rangé avant, je le mets entre le bouquin 1 et le bouquin 2. S’il doit être rangé après, je le mets en dernière position.
Et ainsi de suite, jusqu’à ce que ma bibliothèque soit rangée. À chaque livre que j’insère, je compare, dans l’ordre, avec les livres déjà en place, et je l’insère entre le dernier livre qui est « plus petit » et le dernier livre qui est « plus grand ».

Et maintenant, je me demande combien de temps ça prend si j’ai, mettons, 100 livres, ou un nombre quelconque de livres. Je vais donner la réponse dans les deux cas : pour 100 livres et pour un nombre n de livres. Le temps pour n livres sera une fonction du nombre de livres, et c’est ce qui m’intéresse vraiment ici, ou plutôt ce qui m’intéressera vraiment dans le deuxième billet de cette introduction.

La réponse est que ça dépend de l’ordre dans lequel mes livres étaient au début quand ils étaient sur ma table. Il peut arriver, pourquoi pas, qu’ils étaient déjà triés. J’aurais peut-être dû vérifier ça avant de tout poser sur la table, ça aurait été plus malin, mais je n’y ai pas pensé avant. Il se trouve que c’est la pire chose qui puisse m’arriver avec cet algorithme, parce qu’à chaque fois que je veux ranger un livre, comme il est plus grand que tous ceux que j’ai rangés avant, il faut que je compare avec tous les livres que j’ai rangés avant. Comptons :

Je mets le premier livre dans la bibliothèque. Nombre d’opérations : 1.
Je compare le deuxième livre avec le premier livre. Je le mets dans la bibliothèque. Nombre d’opérations : 2.
Je compare le troisième livre avec le premier livre. Je compare le troisième livre avec le deuxième livre. Je le mets dans la bibliothèque. Nombre d’opérations : 3.
Je compare le quatrième livre avec le premier livre. Je compare le quatrième livre avec le deuxième livre. Je compare le quatrième livre avec le troisième livre. Je le mets dans la bibliothèque. Nombre d’opérations : 4.
Et ainsi de suite. À chaque fois que j’insère un livre, je le compare avec tous les livres qui l’ont précédé ; quand j’insère le 50e livre je fais donc 49 comparaisons, plus l’ajout du livre dans la bibliothèque, 50 opérations.

Donc pour insérer mes 100 livres, s’ils sont dans l’ordre au début, il me faut 1+2+3+4+5+…+99+100 opérations. Il se trouve, et je vais vous demander de me croire sur parole ici (c’est facile à démontrer, mais c’est pas l’objet) que 1+2+3+4+5+…+99+100, ça fait exactement (100*101)/2 = 5050 opérations. Et que, si je n’ai plus 100 livres, mais n livres qui se trouvent être dans l’ordre, il me faut n*(n+1)/2 = (n² + n)/2 opérations.

Supposons maintenant que mes livres étaient exactement dans l’ordre inverse duquel ils doivent être rangés. Ben cette fois ci, c’est la meilleure chose qui puisse m’arriver avec cet algorithme, parce que le livre que j’ajoute est toujours plus petit que tous ceux que j’ai rangés avant, donc il suffit de comparer avec le premier livre.

Je mets le premier livre dans la bibliothèque. Nombre d’opérations : 1.
Je compare le deuxième livre avec le premier livre. Je le mets dans la bibliothèque. Nombre d’opérations : 2.
Je compare le troisième livre avec le premier livre. Je le mets dans la bibliothèque. Nombre d’opérations : 2.
Et ainsi de suite : je compare toujours avec le premier livre, il est toujours plus petit, et j’ai toujours 2 opérations.

Donc si mes 100 livres sont exactement dans l’ordre inverse, je fais 1+2+2+2+…+2 = 1 + 99*2 opérations = 199 opérations. Et, si j’ai n livres dans l’ordre inverse, il me faut 1+2*(n-1) = 2n – 1 opérations.

C’est à partir d’ici que ça se corse un peu, parce que la situation devient moins bien définie, et que je vais commencer à faire des approximations dans tous les sens. J’essaie de justifier à chaque fois les approximations que je fais et pourquoi elles sont valides ; il est possible, cependant, que je zappe quelques étapes. N’hésitez pas à râler dans les commentaires si je suis complètement partie en sucette, parce que j’ai un peu de mal à me rendre compte

Je vais maintenant supposer que mes livres en bordel sont dans un état qui fait que, à chaque fois que j’ajoute un livre, il est inséré à peu près au milieu de ce qui a déjà été trié. (Je dis à peu près parce que si j’ai trié 5 livres, je vais typiquement ranger le 6e après le 2e ou après le 3e livre – les emplacements sont entiers, je vais pas le ranger après le 2.5e livre). Supposons que j’insère le livre numéro i ; j’estime le nombre de comparaisons que je fais à i/2 + 1, qui est supérieur ou égal au nombre de comparaisons que je fais effectivement. Pour voir ça, je distingue sur le fait que i soit pair ou impair. On peut montrer que ça marche pour tous les nombres ; je vais juste donner deux exemples pour expliquer qu’effectivement ça a de bonnes chances de marcher.

Si j’insère le 6e livre, j’ai 5 livres déjà rangés ; supposons que je veuille le ranger après le 3e livre (au « presque milieu »), je fais 4 comparaisons (parce qu’il est plus grand que le premier, deuxième, troisième livre, mais plus petit que le 4e) ; on a i/2 + 1 = 6/2+1 = 4.

Si j’insère le 7e livre, j’ai 6 livres déjà rangés, je veux le ranger après le 3e livre aussi (exactement au milieu), je fais également 4 comparaisons, et j’ai i/2+1 = 7/2 + 1 = 4.5.

Donc, je vais estimer le nombre d’opérations qu’il me faut pour ranger 100 livres, en comptant « large », et en me permettant des « demis-opérations ». Le but du jeu n’est pas ici de dénombrer exactement, mais d’avoir un ordre de grandeur, qui se trouvera être supérieur au nombre exact d’opérations.

Livre 1 : 1/2+1 = 1.5, plus le rangement, 2.5 opérations (je n’ai pas besoin de comparer, en fait, ici ; je le fais quand même parce que ça me facilite les calculs à la fin)
Livre 2 : 2/2 + 1 = 2, plus le rangement, 3 opérations (pareil ici, j’ai une comparaison de trop, parce que je n’ai qu’un seul bouquin de rangé, mais encore une fois je ne suis pas à un près).
Livre 3 : 3/2 + 1 = 2.5, plus le rangement, 3.5 opérations
Livre 4 : 4/2 + 1 = 3, plus le rangement, 4 opérations

Si je continue comme ça et que je range un peu mes calculs, j’ai, pour 100 livres, au plus

(1+2+3+4+…+99+100)/2 + 100 + 100 = (100*101/2)/4 + 200 = 2725 opérations.

Le premier élément de ma somme vient du « i/2 » que j’ai dans tous mes calculs de nombre de comparaisons. Le premier 100 vient du « 1 » que j’ajoute chaque fois que je compte les comparaisons (et je fais ça 100 fois), le deuxième 100 vient du « 1 » que j’ajoute à chaque fois que je compte le rangement des livres, et que je fais également 100 fois.

Ce 2725 est un peu surestimé, mais « de peu » : pour les deux premiers livres, j’ai exactement 2.5 comparaisons de trop ; pour les autres, j’ai au pire 0.5 comparaisons de trop. Sur 100 livres, ça fait donc au plus 98*0.5 + 2.5 = 51.5 opérations comptées en trop ; mon nombre exact d’opérations est donc compris entre 2673 et 2725. Il y aurait moyen de faire les choses un peu plus précisément, mais on verra par la suite (dans le prochain billet) pourquoi ça n’a pas grand intérêt.

Si je compte pour n livres, j’arrive à une estimation de (n*(n+1)/2)/2 + 2*n = (n²+9n)/4 opérations.

On peut montrer (mais pour le coup ça prendrait vraiment des proportions ici) que ce comportement est à peu près celui qu’on a quand on a des livres dans un ordre aléatoire. L’idée, c’est que si mes livres sont dans un ordre aléatoire, je vais en insérer certains plutôt au début, d’autres plutôt à la fin, et donc, « en moyenne », à peu près au milieu.

Une autre méthode de tri

Je vais maintenant expliquer une autre méthode de tri, qui est probablement moins facile à conceptualiser, mais qui je pense est la méthode la plus simple qui me permet de continuer mon argument.

Je vais supposer, cette fois, que je n’ai pas 100 livres à trier, mais 128. Parce que c’est une puissance de 2 et que ça me facilite la vie pour mon exemple concret. Et parce que j’y ai pas pensé avant et que j’ai la flemme de remonter dans mon exemple pour repartir sur 128 plutôt que 100.

Je suppose que tous mes livres sont sur la table, directement posés dessus, et je vais faire des « ensembles » avant de ranger mes bouquins dans la bibliothèque. Et je vais faire ces ensembles d’une façon un peu bizarroïde, mais efficace.

Je commence par combiner mes livres deux par deux. Je prends deux livres, je les compare, je mets le plus petit à gauche et le plus grand à droite. À la fin de cette opération, j’ai 64 ensembles de deux livres, avec dans chaque ensemble un petit livre à gauche et un grand livre à droite. Pour faire cette opération, j’ai dû faire, en tout, 64 comparaisons, et 128 déplacements de livres (je suppose que je déplace toujours les livres, ne serait-ce que pour les prendre en main et lire les auteurs/titres).

Ensuite, je prends mes ensembles de deux livres, et je les combine aussi de façon à avoir des ensembles de 4 livres, toujours ordonnées. Pour faire ça, je compare les deux premiers livres de deux ensembles, le plus petit des deux devient le premier livre de mon nouvel ensemble de 4. Je compare ensuite le livre restant de l’ensemble de 2 avec le premier livre de l’ensemble de 2, et je mets le plus petit en 2e position de mon ensemble de 4. Là, il peut se passer deux choses. Ou bien il me reste un livre dans chacun des ensembles initiaux ; auquel cas, je les compare, et je les mets dans l’ordre dans mon ensemble de 4. Ou bien il me reste un ensemble de deux ; je peux alors me contenter de les ajouter à la fin de mon ensemble de 4 et j’ai mon ensemble de 4. Voilà deux petits dessins qui distinguent les deux cas ; chaque carré représente un livre dont l’auteur a un nom commençant par la lettre indiquée, chaque rectangle représente mes ensembles de livres (les initiaux de 2 et le final de 4 livres), et les éléments rouges sont ceux qui sont comparés à chaque étape.

Bref, pour chaque ensemble de 4 que je crée, je dois faire 4 déplacements, et 2 ou 3 comparaisons. Je termine cette opération avec 32 ensembles de 4 livres ; donc au final je fais 32*4 = 128 déplacements et entre 32*2 = 64 et 32*3 = 96 comparaisons.

Je crée ensuite 16 ensembles de 8 livres, également en comparant le premier élément de chaque ensemble de livres et en créant un ensemble commun trié. Pour combiner deux ensembles de 4, il me faut 8 déplacements et entre 4 et 7 comparaisons. Je ne vais pas rentrer dans le détail de la manière d’obtenir ces chiffres ; la manière la plus simple avec ce genre de chiffres est d’énumérer tous les cas, ça commence à être fastidieux à 4, mais c’est encore gérable. Donc pour créer les 16 ensembles de 8 livres, il faut que je fasse 16*8 = 128 déplacements et entre 16*4 = 64 et 16*7 = 112 comparaisons.

Et je continue comme ça jusqu’à avoir 2 ensembles de 64 livres, que je finis par combiner (directement dans la bibliothèque pour gagner du temps) pour obtenir une bibliothèque rangée.

Bon, et combien de temps ça me prend cette affaire ? Je vais déjà commencer par donner une estimation pour 128 livres, et après je regarderai ce que ça donne pour n livres. Le plus pénible, ça ne surprendra personne, est d’évaluer le nombre de comparaisons quand on combine deux ensembles de livres. Je vais me permettre une approximation de plus pour dire que, si je veux combiner deux ensembles qui font chacun k éléments en un gros ensemble qui fait 2*k éléments, il me faut au plus 2*k comparaisons. Pour voir ça, on peut essayer de raisonner par énumération et faire une preuve propre et tout. J’avoue que j’ai pas le courage, d’autant plus que je sais où mon raisonnement va, et que je sais que j’ai pas envie de faire des calculs précis, parce qu’au final c’est pas très important d’être précis. On peut aussi faire l’observation suivante : à chaque fois qu’on fait une comparaison, on pose un bouquin dans le « gros » ensemble. Comme je ne pose que 2*k livres, je ne peux pas faire plus de 2*k comparaisons : si je faisais, par exemple, 2*k+1 comparaisons, il faudrait que je pose 2*k+1 livres… et je ne les ai pas. Donc, je vais estimer qu’à chaque fois que je combine deux ensembles de k éléments chacun en un ensemble de 2*k éléments, je fais au maximum 2*k comparaisons, et que je fais exactement 2*k déplacements. La deuxième observation, pour aller un peu plus loin et gagner encore un peu de temps dans les estimations, c’est qu’à chaque fois que je combine mes ensembles de k éléments en ensembles de 2*k éléments, je pose, en tout, exactement 128 livres (puisque c’est le nombre total de livres que j’ai, que chaque livre est dans un « petit » ensemble au départ et qu’il arrive dans un « grand » ensemble). Donc, je ne fais, au maximum, que 128 comparaisons à chaque étape.

Il me reste donc à compter le nombre d’étapes.

Pour 128 livres, ça me fait donc, au maximum :

Passer de 128 ensembles de 1 à 64 ensembles de 2 
Passer de 64 ensembles de 2 à 32 ensembles de 4
Passer de 32 ensembles de 4 à 16 ensembles de 8
Passer de 16 ensembles de 8 à 8 ensembles de 16
Passer de 8 ensembles de 16 à 4 ensembles de 32
Passer de 4 ensembles de 32 à 2 ensembles de 64
Passer de 2 ensembles de 64 à 1 ensemble de 128

Soit 7 étapes. Dans chacune de ces 7 étapes, j’ai 128 déplacements, et au maximum 128 comparaisons, soit au maximum 7*(128+128) = 1792 opérations. Notons que je n’ai fait ici aucune hypothèse sur l’ordre initial des livres. À comparer avec les 5050 opérations du « pire cas » du tri précédent, ou avec les environ 2700 opérations du cas « moyen » – nombres qui étaient d’ailleurs calculés pour 100 livres et pas 128 - pour 128 livres, on aurait, respectivement, 8256 opérations pour le « pire cas » et environ 4300 opérations pour le cas moyen.

Qu’en est-il exactement de la formule générale pour n livres ? Je pense qu’on peut être d’accord sur le fait que, à chaque étape, on déplace n livres, et qu’on fait au plus n comparaisons (puisque chaque comparaison correspond au fait de poser un livre). Donc, à chaque étape, je fais au plus 2*n comparaisons. La question est maintenant de savoir combien d’étapes on fait. Et c’est ici que mon splendide billet sur les logarithmes (kof) m’est utile. Est-ce que vous pouvez voir la similarité avec la figure suivante ?

Et si je dis que les feuilles de l’arbre sont les livres en bordel avant la première étape ? C’est plus clair ? (J’espère…). Au niveau d’au-dessus, les feuilles (livres) sont combinées en ensembles de deux, qu’on combine au niveau d’au-dessus en ensembles de quatre, etc… jusqu’à n’avoir qu’un seul ensemble qui contient tous les livres. Et le nombre d’étapes est précisément égal au logarithme (en base 2) du nombre de livres, ce qui correspond à la « profondeur » (le nombre de niveaux) de l’arbre en question.

Donc, pour conclure, pour n livres, j’ai, dans le modèle que j’ai défini, 2*n*log(n) opérations (où mon log est en base 2).

Voilà, je vais arrêter là pour ce premier billet. Dans le billet suivant, j’expliquerai pourquoi je ne me suis pas trop fatiguée à faire des calculs complètement exacts et pourquoi la phrase que je prononce probablement le plus souvent c’est « pff, c’est une constante, on s’en fout ». (Et peut-être aussi pourquoi des fois on s’en fout pas tant que ça 🙂 ). J’espère que c’était à peu près compréhensible jusqu’ici ; sinon, n’hésitez pas à râler, poser des questions, et tout ce genre de choses. Moi en tous cas je trouve ça rigolo d’écrire tout ça 🙂

Intuition mathématique

Publié le 8 février 20139 novembre 2013 par Balise6 commentaires

Je viens de commencer à rédiger un billet sur la complexité algorithmique, mais je me suis dit que celui-ci venait avant, parce que je ne suis pas à l’abri des tics de langages qui commencent à me venir : « intuitivement », « on voit bien que », « il est évident que ». Christophe m’a d’ailleurs fait remarquer que mon « ça me paraît assez clair » du billet sur les logarithmes (je crois que j’en ai au moins deux) n’était pas forcément des plus heureux. J’avais commencé par intituler ce billet « Compréhension, intuition et créativité », je crois que je vais me limiter au deuxième, parce que ça fait déjà un billet d’un fort beau gabarit ma foi.

J’essaie autant que possible, quand j’explique, d’éviter « l’argument d’intuition », parce que ça m’angoissait pas mal au début quand on me l’offrait et que, justement, je nageais pas mal à comprendre pourquoi c’était intuitif. Notons au passage que ça m’est encore arrivé l’autre jour en examen, de me vautrer sur le « pourquoi c’est intuitif ». Un truc qui me paraissait tellement lumineusement évident que j’en oubliais la raison profonde pour laquelle c’était évident. C’est assez agaçant quand on te le fait remarquer… surtout quand « on » est un examinateur. Mais je m’égare.

Un des articles les plus intéressants que j’ai lus sur le sujet est un article de Terry Tao, There’s more to mathematics than rigour and proofs (et oui, les plus observateurs remarqueront qu’il est en anglais 🙂 ). Il y distingue trois « stades » dans l’éducation mathématique :

le stade « pré-rigoureux » : on fait beaucoup d’approximations, d’analogies, et probablement plus de calculs que de théorie
le stade « rigoureux » : on essaie de faire les choses proprement, de façon précise et formelle, et on manipule des objets abstraits sans avoir forcément de compréhension profonde de ce qu’ils représentent (mais on les manipule correctement)
le stade « post-rigoureux » : on connaît suffisamment son domaine pour savoir quelles approximations et quelles analogies sont effectivement valides, on a une bonne idée rapidement de ce qu’un truc va donner quand on aura fini la preuve/le calcul, et on comprend effectivement les concepts qu’on manipule.

Je m’estime à peu près dans un mélange des trois niveaux 🙂 Je commence à avoir une certaine « intuition » (je reviendrai sur ce que je mets là-dedans), mais j’ai toujours autant de mal à mener un calcul proprement. Et, évidemment, ça dépend des domaines : dans mon domaine, je suis à peu près là ; si on me demande là tout de suite de résoudre des équadiff ou de faire de l’analyse qui tache, je vais probablement me sentir au stade pré-pré-rigoureux :)

Donc, de mon point de vue, les catégories sont évidemment plus fluides que ça, mais je crois que le message est le bon. Et qu’il faut pas paniquer quand la personne en face dit « il est évident/intuitif que » : c’est juste qu’elle a plus de pratique. Et qu’il est parfois difficile d’expliquer ce qui est devenu, avec la pratique, évident. Si je dis « il est évident que 2+3=5 », on sera probablement tous d’accord là-dessus ; si je demande « oui mais pourquoi 2+3=5 ? », on finira bien par me répondre, mais je m’attends à un blanc d’au moins quelques secondes avant ça. Je caricature un peu, mais je crois que c’est à peu près l’idée.

Dans le langage courant, l’intuition a quelque chose de magique, de « je sais pas pourquoi, mais je crois que les choses sont comme ci ou comme ça et qu’il va se passer ci ou ça ». J’ai tendance à me méfier pas mal de l’intuition dans la vie courante, parce que j’ai tendance à me méfier de ce que je ne comprends pas. En maths, la définition est à peu près la même : « je crois que le résultat va avoir cette gueule là, je sens bien que si je déroule cette preuve ça va marcher ». L’avantage de l’intuition mathématique, c’est qu’on peut la vérifier, comprendre pourquoi elle est juste, ou pourquoi elle est fausse. Dans mon expérience, l’intuition - juste - (ou ce qu’on met derrière ce mot) vient surtout avec la pratique, avec le fait d’avoir vu différentes choses, avec le fait d’avoir étudié pas mal, avec le fait de relier les choses les unes aux autres. Je pense que ce qu’on met derrière le mot « intuition », c’est le fait de relier quelque chose de nouveau (un nouveau problème) à quelque chose qu’on a déjà vu, et de faire ça correctement. C’est aussi le fait de reconnaître des « schémas » (j’utiliserais le mot « pattern » si j’écrivais en anglais). Dans le domaine de la complexité algorithmique, qui est le sujet du prochain billet en projet, c’est « je pense que cet algorithme va me prendre tant de temps, parce qu’au final c’est la même chose que celui-là qui est super connu et qui prend tant de temps ». Le truc, c’est que les associations ne sont pas toujours « conscientes » : on se retrouve à voir le résultat d’abord, et à l’expliquer après.

Ça n’empêche évidemment pas de se planter dans les grandes largeurs. Penser qu’un problème va prendre beaucoup de temps à résoudre (algorithmiquement parlant), alors qu’en fait il y a une condition qui le rend facile. Penser qu’un problème n’est pas très difficile, et se rendre compte qu’en fait il va prendre plus de temps que ce que l’on pensait. Enfin, en tous cas, à moi ça m’arrive toujours. J’estime le fait de me planter comme un progrès par rapport à l’étape précédente qui était « mais comment peut-on avoir une quelconque idée sur le sujet ? ».

Je ne sait pas comment se développe cette intuition. Je sais que la mienne est dans un bien meilleur état que ce qu’elle était il y a un an et demi. C’est suffisamment récent pour qu’il m’arrive encore de m’émerveiller sur le fait que des choses sur lesquelles je nageais à l’époque me paraissent maintenant assez naturelles.

C’est aussi suffisamment récent pour que je me rappelle l’angoisse de pas comprendre pourquoi ça peut être intuitif pour certaines personnes. Alors, promis, je vais essayer d’éviter. Mais j’aimerais bien que si jamais ça m’échappe vous me le fassiez remarquer, surtout si ça vous pose problème. Accessoirement, il y a de bonnes chances que si je dis « c’est intuitif », c’est parce que j’ai la flemme de partir dans des explications qui me semblent évidentes (mais qui ne le seraient peut-être pas pour tout le monde). Donc, voilà, je vais essayer de ne pas avoir la flemme 🙂

Et donc, c’est quoi un logarithme ?

Publié le 6 février 20138 janvier 2019 par Balise14 commentaires

Je soupçonne que je vais avoir besoin, dans ma série d’articles d’informatique théorique, de logarithmes. Pourquoi ? Parce que c’est une des fonctions « utiles » lorsque l’on parle de complexité algorithmique. Donc, pour être sûr que tout le monde soit sur la même page, je fais un cours de rattrapage sur les logarithmes. Les gens qui ont de mauvais souvenirs de leurs maths de lycée ont probablement aussi de mauvais souvenirs des logarithmes, et pourtant, les logarithmes, c’est chouette.

En parlant de logarithmes, je ne sais pas comment ils ont été introduits dans vos cours de maths respectifs ; pour ma part, je suis à peu près sûre qu’on me l’a défini à partir de l’intégrale de la fonction inverse. RESTE ICI, C’EST PAS CE QUE JE VAIS FAIRE. Enfin pas tout de suite. Je vais commencer par essayer de donner une intuition du bidule.

Considérons la figure que je viens d’insérer avec brio dans mon billet. Je suis partie d’un point, à partir de ce point j’ai fait deux branches, au bout desquelles j’ai ajouté un point ; sur chacun de ces points, j’ai ajouté deux branches, au bout desquelles j’ai ajouté un point, et ainsi de suite. J’aurais pu continuer comme ça longtemps, conceptuellement – je vais avoir des problèmes de place et des problèmes de fatigue (ça va être pénible très vite d’ajouter des ptits points), mais conceptuellement, je pense qu’on peut tous imaginer un arbre comme celui-ci avec autant de niveaux qu’on le souhaite. Supposons aussi, parce qu’on fait de l’informatique, que la « racine » de l’arbre (le tout premier point que j’ai ajouté sur ma figure) soit au niveau 0. Si je « retourne » l’arbre, ça peut avoir une certaine logique, c’est le « rez-de-chaussée », et le niveau suivant est le « premier étage ». Supposons maintenant que je veuille compter le nombre de « feuilles » de mon arbre, c’est-à-dire le nombre de points que j’ai sur le dernier niveau de mon arbre.

Il est assez clair que le nombre de feuilles dépend du niveau auquel j’arrête mon arbre, et qu’il augmente à chaque niveau. Si je m’arrête au niveau 0, j’ai 1 feuille. Si je m’arrête au niveau 1, je multiplie ça par deux (parce que je fais deux branches), ça fait 2. Si je m’arrête au niveau 2, je multiplie le nombre de feuilles du niveau 1 par deux encore, ça fait 4. Et à chaque niveau, je prends le nombre de feuilles du niveau précédent et je le multiplie encore par deux. Au niveau 3, j’aurai donc 2*2*2 = 8 feuilles et, au niveau 4, 2*2*2*2 = 16 feuilles. Pour connaître le nombre de feuilles au niveau numéro $n$ , où $n$ est le numéro de mon niveau, je fais $n$ multiplications de 2 par lui-même, ce qui s’écrit $2^n$ (et se lit « deux à la puissance $n$ »).

Supposons à présent que je ne veuille pas connaître le nombre de feuilles correspondant à un niveau, mais le nombre de niveaux correspondant à un nombre de feuilles donné. Par exemple, j’ai 2 feuilles : ça correspond au niveau 1. 16 feuilles : ça correspond au niveau 4. Si j’en ai 32, ça correspond au niveau 5. Et si j’ai 128 feuilles, ça correspond au niveau 7. Bon, évidemment, ça se complique un peu si j’ai, mettons, 20 feuilles. 20 feuilles, ça correspond à un niveau « 4 et des poussières » – j’ai dessiné jusqu’au niveau 4, j’ai commencé à dessiner le niveau 5, et j’ai eu la flemme de finir. Cette opération, qui est l’opération réciproque de l’opération précédente, c’est un logarithme. Je dis que c’est l’opération réciproque, parce qu’elle me permet de « défaire » l’opération précédente. Je prends un nombre $n$ , j’en prends la puissance de 2, ça me donne $2^n$ , et si je reprends le logarithme de ça, j’ai

$\log(2^n)= n$

De la même manière, si j’ai un nombre $n$ , que j’en prends le logarithme, et que j’en reprends la puissance de 2, j’ai

$2^{\log n} = n$

Bon, c’est bien gentil, tout ça, mais qu’est-ce qu’il se passe, si au lieu de faire deux branches à chaque étape, j’en fais 3 ? Selon le même raisonnement que précédemment, au niveau $n$ , j’ai 3*3*…*3 feuilles, c’est à dire $3^n$ . Et, bon, ben de la même manière, je peux définir un logarithme qui soit la réciproque de ce $3^n$ . Mais, bon, je veux pouvoir les distinguer – donc je mets la puissance à laquelle ils correspondent en indice, comme ceci :

$\log_2$ , $\log_3$

avec

$3^{log_3 n} = n$

$\log_3(3^n) = n$

L’indice de mon logarithme, on appelle ça la « base » du logarithme. J’en profite pour faire une petite remarque sur le logarithme en base 10 (c’est aussi valable pour les autres bases, au moins entières, de logarithmes, mais je ne rentre pas là-dedans). Il est très facile d’avoir une évaluation « à la louche » du logarithme en base 10 d’un nombre. C’est le nombre de chiffres du nombre en question, moins 1. On a $\log_{10}(10) = 1$ , $\log_{10}(100) = 2$ (parce que $10^2 = 100$ ); tous les nombres entre 10 et 100 ont un logarithme en base 10 entre 1 et 2. De la même manière, on peut estimer que le logarithme en base 10 de 14578 est entre 4 et 5. Pour voir ça, il suffit de voir que 14578 est compris entre $10000 = 10^4$ et $100000 = 10^5$ , ce qui permet de conclure sur la valeur du logarithme. (Je passe un certain nombre de choses sous le tapis ici, en particulier les raisons qui font qu’on peut effectivement conclure ça.)

Bon, cela dit, maintenant que j’ai défini des bases de logarithme, qu’est-ce qui m’empêche d’utiliser des bases « exotiques » pour mes logarithmes ? La réponse est « rien ». Je peux définir un logarithme en base 3.5 (qui correspond à la puissance à laquelle j’élève 3.5 pour obtenir le nombre dont je prends le logarithme en base 3.5), $\frac 5 3$ (qui correspond à la puissance à laquelle j’élève $\frac 5 3$ pour obtenir le nombre dont je prends le logarithme en base $\frac 5 3$ ), ou même $\pi$ (qui correspond à… bon, ça ira, peut-être) si ça me chante. C’est moins « intuitif » si je considère mon explication avec les arbres et le nombre de niveaux (parce que c’est difficile de faire $\pi$ branches), mais en considérant la réciproque des fonctions puissance, ça me paraît raisonnablement clair.

La question suivante qu’on peut se poser, c’est si tous ces logarithmes en différentes bases ont un lien entre elles, ou plus exactement si on peut les exprimer d’une façon commune. La réponse est « oui ». C’est ici que j’introduis le logarithme népérien, aussi appelé logarithme naturel, dénoté $\ln$ . Le logarithme népérien est un logarithme en base $e \approx 2.71828$ . On peut exprimer n’importe quel logarithme dans n’importe quelle base $a$ comme ceci :

$\log_a(x) = \frac{\ln x}{\ln a}$

Ce qui veut aussi dire qu’on peut passer d’un logarithme d’une base $a$ à un logarithme d’une base $b$ comme ça :

$\log_a(x) = \frac{\ln x}{\ln a} = \frac{\ln x}{\ln b} \times \frac{\ln b}{\ln a} = \frac{\ln b}{\ln a}\log_b(x)$

(Et oui, c’est typiquement le genre de chose que j’ai dans mon formulaire d’examen, parce que je me souviens jamais dans quel sens c’est !)

L’important à retenir, ici, c’est que tous les logarithmes sont égaux « à une constante près » ; ils ont le même « comportement asymptotique » (j’introduis les termes ici, mais je ferai un billet spécifique sur le sujet, parce que c’est un peu long à expliquer). C’est intéressant dans le domaine qui nous préoccupe ici, parce qu’on s’intéresse surtout à l’estimation des comportements « à une constante près » quand on parle de temps d’exécution ou d’occupation mémoire d’un algorithme. Encore une fois, j’y reviendrai – prenez ça comme un « spoiler » des prochains épisodes 🙂

J’en arrive à la relation entre le logarithme népérien et la fonction inverse. Formellement, on écrit que

$\ln(x) = \int_1^x \frac 1 t \text{d}t$

Et voilà ce que ça veut dire, graphiquement :

La courbe rouge est la courbe de la fonction $x \mapsto 1/x$ . La zone grise correspond ici à l’intégrale de 1 à 6 ; l’aire de cette zone est égale à ln(6). Et on peut représenter le logarithme népérien de n’importe quelle valeur (supérieure à 1) par l’aire de la surface située entre l’axe des $x$ et la courbe $x \mapsto 1/x$ , prise entre 1 et cette valeur. Remarquons au passage que cette aire est égale à 1 lorsqu’on la considère entre 1 et e, e étant la base du logarithme népérien (parce que ln(e) = 1).

Et pour finir, une propriété intéressante de la fonction logarithme : on peut écrire (dans n’importe quelle base du logarithme)

$\log(a \times b) = \log(a) +\log (b)$

$\log(a/b) = \log(a) - \log(b)$

En tant que réciproque de la fonction puissance, c’est assez clair de voir ça. Étant entendu que si deux puissances d’un même nombre sont égales, alors l’exposant l’est aussi, on a d’une part :

$2^{\log_2(a \times b) } = a \times b$

et d’autre part

$2^{\log_2 a + \log_2 b} = 2^{\log_2 a}\times 2^{\log_2 b} = a \times b$

On peut dériver la deuxième égalité de la même manière – hop, exercice 😛

Notons au passage que c’est à cause de ce genre de propriété que les logarithmes ont été utilisés au départ. Si on a une grosse table avec plein de correspondances « nombre/logarithme », et qu’on veut multiplier deux nombres facilement, on regarde dans la table les logarithmes des deux nombres, on les ajoute (ce qui est vachement plus facile que de les multiplier), et on regarde la valeur correspondante du logarithme (on utilise la table dans l’autre sens) pour avoir la valeur des deux nombres initiaux multipliés. Historiquement, ce genre de tables est apparu au XVIIe siècle (on remerciera M. Napier) pour faciliter les calculs astronomiques ; la règle à calcul fonctionne également sur ce principe ; et tout ça n’a été détrôné que par l’arrivée, plutôt récente, des machines à calculer et des calculatrices…

Bref, les logarithmes, c’est cool. Et j’espère que vous en êtes à présent aussi persuadés que moi 🙂

« Et donc, tu fais quoi en ce moment ? » « De l’informatique théorique. Des maths, en gros. »

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

Ça fait quelques jours que j’ai envie d’écrire des choses un peu plus consistantes que « oh j’ai lu ça, c’était cool ». Plus spécifiquement, il y a une question qu’on me pose relativement souvent : « Et donc, tu fais quoi en ce moment ? ». J’ai beaucoup de mal à y répondre – en général je réponds quelque chose du genre « de l’informatique théorique. Enfin des maths, en gros ». C’est pas très satisfaisant, mais rentrer dans les détails quand on me pose une question « sociale » n’est pas forcément une bonne idée non plus. Mais peut-être qu’il y a des gens qui seraient intéressés par un peu plus de détails, et d’une façon que je pourrais expliquer à quelqu’un qui ne baigne pas dans le domaine depuis un an et demi. Pour donner une idée, j’essaie de viser un niveau « j’ai pas fait de maths depuis le lycée ». Je sais pas trop si je vais y arriver, ça commence à faire un bout de temps que j’ai quitté le lycée, et j’ai fait des maths depuis 🙂

Je vais donc commencer par rédiger un billet très général (celui-ci) pour poser un peu quelques bases ; et après, j’ai la ferme intention de rentrer dans les détails un peu plus. L’idée, c’est que je trouve vachement cool ce que j’étudie en ce moment ; et j’aimerais bien expliquer pourquoi je trouve ça vachement cool. Ça va demander un peu de boulot ; j’hésite limite à faire un premier billet sur « mais, mais, mais… c’est QUOI, un logarithme ? », parce que quand même les logarithmes c’est super utile, mais j’ai peur de faire une insulte à la culture scientifique de mes lecteurs. Je crois que je vais le faire quand même, parce que ça m’amuse moi, et que c’est quand même la raison principale de faire des choses. Et après, je compte faire des billets plus ou moins selon l’humeur du moment. Probablement un peu de complexité, probablement des graphes (j’aime bien les graphes), probablement un peu de probabilités (haha), et les « prérequis » pour tout ça (je suis en train de réfléchir à ce qu’il me faut pour un billet expliquant P/NP, ce qu’est un problème NP-complet, et la grande question de savoir si P = NP, je ne suis pas la première à me frotter à ce genre de billet, mais je pense que l’exercice didactique est intéressant 🙂 )

Je digresse déjà, c’est pas gagné. Revenons à nos moutons. Je suis actuellement en master d’informatique, spécialisation informatique théorique, de l’ETH à Zürich. Les modalités « usuelles » sont de faire 60 crédits de cours, généralement en deux-trois semestres, suivis d’un semestre de projet de recherche (avec rapport et soutenance à la fin, classique). Il se trouve que j’ai pris des chemins un peu détournés pour mon master, et que de fait je vais rentrer dans mon 4e semestre de cours, mais c’est pas vraiment la question ici.

« Mais c’est quoi, l’informatique théorique ? » seriez-vous peut-être tentés de me demander. La première réponse qui me vient à l’esprit, c’est que c’est la théorie de tout ce qu’on peut faire avec un ordinateur. Au cœur de tout ça, il y a la notion d’algorithme. Un algorithme, c’est simplement une suite d’instructions. On peut par exemple penser à une recette de cuisine comme à un algorithme :

Pour faire de la béchamel, il me faut du beurre, de la farine et du lait.
Mesurer des quantités égales de beurre et de lait.
Dans une casserole à feu moyen, faire fondre le beurre et y incorporer la farine jusqu’à obtenir une pâte épaisse.
Tant que la béchamel n’a pas la consistance souhaitée, ajouter du lait et mélanger.
Si on le souhaite, ajouter du sel, du poivre, de la muscade ou du fromage râpé.

On a une suite d’instructions (qui sont numérotées), qui peuvent être répétées (tant que la béchamel n’a pas la consistance souhaitée) ou qui ne sont exécutées que dans certaines conditions (on n’ajoute de la muscade que si on le souhaite).

De façon plus « classique », on peut aussi penser à l’algorithme de la division que tout le monde étudie à l’école primaire.

Je suis un peu biaisée sur les catégories de ce qu’on peut faire rentrer dans l’informatique théorique, parce qu’il y a des domaines que je connais bien mieux que d’autres, mais en voici une liste explicitement non exhaustive (si j’oublie votre domaine favori… c’est que je ne sais pas quoi en dire, n’hésitez pas à expliquer en commentaire). Pour une liste un peu plus complète, je vous renvoie sur l’article correspondant de la Wikipedia : Informatique théorique, qui reprend lui-même la liste de SIGACT (une grosse société savante du domaine, en gros). Quant au fait que « je fais des maths », l’informatique théorique est souvent considérée comme une branche des maths discrètes ; et en pratique, prouver qu’un truc marche implique de faire de jolies preuves pleines de jolies maths 🙂 (Ou de moches maths, mais c’est nettement moins satisfaisant.)

Je me permets un certain nombre d’approximations ici (en particulier je fais la confusion entre un problème et une instance d’un problème), j’essaie de faire simple sans faire de paragraphe à rallonges. Ceux qui savent de quoi je cause corrigeront d’eux-mêmes ; pour les autres : c’est une première approximation, qui n’est par définition pas exacte, mais que j’ai l’intention d’affiner dans les billets qui suivront.

L’algorithmique. Étant donné un problème, comment le résoudre avec un algorithme, comment prouver que la méthode de résolution (l’algorithme) qu’on propose est effectivement correcte, et combien de temps faut-il pour avoir un résultat ?
La théorie de la complexité. Ça inclut, mais pas seulement, le point « combien de temps il faut pour avoir un résultat » du point précédent. On s’intéresse aussi ici à la question : étant donné un problème, quel est le temps minimum et la consommation de mémoire minimum qu’il me faut pour le résoudre ?
La théorie des graphes. Un graphe est une structure mathématique composée de points (les « sommets » du graphe) et de traits (les « arcs » du graphe). Un exemple de graphe pourrait être la carte d’un réseau de métro : les stations sont les sommets, les arcs sont les connexions d’une station à une autre par une ligne de métro. En théorie des graphes, on s’intéresse aux propriétés de ces graphes (par exemple : est-ce que je peux aller d’un point à un autre ; quel est le plus court chemin d’un point à un autre ; si je supprime ce sommet là (ou, dans l’analogie précédente, si je ferme ma station de métro), est-ce que je peux toujours aller de mon point A à mon point B), et aux algorithmes pour décider ces propriétés (comment je fais pour déterminer quel est le plus court chemin d’un point à un autre du graphe).
Les structures de données. Comment stocker les données du problème qu’on cherche à résoudre, de la façon la plus efficace possible (en temps et en mémoire) pour le problème en question ? Ou, pour reprendre mon exemple précédent, comment stocker la carte du réseau de métro pour faire des calculs dessus ?
La géométrie algorithmique. Comment représenter et résoudre avec un ordinateur des problèmes qui touchent à la géométrie ? Un exemple typique est celui du « bureau de poste » : étant donné l’emplacement de tous les bureaux de poste d’une ville, comment déterminer efficacement celui qui est le plus proche de ma maison ? Si je ne cherche que celui qui est le plus proche de ma maison, je peux calculer la distance entre ma maison et tous les bureaux de poste ; mais comment faire ça plus efficacement si je cherche à définir, pour toutes les maisons de la ville, le bureau de poste le plus proche ? Et qu’est-ce que je fais si je veux ajouter/supprimer un bureau de poste ?
L’impact de l’aléatoire dans tout ça – pour certains algorithmes, il est intéressant d’ajouter une part de hasard dans les calculs (je lance une pièce, si elle fait pile mon algorithme fait ceci, si elle fait face mon algorithme fait cela). Quel impact ça a sur les algorithmes – en particulier sur le fait qu’ils renvoient le résultat correct ou non, et comment évaluer le temps nécessaire à résoudre (correctement) un problème avec un algorithme aléatoire ? L’étude de certaines structures aléatoires a aussi un intérêt en soi. On peut par exemple définir des graphes aléatoires : on prend un ensemble de points, et on ajoute un arc entre deux points selon une certaine probabilité. Selon la manière dont on définit un graphe aléatoire, il peut s’avérer un assez bon modèle d’un graphe de réseau social (qui est ami avec qui)… ou du cerveau humain.
La cryptographie. Si Alice veut envoyer un message à Bob en étant sûre qu’Ève ne puisse pas le lire, et si Bob veut être sûr que le message qu’il vient de recevoir provient bien d’Alice, comment faire ? Et surtout, comment prouver qu’effectivement Ève ne peut pas lire le message, et que Bob peut être sûr de la provenance du message ?
[EDIT] La calculabilité, comme on me le signale en commentaire. Il se trouve qu’on ne peut pas tout résoudre avec un algorithme, et qu’on peut même prouver que certaines choses ne peuvent pas être être calculées avec un algorithme. L’exemple le plus célèbre est celui du « problème de l’arrêt », c’est un peu méta, mais j’espère que vous me le pardonnerez. On peut prouver qu’il n’existe pas de programme qui décide si un programme donné finit par s’arrêter et à renvoyer un résultat. La preuve est jolie, même si elle fait un peu mal au crâne la première fois qu’on y est confronté ; j’en ferai peut-être un prochain billet 🙂

Voilà, tout ça, c’est des trucs dans lesquels j’ai au moins des notions de base. L’informatique théorique regroupe encore pas mal de choses dans lesquelles mon niveau de connaissance est à peu près nul : la théorie de l’information (à ma grande honte), l’apprentissage automatique (ou comment réussir à faire reconnaître des photos de chat à un ordinateur), les méthodes formelles (ou comment réussir à prouver que mon programme n’a pas de bug), l’informatique quantique (sait-elle mieux reconnaître une photo de chat que l’informatique classique), la bio-informatique (comment déterminer si deux séquences ADN sont proches ou non) et j’en oublie encore probablement un peu.

Notons accessoirement que faire rentrer ceci ou cela dans le domaine de l’informatique théorique peut toujours prêter à débat. Je ne suis par exemple pas convaincue de la présence de l’apprentissage automatique dans l’informatique théorique, parce que ça me paraît encore très expérimental (on a modifié ce paramètre là et par conséquent l’ordinateur reconnaît 2.2% de plus de chats). La Wikipedia parle d’informatique distribuée et concurrente (l’art d’utiliser plusieurs ordinateurs à la fois pour exécuter des programmes) comme faisant partie de l’informatique théorique. Je suis d’accord que l’intersection n’est pas nulle – mais je ne considérerais pas l’informatique distribuée comme un sous-ensemble de l’informatique théorique. Idem pour la bio-informatique ; certains éléments en font partie (l’exemple des chaînes ADN par exemple), mais je ne suis pas sûre que tous les bio-informaticiens se définissent comme des informaticiens théoriques 🙂

Je pensais que ce billet serait relativement court ; je crois que c’est un échec cuisant de ce point de vue. J’espère qu’il était cependant vaguement intéressant ; et s’il y a des choses que vous pensez que je peux traiter dans un futur billet de cette catégorie… ben n’hésitez pas 🙂

	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:

Un premier tri

Une autre méthode de tri

Flattr:

WordPress:

Flattr:

WordPress:

Flattr:

WordPress:

Flattr:

WordPress: