CALIN: Combinatoire, algorithmique et interactions

Responsable: Frédérique Bassino


L'équipe CALIN réunit des chercheurs ayant des compétences dans les divers domaines de la combinatoire (analytique, algébrique et bijective) avec un intérêt pour la complexité des algorithmes dont ils cherchent à déterminer le comportement en moyenne ou en distribution, pour l'analyse fine de structures de données, ainsi que pour la physique dont ils étudient certains problèmes ou utilisent des méthodes. (rapport d'activité)

L'équipe s'organise autour de deux axes : l'un tourné vers la physique combinatoire, l'autre abordant l'analyse d'algorithmes et de structures combinatoires.

En plus de ses séminaires hebdomadaires, l'équipe CALIN organise tous les mardi un thé combinatoire.

 

Axe 1 : analyse d'algorithms et de structures combinatoires

Le but de cet axe est l'analyse théorique de structures combinatoires
de grande taille, qui apparaissent en informatique théorique. Elles
vont des arbres et graphes, aux permutations et partitions, en passant
par les mots, automates et autres aspects de théorie des langages.

On s'intéresse plus particulièrement à celles de ces structures qui
sont liées à des problèmes de la vie réelle ou ayant une forte proximité avec les problèmes originaux que l'on cherche à modéliser (applications en bio-informatique, en algorithmique, en physique statistique, etc.).

Nos méthodes sont bijectives, probabilistes ou issues de la combinatoire analytique.

Ce domaine, dont le développement doit beaucoup à Ph.Flajolet, consiste à transcrire des problèmes
combinatoires en termes de séries génératrices formelles, puis, en traitant les séries génératrices comme des fonctions de variable complexe, à utiliser des méthodes analytiques pour caractériser
précisément des comportements asymptotiques.


Nos recherches s'inscrivent dans le cadre de projets ANR
(Magnum : 2010-2014), QuasiCool : 2013-2017) de projets
internationaux (Argentine, Autriche, Brésil, Pologne, Taiwan, Tunisie,
Uruguay), et  sont menées en relation avec
le Gt Aléa du GDR Informatique Mathématique.

Axe 2 Physique Combinatoire


Les liens entre physique quantique et combinatoire sont très bien
illustrés par les travaux pionniers de Connes et Kreimer, qui ont
montré comment décrire la renormalisation des diagrammes de Feynman en
théorie perturbative des champs par une algèbre de Hopf dont le
coproduit est défini à l'aide de manipulations combinatoires d'arbres
ou de graphes.


Notre objectif est la construction, ainsi que l'étude de structures
combinatoires et/ou algébriques qui codent des symétries fondamentales
de certains modèles physiques.

Notre équipe a contribué à enrichir cette jeune
tradition de physique combinatoire en construisant des structures
algébriques dont les générateurs sont indexés par différentes classes de
graphes, et qui «encapsulent» la combinatoire sous-jacente à des
problèmes particuliers de physique, ouvrant la voie au développement
d'outils de calcul formel adaptés.


Nos recherches s'inscrivent dans le cadre du projet ANR PhysComb et d'importantes collaborations avec la Pologne, et en relation avec l'activité
du GDR Renormalisation.

Valid HTML 4.01! Valid CSS!
Accès rédacteur