Liste des événements uniques du groupe Séminaire du LaBRI


2015-04-03Dessin de graphes planaires sur une grille
09:30-10:15
Amphithéâtre (050)
 Plus d'infos  


2015-04-03Coding loopless maps
10:45-11:45
Amphithéâtre (050)
 Plus d'infos  


2015-04-03Meanders
14:00-15:00
Amphithéâtre (050)
 Plus d'infos  


2015-04-03The labyrinth of Discrete Mathematics: a challenge for the XXI century?
15:30-16:30
178
 Plus d'infos  


2014-10-02Énumération asymptotique d'automates finis
10:00-11:00
Amphithéâtre du LaBRI (050)
Cet exposé portera sur l'énumération d'automates finis. Les automates peuvent être vus comme des graphes orientés dont les arêtes sont étiquetées sur un alphabet fini et dont deux sous-ensembles de sommets sont distingués (l'ensemble respectivement des états initiaux et des états terminaux). Les automates (resp. minimaux) constituent une représentation (resp. canonique) des langages rationnels et de ce fait jouent un rôle important en informatique.
Nous présenterons des résultats concernant l'énumération des automates déterministes et accessibles, i. e. dans lesquels tout état peut-être atteint par un chemin partant de l'unique état initial. Nous déterminerons ensuite précisément la proportion asymptotique d'automates minimaux parmi les automates déterministes accessibles et complets. Ces résultats ont des conséquences en terme de complexité en moyenne d'algorithmes.
Toutes ces estimations peuvent être obtenues grâce à une interprétation combinatoire des propriétés structurelles des automates et à des bijections qui permettent de se ramener à l'étude combinatoire de tableaux particuliers.
Nous conclurons en présentant quelques problèmes ouverts.
Cet exposé s'appuie sur une série de travaux communs avec Julien David, Cyril Nicaud et Andrea Sportiello.
 Plus d'infos  


2014-10-02Variations algorithmiques sur les équations différentielles linéaires
11:00-12:00
Amphithéâtre du LaBRI (050)
Depuis une vingtaine d'années, le calcul formel a beaucoup progressé dans l'algorithmisation des mathématiques. De nombreuses suites et fonctions spéciales utiles en mathématiques appliquées et en combinatoire sont ainsi devenues manipulables efficacement et de manière fiable. Nous montrerons quelques idées simples et fécondes qui ont mené à un ensemble de progrès récents dans ce domaine.
 Plus d'infos  


2014-10-02Arbres et cartes combinatoires : de l'énumération au codage compact
14:00-15:00
Amphithéâtre du LaBRI (050)
Depuis des années les belles propriétés énumératives des cartes planaires passionnent des combinatoristes de Bordeaux et d'ailleurs. Je raconterai une (petite) partie de cette histoire et en particulier comment le fait de comprendre bijectivement une jolie formule peut conduire à des algorithmes de codage compact.
 Plus d'infos  


2014-10-02Cérémonie de remise de la médaille d'argent du CNRS
15:15-19:00
Amphithéâtre du LaBRI (050)
15h15-15h25 Pascal Weil, Directeur du Laboratoire bordelais de recherche en informatique (LaBRI)
15h25-15h55 Robert Cori, Professeur émérite à l’université de Bordeaux : « Combinatoire à la bordelaise »
15h55-16h05 Jean-François Jaulent, Directeur de l’Institut de mathématiques de Bordeaux (IMB)
16h05-16h15 François Cansell, Directeur de Bordeaux INP
16h15-16h25 Manuel Tunon de Lara, Président de l’université de Bordeaux
16h25-16h35 Michel Bidoit, Directeur de l’Institut des sciences de l’information et de leurs interactions (INS2I, CNRS)
16h35-16h45 Christoph Sorger, Directeur de l’Institut national des sciences mathématiques et de leurs interactions (INSMI, CNRS)
16h45-17h00 Pause
17h00-17h50 Mireille Bousquet-Mélou, Directrice de recherche CNRS au LaBRI
17h50-19h00 Cocktail
 Plus d'infos  


2013-04-25[Sem-LaBRI] Tour d'horizon de divers problèmes d'optimisation dans les réseaux
13:30-14:30
Amphi du LaBRI
Cet exposé présente trois problèmes d'optimisation dans les réseaux. Le premier vise à concevoir l'ossature virtuelle (virtual backbone) d'un réseau de télécommunication sans fil. Il est formulé comme un problème d'arbre dominant de poids minimum. Le second problème vise à maximiser la durée de vie d'un réseau de capteurs sans fil directionnels. La génération de colonnes sert de base à la résolution, et utilise un algorithme génétique pour accélérer la convergence. Enfin le dernier problème traite de la communication multicast dans les réseaux de fibre optique, et est représenté comme un problème d'arbre couvrant avec contrainte sur les degrés.
 Plus d'infos  


2013-04-11[Sem-LaBRI] Intégrer la reconnaissance des expressions figées dans des analyseurs linguistiques
13:30-14:30
Amphi du LaBRI
L'analyse linguistique automatique est confrontée à deux problèmes majeurs inhérents aux langues: l'ambiguité et le figement. Alors que la littérature regorge d'analyseurs tentant de traiter le cas de l'ambiguité, on constate que très peu d'études s'attaquent à l'intégration de la reconnaissance d'expressions figées qui constituent des unités sémantiques minimales (ex. eau de vie, perdre la boule). Or, leur repérage est crucial pour des applications comme la traduction automatique.
Dans cet exposé, nous nous intéressons à l'intégration d'expressions figées contigues dans des analyseurs syntaxiques de textes. Nous abordons ce problème avec une approche hybride combinant modèles probabilistes et ressources linguistiques symboliques. Nous montrerons qu'une telle approche permet non seulement d'améliorer le repérage des expressions figées, mais aussi la qualité globale d'analyse syntaxique.
Les travaux présentés dans cet exposé ont été réalisés en collaboration avec Olivier Blanc, Joseph Le Roux, Anthony Sigogne, Isabelle Tellier et Patrick Watrin.
 Plus d'infos  


2013-04-04[Sem-LaBRI] La tuile : vers un modèle pour la programmation structurée de l’espace et du temps
13:30-14:30
Amphi du LaBRI
Quel rapport peut-il y avoir entre les structures musicales, les systèmes interactifs temps-réel et la théorie des langages d’arbres ou de mots ? La notion de tuile conduit

- en théorie des langages, à une extension de la notion de reconnaissabilité: les langages (co-)reconnaissables par pré-morphismes, par automates de tuiles ou par automates déambulants

- en théorie de la programmation, à un nouveau paradigme : la programmation par tuilage, qui permet de concilier, dans un même langage, la programmation parallèle synchrone, et la programmation réactive, événementielle

- en informatique musicale, à un outil de manipulation de flux audio particulièrement souple : la libTuile, qui pourrait à terme concurrencer les logiciels modernes de mixage interactif et temps-réel.

Travaux en cours avec Florent Berthaut, Myriam DeSainte-Catherine, Anne Dicky, Etienne Dubourg, Yann Orlarey et Sylvain Salvati.
 Plus d'infos  


2013-03-21[Sem-LaBRI] Propriétés combinatoires et de robustesse de modèles discrets de réseaux biologiques
13:30-15:00
Amphi du LaBRI
Les réseaux d'automates sont des objets mathématiques mettant en jeu des entités (dites automates) qui interagissent les unes avec les autres au cours d'un temps discret. En voyant ces réseaux comme des modèles potentiels de systèmes d'interactions biologiques, l'idée générale de cet exposé est de montrer que l'informatique fondamentale permet d'accroître la connaissance des lois générales qui régissent le vivant. Plus précisément, nous utiliserons les réseaux d'automates booléens comme modèles de réseaux de régulation génétique. Dans ce cadre, nous focaliserons notre attention sur deux thèmes, développés en collaboration avec Jacques Demongeot (IMAG, UJF), Mathilde Noual (I3S, UNS) et Damien Regnault (IBISC, UEVE) :
- la combinatoire comportementale des cycles, objets dont on connaît l'importance sur la dynamique des réseaux depuis les travaux de René Thomas (1981) et de François Robert (1986) et
- la robustesse structurelle des réseaux, au sens de René Thom (1972), que nous aborderons au travers de l'influence des modes de mise à jour, et qui nous mènera à l'étude d'une famille particulière de réseaux, les réseaux xor circulants.
 Plus d'infos  


2013-03-14[Sem-LaBRI et GT MABioVis] Measuring truth in visualizations
11:00-12:00
salle 178
It’s well known that visualizations can lie, that is, distort the true relationship between the variables and records being represented visually. Example precursors of this topic were Huff and Geis How to Lie with Statistics, Tufte with indirectly measuring the synthesis of the visualization's chart noise and ink metrics, and Bertini, Ward, and others with visualization quality metrics. The more direct question we would like to answer is how to tell if a visualization is accurately representing its data. Or more precisely how can we measure the truth in a visualization.
In this presentation we will describe three different approaches to measuring the truth in visualizations. First we will define what we mean by truth. We then will describe Weave, an open source analysis and visualization environment [iWeave.org] and our architecture for computing descriptions of visualizations developed for ADA compliance within Weave. Finally we will give preliminary examples of the measures.
This research work has broad implications and applications to applied visualization.
 Plus d'infos  


2013-03-07[Sem-LaBRI] Next Generation Radiotherapies
13:30-14:30
Amphi du LaBRI
In this talk, we will address three kinds of "Next Generation Radiotherapies" and present some algorithmic aspects and results. Radiation therapy is one of the commonly used cancer therapies. The radiation treatment poses a tuning problem: the radiation needs to be effective enough to destroy the tumor, but it should maintain the functionality of the organs close to the tumor (organs at risk). Towards this goal, the design of radiation treatment has to be customized for each patient. We will focus on a) Intensity Modulated Radiation Therapy using Multi-Leaf Collimators, b) Curie-therapy and c) Proton therapy and give both some open questions and recently achieved algorithmic results.
 Plus d'infos  


2013-02-21[Sem-LaBRI] Towards a new era of SAT Solvers
13:30-14:30
Amphi du LaBRI
Since the first complete SAT solvers (DPLL-62, based on classical backtrack-search), major breakthroughs were observed in the practical – and theoretical – study of SAT. Nowadays, SAT solvers can be used in many critical systems, from very hard problems (Formal Verification, Biology, Cryptology) with potentially long runs, to more reactive applications (were a SAT solver can be called many times per second). In this talk, we will review the progresses made since the first breakthrough of 2001, with the introduction of CDCL solvers, called “modern solvers”. We will show how the field is slowly moving from a “complete” vision of Solvers to a more “uncomplete” one. We will end the talk by some open questions on the future of SAT Solvers, and the recent trends in "incremental SAT Solving", where SAT solvers are called thousand times for each run.
 Plus d'infos  


