La jeune informatique et les mathématiques anciennes entretiennent des collaborations fructueuses. La première tire parti des théorèmes et des logiques pour concevoir ses langages, la seconde profite de la puissance de calcul des ordinateurs pour ses démonstrations. Cette relation semble prendre même une forme de symbiose…
Des mathématiques emblématiques de l’informatique
De nombreux domaines de l’informatique utilisent les mathématiques. Le traitement de l’image recourt à la géométrie et l’algèbre, la cryptographie à la théorie des nombres. Trois domaines mathématiques nous semblent emblématiques de cette relation.
Le système binaire : base de plusieurs langages informatiques
Le système binaire utilise le 0 et le 1. Deux chiffres qui représentent l’informatique dans de nombreuses illustrations. C’est une base deux. Un tel calcul demande une gymnastique de l’esprit, car nous sommes habitués à compter en base 10. Par exemple, 1+1 = 10 et non 2 comme en base 10.
Le code ASCII et l’Unicode U-TF8 se fondent sur le binaire. Les langages de programmation de bas niveau, comme le langage machine, et le langage d’assemblage l’utilisent également.
Il sert aussi au fonctionnement des transistors et des composants électroniques. Il est en effet aisé de gérer un flux électrique avec le système binaire : 1 pour le lancer, 0 pour l’arrêter.
Les mathématiques booléennes : de la logique avant toute chose
Les mathématiques booléennes, proches du système binaire, sont très présentes en informatique. On les retrouve dans le Java, le Pascal, le C#. Elles se caractérisent par ses principes de comparaison (=, ==, >) et ses opérateurs logiques : « ou », « et », « vrai, « faux », « non et, « non ou », etc. Les utilisateurs de tableurs en sont familiers quand ils comparent, filtrent, extraient des valeurs de leurs bases de données.
Les mathématiques booléennes illustrent le rôle majeur de la logique en informatique. En effet, les programmes sont essentiellement des suites d’instructions ordonnées avec logique. Le raisonnement d’un informaticien et la description de l’objet qu’il doit coder (une appli, un jeu vidéo par exemple) nécessitent de recourir à la logique.
Quand l’informatique réveille l’antique algorithme
Les algorithmes sont anciens, ils datent de l’époque babylonienne. Cela n’empêche pas l’informatique d’y recourir abondamment.
En effet, qu’est-ce qu’un programme informatique ? Un algorithme écrit dans un langage et exécuté par un ordinateur. Et que faut-il pour concevoir un algorithme ? Des mathématiques !
Ainsi, les algorithmes de distance, comme celui de Dijkstra et de Bellman-Ford, s’appuient sur la théorie des graphes. L’algorithme du chiffrement RSA utilise l’arithmétique : la congruence sur les entiers et le petit théorème de Fermat.
Quand le célèbre informaticien Knuth et ses deux comparses, Graham et Patashnik, rédigent Mathématiques concrètes, ils font la part belle aux algorithmes. Cet ouvrage de référence en informatique aborde largement les mathématiques. Des chapitres traitent de la théorie de nombres, des coefficients binomiaux, des séries génératrices, etc.
Les correspondances entre mathématiques et informatique
Les démonstrations mathématiques deviennent longues et complexes. Avec les détails et la formalisation, il est désormais difficile à un humain de les lire. Il a ainsi fallu pas moins de cent auteurs et des dizaines de milliers de pages pour démontrer le théorème de classification des groupes simples.
Mais un ordinateur, grâce à sa puissance de calcul, peut le faire. Des logiciels, les assistants de preuve, facilitent le formalisme et aident à la vérification et à l’exactitude des démonstrations. Le logiciel Coq, mis au point par Thierry Coquand, Gérard Huet et Christine Paulin-Mohring, a ainsi permis de démontrer le théorème des quatre couleurs et celui de Feit-Thomson.
Thierry Coquand va plus loin dans sa réflexion et évoque les « correspondances » entre les deux domaines, par exemple :
- la notation : la notation utilisée en informatique peut aider au formalisme des démonstrations mathématiques ;
- le langage fonctionnel : établit une correspondance entre programmation et démonstration ;
- les outils de vérification sont les mêmes ;
- les intuitions des informaticiens servent aux démonstrations mathématiques et les intuitions des mathématiciens servent à l’écriture des programmes.
Les systèmes de calcul formel sont une autre aide informatique aux mathématiciens. Le calcul formel manipule sur ordinateur des objets mathématiques comme les entiers, les polynômes, les groupes, les algorithmes, etc. Des systèmes, tels Maxima ou Pari/GP, permettent d’effectuer ces manipulations.
A la croisée de l’informatique et des mathématiques, ce domaine récent intéresse les mathématiciens sensibles à l’informatique et les « informaticiens mathématiquement réceptifs ».
Des mathématiques nécessaires à la conception de logiciels qui aident à faire des mathématiques : assurément une forme de symbiose s’établit entre les deux domaines.
Et vous, de quel raisonnement mathématique avez-vous besoin quand vous faites de l’informatique ?