Ce site est maintenant une archive couvrant les séminaires des années 2006, 2007 et 2008.

Le séminaire du LaBRI (Approximativement un jeudi sur deux à 14 heures)

Le séminaire du LaBRI se déroule approximativement deux fois par mois le jeudi de 14h à 15h en temps normal dans l'amphithéatre du LaBRI. L'exposé de 50 minutes du séminaire s'adresse à tous les chercheurs du LaBRI. L'orateur a la tâche délicate de présenter un domaine de recherche, en restant accessible à un large public d'informaticiens, sans renoncer à un ou deux passages techniques illustrant les modes de raisonnements du domaine.
Le secrétaire du séminaire du LaBRI.
Yvan Le Borgne
On trouvera plus de détails sur l'organisation du séminaire ici (Ce lien n'est accessible que depuis les machines du LaBRI.)

Le(s) prochain(s) séminaire(s)

Le responsable est maintenant David Ilcinkas.

Programme prévisionel (encore en discussion)

Anciens séminaires

(Les exposants peuvent mettre en ligne ici les transparents de leur exposé.)

20 novembre Tamas Sziranyi (Computer and Automation Institute of Hungarian Academy of Sciences and PeterPazmani Catholic University of Budapest)

invittée de Jenny Benois-Pineau

Bayesian inference for video geometry"

Structure and objects in video images are often not known. If we search for camera registration or focused areas of these situations, some a priori knowledge was needed. Now I present methods for finding geometrical structures in images or videos without any preliminary object definition:
- First, a new motion-based method is presented for automatic registration of images in multi-camera systems, to permit synthesis of wide-baseline composite views by using an iterative Bayesian assignment of corresponding image areas. Another application of this co-motion inference is to find the vanishing-point position for planar reflected images or shadows.
- A new automatic solution for finding focused areas based on localized blind deconvolution. This approach makes possible to determine the relative blur of image areas without a priori knowledge about the images or the shooting conditions. The method uses deconvolution based feature extraction and a new residual error based classification for the discrimination of image areas. We also show the method´s usability for applications in content based indexing and video feature extraction.
- An MRF approach is also introduced for Bayesian Foreground and Shadow Detection in Uncertain Frame Rate Surveillance Videos.

3 juillet Claire Mathieu (Brown University)

invitée de Robert Cori.

Théorie algorithmique des jeux et enchères combinatoires

Les théories économiques recherchent des solutions satisfaisant des propriétés d'équilibre naturelles ou souhaitables, mais jusqu'à récemment le point de vue d'efficacité de calcul et de complexité algorithmique était laissé de côté. Les questions algorithmiques étudiées en informatique ont récemment commencé à incorporer des modèles de compensation financière. Les rapprochements entre les deux domaines commencent à porter leurs fruits.
La notion d'équilibre de Nash est fondamentale en théorie des jeux. Dans quelles circonstances peut-on efficacement calculer un équilibre de Nash?
L'optimisation du fonctionnement de réseaux repose sur la collaboration des participants. Si chacun travaille pour son propre compte, quelles seront, au pire ou au mieux, les qualités du réseau dans l'équilibre résultant, selon les modèles de participation aux couts?
Les enchères combinatoires permettent de vendre des collections d'objets à des acquéreurs dont les préférences peuvent être complexes. Comment concevoir un mécanisme d'allocation et de détermination des prix de faible complexité algorithmique et permettant de satisfaire au mieux les acquéreurs?
Cet exposé abordera ces questions pour présenter un panorama partiel d'un domaine de recherche émergeant à l'interface entre algorithmique et économie.

12 Juin Arnaud Pêcher (LaBRI)

Présentation du projet REALOPT

RealOpt est une équipe-projet INRIA en cours de création (porteur F. Vanderbeck) formée de quelques chercheurs du LaBRI (pour les aspects graphes) et du MAB (pour les aspects programmation mathématique). Notre but est de développer des formulations pertinentes pour les problèmes d'optimisation combinatoire, en exploitant des techniques telles que la programmation linéaire (génération de colonnes, approche polyédrale), la programmation non-linéaire (quadratique) et l'algorithmique de graphes.
La modélisation par des graphes de Feketete et Shepers (1997) du problème du placement de parallélépipèdes dans un container est une bonne illustration de ce que nous souhaitons faire: cette modélisation a permis de faire un saut quantitatif quant à la taille des problèmes traités. En effet, en représentant les solutions par des graphes, de nombreuses symmétries (i.e. des solutions identiques) sont éliminées et les bonnes propriétés algorithmiques des graphes mis en jeu, des graphes d'intervalle, sont la clef pour la conception de l'algorithme de Fekete et Shepers.

22 mai Alexis Bouquet (DCSSI)

invité de Julien Bernet, Serge Chaumette et Olivier Ly.

Evaluation de la sécurité des systèmes d'information.