2013-02-07[Sem-LaBRI] Optimizing Energy and Bandwidth in Mobile Streaming Systems
13:30-14:30
Amphi du LaBRI
Dramatic recent improvements in the computing power, memory capacity, screen size, and video quality of mobile devices have resulted in substantial demand for mobile multimedia services. However, these improvements have also resulted in increased demands for limited and expensive wireless bandwidth and for the energy of mobile devices with limited battery capacities. In this talk, I will consider the problem of multicasting multiple video streams from a wireless base station to many mobile receivers over a common wireless channel. I will present a sequence of increasingly sophisticated approaches to the problem of optimizing both the bandwidth utilization of the wireless channel and the energy usage of the mobile receivers.
 Plus d'infos  


2012-12-06[Sem-LaBRI] Promoting systems biology research through intelligent information mining of omic datasets
16:00-17:00
salle 178
Exponentially thriving biological data sets present a challenge and an opportunity for researchers to contribute to the understanding of the genetic basis of phenotypes. Due to breakthroughs in microarray and recently in sequencing technologies, it is more than ever possible, to simultaneously monitor the expressions of an unprecedented size of molecular actors, thus providing the ground and the promise to biomedical researchers for a successful, clinical, system-wide interpretation of disease related tissue data that can be analyzed in this way. This technology could be a landmark in personalized medicine, paving the way for innovative methods of data handling and storage for clinical purposes in electronic health records. Merging experimental data with disparate preexisting data (literature, provenance data, clinical records, etc.) in these analytic pipelines strengthens the diagnostic value of the disease signatures derived, in order to be considered robust, early biomarkers of disease. High dimensionality and biological variability is ubiquitously present. The efficient manipulation of this complexity, through the application or development, of innovative high-performance computing approaches, represents a critical determinant.
The presentation will showcase the integration of various software products, in a unified translational workflow, able to cope with versatile, high-volume exploratory tasks, and at the same time provide a reliable systemic interpretation for the biological mechanism studied. In this way, a powerful translational backbone is proposed which connects the wet-lab part with the semantic relevant information for the biological problem interrogated, as rescued in molecular databases, controlled ontological vocabularies or the literature. This encompasses, signal-quality estimators for feature evaluation, robust, resampling-based statistical measures at either the single (probe) or group (pathways, expression-based molecular sets) level, graph theoretic criteria and exploitation of literature-gleaned information. Altogether this represents an efficient and innovative, either in terms of speed of analysis, and practical biological value, approach, as it forms a composite framework that yields results combining ideally both individual as well as group quality measures deriving an insightful comprehension of the problem studied.
 Plus d'infos  


