Td corrigé Mathématique et Informatique - Inria pdf

Mathématique et Informatique - Inria

Le nombre et la taille de ces configurations étant commensurables avec ce que permettent les ordinateurs du moment, un examen exhaustif des cas spéciaux .... en algèbre booléenne (BDD, SAT), et le développement d'une nouvelle formalisation des circuits combinant les automates finis synchrones avec des opérateurs ...




part of the document



, 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. 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 la sorte d’un appareil mathématique puissant, permettant de guider la conception de logiciels efficaces, robustes et fiables.

Nous allons expliquer dans ce chapitre les principales articulations de ces deux courants qui interpénètrent profondément la mathématique et l’informatique fondamentale.


2. Algorithmique

2.1 Bases.

À partir de 1965, Donald E. Knuth, alors à l’Université de Stanford, entreprend un gigantesque travail de synthèse. Il s’agit de l’ouvrage en plusieurs volumes intitulé The Art of Computer Programming, où sont résumés les principaux algorithmes et structures de données de base de l’informatique non numérique. Dans le même temps, Knuth invente un nouveau domaine, l’analyse d’algorithmes. Il s’agit de caractériser le comportement en nombre d’opérations élémentaires, de ces méthodes de calcul. Allant bien au delà de la détection des cas pathologiques qui donnent lieu aux pires cas (« worst-case analysis »), l’analyse d’algorithmes s’attache dans un premier temps à évaluer les algorithmes selon leur comportement moyen (« average-case analysis »), puis, plus finement, selon leur comportement typique (« probabilistic  analysis »). Cette entreprise globale qui se poursuit de nos jours fournit un cadre rigoureux à la comparaison des algorithmes, en même temps qu’une organisation de ces algorithmes en grandes catégories selon leur fonction et leur complexité mesurée par la consommation de ressources (temps, mémoire). Ce que constate déjà Knuth, et qui reste dans une large mesure un mystère, c’est d’après le mot du physicien Eugène Wigner « la déraisonnable efficacité des mathématiques » dans ce secteur. Il est en effet surprenant de découvrir que des domaines fort classiques des mathématiques, développés le plus souvent sans visée applicative immédiate, comme l’analyse combinatoire et l’analyse asymptotique (réelle ou complexe),« aient à voir » avec un monde aussi artificiel que celui des ordinateurs et de leurs programmes,

Les années 1960—1970 voient également l’émergence d’une théorie de la complexité, domaine qui s’inspire d’une abstraction de la complexité des algorithmes et puise ses racines dans la théorie de la calculabilité examinée ci-dessous. L’optimisation combinatoire, issue pour une large part du traitement informatique de problèmes de recherche opérationnelle, effectue une jonction avec la théorie de la complexité grâce aux travaux de Stephen Cook et Richard Karp vers 1970. Ceux-ci montrent en effet que parmi des centaines de problèmes d’optimisation discrète qui étaient l’objet de recherches éparses, il existe une classification fondamentale: d’une part la classe P de ce qui est résoluble en temps polynomial en la taille des données; d’autre part la classe NP des problèmes dont une solution est facilement vérifiable mais difficilement trouvable (l’aiguille dans une botte de foin!). Cette trame imprègne désormais l’ensemble de l’informatique; elle donne à son tour lieu à l’émergence de nouvelles méthodes conçues pour contourner les barrières de complexité de la classe NP: techniques d’approximation, approches probabilistes, raffinements « paramétrés » en sont des exemples. Notons que le problème P =? NP est l’un des sept « Problèmes du Millénaire » recensés en sciences mathématiques par la Fondation Clay.

À partir de 1976, Michael O. Rabin découvre et popularise l’importance d’approches probabilistes dans la conception d’algorithmes. C’est ce qu’on appelle parfois l’aléatoirisation (randomisation, en anglais) —l’aléa est introduit volontairement dans le calcul. L’ordinateur peut avoir intérêt à jouer aux dés… Ce changement de paradigme de programmation apporte dans un nombre de domaines des gains spectaculaires. Il s’agit notamment des calculs arithmétiques, des structures de données classiques pour l’accès rapide à l’information, de la géométrie algorithmique, et de l’algorithmique distribuée. Ainsi une algorithmique probabiliste permet pour la première fois de déterminer la primalité (avec risque d’erreur inférieur à 10-100) de nombres de plusieurs centaines de chiffres : le système cryptographique RSA qui garantit quotidiennement la sécurité de plusieurs millions de transactions repose sur ces techniques. Dans un autre domaine, afin que des ordinateurs communiquent en réseau, il est avantageux de se départir de l’approche déterministe de la téléphonie classique et de résoudre les conflits d’accès tout simplement par tirages au sort: ces principes sont à la base des réseaux Ethernet et du protocole TCP régissant plus de 90% des échanges sur l’Internet.

Pour les trois grandes catégories de problèmes cités, il est clair qu’une démarche mathématique joue tout d’abord un rôle capital dans la formalisation des problèmes et la constitution d’un cadre de pensée. La recherche en optimisation combinatoire n’est plus la même —elle est infiniment plus structurée et fructueuse— après les travaux de Cook, Karp, et leurs successeurs. Les percées de Knuth et Rabin, relayées par une large part de la communauté des chercheurs informaticiens, ont changé la manière dont se conduit la recherche en algorithmique,en offrant des repères clairs dans ce qui ne serait autrement qu’une jungle de techniques. Les sciences mathématiques alimentent continûment l’algorithmique, en suscitant les principes de nouveaux algorithmes ou encore en permettant, via l’analyse d’algorithmes,les optimisations et dimensionnements fins qui sont nécessaires à de nombreuses applications informatiques.

2.2. Présent et futur.

