Aux origines de zéro

On 21.10.2012, in Dossiers, by Nicotupe
VN:F [1.9.22_1171]
Rating: 4.8/5 (6 votes cast)

Dans ce dossier, nous allons raconter la longue histoire de la découverte d’un nombre. Un simple nombre qui pourtant a tout changé et permet aujourd’hui l’existence des plus grandes théories (mle grand saut desais ça, nous le verrons la semaine prochaine). Eh oui, après vous avoir parlé de l’infini, de pi, aujourd’hui on s’attaque au zéro!

La vie sans rien

Mais avant de parler du zéro lui même, nous allons un peu parler du temps où l’on vivait sans cet étrange nombre. On a peu de traces avant l’apparition de l’écriture, pour autant, on peut avoir des indices sur l’existence sans le nul en observant notre vie contemporaine. On se rend alors vite compte que l’on n’a pas vraiment besoin de lui dans notre vie de tous les jours : personne n’a besoin d’aller acheter zéro baguettes, d’inviter zéro amis à une soirée ou de passer zéro secondes sur un travail (surtout ce dernier point, qui est un sous-entendu universel de l’humanité procrastinatrice). Ou plus précisément, on peut en avoir le besoin mais alors on a pas besoin de l’exprimer : je ne vais pas lister tous les produits dont j’ai besoin sur une liste en mettant un zéro dessus!


En fait, à l’aube des temps humains, les gens faisaient apparement seulement la distinction entre un et beaucoup. On était capable de dire s’il y avait un arbre. Et s’il y en avait plus, il y en avait tout de suite beaucoup. Remarquons que cela aussi est peu différent aujourd’hui, du moins sans compter, tant qu’il y a 4–5 objets, on est capable de tout de suite dire leur nombre et ensuite il y en a “beaucoup” (faites le test chez vous, ça marche!).

Les hommes réussissaient quand même à différentier les groupes, en utilisant la bijection! Comme on l’a vu dans le dossier sur l’infini, en plaçant sur le sol un caillou à chaque objet que l’on voit, on peut savoir qu’il y a plus d’éléments dans un groupe qu’un autre sans compter. Mais pour y arriver sans bijection et de manière absolue, il faut savoir compter… Et donc les hommes se sont mis à compter justement. Et comme il ne savaient pas forcément encore écrire, ils utilisaient ce qu’ils avaient de plus facilement disponible : les parties de leur corps!  L’évolution, la selection génétique et beaucoup de hasard nous ont amenés à avoir 5 doigts sur chaque main et pied. On pouvait alors facilement compter jusqu’à 5 et quand il fallait plus, on donne un nom au 5 et on pouvait recommencer à 1, histoire de pouvoir continuer à compter avec les parties de son corps :

1,2,3,4,5,5 et 1,5 et 2, 5 et 3, etc.

Et il suffisait d’avoir un nouveau mot pour 10, 15, 20, 25, etc. pour pouvoir compter autant qu’on voulait.

C’est ce qu’on appelle compter en base 5! Et hasard de l’anatomie, 5 est justement la base préférée des hommes quelle que soit la culture. Il y avait d’autres bases aussi, le plus souvent liées à une partie de notre corps : 5, 10 (deux mains), 20 (mains et pieds) et… 60 qu’utilisaient les Babyloniens!

Remarquez que ces systèmes de numérotations ressemblent beaucoup au système romain (même s’il est postérieur), que l’on connait tous.

Avec ces systèmes, les gens pouvaient compter. Pour autant, ces systèmes n’avaient pas de zéro; ce concept n’existait tout simplement pas! Pour dire qu’on a zéro baguette, il suffit de dire “nous n’avons pas de baguettes”, aucun besoin de créer un nombre pour exprimer le manque de quelque chose! Les gens vécurent longtemps sans zéro car ils n’en avaient pas besoin. Et dans les esprits de cette époque, il aurait été bien saugrenu de créer un symbole pour représenter ce rien.

Un rien facilite le comptage

Les Grecs, les Egyptiens et la plupart des peuples anciens avaient des systèmes plus ou moins sophistiqués mais tous basés sur cette même idée. Le peuple qui a vraiment révolutionné la numérotation (tout comme il révolutionna bien d’autres choses) sont les Babyloniens.

Les Babyloniens représentaient les chiffres comme s’ils dessinaient symboliquement un abaque. Chaque groupe de symboles représentait le nombre de pierre qu’on avait déplacé sur l’abaque. La véritable nouveauté de ce système est que, comme le nôtre, il fonctionnait par colonnes. L’unité babylonienne ressemble à un Y ou à un clou. Quand un Babylonien écrivait YYY, le premier symbole représentait les “centaines”, le second les “dizaines” et le troisième les “unités”. Si je met ici des guillemets c’est que les Babyloniens ne comptaient pas comme nous, mais en base 60. Ainsi, le premier Y représentait en fait 3600, le second 60 et le troisième 1. Comme nous écrivons 123 pour dire en fait 1×100+2×10+3, les Babyloniens écrivaient YYY pour dire 1×3600+1×60+1.

Reste qu’aussi ingénieux soit-il, ce système présentait un problème de taille. Le nombre YY pouvait aussi bien vouloir dire 3601 que 3660 ou encore 61. En effet, si l’un des chiffres de la décomposition dans la base ne présentait pas d’éléments, les Babyloniens se contentaient de laisser un espace. Il était alors très difficile de différencier les chiffres avec précision. A la recherche d’une solution pour palier ce problème, les Babyloniens ont inventé le zéro! A cette époque, il n’est pas encore un nombre, il se contente seulement d’être la représentation d’un espace, un rien mais qui permet déjà de lever toute ambiguité sur le système de numérotation. C’est autour de 300 avjc que les Babyloniens ont commencé à utilisé cet espèce de Y penché pour le zéro.

Reste que ce zéro là n’était pas un nombre, c’était juste un espace dans le système de numérotation, une ponctuation des mathématiques, en somme. Les Babyloniens auraient par exemple été bien incapable de le classer parmi les autres nombres et l’auraient peut être amené à la droite du 9 comme sur nos claviers, les malheureux! Les Babyloniens n’étaient pas les seuls à utiliser un système de numérotation où les chiffres étaient sur des colones, les Mayas aussi. Et eux choisirent justement de commencer à compter à partir de zéro. Reste qu’à cette époque, zéro n’est pas encore réellement un nombre ou du moins on n’a pas retrouvé d’utilisation mathématique.

Le vertige des Grecs

Les grecs détestaient le zéro. Ils avaient pourtant connaissance du système babylonien qu’ils utilisaient entre autres pour leur calculs astronomiques mais se dépêchaient de le reconvertir dans leur système pur, sans ce nombre vide. Il est à noter que les grecs écrivaient le zéro “o” pour omikron, dont la ressemblance avec notre zéro actuel est un pur hasard, on va rapidement voir pourquoi.

Une des premières raisons de cette détestation de ce simple nombre est que selon les croyance grecques, avant la création, il y avait le vide et le chaos ; zéro leur était alors inexorablement associé.

Mais ce n’était pas la seule raison de ce rejet, loin de là! Le zéro était en contradiction ou pire, paradoxal, pour la plupart des croyances grecques. Par exemple zéro additionné à lui même reste le même nombre nul. Ce qui contredit directement le principe d’Archimède qui dit qu’en ajoutant n’importe quel nombre à lui-même suffisament de fois, on dépasse tout nombre. De plus, les grecs avaient une vision géométrique des nombres; n’importe quel nombre était associé à un segment, une multiplication revenait alors à dilater le segment et une division à le contracter. Mais à quoi correspondrait une multiplication par zéro? Et à quel type de segment correspondrait ce nombre étrange?  Comme n’importe quel nombre multiplié par zéro donne justement zéro, le segment est cassé de manière irréversible, zéro est une brute qui casse tout ce qu’il touche, les grecs n’en veulent pas!

De nous jours, la définition de zéro est justement qu’additionné à n’importe quel nombre, il laisse le nombre inchangé. En revanche, le fait que sa multiplication par n’importe quel nombre donne zéro se démontre! L’ensemble des nombres entiers relatifs (qui n’existe pas encore certes, mais c’est ici une apparté!) ou plus simplement nommé ensemble de tous les nombres entiers positifs est ce que l’on appelle en mathématiques un groupe pour l’addition. C’est à dire qu’il respecte les 4 règles suivantes :

  • Si l’on prend deux nombres quelconques de ce groupe, leur somme appartient aussi au groupe. Par exemple 2 et 5 sont des entiers relatifs et leur somme 7 aussi.
  • L’addition respecte l’associativité. C’est à dire qu’on peut changer la place des parenthèses : 2+(3+4)=(2+3)+4
  • Le groupe possède un élément neutre, c’est à dire un élément ‘e’ tel que pour n’importe quel nombre ‘a’, a+e=e+a=a. C’est justement cet élément neutre que l’on appelle zéro pour l’addition.
  • Chaque élément possède un inverse. C’est à dire que pour chaque nombre ‘a’, il existe un nombre ‘b’ tel que a+b=e, l’élément neutre. Par exemple, pour 5, il existe -5 tel que 5+(-5)=0!
