Aller au contenu

ALGORITHMIQUE ET COMBINATOIRE

Normastic

La culture de l’axe AlgoComb

Les membres de l’axe AlgoComb partagent une culture commune, celle de l’Informatique Mathématique, telle qu’elle est définie et pratiquée sur le terrain national par le GDR IM « Informatique Mathématique ». Cet axe rassemble presque exactement les scientifiques de Norm@STIC qui travaillent en IM. Il faut d’ailleurs noter que des membres de l’axe AlgoComb de Norm@STIC exercent ou ont exercé des responsabilités importantes à l’intérieur de ce GDR IM. Cette culture est fondée sur des objets et des concepts dans des domaines assez variés de l’IM avec des approches complémentaires: combinatoires (combinatoire des mots, combinatoire algébrique, combinatoire analytique, combinatoire dynamique), théorie de l’information et algorithmique du texte, arithmétique, calcul formel, codage et cryptographie, complexité et logique (en émergence), etc. Avec l’ensemble de ses membres, l’axe AlgoComb participe à de nombreux groupes de travail du GDR IM : Alea, Comatege (combinatoire des mots, algorithmique du texte et du génome), SDA2 (systèmes dynamiques, automates et algorithmes), CombAlg (combinatoire algébrique), Arith, calcul formel, C2 (codage et cryptographie), CMF (complexité et modèles finis), CoA (complexité et algorithmes).

Présentation des compétences associées au sein de l’axe

Les compétences scientifiques que l’on retrouve au sein de l’axe sont les suivantes.

Algorithmes et complexité

Ces compétences se structurent autour de deux concepts génériques : l’algorithme et la complexité abordés des points de vue complémentaires des modèles de calcul et des structures aléatoires. Les compétences sur les modèles de calcul concernent l’étude de la notion de complexité dans le pire des cas via les classes de complexité. Ces compétences concernent l’étude des structures aléatoires dans un cadre probabiliste et la protection de l’Information, notamment en codage et cryptographie, avec une activité algorithmique amont en théorie de l’information et arithmétique, où sont élaboré des algorithmes et des analyses. Il existe aussi une recherche transversale en algorithmique dite « non exacte » qui utilise une approche probabiliste, souvent complétée par un point de vue d’approximation.

Aspects fondamentaux du calcul

Les compétences autour des aspects fondamentaux des algorithmes, se concentrent sur les structures qui modélisent l’information (mots, monoïdes libres) et sur les aspects fondamentaux du calcul (automates, séries génératrices), notamment dans leurs aspects algébriques (systèmes polynomiaux, par exemple), où elles permettent l’analyse de leur complexité, en liaison avec leur utilisation en cryptologie.

L’algorithmique du texte 

Des compétences sont aussi avérées autour des méthodes et des structures pour rechercher, indexer et extraire des informations pertinentes dans des données biologiques (génomes et expression des génomes). Les travaux concernés visent à améliorer la compacité, l’efficacité et la dynamicité des structures de données sous-jacentes à l’algorithmique du texte, et tout particulièrement, la principale, l’arbre des suffixes, et ses variantes, les vecteurs de suffixes et les tableaux de suffixes.

Composition

L’axe est composé d’une trentaine de membres permanents, une dizaine de doctorants et ainsi que de membres non-permanents (Professeurs émérites, post-doctorants, ATER, associés etc.) répartis sur les 3 sites (Caen-Le Havre-Rouen). La plupart des membres appartiennent à l’une des trois équipes suivantes: AmacC (GREYC), Combinatoire et Algorithme (LITIS) et TIBS (LITIS).

Nous décrivons maintenant plus en détail les synergies déjà établies, tandis que les synergies potentielles seront décrites dans la section suivante.

Synergies existantes au sein de l’axe

Combinatoire des mots, algorithmique du texte et théorie de l’information

Beaucoup de questions, qui se posent dans la combinatoire des mots ou sur les automates, peuvent se généraliser quand les symboles ne sont plus équiprobables ou indépendants. Les propriétés probabilistes de la source qui produit les mots jouent alors un rôle important dans l’analyse de ces principaux phénomènes. Il y a deux volets complémentaires en algorithmique du texte : une activité créatrice sur les structures de données et une expertise dans l’analyse des propriétés probabilistes de ces structures.

Arithmétique, calcul formel, cryptographie et codage

