Les Journées Nationales d’Informatique Mathématique auront lieu les 21 et 22 janvier 2010 à l’Université Paris 6 (Jussieu, Amphi Durand).

Programme

Jeudi 21 janvier 2010

• 10:30 – 11:00 : Accueil et café
• 11:00 – 12:00 : Conférence invitée : Günter Rote (Berlin) « Ps­eudotriangulations » Résumé
• 12:15 – 13:00 : Eric Rivals (LIRMM) « Scaling Exact Set Pattern Matching Algorithms for Small Alphabets » Résumé
• 13:15 – 14:30 : Déjeuner
• 14:30 – 15:15 : Sylvain Périfel (LIAFA) « Bornes inférieures en complexité booléenne et algébrique » Résumé
• 15:15 – 16:00 : Jean-François Marckert (LABRI) « Sur la convergence des grands arbres » Résumé
• 16:00 – 16:30 : Pause café
• 16:30 – 17:15 : Gilles Zémor (Inst. Math. Bordeaux) ­ « Codes et graphes extenseurs » Résumé
• 17:15 – 18:30 : Discussion sur le GDR
• 18:30 – 21:00 : Buffet-cocktail (cave Esclangon) ­

Vendredi 22 janvier 2010

• 09:00 – 10:00 : Conférence invitée : Xuding Zhu (Taiwan) « Thue choice number of paths » Résumé
• 10:15 – 11:00 : Valérie Berthé (LIRMM) « Autour de la conjecture de Pisot » Résumé
• 11:00 – 11:30 : Pause café 
• 11:30 – 12:15 : Gilles Trombettoni (INRIA-Sophia) « Introduction aux méthodes à intervalles pour la résolution de systèmes d’équations non linéaires » Résumé
• 12:15 – 13:00 : Mohab Safey el Din (LIP6) « Autour de l’élimination des quantificateurs sur les réels » Résumé
• 13:15 – 14:30 : Déjeuner
• 14:30 – 15:15 : Thomas Colcombet (LIAFA) « Jeux d’existence de bornes et applications » ­Résumé
• 15:15 – 16:00 : Paul-André Melliès (PPS) « Catégories de dialogue et sémantique des jeux » Résumé

Les orateurs ont été proposés par les GT suivants : GT GeoAlgo : Conférence invitée : Günter Rote GT Graphes : Conférence invitée : Xuding Zhu GT Comatege : Eric Rivals GT CMF : Sylvain Périfel GT ALEA : Jean-François Marckert GT C2 : Gilles Zémor GT SDA2 : Valérie Berthé GT Arith : Gilles Trombettoni GT CF : Mohab Safey el Din GT Jeux : Thomas Colcombet GT Geocal et LAC : Paul-André Melliès

Résumés

Günter Rote (Berlin), « Pseudotriangulations »

Abstract: A pseudotriangle is a polygon with three convex vertices and an arbitrary number of reflex vertices. A pseudotriangulation of a planar set of n points is a decomposition of the convex hull into pseudotriangles, using the given set of points as vertices. I will survey the main properties and some of the applications of pseudotriangulations and their connections to other fields, such as expansive motions, data structures for ray shooting, or locally convex surfaces.

Xuding Zhu (Taiwan), »Thue choice number of paths »

Abstract: A vertex colouring of a graph G is called non-repetitive if for any path of G of even length, say of length 2n, the colour sequence of the first half (i.e., the first n vertices) is different from the second half (i.e., the last n vertices). The Thue chromatic number of G is the least number of colours needed in a non-repetitive colouring of G. A classical result of Thue says that the infinite path has a Thue chromatic number 3. The Thue choice number of a graph G is the minimum integer k such that if each vertex v is given a set L(v) of k permissible colours, then there is a non-repetitive colouring f of G with f(v) in L(v). It was known before that the Thue choice number of the infinite path is at most 16. In this talk, I shall sketch a proof showing that the Thue choice number of the infinite path is at most 4.

Valérie Berthé (LIRMM), « Autour de la conjecture de Pisot »

Résumé : Une substitution est un morphisme de monoïde libre : il s’agit de remplacer une lettre par un mot. Les systèmes dynamiques substitutifs sont des modèles symboliques naturels pour de nombreux systèmes dynamiques déterministes auto-similaires. La conjecture de Pisot fait un lien entre propriétés arithmétiques et propriétes spectrales d’une substitution : plus précisément, le système dynamique symbolique engendré par une substitution Pisot est conjecturé avoir un spectre discret. Les substitutions sont non seulement étudiées d’un point de vue symbolique mais aussi dans un cadre géométrique multi-dimensionnel. Il existe alors un analogue de la conjecture Pisot exprimé en termes d’ensembles de Delone et de quasi-cristaux. Le but de cet exposé est de présenter plusieurs formulations équivalentes de cette conjecture ainsi que des conditions (suffisantes et/ou nécessaires) effectives exprimées en termes de graphes, de pavages et de plusieurs variations autour de la notion de coïncidence. 

