LaBRI Seminar
The LaBRI seminar takes place approximately twice a month on Thursday, from 1:30pm to 2:30pm in the LaBRI amphitheater. The 50-minute presentation of the seminar is aimed at all researchers of the laboratory (including PhD students). The speaker has the delicate task of presenting a research area, while remaining accessible to a wide audience of computer scientists, without giving up one or two passages illustrating technical modes of reasoning in the field.
Useful information on how to reach LaBRI can be found here.
Contact : LaBRI director
Next seminar(s)
Previous seminar(s)
- André Rossi (Université de Bretagne-Sud, Lab-STICC)
April 25, 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)
April 11, 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.
April 4, 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)
March 28, 2013
Evolving networks: communities and reachability
The last ten years have witnessed an upsurge in the number of real world datasets modeled by graphs, also called complex networks. Recent studies in the field are focused on the definition of methods and algorithms to describe and study the evolution of such networks. During my talk I will discuss two of my research interests on this issue: community detection in evolving networks and reachability in delay tolerant networks.
The computation and tracking of evolving communities is generally used to follow the evolution of initial communities coupled with the evolution of the underlying network. I will introduce different approaches to tackle this problem and will show that they suffer either from strong instability issues or from high complexity which prevent their usage on large or highly evolving networks.
I will then talk about reachability in evolving complex networks with a special focus on delay tolerant networks. I will present the theoretical framework around temporal reachability graphs which allowed us to propose an algorithm for their efficient computation. I will finally demonstrate the interest of the temporal reachability graph concept by applying it to synthetic and real-life datasets.
- Sylvain Sené (IBISC, Université d'Evry ; et IXXI, ÉNS-Lyon)
March 21, 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)
March 14, 2013, at 11:00am, room 178 (joint seminar with 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)
March 7, 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)
February 21, 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)
February 7, 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)
December 6, 2012, exceptionally in room 178 at 4:30pm
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)
November 15, 2012
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)
September 13, 2012
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)
June 14, 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))
April 19, 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.
April 12, 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)
April 5, 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)
March 29, 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)
March 15, 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)
March 8, 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)
February 23, 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)
January 19, 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)
January 10, 2012, at 4pm.
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)
November 24, 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)
September 29, 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 )
July 7, 2011 at 10:00am
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 )
June 23, 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)
June 10, 2011 (at 2:00pm)
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)
June 7, 2011 (at 11:00am)
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)
April 28, 2011 (at 11:00am)
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)
March 31, 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)
March 24, 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)
March 10, 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)
December 16, 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)
November 4, 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)
October 21, 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)
October 7, 2010,
from 1:30pm to 2:30pm
- 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)
September 23, 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, MF team)
May 20, 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, CombAlgo team) and Hicham Khalife (LaBRI, LSR team)
May 6, 2010
Introducing newcomers in 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)
April 22, 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é)
April 15, 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)
April 8, 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)
March 18, 2010, from 1:30pm to 2:30pm
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)
March 18, 2010, from 2:30pm to 3:30pm
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)
March 4, 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)
February 18, 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)
February 11, 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, MaBioVis team) and Paul Dorbec (LaBRI, CombAlgo team)
December 10, 2009
Introducing newcomers in 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)
November 19, 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)
November 12, 2009, from 1:30pm to 2:30pm
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)
October 15, 2009, from 2:00pm to 3:30pm
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)
July 9, 2009
Sound Multiagent Incremental LEarning ;-)
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)
June 4, 2009, from 2:30pm to 3:30pm, room 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)
May 14, 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 and Sébastien Canevet
April 30, 2009, from 2pm to 4pm
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
là.
April 2, 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.
March 5, 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)
February 19, 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)
February 12, 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.
January 15, 2009
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.
December 11, 2008
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)
November 20, 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.