À l’aube du troisième millénaire, la question est posée de déterminer si cette période des pionniers de l’informatique s’appuyant sur les sciences mathématiques est ou non en phase terminale. Il est tentant de penser que la science informatique a fait son œuvre et peut maintenant tranquillement passer le témoin à une recherche technologique pilotée par les besoins du temps. Nous vivons en effet une période où un ordinateur portable de faible coût possède une puissance de calcul un million de fois supérieure à celle des premiers calculateurs électroniques, et où un étudiant peut acquérir un dispositif de stockage de données permettant de conserver l’équivalent de plusieurs dizaines de milliers d’ouvrages. La loi de Moore, proposée par l’un des fondateurs d’Intel dès 1965, stipule de fait le doublement de la vitesse de calcul des ordinateurs tous les 18 mois. En plus de trente ans de vie, elle n’a pas été démentie et les physiciens estiment que son applicabilité s’étendra encore jusqu’à l’horizon 2010, avant que ne soient atteintes les limites imposées par la structure atomique de la matière et les phénomènes quantiques. La problématique algorithmique ne deviendrait-elle pas dans ces conditions quelque peu désuète voire obsolète ?

En fait une révolution, appuyée initialement par le Département de la Défense des Etats-Unis et relayée par d’actifs universitaires débouche dans les années 1990 sur une version déjà accomplie de l’Internet, réseau mondial reliant initialement le monde académique et sur lequel se greffent progressivement nombre d’industriels. Celui-ci permet communication et échange de données à distance. Le besoin de disposer de surcroît de documents en accès partagé, combinant texte et images, conduit alors d’inventifs informaticiens du CERN à développer ce qui devient très vite connu à partir de 1995 comme la Toile ou le Web. La Toile change la donne! Elle permet l’échange massif de données extrêmement variées et non structurées. On estime à plusieurs milliards le nombre de pages aujourd’hui accessibles à tout un chacun. (Il se produit même le fait étonnant que l’infrastructure des réseaux informatiques englobe graduellement l’infrastructure téléphonique traditionnelle.)

Cette arrivée de la communication informationnelle et informatique massive pose un grand nombre de problèmes nouveaux. Disons tout d’abord que, face à la loi de Moore, le doublement des informations accessibles ou stockables obéit actuellement à un rythme de croissance d’un facteur deux tous les 8 mois environ. Donc, ne serait-ce que pour maintenir des performances constantes, de nouveaux algorithmes doivent être en permanence conçus, comme l’observe Robert Sedgewick. De fait, il existe une importante communauté de recherche en informatique travaillant dans le domaine des données massives et de la fouille de données (« data mining »). Parmi le foisonnement d’algorithmes récents, signalons par exemple ceux qui s’appliquent aux flots de données et en extraient des informations essentielles au prix d’une mémoire très réduite et d’une seule passe. C’est un peu comme si l’on pouvait assister à une pièce de Shakespeare équipé d’une simple feuille de papier, d’un crayon et d’une gomme, et ressortir avec une estimation précise (typiquement avec moins de1% d’erreur) du nombre de mots différents prononcés par les acteurs. L’algorithme évoqué ici repose sur la technique d’aléatoirisation déjà discutée, sur l’analyse fine de phénomènes probabilistes semi-classiques, ainsi que sur d’intéressantes méthodes d’analyse asymptotique complexe. Ce cas récent illustre bien l’une de nos thèses, à savoir que les relations d’échange dialectique entre mathématique et informatique sont loin d’être achevées.

La compression de données est un thème lancé par les travaux de Claude Shannon (à partir de 1948), lui-même inspiré par la thermodynamique statistique, voir l’identification entre entropie et quantité d’information. Signalons qu’un texte est compressible dans un rapport de l’ordre de 3, une image dans un rapport entre 10 et 100, une séquence vidéo dans un rapport 1000 environ —les coûts de transmission et de stockage en sont diminués d’autant. Ce domaine se fonde sur la théorie de l’information (que l’on retrouve en statistiques et en analyse financière) et passe par la formalisation de la notion de source, laquelle emprunte dans son esprit autant à la théorie des probabilités qu’à la théorie ergodique. Les algorithmes de compression reposent, entre autres ingrédients, sur les structures d’arbres et sur la transformation de Fourier. Le domaine connexe de la correction d’erreurs, lui aussi lancé par Shannon, intervient fréquemment ; en effet, toute connexion par modem met en jeu de la correction d’erreur, et il est frappant qu’une norme internationale détermine un certain polynôme sur un corps fini : c’est sur ce polynôme qu’est construit par des méthodes d’algèbre des corps finis un procédé de transmission robuste. L’avènement des DVD n’a d’ailleurs été possible que grâce à l’élaboration de codes fondés sur l’exploitation de la structure des corps finis et présentant de très haute capacité de correction —une éraflure de la largeur d’un cheveu peut entraîner la perte de plusieurs milliers de bits.

Enfin, comme l’ont reconnu il y a peu (et avec réticence) les gouvernements occidentaux, la cryptographie correspond à un besoin du grand public. Il s’agit de garantir confidentialité et authenticité des communications sur des réseaux ouverts à tous. La première génération est représentée par le système mathématico-informatique RSA dont le succès a déjà été souligné. La mise en œuvre de ce système repose sur des propriétés élémentaires de la théorie des nombres exploitées astucieusement et conjuguées à une algorithmique adaptée.La sécurité de ce système repose sur le problème mathématiquement et algorithmiquement difficile de la factorisation de grands entiers (disons, supérieurs à 10100) et a donné lieu à une branche nouvelle, la théorie algorithmique des nombres à laquelle participent de concert mathématiciens et informaticiens. Il est de surcroît intéressant de noter que de nouvelles générations de systèmes dotés de meilleures caractéristiques (longueur de clefs, sécurité) sont en développement et que plusieurs d’entre eux reposent sur la géométrie algébrique des courbes et variétés sur les corps finis. Certains de ces nouveaux systèmes ont la curieuse caractéristique de revitaliser des études vieilles d’un siècle et quelque peu oubliées, portant sur la structure des courbes hyperelliptiques, tout en bénéficiant d’acquis extrêmement récents de la géométrie arithmétique.





3. Logique et programmation


