Des maths discrètes

Posted on 24 septembre 2011 par π² / 6

Si vous me connaissez IRL, vous savez que je suis parti en direction de l’étoile polaire dans le but d’étudier les maths discrètes. Au cours de ma (pas si longue) existence, chacune de mes déclarations à ce sujet s’est vue accueillir de deux façons différentes :

Version initiée : «  Des maths discrètes ? Mais t’es fou ! Qu’est-ce qui t’a pris ?! »
Version profane : «  Maths discrètes ? Ah… Euh… C’est quoi au juste ? »

Deux interrogations légitimes qui vont recevoir céant des réponses que j’espère convaincantes.

« Maths discrètes ? Ça se mange ce truc ? »

Non, du moins pas que je sache.

Tout d’abord, entendons nous bien : l’adjectif discret n’a absolument rien à voir avec une quelconque furtivité, invisibilité ou autre. En d’autres termes, les maths discrètes ne sont pas appelées ainsi à cause des ninjas [1]. Encore que ça aurait pu leur être utile, comme nous le verrons plus tard.

Un mathématicien discret vient d’être dérangé dans ses œuvres (vue d’artiste). Merci wikicommons pour la photo !

En mathématique, discret s’oppose à continu. Exemple de truc continu : les nombres réels. Exemple de truc pas continu : les nombres entiers. Pour comprendre intuitivement à quoi on se réfère quand on parle d’ensemble continu ou discret, pensez à une chose toute simple : est-ce que, pour deux éléments d’un ensemble, il y en a toujours un entre les deux ? Par exemple, est-ce qu’entre deux nombre réels, il y en a toujours un ? Ben oui, leur moyenne par exemple. Est-ce qu’entre deux nombres entiers il y en a toujours un ? Ben non, par exemple on ne trouvera jamais de nombre entier entre 1 et 2.

C’est en fait un peu plus compliqué puisque Q, l’ensemble des nombres rationnels (les fractions, à peu de choses près), n’est PAS continu en dépit du fait qu’il soit toujours possible de trouver un nombre rationnel entre deux éléments de Q. Ne chipotez pas.

Les maths discrètes s’intéressent donc à des structures… discrètes. Logique. En particulier, des pans entiers des mathématiques ne s’intéressent qu’à ce qui se passe dans N (ou Z), c’est à dire au sein des entiers. Par exemple, l’arithmétique et son cortège de nombres premiers constituent un domaine d’étude conséquent (et passionnant). Il y a cependant également d’autres structures discrètes, comme les ensembles désignés par « Z/nZ » correspondant très grossièrement aux nombres allant de 0 à n-1. On peut aussi penser aux graphes, à la logique booléenne, etc.

« Et ça sert à quoi ? Ça me dit pas pourquoi tu veux en faire… »

Vous faites donc partie de ces gens qui estiment que l’utilité prime sur le reste dans la recherche ? Je ne vous félicite pas, rustre. Jusqu’à récemment, la meilleure réponse à cette question était « à occuper les matheux », ce qui est en soit une très noble cause. Néanmoins, avec le développement de l’informatique, une nouvelle réponse un tantinet plus classe est de rigueur : « à faire tourner le monde ». Rien que ça. En effet, le principe de fonctionnement des ordinateurs repose sur un modèle établi par Turing [2] au milieu du XXème siècle, celui de la machine de Turing. Son étude, ainsi que toute la théorie de la complexité qui en découle relève des maths discrètes. L’algorithme permettant à un GPS de calculer le chemin le plus efficace, nommé algorithme de Dijkstra en l’honneur de M. Dijkstra repose sur la théorie des graphes. La sécurité de vos transactions bancaires informatiques dépend de RSA, une méthode de chiffrement reposant sur la théorie des nombres, en l’occurrence la difficulté à factoriser un grand entier. Le processeur, c’est à dire le « cerveau » de votre ordinateur utilise massivement la logique booléenne. Je pourrais continuer pendant des pages, mais je pense que j’ai montré où je voulais en venir : les maths discrètes sont cruciales !

Ce domaine des mathématiques n’est, en dépit de son importance, pas très apprécié en général par les étudiants. Le problème est que les modes de raisonnement employés peuvent être assez éloignés de ce à quoi l’on est habitué dans le cas continu ; c’est du moins mon point de vue. Les maths discrètes peuvent aussi très facilement devenir complètement barrées et ultra-abstraites, par exemple dans le cas de la théorie de la complexité où on se retrouve à considérer des machines de Turing non-déterministes, c’est à dire très (mais alors très très) grossièrement des calculateurs qui peuvent renvoyer le bon résultat, ou pas, sans que ce soit un problème. Bizarre ? Vous n’avez pas idée…

