Section 06 Sciences de l'information : fondements de l'informatique, calculs, algorithmes, représentations, exploitations

I. Calcul : algorithmes, combinatoire, protection de l'information

Un volet important du traitement de l'information s'articule autour de la notion de calcul avec tout ce qu'elle comporte : algorithmes, arithmétique des ordinateurs, calcul formel, protection de l'information, ainsi que l'analyse des structures associées qui sont le propre de la combinatoire, de la théorie des graphes ou encore des systèmes dynamiques. Ce domaine de recherche constitue une interface très active entre mathématiques discrètes et informatique.

A. Algorithmes : méthodes génériques, analyse de complexité

La recherche en algorithmique s'organise principalement autour du développement de techniques permettant de rapprocher bornes inférieures (résultats d'impossibilité) et supérieures (algorithmes) tant sur la complexité de problèmes informatiques que sur la qualité des solutions produites. L'explosion des données massives a suscité un intérêt croissant pour les modèles de calcul qui prennent en compte un accès contraint aux données, comme le calcul distribué, en ligne, de streaming, ou encore les algorithmes sous-linéaires. L'exportation de la notion d'algorithme à d'autres sciences s'est traduite par l'étude algorithmique des systèmes dits naturels engendrés par les réseaux sociaux ou encore en biologie. La recherche en France dans ce domaine est d'un très bon niveau international.

Plusieurs rapprochements thématiques ont eu lieu, en particulier avec les mathématiques. Un exemple typique est celui de la recherche opérationnelle, ou plus précisément de la programmation mathématique. Un des résultats les plus marquants concerne les limites de la programmation linéaire comme outil pour concevoir des algorithmes d'approximation, par rapport à ceux plus complexes de la programmation semi-définie. Une séparation vient d'être établie sur un problème pratique important, le voyageur de commerce, résolvant ainsi une question formulée il y a 20 ans par Yannakakis. La beauté de ce résultat réside dans le lien nouveau qu'il établit entre programmes linéaires et complexité de la communication quantique. Toute une série de résultats similaires tant théoriques que pratiques ont été établis à sa suite. Les chercheurs européens, dont quelques uns en France, ont joué un rôle moteur dans l'établissement de ces ponts.

Parallèlement à l'analyse de la complexité des problèmes, l'analyse (en moyenne) des algorithmes eux-mêmes a remporté quelques succès en permettant de comprendre et prédire le comportement d'algorithmes plus complexes exécutés sur des instances plus réalistes. Ces avancées ont été réalisées grâce à l'apport de méthodes génériques issues de la combinatoire analytique, fructueux mariage de la combinatoire formelle et de l'analyse complexe, domaine qui s'est développé sous l'impulsion de Philippe Flajolet et Robert Sedgewick.

B. Théorie des graphes, algorithmique des graphes

Les activités de recherche autour des graphes portent à la fois sur des aspects structurels et algorithmiques. La communauté française nombreuse dans ce domaine est internationalement reconnue.

Parmi les principales avancées, on peut citer le développement de toute une théorie pour traiter les graphes en les voyant comme des objets limites. La théorie est bien comprise et unifiée pour les graphes denses et a de nombreuses ramifications vers des sujets variés comme les algorithmes sous-linéaires et l'échantillonnage. De nouveaux progrès ont permis de résoudre d'importantes conjectures relatives à certaines partitions de graphes. Fort de la compréhension des graphes denses, un recentrage s'est effectué vers l'étude des graphes creux ou épars, véritable enjeu pour la modélisation des grands graphes issus des applications récentes comme les réseaux au sens large. Plusieurs résultats obtenus en France ont permis de développer un cadre unifié pour traiter les graphes creux.

Un résultat notable à l'interface des mathématiques discrètes et de l'algorithmique concerne la version constructive du lemme local de Lovasz. Ce lemme est une variante de la méthode probabiliste qui permet de construire des objets à partir d'évènements dont chacun ne dépend que d'un petit nombre d'autres évènements. Les applications sont nombreuses et vont de la théorie des graphes extrémaux aux problèmes de routage et de coloration. La construction algorithmique proposée par Moser a ouvert de nouveaux champs d'applications qui ont été investis en partie par la communauté française.

Dans le domaine de la complexité paramétrée, les progrès récents les plus significatifs sont des résultats montrant l'existence de noyaux polynomiaux pour de larges familles de problèmes paramétrés ainsi que le développement de techniques de bornes inférieures sur la taille des noyaux. Dans ce contexte, l'optimisation des complexités existantes, les liens entre les méthodes paramétrées et les méthodes d'approximations sont des enjeux importants.

C. Combinatoire, systèmes dynamiques discrets, algorithmique du texte

