Sciences et Technologies de l'Information
Sommaire : Trois questions à Philippe Flajolet | L'actualité de la semaine | Théories et concepts | Le livre de la semaine |
ABONNEMENT/DESABONNEMENT| PAGE D'ACCUEIL DE L'ASTI | NUMEROS PRECEDENTS.
Asti-Hebdo
: Vous avez écrit "Mathématique et informatique se rejoignent", et vous
en débattrez à la journée Asti. Mais, au fond, où situez-vous l'algorithmique,
votre spécialité ?
Philippe Flajolet : L'algorithmique se situe à la frontière. On pourrait la qualifier d' "informatique mathématique", comme on parle de"physique mathématique".
Au sein de l'algorithmique, on peut distinguer la conception (algorithmes nouveaux, perfectionnement d'algorithmes anciens) de l'analyse, c'est-à-dire, pour l'essentiel, l'analyse quantitative des performances. C'est elle qui permet de comprendre quelles sont les bonnes ou les mauvaises utilisations de tel algorithme, quelles sont les sources d'inefficacité des traitements informatiques, et sur quoi fonder de bonnes solutions, voire de nouvelles fonctions. En particulier, en ce qui concerne mon domaine de recherche principal, l'analyse d'algorithmes, on y trouve plus facilement des chercheurs en Europe qu'aux Etats-Unis. En effet, la séparation entre les disciplines y est plus précoce que chez nous. Cela facilite là-bas l'apparition de programmeurs très précoces. Par contre, en Europe, la séparation ne se fait qu'assez tard, dans les universités et les grandes Ecoles, ce qui enrichit notre potentiel de jeunes de culture interdisciplinaire.
L'algorithmique a un caractère plus immédiatement applicable que la logique mathématique, avec ses perspectives absolument généralistes (par exemple en théorie de la démonstration), qui la font souvent se heurter à des problèmes d'indécidabilité. En revanche, les chercheurs en algorithmique se spécialisent en général dans une catégorie donnée d'applications, avec des concepts et des objets plus délimités, voire dans des sous-domaines précis, par exemple la communication sur réseau, les bases de données, le traitement de données en langue naturelle. Pour ce qui me concerne, l'un de mes thèmes de prédilection actuel est le calcul formel. outil qui peut servir aussi bien aux physiciens qu'aux mathématiciens... et aux informaticiens.
J'utilise largement des méthodes de nature mathématique, mais ma problématique n'existerait pas du tout, s'il n'y avait pas l'informatique.
Hebdo : Y a-t-il toujours des progrès à faire, dans ce domaine brillamment défriché par Donald Knuth dans les années 60 ?
P.F. : Knuth, n'a encore aujourd'hui que 63 ans ! Il a fait un travail énorme (notamment sa célèbre série d'ouvrages "The Art of Computer Programming") et beaucoup croient qu'il a pris sa retraite. Mais il continue d'être actif, comme un certain nombre de seniors de la spécialité.
En informatique, on a tendance à ne voir que la loi de Moore, avec la montée des processeurs en puissance et des mémoires en capacité. Or ce n'est qu'un aspect de l'histoire. On pourrait même dire que la loi de Moore oblige à faire des progrès en algorithmique, car elle encourage à traiter des volumes de données qui croissent encore plus vite.
Les progrès algorithmiques ont permis, pour nombre de problèmes, de se ramener à une complexité polynomiale alors qu'ils étaient considérés longtemps comme de complexité exponentielle. On a progressé aussi en recherche rapide d'informations complexes, en communication sur les réseaux (où l'on est sur plusieurs plans aujourd'hui proche de l'optimum informationnel).
Notre discipline change aussi dans ses méthodes. Dans les années 70-80, on tendait à construire des gratte-ciel très compliqués, avec de grosses équipes. Aujourd'hui, la complexité et la versatilité des problèmes posés par l'informatique appellent plutôt des solutions efficaces, claires, validées, garanties, donc à élaborer des fonctions de base bien balisées.
On observe aussi un certain retour de la géométrie. Ce mouvement pourrait se comparer à certains travaux récents de logiciens (notamment de Jean-Yves Girard, qui parle de "locus solus"). Nous nous apercevons, en effet, que pour comprendre le comportement quantitatif des algorithmes, nous avons tout intérêt à en regarder des géométries associées. En quelque sorte, on revient ainsi de l'univers du discret à l'univers du continu (au niveau de l'analyse, pas de la conception).
Hebdo : Quelles sont à votre avis, les applications les plus importantes de vos travaux ?
P.F. : On cherche des algorithmes pour aller plus vite (en bases de données, sur Internet) ou pour assurer des fonctions inaccessibles jusqu'à présent, et que les progrès du calcul formel permettent maintenant de traiter effectivement. L'algorithmique est tout spécialement d'actualité en matière de cryptographie (avec des progrès rapides) ou en compression de données pour le stockage et la transmission de la vidéo par exemple.
Pour ce qui concerne le calcul formel, celui-ci a été créé historiquement par les physiciens, s'appuyant sur Fortran et sur Lisp, au cours des années 60. On leur doit des outils comme Mathematica et Reduce. A ses débuts, le calcul formel se sentait proche de l'intelligence artificielle. Il s'en est assez rapidement détaché, car le calcul formel ne relève guère des systèmes experts mais d'une bonne algorithmisation des connaissances mathématiques.
Aujourd'hui les physicien sont assez coupés de la communauté de recherche en calcul formel, et poursuivent leurs travaux au sein de laboraroies spécialisés (le CEA ou le Cern, notamment). En pratique, le premier marché est celui de l'enseignement, avec ses logiciels voire ses calculettes (TI 92) qui peuvent traiter des formules aussi bien que des nombres.
Parmi les applications intéressantes, celles des automaticiens se distinguent, avec un processus de développement en deux phases. Partant d'un problème de mécanique, ils en font la modélisation exacte en calcul formel. A ce niveau, ils travaillent par exemple sur des matrices jacobiennes (inversions, notamment), sur les dérivations... Ensuite, ils peuven produire automatiquement du code Fortran pour utiliser numériquement les formules, pratiquer les intégrations et les simulations.
Mais, parmi les plus stimulantes applications, il faut citer les "mathématiques expérimentales" (une spécialité notamment de l'équipe canadienne de Jonathan Borwein, à Vancouver). Il s'agit de soutenir et d'affiner l'intuition, de saisir ce qui est vrai et ce qui ne l'est pas, pour en chercher ensuite la démonstration. Le calcul numérique n'apporte ici qu'une aide limitée, car il bute rapidement sur les limites de précision des opérations sur très grands nombres. Les outils formels permettent au contraire l'expérimentation en très grande précision tout en ayant des résultats garantis.
Ainsi, vous le voyez : mathématique et informatique se rejoignent. En tous cas à l'Inria !
Pour Le Monde : "Ce texte a pour objectif d'instaurer la confiance entre les utilisateurs d'Internet et ses différents acteurs".
Philippe Crouzillacq (01 Net) considère que : "La copie est à revoir... ce texte s'attire déjà les foudres des acteurs et utilisateurs de l'Internet".
Il s'agit en quelque sorte de "composants services", c'est à dire de parties d'applications mises à disposition, sur un serveur, d'autres applications opérant sur d'autres serveurs. Par exemple un module de calcul des points de retraite qui permettra à un site de gestion du personnel (ou à un éditeur de logiciels de ce type), de proposer cette fonctionnalité sans avoir ni à la développer ni à l'intégrer à ses produits.
"Opérables à partir du Net, plus souples que les chaînes de progiciels standards qui exigent un important travail de paramétrage, moins rigides que les solutions ASP (Application service provider), elles préfigurent la distribution de services informatiques à la demande et le "tuning" fin des besoins à partir d'un marché de composants logiciels obéissant réellement au lois de l'offre et de la demande", commente Jean-Marc Zuliani.
Arno Scharl dans son "Evolutionary Web Development" (Springer 2000) ne fournit pas moins de 42 pages de bibliographie. Le livre se centre sur une présentation de la méthodologie eW3DT, une "boxologie" adaptée à ce type d'applications. Mais, balayant largement autour de ce coeur technique, il offre en fait une synthèse dense (parfois trop dense, même, pour une lecture aisée) de la littérature du domaine. C'est l'ouvrage type à recommander à un thésard !
L'IA retrouve ici un domaine très actif d'application, comme en témoigne le tome 1991 des Lecture Notes in Artificial Intelligence, intitulé "Agent Mediated Electronic Commerce" (ici encore, chez Springer). Le volume se répartit en quatre sections: négociation, marchés, sécurité. On y note avec plaisir la présence d'un auteur français, Jean-Luc Koning, de l'Esisar-INPG de Valence (Drôme).