Lorsque l’on a ces 4 règles très simple, on peut faire la plupart des opérations que vous utilisez quotidiennement. Mais bien sûr on n’utilise pas que l’addition, il existe aussi la multiplication. Dans ce cas, ça se complique un peu car tous les entiers n’ont pas un inverse entier, par exemple si 2 est bien entier, son inverse 1/2 ne l’est pas. Du coup, pour avoir un groupe avec la multiplication, il faut prendre un groupe plus grand, par exemple les rationnels. Pour rappel, l’ensemble des rationnels, c’est l’ensemble des fractions, c’est à dire les nombres qui sont le quotient de deux entiers : 2/3, 6/7, etc. L’ensemble des rationnels privés de zéro (on va y revenir tout de suite) est justement un groupe pour la multiplication. Vous pouvez vérifier, les quatre règles sont respectées!
Alors si l’on résume, l’ensemble des rationnels est un groupe pour l’addition et est un groupe pour la multiplication si on le prive de zéro. Mais comme on veut toujours plus, on va vouloir un ensemble ou l’on peut utiliser les deux opérations en même temps. C’est grosso-modo ce que l’on appelle un anneau. Dans un anneau, il y a donc deux neutres, un pour l’addition (zéro) et un pour la multiplication (un). le Un était déjà dans le groupe pour l’addition, donc on sait faire des additions avec. En revanche, le zéro n’étant pas dans le groupe de la multiplication, on ne sait pas comment il réagit lorsqu’il est multiplié, il est nécessaire de le démontrer!

Prenons par exemple 4 (ça marche bien sur avec tous les nombres), En utilisant la factorisation et la propriété du neutre pour l’addition, on peut écrire :

0×4+0×4=4x(0+0)=4×0

En simplifiant par 4×0, on obtient 4×0=0. Le zéro transforme par la multiplication n’importe quel nombre en lui-même!

[Dessin - Les mathématiciens savent démontrer que 0x0=0)

Revenons à nos grecs anciens. Le zéro transformait donc  le nombre-segment grec en un point, on détruisait le segment, ce qui était impensable dans la pensée grecque et surtout enlevait toute possibilité d’inversion du phénomène… Mais justement, que se passait-il si on divisait par zéro?

Tout le monde le sait depuis la petite école, comme il est interdit de prononcer le nom de “vous savez qui”, il est INTERDIT DE DIVISER PAR ZERO. C’est un phénomène assez amusant et aussi l’objet d’un mème! En fait il n’est pas exactement interdit de diviser par zéro, c’est juste que si vous vous l’autorisez ne serait-ce qu’une seule fois, vous pouvez démontrer tout et n’importe quoi. Par exemple, nous allons démontrer avec une division par zéro un bien joli résultat.

On sant que pi x 0 = 42 x 0 car tout nombre multiplié à zéro fait zéro. Une division par zéro plus tard on a alors

pi=42.

Jusque ici rien de très étonnant, on savait depuis longtemps que 42 était la réponse à tout ce qui existe mais comme on a pu le voir dans le dossier sur le théorème de Gödel ou celui sur l’infini, s’autoriser une contradiction (bah oui parce que pi n’est pas égal à 42) amène à une théorie contradictoire où tout résultat et son contraire est vrai. Alors certes on peut s’amuser à diviser par zéro mais alors, plus rien n’a de sens!

Le rejet du zéro par les grecs était avant tout philosophique, il représentait une réelle plaie pour la pensée de l’époque, un peu comme le furent les irrationnels. Remarquons que l’infini avait déjà pas mal agacé les grecs entre autrse avec le paradoxe de Zénon. En fait, zéro et infini sont intimement liés, comme nous le verrons plus en détail la semaine prochaine.

Mais celui qui a de loin le plus empêché le zéro d’arriver pleinement chez les Grecs à cette époque-là et plus tard en Europe est Aristote. En effet, sa pensée a influencé l’Europe pendant les siècles suivants et il était le plus fervent opposant au nombre étrange. Cette opposition d'Aristote a laissé aujourd'hui quelques restes comme l'expression "la nature a horreur du vide".

Des particules élémentaires oui mais sûrement pas du vide

A l’époque, la théorie des atomes commençait à naître. Or les atomes impliquent d’avoir du vide, en effet, entre ces atomes il y a beaucoup de vide… et dans l’univers, la théorie atomiste imposait un vide infini. Pour exemple, si l’on retire le vide de tous les atomes de l’empire state building, on obtient quelque chose pas plus grand que la taille d’un grain de riz.

Aristote refusait de croire au vide, il acceptait l’idée de particules élémentaires mais rejettait la notion d’atomes et considérait que toute la matière était constituée des 4 éléments : Eau, Feu, Air et Terre. Et il considérait la matière comme continue, ne s’interrompant jamais. Il est assez ironique de remarquer que les théories modernes de cosmologie reviennent sur cette notion de vide absolu en donnant non seulement une courbure à ce vide (avec la relativité générale) ou encore en postulant que le champ de Higgs est partout et interagit sur les particules.

Reste que pour palier ce problème avec le vide et surtout avec l’infini, les philosophes de l’époque complétèrent la théorie atomiste d’une manière particulièrement poétique. Ils postulèrent que l’univers était en fait dans une gigantesque sphère, où, bien sûr, la Terre était au centre. Cette sphère englobante était un globe bleu, incrusté de petits points brillants : les étoiles. L’univers devenait fini et Aristote déclarait que les mathématiciens n’avaient pas besoin d’infini, ni de l’utiliser. Or pour rejeter l’infini, il faut rejeter le vide, les deux sont intimement liés. En effet, a partir du moment où l’on accepte l’existence du vide, comme zéro ajouté à lui même reste zéro, il y a aussi une infinité de vide!

Pour l’anecdote, Archimède calcula qu’il fallait 1051 grains de sable pour remplir la sphère de l’univers. Ce nombre était tellement grand que le système de numérotation grec ne pouvait pas l’écrire!

Ce système a perduré pendant de nombreux sciècles pour une raison très simple: il prouvait de manière irréfutable l’existence de Dieu. La grosse sphère incrustée de points lumineux qui englobait l’univers tournait et il fallait bien une force extérieure pour la faire tourner, cela ne pouvait être que Dieu!

1400 ans sans entendre parler de rien et le bug de l’an 2000

Une fois qu’Aristote eut fait son oeuvre, impossible pour le zéro d’entrer en Grèce. Et avec l’invasion des Romains, le neutre fut rayé d’Europe pendant plus de 1400 ans… Les 7 sciècles d’ère romaine n’ont pas spécialement marqué l’histoire mathématique, l’auteur de “Zero, Biography of a Dangerous Idea”, qui a servi de base à ce dossier résume cela en disant que le meurtre d’Archimède fut sans doute la contribution la plus notable des Romains à cette science!

Pour s’en convaincre plus encore, il suffit de regarder leur système de numérotation que l’on utilise tous encore parfois; il est bien loin de l’innovation Babylonienne. Pendant les 7 sciècles qui suivirent les romains, le zéro ne montra pas non plus son nez, ce qui laissa tout le temps aux moines de faire n’importe quoi…

Les moines à cette époque n’avaient besoin des maths que pour deux activités : la prière et l’argent. Pour organiser les prières, il était nécessaire de créer un calendrier et c’est exactement ce à quoi s’attela Dyonysius Exiguus sur les ordres du pape Jean 1er. En traduisant des tables provenant de l’Est du continent, il découvrit qu’il pourrait calculer la date de naissance de Jésus Christ. En faisant rapidement quelques calculs, il décida que l’année courante était la 525e année depuis la naissance du Christ (soit dit en passant, il s’était en fait trompé de 4 ans…).Et en toute logique, il choisit l’année 1 pour la naissance du Christ. Remarquez que l’on refuse aussi de dire qu’un bébé a zéro ans. Pendant sa première année, on commence à compter en jours, puis en semaines, puis en mois, puis enfin en années en banissant la phrase toute simple “il est beau hein, il a zéro ans”. Il est quand même balo que pour mettre le Christ au centre de leur calendrier, les moines ont tout simplement oublié son année de naissance.

Le zéro ayant été bani par Aristote, les années s’organisaient donc sans lui

… –2 –1 1 2 …

Cette simple décision nous fait encore aujourd’hui faire des erreurs. Par exemple, 6 milliards de personnes (ce n’esst pas rien) ont fêté le nouveau millénaire un an trop tôt, sans année zéro, celui-ci commence en 2001!