Nous étudions les algorithmes travaillant sur des structures mathématiques, de nature algébrique (polynômes) ou arithmétique (nombres entiers, ou réseaux euclidiens), avec une expertise sur l’analyse probabiliste de ces algorithmes. Nous travaillons également dans le domaine du codage et de la cryptographie, notamment dans des activités de cryptanalyse, en utilisant deux approches complémentaires: l’une utilise davantage des outils arithmétiques (par exemple les réseaux euclidiens), et l’autre davantage des outils de calcul formel (les systèmes polynomiaux). Nous étudions aussi la complexité des algorithmes utilisés dans ces cryptanalyses. Ces synergies se retrouvent également dans l’axe applicatif transverse « Sécurité ».

Combinatoires : combinatoire analytique et combinatoire algébrique

Les séries génératrices interviennent dans deux approches complémentaires pour étendre les modèles classiques sous-jacents à la définition des algorithmes et à leur analyse:

  • Le premier est centré sur l’analyse probabiliste des structures aléatoires et des algorithmes. Dans son volet méthodologie, nous poursuivons le développement du cadre réaliste pour la modélisation des algorithmes, où ceux-ci sont vus comme des systèmes dynamiques. La série génératrice associée à l’algorithme est alors étendue en un opérateur générateur (associé à l’opérateur de transfert du système dynamique).
  • La généralisation des séries génératrices à d’autres structures notamment non-commutatives. En particulier, nous étudions les fonctions symétriques, les algèbres de Hopf et les opérades. La notion d’opérade, issue de la topologie algébrique, permet de modéliser les propriétés algébriques des opérateurs n-aires. Elle s’applique naturellement en Combinatoire Algébrique et en Physique Combinatoire. Nous développons aussi une approche nouvelle en modélisant certains opérateurs intervenant en théorie des langages grâces à ces structures. Plus généralement, l’informatique mathématique peut devenir un terrain de jeu idéal pour les opérades.

Autres compétences

D’autres compétences existent ou peuvent être développées au sein de l’axe et en Normandie:

  • Analyse et complexité des algorithmes: En particulier, nous voudrions développer des outils d’analyses pour les algorithmes sur les mots et les automates conçus au sein de l’axe. Les travaux menés sur la complexité de l’énumération sur les automates ou en logique sont un autre point de convergence possible, en lien aussi avec les questions de génération aléatoire. Par ailleurs, les approches d’algorithmique dite « non exacte » sont naturelles dès lors qu’une notion de distance peut être définie sur les objets étudiés. C’est notamment le cas des mots et des automates, deux types d’objets pour lesquels il existe une grande richesse de distances naturelles.
  • Physique combinatoire: En particulier nous intervenons dans deux domaines; l’information quantique, où nous étudions l’intrication, et la théorie de l’effet de Hall fractionnaire quantique. Dans les deux cas, nous développons des outils issus de la théorie des représentations qui peuvent être utiles dans d’autres domaines étudiés dans l’axe, par exemple la cryptanalyse, ou l’analyse d’algorithmes.
  • Synergies possibles entre Norm@Stic et la Fédération de mathématiques: Les systèmes dynamiques sont là encore un objet d’intérêt et d’étude commun, avec des points de vue complémentaires : ils sont étudiés avec un point de vue analytique ou probabiliste ou avec un point de vue plus discret, en liaison avec la théorie des codes ou avec les automates cellulaires. Ce thème « Systèmes Dynamiques » intéresse clairement aussi les mathématiciens de la Fédération Normandie-Mathématiques, et peut constituer un point d’accroche à l’axe « Systèmes Complexes » de Norm@Stic. et une première base au pentagone Math/Info/Rouen/Caen/Le Havre.

L’axe AlgoComb et l’enseignement

En ce qui concerne l’enseignement, l’axe s’appuie sur trois Masters 2 :

  • deux Masters rouennais, le Master ITA (Informatique Théorique et applications), d’orientation plus recherche, et le Master SSI (Sécurité des Systèmes Informatiques), d’orientation plus professionnelle,
  • le Master caennais E-Secure, d’orientation plus mixte. Il s’agit de proposer des cours d’ouverture, et des co-directions de stages sur les thématiques de l’axe AlgoComb.

INFORMATIONS

Brigitte Vallée

Responsable

Nicolas Bedon

Responsable