Les technologies de l'information sont aujourd'hui omniprésentes dans l'organisation de la population, des états et des entreprises. Or ces acteurs se développent en ayant parfois des intérêts conflictuels conduisant à un monde hostile où l'information est devenue un bien sensible au regard d'enjeux politiques et économiques. Ceux-ci mettent par conséquent en exergue un besoin de sécuriser les systèmes d'information au sein de leur environnement opérationnel. L'évaluation de la sécurité des systèmes d'information ou produits de sécurité sous-jacents devient alors une problématique majeure pour l'ensemble des acteurs qui souhaitent protéger par exemple leurs informations d'identité, leurs données bancaires, leurs politiques de défense, leurs services publics, leurs propriétés intellectuelles, leurs stratégies commerciales ou leurs moyens de conception, de développement ou de vente, etc... aussi bien en confidentialité, intégrité et disponibilité. Les résultats des évaluations devraient aussi permettre de comparer les systèmes ou produits de sécurité entre eux. Comment évaluer la sécurité des systèmes d'information ? Quelle confiance doit-on accorder aux résultats des évaluations ? Ces deux questions initient l'exposé dont l'objectif est de présenter le schéma français de certification, la méthodologie d'évaluation Critères Communs (CC), ainsi qu'un exemple d'évaluation d'une carte à puce. Les méthodes formelles au sein des CC seront également abordées.

10 avril Frederic Guinand, Professeur au LITIS, Université du Havre

invité de Serge Chaumette.

Quelques résultats dans le domaine des réseaux mobiles ad hoc discontinus

Les réseaux mobiles ad hoc (MANET) sont des réseaux auto-organisés composés de stations équipées d'interface de communication sans fil de type WiFi. Un MANET peut être modélisé par un graphe dynamique dont les sommets correspondent aux stations et les arêtes aux connexions entre stations. Très souvent, ce graphe est considéré connexe. Nous nous intéressons aux problèmes qui surviennent lorsque cette connexité n'est plus garantie, on parle alors de réseaux mobiles ad hoc discontinus ou tolérant les délais (DT-MANET). C'est en particulier le cas des réseaux mobiles ad hoc métropolitains. Pour ces réseaux, nous évoquerons différents problèmes allant de la diffusion à la pertinence des modèles de mobilité.

17 avril Alberto Del Bimbo

invité de Jenny Benois-Pineau

3 avril Sang Il Oum

invité de Bruno Courcelle

Line graphs of large rank-width

