Étiquette : maths

Le problème SAT

Publié le 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 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 :

3clique

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

carre

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 :

bipartite

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 :

8clique

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 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.

Intuition mathématique

Publié le 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 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.

arbre

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

et

\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 :

log

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 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 :

  1. Pour faire de la béchamel, il me faut du beurre, de la farine et du lait.
  2. Mesurer des quantités égales de beurre et de lait.
  3. Dans une casserole à feu moyen, faire fondre le beurre et y incorporer la farine jusqu’à obtenir une pâte épaisse.
  4. Tant que la béchamel n’a pas la consistance souhaitée, ajouter du lait et mélanger.
  5. 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 🙂

En vrac

Publié le par Balise2 commentaires

Hop, une liste de trucs marrants vus ces derniers jours/semaines/mois. C’est guère que de la « resucée » de Google+, mais comme ça je garde aussi trace de ces trucs là 🙂  Pas vraiment d’ordre, c’est du vrac. Et heu, ya à peu près presque de l’anglais.

bon, j’vais ptêt arrêter là ?

Mon formulaire d’examen

Publié le par Balise3 commentaires

Puisqu’il suffit visiblement d’écrire pour avoir des choses à écrire, je viens de mettre en ligne la version courante de mon « formulaire d’examen » – le truc qui me sert de « doudou » et de référence rapide pour les trucs que je suis susceptible d’utiliser et d’avoir oubliés (parce que j’ai pas de mémoire ou parce que je panique). C’est évidemment relativement personnel, et je pense être la seule personne au monde à mettre une table de multiplication sur ce genre de trucs, mais, bon, je trouve ça rigolo de manière générale de voir ce genre de choses, donc peut-être que ça peut en amuser d’autres.

Le machin est là : formulaire d’examens, en anglais et en maths dans le texte 🙂

(Pour la petite histoire sur les tables de mult’, je me souviens avoir eu beaucoup de mal à les apprendre. J’ai aussi comme souvenir, mais c’est peut-être du souvenir regénéré a posteriori, d’avoir codé un machin en Basic pour m’interroger sur mes tables de mult’ :P)

Bon, et peut-être plus utile, mon collègue Haffi vient de me signaler une Theoretical Computer Science Cheat Sheet, qui est un peu très amour, en fait. Voilà, pour la complétude de la chose 🙂

En vrac

Publié le par Balise1 commentaire
  • C’est petit et mesquin, tant pis
  • Mais non le java c’est pas lourd ! (comme le confit, quoi) (oui, j’ai vu le Bonheur est dans le pré pour la première fois quand c’est passé à la télé en hommage à Michel Serrault, je n’ai qu’un regret, ne pas l’avoir vu plus tôt !!)
  • La news people du jour : Brian May (guitariste de Queen) a rendu son mémoire de thèse d’astronomie aujourd’hui, faut dire que ça traînait depuis trente ans. (Me demande où en est son directeur de thèse d’ailleurs….. !) Bon, faudrait bien que ça me motive à finir la mienne 🙂
  • Un bouquin de maths « spécial filles »… Je suis dubitative. Certes, ça paraît une bonne idée d’essayer de « recruter » les filles en maths… Mais il y a quand même quelque chose qui me tititlle. Ça fait un peu « Barbie t’explique les maths, OUAIIIIS ! » (hurlements hystériques). Disons que ça me paraît « yet another way » de renforcer les stéréotypes…