Mathématique et Informatique - Gallium - Inria

Mathématique et Informatique
Philippe Flajolet & Gérard Huet L'informatique est à la fois science et technologie. La technologie est la
partie visible de l'iceberg, celle à laquelle est confronté le grand
public. Réservation d'avions, consultation de prévisions météorologiques
pour une île lointaine, échanges de courrier électronique, ou recherche
d'itinéraires en banlieue font désormais partie de la vie quotidienne. Que
ces services soient possibles, est largement sous-tendu par les progrès du
matériel, issus eux-mêmes d'avancées tant fondamentales qu'appliquées dans
des domaines variés des sciences physiques tels la physique des solides,
l'électronique, la microélectronique, ou l'optique. Mais une condition sine
qua non est le progrès fondamental accompli au cours des cinq dernières
décennies sur les aspects dits logiciels, c'est-à-dire l'algorithmique, la
programmation, et, plus généralement, le développement de systèmes de
calcul complexes. Ceci repose sur une science jeune mais désormais
établie, l'informatique, largement indépendante des dispositifs matériels
(ordinateurs). Nous parlerons ici de la discipline scientifique qu'est l'informatique[1].
Nous en dégagerons d'abord les principales racines historiques ancrées dans
la tradition scientifique classique. Puis nous examinerons la manière dont
informatique fondamentale et sciences mathématiques sont intimement liées
tout autant dans leur développement récent que dans un futur prévisible.
1. Contexte historique L'informatique a des racines qui remontent aux mathématiques de
l'antiquité, à travers deux courants principaux : l'algorithmique, qui
systématise la notion de calcul, et la logique, qui formalise la notion de
démonstration. Ces deux aspects sont déjà fortement présents dans la
science grecque: Archimède et Diophante « calculent » l'aire sous une
parabole et les solutions de systèmes d'équations en nombres entiers,
tandis qu'Euclide dégage la notion de système axiomatique pour la géométrie
élémentaire, et Aristote abstrait du discours la logique propositionnelle.
Il est piquant de noter que ces deux courants fondamentaux constituent
toujours la base de l'informatique contemporaine. Jusqu'au XIXe siècle, de grands mathématiciens, comme Newton, Leibniz,
Euler ou Gauss, inventent des méthodes originales de calcul numérique et
symbolique. Celles-ci sont destinées à un calculateur humain, mais leur
caractère systématique préfigure déjà ce qui servira à établir les premiers
fondements de l'informatique. En parallèle, au tournant du XXe siècle, le
courant axiomatique conquiert de nombreuses branches des mathématiques,
avec pour corollaire des interrogations méthodologiques (ou
« métamathématiques ») donnant lieu à une discipline nouvelle -la logique
mathématique. De ce courant seront issues en particulier une théorie
générale de la calculabilité (Post, Turing, Kleene, Church) et plusieurs
théories de la démonstration (Gentzen, Herbrand, Heyting). Ces théories
constituent la seconde base de l'informatique : dès qu'il sera nécessaire
de formaliser la notion d'algorithme, de définir des langages de
programmation propres à l'expression non-ambiguë d'algorithmes, de vérifier
la cohérence de langages et de programmes, elles s'avéreront
particulièrement précieuses. 1.1 Algorithmique Par algorithme, on entend un procédé systématique de calcul. Le sens
médiéval est celui de méthode pour effectuer les quatre opérations
arithmétiques de base (formalisée par Al Khwarizmi au IXe siècle), mais il
s'étend rapidement à tout procédé de calcul. Les calculs étant effectués
par les scientifiques eux-mêmes (ou leurs disciples), la notion de
complexité est déjà très présente : on sait ou on perçoit bien que tel
procédé est plus efficace - converge plus vite ou nécessite moins de
manipulations - que tel autre, mais la notion reste informelle et
subliminale. Jusqu'au XVIIe siècle, il y a d'ailleurs souvent coïncidence
entre mathématiques et calcul proprement dit. Newton, célèbre (entre
autres) pour son procédé numérique de résolution d'équations invente même
des procédés de calcul que l'on qualifierait de nos jours de symbolique ou
formel : voir par exemple le fameux « polygone de Newton » utile à la
caractérisation locale des courbes algébriques. Au milieu du XVIIIe siècle,
Euler propose de nombreux procédés de calculs, tant numériques (la
discrétisation des équations différentielles) que symboliques
(l'intégration en termes finis et l'explicitation de nombreuses sommes et
intégrales définies). Le dix-neuvième et la première moitié du vingtième
siècle verront ces approches se développer, par exemple en liaison avec la
constitution de tables, lesquelles sont un « pré-calcul » effectué une
seule fois et disponible universellement pour des tâches répétitives.
Jusqu'aux années 1950, la construction de telles tables s'appuie d'ailleurs
déjà sur une utilisation systématique, mais encore supervisée par l'homme,
de calculateurs mécaniques ou électromécaniques. La seconde guerre mondiale verra un investissement important dans le
développement des calculateurs à fins militaires (défense anti-aérienne
mais aussi analyse cryptographique), période pendant laquelle le
mathématicien John von Neumann joue un rôle connu de tous. Ainsi, les
premières applications sont-elles très largement du ressort de l'analyse
numérique de systèmes différentiels. La période qui suit, de 1945 à 1955,
est celle où s'effectue progressivement la fusion entre calculateurs
scientifiques et calculateurs de gestion, domaine dans lequel fleurit la
puissante société IBM. C'est sur ce terrain que va se développer ce qui est
d'abord un ensemble de savoir-faire techniques et qui donnera ensuite
naissance à la science informatique. Le volume en croissance régulière des données à traiter (par ex., les
recensements), la diversité et l'hétérogénéité de ces mêmes données
nécessitent des méthodes d'accès rapide à l'information non-numérique.
Comment accéder efficacement à des ensembles de données dans un espace
multidimensionnel ? Comment trouver rapidement une information
partiellement spécifiée ? Comment maintenir l'efficacité sur des données
qui varient dynamiquement ? Comment interroger des volumes de données
organisés selon des critères différents ? Sur ces questions, se constitue
à partir des années 1960 un ensemble de méthodes : on en arrive aux
concepts de structures de données, puis de bases de données, et l'on dégage
simultanément quelques grands paradigmes de programmation, comme le célèbre
principe « diviser-pour-régner » fondé sur la récursion. Un regard sur les
premiers volumes du journal ou des communications de l'ACM montre
d'ailleurs que cette entreprise n'allait pas de soi. Les mathématiques
jouent en cela un rôle conceptuel majeur, et par exemple les meilleures
structures de données actuelles sont souvent fondées sur une utilisation
astucieuse de la structure d'arbre, dérivé naturel de la notion
mathématique de graphe, dont Knuth affirme qu'il s'agit de la structure la
plus importante de toute l'informatique. C'est aussi un effet de la
formalisation mathématique du domaine que des algorithmes qui
représentaient des tours de force d'ingéniosité il y a quatre décennies
puissent maintenant être pensés et programmés de manière simple par un
étudiant d'université bien formé. Nous discutons à la section 2 ci-dessous
quelques grandes étapes et quelques faits marquants de cette évolution. 1.2 Logique. La logique est une préoccupation philosophique depuis l'antiquité, par ses
rapports avec le langage, et comme investigation rationnelle de la notion
de vérité. Support de la rhétorique, elle resta longtemps une discipline
distincte de la mathématique, avant que les considérations sur les
fondements et sur la notation mathématique ne développent dans les années
1930 une discipline renouvelée dite logique mathématique, et notamment la
théorie de la démonstration. Mais les progrès de l'électronique dans les
cinquante dernières années, en permettant le développement de machines à
calculer électroniques ou ordinateurs, a permis de transcender la notion
traditionnelle de calcul pour élaborer une notion étendue de calcul formel
possiblement non déterministe faisant rentrer l'élaboration de
démonstrations dans un cadre général de programmation. Ceci a re-déplacé la
logique mathématique, qui se trouve aujourd'hui au c?ur des préoccupations
de l'informatique. Une convergence remarquable entre la théorie des
catégories (qui renouvelle ce qu'on appelait avant-guerre l'algèbre
universelle), la théorie de la démonstration (avec son dernier avatar, la
ludique liée à la théorie des jeux), et la théorie des langages (elle-même
en rapport dialectique fécond avec la linguistique), permet maintenant le
développement d'une méthodologie appelée théorie des types, qui donne un
fondement rigoureux à la sémantique des langages de programmation, lesquels
sont passés du statut de notation de haut niveau pour des codes exécutables
par une machine, à celui de notations complètement générales pour les
mathématiques (plus ou moins constructives). Les « programmes »
informatiques deviennent ainsi les squelettes de la preuve de leur
adéquation à des spécifications formelles. L'informatique se dote de l