L'inclusion des graphes au sens des "vertex-minors" est une notion analogue à l'inclusion au sens des mineurs, tout comme la largeur de rang ("rank-width") est analogue à la largeur arborescente. On conjecture que les graphes d'intersection des cordes d'un cercle ("circle graph") jouent , par rapport à la largeur de rang, un rôle semblable à celui des graphes planaires par rapport à la largeur arborescente, et que les graphes qui ne contiennent pas comme "vertex minor " un graphe d'intersection de cordes donné sont de largeur de rang bornée. Ce résultat généraliserait "Graph Minors V". Il est montré dans l'exposé pour les "line graphs" (graphes d'incidences) et les graphes d'intersection de cordes bipartis. La conjecture reste ouverte.
Résumé fait par B. Courcelle

20 Mars Jean-Luc Toffart (Adjoint au fonctionnaire sécurité et Défense du CNRS)

Protection du patrimoine scientifique

invité de Maylis Delest
Il s'agit d'un expose de sensibilisation aux menaces dirigees contre le patrimoine scientifique et humain du CNRS avec des exemples concrets de problemes rencontres dans certains laboratoires. Les menaces sont elles un mythe ou une realite ? Protection contre une menace interieure ou exterieure ? Sommes nous sur de ne pas nous mettre en situation de faiblesse ? Cet expose sera ouvert a toutes les questions que vous pourriez vous poser sur la fonction du Fonctionnaire de securite defense.

13 mars Cédric Chauve, Simon Fraser University

Calcul de distances génomiques.

Les récents efforts de séquencages de génomes complets ont permis d'attaquer des questions de biologie évolutionnaire fondamentales, notamment sur les scenarios possibles d'évolution entre espèces. Au coeur de la plupart des approches, on retrouve la question suivante : étant donnes deux génomes, quelle suite d'évènements de type "réarrangement génomiques" permet de passer de l'un à l'autre.
Cette question peut se traduire en différentes questions algorithmiques, selon le type de génomes étudiés, le modèle d'évolution que l'on prend en compte ou le critère d'optimisation combinatoire que l'on choisit par exemple.
Cet exposé propose un tour d'horizon de ces questions, dont certaines sont difficiles a résoudre (tri de permutations non-signées par renversements) alors que d'autres sont extrêmement faciles a résoudre (distance par "double-cut-and-join")... bien qu'elles soient toutes issues de la même question de biologie évolutionnaire.
Certains des résultats présentés ont été obtenus en collaboration avec Anne Bergeron (Montréal), Sèverine Bérard (Montpellier), Annie Chateau (Montpellier), Christophe Paul (Montpellier) et Eric Tannier (Lyon).

6 mars Markus Lohrey, Université de Leipzig

invité de Géraud Senizergues

Algorithmics on compressed strings

(joint work with Yury Lifshits and Saul Schleimer).
In recent years, straight-line programs (SLPs) turned out to be a convenient formalism for investigating algorithms on compressed string data. An SLP is a context-free grammar that generates exactly one string $w$. Since the length of the generated string $w$ may grow exponentially with the size of the SLP, the latter may be seen as a compressed representation of $w$. The output of many practical compression algorithms, like for instance those of the Lempel-Ziv family, can be considered as SLPs. The talk will give an overview on recent complexity results for algorithmic string problems, where the input string is given compressed as an SLP. Also applications in other fields like for instance algorithmic groups theory will be presented. If time permits, extensions to compressed trees will be discussed.

14 février Hans Meine (Université de Hambourg)

A New Sub-pixel Topological Map for Image Analysis

This talk introduces our new, sub-pixel precise GeoMap as a unified representation for both topological and geometrical aspects of a partition of the plane (e.g. a 2D segmentation result). Our GeoMap is conceptually very similar to the toger framework developed at the LaBRI, but is not based on discrete maps using inter-pixel boundaries, but on a polygonal representation.
This has several advantages: For image segmentation, it becomes possible to combine the advantages of sub-pixel accuracy (as provided e.g. from the well-known edge-detector by Canny) and topologically useful, closed boundaries (as known from the traditional watershed transform), and lets us introduce the exact watershed transform as the basis for hierarchical segmentation approaches.
Furthermore, we demonstrate that our new sub-pixel GeoMap is also suitable for applications beyond image segmentation, e.g. triangulation or skeletonization.

24 Janvier Olivier Beaumont (LaBRI)

Présentation de l'équipe-projet Cepage: Chercher et Essaimer dans les Plates-formes A Grande Echelle

Les membres de l'équipe-projet INRIA Cepage s'intéressent à la conception d'algorithmes, de structures de données et de services pour les plates-formes à grande échelle comme les grilles de calcul et les réseaux pair-à-pair. Ces nouvelles plates-formes sont caractérisées par leur grande taille et par l'hétérogénéité et la volatilité des ressources (de calcul et de communication) qui les composent. D'un point de vue algorithmique, ces caractéristiques nécessitent la conception d'algorithmes distribués s'appuyant sur des informations locales. Dans cet exposé, je présenterai rapidement les solutions apportées par l'algorithmique parallèle pour la gestion de l'hétérogénéité et les systèmes distribués pour la gestion du dynamisme. Je présenterai ensuite les objectifs du projet et j'insisterai plus particulièrement sur quelques techniques d'algorithmique distribuée (calcul de multi-flots, network coding...) pour illustrer les méthodes qui peuvent être employées pour la conception d'algorithmes efficaces et garantis sur des plates-formes volatiles et distribuées à grande échelle.

10 Janvier Bertrand Augereau (Laboratoire SIC, Université de Poitiers)

Champs de déplacements et bases polynômiales

Cette présentation part d'un a priori : la volonté de représenter les déplacements par des champs vectoriels denses, champs dont la densité initiale est donnée par la résolution spatiale de la séquence d'images.
Le premier point abordé sera celui de l'extraction de ces champs. Nous insisterons sur une méthode régularisante qui couple approximation de la composante normale du déplacement et lissage directionnel. Nous présenterons également une extension couleur fondée sur la notion de tenseur de flot.
En second lieu, nous aborderons l'utilisation pratique de ces champs de déplacements. Nous introduirons alors une méthode de représentation à l'aide de bases finies orthogonales de polynômes bi-variables. Après avoir donné quelques propriétés fondamentales de ces bases, nous nous pencherons plus particulièrement sur la modélisation par projection des champs de déplacements et, notamment, sa possible utilisation en tant que descripteur du mouvement perçu.

22 novembre Patrice Ossona de Mendez (EHESS)

Partitions régulières de graphes épars et applications

Le concept de tree-width est central dans l'analyse des classes de graphes à mineurs exclus menée par Robertson et Seymour et à gagné un intérêt important de par ses applications algorithmiques, essentiellement à la suite du résultat général de Courcelle concernant la décidabilité de propriétés exprimées en logique monadique du second ordre pour les graphes de tree-width borné. Il est apparu que nombre de problèmes NP-complet peuvent être résolus en temps polynomial lorsqu'ils sont restreints à une classe de tree-width borné. Néanmoins, une telle restriction est extrêmement forte, les graphes planaires, par exemple, n'ayant pas un tree-width borné. Une approche alternative consiste à considérer des partitions de graphes, de manière à ce que p parties induisent un sous-graphe de faible tree-width. DeVos et al. ont ainsi démontré que pour toute classe propre C fermée par mineur (i.e. toute classe fermée par mineur excluant au moins un graphe) et pour tout entier p, il existe une constante N(C,p) telle que tout graphe G?C possède une partition de ses sommets en au plus N(C,p) parties telle que i?p parties induisent un sous graphe de tree-width au plus (i-1). Il est naturel de se demander si les parties pourraient être choisies «plus petites»ou «plus simples». Le tree-depth td(G) d'un graphe G comme étant la hauteur minimale d'une forêt enracinée dont la fermeture inclue G. Cet invariant monotone par mineur est lié au tree-width par tw(G)+1?td(G)?tw(G) log n, où n est l'ordre de G. Les classes de tree-depth bornées sont particulièrement petites, dans le sens qu'elles n'incluent qu'un nombre fini de classes d'équivalences pour l'homomorphisme, et qu'elle exclue les longues chaînes (à comparer avec les classes de tree-width borné qui excluent les grandes grilles). Notre résultat principal est que pour toute classe propre C fermée par mineur et pour tout entier p, il existe une constante N'(C,p) telle que tout graphe G?C possède une partition de ses sommets en au plus N'(C,p) parties telle que i?p parties induisent un sous graphe de tree-depth au plus i, le tree-depth étant le plus grand invariant satisfaisant une telle propriété. Notre démonstration conduit de plus à un algorithme en temps linéaire pour les classes d'expansion bornée (qui peuvent être vue comme une généralisation des classes excluant un mineur topologique). Précisons ce que sont les classes d'expansion bornée: Le grad de rang r d'un graphe G est défini par ?r(G)=max |E(H )| / |V(H )| où le maximum concerne tous les mineurs H G obtenus en contractant un ensemble de sous graphes sommets-disjoints de rayons au plus r et en effaçant arbitrairement des sommets et des arêtes. Une classe de graphe C est d'expansion bornée si supG?C ?r(G)< ? (pour tout entier r). Ainsi, toute classe propre fermée par mineur, toute classe de degré borné, mais aussi toute classe composée de squelettes de complexes simpliciaux de dimension d et d'aspect ratio borné et, plus généralement, toute classe excluant un mineur topologique sont des classes d'expansion bornée. Nos résultats algorithmiques principaux concernant les classes d'expansion bornée sont: a.. un algorithme en temps linéaire de coloration induisant de faibles tree-depth, b.. un algorithme en temps linéaire de recherche et de dénombre des sous graphes isomorphes à un sous graphe fixé. c.. d'un point de vue plus général, la décidabilité en temps linéaire de propriété du premier ordre, d.. l'existence de séparateurs de tailles sous-linéaires pour les classes d'expansion sous-exponentielle, e.. l'extension des résultats sur les dualités restreintes d'homomorphismes aux classes d'expansion bornée.

25 octobre Frédéric Magniez (LRI)

Les défis de l'ordinateur quantique

Chaque année les ordinateurs sont de plus en plus rapides, mais utilisent fondamentalement tous la même physique de Newton. Feynman s'est interrogé en 1982 sur cette restriction. Le principe d'un ordinateur quantique serait d'utiliser des phénomènes quantiques pour mener à bien des tâches que nos machines ne savent pas réaliser aujourd'hui. En partant de cette reflexion, Bennett et Brassard ont exhibé en 1984 le premier protocole quantique permettant des conversations chiffrées parfaitement sûres, alors qu'une telle sécurité inconditionelle n'existe pas en classique. A l'opposé, Shor a montré en 1994 comment la plupart des systèmes cryptographiques classiques actuels deviendraient vulnérables face à utilisation d'un ordinateur quantique (par exemple : cartes bleues, signatures numeriques, conversations chiffrées...). Dans cet exposé, je passerai en revue les notions importantes de la cryptographie quantique et du calcul quantique, afin de présenter les principaux protocoles et algorithmes battant leurs analogues classiques. J'exposerai aussi certains résultats récents ainsi que des problèmes ouverts.

Jeudi 4 octobre 2007 : James Abello, DIMACS Center, Rutgers University, NJ 08854, USA and Ask.com

invité de Guy Melançon au LaBRI.

The Majority Rule, Combinatorial Geometry and Visibility Graphs

The Marquis du Condorcet recognized 200 years ago that majority rule can produce intransitive group preferences if the domain of possible (transitive) individual preference orders is unrestricted. We present results on the cardinality and structure of those maximal sets of permutations for which majority rule produces transitive results (consistent sets). Consistent sets that contain a maximal chain in the Weak Bruhat Order of the Symmetric Group inherit from it an upper semimodular sublattice structure. They are intrinsically related to a special class of Hamiltonian graphs called persistent graphs. These graphs in turn have a clean geometric interpretation: they are precisely visibility graphs of staircase polygons. We highlight the main tools used to prove these connections and indicate possible social choice and computational research directions. The talk will be "almost" self contained.

Le MERCREDI 5 septembre 2007 : Gerald Weber, University of Auckland, New Zealand

invité de Robert Strandh au LaBRI.

Old and New: User Interfaces for Enterprise Applications

As the technologies in enterprise computing evolve, we are also confronted with new problems in the construction of good interfaces. The humble form-based interface still has some surprising potentials. In this talk I give an overview of our recent research in this area.

Le 7 Juin 2007: Alexandru Telea (Eindhoven University of Technology)

Visualisation de l'évolution des logiciels

Les logiciels modernes sont des systèmes aux structures très complexes comprenant des milliers de fichiers contenant des millions de lignes de code, développés par des dizaines de programmeurs pendant des années. Dans les dernières années, la maintenance des logiciels est devenue le problème le plus coûteux et un des plus compliqués dans le génie logiciel, prenant plus de 80% du temps du processus informatique. La compréhension des grandes bases des logiciels est une des composantes les plus importantes dans la maintenance.
Dans cet exposé, nous présentons un jeu de méthodes et techniques recherchées pour la visualisation interactive de la structure, la qualité, et l'évolution des logiciels. Ces méthodes assistent les développeurs, ingénieurs, et leaders de projet pour la gestion des grands projets de développement. Nous démontrons les méthodes et techniques proposées par plusieurs scénarios exécutés sur des grands projets open-source et industriels trouvés dans des dépôts CVS et Subversion.

Le 5 avril 2007 : Raymond Namyst (LaBRI)

Les architectures multiprocesseurs hiérarchiques seront bientôt partout... Mais sait-on les programmer efficacement ?

Les calculateurs parallèles les plus puissants sont aujourd'hui majoritairement formés d'un très grand nombre de noeuds multiprocesseurs interconnectés par un réseau rapide. Dans ce domaine, les évolutions les plus spectaculaires portent essentiellement sur l'architecture des noeuds dont le nombre de niveaux hiérarchiques atteint une ampleur sans précédent. La faute en incombe aux constructeurs de microprocesseurs qui, après s'être livrés durant 30 ans à une course à la fréquence, rivalisent désormais à coups de puces multi-coeurs multiprogrammées. Sun, par exemple, s'apprête à commercialiser des puces capables d'exécuter simultanément 8 "threads" sur chacun des 8 coeurs et IBM en est à 4 "threads" x 2 coeurs. De leur côté AMD et Intel commencent à produire des puces à 4 coeurs et annoncent l'intégration de près d'une centaine de coeurs sur une même puce. Vu la diversité des temps d'accès mémoire et de communication entre les différentes unités de calcul, ces nouvelles architectures exigent, pour en tirer la quintessence, de répartir les flots d'exécutions, les données et les communications avec d'extrêmes précautions. Dans cet exposé, nous examinerons comment les utilisateurs tentent de programmer efficacement de telles architectures, et je présenterai les problèmes rencontrés lorsque, pour aider ces utilisateurs, nous concevons des supports d'exécution pour ces machines.

Remarque sur le 29 mars 2007 : Exposé au Colloquium de l'IMB vers 16h de Pierre Castéran et Christine Bachoc (math)

Le 15 mars 2007 : Guy Melancon (LaBRI)

Fouille de données interactive, visualisation et exploration de grands graphes.

L'exposé proposera un survol des questions qui animent la communauté de recherche en visualisation, en mettant l'accent sur la visualisation de graphes et plus particulièrement sur ses apports en termes de fouille de données. La visualisation apparaît aujourd'hui comme une approche prometteuse pour affronter les nombreuses questions soulevées par le volume croissant de donner à maîtriser, à fouiller et à analyser. Elle intervient aussi en appui du travail de modélisation et de simulation de phénomènes "complexes" (calcul intensif, modélisation des systèmes biologiques, etc.). Les acteurs des milieux académiques institutionnels et du monde industriel s'accordent sur l'importance que pourront prendre les approches tirant profit des technologies de visualisation et paradigmes visuels (NSF, NIH, Ministère de l'industrie, ANR, ...), sans exclure aucune approche: cartographie interactive, réalité virtuelle, visualisation et informatique nomades, visualisation et travail collaboratif, etc. Nous nous pencherons plus particulièrement sur les aspects relatifs à la fouille de données, soulignant l'apport de la combinatoire au travail amont (algorithmique des graphes, calcul de centralités, filtrage, clustering). Nous regarderons aussi certaines questions liés au dessin de graphes, au plongement de données multi-dimensionnelles, à la navigation de hiérarchies de graphes.

