Séminaire du LaBRI

Le séminaire du LaBRI se déroule approximativement deux fois par mois le jeudi de 13h30 à 14h30 dans l'amphithéatre du LaBRI. L'exposé de 50 minutes du séminaire s'adresse à tous les chercheurs du LaBRI (doctorants compris). L'orateur a la tâche délicate de présenter un domaine de recherche, en restant accessible à un large public d'informaticiens, sans renoncer à un ou deux passages techniques illustrant les modes de raisonnements du domaine.

Les différentes informations permettant d'accéder au LaBRI facilement se trouvent ici.

Contact : Direction du LaBRI


Prochain(s) séminaire(s)



Précédent(s) séminaire(s)


  • André Rossi (Université de Bretagne-Sud, Lab-STICC)
Jeudi 25 avril 2013
Tour d'horizon de divers problèmes d'optimisation dans les réseaux
Mots clés : Réseaux sans fil, télécommunications, fibre optique, optimisation combinatoire.
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.
  • Matthieu Constant (IGM - Université Paris-Est)
Jeudi 11 avril 2013
Intégrer la reconnaissance des expressions figées dans des analyseurs linguistiques
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.
  • David Janin (LaBRI)
Jeudi 4 avril 2013
La tuile : vers un modèle pour la programmation structurée de l’espace et du temps
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.
  • Jean-Loup Guillaume (LIP6, UPMC)
