Journées Nationales d'Informatique Mathématique 2010

Journées Nationales d'Informatique Mathématique 2010

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

­­­
Les invités sont Günter Rote (Berlin) et Xuding Zhu (Tai­wa­n). Le programme est maintenant disponible (en savoir plus...)

 

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éees

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 des 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 est

connu pour être décidable depuis les travaux d'A. Tarski (1932). Du fait

de 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).