Personnellement je trouve ces divers sujets absolument passionnants, encore plus que la résolution d’équations différentielles ou la physique. D’où mon départ en direction de l’étoile polaire.

« Et les ninjas dans tout ça ? »

En bons espions, les ninjas se devaient probablement de communiquer de façon sécurisée avec un commanditaire [3]. Dans ce cas, ils devaient probablement chiffrer leurs messages, c’est à dire les rendre illisibles pour le cas où un malotru les intercepterait. L’art du chiffrement, la cryptographie, utilise lui aussi massivement les mathématiques discrètes.

D’ailleurs, je compte publier dans les semaines à venir diverses méthodes pour protéger vos informations personnelles sur votre ordinateur, histoire que vous n’ayez pas les mêmes problèmes que Scarlett Johansson.

Sur ce, je retourne à mes activités suédoises et vous souhaite une bonne journée.

[1] (retour) Les ninjas étaient des sortes d’espions œuvrant dans le japon féodal, c’est à dire grossièrement au pays des samouraïs et des geishas (ce blog n’avait pas respecté son quota de cliché ce mois-ci). Dans l’imagerie populaire, ils sont vêtus de noir et ont le visage masqué. C’est en réalité, aussi incroyable que cela puisse paraître, un poil plus compliqué.

[2] (retour) Turing est, à mon avis du moins, un des plus grands génies du XXème siècle, à ranger entre Einstein et Gödel. Grosso modo, il a inventé l’ordinateur pour combattre les nazis : c’est assez dur de faire plus classe. Plus précisément, il a participé activement à la conception des premières bombes cryptographiques qui ont permis d’industrialiser le « cassage » (on dit « cryptanalyse » normalement) de la machine utilisée par les nazis pour chiffrer leur communications, contribuant ainsi à l’invention de l’informatique et à la victoire des alliés pendant la IIème guerre mondiale. Par contre, comme il était gay, il a été castré chimiquement et s’est suicidé en conséquence de cela en mangeant une pomme empoisonnée. La prochaine fois, il y réfléchira probablement à deux fois avant de sauver le monde…

[3] (retour) Pure spéculation de ma part, mes compétences en « ninjalogie » (néologisme pour nommer la science des ninjas) étant plus que limitées.

Google, ces p’tits rigolos

Posted on 17 août 2011 par π² / 6

Aujourd’hui, google nous propose un « doodle » (une image qui remplace le logo traditionnel sur leur page principale) qui contient une blague de matheux ! En effet, quand on survole l’image avec la souris, un texte obscur apparaît :

J’ai trouvé une merveilleuse démonstration de cette proposition mais ce doodle est trop étroit pour la contenir.

Le doodle en question. On peut y voir un énoncé simplifié du grand théorème de Fermat ainsi, entre autre, qu’un triangle rectangle.

Grand théorème de Fermat

Pierre de Fermat était un mathématicien du XVIIème à qui l’on doit en particulier deux théorèmes de théorie de nombres sobrement appelés « petit théorème de Fermat » et… « grand théorème de Fermat » [1]. On lui doit également des découvertes dans d’autres domaines, comme toujours avec les scientifiques de l’époque, notamment en optique.

En l’occurrence, c’est le grand théorème de Fermat qui nous intéresse ici. En effet, celui-ci stipule que :

Il n’existe pas de nombres entiers non nuls x, y et z tels que :
$x^n + y^n = z^n$
dès que n est un entier strictement supérieur à 2.

Tout est dit : Vous ne trouverez par exemple jamais deux entiers x et y tels que x^3 + y^3 = 42.

Et pour la blague ?

Dans l’ouvrage où il a exposé cette proposition, Fermat a écrit dans la marge :

J’ai trouvé une merveilleuse démonstration de cette proposition, mais la marge est trop étroite pour la contenir.

Fermat, Arithmetica de Diophante (traduction)