Jeudi 28 mars 2013
Graphes dynamiques, communautés et accessibilité
On assiste depuis quelques années à une explosion de l'utilisation des graphes pour modéliser des données réelles, d'où le terme graphes de terrain. L'un des axes de recherche qui a commencé à émerger il y a quelques années a pour objectif de définir des méthodes et algorithmes pour l'étude de la dynamique de ces graphes de terrain. Dans cet exposé j'aborderai deux pistes de recherche liées à cette problématique : la détection de communautés et l'accessibilité dans les réseaux tolérants aux délais.
Le calcul et le suivi de communautés dynamiques a pour objectif de faire évoluer un découpage initial en communautés au fur et à mesure des modifications de la topologie du réseau sous-jacent. Je proposerai plusieurs solutions et montrerai qu'elles souffrent soit d’un problème d’instabilité qui limite leur utilisation, soit que leur complexité limite leur utilisation à des réseaux de taille réduite ou peu dynamiques.
Le second point que j'aborderai concerne l'accessibilité dans les réseaux dynamiques type DTN afin de savoir qui peut joindre qui en un temps borné. Je montrerai les bases théoriques qui nous ont permis de proposer un algorithme efficace du calcul du "graphe d'accessibilité temporel" qui représente une fermeture transitive du graphe dynamique sous-jacent. Je validerai son utilisation sur des traces synthétiques et réelles et montrerai quelques applications.
  • Sylvain Sené (IBISC, Université d'Evry ; et IXXI, ÉNS-Lyon)
Jeudi 21 mars 2013
Propriétés combinatoires et de robustesse de modèles discrets de réseaux biologiques
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.
  • Georges Grinstein (University of Massachusetts Lowell)
Jeudi 14 mars 2013, en 178 et à 11h, séminaire en commun avec le GT MaBioVis
Measuring truth in visualizations
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.
  • Guillaume Blin (IGM - Université Paris-Est)
Jeudi 7 mars 2013
Next Generation Radiotherapies
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.
  • Laurent Simon (LRI, Université Paris 11)
Jeudi 21 février 2013
Towards a new era of SAT Solvers
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.
  • Joseph Peters (School of Computing Science, Simon Fraser University)
Jeudi 7 février 2013
Optimizing Energy and Bandwidth in Mobile Streaming Systems
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.
  • Aristotelis Chatziioannou (Institute of Biology, Medicinal Chemistry & Biotechnology, NHRF, Athens, Greece)
Jeudi 6 décembre 2012, exceptionnellement en salle 178, et à 16h30
Promoting systems biology research through intelligent information mining of omic datasets
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.
  • Gilles Dowek (Deducteam, INRIA-Rocquencourt)
Jeudi 15 novembre 2012
Causal graph dynamics
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
  • Michael Albert (University of Otago, New Zealand)
Jeudi 13 septembre 2012
Permutation Patterns
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.
  • Nathalie Henrich (GIPSA-AB, Grenoble)
Jeudi 14 juin 2012
L’instrument vocal humain : entre vibrations et résonances
L’instrument vocal humain est tout à la fois un outil essentiel de la communication humaine et un instrument de musique aux multiples facettes. Après avoir décrit la physiologie de la production vocale humaine, nous détaillerons les principes physiques à la base de la compréhension et de la modélisation de la voix humaine. Nous illustrerons ensuite l’approche pluri-disciplinaire mise en œuvre dans les recherches scientifiques sur la voix chantée, à travers la description de deux études récentes : la voix du Bassu dans le chant polyphonique traditionnel A Tenore de Sardaigne, et les qualités vocales dans le chant féminin Bulgare.
  • Yacine Ghamri-Doudane (LIGM (Marne-la-Vallée) et ENSIIE (Evry))
Jeudi 19 avril 2012
Routage géographique dans les réseaux véhiculaires ad hoc en environnement urbain
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.
  • David Janin (LaBRI)
Jeudi 12 avril 2012
Musique computationnelle : des arabesques de Debussy aux monoides quasi-inversifs de Lawson
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 ?
  • Gautier Stauffer (IMB, projet INRIA RealOpt, Bordeaux)
Jeudi 5 avril 2012
Extended formulations for the design of approximation algorithms : an example in inventory control
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.
  • Anthony Busson (Université Paris Sud 11)
Jeudi 29 mars 2012
Algorithmiques et évaluation de performance dans les réseaux ad hoc
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.
  • Volker Diekert (FMI, Universität Stuttgart, Germany)
Jeudi 15 mars 2012
Power circuits and arithmetic for highly compressed integers
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.
  • Frédéric Bimbot (IRISA, Rennes)
Jeudi 8 mars 2012
Concepts et méthodologie pour une description sémiotique de la structure musicale
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.
  • Fabien Lotte (INRIA Bordeaux)
Jeudi 23 février 2012
Une introduction aux interfaces cerveau-ordinateur basées sur l'électroencéphalographie
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.
  • Dan Brown (University of Waterloo, Ontario)
Jeudi 19 janvier 2012
From DNA to Jay-Z: how ideas from bioinformatics can automate finding rhymes in rap music
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
  • Tim Sheard (Université de Portland State, Oregon)
Mardi 10 janvier 2012, à 16h dans l'amphi du LaBRI.
Nax: a logic based upon Mendler style Iteration/Recursion Combinators
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.
A noter : Tim Sheard séjournera à Bordeaux jusqu'à fin mars 2012.
  • Gérard Berry (INRIA Sophia Antipolis, projet INDES)
Jeudi 24 novembre 2011
Systèmes embarqués complexes : défis et solutions envisageables
In the 20th century, an embedded system was most often thought of as a single piece of equipment driven by a single software program. Many efficient modeling, programming and verification paradigms have been developed in this setting: mathematical modeling using differential equations, reactive and synchronous programming, data-flow based signal processing, model-checking, etc. In the 21st century, systems are becoming much more complex. They mix hardware and software in subtle ways, involve a large number of sensors and actuators, become physically distributed, and may be remotely controlled by Web-based devices such as smartphones. Designing and verifying such systems raises many challenges that were independently known in particular areas but now need to be solved together. Here are some: understanding the relation between continuous and discrete time models, still quite unclear in the available mathematical modelers; understanding the ways in which synchronous and asynchronous communication could work in harmony; relaxing determinacy and timing constraints without losing too much predictability; being able to write full and faithful simulators of systems before building them, which is still a big problem in areas such as SoCs or transportation networks; developing methods to couple classical embedded systems with Web-based systems, which are of a very different nature. We will review some of the new problems posed in this area and some emerging solutions that could be applied to them, taking the notion of causality as the pivot of our reflections.
  • Bert Hartnell (Saint Mary's University, Halifax, Canada)
Jeudi 29 septembre 2011
Girth and the greedy algorithm
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.
  • Tom Mens (Université de Mons )
Jeudi 7 juillet 2011, à 10h
Analysing the evolution of social aspects of open source software ecosystems
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.
  • Bruno Salvy (Projet ALGO,INRIA Rocquencourt )
Jeudi 23 juin 2011
Preuves automatiques d'identités
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.
  • Frances Rosamond (Charles Darwin University, Darwin, Australia)
Vendredi 10 juin 2011 à 14h, en commun avec le GT Graphes et Applications
Computational Social Choice: Kemeny Scores and Parameterized Complexity
The multidisciplinary Consensus Problem: how independent agents reach a joint, collective decision, has applications in political resolution, but also important applications in Health (agreement on services), Image Processing (pixel value), Networks (agreement among processors), Auctions (agreement on bids), Search Engines (agreement on pages), among many others. The objects of study: opinions, rankings, observations, votes, gene sequences, sensor-networks in security systems or climate models, together with the presence of massive datasets, partial or uncertain information, distributed or interoperating decision makers, possibly over various time-frames, with the ability to share information at unprecedented speeds, make the Consensus Problem extremely complex.
This talk will describe in a general way some of the history of Computational Social Choice, and it will use Parameterized Complexity to investigate the structure of the Kemeny Score as the primary example of the multivariate approach.
  • Mike Fellows (Charles Darwin University, Darwin, Australia)
Mardi 7 juin 2011 à 11h, en commun avec le GT Graphes et Logique
A Short History of the Theory of Preprocessing
The talk will survey the theory of preprocessing for NP-hard problems that has emerged in recent years in the context of parameterized / multivariate algorithmics. Some general techniques for obtaining small kernels in polynomial time will be described, as well as new methods for obtaining lower bounds, recent results and research frontiers.
  • Julia Lawall (DIKU, University of Copenhagen)
28 avril 2011 (exceptionnellement à 11h)
Faults in Linux: Ten Years Later
Joint work with Nicolas Palix, Gael Thomas, Suman Saha, Christophe Calves, and Gilles Muller
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.
  • Yannis Avrithis (NTUA, Athens)
31 mars 2011
Image matching and visual search: local features and geometry
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.
  • Cornelia Falch (Fraunhofer Institute, Erlangen, Allemagne)
24 mars 2011
Spatial Audio Object Coding (SAOC) – an interactive perceptual coding standard
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.
  • Frédéric Guyon (Univ. Paris Diderot)
10 mars 2011
Méthodes bio-informatiques appliquées aux tumeurs cancéreuses à partir de données haut débit.
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.
  • Michele Abrusci (Roma III University, Italy)
16 décembre 2010
La logique non-commutative, dix ans après
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.
  • Ioannis Patras (Queen Mary University, UK)
4 novembre 2010
Recognition and Tracking of Human Actions in Image Sequences
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.
  • Prosenjit Bose (Carleton University, Canada)
21 octobre 2010
On Plane Geometric Spanners
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 >= 1 times the shortest path from x to y in G. The parameter t is commonly referred to as the spanning ratio, the dilation or the stretch factor. In addition to having bounded spanning ratio, it is desirable 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.
  • Vivien Quéma (LIG, Grenoble) et Gaël Thomas (LIP6, Paris)
7 octobre 2010, de 13h30 à 14h30
  • The Next 700 BFT Protocols (Vivien Quéma)
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).
  • VMKit: a Substrate for Managed Runtime Environments (Gaël Thomas)
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.
  • Paul Grace (Lancaster University)
23 septembre 2010
From Distributed Systems to Systems-of-Systems and Beyond: Challenges to Middleware
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.
  • Dietrich Kuske (LaBRI, équipe MF)
20 mai 2010
Automatic structures: Ramsey's theorem
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.
  • Valentin Feray (LaBRI, équipe CombAlgo) et Hicham Khalife (LaBRI, équipe LSR)
6 mai 2010
Présentation de nouveaux arrivants au 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.
  • Alain Cournier (LaRIA, Université de Picardie)
22 avril 2010
Algorithmique Stabilisante : Mesurer la qualité du service
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é.
  • Ahmed Mostefaoui (LIFC, Université de Franche-Comté)
15 avril 2010
Réseaux de capteurs multimédias : nouveaux challenges ou vieilles problématiques ?
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.
  • Jean-Baptiste Yunès (LIAFA, Université Paris Diderot)
8 avril 2010
Calculs, Automates Cellulaires et Grilles de calcul
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.
  • Xavier Blanc (Université Pierre et Marie Curie)
18 mars 2010, de 13h30 à 14h30
Gestion de la cohérence lors de la construction de logiciel
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.
  • Makoto Kanazawa (National Institute of Informatics, Japan)
18 mars 2010, de 14h30 à 15h30
Formal language theory inspired by natural language
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.
  • Jurek Czyzowicz (Université du Québec en Outaouais)
4 mars 2010
Le problème de rendez-vous asynchrone dans un graphe quelconque
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.
  • José Neuman De Souza (Federal University of Ceara)
18 février 2010
Self-organization and self-management in communications as applied to autonomic networks - Introduction and Some Research Issues
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.
  • Jean-Luc Rouas (LIMSI, CNRS)
11 février 2010
Description de documents audio multilingues : apport de la prosodie
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.
  • Romain Bourqui (LaBRI, équipe MaBioVis) et Paul Dorbec (LaBRI, équipe CombAlgo)
10 décembre 2009
Présentation de nouveaux arrivants au 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.
  • Pascal Costanza (Vrije Universiteit Brussel)
19 novembre 2009
Context-oriented Programming
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.
  • Hamid Asgari (Thales Research and Technology (UK) Ltd)
12 novembre 2009, de 13h30 à 14h30
Wireless Networking Research in TRT (UK)
Thales Research and Technology (UK) Ltd, or TRT (UK), is part of a global network of research centres situated in the UK, France, Netherlands and Singapore that support the Thales Group. Founded in 1958, TRT (UK) offers complete solutions, not only to the Thales Group, but also to a wide range of civil and defence customers.
This seminar provides you with an introduction to TRT (UK) and R&D topics that has been investigated in the company. In general, key application and technology areas investigated in TRT (UK) are: secure networks and applications, secure radio communications, advanced sensors and sensor networks, navigation and precise positioning techniques, algorithms and collaborative systems. Specifically, the seminar will focus on web enabled wireless sensor networks for building management; frequency planning, routing and provisioning in wireless mesh access networks, and QoS.
  • Pierre-E. Mounier-Kuhn (CNRS & Centre de recherches en Histoire de l'Innovation - Université Paris-Sorbonne)
15 octobre 2009, de 14h00 à 15h30
L'émergence d'une science : l'informatique en France (1950-1975)
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).
  • Henry Soldano (Université Paris 13)
9 juillet 2009
Apprentissage incrémental collectif de concept
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.
  • Dieter Kratsch (Université Paul Verlaine - METZ)
4 juin 2009, de 14h30 à 15h30, salle 178
Moderately exponential time algorithms
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.
  • Maurice Margenstern (Université Paul Verlaine - METZ, IUT de Metz)
14 mai 2009
Le problème du pavage dans le plan hyperbolique
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.
  • François Pellegrini et Sébastien Canevet
30 avril 2009, de 14h à 16h
Les problèmes de licences et de valorisation du logiciel en environnement académique
À 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.
Plus d'informations ici ou .
  • Pascal Ferraro (LaBRI)
2 avril 2009
Comparaison de Séquences et d'Arborescences, De la BioInformatique à la Musique
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.
  • Colette Johnen (LaBRI)
5 mars 2009
De l'espace mémoire nécessaire aux algorithmes auto-stabilisants
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.
  • Helen Purchase (University of Glasgow)
19 février 2009
Graph drawing algorithms: how good are they really?
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.
  • John Hamer (Visiting Researcher, University of Glasgow)
12 février 2009
"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.
  • Damien Magoni (LaBRI)
15 janvier 2009
Topologies de l'Internet
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.
  • Robert Strandh (LaBRI)
11 décembre 2008
Le langage Common Lisp
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.
  • Tamas Sziranyi (Computer and Automation Institute of Hungarian Academy of Sciences and Peter Pazmani Catholic University of Budapest)
20 novembre 2008
Bayesian inference for video geometry
Structure and objects in video images are often not known. If we search for camera registration or focused areas of these situations, some a priori knowledge was needed.
Now I present methods for finding geometrical structures in images or videos without any preliminary object definition:
  • First, a new motion-based method is presented for automatic registration of images in multi-camera systems, to permit synthesis of wide-baseline composite views by using an iterative Bayesian assignment of corresponding image areas. Another application of this co-motion inference is to find the vanishing-point position for planar reflected images or shadows.
  • A new automatic solution for finding focused areas based on localized blind deconvolution. This approach makes possible to determine the relative blur of image areas without a priori knowledge about the images or the shooting conditions. The method uses deconvolution based feature extraction and a new residual error based classification for the discrimination of image areas. We also show the method´s usability for applications in content based indexing and video feature extraction.
  • An MRF approach is also introduced for Bayesian Foreground and Shadow Detection in Uncertain Frame Rate Surveillance Videos.


Archives

Page mise à jour le 02/12/2013 à 10:34