L’objet d’étude de l’informatique s’est progressivement déplacé des machines vers les algorithmes et les langages. Des considérations de linguistique formelle et de logique allaient ainsi marquer l’informatique fondamentale. Rappelons que la logique elle-même, au départ une préoccupation des philosophes avec la notion de vérité, vint progressivement se mathématiser, d’une part avec la théorie des modèles qui utilise les structures mathématiques de théorie des ensembles et d’algèbre universelle (catégories), et d’autre part avec la théorie de la démonstration ou méta-mathématique qui se préoccupe de notations, de preuves, et plus généralement des structures combinatoires sous-jacentes.

Très vite, il fut reconnu que la logique mathématique était l’un des principaux fondements de l’informatique. Mais l’interaction mit du temps à se mettre correctement en place ; en effet, la théorie des ensembles et, en France tout particulièrement, l’effort Bourbakiste allaient rigidifier le discours officiel des mathématiques autour d’un langage standardisé de théorie des ensembles de premier ordre, axiomatisé dans un calcul des prédicats classiques (c’est-à-dire admettant le principe du tiers exclu). La notion de fonction, associée traditionnellement à un procédé de calcul, était reléguée à une place auxiliaire de relations fonctionnelles ou graphes de fonctions extensionnelles. Ce point de vue est inadéquat pour un informaticien, pour lequel la fonction abstrait l’algorithme. Identifier toutes les fonctions qui calculent la forme triée d’une liste empêche de s’intéresser aux propriétés intentionnelles de leurs algorithmes, comme la complexité du calcul. La première étape consiste donc à dégager une notation fonctionnelle uniforme pour noter l’algorithme qui, à la variable formelle x, fait correspondre la valeur d’une expression e[x] contenant des occurrences de x. En effet, la méta-notation x(e[x] n’a pas de bonnes propriétés de composition.

Le logicien Alonzo Church allait changer cet état de fait dans les années 1930, en proposant un formalisme élégant pour les notations fonctionnelles, appelé lambda-calcul ((-calcul), où maintenant l’expression ((x. e[x]) (qui abstrait la fonction associant à x la valeur de l’expression e[x]) est une formule à part entière, pouvant notamment être utilisée comme sous-formule. La notion de calcul y est réduite à une règle très simple, dite (-réduction. Cette notion de calcul non-déterministe vérifie des propriétés remarquables, notamment la confluence, qui exprime que les calculs convergent en une forme normale unique. Ce calcul allait progressivement passer du statut de formalisme définissant les fonctions calculables (c’est-à-dire pouvant servir de codage aux fonctions partielles récursives de l’arithmétique, parmi d’autres formalismes équivalents comme les machines de Turing) au statut de primitive centrale des langages de programmation des informaticiens. D’autres formalismes similaires, comme le (-calcul de Milner, furent inventés par la suite pour modéliser notamment les processus concurrents.

De même que certaines précautions doivent être prises en théorie des ensembles pour éviter les paradoxes issus de notations ensemblistes trop laxistes telles que {x (x( x }, il convient de munir le (-calcul de limitations stratifiantes pour le restreindre à des calculs convergents. C’est ainsi que Church dut recourir à un système de types pour restreindre le calcul à dénoter des fonctions totales, dans un calcul des prédicats d’ordre supérieur appelé théorie des types simples. Bien sûr, tout système bureaucratique de ce genre est relativement ad-hoc, et l’espoir d’une notation uniforme pouvant servir de fondement à une Mathématique cohérente universelle s’est évanoui avec la destruction par Gödel du programme de Hilbert.

Le (-calcul n’est pas qu’une notation pour les expressions fonctionnelles. Sous sa forme typée, les règles d’inférence définissant le typage peuvent être considérées comme des règles logiques très générales. C’est ainsi que les (-termes simplement typés peuvent être vus comme des notations pour les preuves sous forme de déduction naturelle du fragment implicationnel du calcul propositionnel. Cette correspondance, dégagée progressivement par Curry, Howard et de Bruijn, est un isomorphisme profond entre espaces fonctionnels et structures de démonstration. Elle permet notamment de faire correspondre à la preuve formelle d’un énoncé mathématique un programme informatique, qui réalise cet énoncé comme spécification.

À l’inverse, un programme informatique peut être considéré comme squelette d’un raisonnement mathématique. Ce point de vue extrêmement fécond allait être développé dans les vingt dernières années dans un programme de Théorie des Types, rassemblant des logiciens et des informaticiens à la recherche des fondements logiques de la programmation. Le cadre dit intuitionniste des mathématiques constructives allait servir de langage de spécification à la partie purement fonctionnelle de la programmation, mais d’autres paradigmes allaient trouver leur place pour justifier d’autres constructions programmatoires, comme le call-cc, qui correspond à l’utilisation du tiers exclu en logique classique, par exemple dans le ((-calcul. Ce programme de réalisabilité logique fait ainsi apparaître une analogie profonde entre la programmation d’algorithmes informatiques et la mise au point de démonstrations mathématiques. Ce domaine a été particulièrement actif en Europe pendant les deux dernières décennies, et notamment en France avec la logique linéaire, le calcul des constructions, et plus généralement les travaux menés à l’Institut de Mathématiques de Luminy, aux laboratoires de l’INRIA à Rocquencourt et à Nancy, au laboratoire LRI de l’Université d’Orsay, au laboratoire PPS de l’Université Paris 7, et au laboratoire de Mathématiques de l’Université de Chambéry. L’informatique française a d’ailleurs toujours été en pointe dans la conception de langages de programmation, puisqu’on lui doit notamment ADA, Prolog, Eiffel et Caml.

Ce programme de recherche fondamentale, à la frontière entre la logique mathématique et l’informatique, trouve sa justification applicative dans la problématique de la sécurité des logiciels. D’une part, le typage des langages de programmation permet de certifier qu’un programme accepté par le compilateur (qui comporte un module d’analyse statique vérifiant l’adéquation du programme au système de types, éventuellement en en synthétisant le type le plus général) ne peut échouer à l’exécution, ni ne peut provoquer de corruption des structures de données. D’autre part, cette recherche permet de concevoir des environnements de programmation sophistiqués, assistant un concepteur à construire un logiciel conforme à ses spécifications, voire synthétisant un programme certifié correct à partir de la preuve de cohérence de ses spécifications. Le logiciel de manipulation de preuves Coq permet d’expérimenter avec ces nouvelles technologies. La société Trusted Logic, spécialisée dans l’élaboration de solutions sécuritaires fiables basées sur la carte à puce, a ainsi pu obtenir la certification au niveau le plus élevé de la chaîne d’exécution du langage JavaCard de SUN.

Un autre avatar des études de sémantique dénotationnelle, initiées dans les années 1970 par les informaticiens théoriciens pour comprendre la notion de calcul possiblement non terminant, a été le développement de la programmation du temps-réel, autour notamment des langages réactifs Lustre au laboratoire Verimag de Grenoble et Estérel aux laboratoires de l’Ecole des Mines et de l’INRIA à Sophia-Antipolis. Le premier allait trouver son application dans l’avionique Airbus, le second, à travers la Société Estérel Technologies, est en train de devenir un acteur incontournable de l’automatique et de la conception de circuits. Finalement, notons les recherches prometteuses sur des formalismes de calcul de processus tels que les réseaux d’interaction ou le join-calculus, qui contribuent à poser les fondements des futurs langages de programmation de l’informatique distribuée, enjeu économique considérable à l’heure du déploiement d’Internet.


4. Quelques domaines-frontière

Rappelons d’abord que la discipline informatique se distingue des autres sciences par son corpus propre de méthodes, d’objets, et de problématiques, désormais bien établi. Elle diffère des mathématiques par le fait qu’elle examine des objets variant dynamiquement au cours d’un calcul, qu’elle se soucie de leurs représentations, qu’elle est liée à une notion fondamentale de complexité, et qu’elle doit raisonner sur des systèmes qui sont sans équivalent en logique mathématique classique (systèmes distribués, par exemple). Comme nous l’avons souligné sur quelques exemples choisis, la démarche mathématique imprègne dans le même temps le développement de l’informatique fondamentale: nombre de théories et résultats mathématiques y sont utilisés, tandis que le schéma mathématique définition-théorème-preuve joue un rôle capital dans la structuration des connaissances. En ce sens, la situation de la science informatique vis-à-vis des mathématiques peut être dans une certaine mesure comparée à celle de la physique théorique ou de la physique mathématique.

Dans cette section, nous examinons quelques uns des courants contemporains où se manifeste une synergie particulière entre mathématiciens et informaticiens.

4.1. Mathématiques expérimentales.

Une conjecture célèbre du XIXe siècle énonce que toute carte de géographie (c’est-à-dire, tout graphe planaire) est coloriable avec au plus quatre couleurs. Cette conjecture, objet de très nombreuses tentatives infructueuses, resta ouverte plus de cent ans. En 1976, Appel et Haken surprirent la communauté en en offrant une preuve fondée sur l’utilisation de l’ordinateur. En gros, une analyse fine et originale de la combinatoire qui est en jeu réduit l’infini des exceptions a priori possibles à un nombre élevé mais fini de configurations spéciales. Le nombre et la taille de ces configurations étant commensurables avec ce que permettent les ordinateurs du moment, un examen exhaustif des cas spéciaux conclut la preuve. Cet exemple est emblématique de l’utilisation de l’outil informatique dans les sciences, mais il faut noter que la discipline informatique n’y intervient que très indirectement, en fournissant le soutien logistique des langages de programmation, systèmes, et modes de représentation des données. Le cœur de la difficulté réside ici véritablement dans l’analyse du problème et dans une vision novatrice de la combinatoire qui y intervient.

Waring affirme en 1770 que tout cube d’entier est somme d’au plus neuf cubes et tout bicarré somme d’au plus dix-neuf bicarrés. La conjecture portant sur les bicarrés sera finalement résolue deux siècles plus tard (en 1986) par Balasubramanian, Deshouillers, et Dress, ce par une succession de procédés où alternent estimations de sommes trigonométriques, méthodes de crible, congruences élémentaires, et vérification informatique. Cet exemple illustre bien la manière dont l’ordinateur en tant qu’instrument d’expérimentation peut affecter la conduite d’une recherche mathématique : la stratégie d’attaque du problème de Waring n’aurait sans doute pas été élaborée indépendamment des vérifications informatiques qu’elle nécessite.

De nos jours, de nombreux mathématiciens font appel à l’expérimentation dont les possibilités se voient décuplées grâce aux systèmes de calcul formel décrits ci-dessous. La démarche est tellement intégrée qu’elle n’est souvent même plus mentionnée explicitement dans les publications de recherche. Il importe de noter au passage que, contrairement à ce qui a pu être affirmé par certains vulgarisateurs, ceci ne diminue en rien le statut de la preuve dans l’activité de recherche mathématique. L’expérimentation permet par contre de gagner beaucoup de temps en écartant rapidement des hypothèses in fine non conformes à la réalité, mais aussi, et c’est plus essentiel, en permettant de mettre en évidence des phénomènes de nature quasiment physique qui sont en jeu dans un problème déterminé. C’est ainsi que la fameuse hypothèse de Riemann peut désormais s’insérer dans un vaste faisceau de conjectures quantitatives beaucoup plus fines concernant les espacements des zéros de la fonction zeta (Montgomery—Dyson), lesquelles sont remarquablement bien étayées par des vérifications extensives qui mettent en jeu une algorithmique non triviale (Odlyzko).

4.2. Calcul formel et mathématiques constructives.

On peut estimer à quelques millions le nombre d’installation dans le monde de systèmes de calcul formel. Ceux-ci sont utilisés par les mathématiciens, les informaticiens, et plus généralement les scientifiques de toutes les disciplines. Par calcul formel, on entend la possibilité de calculer sur des expressions mathématiques exactes et « symboliques », plutôt que sur des quantités numériques en précision limitée (et faible). Le développement du domaine s’effectue par des équipes aux compétences mixtes où il est parfois bien difficile de distinguer la part des uns et des autres.

Des progrès algorithmiques substantiels ont été accomplis dans les domaines liés aux systèmes d’équations polynomiales, aux systèmes différentiels, à l’intégration symbolique (plutôt que numérique), à la manipulation de séries, etc. Les types de base incluent des entiers et réels en précision arbitraire (seulement limités par les capacités physiques des machines), ce qui permet notamment l’expérimentation en analyse numérique impliquant des phénomènes très instables ou chaotiques. Le calcul formel intègre là de manière originale les acquis en structures de données et algorithmique générale de l’informatique, et il s’avère par exemple que les meilleurs algorithmes de multiplication de grands entiers mettent en jeu la transformation de Fourier (dans sa version discrète), diverses méthodes de partage récursif de type « diviser-pour-régner » (le calcul dit « rapide » de la FFT), et l’utilisation adaptée de propriétés de congruences arithmétiques. Par ailleurs, la réduction de systèmes polynomiaux se rattache à la géométrie algébrique contemporaine, la manipulation symbolique de nombreuses fonctions spéciales de la physique devient possible grâce à l’utilisation conjointe de l’algèbre différentielle moderne et de représentations de données adaptées, ou encore la factorisation de polynômes s’effectue au mieux par des méthodes exploitant à la fois la structure des corps finis et les principes d’aléatoirisation de la section 2.1. Ces recherches originellement motivées par des besoins lourds de calcul formel en physique (par ex., développement perturbatifs) débouchent désormais sur un petit nombre de grands systèmes généralistes, lesquels constituent de véritables « usines » d’algorithmique mathématique fondées sur des bibliothèques comportant de l’ordre du million d’instructions.

Mentionnons ici que le calcul formel peut être vu comme une version extrême (allant jusqu’à l’informatisation) du courant constructif en mathématiques, où les preuves d’existence abstraites sont remplacées par des constructions explicites. Ceci n’est pas sans impact sur l’enseignement des mathématiques dans les lycées et les universités, les méthodes constructives étant souvent plus concrètes donc plus faciles à aborder, tout en se prêtant volontiers à l’expérimentation personnelle.

4.3. Mathématiques discrètes.

Les mathématiques les plus classiques, celles notamment suscitées par les besoins anciens de la physique, sont continues. En revanche, tout calculateur est du point de vue opératoire un système fini, agissant sur des données elles aussi finies et plongées dans des ensembles dénombrables (dès qu’on fait abstraction de limitations secondaires). Les mathématiques discrètes sont par définition les mathématiques associées à de telles structures finies ou dénombrables, et elles sont donc a priori les plus proches de l’informatique. Ainsi les algèbres de Boole finies sont le cadre naturel de spécification des circuits élémentaires de calcul. Même si les propriétés structurelles de ces algèbres sont relativement pauvres, l’algorithmique associée est de facto l’un des points clefs de la vérification logique de circuits de calcul (par diagrammes de décision binaire ou systèmes de contraintes). De même, les corps finis sont à la base de nombreux procédés de codage assurant détection et correction des erreurs dans la transmission ou le stockage des données.

La combinatoire est le domaine d’étude des classes d’objets finis construits par un nombre fini de règles. Les concepts issus de la combinatoire ont conduit à doter l’informatique d’un riche ensemble de structures de données, parmi lesquelles en premier lieu la structure d’arbre : arbres de recherche pour la structuration de données uni- ou multi-dimensionnelles, arbres de termes en calcul formel, arbres de jeux (cf les programmes de jeu d’échecs), arbres de mots pour l’organisation de dictionnaires et la compression des données, etc. Les graphes sont les objets combinatoires historiquement les plus étudiés. Ils sont à la base d’une large fraction du domaine de l’optimisation combinatoire, lequel encapsule, à l’ère informatique, la plus ancienne recherche opérationnelle. Comme il a déjà été indiqué la théorie de la complexité a joué dans ce domaine un rôle structurant majeur, tandis que de nombreux algorithmes fondés sur des propriétés mathématiques parfois profondes apportent des gains substantiels. On avait grand mal dans les années 1950 à déterminer une tournée de commis voyageur reliant les cinquante capitales des Etats-Unis, alors qu’on sait désormais, pour ce problème de coût exponentiel, traiter exactement des graphes mettant en jeu plus de 10.000 sommets.

Le domaine des structures discrètes aléatoires a pris au fil du temps une importance croissante. Il s’agit de caractériser les principaux paramètres de structures combinatoires de grande taille, lorsque celle-ci obéissent à un modèle aléatoire déterminé. Arbres, graphes, nuages de points, permutations, et allocations sont certains des objets les plus fondamentaux. Leur examen sous l’angle de l’aléa répond aux nécessités de l’analyse d’algorithme décrite ci-dessus. Les résultats obtenus permettent une classification fondamentale vis à vis des ressources de calcul des principaux algorithmes d’utilisation générale en informatique. Ils permettent également la construction de modèles adaptés (par exemple, modèles de graphes aléatoires liés à la Toile ou à l’Internet), d’où découlent des conséquences pratiques tangibles quant au dimensionnement des réseaux et au réglage fin des protocoles de communication.

Le domaine de l’aléa discret est abordé de nos jours principalement sous deux angles complémentaires mais nullement contradictoires. D’une part les approches probabilistes ou stochastiques conduisent à immerger le discret dans un modèle limite continu (par ex., le mouvement Brownien) riche d’informations souvent plus facile d’accès. D’autre part, les approches dites analytiques poussent le calcul à ses limites dans le domaine discret en se fondant sur l’analyse combinatoire (dénombrements et transformations combinatoires associées à l’algèbre des séries), puis retirent les informations cherchées au prix d’une interprétation des séries génératrices dans le domaine complexe et d’un calcul fin des singularités associées. L’applicabilité du calcul probabiliste et stochastique à l’évaluation de performance de systèmes informatiques pouvait être en partie attendue, étant donnés les nombreux acquis de la période précédant l’informatique, en files d’attentes et modélisation du trafic téléphonique notamment. Les applications nouvelles de l’analyse combinatoire et de l’analyse complexe (dans un style qui prolonge celui des pionniers du début du vingtième siècle) sont peut-être plus surprenantes. (L’approche décrite ici est parallèle à celle de la théorie analytique des nombres, et des échanges portant sur les méthodes d’estimation se font jour, par ailleurs.) La théorie des systèmes dynamiques fait une entrée prometteuse dans ces questions, et par exemple, le comportement probable des algorithmes euclidiens, centraux en calcul formel, n’a été élucidé que tout récemment par des méthodes dynamiques. La physique statistique s’attaque même maintenant au problème délicat qu’est la caractérisation des instances typiques de problèmes d’optimisation combinatoire difficiles (NP-complets), ce en liaison avec la théorie très mathématisée des systèmes désordonnés. Si plusieurs cadres unifiés ont ainsi porté leurs fruits dans l’analyse quantitative des algorithmes et systèmes informatiques, on se doit de noter que de grandes questions ouvertes subsistent en théorie de la complexité intrinsèque des problèmes. Il s’agit de la question: Quelle est la borne inférieure au coût de tout algorithme de calcul répondant à un problème donné ? C’est un challenge que de dégager un ensemble de méthodes générales et de trouver ce qui pourrait être l’analogue de lois de conservation en physique ou du second principe de la thermodynamique pour le calcul. Le fort prisé problème P =? NP appartient à cette catégorie de questions.

4.4. Langages, mots, automates, circuits.

La théorie des langages formels et des automates est issue à l’origine des investigations en théorie de la récursivité, plusieurs logiciens ayant proposé comme modèle universel de calcul des systèmes de réécriture sur des mots formés sur un alphabet fini : systèmes de Post, machines de Turing, grammaires de Thue. Ces modèles de calcul se sont révélés équivalents du point de vue de leur expressivité, c’est-à-dire qu’ils peuvent coder des calculs arithmétiques arbitraires (fonctions récursives partielles). La caractérisation de sous classes décidables, et la complexité de leur appartenance, de leur équivalence, ou d’autres problèmes algorithmiques, est un thème classique depuis les débuts de l’informatique théorique dans les années 1950. Un article décisif de Rabin et Scott, en 1959, proposa un modèle de machines non déterministes, les automates finis, dont les transitions sont représentables comme arcs d’un graphe fini. Une caractérisation plus algébrique, en termes de langages rationnels, représente les langages reconnus par ces automates comme les ensembles de mots engendrés par des opérations d’union, de concaténation, et d’itération —les expressions régulières.

Le mathématicien français Schützenberger allait systématiser l’investigation algébrique d’une hiérarchie de langages formels, dont les langages réguliers (ou rationnels) forment le premier étage, et les langages hors contexte de Chomsky (ou langages algébriques) forment le deuxième étage. Les langages algébriques, reconnaissables par des automates à pile, sont particulièrement importants du point de vue de la linguistique formelle, et ont servi de cadre aux grammaires formelles utilisées pour définir la syntaxe des langages de programmation (et autres systèmes de notation systématiques). Ainsi les classes de langages algébriques déterministes (LR(k) et ses sous-classes LALR et LL), ont-elles été étudiées dans les années 1970 avec pour résultat des analyseurs syntaxiques efficaces et génériques résolvant l’un des problèmes essentiels de la compilation. En linguistique computationnelle, une classe plus large de langages faiblement contextuels (engendrés par exemple par les grammaires d’arbres adjoints TAG et leurs généralisations) permet de prendre en compte la syntaxe des langues naturelles, tout en préservant une complexité d’analyse qui soit polynomiale.

Les automates finis sont un mécanisme de calcul à la fois simple et riche : ils correspondent à un dispositif qui interagit avec son environnement selon une mémoire et des règles finies. Ces automates ont connu un renouveau avec l’apparition des langages réactifs, lesquels ont révolutionné la programmation synchrone et temps-réel, et se sont progressivement imposés dans l’industrie pour la conception des automates de contrôle, notamment en avionique et dans le nucléaire, comme nous l’avons expliqué plus haut. L’étude des automates finis et de l’algorithmique de graphes associée est l’un des domaines d’excellence nationaux, avec notamment les laboratoires LIAFA à Paris 7, le LaBRI à Bordeaux, le LIFL à Lille et le laboratoire d’informatique de l’Université de Marne la Vallée.

Les recherches en conception de circuits ont elles-mêmes engendré une grande variété de méthodes formelles —la taille des circuits intégrés n’autorise plus l’utilisation de méthodes artisanales, et la vérification des circuits est maintenant intégrée à la phase de conception. Cette recherche a engendré un renouveau des méthodes de décision en algèbre booléenne (BDD, SAT), et le développement d’une nouvelle formalisation des circuits combinant les automates finis synchrones avec des opérateurs booléens. La théorie des langages réactifs, qui faisait déjà autorité pour la conception d’automates de contrôle, trouve un nouveau champ d’application dans la conception et la vérification de circuits —là aussi, les enjeux économiques sont énormes, et des acteurs industriels français comme Estérel Technology sont bien placés pour relever ce défi.

4.5. Sémantique, preuves, vérification.

Dans les années 1980, les recherches en théorie des langages allaient s’étendre aux systèmes de description de schémas de programme et aux arbres de syntaxe abstraite, ainsi qu’aux systèmes de notations fonctionnelles ((-calcul). L’étude de modèles calculatoires topologiques, algébriques, ou catégoriques, initiée par Scott et Plotkin, allait mettre en évidence une notion de domaines de calcul, dans lesquels les algorithmes s’interprètent par des fonctions continues. L’extension de ces notions aux calculs distribués et parallèles est à ce jour une voie de recherche toujours très active.

Il est paradoxal de constater que des branches très abstraites des mathématiques ont trouvé leur application en des problèmes informatiques très concrets. Par exemple, l’étude de présentations équationnelles de catégories cartésiennes fermées a permis de dégager une notion de machine virtuelle pour les langages fonctionnels, la CAM (categorical abstract machine). De façon similaire, la problématique d’analyse combinatoire des groupes s’est étendue à la synthèse efficace de déductions équationnelles avec les systèmes de réécriture de termes. La démonstration assistée de théorèmes a également développé l’extension de la recherche de solutions à des équations diophantiennes ou polynomiales à des structures algébriques diverses et variées, permettant le calcul de recherche de motifs (filtrage) ou de résolution d’équations entre termes (unification). Ces recherches ont rejoint progressivement celles menées par les logiciens en théorie de la démonstration, avec l’émergence d’une combinatoire fine des structures de preuve (logique linéaire, réseaux de démonstration, géométrie de l’interaction).

Les années 1980 ont vu le développement de restrictions de la logique du premier ordre aux clauses de Horn (logique conditionnelle) comme paradigme systématique de programmation non déterministe, appelé programmation logique, et popularisé par le langage PROLOG. Progressivement, cette problématique s’est enrichie en un paradigme de programmation par contraintes, agglutinant les méthodes de programmation linéaire, de programmation en nombres entiers, et plus généralement de résolution d’équations algébriques diverses. Cette méthodologie est en train de supplanter progressivement dans certains domaines les méthodes classiques de recherche opérationnelle, et représente donc un enjeu économique important.

Le problème de fiabilité du logiciel a donné lieu à une explosion de recherches aux frontières de la théorie de la démonstration et de l’informatique théorique, comme nous l’avons expliqué ci-dessus, avec le développement de langages de spécification, de sémantiques de langages de programmation, de logiques dynamiques spécialisées et d’assistants de preuve, afin de fournir des systèmes d’aide à la mise au point de logiciels certifiés. Une autre manière d’aborder cette problématique est d’étendre la vérification des programmes, traditionnellement effectuée par une batterie de tests, en une vérification symbolique dans un espace de calcul plus abstrait —appelée « model checking ». Cette technologie a donné lieu à de nombreux développements de nature mathématique, pour prouver l’existence de points fixes dans ces domaines abstraits et donner des algorithmes efficaces pour leur recherche. Ces recherches, poursuivies notamment au laboratoire d’informatique de l’ENS et au laboratoire Verimag de l’Université de Grenoble, ont donné lieu à des vérificateurs automatiques efficaces utilisés industriellement, notamment par la société Polyspace Technology, qui a résolu par ces outils les anomalies ayant conduit à l’échec de la fusée Ariane 501.

4.6. Linguistique et Sciences cognitives.

Le traitement du langage naturel, entrepris dès les années 1950 dans des buts de traduction automatique, a longtemps buté sur les difficultés intrinsèques de l’intelligence artificielle, et notamment sur la modélisation du bon sens. Les difficultés de la compréhension du langage naturel par une machine ont progressivement dégagé des champs d’étude spécialisés où des progrès substantiels ont pû être réalisés, dès qu’une modélisation mathématique pertinente était dégagée. C’est ainsi que le domaine du traitement de la parole, utilisant les méthodes mathématiques du traitement du signal, et une modélisation statistique appropriée (modèles de Markov cachés compilés en des automates stochastiques), est en passe de fournir des interfaces homme-machine utilisant la voix, utilisables par des locuteurs sans apprentissage dans des domaines sémantiques restreints.

Le traitement informatique des phénomènes phonologiques et morphologiques a donné lieu à un renouveau des transducteurs rationnels, et à la généralisation des expressions régulières en des systèmes de notation pour des relations régulières. La compilation de tels formalismes a suscité des études algorithmiques, qui ont permis de faire passer ces méthodes au stade industriel. La recherche d’informations dans de grands corpus, tels que la Toile, et l’organisation des mémoires d’entreprise, sont des enjeux économiques majeurs utilisant ces techniques.

Les études de syntaxe formelle, et notamment des variantes des grammaires catégorielles de Lambek, ont rejoint les formalismes de théorie de la démonstration telles que la logique linéaire non commutative. Les études de sémantique formelle, initiées par Montague autour du (-calcul typé de Church, ont donné naissance à de nombreuses variantes de logiques modales (temporelles, dynamiques, épistémologiques, hybrides, DRT) unifiées autour de la notion de modèle de Kripke. Les études d’unification d’ordre supérieur permettent de modéliser de façon uniforme la recherche d’anaphores, le traitement des ellipses et de nombreux autres phénomènes linguistiques.

Le domaine de structuration de la sémantique lexicale sort progressivement de méthodes ad-hoc (réseaux sémantiques, ontologies) pour dégager des logiques de description aux propriétés algorithmiques mieux comprises. Ces différentes facettes de la modélisation linguistique permettent de progressivement intégrer les théories linguistiques descriptives dans des formalismes mathématiques adaptés au traitement informatique. Ces méthodes de type logique sont complétées par des méthodes statistiques, utilisables à grande échelle maintenant que des corpus informatisés de grande taille sont disponibles (archives de journaux, Toile).

On peut ainsi pronostiquer un développement considérable des applications du traitement de la langue naturelle dans la prochaine décennie. D’autres domaines des sciences cognitives devraient progressivement bénéficier des modèles formels dégagés par ces recherches.

4.7. Autres domaines d’interaction, synthèse.

L’analyse numérique et l’automatique (théorie du contrôle), étroitement liées aux équations aux dérivées partielles, ne sont pas du ressort de ce texte. Il en va de même pour plusieurs domaines importants d’application de l’informatique, comme la vision et le traitement des images, pour lesquels les aspects géométriques (géométrie analytique, géométrie différentielle, topologie différentielle ou algébrique) deviennent naturellement prépondérants. L’informatique joue également un rôle dans les sciences du vivant, en permettant de traiter (avec une algorithmique souvent très fine) les masses de données qui s’y présentent et d’en extraire l’information essentielle —c’est le domaine de la bioinformatique. Si l’on inclut ces applications informatiques, on peut considérer, comme l’a énoncé Don Knuth, que pratiquement toutes les mathématiques ont une pertinence à l’égard de l’informatique.

Prenons un exemple pour conclure cette section. Une personne se connecte sur la Toile et obtient la carte des prévisions météorologiques de sa région. Les couches « basses » de transmission reposent sur des codes correcteurs d’erreur (corps finis), sur la théorie du signal utilisée dans la conception des modems et de l’ADSL, ainsi que sur la compression des données binaires (réalisée par des structures mathématiques d’arbres). L’utilisateur lance, depuis son navigateur, une requête acheminée par le réseau, ce qui met en jeu une algorithmique distribuée complexe (routage et gestion de tables) qui a été optimisée selon des modèles probabilistes adaptés. La communication, lorsqu’elle est chiffrée, repose de plus sur un système fondé sur l’arithmétique et la théorie des nombres. Le navigateur est lui-même un programme complexe dont la construction a mis en jeu des langages de programmation et des modèles d’interaction bénéficiant des théories syntaxiques et logiques amplement discutées ci-dessus. La carte météorologique que l’on va charger traduit des prévisions établies selon divers modèles physiques reposant sur la théorie des équations aux dérivées partielles, lesquelles sont traitées numériquement par une algorithmique mathématique finement optimisée (discrétisation et éléments finis, maillages et décompositions de domaines). La carte quant à elle est un objet digital comprimé dans un rapport important, ce grâce à la conjonction d’analyse de Fourier et, à nouveau, de structures de données arborescentes. Le moteur de recherche met en jeu toute une panoplie d’algorithmes de recherche analysés et optimisés selon les principes d’analyse décrits plus haut. Enfin, les pages chargées sont des objets structurés exprimés dans un langage de description (HTML) qui s’appuie lui aussi sur les méthodes syntaxiques et formelles. Sciences mathématiques et informatiques sont cruciales et partout présentes derrière cet acte désormais banal de la vie quotidienne.


5. Conclusions

L’informatique dans son ensemble représente une construction artificielle qui n’a guère d’équivalent dans l’histoire. Sa simple adaptation à l’évolution constante des besoins de la société nécessite une activité technique de grande ampleur. La tentation peut alors exister pour certains dirigeants de ne percevoir de l’informatique que les besoins de développement technologique de la période en cours. À cela suffiraient des hordes de techniciens et d’ingénieurs formés au fonctionnement de ce qui existe ou est en gestation pour un futur proche.

Par le biais de ses relations avec les mathématiques, nous avons illustré le fait que l’informatique est une science très largement inscrite dans la tradition des autres sciences. Comme dans d’autres domaines, les progrès reposent sur nombre d’idées astucieuses et novatrices, mais au moins autant sur les progrès conceptuels apportés par une réflexion scientifique approfondie, par une abstraction de nature mathématique, et par une relative distanciation à l’égard de la technologie du moment. C’est de la sorte qu’ont pu éclore la plupart des grandes innovations qui ont façonné le paysage informatique. En relation avec les débats récurrents portant sur recherche fondamentale et recherche appliquée, on se doit de noter le fait que plusieurs branches des mathématiques pures longtemps jugées « inutiles » mais au moins reconnues comme ayant une certaine « profondeur », ont trouvé des applications inattendues en informatique. Ainsi, une source historique de l’analyse combinatoire est constituée par un besoin très théorique de compréhension de calculs formels sous-tendant l’analyse mathématique ; la théorie des probabilités plonge ses racines dans les jeux de hasard alors que la combinatoire compte parmi ses origines plusieurs jeux ou récréations mathématiques ; la théorie des catégories et la logique mathématique ont semblé à leurs origines se situer aux confins de la philosophie des sciences, tandis que la théorie des nombres n’avait, en 1940, aux yeux du mathématicien britannique G. H. Hardy, que bien peu d’utilité pour le monde réel. Or c’est in fine grâce à ces acquis que le grand public peut désormais disposer de l’Internet, de la Toile, des DVD, de la téléphonie mobile, etc.

Ces considérations plaident tout d’abord pour l’importance d’un soutien vigoureux à une recherche fondamentale en informatique, comme gage de l’avenir. Elles suggèrent aussi que la meilleure manière de former de futures générations d’informaticiens performants est de les doter d’une formation adaptée aux objets, concepts, et méthodes de l’informatique, mais surtout intégrée à une formation scientifique classique et généraliste de qualité, et comportant notamment des bases mathématiques solides.
 Soulignons que l’objet de cette discussion est la discipline informatique « cœur » (core computer science) encore appelée informatique fondamentale ou informatique théorique. Les très nombreux jeux à trois (modélisation) impliquant mathématique, une autre discipline scientifique, et l’utilisation de l’ordinateur ne seront qu’évoqués indirectement ici.
 Dans un autre ordre d’idées, en 1949, on calcule 103 décimales du nombre ( avec un ordinateur effectuant 103 opérations par seconde ; en 2002, le record du nombre de décimales connues était de l’ordre de 1012 pour un calculateur parallèle effectuant 1012 opérations par secondes. Les algorithmes d’origine ayant une complexité quadratique, la seule progression des vitesses de calcul des processeurs n’aurait guère permis d’atteindre que quelques dizaines de millions de décimales, et non pas les mille milliards obtenus à ce jour. Les meilleurs procédés de calcul du nombre ( sont désormais de complexité légèrement superlinéaire, soit à peine plus que le coût d’une addition (!). Des gains algorithmiques infiniment plus grands ont été atteints pour le problème de la factorisation d’entier, domaine où les recherches ont été motivées par le système cryptographique RSA.
 Cette réduction exprime qu’une sous-formule (( x. e[x])(A) peut se réduire en e[A].
 Au XIXe siècle, Delaunay mit vingt ans de travail à calculer les perturbations de l’orbite de la lune induites par la masse solaire. Ces calculs nécessitent de nos jours quelques dizaines de secondes, ce grâce aux progrès concomitants du matériel et de l’algorithmique du calcul formel.
 Ce message est par exemple bien compris par l’Inde qui est à la fois le pays des prestigieux IITs (Indian Institutes of Technology) et l’un des principaux exportateurs mondiaux de logiciels.

 :