Journées nationales 2009

Les journées 2009 ont lieu à l’unive­rsité Paris 6 sur le campus de Jussieu les 22 et 23 janvier 2009. L’accueil pour de ces journées a lieu à partir de 10h30 au Bâtiment Esclangon (Amphi Durand).

Le programme définitif est maintenant disponible

Jeudi 22 janvier

• 10:30 – 11:30 : Accueil et café
• 11:30 – 12:15 : Florent Hivert (GT CombAlg) :  « Arbres, tris, et fonction tangente », Résumé
• 12:15 – 13:00 : Olivier Bournez  (GT CMF) :  « Calculs continus et Calculs distribués », Résumé
• 13:15 – 14:30 : Déjeuner
• 14:30 – 15:15 : Stéphane Vialette (GT COMATEGE et Graphes) :  « Recherche de motifs connexes dans les graphes colorés », Résumé
• 15:15 – 16:00 : Dominique Michelucci (GT ModGeom et ARITH) :  « Certifier les résultats de calculs approchés », Résumé
• 16:00 – 16:30 : Pause café
• 16:30 – 19:00 : Discussion sur le GDR et la place de l’informatique au CNRS
• 19:00 – 21:30 : Buffet-cocktail (cave Esclangon)

Accès Bâtiment Esclangon :
1) par l’entrée principale de Jussieu, place Jussieu, puis en longeant les barres de la tour 46 vers la tour 66
2) directement par la rue Jussieu, au coin avec la rue Cuvier

Vendredi 23 janvier

• 09:00 – 10:00 : Conférence invitée,   Marc Noy : « Random planar graphs », Résumé
• 10:15 – 11:00 : Cyril Nicaud (GT SDA2 et ALEA) :  « Analyse d’algorithmes pour les langages rationnels », Résumé
• 11:00 – 11:30 : Pause café
• 11:30 – 12:15 : Xavier Goaoc (GT GeomAlgo), « Nombres de Helly et permutations géométriques », Résumé
• 12:15 – 13:00 : Alexandre Miquel (GT LAC et GEOCAL), »Construction de programmes à partir de preuves non-constructives »,  Résumé
• 13:15 – 14:30 : Déjeuner
• 14:30 – 15:15 : Guillaume Hanrot (GT ARITH et C2), « Problèmes de logarithme discret : un survol », Résumé
• 15:15 – 16:00 : Sophie Laplante (GT Quantique et CMF), « La complexité de la communication des distributions quantiques et au-delà », ­ Résumé

­Résumés Journées du GDR IM 2009

­

Marc Noy, « Random planar graphs » ­
  How does it look a large random planar graph? After several years of research we have by now a fairly good description. We know very precisely how many edges has a random planar graph, how many components, how many vertices of a given degree, how many copies of a given subgraph.
We also know about more complex parameters, like the maximum degree, the size of the largest component, and the size of the largest block. In the talk we will discuss in detail these issues and give some  general ideas about the proofs, which are based on graphdecompositions, map  enumeration, and analytic methods. If time permits, we will discuss extensions to graphs embeddable in a fixed surface and graphs defined in terms of forbidden minors.

Florent Hivert, »Arbres, tris, et fonction tangente »
  Le but de cet exposé est de donner un sens à l’équation fantaisiste suivante, due essentiellement à Désiré André en 1884 :
 Tangente(x) = somme de toutes les permutations pour lesquelles l’algorithme du tri rapide fait toujours, lors des appels récursifs, une partition non triviale en choisissant le dernier élément comme pivot. Nous nous intéressons à la combinatoire sous-jacente aux solutions formelles de certains systèmes d’équations fonctionnelles. Le point de départ trivial mais déjà très instructif est l’étude des équations x’ = 1+x2.
L’une des approches combinatoires du calcul formel est de remonter les calculs sur des objets non commutatifs en remplaçant les monômes par des mots. Les transformations sur les mots qui sont utiles dans l’étude de ces deux problèmes apparaissent naturellement dans l’étude des algorithmes de tris par bulle et rapide. Si l’on appelle Tangente la solution non commutative de x’ = 1+x2, on peut alors énoncer et prouver très facilement l’identité ci-dessus. Les développements en arbres des solutions nous permettent alors d’obtenir des preuves très naturelles de différentes formules énumératives sur les arbres dites « des équerres ».

Dominique Michelucci, »Certifier les résultats de calculs approchés »