Or, la démonstration de ce théorème est en fait très récente : elle a été faite en 1994 par Andrew Wiles [2], un mathématicien grand breton. La subtilité de la blague réside dans le fait qu’en plus d’avoir nécessiter 350 ans, la démonstration en question fait plusieurs centaines de pages et fait appel à des concepts que l’on qualifiera pudiquement de « complexes ». En gros, soit Fermat avait une démonstration absolument géniale de simplicité sous le coude, soit il s’était trompé, soit il bluffait. Dans tous les cas, c’était quand même un effet d’annonce de compétition :

Hahaha ! Je connais la démo mais je vous laisse vous débrouiller ! Vous verrez, il y en a pour 5min (ou 350 ans, je sais plus lol).

Fermat (ou presque)

Et le triangle rectangle ?

Dans le théorème, il est précisé qu’il faut que n soit strictement supérieur à 2. En effet, dans le cas n=2, le théorème de Pythagore [3] correspond à un cas où cette équation a une solution. Par exemple, 3²+4²=5². D’où le triangle rectangle.

Comme quoi, les gens de chez Google ont de bonnes références !

[1] Parce que des fois on a pas envie de se fouler.

[2] Du coup, on devrait parler du théorème de Miles et non du grand théorème de Fermat puisque ce sont en théorie ceux qui démontrent un théorème qui lui donnent leur nom. Que voulez-vous, l’habitude est puissante, mais chez les mathématiciens !

[3] Le théorème de Pythagore nous dit que, dans un triangle rectangle, le carré de l’hypoténuse est égal à la somme des carrés des côtés opposés. Par exemple, si un triangle rectangle a deux côtés de 3cm et 4cm qui forment un angle droit, alors le dernier (l’hypothénuse) fera 5cm car 3²+4² = 9+16 = 25 = 5².

Mais pourquoi π² / 6 ?

Posted on 14 août 2011 par π² / 6

Les Suédois étant toujours aussi peu nombreux sur le campus (contrairement aux Allemands, aux Espagnols et surtout aux Français), j’ai beaucoup de mal à réunir suffisamment de matière pour rédiger un article sur le Suédois, le gus. Ce n’est pourtant pas faute d’essayer, mais bref. Comme suggéré dans les commentaires par un historien perplexe devant le nom du présent site, je m’en vais de ce pas lancer la rubriques « les maths, c’est magique ! » de ce blog en répondant à la question qui a donné son titre à cet article : mais pourquoi π² / 6 ?

Déjà, π, c’est cool

Je ne vous ferai pas l’offense de prétendre vous apprendre que π désigne le rapport de la circonférence du cercle à son diamètre. Jusque-là, je pense que tout va bien. Mais ce nombre a plusieurs caractéristiques intéressantes.

π est irrationnel

Cela ne veut bien évidemment pas dire que π fait des mathématiques financières ou raconte à qui veut l’entendre que la fin du monde est pour décembre 2012. En maths, on appelle nombre irrationnel un nombre qui ne peut pas s’écrire sous forme de fraction. Par exemple, 3/7 est rationnel, tout comme 12 (qui s’écrit 12/1) ou encore 0,11111.. avec « une infinité de 1 »[1] qui s’écrit 1/9. π ne peut pas s’écrire sous forme de fraction, cela a été démontré au XVIIIème par Jean-Henri Lambert. On peut néanmoins s’en approcher autant qu’on veut pour peu que l’on ait à disposition une puissance de calcul suffisante. En effet, π est la limite de plusieurs série, c’est à dire qu’en ajoutant une « infinité »[1] de termes bien précis, on obtiendrait ce nombre. Même s’il est impossible de faire une telle somme, on peut l’approcher suffisamment en ajoutant un « grand nombre »[2] de ces termes. C’est notamment en ayant recours à de telles séries que l’on peut appliquer la formule de Machin[3] pour calculer autant de décimales que la puissance de calcul utilisée le permet.>

π est transcendant

Point de jugement de valeur ici, simplement une autre caractéristique mathématique. π n’est la racine d’aucun polynôme à coefficient entiers. « Fort bien» , me direz-vous, « mais cela ne me dit ni ce qu’est une racine ni ce qu’est un polynôme ». Remédions à cela.

Le rapport entre la transcendance divine et la transcendance mathématique ? C’est facile : il n’y en a aucun ! Notre ami bleuté l’aurait su s’il n’avait pas abusé de substances illicites néfastes (et lu cet article).

