lipn

Laboratoire d'Informatique de Paris Nord

UMR 7030, Université Paris 13, 99 avenue Jean-Baptiste Clément, 93430 Villetaneuse

up13 cnrs

Axe 1 : analyse d'algorithmes 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.

pres

w3c-xhtml