Pour la recherche en informatique géométrique, « embrasser l’imprécision » est une mine. Cette mine est  presque inexploitée aujourd’hui, tant est grande la mauvaise réputation de l’imprécision. L’imprécision provoque des incohérences fatales pour certains algorithmes géométriques.  Elle empêche aussi l’échange fiable de données géométriques entre des modeleurs géométriques différents, et donc l’inter-opérabilité.
Pour éviter les incohérences dues à l’imprécision, la géométrie algorithmique utilise  le paradigme du calcul exact paresseux. Mais ce dernier est inutilisable  pour certains problèmes non linéaires (par  exemple,  les coordonnées  des points d’intersection de 3 surfaces rationnelles bi-cubiques sont de degré algébrique très élevé) et surtout il n’est pas pertinent pour les applications (médecine, CFAO, échange de données géométriques) où  les objets géométriques ne sont connus, ou manufacturables, ou contrôlables qu’à une tolérance près (le mot « imprécision » est vraiment trop péjoratif). De telles applications nécéssitent une représentation explicite des tolérances,  ainsi que l’optimisation et la certification des tolérances. Par exemple, le tolérancement en  CFAO épaissit les objets mathématiques: points, courbes, surfaces avec des tolérances, si bien que, dans les cas génériques, ces objets épaissis se coupent en des régions de volume non nul (contrairement aux objets idéaux, d’épaisseur nulle); les intersections contiennent donc des points à coordonnées flottantes, représentables en machine. Par ailleurs, il est toujours possible de calculer des intervalles englobant ces intersections. Ceci suggère des intervalles de solide: un solide est représenté par une approximation de l’intérieur et une approximation englobante. Diverses contraintes sont envisageables entre les deux représentations: leur distance (ou le volume intersticiel) doit être inférieure à un seuil fixé, ou bien les deux surfaces frontières doivent aussi être isotopes. Il est possible d’optimiser les tolérances,  pour éviter  des situations algorithmiquement indécidables (ou algorithmiquement et arithmétiquement trop coûteuses) comme les intersections tangentielles ou quasi tangentielles, ou bien pour garantir la validité d’une représentation par frontières avec tolérancement, ou bien pour faciliter la fabrication; dans ce dernier cas, on souhaite maximiser les tolérances, car ce sont des marges de manoeuvre.
L’exposé présentera quelques problèmes: comment garantir les résultats des méthodes en n’utilisant que des calculs approchés (arithmétique flottantes), arithmétique d’intervalles à bornes flottantes) ? Par exemple, comment calculer et garantir la topologie (homologie / homotopie / isotopie ) d’un objet géométrique ?  Comment certifier qu’une représentation par frontières tolérancée est valide ? Comment représenter et optimiser les tolérances ? L’exposé présentera aussi quelques pistes de solutions, dont une contribution venant de la CFAO à l’analyse par intervalles: les polytopes de Bernstein, qui permettent d’étendre à de grands systèmes d’équations, et à des équations non forcément algébriques, les solveurs numériques utilisant les propriétés des bases tensorielles de Bernstein.

Xavier Goaoc, « Nombres de Helly et permutations géométriques »

Comment la géométrie d’une famille d’objets de l’espace détermine la structure de l’ensemble des droites qui coupent chacun de ses membres ? Dans cet exposé, j’expliquerai comment la combinaison de méthodes géométriques, topologiques et combinatoires ont permis de nouveaux progrès sur cette question centrale en théorie des transversales géométriques ainsi que sur quelques problèmes classiques de géométrie algorithmique.

Sophie Laplante , »La complexité de la communication des distributions quantiques et au-delà »

Nous étudions la quantité de communication nécessaire pour une tâche à deux joueurs, qui consiste à produire des échantillons selon une distribution bipartite conditionnée sur des entrées données à chacun des joueurs.  Ceci inclut les distributions issues de mesures sur des états quantiques bipartites, mais aussi la complexité de la communication classique et quantique traditionnelle. Nous donnons deux méthodes de borne inférieure pour la complexité de la communication classique et quantique de la simulation des distributions causales.  Ces méthodes peut être formulées en termes de violations d’inégalités de Bell et de Tsirelson.  On montre que c’est une extension de la méthode récente de Linial et Shraibman, qui a son tour généralise une grande famille de méthodes connues en complexité de la communication : méthodes de Fourier, discrepancy, etc.  Nous étudions l’écart entre les bornes classiques et quantiques qu’on peut obtenir par ces méthodes, ce qui se traduit par une borne sur l’écart entre inégalités de Bell et de Tsirelson.  Finalement, nous donnons des bornes supérieures sur la complexité de la communication.

Travail réalisé en collaboration avec J. Degorre, M. Kaplan, et J. Roland.