Polynôme : on appelle polynôme une fonction[4] de la forme P(X) = a0 + (a1 × X) + (a2 × X²) + (a3 × X^3) + … + (aN × X^N) où a0, a1, a2, a3… et aN sont des nombres. Par exemple, Q(X) = 3,5 + 2×X + π×X² est un polynôme.
Racine : Une racine d’un polynôme est un nombre qui l’annule. C’est à dire que si P est un polynôme et r une de ses racines, alors P(r) = 0. Par exemple, 2 est une racine de P(X) = 2 - 3×X + X². En effet, P(2) = 2-3×2+2² = 2-6+4 = 0.

Par exemple, la racine de 2 n’est pas transcendante puisqu’elle est racine de P(X) = 1×X²-2 et que 1 et 2 sont entiers.

Une fois ceci précisé, il devrait être clair que comme π est transcendant, on ne trouvera jamais de polynômes P à coefficients entiers (c’est à dire pour lesquels les nombres a0,…,aN sont entiers) tels que P(π) = 0.

On pourrait disserter sur π pendant des pages, d’ailleurs, wikipedia ne s’en prive pas. Mais intéressons-nous maintenant de plus près à « π² / 6 ».

Ensuite, π² / 6, ça l’est encore plus

Somme des 1/n²

J’ai parlé plus haut de série. Et bien π² / 6 est la limite vers laquelle converge une série : celle dite « des 1/n² ». En fait, si on additionne 1 (1/1²), 1/4 (1/2²), 1/9 (1/3²), 1/16 (1/4²),… On s’approche de plus en plus de π² / 6. Si tant est que cela ait un sens, on tomberait sur π² / 6 en ajoutant une infinité de ces termes[1]. Ce résultat, surnommé « problème de Bâle » a été trouvé par Euler, un de ces mathématiciens dont on trouve le nom partout puisqu’il a travaillé dans énormément de domaines, y compris en physique. Il doit se partager avec Gauss la moitié des noms de théorèmes de mathématiques et de physique ![5]

Euler, par Emanuel Handmann. Aurai-je moi aussi un beau chapeau quand j’aurai fini mes études ? Mystère…

La fonction zêta de Riemann

Les mathématiques sont loin d’être « terminées », il reste en effet beaucoup de problèmes non résolu à l’heure actuelle. L’un d’entre eux est le problème des « pôles de la fonction ζ de Riemann ». « Pôle » a ici un sens similaire à celui de racine dans le cas des polynôme : c’est un point en lequel la fonction s’annule. On pense à l’heure actuelle savoir grosso modo où ils se trouvent, mais cela n’a pas été démontré. D’ailleurs, si vous arrivez à le démontrer (ou à démontrer que ce qu’on croit est faux), vous êtes riche puisqu’il s’agit d’un des problèmes du millénaire. Résolvez-le et vous gagnerez un million de dollars ! Le rapport avec π² / 6 ?

ζ(2) = π² / 6

Et je veux ce million.

Conclusion

J’espère avoir été clair, n’hésitez pas à poser des questions dans les commentaires si des points sont obscures. J’espère aussi avoir montré pourquoi π² / 6 est un nom parfait pour ce site ! Demain, j’ai rendez-vous avec le responsable des mathématiques à KTH pour affiner mes choix d’options, je devrais donc bientôt savoir à quelle sauce je vais être mangé. Enfin !

[1] La notion « d’infini » est beaucoup plus compliquée qu’il n’y paraît et fait appel à celle de limite qui est également loin d’être triviale. Considérez ces contenus entre guillemets comme des simplifications pédagogiques 😉

[2] De plus, il existe des méthodes mathématiques permettant de connaître à l’avance une majoration de l’erreur en fonction du nombre de termes ajoutés. Cela signifie qu’avant même de lancer le calcul et sans connaître la « vraie » valeur de π, on peut savoir que notre calcul nous donnera par exemple les 10 premières décimales justes, la suite étant a priori (et de fait, sauf chance incroyable) fausse.

[3] Du nom de M. Machin. Oui oui, ce n’est pas un trou de mémoire de ma part, il s’appelait vraiment Machin !

[4] Les fonctions seront peut-être l’objet d’un article dans le futur. N’ayant aucune idée quant à l’éventuelle date de publication de celui-ci, vous pouvez consulter en attendant consulter la page de wikipedia.

[5] Wikipedia liste les théorèmes de Gauss mais n’a pas de page dédiée pour Euler. Ils n’en sont pas moins nombreux, croyez-moi !

π² / 6

Pérégrination en Suède, maths, informatique et autres joyeusetés

Archives pour la catégorie Maths