Le jeudi 8 février 2007 : Michel Adiba (Ministère) et Rémi Vigne (Innovalis Aquitaine)

Le 7ème PCRD: quelles opportunités pour les Technologies de l'Information et de la Communication (TIC) ?

Le jeudi 25 janvier 2007 : Patrick Lambert (Université de Savoie)

Quelques utilisations de la couleur en analyse d'image

La présentation comportera deux parties assez différentes mais qui ont comme dénominateur commun le souci d'aborder le problème du traitement et de l'exploitation de la couleur en analyse des images.
La première partie portera sur la caractérisation de séquences d'images. On cherchera plus particulièrement à montrer comment la couleur peut se révéler un attribut très utile et très discriminant. Deux situations seront envisagées : la détection de transitions lentes d'une part, et la description symbolique floue de la distribution des couleurs dans un film d'animation.
La deuxième partie, correspondant à des travaux plus anciens, abordera le problème du filtrage des images couleurs, et plus particulièrement le filtrage non linéaire basé sur l'ordre. Les images couleurs sont des images multi-composantes, et le filtrage d'ordre de données multi-composantes n'est pas aussi simple et naturel qu'en imagerie mono-composante car il demande la définition d'un ordre vectoriel. Nous verrons quelques solutions à ce problème et leurs applications dans le cas du filtrage médian et de la morphologique mathématique.

