Philippe Flajolet & Gérard Huet








télécharger 91.05 Kb.
titrePhilippe Flajolet & Gérard Huet
page1/3
date de publication23.12.2016
taille91.05 Kb.
typeDocumentos
l.21-bal.com > loi > Documentos
  1   2   3
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’informatique1. 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.2 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.
  1   2   3

similaire:

Philippe Flajolet & Gérard Huet iconJean-Luc charache, Gérard gouraud, Bruno chapelier, Jean-Claude larrivee,...

Philippe Flajolet & Gérard Huet iconMesdames larrode sandra,,descamps frédérique, pessonnier nathalie...

Philippe Flajolet & Gérard Huet iconExtraits du journal de François Huet, instituteur
«Promenades éducatives», pendant lesquelles IL nous suivait, rameutant les traînards à la manière d'un chien de berger

Philippe Flajolet & Gérard Huet iconAudition M. Sylvestre Huet
«presse d’information», qui peut paraître redondant, a été choisi à la création de l’association pour montrer que nous ne regroupons...

Philippe Flajolet & Gérard Huet iconQuestionnaire Gérard piard

Philippe Flajolet & Gérard Huet iconBegnis michèle + ferrigno gérard

Philippe Flajolet & Gérard Huet iconChristopher Gérard : Qui êtes-vous ?

Philippe Flajolet & Gérard Huet iconCompte rendu de l'entrevue avec Gérard Roussillon

Philippe Flajolet & Gérard Huet iconMémoires d'outre-tombe, III, 1848-1850. Texte d annexe : Gérard Genette,...

Philippe Flajolet & Gérard Huet iconSous la direction de Philippe Nanopoulos








Tous droits réservés. Copyright © 2016
contacts
l.21-bal.com