[Dessin d'un mec tout seul dans son lit pendant que les mec font la fete à la fenetre "Les cons!"]

Mais pire encore, comme on l’a vu au-dessus, sans zéro, pas de neutre et donc pas de groupe au sens mathématique; on n’a plus le droit aux soustraction sans erreurs… Grâce à ce zéro, on peut inverser l’opération d’addition et simplifier les équations, c’est ce qui nous permet d’écrire que

x+5=3

est équivalent à

x=5–3=2

Sans ce neutre, on ne peut plus faire tout ça! Reprenez la ligne des nombres sans zéro de tout à l’heure :

… –5 –4 –3 –2 –1 1 2 3 4 5 …

5, à qui l’on soustrait cinq unités donne –1 : 5–5=1. Mais pire encore, 5+(–5)=1. L’addition n’est même plus commutative! Sans cette simple année zéro, on ne peut pas soustraire des dates, et on ne peut pas additionner indifféremment des dates positives avec des dates négatives ou des dates négatives avec des dates positives! C’est exactement ce type d’erreur que fit le Washington Post en annonçant fièrement que comme le Christ était né en –4, le nouveau millénaire devait être fêté en 1996!

A titre de remarque, cette notion de neutre est indispensable pour pouvoir inverser une opération. Dans le cas de la multiplication, c’est le 1 qui joue ce rôle de neutre.

Quant au fait de compter les années à partir de la naissance de Jesus Christ plutot qu’un autre, sachez que les astronomes utilisent une autre référence, elle aussi complètement arbitraire, mais pas biblique, en particulier pour y ajouter le zéro et faciliter les calculs.

Mais si nous avons autant fêté l’année 2000, c’est avant tout parce que l’on aime les nombre avec pleins de zéros! Malgré la lutte d’Aristote pour le faire disparaître, qui n’a jamais joué avec le compteur d’une pompe à essence pour tomber sur le nombre rond, qui n’a jamais attendu qu’un réveil à chiffres affiche l’heure pile?

Le grand saut des Indiens

La fin de l’histoire de la découverte du zéro est moins épique. C’est chez les Indiens qu’il réapparaît. Les Indiens n’avaient ni peur du vide ni de l’infini. Le cosmos hindou était infini et pour eux, tout avait été créé à partir du vide. Les indiens appréciaient donc le zéro. Ils passèrent d’un système grec à un système Babylonien en base 10. Nos chiffres sont des évolutions de leurs chiffres et ne méritent donc pas vraiment l’appellation de chiffres “arabes”.

C’est en 628 qu’est défini le zéro dans le traité de Brahmagupta. Il définit ce nombre comme la soustraction d’un nombre par lui-même. Les Arabes récupèrent alors ces écrits, les traduisent et importent ainsi le zéro.

Pendant ce temps, en Europe on continue à utiliser le système romain pourtant bien peu pratique pour faire des mathématiques. La peur du vide est toujours là mais grâce aux marchés, le zéro aura le dernier mot! La première étape est de retirer certaines doctrines un peu absurdes en postulant qu’Aristote n’a pas à décider ce que Dieu peut faire ou non!

Fibonacci, un mathématicien italien, influencé par les Arabes, introduit le zéro en Europe dans son livre où il présente la fameuse suite qui porte son nom. Les marchands, ayant besoin de faire des opérations sans erreurs adoptèrent très rapidement le nouveau nombre… Le zéro est enfin arrivé en Europe!

Sources :

Suite (et fin) du dossier:

» Zéro et l’Infini… Une’histoire d’amour impossible

VN:F [1.9.22_1171]
Rating: 4.8/5 (6 votes cast)
Tagged with:  

L'histoire de la recette de cuisine

On 18.04.2012, in Dossiers, by Nicotupe
VN:F [1.9.22_1171]
Rating: 4.8/5 (4 votes cast)

Pour un troisième dossier, on s'attaque aujourd'hui à un sujet très vaste, sans aucun doute le plus vieux de l'histoire des sciences… Lors du dossier sur Pi, nous avions pu découvrir que dès que l'homme a su écrire, il a parlé de la constante célèbre. Force est de constater que depuis que l'homme existe, il existe des algorithmes même si ce n'est que très récemment (au début du XXe siècle) qu'une définition formelle à commencé à se montrer. Je serais même tenté d'affirmer que certains animaux usent d'algorithmes, mais devant ma méconnaissance du sujet, je laisserai des personnes plus compétentes apporter leur contribution une fois le dossier assimilé!

Un algorithme? Mais koikeskecédonc?

Depuis que l'homme existe donc et encore aujourd'hui, tout le monde utilise tous les jours, toutes les heures des algorithmes… Pour autant peu de personnes connaissent le mot et moins encore la définition exacte et cela est bien compréhensible tant elle est finalement complexe! Pourtant, l'idée est assez simple, voire même naturelle : une méthode qui, à partir de plusieurs données permet d'obtenir un résultat. Si cette définition n'est pas suffisamment précise pour bâtir une théorie mathématique, elle est suffisante pour donner à ce stade quelques exemples.

Commençons donc par le plus célèbre des algorithmes, celui que l'on a tous utilisé au moins une fois, celui qui est aussi vieux que l'invention du feu (ou presque) : la recette de cuisine! Dans toute bonne recette, à l'image de celle ci-dessous (provenant de l'excellent blog la foodbox), on a exactement les mêmes éléments…

Romanesco
Recette

Le nom nous permet de savoir à quoi sert cette recette, la liste d'ingrédients assure que l'on ait tous les outils et éléments nécessaires à sa réalisation. La procédure à suivre permet à n'importe qui, cuisinier ou non, intelligent ou non, de produire cette réalisation complexe. Les variantes et autres tests permettent de s'adapter à la situation et à l'envie.

Cet exemple traduit très bien l'idée partagée par nombre de scientifiques de la notion d'algorithme après l'apparition de ce mot au IXe siècle. L'origine du mot algorithme est arabe, il correspond à la traduction du nom du mathématicien Al-Khwārizmī qui a accessoirement écrit un ouvrage qui a permis de propager en Europe l'écriture décimale positionnelle des nombres inventée par les Indiens (c'est celle que nous utilisons encore aujourd'hui). S'il n'y a pas aujourd'hui de définition simple communément acceptée de la notion d'algorithme, on y retrouve toujours les idées suivantes :

  • Le dictionnaire de symboles, de mots est limité. Il se veut aussi simple et précis que possible. Dans le cas de la recette, ce dictionnaire de symboles est l'alphabet occidental accompagné de la ponctuation et des chiffres;
  • On doit obtenir le résultat en un nombre fini d'étapes;
  • Il doit pouvoir être suivi par un humain en ne nécessitant aucune intelligence, tout au plus, la capacité d'exécuter les différentes instructions. Cet aspect est particulièrement important pour les recettes. Si elles sont largement diffusées et utilisées, c'est entre autres parce qu'elles permettent d'obtenir un résultat proche du restaurant sans aucune connaissance préalable de cuisine.

À partir d'une définition aussi générale, vous comprendrez pourquoi j'affirme sans peur que c'est le plus vieux sujet scientifique : partout où il y a routine, méthode, transmission d'un savoir-faire, il y a algorithme! On pourrait donc pousser le vice jusqu'à considérer que les méthodes de chasse de nos ancêtres préhistoriques, qu'ils inscrivaient selon certaines théories sur les murs des grottes, étaient bel et bien des algorithmes.

Quelques algorithmes au cours de l'histoire

Pour autant, ce n'est que beaucoup plus tard qu'est généralement placée la date des premiers algorithmes principalement parce qu'il fallut attendre l'apparition de l'écriture pour avoir des traces des méthodes employées et non seulement de leur résultat. Dans le dossier sur Pi, je vous avais présenté une des premières apparitions du nombre sur le papyrus de Rhind. Ce papyrus, qui date de -2000, contient aussi des traces d'un algorithme pour réduire plusieurs fractions au même dénominateur. De manière plus générale, toutes les méthodes pour calculer Pi sont des algorithmes et sont un bon exemple de la diversité du sujet.

Datant cette même période des débuts de l'écriture, entre -3500 et -1500 av. J.-C., on a retrouvé des tablettes babyloniennes indiquant comment calculer un inverse, effectuer une division, etc. Ces opérations peuvent paraître simples aujourd'hui, mais en tant qu'algorithmes, les méthodes devenaient applicables par n'importe qui (sans culture ni éducation nécessaire). Ces méthodes permettaient de faire facilement des multiplications, des règles de trois, etc. Pour l'anecdote, cette civilisation ne comptait pas en base 10 (avec 10 chiffres), mais en base 60, cela simplifie les divisions. Le choix de la base 60 s'explique probablement du nombre de phalanges des doigts d'une main (sans compter le pouce) et du nombre de doigts de la main (5×12=60). À titre d'anecdotes à ressortir en dîner de famille, c'est parce que les Babyloniens comptaient en base 60 que nous comptons 60 minutes dans une heure.

Il n'y a pas que ces vieilles civilisations qui s'aidaient d'algorithmes pour effectuer des opérations simples. Lorsque vous posez une division, vous effectuez des étapes mécaniques sans forcément savoir pourquoi elles fonctionnent, mais au contraire, vous avez appris par cœur un rituel qui permet de vite effectuer l'opération. Parmi les outils originaux pour effectuer des opérations simples, l'image ci-dessous (provenant de Wikipedia) représente l'invention de Lucas-Genaille : un système de réglettes pour effectuer la multiplication de deux grands nombres.

LucasGenaille

Pour effectuer la multiplication, il suffit de placer les réglettes correspondant au nombre choisi et de suivre les flèches noires comme sur la figure ci-dessous (provenant tout autant de Wikipedia).

Dans cet exemple, on effectue la multiplication de 52749 par 4 : en suivant les flèches noires, on trouve 210996. Ces réglettes furent commercialisées jusqu'en 1911! Ce système aussi amusant qu'ingénieux est une goutte d'eau au milieu des autres méthodes permettant de faire des opérations arithmétiques.

De tout temps, les algorithmes ont donc été au centre de l'activité humaine, mais il fallut attendre 1900 pour voir apparaître un début de formalisation de ce concept avec le 10e problème de Hilbert, nous y revenons dans la prochaine partie. Il n'a pas fallu attendre la formalisation pour voir apparaître des algorithmes très complexes. Jusqu'à cette période, le mot algorithme était le plus souvent associé à Euclide et une manière simple de présenter la notion d'algorithme était de donner l'exemple du célèbre calcul.

