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) ?
- 14h05 Le 7ème PCRD et les TIC
- - Bilan synthétique des résultats français du 6ème PCRD en TIC
- - Les appels à propositions en TIC : programme de travail 2007-2008
- - Le Conseil Européen de la Recherche : Agence de financement de la recherche fondamentale
- - Le dispositif national pour la préparation des projets européens
un exposé de Michel ADIBA, Ministère de la Recherche,
Représentant au comité de programme «Technologies de l'information et de la communication » du 7ème PCRD
-
15h00 Les Actions Marie Curie / Le dispositif régional d'appui aux porteurs de projets
un exposé de Rémi VIGNES, Innovalis Aquitaine / Bureau Europe
-
15h20 Discussions - questions / réponses
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é.