À l'interface entre informatique théorique, mathématiques discrètes, théorie des probabilités et physique théorique, une large communauté s'intéresse aux structures discrètes aléatoires ou algébriques issues de ces disciplines. Cette interaction est particulièrement riche en France et constitue une des forces de la combinatoire. Des contributions notables ont ainsi été obtenues à l'interface avec la physique (physique statistique et renormalisation) et dans des interactions renouvelées avec des domaines des mathématiques centrés sur le calcul, comme le calcul moulien ou le calcul opéradique. Parmi les nombreux résultats marquants récemment obtenus citons l'élaboration d'interprétations combinatoires d'objets extrêmement difficiles à calculer, notamment autour des polynômes de MacDonald, la résolution d'un problème ouvert depuis plus de 20 ans sur les systèmes de particules en interaction (modèles ASEP et TASEP) ou encore la preuve de la conjecture de Razumov-Stroganov intimement liée aux travaux sur les matrices à signes alternants.

L'étude des systèmes dynamiques discrets s'est principalement développée récemment autour des domaines de la dynamique symbolique, de la théorie des pavages (et de leurs espaces), et des automates cellulaires. La notion de substitution agissant sur des mots ou sur des tuiles est un concept crucial dans ce contexte. Les substitutions permettent en effet d'exprimer la dynamique de la renormalisation, de l'induction (l'étude des échanges d'intervalles en est une bonne illustration), mais aussi des notions issues de la calculabilité : elles sont utilisées pour coder et construire des zones de calcul. Dans le cadre de la dynamique multidimensionnelle, la communauté française a ainsi contribué à montrer que les outils de complexité et de calculabilité sont essentiels pour la description et la compréhension des systèmes dynamiques symboliques, en obtenant en particulier la caractérisation des sous-shifts effectifs de dimension d comme projection de sous-shifts de type fini de dimension (d+1).

L'algorithmique du texte a connu un essor important en liaison en particulier avec les travaux sur des problèmes issus du traitement des séquences génomiques (représentation compressée des graphes de De Bruijn grâce aux filtres de Bloom, table des suffixes dynamique et transformée de Burrows-Wheeler, toutes trois utilisées au sein des algorithmes d'assemblage pour accélérer et limiter la consommation mémoire du traitement des données produites par séquençage haut-débit). La France est ainsi très reconnue dans les domaines fondamentaux, mais elle souffre d'un manque de valorisation, la plupart des outils utilisés dans les laboratoires de biologie n'étant pas des logiciels français. Il existe cependant quelques exceptions notables, par exemple, pour la recherche des duplications en tandem (logiciels PhyML et STAR) et le repliement comparatif des ARN (CARNAC), où des outils constituant l'état de l'art du domaine sont développés en France.

D. Calcul arithmétique et formel, codage et cryptographie

L'arithmétique des ordinateurs et le calcul formel s'intéressent à la manipulation des objets fondamentaux de l'arithmétique et de l'algèbre (nombres, polynômes, séries, solutions d'équations différentielles...). Lorsque l'on conçoit les briques de base du calcul, sur lesquelles repose tout l'édifice, l'efficacité et la sécurité sont alors primordiales. La cryptographie, qui s'est longtemps appuyée sur des objets algébriques relativement simples (calcul modulaire), fait maintenant davantage appel à des objets nettement plus complexes relevant du calcul formel, comme les courbes elliptiques et les réseaux euclidiens.

En cryptographie, les thèmes et résultats qui ont émergé ces dernières années concernent la sécurité pour le cloud computing avec notamment les chiffrements fonctionnels (qui permettent plusieurs niveaux de déchiffrement en fonction de la clé secrète détenue) et les chiffrements complètement homomorphes (qui permettent de déléguer sur un serveur un calcul sur des données qui restent chiffrées tout au long du calcul), ainsi que les attaques physiques par canaux cachés et la résistance aux fuites partielles d'information. Enfin, les thématiques autour de la protection de la vie privée et de l'anonymat ont pris une importance considérable.

Sur des aspects plus algorithmiques, les avancées majeures concernent la sécurité de systèmes de chiffrement qui repose maintenant sur des complexités en pire cas, et non plus en moyenne (en utilisant des problèmes de réseaux euclidiens), en particulier la découverte d'un algorithme efficace pour le calcul du logarithme discret dans les corps finis de petite caractéristique.

En arithmétique des ordinateurs, la reproductibilité numérique prend de l'importance pour les applications de calcul intensif. La conception automatique de bibliothèques de fonctions élémentaires ou spéciales, afin de s'adapter très vite à un nouveau contexte (format cible, processeur utilisé, exigences en matière de vitesse, précision, etc.) est au cœur des travaux actuels, pour lesquels la communauté française est bien positionnée. Les thèmes traités vont de l'arithmétique matérielle et logicielle pour la cryptographie à la génération de bibliothèques et d'opérateurs d'arithmétiques flottantes ou fixes, en passant par la validation et la preuve automatique. On peut néanmoins regretter la quasi-absence d'une industrie française des semi-conducteurs à l'exception notable de STMicroelectronics.