Algorithme d'Euclide

Euclide écrit au troisième siècle  av. J.-C. 13 livres “les éléments“. Les premiers traitent de géométrie alors que les livres VII, VIII et IX posent les bases de la théorie des nombres. C'est justement dans le 7e livre qu'Euclide présente une méthode pour calculer le plus grand diviseur commun à deux nombres. Le plus grand diviseur commun de a et b, PGCD pour les intimes, est le plus grand nombre qui divise a et b (c'est-à-dire le plus grand nombre p tel que a/p et b/p soient entiers). Nous ne reviendrons pas ici sur la preuve du fonctionnement de l'algorithme ni sur la théorie des nombres, car ce n'est pas le sujet.

Bien qu'il soit très vieux, cet algorithme reste d'actualité et contient tous les éléments d'un algorithme “moderne”. Son fonctionnement tel que décrit dans le livre est résumé par la figure suivante. Pour les puristes, l'algorithme présenté ici est celui décrit par Euclide dans son livre et non l'amélioration utilisant la division euclidienne généralement présentée.

C'est un algorithme très utile et encore très utilisé, car il à été généralisé pour plusieurs résultats, par exemple, il permet de calculer les coefficients de l'identité de bezout qui sert dans le système de cryptage RSA, énormément utilisé pour la sécurisation du e-commerce. C'est l'un des plus vieux algorithmes encore en activité.

On y retrouve encore nombre d'éléments de la recette de cuisine :

  • Des déclarations : trois variables sont déclarées (a, b et c) même si avec le seul schéma ci-dessus, cela est sous-entendu. Dans la recette, la liste d'ingrédients joue ce rôle de déclaration. En plus de cela, est comme c'est parfois précisé, il faudrait “déclarer” quels sont les ustensiles nécessaires.
  • Des affectations : les trois variables se voient affecter plusieurs résultats tout au long de l'algorithme. Dans la recette, c'est le contenu des bols et autres assiettes qui joue ce rôle d'affectation.
  • Une séquence d'instruction : les flèches sur le diagramme permettent de savoir dans quel ordre effectuer les opérations. Dans la recette, c'est l'ordre des phrases.
  • Des tests : “c=1″ par exemple. Dans la recette, on trouvait le test “est-ce que le chou est croquant?”
  • Une boucle : dans cet algorithme, la même opération est répétée jusqu'à ce que l'on trouve le PGCD. Dans la recette, on fait cuire le chou tant qu'il est “croquant” jusqu'à ce qu'il devienne “un peu croquant”.

Et surtout, l'algorithme d'Euclide correspond bien à l'idée de ce qu'est un algorithme présenté en début de dossier. Les souhaits présentés dans la première liste correspondent à ce que l'on attend d'un algorithme alors que cette nouvelle liste correspond à 5 outils qui permettent de construire des objets correspondant à la première intention. Deux questions s'imposent alors : ces 5 outils sont-ils indispensables? Et surtout est-ce qu'avec ces seuls 5 outils, on peut construire tous les algorithmes correspondants aux désirs énoncés? Avant de répondre à ces deux questions, nous allons faire un petit écart historique pour dire deux mots sur l'événement qui amena à une meilleure définition des algorithmes et déclencha les nombreux travaux qui aboutirent à leur réponse.

La fin du formalisme de Hilbert

En 1900, au congrès international des mathématiciens, Hilbert présenta 23 problèmes non résolus qui selon lui étaient les plus importants du moment. Un certain nombre sont aujourd'hui résolus : c'est-à-dire que l'on a montré qu'ils étaient soit vrais soit faux. Ou alors on a prouvé qu'ils étaient indécidables, qu'on ne peut pas dire s'ils sont vrais ou faux; ils sont indépendants de la théorie considérée. Un équivalent aujourd'hui de cette démarche est les problèmes du prix du millénaire pour lesquels l'institut mathématique Clay offre un million de dollars à qui apporte une solution (et pour information, cette somme ne serait qu'un pourboire tant la plupart de ces problèmes sont importants et ont plusieurs applications cruciales telles que la cryptographie).

Hilbert dans sa démarche visait à montrer une certaine “perfection” des mathématiques en demandant la démonstration de trois résultats :

    • La complétude des mathématiques : c'est-à-dire que tout énoncé peut être confirmé ou infirmé. En d'autres termes que l'on peut construire une théorie sans aucune proposition indécidable;
    • La consistance des mathématiques : c'est-à-dire qu'il n'existe pas d'énoncé contradictoire, qui serait vrai ainsi que son contraire;
    • La décision des propositions mathématiques : c'est-à-dire qu'il existe une procédure s'exécutant en un temps fini permettant de démontrer qu'un énoncé mathématique est vrai.

Ironie de l'histoire, alors qu'Hilbert souhaitait que tous ces énoncés soient vrais, il fallut moins de 50 ans pour démontrer q

u'il n'existait pas de théorie mathématique suffisamment complexe pour contenir les opérations élémentaires (addition, multiplication, inverse…) à la fois consistante et complète. Et surtout qu'une procédure qui permet de décider si un énoncé est vrai en un temps fini n'existe pas. Une défaite pour la pensée de Hilbert, mais grâce à ses problèmes, une avancée exceptionnelle des mathématiques et de la connaissance de leurs limites.