Thomas Colcombet (LIAFA), « Jeux d’existence de bornes et applications »

Résumé : Dans cet exposé, nous montrerons comment il est possible d’utiliser des jeux pour résoudre certains problèmes en logique ou en théorie des langages. Les problèmes considérés sont par exemple l’existence d’une borne sur le nombre d’itérations du point fixe d’une formule monadique sur les mots, la résolution de la hauteur d’étoile restreinte sur les arbres ou encore le calcul de l’index de Mostowski d’un langage régulier d’arbres infinis (i.e., le nombre d’alternance de point fixe nécessaire). Les jeux que l’on considère sont des jeux quantitatifs à deux joueurs antagonistes. On ne cherche pas à en déterminer la valeur de manière exacte, mais simplement à en donner une `estimation’ suffisante pour les applications. Ces méthodes reprennent certaines idées classiques utilisées en théorie des automates sur les arbres infinis.

Jean-François Marckert (LABRI), « Sur la convergence des grands arbres »

Résumé : L’objet de la combinatoire est l’étude des structures discrètes. Dans le passé, on a souvent entendu par cela, décomposer, compter le nombre d’objets de taille $n$, trouver des bijections avec des objets plus simples… Par exemple, on voit qu’un arbre plan est une liste, possiblement vide d’arbres plans, on sait que nombre d’arbres plans à $n+1$ noeuds est le $n$ ème nombre de Catalan, et qu’il existe une bijection entre la famille des arbres plans à $n+1$ noeuds et la famille des chemins de Dyck à $2n$ pas. Seulement, tout cela, ne nous dit pas à quoi ressemble un arbre plan typique à 10 000 000 noeuds. Ces dernières décennies on a vu apparaître d’autres types de résultats: par exemple, la hauteur moyenne d’un arbre plan à $n$ noeud est de l’ordre de $sqrt{n}$, tout comme la distance entre deux noeuds tirés au hasard. Cela donne l’ordre de grandeur d’un arbre typique à 10 000 000 de noeuds, mais ne nous dit toujours pas à quoi il ressemble. Dans cet exposé, je parlerai d’une nouvelle famille de résultats, apparus ces dernières années, sur l’impulsion de David Aldous. Il s’agit de montrer la convergence non pas d’un paramêtre associé à l’arbre mais bien de la structure complète: soigneusement normalisé, les arbres plans à $n$ noeuds, sous la loi uniforme, convergent en loi vers un arbre continu. J’expliquerai ce que cela signifie, comment se montre ce genre de résultats, et en donnerai quelques exemples.

Paul-André Melliès (PPS), « Catégories de dialogue et sémantique des jeux »

Résumé : Une catégorie de dialogue est une catégorie monoidale équipée d’un objet exponentiable. Dans cet exposé, j’expliquerai comment construire la catégorie de dialogue libre sur une catégorie donnée. La construction est inspirée de la théorie fonctorielle les noeuds, qui est appliquée ici aux démonstrations de la logique formelle. Nouveauté de la construction, les diagrammes de corde 2-dimensionnels de la théorie des noeuds sont remplacés par des diagrammes de surface 3-dimensionnels décrivant les démonstrations formelles comme des suites de transformations élémentaires sur les arbres de formule. Ce point de vue topologique sur la logique formelle permet de penser la catégorie de dialogue libre comme une catégorie dont les objets sont des jeux de dialogue, et dont les morphismes sont des stratégies interactives particulières (dites innocentes) entre ces jeux. J’expliquerai au cours de mon exposé en quoi ce travail permet de mettre à profit les idées de la logique linéaire et de l’algèbre pour mieux comprendre les structures de contrôle des langages de programmation.

Sylvain Périfel (LIAFA), « Bornes inférieures en complexité booléenne et algébrique »

Résumé : Un des objectifs centraux en complexité est la preuve de bornes inférieures : par exemple, montrer une borne inférieure super-polynomiale sur le temps d’exécution de tout algorithme pour SAT. Plus modestement, beaucoup d’autres bornes inférieures restent à montrer et mon exposé s’attachera principalement aux bornes inférieures sur la taille de circuits pour certains problèmes. Les circuits sont, en quelque sorte, une manière de se donner un algorithme potentiellement différent pour chaque taille d’entrée d’un problème à résoudre.

Je montrerai d’abord des liens entre ces bornes inférieures pour les circuits et la dérandomisation d’algorithmes, c’est-à-dire le fait de rendre déterministe des algorithmes probabilistes. Ensuite je parlerai du calcul du permanent, un polynôme similaire au déterminant mais a priori bien plus difficile à calculer. Enfin, nous verrons des bornes inférieures pour le calcul d’autres polynômes plus ou moins explicites.

Eric Rivals (LIRMM), « Scaling Exact Set Pattern Matching Algorithms for Small Alphabets »

Abstract : The biotechnological revolution of Ultra-high Throughput Sequencers (HTS) led us to reconsider exact set pattern matching for huge pattern sets, a well-studied problem in computer science. The main goal of many researches is to keep running times reasonable while being able to search in large texts for millions of short words simultaneously: a scalability issue. A few years ago (2003), the fastest state of the art solutions could handle up to $100.000$ patterns at a time. Clearly, efficient programs resort to filtration: a phase that eliminates some text positions that cannot match any pattern. However, usual filtration techniques proves to be less efficient with small alphabets as those of biological texts. We will present an exact set pattern matching algorithm that reaches the objective in terms of pattern number and illustrate our approach to deal with small alphabets. We will also show that the tool we implemented, MPSCAN, can keep up in practise with algorithms that preprocess the text off-line before the search procedure. Finally, we illustrate the efficiency of our algorithm by showing its applications on real biological data. 

Related publications: 

• MPSCAN: fast localisation of multiple reads in genomes E. Rivals, L. Salmela, P. Kiiskinen, P. Kalsi, J. Tarhio Proc. 9th Workshop on Algorithms in Bioinformatics Lecture Notes in BioInformatics (LNBI), Springer-Verlag, Vol. 5724, p. 246-260, 2009.
• Using reads to annotate the genome: influence of length, background distribution, and sequence errors on prediction capacity. N. Philippe*, A. Boureux*, L. Bréhèlin, J. Tarhio, T. Commes, E. Rivals Nucleic Acids Research (NAR) doi:10.1093/nar/gkp492; 2009. Work in collaboration with the lab of Jorma Tarhio at Helsinki Universtity of Technology (Finland).

Mohab Safey El Din (Lip6), « Autour de l’élimination des quantificateurs sur les réels »

Résumé: Le problème classique d’élimination des quantificateurs sur les réels estconnu pour être décidable depuis les travaux d’A. Tarski (1932). Du fait le la multitude d’applications potentielles de ce problème, ces dernières décennies ont vu d’importants efforts pour obtenir des algorithmes et implantations performants permettant de le résoudre. Il est connu que dans le pire cas, ce problème est de complexité doublement exponentielle en le nombre d’alternances de quantificateurs. Il est donc naturel de chercher des algorithmes dédiés à des situations moins générales mais utiles dans les applications. Nous montrerons ainsi comment exploiter certaines propriétés géométriques pour obtenir des algorithmes efficaces sur une variante du problème général, permettant par exemple l’analyse de schémas numériques pour les EDP. Une première implantation de l’algorithme obtenu permet de résoudre des problèmes inattegnables par les méthodes générales de résolution précédemment connues.

Gilles Trombettoni (INRIA Sophia-Antipolis), « Introduction aux méthodes à intervalles pour la résolution de systèmes d’équations non linéaires »

Résumé : Cet exposé présente le schéma de résolution des systèmes de contraintes (équations, inégalités) non linéaires utilisé par les méthodes à intervalles. On présentera l’arbre de recherche utilisé pour trouver l’ensemble des solutions ainsi que les trois catégories d’algorithmes de filtrage/contraction permettant de simplifier l’espace de recherche en temps polynomial: l’algorithme de Newton intervalles issu de l’analyse numérique (par intervalles), les algorithmes de programmation par contraintes et la relaxation linéaire.

Gilles Zémor (Institut de Mathématiques de Bordeaux)

Les graphes extenseurs (expander graphs) sont des familles de graphes pour lesquels tout sous-ensemble de sommets X suffisamment distinct de l’ensemble complet a un nombre de voisins au moins égal à cjXj pour une certaine constante c. Cette propriété se caractérise par un large écart entre les première et seconde valeurs propres du graphe. Les premières constructions de tels graphes remontent aux années 1980 et ont trouvé de nombreuses applications depuis, principalement dues à ce qu’ils ont des propriétés typiques de graphes aléatoires mais non triviales à obtenir constructivement. Or justement, les meilleurs codes correcteurs étant des codes aléatoires typiques, il est tentant d’essayer d’obtenir des bonnes constructions de codes par l’intermédiaire de graphes extenseurs. L’idée de construire des codes à l’aide d’un graphe et de petits codes linéaires constituants remonte à Tanner (1981) et pris son plein essor en 1996 grâce à un travail de Sipser et Spielman qui montrèrent, en s’appuyant sur la propriété d’expansion, que l’idée de Tanner permet à la fois la construction de codes binaires asymptotiquement bons et de garantir la correction d’un nombre d’erreurs proportionnel en la longueur du code n, le tout en temps quasi-linéaire en n. Nous présenterons cette construction ainsi qu’un certain nombre de variantes et de développements récents. Cette approche peut être vue comme intermédiaire entre le codage algébrique traditionnel et les méthodes plus modernes de décodage itératif impliquant les codes à matrice de parité creuse (LDPC).