Alexandre Miquel, »Construction de programmes à partir de preuves non-constructives »

La correspondance de Curry-Howard permet d’interpréter une preuve mathématique comme un programme réalisant une spécification déduite de la formule prouvée. Une application directe de cette correspondance (dont on trouve une implémentation dans Coq) est qu’à partir d’une preuve constructive d’existence d’un certain objet mathématique, on peut toujours extraire un programme calculant effectivement cet objet.
Mais que se passe-t-il lorsque la preuve mathématique utilise des mécanismes de raisonnement non constructifs tels que le tiers-exclu ou l’axiome du choix? Dans cet exposé je m’intéresserai au problème posé par l’extension de la correspondance de Curry-Howard à des logiques non-constructives (logique classique, axiome du choix, logiques modales) et je montrerai en quoi la méthode de réalisabilité introduite par Jean-Louis Krivine permet d’exprimer de telles extensions. Je montrerai également à l’aide de quelques exemples comment ces extensions de la correspondance preuve-programme font naturellement intervenir des traits de programmation non fonctionnels, tels que les continuations, les références ou les signatures de fichiers.

Guillaume Hanrot, »Probl`emes de logarithme discret : un survol »

Soit $G$ un groupe et $g$ un ‘el’ement de $G$. L’une des hypoth`eses de la cryptologie moderne est que quand $G$ est bien choisi, la fonction $n mapsto g^n$ est difficile `a inverser. Un r’esultat obtenu ind’ependamment par Nechaev et Shoup dit que si $G$ est « g’en’erique », tout algorithme inversant cette fonction effectue $#G^{1/2}$ op’erations au moins. Nous pr’esenterons des algorithmes connus pour ce probl`eme dans le cas o`u $G$ est g’en’eral, et pour les $G$ pertinents en cryptologie moderne, i.e. $G = ({mathbb F}_q)^*$ ou $G$ le groupe des points d’une vari’et’e ab’elienne sur un corps fini.

Olivier Bournez,  « Calculs continus et Calculs distribués »

Population protocols have been introduced as a model of sensor networks consisting of very limited mobile agents with no control over their own movement. A population protocol corresponds to a collection of anonymous agents, modeled by finite automata, that interact with one another to carry out computations, by updating their states, using some rules. Their computational power has been investigated under several hypotheses but mainly when restricted to finite size populations. In particular, predicates stably computable in the original model have been characterized as those definable in Presburger arithmetic.
We will consider the case when the size of the population goes to infinity. Dynamics of protocols can then be abstracted by continuous time dynamical systems, using classical mathematical population models.  We will survey some results about the mathematical convergence of population protocols to their continuous time abstraction when the size of the population goes to infinity and we will discuss some results about the power of the obtained model.

Cyril Nicaud, Analyse d’algorithmes pour les langages rationnels.

Je présenterai des analyses en moyenne et des algorithmes de génération aléatoire pour des objets issus de la théorie des langages : expressions rationnelles et automates finis. Ces résultats sont obtenus en appliquant diverses techniques de combinatoire analytique. Je parlerai notamment de la construction de l’automate de Glushkov, des opérations rationnelles sur les langages finis (travail en collaboration avec Frédérique Bassino et Laura Giambruno) et de l’algorithme de minimisation de Moore (travail en collaboration avec Frédérique Bassino et Julien David).

Stéphane Vialette , « Recherche de motifs co­nnexes dans les graphes colorés »
L’étude des réseaux biologiques est un sujet en pleine expansion (on entend ici par réseaux biologiques une grande variété de structures : réseaux métaboliques, réseaux d’interactions entre protéines, réseaux de régulation, …) et les motifs dans ces réseaux (graphes) jouent un rôle de première importance. Informellement, il existe deux façons de définir un motif dans un graphe. La plus ancienne est la vue topologique qui induit fondamentalement un problème d’isomorphisme de sous-graphes. Plus récemment, une nouvelle description (fonctionnelle) a été introduite qui se démarque par l’abandon de la topologie des motifs au profit de leur fonctionnalité (la fonctionnalité d’un sommet est alors dénotée par une couleur). C’est cette dernière description qui sera ici considérée.d’un point de vue algorithmique par l’étude du problème GRAPH MOTIF: Étant donnes un ensemble de couleurs M et un graphe G muni d’une coloration de ses sommets, trouver une occurrence connexe de M dans G, i.e., un sous-graphe connexe de G colorié par M. Nous présenterons l’état de l’art sur la complexité du problème GRAPH MOTIF (complexité standard et paramétrée) et introduirons quelques variantes dont nous discuterons la complexité.