2012-11-15Causal graph dynamics
13:30-14:30
Amphi du LaBRI
We extend the theory of Cellular Automata to arbitrary, time-varying graphs. In other words we formalize, and prove theorems about, the intuitive idea of a labelled graph which evolves in time under the natural constraint that information can only ever be transmitted at a bounded speed, with respect to the distance given by the graph. The notion of translation-invariance is also generalized. The definition we provide for these `causal graph dynamics' is simple and axiomatic. The theorems we provide also show that it is robust. For instance, causal graph dynamics are stable under composition and under restriction to radius one. In the finite case some fundamental facts of Cellular Automata theory carry through: causal graph dynamics admit a characterization as continuous functions, and they are stable under inversion. The provided examples suggest a wide range of applications of this mathematical object, from complex systems science to theoretical physics.

This is a joint work with Pablo Arrighi
 Plus d'infos  


2012-09-13Permutation Patterns
13:30-14:30
Amphi du LaBRI
Patterns in permutations are subsequences considered only according to
their relative order. For instance 231 occurs as a pattern in 14352 in
two ways: as 452 and as 352. The study of collections of permutations
defined by forbidding certain patterns exposes a great deal of
structure, and interesting enumerative problems. I will introduce this
field of study in a "hands on" way, making use of a software suite
called PermLab which facilitates the graphical and numerical
exploration of such collections.
 Plus d'infos  


2012-04-19Routage géographique dans les réseaux véhiculaires ad hoc en environnement urbain
14:00-15:00
Amphi du LaBRI
Les réseaux véhiculaires sont passés du stade de simple curiosité pour revêtir aujourd'hui un intérêt certain aussi bien du point de vue de l'industrie automobile que des opérateurs de réseaux et de services. Ces réseaux sont en effet une classe émergente de réseaux sans fil permettant des échanges de données entre véhicules ou encore entre véhicules et infrastructure. Ils suscitent un intérêt certain de la communauté de recherche et des industriels, aussi bien en Europe qu’au Japon et en Amérique du Nord, dans le but de fournir de nouvelles technologies capables d'améliorer la sécurité et l'efficacité des transports routiers.
Dans le cadre de ce séminaire, nous nous intéressons plus particulièrement aux communications inter-véhicules dans un environnement urbain. Notre objectif principal est de présenter un nouveau protocole de routage, qui s'adapte efficacement aux caractéristiques des réseaux véhiculaires (forte mobilités des n½uds, fragmentation fréquente du réseau, connectivite intermittente, etc.). Notre démarche consiste à prendre en compte un paramètre clé qui influence le bon fonctionnement du réseau véhiculaire ad hoc, à savoir la densité du réseau. Dans un premier temps, nous discuterons donc d’un mécanisme distribué qui permet de caractériser de manière fine la densité de trafic d'un tronçon de route entre deux intersections, en fournissant une distribution spatiale des véhicules mobiles sur la voie de circulation. Ensuite, nous proposons un nouveau protocole de routage géographique lequel tire partie des caractéristiques des voies urbaines et qui intègre le mécanisme d'estimation de densité de trafic pour le routage des paquets. Les bases conceptuelles de ce nouveau protocole de routage et du mécanisme d’estimation du trafic associé ainsi que leurs évaluations seront détaillés tout au long de ce séminaire.
Mots-clés : réseaux véhiculaires ad hoc, environnement urbain, communications basées sur les intersections, routage multi-sauts, densité du trafic routier.
 Plus d'infos  


2012-04-12Musique computationnelle : des arabesques de Debussy aux monoides quasi-inversifs de Lawson
14:00-15:00
Amphi du LaBRI
Au XVIIIème siècle, au dire d'Amadeus lui-même - dans le film éponyme de Milos Forman - l'opéra est le seul moyen de faire parler plusieurs personnes en même temps tout en garantissant qu'elles se comprennent. Aujourd'hui, les réseaux font cela quotidiennement.
La musique, activité empirique quasi-scientifique qui nous vient du fond des âges, recèle-t-elle encore quelques mystères à découvrir qui seraient applicables à l'informatique moderne ?
En parcourant les pièces musicales telles les arabesques de Debussy on découvre des mécanismes de tuilages typique de la théorie (très moderne) des semigroupes inversifs. Par rebond, on en déduit des opérateurs originaux de combinaison et de modification de motifs musicaux. Et si on pousse l'exploration, on a soudainement envie de revisiter complètement la théorie algébrique des langages...
Mozart ne nous aurait-il pas tout dit ?
 Plus d'infos  


2012-04-05Extended formulations for the design of approximation algorithms : an example in inventory control
14:00-15:00
Amphi du LaBRI
Linear programming plays a central role in the design of efficient approximation algorithms. In particular, many approximation algorithms builds on the 'natural' linear programming formulation of the problem and apply some rounding techniques and/or primal-dual schemes. In this talk, we show how extended formulations can help in the design of approximation algorithms. We illustrate those findings on the one-warehouse multi-retailer problem, a standard in inventory control.
 Plus d'infos  


2012-03-29Algorithmiques et évaluation de performance dans les réseaux ad hoc
14:00-15:00
Amphi du LaBRI
Les travaux de recherches présentés lors de ce séminaire portent sur la proposition d’algorithmes dans les réseaux ad hoc et l’évaluation de leurs performances. 3 types de réseaux sont abordés : les réseaux de capteurs, les réseaux meshs et les réseaux de véhicules. Les problématiques associées sont différentes d’un réseau à l’autre : problème de diffusions dans les réseaux de capteurs à grande échelle, mobilité et capacité dans les réseaux meshs, et dissémination des messages d’alertes dans les réseaux de véhicules. Les contributions sont algorithmiques, validés au travers de modèle théorique, de simulations et parfois d’expérimentations.
 Plus d'infos  


2012-03-15Power circuits and arithmetic for highly compressed integers
14:00-15:00
Amphi du LaBRI
Power circuits represent integers using directed acyclic graphs having edge and node labels from {-1,0,+1}. It generalizes the ``compact representation" of integers as sums over b_k 2^k where the b_k are not bits, but values in {-1,0,+1}.
Power circuits of linear size O(n) may represent numbers involving tower values t(n) where t(0) = 1 and t(n) = 2^{t(n)}. Thus, the compression rate on some huge integers is extremely high. The data structure has been introduced by Myasnikov, Ushakov and Won in order to show that the word problem in the famous one-relator Baumslag group (a.k.a. Baumslag-Gersten group) can be solved in polynomial time.
In my lecture, I report on a joint work with Laun and Ushakov which was presented this year at the STACS conference in Paris. I show that certain arithmetical operations can be performed efficiently, and I present an efficient reduction algorithm which is needed to compare values encoded in power circuits.
Using these techniques we were able to improve the time bound for solving the word problem in the Baumslag group from O(n7) to cubic time, which we believe to be optimal. We also showed that the word problem in the Higman group H_4 can be solved in polynomial time.
The focus of the talk is however more on power circuits than on the applications in algorithmic group theory.
 Plus d'infos  


2012-03-08Concepts et méthodologie pour une description sémiotique de la structure musicale
14:00-15:00
Amphi du LaBRI
La structure musicale d’un morceau de musique est un concept auquel il est fréquemment fait référence en musicologie et en informatique musicale, mais pour lequel il n’existe pas de définition communément admise. Modéliser la structure musicale des morceaux de musique est pourtant un objectif essentiel, que ce soit pour améliorer les traitements automatiques des contenus ou pour proposer des interfaces de navigation intelligente dans les données musicales.
Des travaux récemment conduits à l'IRISA ont permis de développer des concepts méthodologiques visant à caractériser l'organisation générale d'un morceau de musique par sa "structure sémiotique latente". L'approche est fondée sur des concepts issus de la sémiologie et de la théorie des communications. La méthodologie d'analyse structurelle proposée permet de caractériser les principaux éléments de la structure musicale d'un morceau indépendamment de sa substance spécifique et sans faire appel à des connaissances musicologiques expertes.
La méthode proposée est plus spécifiquement destinée à la modélisation de morceaux de musique dite "pop", mais elle s'étend potentiellement à une grande variété de genre musicaux. L'exposé illustrera les principaux concepts-clefs sur la base d'exemples musicaux mais aussi sous forme métaphorique et visuelle.
 Plus d'infos  


2012-02-23Une introduction aux interfaces cerveau-ordinateur basées sur l'électroencéphalographie
14:00-15:00
Amphi du LaBRI
Les interfaces cerveau-ordinateur (ou BCI, terme venant de l'anglais Brain-Computer Interface) sont des systèmes de communication permettant à un utilisateur d'envoyer des commandes à un ordinateur en utilisant uniquement son activité cérébrale, celle-ci étant généralement mesurée par électroencéphalographie (EEG). Dans cette présentation, nous verrons tout d'abord ce que sont et à quoi servent les BCI. Ensuite nous nous intéressons à comment celles-ci marchent et plus précisément comment traiter et classifier les signaux EEG afin d'identifier l'état mental de l'utilisateur. Nous aborderons ainsi quelques techniques d'apprentissage artificiel (machine learning) utilisées dans ce contexte.
 Plus d'infos  


2012-01-19From DNA to Jay-Z: how ideas from bioinformatics can automate finding rhymes in rap music
14:00-15:00
Amphi du LaBRI
Unlike most kinds of music, the core of rap music is found in the rhythm and rhyme of its lyrics. Different artists or subgenres will use different kinds of rhyme, which in some cases can be extremely complicated: the end of one line may rhyme with several parts of the previous line, and in some cases, rhymes may be imperfect.
Detecting these complex rhyme patterns manually is time consuming and tedious. We have designed a system for automatic rhyme annotation. Our approach is founded on several bioinformatics ideas. First, using a test corpus of known rhymes, we develop a probabilistic model of rhymed and unrhymed syllables. Then, we use that model to build a log-likelihood ratio scoring matrix for identifying what is and is not a rhyme. Finally, we create a local alignment procedure to find high-scoring lyrics segments.
Our procedure has high sensitivity and specificity in identifying true rhymes in an annotated corpus; essentially, it identifies most complex rhymes, and identifies few false rhymes. We can use it to characterize artists, and then to develop classifiers for individual artists with surprising success.
Joint work with MMath student Hussein Hirjee
 Plus d'infos  


2012-01-10Nax: a logic based upon Mendler style Iteration/Recursion Combinators
16:00-17:00
Amphi du LaBRI
We are interested in systems which are both a sound logic and a programming language. The design of such a system is quite delicate. Features that programmers deem absolutely necessary (rich data types, effects, unlimited recursion, possible non-termination) have negative effects on the soundness of a logic. To address these issues we have been experimenting with a language we call Nax. Nax is a simple functional language based upon a family of principled iteration/recursion combinators first described my Mendler in which every computation terminates. Traditional logics limit the sorts of data types definable, but place no restriction on how those data types are constructed or analyzed. Following the Mendler style, we place no restriction on what sorts of data types can be defined, or on how they can be constructed, but place strict limits on how they can be analyzed. Both approaches can form the basis of a sound logic.
Careful design of Nax has led to a language which supports many features desired by programmers, including, rich datatypes (including nested dataypes, GADTS, and higher order datatypes with negative occurrences), and an expressive type inference mechanism (even in the presence of GADTS), and traditional programing style (based upon pattern matching and the writing of defining equations) while still retaining its logical properties.
 Plus d'infos  


2011-09-29Girth and the greedy algorithm
14:00-15:00
Amphi du LaBRI
Finding an efficient algorithm to decide if a given graph or network has a certain property is often difficult or very unlikely. Thus there is some interest in graphs with the characteristic that a simple, such as the greedy, algorithm produces a set with the desired property efficiently. For example, well-covered graphs (every maximal independent set of vertices is of one size and, hence, maximum) fall into this category. Many such problems have the rather curious feature that if one knows the structure of trees in the collection, then this characterization is essentially the same even with cycles present as long as they are not too small. For instance, the well-covered graphs of girth 8 or more (i.e., with no cycles of length 7 or smaller) can be described essentially the same as well-covered trees. A similar situation arises with the problem of where to locate undesirable objects (garbage dumps, nuclear sites) so that we have no more that k in the neighbourhood of anyone. A number of problems of this type will be outlined.
 Plus d'infos  


2011-07-07[Sem-LaBRI] Analysing the evolution of social aspects of open source software ecosystems
10:00-11:00
Amphi du LaBRI
Empirical software engineering is concerned with statistical studies that aim to understand and improve certain aspects of the software development process. Many of these focus on the evolution and maintenance of evolving software projects. They rely on repository mining techniques to extract relevant data from software repositories or other data sources frequently used by software developers. We enlarge these empirical studies by exploring social software engineering, studying the developer community, including the way developers work, cooperate, communicate and share information. The underlying hypothesis is that social aspects significantly influence the way in which the software project will evolve over time. We present some preliminary results of an empirical study we are carrying out on the different types of activities of the community involved in the GNOME open source ecosystem, and we discuss suggestions for future work.
 Plus d'infos  


2011-06-23[Sem-LaBRI] Preuves automatiques d'identités
14:00-15:00
Amphi du LaBRI
Depuis une vingtaine d'années, le calcul formel a beaucoup progressé dans l'algorithmisation des mathématiques. En particulier, quelques idées simples mais fécondes permettent maintenant de calculer automatiquement des sommes ou des intégrales de fonctions très diverses. Nous montrerons ces idées ainsi que des progrès récents qui permettent encore d'élargir la classe de fonctions manipulables algorithmiquement.
 Plus d'infos  


2011-04-28[Sem-LaBRI] Faults in Linux: Ten Years Later
11:00-12:00
Amphi du LaBRI
Since the study of Chou et al. of Linux code in 2001, a guiding hypothesis of work on improving the reliability of systems code has been that drivers contain the highest rate of errors. Today, however, Linux is used in a much wider range of environments, provides a much wider range of services, and has adopted a new development and release model. What has been the impact of these changes on code quality? Are drivers still a major problem?

To answer these questions, we have transported the experiments of Chou et al. to Linux versions 2.6.0 to 2.6.33, released between late 2003 and early 2010. We find that Linux has more than doubled in size during this period, but that the number of faults per line of code has been decreasing. And, even though the drivers directory still accounts for a large part of the kernel code and contains the most faults, its fault rate is now below that of other directories, such as arch (HAL) and fs (file systems). These results can guide further development and research efforts. To enable others to continually update these results as Linux evolves, we define our experimental protocol and make our checkers and results available in a public archive.

This talk is based on work presented at ASPLOS 2011.

Joint work with Nicolas Palix, Gael Thomas, Suman Saha, Christophe Calves, and Gilles Muller
 Plus d'infos  


2011-03-31[Sem-LaBRI] Image matching and visual search: local features and geometry
14:00-15:00
Amphi du LaBRI
Methods based on local features have been very successful in visual search, especially when the objective is to identify near-identical objects or scenes under occlusion and varying viewpoint or lighting conditions. After a brief introduction to such methods, including bag-of-words models, sub-linear indexing and spatial matching, this talk focuses on recent research results related to local feature detection and the role of geometry, as well as a number of applications.

In particular, we present methods based on image gradient and distance maps that are able to detect blob-like regions of arbitrary scale and shape, and their application to image matching. We then investigate the potential of embeding the spatial matching process within the index, so that it becomes sub-linear as well. We also report on an accelerated spatial matching method for re-ranking, that allows flexible matching of multiple surfaces.

We then move to the more difficult problem of organizing large photo collections, and examine the use of sub-linear indexing in a mining process. Photos are automatically grouped wherever they depict the same scene; this structure is then exploited to increase the recall of the retrieval process. Working on community collections of geo-tagged photos depicting urban scenery, this approach is applied to automatic location and landmark recognition from a single photo. We also present our online application, VIRaL. Finally, we present our C++ template library ivl, that is used as infrastructure in our implementations.
 Plus d'infos  


2011-03-24[Sem-LaBRI] Spatial Audio Object Coding (SAOC) – an interactive perceptual coding standard
14:00-15:00
Amphi du LaBRI
Perceptual coding of high quality audio signals has become a tremendously successful technology for many multimedia applications (e.g. music on the Internet). By exploiting the characteristics of human auditory perception, perceptual audio coders have been able to achieve considerable bitrate reduction while retaining high audio quality. During the past ten years, an advanced generation of perceptual audio coders has emerged enabling the efficient representation of multi-channel audio signals by exploiting spatial auditory cues.

As the latest extension of the Spatial Audio Coding (SAC) technology, Spatial Audio Object Coding (SAOC) is especially designed for interactive and personalized audio applications providing the user control over a number of individual audio objects at playback side. With SAOC multi-object audio content is efficiently represented by a downmix signal and object related parametric side information which enables the consumer to create his/her own remix of the music (similar to the way a sound engineer performs the mixing process in a professional audio production).

Significant object level manipulations such as extreme amplification or suppression of individual audio objects has been found to be a challenging process. Because all audio objects are contained in the downmix signal, it is essential for the SAOC decoding process to completely extract and remove the particular audio object that is to be suppressed from the downmix signal. A special operation mode has been introduced to guarantee adequate coding performance even in such demanding situations.
 Plus d'infos  


2011-03-10[Sem-LaBRI] Méthodes bio-informatiques appliquées aux tumeurs cancéreuses à partir de données haut débit.
14:00-15:00
Amphi du LaBRI
La recherche sur le cancer s'appuie de plus en plus sur les techniques de biologie à grande échelle. Dans cet exposé seront présentées des méthodes d'analyse de données de puces CGH, SNP et d'expression exons.

Nous avons en collaboration avec l'institut Curie développé un algorithme de reconstruction d'arbre représentant l'évolution génomique d'une tumeur chez un patient pour lequel plusieurs échantillons tumoraux sont disponibles. Les arbres sont reconstruits à partir du nombre de copies chromosomiques observées à l'aide de puces CGH et SNP. L'algorithme de reconstruction utilise une heuristique qui vise à minimiser le nombres de pertes et gains chromosomiques nécessaires pour générer, à partir d'une cellule normale, l'ensemble des profils de tumeurs observés. Appliquée au cancer de la vessie et au cancer du sein, cette approche a permis d'établir (de confirmer) que les tumeurs primaires et récurrentes sont clonales, d'identifier les aberrations à l'origine de la tumorogénèse et plus généralement de mettre en évidence les étapes successives et les différentes voies de cancérisation.

Les puces pour étudier les variants d'épissage (puces exon) n'ont été introduites que relativement récemment et sont encore très peu exploitées. Le but du projet est d'utiliser ces puces exon dans les cancers de vessie pour 1) caractériser de nouveaux sous-groupes de tumeurs, 2) identifier de nouveaux marqueurs de la progression tumorale, 3) tenter d'identifier des gènes de fusion, 4) identifier de nouveaux gènes candidats impliqués dans la progression tumorale. Ce projet devrait aboutir à définir des expériences fonctionnelles qui feront l'objet d'autres demandes de financement. Les outils bioinformatiques et statistiques que nous serons amenés à développer seront utiles non seulement pour l'étude des cancers de vessie mais également pour l'étude d'autres cancers.
Nous utilisons des méthodes de classification spectrales et testons de nouvelles approches qui recherchent les liens de cause à effets entre variables ou facteurs et observations applicables dans des espaces de données à grandes dimensions.
 Plus d'infos  


2010-12-16Sém LaBRI. La logique non-commutative, dix ans après
14:00-15:00
Amphi LaBRI
Je propose quelques remarques méthodologiques sur la logique
non-commutative qui a été introduite par moi et Paul Ruet en
2000.

Les remarques ont été inspirées par les développements de la
logique linéaire et de la logique non-commutative, et elles
concernent : le sens dans lequel la logique non-commutative est
un raffinement de la logique linéaire, la computation dans la
logique non-commutative, la focalisation dans la logique
non-commutative, la description et l'imposition de l'ordre en
logique non-commutative, les connecteurs multiplicatifs
non-commutatifs généralisés.
 Plus d'infos  


2010-11-04Sém LaBRI. Recognition and Tracking of Human Actions in Image Sequences
14:00-15:00
Amphi LaBRI
Recent years have witnessed an unprecedented interest in the
visual analysis of human motion that is stimulated by
applications that include computer games, animated films and
entertainment, human computer interaction, surveillance/security
and multimedia retrieval. In this talk we will present an object
tracking scheme in which the predictions of multiple observations
are weighted by a probabilistic classifier that determines our
expetation that the corresponding prediction is relevant/useful
for the estimation of the state (position/scale/rotation) of the
target. This is particularly useful in the case of large motions
and occlusion, where many observations fall in areas that are far
from the target. The proposed scheme derives both generative and
discriminative tracking methods as special cases. We show the
benefits in accuracy in presence of persistent occlusions and
motion large in magnitude and briefly discuss the related
applications. Time permitting we will present our recent work in
discriminative action recognition and localisation, that is based
on a part-based implicit shape model in which local parts vote
for the location and scale of an action.
 Plus d'infos  


2010-10-21Sém LaBRI. On Plane Geometric Spanners
14:00-15:00
Amphi LaBRI
A geometric graph $G$ is a graph whose vertices are points in the
plane and whose edges are line segments weighted by the Euclidean
distance between their endpoints. In this setting, a $t$-spanner
of $G$ is a spanning subgraph $G'$ with the property that for
every pair of vertices $x, y$, the shortest path from $x$ to $y$
in $G'$ has weight at most $t geq 1$ times the shortest path
from $x$ to $y$ in $G$. The parameter $t$ is commonly referred to
as the {em spanning ratio}, the {em dilation} or the {em
stretch factor}. In addition to having bounded spanning ratio, it
is desireable to build $t$-spanners that possess other
properties, such as bounded degree, low weight, or
fault-tolerance to name a few. In this talk, we are particularly
interested in planarity. We review various results in the
literature on how to build spanners that are planar.
 Plus d'infos  


2010-10-07Sém LaBRI. The Next 700 BFT Protocols
13:30-14:00
Amphi LaBRI
Byzantine fault-tolerant state machine replication (BFT) has
reached a reasonable level of maturity as an appealing,
software-based technique, to building robust distributed services
with commodity hardware. The current tendency however is to
implement a new BFT protocol from scratch for each new
application and network environment. This is notoriously
difficult. Modern BFT protocols require each more than 20.000
lines of sophisticated C code and proving their correctness
involves an entire PhD. Maintaining and testing each new protocol
seems just impossible.

This talk will present a candidate abstraction, named
ABSTRACT (Abortable State Machine Replication), to remedy this
situation. A BFT protocol is viewed as a, possibly dynamic,
composition of instances of ABSTRACT, each instance developed and
analyzed independently. A new effective BFT protocol can be
developped by adding less than 10% of code to an existing
one. Correctness proofs become at human reach and even model
checking techniques can be envisaged. To illustrate the ABSTRACT
approach, we describe a new BFT protocol we name Aliph: the first
of a hopefully long series of effective yet modular BFT
protocols. The Aliph protocol has a peak throughput that
outperforms those of all BFT protocols we know of by 300% and a
best case latency that is less than 30% of that of state of the
art BFT protocols.

This is joint work with Prof. R. Guerraoui (EPFL) and Dr
M. Vukolic (IBM).
 Plus d'infos  


2010-10-07Sém LaBRI. VMKit: a Substrate for Managed Runtime Environments
14:00-14:30
Amphi LaBRI
Managed Runtime Environments (MREs), such as the JVM and the CLI,
form an attractive environment for program execution, by
providing portability and safety, via the use of a bytecode
language and automatic memory management, as well as good
performance, via just-in-time (JIT) compilation. Nevertheless,
developing a fully featured MRE, including e.g. a garbage
collector and JIT compiler, is a herculean task. As a result, new
languages cannot easily take advantage of the benefits of MREs,
and it is difficult to experiment with extensions of existing MRE
based languages.

This talk will describe and evaluates VMKit, a first attempt to
build a common substrate that eases the development of high-level
MREs. We have successfully used VMKit to build two MREs: a Java
Virtual Machine and a Common Language Runtime. An extensive study
of this infrastructure assesses the ease of implementing new MREs
or MRE extensions and evaluates the resulting performance. In
particular, it took one person only one month to develop a Common
Language Runtime using VMKit. VMKit furthermore has perfor- mance
comparable to the well established open source MREs Ca- cao,
Apache Harmony and Mono, and is 1.2 to 3 times slower than
JikesRVM on most of the DaCapo benchmarks.
 Plus d'infos  


2010-09-23Sém LaBRI. From Distributed Systems to Systems-of-Systems and Beyond: Challenges to Middleware
14:00-15:00
Amphi LaBRI
As the complexity of distributed systems increases towards
systems-of-systems, ultra large scale systems, cyber-physical
systems, etc. there is of course the need to help the developers
of such systems overcome many challenges, which range from:
extreme heterogeneity of technology and environments,
interoperability issues, and high levels of dynamicity. In this
talk, I will present work from the Next Generation Middleware
Group at Lancaster University, where we focus of dynamically
adaptive middleware solutions for complex distributed
systems. This will cover three broad areas. First, approaches for
developing adaptive solutions; this will cover the work of
OpenCom, a reflective component model for developing systems
software, and the emerging field of Models@Runtime that offers
higher-level abstractions to manage complex runtime
adaptation. Second, the ideas of deep middleware to engineer
middleware that can handle high levels of device and network
heterogeneity. Thirdly and finally, I will present our work on
interoperability that allows systems developed with different
middleware to be composed together.
 Plus d'infos  


2010-05-20Sém LaBRI. Automatic structures: Ramsey's theorem
14:00-15:00
Amphi LaBRI
Automatic structures are a class of effectively given structures
that have, compared to general computable structures, favourable
algorithmic properties. One line of research in this area aims at
a better understanding of the differences and similarities
between these two classes. This talk will present the findings
and some open questions in this direction as far as Ramsey's
theorem is concerned.
 Plus d'infos  


2010-05-06Sém LaBRI. Présentation de nouveaux arrivants.
14:00-15:00
Amphi LaBRI
Un problème combinatoire sur les graphes lié aux caractères du groupe symétrique (Valentin Feray)

L'exposé est constitué de deux parties relativement
indépendantes.
L'objectif de la première est de présenter rapidement mon domaine
de recherche, à savoir l'étude combinatoire des représentations
du groupe symétrique. Qu'est-ce que le groupe symétrique ?
Qu'est-ce qu'une représentation ? Quel est le lien avec la
combinatoire ?
La seconde présente de manière plus concrète un problème de
combinatoire sur les graphes au coeur de mes travaux. Il s'agit
d'itérer une transformation locale simple aussi longtemps que
l'on peut et d'étudier le résultat obtenu.

Routage et sélection dynamique de canaux dans les réseaux radios cognitifs (Hicham Khalife)

Dans cet exposé nous nous intéressons aux réseaux radios
cognitifs multi-sauts vus comme l'avenir et la généralisation de
tous les réseaux sans fil existants. Dans ce nouveau domaine où
l'accès aux bandes de fréquences disponibles s'effectue de
manière complètement opportuniste, des problèmes de base restent
encore non résolus. Nous commencerons par donner une
classification des réseaux radios cognitifs en trois catégories
chacune adaptée à un type spécifique de communications. Ensuite
dans chacune de ces catégories, nous proposerons des techniques
de contrôle et d'établissement de chemins de communication. Nous
parlerons alors de l'algorithme de routage MPP (Most Probable
Path routing) dont le but est d'établir un chemin de bout en bout
dans les réseaux radios cognitifs. Nous présenterons aussi SURF
une technique de dissémination de données pour environnements
sans fil opportunistes.
 Plus d'infos  


2010-04-22Sém LaBRI. Algorithmique Stabilisante : Mesurer la qualité du service
14:00-15:00
Amphi LaBRI
L'algorithmique stabilisante a été définie par Dijkstra en 1974,
cette définition a été par la suite affinée par Bui et al. en
1999. Aujourd'hui, la complexité des algorithmes est évaluée en
nombre de rondes. Toutefois, la mesure de la qualité du service
rendu peut prendre en compte d'autres paramètres que nous
étudierons dans cet exposé.
 Plus d'infos  


2010-04-15Sém LaBRI. Réseaux de capteurs multimédias : nouveaux challenges ou vieilles problématiques ?
14:00-15:00
Amphi LaBRI
Les récentes avancées technologiques ont permis l'émergence des
réseaux de capteurs multimédias où l'information récoltée, en
plus des données scalaires classiques, est sous la forme d'images
ou de vidéos. Par réseaux de capteurs multimédias, nous entendons
un ensemble de machines « n½uds » miniatures, chacune d’elles
étant dotée de capacités de capture multimédia (audio et vidéo),
de traitement de l’information (souvent un microprocesseur et
une mémoire vive de faible capacité) et de communication sans
fil (Bluetooth, wifi, WiMax, etc.). Les n½uds constituent ainsi
des unités complètement autonomes.

Après une présentation synthétique des problématiques de
recherche posées par les réseaux de capteurs multimédias, deux
points de nos travaux de recherche seront abordés : (1) la
présentation d'une approche algorithmique distribuée pour
l'optimisation/rationalisation de la consommation énergétique
dans le réseau permettant ainsi une prolongation de sa durée de
vie dans sa globalité. (2) la description de notre architecture
d'un réseau de capteurs multimédias, dédié principalement aux
applications de vidéo surveillance. Contrairement aux
architectures classiques, notre proposition est fondée sur deux
idées maîtresses. (a) Nous proposons une reconstruction 3D des
scènes observées afin de pouvoir exploiter plus facilement et
plus efficacement les données vidéo récoltées par les différents
capteurs. (b) À cette fin, les traitements vidéo correspondants
ont été déportés sur les capteurs eux même permettant ainsi une
réduction substantielle de la charge du système dans sa globalité
et du réseau en particulier. Des résultats expérimentaux seront
présentés.
 Plus d'infos  


2010-04-08Sém LaBRI. Calculs, Automates Cellulaires et Grilles de calcul
14:00-15:00
Amphi LaBRI
Nous montrerons comment l'universalité intrinsèque des automates cellulaires (universalité obtenue dans le modèle sans passer par «l'artifice» d'un modèle intermédiaire) peut être envisagée en s'affranchissant de l'hypothèse de synchronicité pour ne plus se préoccuper que des rapports de causalité. L'espace-temps bien régulier d'un automate cellulaire devient alors une grille que l'on s'autorise à déformer en tout sens.
 Plus d'infos  


2010-03-18Sém LaBRI. Gestion de la cohérence lors de la construction de logiciel
13:30-14:30
Amphi LaBRI
La construction de logiciel implique l'intervention de plusieurs
développeurs qui collaborent à l'édition d'artefacts logiciels
hétérogènes tout au long du processus de développement. Ces
artefacts logiciels sont, par exemple, des documents textuels
précisant les exigences du système, des modèles d'analyse et de
conception, du code, des tests, des guides utilisateur, etc. Tous
ces artefacts, quelle que soit leur nature, décrivent des parties
d'un même système. Ils se doivent d'être cohérents.

L'approche dite de « gestion de la cohérence » considère qu'il
n'est pas possible d'assurer la cohérence globale de tous les
artefacts logiciels à tout moment. N'importe quel artefact peut
être temporairement incohérent. Les incohérences temporaires
seront corrigées le moment venu par l'équipe de développement. La
principale problématique de cette approche réside dans le suivi
des incohérences. Il faut en effet pouvoir détecter
l'introduction de nouvelles incohérences ainsi que la suppression
d'incohérences existantes lors des modifications successives
faites par les développeurs sur les artefacts ; et ce, sans gêner
le cours du processus de développement.

Dans cet exposé nous présenterons Praxis, notre approche de
gestion de la cohérence qui a la particularité d'être basée sur
la trace de construction des artefacts logiciels. Praxis détecte
la présence ou l'absence d'incohérence dans les artefacts. Les
incohérences sont spécifiées par des règles logiques portant sur
les opérations de construction. Cette représentation a l'avantage
de supporter la mise en ½uvre d'une détection incrémentale
offrant des gains de performances très intéressants. De plus,
elle permet la définition de règles d'incohérence dites
méthodologiques permettant de spécifier des ordres temporels
entre les opérations de construction.
 Plus d'infos  


2010-03-18Sém LaBRI. Formal language theory inspired by natural language
14:30-15:30
Amphi LaBRI
Until the mid-1980s, fruitful interactions between formal
language theory and linguistics had been limited to the study of
context-free grammars during a brief period in the late 50s and
the early 60s. About 20 years ago, multiple context-free grammar
was introduced to overcome the difficulty of context-free
grammars to describe some natural language constructions. The
formalism of multiple context-free grammar is just as elegant and
natural as that of context-free grammar, and calls for thorough
mathematical investigations. I sketch some recent developments
and open problems in the theory of multiple context-free
grammars.
 Plus d'infos  


2010-03-04Sém LaBRI. Le problème de rendez-vous asynchrone dans un graphe quelconque
14:00-15:00
Amphi LaBRI
Nous montrerons comment deux agents mobiles se promenant de façon
asynchrone peuvent se rencontrer dans un graphe inconnu
quelconque. À chaque étape, l'agent doit choisir un numéro de
port correspondant à une des arêtes incidentes du sommet courant
et traverser cette arête. Les deux agents se rencontrent s'ils
sont sur un même sommet ou s'ils se croisent sur une arête. La
durée de chaque étape d'un agent est déterminée par un adversaire
omniscient qui essaye d'empêcher le rendez-vous. Les agents ont
des identifiants uniques afin de permettre le rendez-vous de
manière déterministe. Nous montrerons aussi comment on peut
étendre cette approche au problème de rendez-vous dans un
environnement géométrique pour des agents ayant une visibilité
non nulle.
 Plus d'infos  


2010-02-18Sém LaBRI. Self-organization and self-management in communications as applied to autonomic networks - Introduction and Some Research Issues
14:00-15:00
Amphi LaBRI
The essence of autonomic networking, and thus autonomic
communication, is to enable the autonomic network (and the
systems and component that make up the network) to adapt the
services and resources that they offer in accordance with
changing user needs, environmental conditions, and business
goals, all the while ensuring that context-sensitive business
goals are protected. Academic and industry efforts have been
devoted to exploring how autonomic principles are being applied
directly to networking infrastructure for governing services and
resources made available by the network, as well as how new
components and devices join, leave, and organize themselves into
integrated or loosely connected separate networks. This seminar
discusses about concepts in general, research challenges and some
undertaken and ongoing works to face them.
 Plus d'infos  


2010-02-11Sém LaBRI. Description de documents audio multilingues : apport de la prosodie
14:00-15:00
Amphi LaBRI
Au cours de ce séminaire, je décrirai les méthodes utilisées par
le traitement automatique de la parole d'une manière générale, au
niveau des paramètres extraits du signal et des modèles
statistiques employés selon les différentes problématiques posées
par des applications telles que la détection automatique de zones
de parole et de musique, l'identification du locuteur et
l'identification de la langue.

La suite de mon exposé portera sur mes travaux en analyse de la
prosodie. La prosodie, qui représente ce que l'on peut
appeler "la mélodie de la parole", est un phénomène perceptif,
que l'on exprime en termes de rythme, d'intonation et de
hauteur. Comment relier ces notions perceptuelles à des
paramètres mesurables? Comment peut-on modéliser le rythme de la
parole? Je présenterai quelques éléments de réponse à ces
questions qui se sont posées lors de mon travail sur la
caractérisation et l'identification automatique des langues,
ainsi que les perspectives de recherches envisagées.
 Plus d'infos  


2009-12-10Sém LaBRI. Présentation de nouveaux arrivants.
14:00-15:00
Amphi LaBRI
Visualisation de réseaux biologiques (Romain Bourqui)

L'amélioration des techniques d'acquisition de données, notamment
en biologie, a permis d'extraire toujours plus d'information,
rendant nécessaire la mise en place de systèmes d'exploration et
d'analyse. Nous nous intéresserons dans cet exposé à la
visualisation de telles données, et en particulier, à la
visualisation des réseaux métaboliques et de régulation de gènes.


Paire-domination dans les graphes sans étoiles subdivisées (Paul Dorbec)

Au cours de cet exposé, nous rappellerons le contexte de la
domination, et présenterons la paire-domination, variante où l'on
impose que le sous-graphe induit par l'ensemble dominant admette
un couplage parfait. Nous présenterons quelques résultats récents
et représentatifs des techniques fréquemment utilisées dans le
domaine. La présentation sera prévue pour être accessible à un
public non averti.
 Plus d'infos  


2009-11-19Sém LaBRI. Context-oriented Programming
14:00-15:00
Amphi LaBRI
There is an increased need for applications that can dynamically
adjust their behavior to the context of use. Three years ago, we
have introduced Context-oriented Programming (COP) by developing
a number of extensions to languages such as Common Lisp,
Smalltalk and Java. In COP, programs consist of partial class and
method definitions that can be selected and composed at runtime
as needed. Employing potentially crosscutting runtime adaptations
to class and method definitions, COP encourages continually
adjusting behavior of programs according to their context.

Since then, we have carried out a number of successful
application and language experiments which show that the basic
building blocks of COP remain stable. Among others, we have
implemented multiple context-dependent views, coordination of
screen updates, context-dependent discerning of phone calls, and
selecting context-dependent billing schemes. We have also taken
first steps towards the design and requirements engineering
stages for context-aware applications. Furthermore, our ideas
have been picked up in large-scale industrial settings.

This talk introduces the basic language constructs for COP, shows
some non-trivial examples, discusses the impact of COP so far,
and sketches some promising next steps in the field of COP.

Pascal Costanza has a Ph.D. degree from the University of Bonn,
Germany, and works as a research assistant at the Software
Languages Lab of the Vrije Universiteit Brussel, Belgium. His
past involvements include specification and implementation of the
languages Gilgul and Lava, and the design and application of the
JMangler framework for load-time transformation of Java class
files. He has also implemented ContextL, the first programming
language extension for Context-oriented Programming based on
CLOS, and aspect-oriented extensions for CLOS.
 Plus d'infos  


2009-10-15Sém. LaBRI. L'émergence d'une science : l'informatique en France (1950-1975)
14:00-15:30
Amphi LaBRI
Pourquoi la France, où l'on prétendait en 1947 avoir « une avance
théorique » en calcul électronique, a-t-elle dû vingt ans après
lancer un Plan Calcul pour rattraper son retard ? En dépouillant
archives et revues scientifiques, on découvre que la France est
le seul de tous les pays industrialisés où la recherche publique
n'a pas réussi à construire d'ordinateur dans la période
pionnière, avant 1960. L'informatique s'y est cependant
développée grâce aux initiatives d'universitaires, véritables
entrepreneurs de science, souvent en Province, qui collaboraient
avec des industriels novateurs et avec les administrations
techniques civiles ou militaires. Ils ont dû bientôt faire face à
l'explosion de la demande du marché du travail, qui réclamait
toujours plus d'informaticiens. Au cours des années 1960-1970, on
est passé progressivement du calcul électronique, outil au
service des ingénieurs et des mathématiques appliquées, à une
discipline nouvelle, l'informatique, qui recomposait le paysage
scientifique. Cette évolution ne s'est pas accomplie sans
résistances et polémiques. Mais elle répondait à la fois à la
nécessité de formaliser les savoirs pour les enseigner et au
besoin de mieux comprendre ce qui se passait dans les systèmes
informatiques, afin d'améliorer leurs performances et d'étendre
leurs champs d'application.

Pierre-E. Mounier-Kuhn, "L'émergence d'une science.
L'informatique en France, de la 2e guerre mondiale au Plan
Calcul", Presses de l'Université Paris-Sorbonne, 2009 (ISBN
978-2-84050-654-6. F138783).
 Plus d'infos  


2009-07-09Sém LaBRI. Apprentissage incrémental collectif de concept
14:00-15:00
Amphi LaBRI
Nous considérons le problème de l'apprentissage collectif dans un
système multi-agents constitué d'agents cognitifs autonomes. Il
s'agit ici de résoudre collectivement le problème de cohérence en
apprentissage de concepts : l'hypothèse retenue doit accepter les
exemples positifs et rejeter les exemples négatifs d'un
concept. Un flux d'exemples parvient à la collectivité par
l'entremise d'un agent ou un autre et la question est celle du
maintien de la consistance (ici la cohérence) de l'hypothèse
relativement à l'ensemble des informations (les exemples) dans le
système. Chaque agent a un mécanisme élémentaire de mise à jour
et suit un protocole lui permettant de s'assurer de la
consistance relativement à l'ensemble du système via des
interactions avec les autres agents. Il n'y a pas dans ce modèle
de mémoire centralisée, ni d'agents ayant un rôle particulier :
les agents ne sont pas spécialisés et prennent donc tour à tour
un rôle d'apprenant ou de critique. Nous supposons dans une
première partie qu'une seule hypothèse est maintenue et commune à
tous les agents : les agents sont dits non-individualistes et
adoptent une hypothèse qui leur est proposée et qu'ils ne peuvent
réfuter. Dans la seconde partie les agents sont individualistes :
ils acceptent une hypothèse qu'ils ne peuvent réfuter mais ne
l'adoptent pas : à un instant donné chaque agent a une hypothèse
différente. Nous donnerons quelques propriétés du mécanisme
proposé et montrerons expérimentalement que dans le cas
non-individualiste le système peut tirer parti, en termes de
qualité de prédiction, des ressources consacrées à explorer
l'espace de recherche, alors que dans le cas individualiste il
peut tirer parti de la multiplicité des hypothèses si la décision
devient collective.
 Plus d'infos  


2009-06-04Sém. LaBRI. Moderately exponential time algorithms
14:30-15:30
salle 178
Some important part of the research on design and analysis of algorithms is trying to find better approaches for solving NP-hard problems. In most cases the notion of "solving a problem exactly" is relaxed: approximation algorithms, heuristics, randomized algorithms, parameterized algorithms, algorithms for restricted inputs, etc.

Another approach, called moderately exponential-time algorithms, has attracted a lot of interest recently. Such an algorithm indeed tries to cope with NP-hardness in the strongest sense: the problem needs to be solved by the algorithm for all inputs and worst-case running time is considered. Techniques for the design and analysis of moderately exponential-time algorithms will be presented, among them branching algorithms, dynamic programming algorithms and inclusion exclusion algorithms.

The breakthrough result of Bjorklund, Husfeldt and Koivisto (FOCS 2006), a O*(2^n) algorithm to compute the chromatic number of an n-vertex graph will be outlined.
 Plus d'infos  


2009-05-14Sém. LaBRI. Le problème du pavage dans le plan hyperbolique
14:00-15:00
Amphi LaBRI
Le problème du pavage a été posé dans les années 50 par Hao Wang. Existe-t-il un algorithme possédant la propriété suivante : appliqué à un ensemble fini de tuiles T, l'algorithme répond "OUI" si on peut paver le plan en utilisant des copies d'éléments de T et "NON" si c'est impossible. Hao Wang démontra en 1958 qu'une version partielle du problème est indécidable. Il conjectura que le problème général, sans restriction sur l'utilisation de l'ensemble de tuiles, était décidable. Un de ses élèves, Robert Berger démontra en 1966 que le problème général était lui aussi indécidable. Il convenait de préciser dans ce qui précède que lorsqu'on parlait du plan, il s'agissait du plan euclidien. Dans une preuve restée célèbre du même problème simplifiant beaucoup celle de Berger, Raphael Robinson posa en 1971 la question suivante : "Qu'en est-il du problème du pavage en ce qui concerne le plan hyperbolique?". Robinson apporta une réponse partielle en 1978, toujous dans le sens de l'indécidabilité. Rien ne changea jusqu'en 2006 où l'auteur apporta une réponse également négative dans un cas toujours partiel mais plus général que le cas étudié par Robinson en 1978. En 2007, le problème fut résolu, indépendamment et simultanément (les approches sont très différentes) par l'auteur et Jarkko Kari, dans le sens de l'indécidabilité. La preuve de l'auteur a été publiée en 2008 dans TCS, N°407. L'exposé se propose de donner les grandes lignes de cette preuve.
 Plus d'infos  


2009-04-30Les problèmes de licences et de valorisation du logiciel en environnement académique
14:00-16:00
Amphi LaBRI
À l'initiative de Scideralle et de l'ABUL dont le LaBRI est
partenaire pour l'organisation des Rencontres Mondiales du
Logiciel Libre de juillet 2010 à Bordeaux, ce séminaire portera
sur les problèmes de licences et de valorisation du logiciel en
environnement académique.

En effet, concernant la question du droit qui peut s'appliquer
sur les sources et algorithmes que les chercheurs sont amenés à
publier, il existe pour les intéressés de larges zones d'ombre
quant au statut et à la protection du code qu'ils publient,
notamment si l'on cherche à bien différencier trois concepts, et
trois moments de leur travail :

* l'idée elle-même ;
* l'algorithme en pseudo code ;
* la mise en ½uvre ("implementation") dans un langage.

Vulgariser le droit positif sur ces notions fines n'est pas
facile, les réponses de services juridiques universitaires ou
ministériels sont souvent difficiles à obtenir et pas toujours
compatibles entre elles, parfois même sujettes à caution.

Nous souhaitions donc inviter un juriste spécialisé sur ces
questions relatives à l'informatique et au droit d'auteur ainsi
qu'un chercheur ayant l'expérience de publication de son code
sous licence et à même de faire part de celle-ci.

Sébastien Canevet et François Pellegrini ont accepté de bonne
grâce de se prêter à l'exercice jeudi 30 avril 2009 de 14h à 16h
pour un séminaire du LaBRI plus long qu'à l'habitude compte tenu
du sujet.

Pour de plus amples informations:
http://scideralle.org/Seminaire-LaBRI-30-avril-2009.html
http://abul.org/Seminaire-LaBRI-30-avril-2009.html
 Plus d'infos  


2009-04-02Sém. LaBRI. Comparaison de Séquences et d'Arborescences, De la BioInformatique à la Musique. Pascal Ferraro
14:00-15:00
Amphi LaBRI
Cet exposé présente l'application des méthodes d'analyse
structurelles des séquences et d'arborescences, développées
depuis trois décennies en Bioinformatique, à l'analyse et à l'
identification automatique de la structure dans la musique.

De plus en plus de documents musicaux numériques sont disponibles
en ligne (Internet , mobile , ...). Les utilisateurs ne disposent
actuellement que d'une navigation basée sur les noms (morceaux,
interprètes), et ont donc besoin de se voir proposer de nouvelles
méthodes de recherche adaptées à la spécificité de la
musique. Par exemple, des applications comme la requête par
fredonnement (query-by-humming), permettant de retrouver un
morceau à partir d'un extrait fredonné, ou la requête par
l'exemple, permettant de retrouver des morceaux ressemblant à un
extrait donné, doivent faciliter aux utilisateurs l'accès à de
nouvelles pièces musicales.

Ces nouvelles méthodes de navigation reposent en grande partie
sur l'estimation de la similarité musicale entre deux
morceaux. La notion de similarité est très difficile à définir
avec précision, le problème de la similarité musicale reste un
des problèmes majeurs de la recherche en système d'informations
musicales. D'un point de vue informatique, estimer la similarité
consiste à développer des algorithmes qui calculent une mesure de
ressemblance entre deux segments de morceaux comme cela se fait
en bioinformatique des séquences. Partant de ce constat cet
exposé présentera comment les techniques appliquées pour
l'évaluation de la similarité en biologie, peuvent être
appliquées à la Musique.
 Plus d'infos  


2009-03-05Sém. LaBRI. De l'espace mémoire nécessaire aux algorithmes auto-stabilisants. Colette Johnen
14:00-15:00
Amphi LaBRI
La notion d'auto-stabilisation a été introduite par Edsger
Dijkstra en 1974 : Quel que soit son état initial, un système
auto-stabilisant est certain d'atteindre un état cohérent en un
nombre fini d'étapes. Une telle propriété est hautement
souhaitable, car après une perturbation inattendue de l'état des
mémoires des processus, un système auto-stabilisant retourne
finalement à un état correct sans aucune intervention extérieure.

Les deux principaux problèmes "étalons" de l'algorithmique
répartie sont l'élection de leader et l'exclusion mutuelle. Je me
suis intéressée à concevoir des solutions auto-stabilisantes à
ces problèmes dans le cadre d'anneaux anonymes. Dans la plupart
des cas, il n'existe pas d'algorithme déterministe et
auto-stabilisant d'élection de leader, ni d'exclusion
mutuelle. J'ai donc proposé des algorithmes probabilistes. Je me
suis particulièrement attachée, à concevoir des solutions
optimales en terme d'espace mémoire.
 Plus d'infos  


2009-02-19Sém. LaBRI. Graph drawing algorithms: how good are they really? Helen Purchase
14:00-15:00
Amphi LaBRI
Much effort has been spent on designing algorithms for the
automatic layout of graphs. Typically, the worth of these
algorithms has been assessed by their computational efficiency
and by the extent to which the graph drawings they produce
conform to pre-defined "aesthetics" (e.g., minimising the number
of edge crosses and edge bends, or maximising symmetry) that are
assumed to make the drawing easier to understand.

This talk will report on a long-term Human Computer Interaction
project which investigates the worth of these algorithms with
respect to human comprehension of the drawings
produced. Empirical studies have been conducted looking at the
aesthetics of static graph drawings, and, more recently, dynamic
graphs which change over time. This talk will outline the
experimental methodologies used and present the important results
obtained. It will also outline the current project which
investigates the importance of maintaining the user's mental map
when a diagram changes over time.

Dr Helen Purchase is Senior Lecturer in the Department of
Computing Science at the University of Glasgow.
 Plus d'infos  


2009-02-12Sém. LaBRI. Teaching Considered Harmful. John Hamer
14:00-15:00
Amphi LaBRI
"Teaching Considered Harmful"
Learning through contribution: reinventing Computer Science pedagogy

Computer Science has, in its youthful way, evolved a pedagogy by
adopting elements from its parent disciplines of Mathematics and
Engineering.

However, if we characterise Mathematics as dealing with
disembodied knowledge, and Engineering with established, stable
subject knowledge, then clearly Computer Science is unlike either
of these. Much knowledge in Computing is ephemeral, and one of
the key skills in the discipline is knowing where to look for a
solution and how to evaluate its utility.

Nevertheless, our "signature" pedagogy centres around traditional
lectures, handing out extensive course notes (in lieu of
textbook), and setting individual assignment work.

In this talk, I present an alternative approach to teaching and
learning in the subject, in which students take on some or many
of the roles of the teacher. Two of the techniques described
(peer assessment, and multiple-choice question authoring) are
ideally suited to large classes, while others (such as
collectively authoring a course textbook) are intended for use
with smaller groups. The claim that the approach leads to
enhanced and deepened learning is evaluated in the light of the
research evidence we have collected.
 Plus d'infos  


2009-01-15Sém. LaBRI. Topologies de l'Internet. Damien Magoni
14:00-15:00
Amphi LaBRI
L'Internet est devenu sans conteste en trois décades le support
matériel majeur de l'ère de l'information. Durant cette courte
période, il a subi deux mutations importantes. Tout d'abord, il a
subi une mutation de taille : de quelques dizaines de systèmes
interconnectés, l'Internet est passé à une taille phénoménale de
plus de 300 millions d'hôtes. De plus, il a subi une mutation de
forme : nous sommes passés des gros systèmes fixes à des
ordinateurs personnels mobiles. Ces deux mutations entraînent
deux défis importants pour les chercheurs qui oeuvrent à
l'amélioration de l'Internet. Premièrement, il est nécessaire de
connaître avec le plus de précision possible, la topologie de
l'Internet. Seules des méthodes macroscopiques et statistiques
permettent désormais de connaître cette topologie car plus
personne n'a autorité sur l'organisation et l'expansion du réseau
Internet.
Deuxièmement, l'évolution rapide des technologies a fait que les
paradigmes qui sous-tendaient à la création des protocoles
initiaux de l'Internet ne sont plus valables à l'heure
actuelle. Les notions de mobilité, de sécurité et de diffusion
quasi-inexistantes à l'origine sont désormais ardemment
souhaitées par les utilisateurs mais difficiles à mettre en
oeuvre dans les protocoles actuels. Il faut donc trouver les
moyens d'offrir ces nouvelles fonctionnalités en conservant les
propriétés initiales des protocoles qui ont fait le succès
d'Internet. Dans ce séminaire, nous présentons des contributions
qui tentent de répondre à certains aspects de ces deux défis
majeurs. Nous nous concentrons tout particulièrement sur la
cartographie de l'Internet, le stockage d'états dans les routeurs
exécutant des protocoles multipoints, l'implémentation de
fonctionnalités réseaux dans les hôtes par la conception de
réseaux recouvrants et l'optimsation des puissances de
transmission dans les réseaux sans fils.
 Plus d'infos  


2008-12-11Sém. LaBRI. Le langage Common Lisp. Robert Strandh
14:00-15:00
Amphi LaBRI
Ce séminaire sera le premier d'une série dont le but est de
présenter le langage Common Lisp aux collègues du LaBRI. Pour
le premier séminaire de la série, je donnerai un survol du
langage et un plan préliminaire pour les autres séminaires de la
série.

La plupart des membres du LaBRI on soit appris Lisp bien avant la date
de la normalisation par ANSI du langage Common Lisp (1994), soit pas
du tout (les jeunes). Le langage Common Lisp est très différent
du langage Lisp d'il y a quelques décennies et surtout très
différent d'un certain nombre de préjugés très
répandus. En particulier :

* La plupart des implémentations de Common Lisp génère du
code natif grâce à un compilateur incrémental. Par
contre, le langage est DYNAMIQUE et INTERACTIF dans le sans que la
sémantique est définie par une succession d'interactions.

* Grâce au compilateur et à la possibilité d'annoter le
programme de déclarations de types, la vitesse du code
généré est comparable à celle du compilateur GCC pour
le langage C.

* Le langage normalisé contient un système très
sophistiqué de programmation par objets, permettant notamment
la sélection multiple (multi-méthodes), les méthodes
secondaires (:before, :after, :around), plusieurs combinaisons de
méthodes et l'introspection etc. grâce au MOP
(méta-object protocol).

* Le système de conditions (appelés "exceptions" dans d'autres
langages) permet un véritable dialogue entre le code qui
détecte une situation exceptionnelle et le traitant de la
condition, grâce au système de RESTARTS.

* Les macros Common Lisp sont des fonctions qui transforment du code
Common Lisp (sous forme d'arbres syntaxiques) permettant ainsi le
rajout de nouvelles constructions syntaxiques sans les
problèmes du préprocesseur C ou C++. Ceci permet
l'écriture de langages dédiés sous forme de LANGAGES
ENCHÂSSÉS.

Après le premier séminaire, je compte présenter le langage de
manière interactive (sur ordinateur) en commençant par les
fonctionnalités les plus simples, et je pense consacrer chaque
séance à une fonctionnalité différente du langage afin de
permettre aux collègues de pouvoir suivre la présentation sans
avoir assisté à toutes les présentations précédentes.
 Plus d'infos  


2008-11-20Séminaire LaBRI: Bayesian inference for video geometry. Tamas Sziranyi
14:00-15:00
Amphi LaBRI
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.
 Plus d'infos  


2008-07-03Séminaire LaBRI, Claire Mathieu, Théorie algorithmique des jeux et enchères combinatoires
14:00-15:00
Amphi LaBRI
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.
 Plus d'infos  


2008-06-12Séminaire LaBRI, Arnaud Pêcher, Présentation de l'équipe-projet RealOpt (en création)Reformulation based algorithms for combinatorial optimization.
14:00-15:00

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.
 Plus d'infos  


2008-05-22Séminaire LaBRI, Alexis Bouquet, Evaluation de la sécurité des systèmes d'information.
14:00-15:00
Amphi LaBRI
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.
 Plus d'infos  


2008-04-17Séminaire LaBRI, A few topics of investigation for video obtained from active cameras
14:00-15:00
Amphi LaBRI
Pan tilt zoom cameras are of frequent use in sport video and are increasingly popular in surveillance. They permit to actively track the targets with much
wider coverage than fixed cameras, focus on target's parts such as faces or objects, and, in their IP-based configuration, have low cost network infrastruc
ture.
However the use of these devices introduces new complexities and requirements in several classical problems of video analysis.
In particular, SIFT-based shape matching appears appropriate in that it exhibits invariance under rotation, translation and scale change. But in practical
applications its effective application depends on how much the thresholds used for matching adapt to the active camera observations.
In networked surveillance configurations with IP active cameras, due to the network lag, it is difficult to perform tracking from the analysis of the frames
of the active camera or acquire high resolution images without loosing camera calibration.
Using active cameras in surveillance applications permits to focus on target faces and therefore, at least in principle, more effective recognition. Due to
the increasing availability of three-dimensional face models, this drives the interest in face recognition based on 3D face models so as to improve the eff
ectiveness of face recognition systems.
We discuss these issues and the solutions that have been developed at Media Integration and Communication Center of the University of Florence.
 Plus d'infos  


2008-04-10Séminaire LaBRI: Quelques résultats dans le domaine des réseaux mobiles ad hoc discontinus
14:00-15:00
Amphi LaBRI
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é.
 Plus d'infos  


2008-04-03Séminaire LaBRI, Sang-il Oum, Line graphs of large rank-width
14:00-15:00
Amphi LaBRI
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
 Plus d'infos  


2008-03-20 Séminaire LaBRI Protection du patrimoine
14:00-15:00
Amphi LaBRI
Jean-Luc Toffart
Adjoint au fonctionnaire sécurité et Défense du CNRS

Son exposé s'intitule

Protection du patrimoine

" Il s'agit d'un exposé de sensibilisation aux menaces dirigées contre le
patrimoine scientifique et humain du CNRS avec des exemples concrets de
problèmes rencontres dans certains laboratoires.

Les menaces sont-elles un mythe ou une réalité ?
Protection contre une menace intérieure ou extérieure ?
Sommes-nous sûrs de ne pas nous mettre en situation de faiblesse ?

Cet exposé sera ouvert à toutes les questions que vous pourriez vous
poser sur la fonction du Fonctionnaire de sécurité défense."

NB: séminaire organisé par Brice Goglin.
 Plus d'infos  


2008-03-13Séminaire du LaBRI, Calculs de distances génomiques
14:00-15:00
 Plus d'infos  


2008-03-06Séminaire LaBRI, Markus Lohrey, Algorithmics on compressed strings
14:00-15:00
Amphi LaBRI
Markus Lohrey (Université de Leipzig) est un invité au LaBRI de Géraud Senizergue.

Son exposé s'intitule

Algorithmics on compressed strings
(joint work with Yury Lifshits and Saul Schleimer).

En voici le résumé :

"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."
 Plus d'infos  


2008-02-14A New Sub-pixel Topological Map for Image Analysis
14:00-15:00
Amphi LaBRI
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.
 Plus d'infos  


2008-01-24Séminaire LaBRI. Présentation de l'équipe-projet Cepage: Chercher et Essaimer dans les Plates-formes A Grande Echelle.
14:00-15:00
Amphi 050
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.
 Plus d'infos  


2008-01-10 Champs de déplacements et bases polynômiales
14:00-15:00
Amphi 050
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.
 Plus d'infos  


2007-11-22Partitions régulières de graphes épars et applications
14:00-15:00
Amphi LaBRI
Le concept de "tree-width" est central dans l'analyse des classes de
graphes à mineurs exclus menée par Robertson et Seymour, et a 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
du second ordre monadique pour les graphes de "tree-width" bornée.
Il est apparu que nombre de problèmes NP-complets peuvent être résolus
en temps polynomial lorsqu'ils sont restreints à une classe de
"tree-width" bornée. Néanmoins, une telle restriction est extrêmement
forte, les graphes planaires, par exemple, n'ayant pas de "tree-width"
bornée.

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 qui exclue au moins un graphe) et pour tout entier p, il existe
une constante N(C,p) telle que tout graphe G dans C possède une
partition de ses sommets en au plus N(C,p) parties telle que i au plus p
de ces 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 est la hauteur minimale d'une forêt enracinée dont
la fermeture inclut G.
Cet invariant monotone par mineur est lié à la 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é sont particulièrement petites, dans
le sens qu'elles n'incluent qu'un nombre fini de classes
d'équivalences pour l'homomorphisme, et qu'elles excluent les longues
chaînes (à comparer avec les classes de tree-width bornée 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 dans C possède
une partition de ses sommets en au plus N'(C,p) parties telle que
iau plus p de ces 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 vues 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
NABLAr(G)=max |E(H )| / |V(H )| où
le maximum concerne tous les mineurs H de 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 graphes C est d'expansion bornée si sup{pour G dans C de NABLAr(G)} est
fini (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énombrement
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és 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.
 Plus d'infos  


2007-10-25Les défis de l'ordinateur quantique
14:00-15:00
Amphi LaBRI
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.
 Plus d'infos  


2007-06-07Visualisation de l'évolution des logiciels
14:00-15:00
Amphi LaBRI
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.
 Plus d'infos  


2007-03-29Fouille de données interactive, visualisation et exploration de grands graphes.
14:00-15:00
Amphi 050
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.
 Plus d'infos  


2007-02-08Présentation du 7ième programme cadre et de l'European Council Research.
14:00-15:00
(Résumé précis à venir)
 Plus d'infos  


2007-02-08Le 7ème PCRD: quelles opportunités pour les Technologies de l'Information et de la Communication (TIC) ?
14:00-15:30
050
14h00 Accueil de Maylis Delest, Directrice du LaBRI.

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
 Plus d'infos  


2007-01-18Présentation du projet ANR MARS
14:00-15:00
Amphi 050
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.
 Plus d'infos  


2006-12-14Quelques aspects de l'information quantique.
14:00-15:00
Amphi 050
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.
 Plus d'infos  


2006-12-07Exposés d'Ingénieurs de Recherche du LaBRI (II)
14:00-15:00
050
Pour Nathalie Furmento (accompagnée de Raymond Namyst) :

Calcul parallèle à hautes-performances en MPI

Les travaux présentés portent autour de l'optimisation des
communications sur réseaux rapides au travers de différentes
implantations du standard MPI élaborées dans l'équipe Runtime. La
toute première implantation, MPICH-Madeleine, est basée sur MPICH
développée à Argonne. Les principaux aspects de MPICH-Madeleine sont
l'hétérogénéité au niveaux des réseaux, et le support des applications
multi-threadées. L'implantation, qui s'appuie à la fois sur une
bibliothèque de communication bas-niveau et sur une bibliothèque de
multithreading, est capable d'assurer la progression des
communications parallèlement au déroulement de l'application. Une
deuxième version de MPICH-Madeleine repose sur PadicoTM, une
infrastructure de communications pour les grilles de calcul, et permet
donc de cibler un éventail plus large d'architectures pour l'exécution
d'applications MPI.

Plus récemment, nous avons développé MadMPI, une nouvelle
implantation de MPI, basée sur un moteur de communication nommé
NewMadeleine développé tout récemment dans l'équipe. Ce moteur permet
d'implanter des optimisations agressives des transferts en inversant,
regroupant ou encore en découpant les paquets. Il est en outre capable
d'exploiter plusieurs réseaux simultanément. MadMPI implante un
sous-ensemble des fonctionnalités de MPI, en mettant plus
particulièrement l'accent sur les performances des communications
point à point.

Des mesures de performances des communications seront présentées pour
MPICH-Madeleine et MadMPI, sur différents réseaux rapides. On
présentera également l'évaluation de différents mécanismes
d'optimisation.



Pour Gérald Point (accompagné de Alain Griffault et Jérôme Leroux) :

Activités de Gérald Point au sein du thème MV

AltaRica est un langage de modélisation de systèmes qui a été conçu pendant
la thèse de G. Point. Il est maintenant utilisé dans l'industrie (Dassault,
Onera, ...) et utilisé dans les enseignements de méthodes de vérifications
formelles. Plusieurs outils d'analyse et de compilation du langage sont
développés au LaBRI et diffusés sur le site du projet AltaRica. Deux outils
sont actuellement diffusés, MEC 5 développé par A. Vincent et les AltaTools
développés par G. Point. Afin de rationnaliser les développements, G. Point
travaille à l'intégration de MEC 5 et des AltaTools au sein d'un même outil
appelé ARC.

La logique de Presburger permet de décrire des modèles infinis (par exemple
un réseau de Petri non borné). L'outil FAST développé au LSV (Cachan) par
J. Leroux et S. Bardin permet l'analyse de systèmes décrits dans cette logique.
Les semi-algorithmes mis en oeuvre dans l'outil requièrent l'utilisation d'un
moteur de calcul permettant la résolution et le stockage des solutions de
formules de Presburger. Jusqu'à présent FAST utilisait la bibliothèque MONA.
Depuis 2005, nous avons réorganisé le code de FAST afin de faciliter
l'intégration et la comparaison d'autres moteurs de calcul. En particulier nous
avons pu intégrer dans FAST la bibliothèque Prestaf conçue par J.M. Couvreur.

Après une présentation des thèmes d'activités précédents, nous donnerons un
aperçu des outils développés par G. Point autour d'AltaRica et du traitement
des formules de Presburger.
 Plus d'infos  


2006-11-30Exposés ingénieurs de recherches du LaBRI(I)
14:00-15:15
Amphi 050
Patrick Henry (accompagné de Christian Rétoré)

Lexique génératif (15 minutes)

La linguistique décrit le fonctionnement de la langue tandis que
l’informatique linguistique s’attache au traitement automatisé de
l’information langagière. Pour analyser le langage naturel avec des
moyens informatiques, les modèles morpho-syntaxiques ne suffisent pas.
Il faut aussi être capable de représenter le sens des mots et des
phrases, notamment pour filtrer les constructions syntaxiquement
possibles mais sémantiquement mal fondées. James Pustejovsky a été un
des premiers à proposer l’introduction d’informations sémantiques dans
le lexique. Cette sémantique « de surface » est suffisante pour décrire
des mécanismes de composition et de filtrage plus sophistiqués,
notamment certaines reprises anaphoriques. Le travail que je présente
est une implémentation de tels mécanismes. Après avoir défini et
implémenté un lexique génératif, ainsi qu’une boite à outils pour
l’exploiter, j’ai développé une petite application qui valide cette
implémentation ainsi que les idées d’un article présenté par Ch. BASSAC
et P. BOUILLON à GL2005.


Corpus de langue des signes (15 minutes)

La langue des signes française est une langue à part entière qui
utilise des gestes au lieu d’ondes sonores. Interdite en France de 1880
à 1980, elle suscite l’intérêt des linguistes qui cherchent à formaliser
ses mécanismes et à la comparer aux langues parlées. Une condition
préalable à l’étude de cette langue qui est surtout « orale » par
opposition à écrite (plus spontanée et moins normée), est la
construction de corpus mettant en relief les aspects que les linguistes
veulent étudier. Dans cette optique la Région Aquitaine a subventionné
un projet de l’étude de cette langue sous la forme d’une bourse d’étude
pour un doctorant et des moyens matériels pour la fabrication d’un
corpus vidéo. C’est dans ce contexte que j’ai commencé à étudier les
meilleurs moyens en logiciel et en matériel pour mener à bien ce projet.
C’est une combinaison de matériels d’acquisition à haute définition
(1080i) et de logiciels d’annotation qui permettent d’alimenter ce
corpus de langue des signes. Bien au-delà des simples prises de vues, la
spécificité de ce travail tient aussi bien dans l’absence de produits
d’annotation directement déployables que dans la difficulté de
manipuler des objets vidéo de grande taille très gourmands en
ressources.

de Boris Masencal
1) titre: "Représentation et segmentation d'images 2D - girl & ise"
intervenants : Achille Braquelaire & Boris Mansencal
résumé : "La segmentation d'image 2D, c'est-à-dire la décomposition d'un image
en régions, nécessite de disposer d'une représentation de la géométrie
et de la topologie de cette décomposition, tant pour piloter le
processus de segmentation que pour exploiter et analyser son
résultat. Un modèle a été développé au LaBRI depuis une quinzaine
d'années, basé sur l'utilisation de cartes combinatoires et de
contours discrets interpixels. Ce modèle avait déjà fait l'objet de
plusieurs développements, dans un premier temps sous la forme de
maquettes expérimentales, puis plus récemment dans le cadre
d'applications pratiques de segmentation et d'analyse d'image.
Le travail présenté ici porte sur le développement d'implémentations
abouties et publiables de ces logiciels, et notamment :
- la bibliothèque GIRL (General Image Representation Library)
implémentant le modèle de représentation
- la bibliothèque ISE (Image Segmentation Environment) implémentant un
moteur de segmentation par découpe/fusion construit au-dessus du
modèle de représentation."

2) titre: "Analyse et indexation vidéo dans le domaine compressé : paradigme du rough
indexing"
intervenants : Jenny Benois-Pineau & Boris Mansencal
résumé : "Le volume de données vidéo disponibles sous forme compressée, est de plus en
plus important. La nécessité d'avoir des outils d'analyse et d'indexation efficace est
donc de plus en plus grande. Or de nombreux outils existants nécessitent la
décompression des flux vidéo compressés pour réaliser ces opérations.
Le thème AIV a développé tout un ensemble d'outils, au sein du paradigme de Rough
Indexing, ou Indexation Primaire que nous définirons, pour réaliser l'analyse et
l'indexation sans décompression complète du flux vidéo. Ainsi des descripteurs vidéo
bas-niveaux disponibles dans le flux grâce à la compression pourront être exploités à des
fins d'indexation.
Nous présenterons la chaine d'outils disponibles, les améliorations que nous avons
apportées, et plus particulièrement le travail effectué sur la détection et le suivi
d'objets en mouvement à l'intérieur d'un plan vidéo. "

3) titre : "Analyse spectrale - InSpect"
intervenants : Myriam Desainte-Catherine, Sylvain Marchand & Boris Mansencal
résumé : "Dans le cadre de la recherche dans le thème Modèles pour le Son et la
Musique, plusieurs outils d'analyse, traitement et synthèse
dans le domaine spectral ont été développés.
Le logiciel Inspect, notamment, vise à rassembler de nombreuses méthodes
d'analyse.
Il se destine à trois types de public : les musiciens qui doivent
pouvoir l'utiliser facilement, les chercheurs qui doivent pouvoir
comparer différents résultats voire tester de nouveaux modules, et les
enseignants qui doivent pouvoir montrer l'effet de différentes opérations.
Nous présenterons le travail effectué pour la refonte de ce logiciel,
dans le but de mettre à disposition l'état de l'art de la recherche en
analyse spectrale."
 Plus d'infos  


2006-11-16Beyond Perfection: On Characterizations and Superclasses.
14:00-15:00
Amphi 050
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.
 Plus d'infos  


2006-11-09How to win infinite games?
14:00-15:00
Amphi 050
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.
 Plus d'infos  


2006-10-26 Systèmes d'aide à la démonstration
14:00-15:00
Amphi LaBRI (50)
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
 Plus d'infos  


2006-10-19Décomposition de graphes
14:00-15:00
Amphi LaBRI (050)
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".
 Plus d'infos  


2006-09-28Présentation de la petite école combinatoire sur les polynômes orthogonaux
14:00-15:00
Amphi LaBRI (050)
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.
 Plus d'infos  


2006-07-06 High Dynamic Range Display Technology for Perceptually Realistic Rendering
15:00-16:00
Amphi 050
Note du secrétaire: Cet exposé organisé par IPARLA est labélisé séminaire du LaBRI.

Résumé:

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.
 Plus d'infos  




Liste des événements répétitifs du groupe Séminaire du LaBRI




Retour
Retour à l'index