Le jeudi 18 janvier 2007 : Xavier Viennot (LaBRI)

Titre : Présentation du projet ANR MARS

Le titre officiel du projet est "Physique combinatoire: autour des Matrices à Signes Alternants et la conjecture de Razumov-Stroganov". D'où l'acronyme MARS. C'est un projet interdisciplinaire recouvrant trois domaines principaux: informatique, combinatoire et physique.
Le but principal est de résoudre la célèbre (en combinatoire et en physique) conjecture de Razumov et Stroganov (RS) relative à certains entiers apparaissant dans un modèle de physique sur des chaînes de spins quantiques (modèle XXZ d'Heisenberg). Ces entiers apparaissent dans un tout autre domaine: les objets combinatoires appelés matrices à signes alternant (MSA), introduits il y a 25 ans, et qui ont fait couler beaucoup d'encre en combinatoire. Une matrice à signe alternant est une matrice carrée, dont les entrées sont 0,1 ou -1, telle que la somme des entrées dans chaque ligne et chaque colonne est égale à 1, et telle que les signes alternent dans les lignes et les colonnes. Les premiers nombres de la suite dénombrant ces matrices selon leur taille sont; 1, 2, 7, 42, 429, ... Depuis le début de ce millénaire, de gros efforts ont été déployés par de nombreux physiciens pour comprendre pourquoi ces entiers apparaissent dans le contexte des chaînes de spins quantiques.
D'une autre manière tout à fait surprenante, ces mêmes entiers apparaissent dans un autre domaine combinatoire: les partitions planes. Imaginez une pièce cubique de 2n = 10 mètres sur chacun de ses cotés et empiler des cubes de 1 mètre de coté dans un coin de la pièce, bien serrés, et sans que la montagne formée de ces cubes n'ait de pics. Imaginez toutes les symétries que vous pouvez faire avec ce genre d'objets (maintenant il faut que les cubes soient bien collés!). Les empilements de votre pièce ayant toutes les symétries imaginables (PPTSAC) sont au nombre de 429, le nombre de MSA ayant n = 5 lignes et 5 colonnes !. Bien entendu, cette coïncidence miraculeuse est vraie pour toute taille n. Depuis 20 ans, malgré de nombreux efforts des combinatoristes, pas la moindre correspondance (bijection) entre les MSA et les PPTSAC n'a été trouvée.
J'esquisserai dans ce séminaire les différentes facettes déjà connues du sujet et touchant des thèmes fort variés. Les probabilités: chaînes de Markov, structures discrètes aléatoires; la combinatoire algébrique: fonctions symétriques, permutoèdre (groupe de permutation) et associaèdre (les arbres binaires). Enfin, des pistes possibles très "labrisiennes": réécritures, algorithmique sur une grille, algorithmique des structures de données, avec une utilisation expérimentale de la visualisation sur ordinateur de structures combinatoires complexes.

Le jeudi 14 décembre 2006 : Yves Leroyer (CPMOH, Universite Bordeaux I)

Titre : Quelques aspects de l'information quantique

Après un exposé des bases conceptuelles de l'information quantique je présenterai
- un exemple d'algorithme quantique « efficace » : l'algorithme de Grover de recherche d'information dans une base de donnée non structurée ;
- un exemple de réalisation expérimentale de qubit.
Je conclurai en évoquant d'autres champs d'application (cryptographie quantique) et en présentant les limitations et les perspectives de l'information quantique.

Le jeudi 7 décembre 2006 : Nathalie Furmento et Gerald Point : Deux autres exposés sur les travaux d'ingénieurs de recherche du LaBRI

Le jeudi 30 novembre 2006 : Patrick Henry et Boris Masencal : Deux exposés sur les travaux d'ingénieurs de recherche du LaBRI

Le jeudi 16 novembre 2006 : Annegret Wagler (Otto-von-Guericke-University Magdeburg)

Titre : Beyond Perfection: On Characterizations and Superclasses

Perfect graphs constitute a well-studied graph class with a rich structure. This is reflected by characterizations of perfect graphs with respect to such different concepts as coloring properties, the integrality of certain polyhedra, or splitting graph entropies. In addition, several otherwise NP-hard combinatorial optimization problems can be solved for perfect graphs in polynomial time.
Thus, perfect graphs play a particular role in such various mathematical disciplines as graph theory, combinatorial optimization, integer and semidefinite programming, polyhedral and convexity theory, and even information theory, thereby linking those disciplines in a truly unexpected way. We present some of these concepts and their relations.
Unfortunately, most graphs are imperfect and do not have such nice properties. It is, therefore, natural to ask which graphs are close to perfection in some sense and how to measure that. A canonical way is to relax several concepts which characterize perfect graphs and to investigate resulting superclasses of perfect graphs. In this talk, we consider more general coloring concepts and classes of $\chi$-bound graphs, the stable set polytope and its canonical LP-relaxation, and different levels of the additivity for the graph entropy.
As a common way to measure perfection w.r.t. all these concepts we present the imperfection ratio: it reflects the quality of coloring properties, the difference between the stable set polytope and its LP-relaxation, as well as additivity for the graph entropy, thereby linking the different concepts of relaxing perfectness.

Le jeudi 9 novembre 2006 : Erich Graedel (Aachen ?)

Titre : How to win infinite games?

Many tasks in computer science can be modelled by graph games, in which two or more players take turns (or not) to move a token through a directed graph, tracing out a possibly infinite path. The objectives of players are given by properties of infinite paths.
The fundamental mathematical questions on such games concern the existence of optimal strategies for the players, the complexity and structural properties of such strategies, and their realisation by efficient algorithms. Which games are determined, in the sense that from each position, one of the players has a winning strategy? How to compute winning positions and optimal strategies? How much knowledge on the past of a play is necessary to determine an optimal next action? Which games are determined by memoryless strategies? And so on.
These questions are not only mathematically interesting, but translate into questions of design and verification of computing systems. The answers strongly depend on the particular form of a graph game, such as the number of players, the form of interaction between players (turn based or concurrent), the information that is available to the players, the structure of the game graph, and the type of the objectives or winning conditions of the players. A well-understood case are two-player, zero-sum games with perfect information and omega-regular objectives.
In the talk, an overview will be given about fundamental concepts and results in the algorithmic theory of infinite games, about connections to other fields such as logic, automata theory, and verification, and about open problems and new challenges.

Le jeudi 26 octobre 2006 : Pierre Casteran (LaBRI)

Transparents

Titre : Systèmes d'aide à la démonstration

Un système d'aide à la démonstration (ou "assistant de preuve'' ) est un logiciel permettant l'écriture et la vérification de preuves mathématiques, soit sur des théorèmes au sens usuel des mathématiques, soit sur des assertions relatives à l'exécution de programmes informatiques. Parmi ces logiciels, citons ACL2, Coq, HOL, Isabelle, Mizar, etc.
Dans cet exposé, nous aborderons les thèmes suivants :
- domaines d'application,
- relation entre calcul et inférence,
- théorèmes, programmes, programmes certifiés,
- degré de [non-]automaticité,
- fiabilité et lisibilité des résultats,
Les exemples seront majoritairement extraits d'un travail en cours sur les problèmes de terminaison (avec le système Coq).
Quelques liens :
Article Wikipedia sur les assistants de preuve
http://fr.wikipedia.org/wiki/Assistant_de_preuve
Site du projet Flyspeck (preuve de la conjecture de Kepler)
http://www.math.pitt.edu/~thales/flyspeck/index.html
Site du système Coq:
http://coq.inria.fr/coq-eng.html

Le jeudi 19 octobre 2006 : Bruno Courcelle et Frédéric Mazoit (LaBRI)

Titre : Décomposition de graphes

Il s'agira d'une présentation tres générale des grands types de décomposition de graphes et de leurs motivations (algorithmique, théorie des graphes, logique, grammaires de graphes). Le cas des décompositions arborescentes sera plus particulièrement développé.
Cette présentation sera une introduction à une série d'exposé sur le thème "Petite Ecole sur les décompositions de graphes".

Le jeudi 28 septembre 2006 : Xavier Viennot (LaBRI)

Titre : Présentation de la petite école combinatoire sur les polynômes orthogonaux

La "petite école de combinatoire" a une longue tradition au LaBRI. La prochaine version, débutant en Octobre, a comme sujet la théorie combinatoire des polynômes orthogonaux, ses extensions, ainsi que ses interactions et applications. Il m'a semblé utile de la présenter à un public élargi, le thème débordant largement les préoccupations de l'équipe combinatoire.
La théorie classique des polynômes orthogonaux était considérée comme une branche de l'analyse. Polynômes de Tchebychef ou polynômes d'Hermite sont peut être pour vous de vieux souvenirs ? Depuis environ 25 ans, cette théorie a été "combinatorisée" et tout un monde nouveau s'est ouvert, en relation avec l'informatique, les probabilités et la physique. Des objets combinatoires très classiques comme les permutations ou les chemins de Dyck (visualisant les mots bien parenthésés) sont à la base de cette théorie combinatoire et permettent d'interpréter aussi bien les coefficients de classes particulières de polynômes orthogonaux, que ce que l'on appelle leur moments, définissant cette notion d'orthogonalité. Cette théorie est équivalente à celle des développements en fractions continues.
Les interactions et les applications sont nombreuses: par exemple en informatique avec le calcul du coût moyen d'une structure de donnée intégré sur une séquence aléatoire d'opérations primitives (théorie de Flajolet, Françon et Vuillemin), en théorie des probabilités avec les processus de vie et de mort de Karlin et McGregor, ou encore en physique statistique avec les modèles de particules "sauteuses" asymétriques avec exclusion mutuelle. Des extensions de la théorie vont vers la théorie des approximants de Padé (approximer une série ou une fonction par une série rationnelle) ou encore la théorie du contrôle et l'automatique non linéaire.

Le jeudi 6 juillet 2006 : Wolfgang Heidrich (UBC : canada)

(ndlr : dans le cadre des journees iparla)

Titre : "High Dynamic Range Display Technology for Perceptually Realistic Rendering "

In this talk I will present work on several high intensity, high contrast display technologies developed at the University of British Columbia over the past few years. I will discuss software and hardware of novel high dynamic range displays, as well as the implications for intensity perception and visual adaptation.

Le jeudi 15 juin 2006 : David Lubicz (Celar)

Titre : "Generic model for groups with pairing and bilinear Diffie-Hellman problems"

Les premieres 15 minutes de l'expose seront consacrees a expliquer ce qu'est le probleme du logarithme discret en l'illustrant sans doute par l'exemple du groupe des points d'une courbe elliptique.
Groups with pairing are used in cryptography since 2001 for new applications. The security of schemes based upon such groups rely on some hypotheses related to discrete logarithm. As these hypothese are not proved, one would like to have some positive security argument for these problems. For this, we provide a precise definition for a generic family of groups and we introduce the generic family of groups with pairing. In this framework, we then prove the intractability of the bilinear Diffie-Hellman problem.
Commentaire naif du secretaire qui n'engage que lui: Cet expose me semble pouvoir interesser les informaticiens par au moins deux de ses aspects: une definition de fonctions "difficilement reversible" utilisees en cryptographie et une analyse d'algorithme probabiliste apparaissant dans les preuves.

Le jeudi 8 juin 2006 : Charles Consel (LaBRI)

Titre : "Une approche langage pour la création de services de communication -- application à la téléphonie"

Une présentation générale des activités du groupe Phoenix accompagnera cet exposé dont voici le résumé :
Telephony is evolving at a frantic pace, critically relying on the development of services to offer a host of new functionalities. However, programming Internet telephony services requires an intimate knowledge of a variety of protocols and technologies, which can be a challenge for many programmers. Furthermore, because telephony is a resource heavily relied on, programmability of telephony platforms should not compromise their robustness. This talk presents an approach to creating telephony services that builds on programming language technology (i.e., language design and implementation, language semantics, and program analysis).We have developed a language, named Session Processing Language (SPL), that offers domain-specific constructs, abstracting over the intricacies of the underlying technologies. By design, SPL guarantees critical properties that cannot be verified in general-purpose languages. SPL relies on a Service Logic Execution Environment for SIP (SIP-SLEE) that introduces a design framework for service development based around the notion of session. SPL and SIP-SLEE have been implemented and they are now being used to develop and deploy real services, demonstrating the practical benefits of our approach. [This is joint work with L. Burgy, F. Latry, J. Lawall, N. Palix, L. Reveillere]

Le jeudi 1er juin 2006 : Andrzej Pelc, (Université du Québec en Outaouais)

Titre : Jeux de recherche avec mensonges (Searching games with lies)

(Le résumé est en anglais mais l'exposé sera en français) We consider the problem of searching with errors in the framework of two-person games. The Responder (Pinocchio) thinks of an object in the search space, and the Questioner has to find it by asking = questions to which Pinocchio provides answers, some of which are erroneous. We give a taxonomy of such games, depending on the type of questions allowed, on the degree of interactivity between the players, and on the imposed limitations on errors. We survey the existing results concerning such games, concentrating on the issue of optimizing the Questioner's querying strategy, and pointing out open problems. We show the relations between searching games with errors and error-correcting codes. Finally, we discuss other search and computation problems with faulty feedback, which are related to searching with errors.

2 mars 2006 : Cyril Gavoille (LaBRI)

Titre : "Structures de données distribuées : un survol."


Résumé : Il s'agit de donner un aperçu général sur le domaine des structures de données dans le cadre du calcul distribué, mais pas seulement. En insistant sur les motivations, un large panel de résultats très récents sera présenté. Cet exposé s'adresse à tous. Quelques mots-clés: calcul de distances, plus proche ancêtre commun et les fichiers XML, représentations implicite et codage des graphes.

19 Janvier 2006 : Francisco Garcia Ugalde

"Les représentations hiérarchiques basées sur une décomposition en ondelettes et son utilisation au codage et à la segmentation des images"


Résumé: Dans ce séminaire il sera présenté l'utilisation du formalisme des représentations hiérarchiques baséees sur une décomposition des images numériques par des ondelettes. L'utilité de ces représentations dans le cadre du codage et son intérêt pour résoudre le problème de la segmentation sera également souligné.