La dernière question, qui correspond au 10e problème de Hilbert, parle sans s'en rendre compte d'algorithme. En effet, Hilbert souhaite trouver une méthode qui s'exécute en un nombre fini d'étapes pour obtenir son résultat. Et pour apporter une solution à ce problème (la solution est que c'est impossible, mais ça reste une solution), il fallut bien définir la notion d'algorithme. Et grâce à cette bonne définition, on put en cerner certaines limites.

La caractérisation précise des algorithmes a pu se faire en définissant la notion de fonction calculable, c'est-à-dire une fonction qui coïncide avec la description faite en début de dossier. Beaucoup de très grands noms des mathématiques du XXe siècle ont proposé une définition de la calculabilité. Il y a d'abord Godel, qui après avoir détruit les rêves de Hilbert sur l'incomplétude et la cohérence présenta une définition de “fonctions récursives” conçues sur quelques règles simples. Alonzo Church démontra l'impossibilité du problème de décision posé par Hilbert, résultat qui a aujourd'hui son nom. Il créa de son côté le lambda calcul, qui tout comme les fonctions récursives de Godel, avait pour but de représenter les algorithmes. Enfin, Turing proposa encore une autre construction, les machines de Turing, dont nous allons reparler tout de suite.

Entre 1931 et 1936, divers scientifiques brillants ont proposé plusieurs définitions de fonctions calculables qui paraissaient toutes aussi pertinentes. En fait toutes ces constructions sont équivalentes, les algorithmes que l'on peut construire avec sont les mêmes! Il n'y avait donc en fait qu'un ensemble de fonctions, de méthodes que l'on pouvait fabriquer et c'est ce que l'on appelle aujourd'hui les algorithmes. Dans la partie suivante, nous allons voir l'une de ces constructions, sans aucun doute la plus célèbre : la machine de Turing.

Machine de Turing

Il n'a pas été facile de choisir la définition de fonction calculable que j'allais présenter pour ce dossier. À vrai dire, je ne savais pas qu'il y en avait autant et surtout celle des machines de Turing était de loin celle qui me parlait le moins, me paraissait la moins intuitive. Puis, j'ai lu l'extrait traduit de “on the computable numbers, with an application to the Entscheidungsproblem” que vous pourrez trouver dans “histoires d'algorithmes”, livre dont la référence complète est donnée en fin de dossier. Si vous le pouvez, lisez le texte directement, c'est limpide et explique très simplement la construction de ces “machines”.

Turing cherche donc à formaliser l'opération que l'on appelle intuitivement “calcul”. Il commence par énumérer les différents éléments nécessaires pour faire un calcul. Le calcul est fait sur une feuille où l'on écrit les symboles les uns après les autres sur une ligne. Il propose donc de modéliser cela par un ruban de papier quadrillé. Il explique ensuite qu'on doit se limiter à un nombre fini de symboles tels que dans notre alphabet et précise que l'un de ces symboles doit être repéré comme étant le “0″, la case vierge.

Tout comme nous ne regardons qu'une étape de recette à la fois, Turing poursuit en disant qu'un calculateur ne peut observer qu'un nombre de symboles fini fixé à chaque étape. Et tout comme le plat est dans un état bien déterminé et le cuisinier dans un état d'esprit bien précis avant le début d'une étape, il précise que sa machine est dans un nombre fini d'états au moment de l'observation.

Il explique ensuite que la donnée de l'état du calculateur et de l'observation des symboles permet d'effectuer deux opérations :

  • changer l'ordre des cases en échangeant une case observée par une case voisine ;
  • remplacer le symbole dans une case du ruban par un nouveau.

Lorsque l'on suit une recette de cuisine, on n'effectue pas autre chose, on ajoute et retire des ingrédients, on les mélange… Si l'on décompose la recette au maximum en opérations simples, on arrive à rester dans la modélisation de Turing.

Et… C'est tout! À partir de cette construction, on arrive à modéliser toutes les choses que nous appelons ou soupçonnons être à ce jour des “algorithmes”. En fait, ce que nous appelons aujourd'hui une machine de Turing est encore plus simple et permet de fabriquer exactement les mêmes systèmes : l'alphabet n'a que deux symboles (0 et 1), on observe une seule case à la fois et on ne peut utiliser que les cases directement voisines à la case observée.

Il fut montré que les machines de Turing sont équivalentes à toutes les autres fonctions “calculables” de l'époque et on ne connaît pas à ce jour de “méthode” exécutable par une machine, un humain ou un animal qui ne soit pas modélisable par l'une d'elles. Mais pour autant, est-ce que ces fonctions calculables correspondent bien à l'intuition de la notion d'algorithme? Alonzo Church en était convaincu et cette hypothèse est aujourd'hui connue sous le nom de “thèse de Church“. Autant dire tout de suite que cette conjecture à peu d'espoir d'être démontrée tant elle est plus proche de la philosophie que des sciences (allez donc jeter un oeil à la conférence mise en lien en fin de dossier si le sujet vous intéresse)… D'autant plus que grâce aux raisonnements de Cantor, on peut démontrer que l'ensemble des fonctions calculables est dénombrable. Comme l'ensemble des nombres réels est indénombrable, il existe une infinité de nombres non calculables par des algorithmes! Reste à savoir si ce sont des nombres atteignables dans le monde “réel”.

Savoir calculer ne suffit pas

Une fois la notion de fonction calculable posée et la thèse de Church avancées, nous savions que nous avions en main tous les outils pour créer des algorithmes des plus complexes. Pourtant, cela est encore trop théorique. Dans les faits, avec l'arrivée des ordinateurs, pourtant dotés d'une capacité de calcul énorme (tout en étant parfaitement stupides, ce qui colle bien avec la définition d'un algorithme), on s'est rendu compte qu'une autre limitation empêchait de finir certains calculs.

Dans le cher monde réel, dire que l'on obtiendra un résultat en un temps fini ne suffit pas, parce que cela n'empêche pas par exemple que le temps d'exécution d'un algorithme prenne plusieurs fois l'âge de l'univers pour s'exécuter (sisi, c'est très grand, mais c'est fini).  Dans le guide du voyageur galactique par exemple, des habitants d'une planète construisent une machine pour répondre à la grande question sur la vie l'univers et tout le reste et ce n'est que 7 millions et demi d'années plus tard que la réponse, 42, est obtenue!

La complexité algorithmique est l'objet de l'un des 7 problèmes à un million de dollars et déjà traité dans le tout premier épisode du podcast (contrairement à ce que l'on a cru brièvement a l'époque, le problème est toujours ouvert). Ce problème, que l'on résume souvent à “P=NP” est selon la plupart des mathématiciens à la fois le plus important de ceux de l'institut Clay et le plus à même à être résolu par un amateur. Certains problèmes appartiennent à la catégorie P (les plus “simples”) et d'autres a la catégorie NP (les plus complexes), tout l'enjeu du problème est de prouver que ces catégories sont les mêmes. Et pour le démontrer, il suffirait soit de prouver qu'un seul problème NP n'est pas P (on a alors P different de NP) ou qu'un seul problème NP-Complet (classe particulière de problèmes NP qui sont équivalents à tous les autres) est en fait dans P (alors P=NP), voilà pourquoi beaucoup pensent qu'un amateur pourrait apporter une solution.

Ce qui différencie ces problèmes, c'est la complexité des algorithmes que l'on connaît pour les résoudre. La complexité d'un algorithme est un ordre de grandeur du temps qu'il faut pour obtenir un résultat en fonction de la taille des données du problème dans le pire des cas. Prenons un exemple amusant qui a été posé à un ami lors d'un entretien d'embauche.

Imaginons que vous ayez une noix de coco et devant vous un immeuble de n étages. Vous souhaitez savoir à quel étage exactement la noix de coco se casse. La seule solution dans ce cas, et d'aller à chaque étage en commençant par le rez-de-chaussée et de lâcher la noix de coco pour voir si elle se casse (on suppose que la noix de coco ne s'abîme pas, soit elle se casse soit elle reste indemne). Dans le pire des cas, c'est au dernier étage que la noix de coco se casse, il faut donc faire n tests.

Avec deux noix de coco, le problème devient plus intéressant. Ce qui vient tout de suite à l'esprit est de balancer la première noix de coco à la moitié du bâtiment puis en fonction de la casse à la moitié de la moitié restante et ainsi de suite jusqu'à ce qu'elle casse et de finir avec l'autre en testant tous les étages restants.

Mais quitte à séparer le bâtiment en deux parties, on peut le séparer en 3, 4, 5 ou plus généralement k parties. Il faudra alors au pire des cas que l'on effectue k tests avec la première noix de coco puis n/k tests (les étages restants) avec la deuxième noix de coco. On effectue donc k+\frac{n}{k} opérations. Il s'agit alors de trouver pour quel k on effectuera le moins d'opérations.

C'est à dire de trouver le nombre m tel que pour toutes les valeurs de k, k+\frac{n}{k} soit supérieur à m. Autrement dit que k+\frac{n}{k} -m est supérieur à zéro pour tous les k. Comme k est supérieur à zéro, cela revient à trouver le minimum du polynôme k^2+n-mk.

Pour résoudre un polynôme de degré 2, rappelez-vous de l'algorithme appris à l'école ou allez consulter votre mémoire numérique Wikipédia, il faut calculer le déterminant \Delta qui vaut  b^2-4ac pour le polynôme  ax^2+bx+c . Dans notre cas, il vaut donc :

 \Delta=m^2-4n

Pour qu'un polynôme ne change pas de signe, il faut qu'il ait une racine double (le fameux cas  \Delta=0 rappelez vous!), c'est-à-dire que  m^2=4n . Le k pour lequel est atteint ce minimum est alors  k=\sqrt{n} . Il faut donc diviser le bâtiment en racine carrée du nombre d'étages pour aller au plus vite à la solution (on obtient alors le résultat en 2\sqrt{n} opérations).

Ces exemples montrent que l'on peut résoudre un même problème de façon plus ou moins rapide. Dans les cas présents, si l'on passe d'un bâtiment de 10 étages à un bâtiment qui en a 100 000, dans le premier cas, on multiplie le nombre d'opérations par 10000 alors que dans le second on le multiplie seulement par 100. Cela peut dans certains cas différencier un algorithme exécutable en temps humain d'un algorithme dont nous ne verrons jamais la fin.

Pour revenir au problème P=NP, les problèmes P sont ceux pour lesquelles ont connaît un algorithme qui ne nécessite “que” un nombre polynomial d'opérations par rapport à la taille des données d'entrée. C'est-à-dire que le nombre d'opérations qu'ils nécessitent pour des données de taille n est inférieur à  n^k pour un certain k. Les problèmes NP sont quant à eux des problèmes dont on ne connaît pas d'algorithme les résolvant en temps polynomial, mais où il est facile de vérifier si l'on a une solution (facile veut dire que cette vérification se fait en temps polynomial). Dans l'exemple de la noix de coco, même s'il faut n opérations pour résoudre le problème il n'en faut qu'une seule pour voir si la noix de coco est cassée.

Les problèmes NP sont alors des problèmes que l'on résout facilement avec de la chance : en prenant une configuration au hasard et pour peu qu'on soit par chance tombé sur la solution, on sait s'en rendre compte rapidement. Toute la question de P=NP est alors de savoir si des problèmes simples à vérifier sont simples à résoudre.

Les problèmes NP ne sont pas du tout des problèmes exotiques mis en avant par un mathématicien un peu fou, ce sont des problèmes que l'on croise tous les jours. Le plus connu, le voyageur de commerce, demande à proposer une méthode pour trouver le chemin le plus court étant donné une répartition de maisons pour que le voyageur de commerce puisse toutes les voir. On sait facilement vérifier si l'on a bien le chemin le plus court, mais on ne sait pas facilement trouver ce chemin.

Plus amusant, étant donné une liste de mots et un mot croisé vierge, trouver où il faut mettre chaque mot est un problème NP, on sait très rapidement vérifier si la grille est bien remplie, mais on ne sait pas la remplir rapidement.

Ce problème reste aujourd'hui complètement ouvert. À une époque, on pensait qu'il était vrai, aujourd'hui beaucoup pensent qu'il est faux et d'autres qu'il serait indécidable…..

Ici s'achève le dossier sur les algorithmes, j'espère vous avoir éclairé sur le sujet et surtout vous avoir démontré que l'on pouvait parler d'algorithmes sans jamais parler d'ordinateur ni de langage de programmation!

Sources bibliographiques et autres liens pour aller plus loin :

merci à Sébastien pour le problème des noix de coco.

zp8497586rq
VN:F [1.9.22_1171]
Rating: 4.8/5 (4 votes cast)
Tagged with:  

Aujourd’hui, le 14/03, est un jour consacré à pi. Pour cette occasion NicoTupe, nous a préparé un dossier pour présenter les particularités de ce nombre, et toute sorte d’information le concernant, comme les méthodes pour le calculer ou encore le nombre de décimales connues.

Le dossier de Nico est consultable ici.

 

Chronique cinéma : les femmes en mathématiques

 

Les quotes de l’émission

- “If you wish to make an apple pie from scratch, you must first invent the universe. — Carl Sagan”

- “Il est plus facile de désintégrer un atome qu’un préjugé. -  Albert Einstein”

- “Love is like pi – natural, irrational, and very important. – Lisa Hoffman”

 

Tagged with:  

Sur la Pi-ste d'une constante mathématique

On 14.03.2012, in Dossiers, by Nicotupe
VN:F [1.9.22_1171]
Rating: 4.6/5 (5 votes cast)

Si nous faisons aujourd'hui une émission sur pi, c'est avant tout parce que le 14 mars est une date très spéciale. Aux États-Unis, on note d'abord le mois puis le jour pour indiquer la date, nous sommes donc le 3-14, ce qui correspond à une estimation des premières décimales de \pi! Cette journée festive pour les mathématiciens est l'occasion de manger des pie (tartes) en buvant des piña colada. Pour l'anecdote, c'est le jour où le MIT dévoile ses admissions, il le fait à 1:59pm (les décimales suivantes dans pi)

Plusieurs nombres ont un statut particulier en mathématiques, principalement du fait de leur histoire. Les plus célèbres sont sans aucun doute \sqrt{2}, le nombre d’or, exponentielle, \pi et oméga (celui-là, vous ne le connaissez probablement pas, j’en parle un peu plus loin dans ce dossier). Cette illustration d’XKCD résume assez bien l’ensemble des nombres “intéressants” pour les mathématiens.

\pi garde un statut particulier, c’est avec \sqrt{2} celui dont la définition est la plus simple et pourtant il a, du fait de ses propriétés complexes perturbées de nombreux scientifiques de l’histoire. Dans ce dossier, nous verrons quelques-unes des propriétés de ce nombre unique.

Je ne vais pas m’attarder trop longtemps sur la définition la plus connue de \pi, à savoir le rapport entre la circonférence (longueur du périmètre d’un cercle) et son diamètre. Ni de la définition qui suit généralement à savoir le rapport entre l’aire du cercle et le carré de son rayon. En revanche, nous allons commencer par répondre à une question que vous ne vous êtes sans doute pas assez posée \pi est-il constant?

Pi est-il constant?

La réponse largement acceptée à cette question est oui. Pourtant cela reste à démontrer. Une démonstration simple utilise un théorème que l’on voit à l’école : le théorème de Thalès. Son énoncé est le suivant :
“Soit un triangle ABC et deux points D et E tels que les droites (DE) et (BC) soient parallèles. Alors on a \frac{AD}{AB}=\frac{AE}{AC}=\frac{DE}{BC}
Si l’on prend alors deux cercles de rayon différents et que l’on trace le plus grand polygone de 10 côtés à l’intérieur, on obtient la figure suivante :

Le théorème de Thalès permet d’affirmer que le rapport entre les côtés de chaque polygones sont égaux au rapport des rayons des deux cercles :

\pi_1=\frac{DE}{AD}=\frac{BC}{AB}=\pi_2
Si on augmente le nombre de côtés des deux polygones, les “rayons” des polygones convergent vers la même valeur et le rapport des circonférences est donc égal au rapport des rayons, les \pi des deux cercles sont donc égaux (pour que la démonstration soit juste, il ne faut pas se contenter de tracer le plus grand polygone contenu dans le cercle, mais tracer aussi le plus petit qui contient le cercle).

Ouf, \pi est constant, on ne nous a pas menti! Enfin, comme toute démonstration mathématique, elle est vraie dans le cadre de certaines hypothèses… Pour que le théorème de Thalès soit vrai, il faut se placer dans la géométrie d’Euclide, soit grossièrement une géométrie “plate” en opposition à une géométrie courbe. Prenons par exemple une assiette à soupe. Le pourtour de l’assiette forme bien un cercle, mais le centre de ce cercle, sur l’assiette, n’est pas sur le même plan que ce cercle et ne coïncide donc pas avec le centre “euclidien” du cercle. Sur Terre, le problème est le même, du fait de la forme de la terre, quand on trace un cercle au sol et mesure son diamètre, la valeur n’est pas la même que celle que l’on obtiendrait en géométrie euclidienne. Cela a pour conséquence que sur Terre \pi n’est pas constant!

Rassurez-vous, le \pi des mathématiques est bel est bien constant et correspond au rapport des cercles en géométrie Euclicienne. Cette remarque permet de différencier deux types de constantes :

  •  Les constantes “physiques” : Des expériences laissent penser qu’une opération donne toujours le même résultat quelles que soient un certain nombre de transformations subies par un objet (par exemple en traçant plusieurs cercles sur le sol et en mesurant diamètre et circonférence, on constate que le rapport fait toujours la même valeur).
  • Les constantes “mathématiques” : Grâce à plusieurs hypothèses, on a démontré que cette valeur était constante.

Dans l’histoire, \pi a d’abord été une constante physique, il n’est devenu constante mathématique assez tard grâce à l’homme dont l’un des bains est le plus célèbre de l’histoire.

Les premières apparitions

Une des premières apparitions de \pi, ou du moins de l’idée d’un rapport constant entre la circonférence du cercle et de son rayon, provient d’une tablette babylonienne datant d’environ 2000 avjc. Grâce à l’hexagone inscrit dans un cercle, les Babyloniens avaient proposé l’approximation \pi=3+\frac{1}{8}.
Les Égyptiens quant à eux ont laissé la trace d’un calcul implicite de \pi sur le papyrus de Rhind. Ce papyrus, rédigé par le scribe Ahmès environ 1650 ans avant notre ère, est la recopie d’un manuel scolaire un peu plus vieux (1800 avjc environ) et est représenté sur l’image ci-dessous (trouvée sur wikipedia).

Sur ce papyrus, on donne une méthode pour calculer la surface d’un cercle à partir de son diamètre D :

  • Enlever 1/9 au diamètre du cercle
  • multiplier le résultat par lui-même

Soit la formule S=\left(D-\frac{D}{9}\right)^2 au lieu de S=\pi\left(\frac{D}{2}\right)^2 soit une estimation de pi à \left(\frac{16}{9}\right)^2.
Notons que rien ne prouve aujourd’hui que les Babyloniens ou les Égyptiens savaient si leurs valeurs de \pi était exacte ou une approximation. Ils avaient expérimentalement constaté qu’il existait un rapport constant et l’avaient estimé par diverses manières.

Et pi devint mathématique

Ce n’est que beaucoup plus tard, autour de 250 avjc qu’Archimède transforme la constante physique en une constante mathématique. Dans le traité “De la mesure du cercle”, il calcule des encadrements de \pi. Pour calculer ces encadrements, il utilise des polygones réguliers (un polygone régulier à n côtés est une figure ayant n côtés égaux). Pour encadrer la circonférence d’un cercle, il encadre le dit cercle par le plus petit polygone qui contient le cercle et le plus grand polygone contenu dans le cercle (comme dans la figure ci-dessous).

Ce type de construction permet non seulement de calculer \pi à la précision que l’on souhaite (en prenant des polygones avec de plus en plus de côtés), mais permet aussi de démontrer que \pi est bien une constante mathématique.

Pourquoi faire simple quand on peut faire compliqué?

Il existe de nombreuses autres manières pour définir \pi. Un constat simple est que partout où l’on trouve un cercle ou une sphère, on peut trouver \pi. Ainsi, le volume d’une sphère dépendra de \pi (\frac{4}{3}\pi r^3), sa surface aussi (4\pi r^2) ainsi que la probabilité pour un cure-dent que vous lancez sur votre parquet de croiser un rainure (l’ensemble des sens selon lequel le cure-dent tombe sur le sol forme un cercle). Aujourd’hui, ces définitions géométriques sont très peu utilisées, les mathématiciens y préfèrent des définitions plus abstraites, mais aussi plus faciles à manipuler.

On peut par exemple définir \pi en disant que c’est l’unique nombre x tel que cos(x/2)=0. Ayant bien sûr avant défini cosinus grâce à des exponentielles complexes et l’exponentielle grâce à une somme infinie de termes, ayant alors posé la théorie des sommes infinies et des nombres complexes… Autant dire que l’on est loin de la simplicité géométrique. Pourtant, ce type de définition permet de démontrer des résultats très élégants et pratiques pour calculer \pi :

\frac{\pi}{4}=1-\frac{1}{3}+\frac{1}{5}-\frac{1}{7}+\frac{1}{9}-...
A l’école, les plus jeunes auront appris que \pi vaut à peu près 3,14 et les plus vieux 22/7, ces deux nombres très simples sont hélas des approximations. On a d’un côté une définition très simple de \pi et de l’autre des formules très compliquées (une infinité de termes) pour le calculer, n’y a-t-il pas une formule plus simple? Durant toute l’histoire, les mathématiciens ont essayé de ranger \pi dans des ensembles de nombres qui par leur propriétés simplifieraient le calcul, sans succès. Ils ont ainsi rendu \pi célèbre pour tout ce qu’il est pas!

Ce que pi n’est pas!

Les premier nombres qui furent utilisés sont les nombres dit “naturels” :

0, 1, 2, 3, 4...
L’ensemble de tous ces nombres est noté \mathbb{N}. Assez rapidement le besoin s’est fait sentir d’avoir des nombres négatifs. Les nombres négatifs sont les inverses pour l’addition des entiers naturels. C’est à dire qu’en additionnant un entier naturel, 3 par exemple, et son inverse, -3 dans ce cas, on obtient 0. Cet ensemble, bien que simple permet, avec les opérations que l’on connaît tous d’addition “+” et de multiplication “x” (on rappellera que la soustraction n’est pas une “vraie” opération, c’est l’addition de l’opposé), offre déjà la possibilité de faire les opérations d’arithmétique classique. C’est-à-dire que l’on peut y définir des polynômes (x^3+3x^2+2x+1 par exemple), la division euclidienne (celle que l’on apprend à la petite école : la division de 13 par 4 a pour reste 1), etc.

Malheureusement et pour revenir à notre sujet, on s’est très rapidement rendu compte que \pi n’est pas un entier. En fait, je n’ai vu qu’un texte qui présentait \pi comme un entier (ou plutôt une approximation, le texte en question datant de 500 avjc, on ne parle pas du \pi moderne) : la Bible. On peut en effet y lire :

“Il fit aussi une mer de fonte de dix coudées d’un bord jusqu’à l’autre, qui était toute ronde : elle avait cinq coudées de haut et était environnée tout à l’entour d’un cordon de trente coudées”

Pi n’est pas aimé des Py-taghoriciens

Les entiers relatifs ne suffisent pas à décrire \pi. En fait, ils ne suffisent pas non plus à décrire la plupart des nombres que nous utilisons chaque jour. Quand on mange un gâteau par exemple, on est très vite amenés à parler du tiers ou du quart du gâteau. On est très habitués à parler en “fractions”. Une fraction s’écrit comme le rapport de deux entiers relatifs (1/3, 2/5, 1242332/58974892676, etc.)

Les fractions sont très utiles pour représenter des quantités intrinsèquement non entières. Par exemple, 1/3 permet de séparer en trois l’unité. L’École Pythagoricienne, qui exista autour des années 500 avjc, était persuadée que tous les nombres pouvaient être représentés par des fractions. Cette école philosophique (qui serait sans doute qualifiée de secte si elle existait encore aujourd’hui) pensait que le rapport entre toute quantité du même type peut être rapporté au rapport entre deux entiers. L’ensemble des fractions paraissait alors si “normal” qu’il est appelé aujourd’hui ensemble des “Rationnels”.
On ne sait sous quelles conditions, mais un jour les pythagoriciens sont tombés devant un paradoxe de taille. Si l’on trace un carré de côté 1, la diagonale de ce carré a pour longueur \sqrt{2} (le nombre qui multiplié par lui même fait 2).

Une ironie amusante est que l’on peut démontrer que cette diagonale correspond à \sqrt{2} grâce au théorème de Pythagore (La paternité du théorème qu’indique ce nom est très loin d’être certifiée…) Ce nombre dont le carré vaut 2 est-il rationnel, autrement dit, peut-on l’écrire sous forme de fraction?
Regardons cela de plus près. Dire que \sqrt{2} est rationnel revient à dire qu’il existe des entiers positifs p et q non nuls tels que

\sqrt{2}=\frac{p}{q}
En élevant cette relation au carré et en multipliant par q, on obtient

2 q^2=p^2
Cette relation permet de déduire que p^2 est pair. Nous allons réécrire les nombres p et q afin de compter “le nombre de fois où ils sont pairs” :

p=2^j r

où r est impair.

On peut dire alors que p est pair j fois. Le carré p^2 de p se décompose alors :

p^2=2^{2j}r^2
r^2 n’est pas pair car le carré d’un nombre impair est impair. On peut donc affirmer que le nombre de fois où p^2 est pair est 2j.

Effectuons le même raisonnement sur q en notant k le nombre de fois où il est pair. q^2 est alors pair 2k fois. Par suite, 2q^2, le produit de q^2 par 2 est pair une fois de plus soit 2k+1 fois.

Or, on a écrit plus haut p^2=2q^2. Ceci implique que

2j=2k+1
Ce qui est tout simplement impossible car 2j est pair et 2k+1 est impair. La seule hypothèse faite ici est que \sqrt{2} pouvait s’écrire sous forme de fraction. Ce nombre ne peut donc pas s’écrire de cette manière sinon on aura des contradictions, il est “irrationnel”!
L’idée Pythagoricienne était alors détruite pour toujours, il existait des nombres non rationnels, que l’on ne pouvait pas écrire sous forme de fraction. \pi rentre aussi dans cette catégorie de nombre, cela a été démontré en 1761 par Lambert. La démonstration est plus compliquée que pour \sqrt{2} donc non détaillée ici, mais les curieux pourront en trouver quelques éléments dans livre de Jean-Paul Delahaye cité en fin de dossier.

La preuve de l’irrationalité de \pi réduit à néant aussi l’un des intérêts de recherches de décimales de \pi (qui occupe encore aujourd’hui plusieurs personnes et supercalculateurs). En effet, un nombre rationnel a la propriété qu’à partir d’un certain nombre de décimales, on voit apparaitre un “cycle” :

1/3=0.3

33333333333… Le 3 est infiniment répété dès la première décimale
22/7=3.1428571428571428571… dès la première décimale, la suite de chiffres 142857 est répétée

Un des buts que pouvaient avoir le calcul des décimales de \pi était de trouver ce cycle. La preuve de l’irrationalité de \pi amena le fait qu’on ne trouvera jamais de cycle dans ses décimales.

Si \pi et \sqrt{2} ont la propriété commune d’être irrationnels, il subsiste une très grande différence entre les deux : À partir d’un segment de longueur 1, je peux avec une règle non graduée et un compas tracer un segment qui fait exactement \sqrt{2}, la diagonale du carré. Qu’en est-il pour \pi?

Pi n’est pas aimé des carreurs

Autour de -500 (maintenant que les nombres relatifs sont définis, je peux les utiliser pour représenter les années), un grec nommé Anaxagore se posa un problème à la fois extrêmement élégant (tout le monde peut le comprendre et penser le résoudre facilement) et très dur à résoudre (plus de 2000 ans d’histoire ont été nécessaires pour trouver la réponse). Ce problème est celui de la “quadrature du cercle”. Le principe est de tracer un cercle et un carré faisant la même aire. Comme tout problème, il y a quelques règles à respecter :

  • On ne doit utiliser qu’une règle non graduée et un compas
  • Le nombre de tracés intermédiaires doit être fini (on ne peut pas en proposer une infinité)

L’impossibilité de quarrer le cercle (c’est le nom technique de la chose) a été démontrée en 1882. Mais l’apparente simplicité du problème a amené certaines personnes à continuer à essayer de trouver une construction pour quarrer le cercle, à tel point qu’une maladie existe pour les personnes qui veulent à tout prix résoudre la quadrature du cercle : “morbus cyclometricus”! Avant la démonstration de l’impossibilité, l’académie des science croulait sous les démonstrations (erronées bien entendu) du résultat à tel point qu’elle décida en 1775 qu’elle n’accepterait plus de regarder des démonstrations de la quadrature du cercle, elle avait probablement la conviction que c’était impossible.

Bien qu’assez élégant, énoncé comme cela il n’est pas simple de s’y attaquer rigoureusement. C’est cette imprécision qui a poussé plusieurs personnes à penser qu’elles l’avaient résolu. Construire un point à la règle et au compas veut dire que l’on a fait un nombre fini de constructions intermédiaires du type :

  • Tracer une droite entre des points déjà construits
  • Tracer un cercle dont le centre est un point déjà construit et le rayon est la distance entre deux points déjà construits.

Pour résoudre ce problème, il fallut faire le lien entre les constructions géométriques et les équations. Plusieurs mathématiciens renommés s’y sont attelés, de Descartes qui montra un lien entre certains type d’équations et les constructions à la règle et au compas jusqu’à Wantzel qui obtint l’équivalence entre les constructions géométriques à la règle et au compas et les “radicaux”.

Un nombre que l’on peut construire par radicaux est un nombre que l’on peut construire en un nombre fini d’étapes grâce aux nombres entiers et aux opérations racine carrée, division, multiplication, addition et soustraction. Ainsi,

\sqrt{2} est constructible par radicaux (à partir de 2 et de l’opération racine carrée)
\frac{1+\sqrt{3+\sqrt{5}+\frac{\sqrt{2}}{6}}}{7-\sqrt{2}+\sqrt{1+\sqrt{5+\sqrt{8}}}} est constructible par radicaux.

Grâce à cette formulation, le problème de la quadrature du cercle devenait : \pi est-il constructible par radicaux? Wantzel démontra que non en 1837.

Les habitués des mathématiques réagiront vite en se demandant pourquoi se limiter aux racines carrées et ils auront bien raison! La notion de construction par radicaux a une grande valeur historique, mais aujourd’hui on parle davantage de nombre “algébrique”. Un nombre algébrique est un nombre qui est la solution d’une équation “polynomiale” à coefficients entiers. C’est-à-dire la solution x d’une équation du type :

x^5+3x^4+2x^3+8x^2+6x+1=0

ou encore

3x^{34}+6x^{39}+x=0
En clair une équation avec des puissances de x, des coefficients entiers et s’annulant. Chose très rare en mathématique, les nombres qui ne sont pas algébriques portent un non moins évident que “non algébriques”, ils sont “transcendants”. Autre chose étonnante et pour le coup très liée à la démarche du mathématicien, la notion de nombre transcendant a été définie avant même que l’on sache s’il en existait. Heureusement, Liouville trouva des nombres transcendants et bien plus tard, en 1882, Lindemann démontra que \pi était transcendant. Autrement dit, jamais aucune équation polynomiale à coefficients entiers n’aura pour solution \pi!

Pour résumer, \pi n’est pas un entier, il ne peut pas être dessiné avec un compas et une règle, il n’est solution d’aucune équation algébrique, ce nombre est-il donc le plus compliqué qu’on puisse trouver, est-il rare de rencontrer des nombres de ce type?

Pourtant pi n’est pas bien compliqué

Comme nous venons de le voir, tout au long de l’histoire il a été démontré que le nombre \pi était différent de la plupart des nombres que les mathématiciens rencontraient, c’est un nombre “transcendant”. Dans mon précédent dossier sur l’infini, nous avons vu qu’il existait plusieurs infinis plus ou moins grands. En particulier, j’ai présenté deux types d’infini, le dénombrable (celui que l’on peut numéroter) et l’indénombrable. Cantor a aussi démontré un résultat sur les nombres transcendants, ils forment un ensemble infini indénombrable alors que les nombres algébriques forment un infini dénombrable. Autrement dit, si l’on prend un nombre réel au hasard (si tant est que cela veuille dire quelque chose), il y a une probabilité nulle de tomber sur un nombre algébrique (comme 2 ou 3 ou \sqrt{2}, etc.). Autrement dit, ce n’est pas \pi qui est rare, c’est plutôt tous les nombres que nous utilisons régulièrement!

En fait, \pi appartient à un ensemble de nombres lui aussi dénombrable, celui des nombres “calculables”. Pour faire simple, un nombre calculable est un nombre duquel on peut approcher à une précision souhaitée en un nombre fini d'opérations. C’est à dire c’est un nombre dont le calcul jusqu’à n’importe quelle décimale peut être obtenu par un ordinateur. Tout comme la bibliothèque de Babel dans mon précédent dossier, l’ensemble de tous les programmes informatiques, de toutes les fonctions calculables est un ensemble dénombrable. L’ensemble des nombres que l’on peut calculer est donc infiniment plus petit que celui des nombres que l’on ne peut pas calculer. Autrement dit, en prenant un nombre réel au hasard, on a une probabilité nulle de tomber sur un nombre calculable… Les nombres Omega de Chaitin, dont je vous parlais en introduction sont justement des nombres incalculables. Il en existe même certains qui respectent beaucoup de très bonnes propriétés, mais dont on ne peut connaître aucune décimale!

Pour être complet sur les propriétés de pi, je me dois de préciser que le travail est loin d’être fini. Plusieurs résultats non démontrés subsistent : pi est-il un nombre univers (nombre dont tous les nombres entiers apparaissent dans les décimales)? Est-il un nombre normal (nombre dont les décimales suivent une certaine forme de hasard)?…

Puisqu’on a la chance d’avoir un nombre calculable, calculons-le!

La chasse aux décimales

Le calcul de décimales de \pi n'a jamais cessé, depuis sa découverte, d'intéresser certains scientifiques. Pourtant cela ne sert pas à grand-chose… Depuis que l'on sait que \pi est irrationnel, on sait qu'on ne trouvera pas de cycle dans ses décimales. Connaître plusieurs milliards de décimales n'aidera pas à savoir si oui ou non \pi est un nombre univers ou un nombre normal. Mais pire encore, avoir plus d'une cinquantaine de décimales apporte beaucoup trop de précision par rapport à tous les calculs que nous serions amenés à faire. Par exemple, la seule connaissance de 40 décimales de \pi suffit à calculer la circonférence de l'univers entier à la précision d'un atome d'hydrogène. Un des seuls intérêts mathématiques qui persiste serait de parvenir à trouver une régularité dans ces décimales, mais après plusieurs milliers de milliards de décimales connues, aucune n'est apparue.

En revanche, le calcul des décimales de pi a énormément fait avancer l'efficacité des méthodes calcul. Au début, les méthodes de calcul de \pi reposaient sur la méthode des polygones présentée en début de dossier. Cette méthode permet de gagner trois décimales toutes les cinq étapes. Une autre méthode populaire est la méthode dite d'”arctangeante”, c'est celle correspondant à la somme infinie présentée plus haut. Elle est tout aussi peu efficace que la méthode d'Archimède. C'est pourtant avec ces méthodes qu'est dépassée la centaine de décimales connues au XVIIIe siècle.

Au XIXe siècle, les calculateurs de décimales s'organisent. La 200e décimale est dépassée en 1844 par Von Strassnitzki, ou plutôt Johann Martin Zacharias Dahse, calculateur prodigue qui effectua la plupart des calculs! Le record continue à être battu par Shanks qui en 1874 calcule 707 décimales. Ce record est pratiquement le dernier record humain (il fut battu en 1945) et a une importance historique. D'abord parce que Shanks a passé 20 ans de sa vie à l'obtenir. Pour que ce type de calcul soit validé, il faut que quelqu'un le vérifie. Évaluons les deux possibilités pour la personne effectuant la vérification :

  • Il trouve les mêmes décimales, Shanks deviens célèbre. Le vérificateur tombe dans l'oubli
  • Il ne trouve pas les mêmes décimales. Cela ne prouve rien, il faut un autre vérificateur pour savoir qui a raison.

Autant dire que pour 20 ans de calcul, le jeu ne vaut pas tellement la chandelle. C'est une des raisons pour lesquelles le record résista d'abord jusqu'en 1945 et surtout jusqu'à l'apparition des premiers calculs par machine.

A la création du Palais de la Découverte à Paris en 1937, à l'occasion de l'exposition universelle, Borel décida de construire une salle dédiée à Pi. Ce lieu, unique salle au monde dédiée à pi (selon plusieurs sources mêmes si j'ai du mal à y croire), a été construite sur une base circulaire et avec un plafond formant une demi-sphère. Tout autour, les décimales de Shanks y ont été affichées. En 1945 avec le nouveau record et avec les records suivants, on eut la certitude que le calcul de Shanks était faux à partir de la 528e décimale. Les décimales du Palais de la Découverte ont donc été fausses jusqu'en 1945, mais contrairement à beaucoup de rumeurs, elles ont été corrigées depuis. Vous pouvez vérifier vous même en cherchant au-dessus du nom “Poisson” de la frise des mathématiciens les décimales “…0213949463…” on y lisait avant “…021395016…”. Ci-dessous une photo des décimales de la salle pi, mais n'hésitez pas à la visiter, elle existe encore!

L'ère des machines

Contrairement à ce que l'on pourrait croire, l'efficacité du calcul de pi par les ordinateurs ne dépend pas seulement de la puissance des ordinateurs, mais bien aussi du raisonnement mathématique utilisé. Il est même amusant de remarquer qu'historiquement les scientifiques se sont beaucoup plus intéressés à la façon de moins faire de calculs depuis que ce n'est plus eux qui les font. Par exemple, pour calculer

2\times 3+2\times 6
on effectue trois opérations (une addition et deux multiplication). Alors que si l'on factorise le calcul,

2\times(3+6)
on effectue plus que deux opérations! Soit un gain de temps de 30%!

Ce sont donc des raisonnements mathématiques à la fois sur la complexité (nombre d'opérations à effectuer) et sur les propriétés de \pi qui ont permis à travers les années de battre les records sur pi. En 1973, le million de décimales est dépassé par Guilloud et Bouyer qui utilisent la même formule que Shanks. La vérification de ce calcul a été effectuée par le CERN, à Genève et le résultat a été publié (oui oui, il s'agit bien d'un ouvrage ne contenant pratiquement que des décimales de pi!).

Aujourd'hui, le milliard de décimales est largement dépassé. En décembre 2009, le français Fabrice Bellard établit le record vérifié de 2700 milliards de décimales calculées avec un simple ordinateur de bureau. En octobre 2011, les Japonais Yee et Kondo affirment avoir calculé 10 000 milliards de décimales, résultat pas encore totalement validé à ma connaissance. Depuis que l'on connaît autant de décimales, il a été vérifié que toutes les dates de naissance (groupes de 6 chiffres) apparaissent, vous pouvez même chercher la vôtre ici.

Pour finir, Pi est donc un nombre qui de tout temps a passionné les scientifiques. Les propriétés et anecdotes rapportées ici ne sont qu'une infime partie de son histoire. Si le sujet vous intéresse, n'hésitez pas à consulter les livres ci-dessous.

L'image du teaser (dont le fond sont les décimales de pi) :

Sources et liens pour aller plus loin :
- Le fascinant nombre Pi de Jean-Paul Delahaye. Le livre à lire si le sujet vous intéresse, il est complet et simple d'accès, un must!
- Alex au pays des chiffres de Alex Bellos. Un livre très général et très agréable à lire, il contient un passage sur pi intéressant.
- Un exposé sur la salle pi au Palais de la Découverte : Permet aux non parisiens de voir la salle pi et contient plein d'informations, d'anecdotes qui ne sont pas dans ce dossier!
- La fabuleux destin de V2 de Benoit Rittaud. J'y ai trouvé la démonstration de non rationalité de racine de 2. C'est un excellent livre sur ce nombre.
- Calculer pi avec la pluie (merci Mathieu): http://amazings.es/2012/02/29/calculando-pi-con-gotas-de-lluvia/
- Des anecdotes sur le jour de pi ici : http://www.piday.org/stuff/
- Un WWsh qui parle de PI, queqlues exemples de WTF sonores autour de pi : http://www.linaudible.com/2011/03/19/wwsh065/

Et pour accéder directement au livres cités sur Amazon, c'est ici :

zp8497586rq
VN:F [1.9.22_1171]
Rating: 4.6/5 (5 votes cast)
Tagged with:  
*