Département
d'informatique et de
recherche
opérationnelle
COLLOQUES du DIRO
Salle 6214, Pavillon André-Aisenstadt,
Université de Montréal
Nos colloques sont normalement le jeudi à 15h30,
mais exceptionnellement
certaines présentations ont lieu à des jours et salles différentes.
Pour avoir plus de détails sur chaque présentation,
appuyez sur le bouton rouge.
Si vous appuyez sur le nom du conférencier, vous obtiendrez soit sa page
web personnelle, soit celle du responsable de son invitation.
Page principale des colloques
Prochain colloque
-
Le jeudi 19 janvier 2006 : 15h30
-
Philippe Langlais,
Université de Montréal
: Quinze années de traduction statistique en 45 minutes
-
Le jeudi 9 février 2006 : 15h30
-
Abderrahim Benslimane, Université d'Avignon
: Réseaux ad hoc mobiles : routage et prise en compte de
l'énergie
-
Le jeudi 23 février 2006 : 15h30
-
Mathieu Blanchette, McGill University
: Reconstruction informatique de génomes ancestraux
-
Le jeudi 9 mars 2006 : 15h30
-
Anthony Bonato,
Wilfrid Laurier University
: The Web Graph
-
Le jeudi 16 mars 2006 : 15h30
-- Attention au local inhabituel: 5340
-
Godfried Toussaint,
McGill University
: Computational Methods for the Analysis and Generation of Musical
Rhythm Timelines
-
Le jeudi 23 mars 2006 : 15h30
-
Romain Rivière,
Université de Montréal
: Algorithmes de graphes pour l'analyse de séquences et structures
biologiques
-
Le jeudi 30 mars 2006 : 15h30
-- Attention au local inhabituel: 5340
-
Ivan Maffezzini,
Université du Québec à Montréal
: Le génie logiciel est-il une discipline ?
-
Le jeudi 13 avril 2006 : 15h30
-
Nazim Agoulmine,
Université d'Évry
: From Centralized Network Management to Autonomic Networking
Attention: Malgré le titre,
cette conférence sera donnée en français /
Despite the title, this talk will be given in French
-
Le jeudi 20 avril 2006 : 15h30
-
Dániel Marx,
Humboldt Universität (Berlin) et
University of Technology and Economics (Budapest)
: Closest Substrings Problems with Small Distances
-
Le jeudi 4 mai 2006 : 15h30
-
Sandeep Krishnamurthy,
University of Washington, Bothell
: Ten Trends That Will Reshape E-Commerce in the Next Five Years
-
Le lundi 8 mai 2006 : 15h30
-- Attention au jour inhabituel
-
David Chaum,
IACR Fellow
: The PunchScan Voting System:
Practical Voter-Verifiable Elections
-
Le mercredi 17 mai 2006 : 15h30
-- Attention au jour inhabituel
-
Christopher Raphael,
Indiana University
: Music Plus One
-
Le mercredi 24 mai 2006 : 14h30
-- Attention au jour, à l'heure et au local inhabituels: 5340!
-
Dominique Borrione,
Université Joseph Fourier de Grenoble
: Un outil pour la mise au point de systèmes embarqués, fondé sur les assertions
Quinze années de traduction statistique en 45 minutes
Philippe Langlais
Université de Montréal
Département d'informatique et de recherche opérationnelle
Le jeudi 19 janvier 2006 : 15h30, 6214 PAA
Comme le titre l'indique, je vais dresser
un état de l'art de la traduction automatique statistique. Je
décrirai la chaîne de traitement typique qu'il faut mettre
en place pour réaliser un moteur de traduction statistique
et m'emploierai à en montrer les limites. Je
présenterai des réalisations développées au
RALI autours de cette technologie et dresserai une liste de pistes qui
font en ce moment l'objet d'études poussées au sein de
notre communauté.
Plus de détails sur
Philippe Langlais
Réseaux ad hoc mobiles : routage et prise en compte de
l'énergie
Abderrahim Benslimane
Université d'Avignon
Laboratoire Informatique d'Avignon
Le jeudi 9 février 2006 : 15h30, 6214 PAA
Les protocoles ad-hoc sans fil sont constitués d'entités
autonomes pouvant collaborer entre elles pour rendre un service.
Ces entités peuvent être des PC portables, des palm pilotes
ou tout autre sorte d'ordinateur. Elles sont équipées
de moyen de communication sans fil, généralement de
norme IEEE 802.11. De même, elles sont mobiles. Cette mobilité
et ce manque d'infrastructure nuisent à l'établissement de
routage simple classique comme dans les réseaux filaires.
La première partie de l'exposé sera consacrée à la
présentation de quelques protocoles de routage connus dans
le groupe de travail MANET de l'IETF. La prise en compte de la
consommation d'énergie dans de tels réseaux est
primordiale vue que la capacité des batteries est
limitée. La deuxième partie présentera la
problématique de l'énergie et la réduction
de la consommation d'énergie, en particulier pour le
protocole de routage OLSR.
Plus de détails sur Abderrahim Benslimane
Reconstruction informatique de génomes ancestraux
Mathieu Blanchette
McGill University
School of Computer Science
Le jeudi 23 février 2006 : 15h30, 6214 PAA
Nous introduisons le problème de la reconstruction de génomes
ancestraux à partir des génomes d'espèces vivant aujourd'hui. Les
différentes étapes de reconstruction (alignement de séquences;
inférence des substitutions, insertions et délétions; inférence des
réarrangements du génome) sont décrites. Nous nous concentrons
particulièrement sur l'élégant problème algorithmique de l'inférence
d'insertions et délétions. A l'aide d'un argument basé sur la théorie
de l'information, nous démontrons ensuite pourquoi le génome de
l'ancêtre des mammifères euthériens (espèce vivant il y a plus de 70
millions d'années) est une cible de choix pour ce type de
reconstruction, permettant une reconstruction correcte à plus de 98%.
Nous concluons en décrivant quelques applications où les génomes
ancestraux permettent de jeter un éclairage sur la fonction de
différentes régions du génome humain.
La présentation sera accessible à des informaticiens sans connaissances
particulières en biologie.
Plus de détails sur Mathieu Blanchette
The Web Graph
Anthony Bonato
Wilfrid Laurier University
Département de mathématiques
Le jeudi 9 mars 2006 : 15h30, 6214 PAA
Much recent attention has focussed on the rigorous design and
analysis of models for the web graph and other massive self-organizing
networks. Models for these networks often incorporate copying in their
design, where a new node imperfectly duplicates some of the link structure
of an existing node. The motivation for copying models comes from the fact
that each node acts as an independent agent, which will base its decision on
how to link to the existing network on local knowledge. As a result, the
neighbourhood of a new node will often be similar to that of an existing
node. Consideration of copying models and their limiting behaviour have led
to the discovery of new connections between random graphs, graph
homomorphisms, vertex pursuit games, and infinite graphs.
This is joint work with Manuel Bodirsky, Peter Cameron, Dejan Delic,
Jeannette Janssen, and Changping Wang.
Plus de détails sur Anthony Bonato
Computational Methods for the Analysis and Generation of Musical Rhythm Timelines
Godfried Toussaint
McGill University
School of Computer Science and
Centre for Interdisciplinary Research in Music Media and Technology
Le jeudi 16 mars 2006 : 15h30, 5340 PAA
-- Attention au local inhabituel
Musical rhythm timelines are considered from the symbolic input
point of view. Several methods used to represent rhythms, as well as
measure rhythmic similarity are reviewed. New measures of rhythm
similarity are proposed, and algorithms for their efficient computation
are discussed. Analysing the histograms of inter-onset duration intervals
in rhythms yields interesting mathematical and computational problems, and
suggests methods for the automatic generation of new rhythms that have
specific properties. Viewing rhythms as sequences (or strings) of symbols,
suggests using tools from bioinformatics to perform phylogenetic analyses
of families of rhythms. Such tools allow us to “reconstruct”
“ancestral”
rhythms, which may be used in automatic music composition systems, or to
test theories of the evolution of musical rhythms. These applications will
be illustrated with examples from African, Latin-American, and Flamenco
music. The Flamenco research has been discussed several times
in the media recently. See for example articles in
McGill Reporter and
Cyber Sciences.
Plus de détails sur Godfried Toussaint
Algorithmes de graphes pour l'analyse de séquences
et structures biologiques
Romain Rivière
Université de Montréal
Institut de recherche en immunologie et cancérologie
et Laboratoire de biologie informatique et théorique, DIRO
Le jeudi 23 mars 2006 : 15h30, 6214 PAA
Mon travail porte sur le développement de méthodes pour l'étude des
motifs dans les structures biologiques. La premiere partie de la
présentation concerne les motifs dans les séquences d'ADN. L'ADN est
modélisé par un mot sur l'alphabet A, C, G, T et les motifs sont des
facteurs de ce mot. Je présenterai un nouveau modèle de séquences
aléatoires, permettant de détecter des motifs correspondant à des
signaux biologiques secondaires. D'un point de vue algorithmique, cela
fait intervenir différents problèmes sur les mots et les graphes dont
certains sont NP et #P-complets.
La deuxième partie de la présentation concerne l'étude de motifs dans
les structures d'ARN. L'ARN est modélisé par un graphe mixte, de dégré
borné, contenant un chemin hamiltonien connu. Dans ce cadre, un motif
peut être vu comme un sous-graphe induit connexe. Je montrerai comment
énumérer efficacement ces motifs à isomorphisme près et présenterai
quelques motifs trouvés à partir de ce travail.
Plus de détails sur Romain Rivière
Le génie logiciel est-il une discipline ?
Ivan Maffezzini
Université du Québec à Montréal
Département d'informatique
Le jeudi 30 mars 2006 : 15h30, 5340 PAA
-- Attention au local inhabituel
La question est loin d'être rhétorique et nous n'avons pas de
réponse. Nous avons par contre plusieurs questions et quelques
indications qui pourraient indiquer la voie d'une possible réponse.
Notre point de départ sera le génie logiciel tel
qu'évoqué par SWEBOK.
Nous poserons des questions sur les frontières, sur leur
étanchéité
et sur leur position ; sur les rapports avec d'autres disciplines
comme l'informatique et les mathématiques. Nous nous demanderons si,
au-delà des « meilleurs pratiques », une théorie est envisageable.
D'autres questions : une fois que l'informatique a pris en charge le
côté machine et le « génie des exigences » le côté
domaine, que
reste-t-il ? Les modes en génie logiciel ne sont-elles qu'une
facilité
commerciale et le symptôme d'un manque au niveau des fondements ?
Nous nous demanderons également si le vieux (et le nouveau) bon sens,
si mal partagé en génie logiciel, n'est pas le noyau dur de la
profession. Les quelques ébauches de réponses, biaisées,
sourdront de
la pratique quotidienne de réalisation de machines de contrôle en
temps réel.
Plus de détails sur Ivan Maffezzini
From Centralized Network Management to Autonomic Networking
Nazim Agoulmine
Université d'Évry, France
Laboratoire de réseaux et systèmes multimédia
Le jeudi 13 avril 2006 : 15h30, 6214 PAA
Attention: Malgré le titre
et le résumé,
cette conférence sera donnée en français /
Despite the title, this talk will be given in French
The huge proliferation of Internet technologies and services in almost all
existing electronic devices has made the control of such environment a
complex process unmanageable with existing approaches. This complexity has
reached not only large operators networks but also all LAN (Local Area
Networks), Wireless LAN, PAN (Personal Area Networks) environments. This
complexity of current systems and the expected even greater of emerging
ones had led the research community to reconsider existing approaches to
handle the challenges in terms of manageability and control. The key issue
of any new approaches is to free the network from a centralized-control
instrumented by human operators and allowing self decision-making. In
fact, the increasing complexity of the networks is reaching a level beyond
the human ability to control them. Consequently, the human intervention
became really the weak piece of the control and management workflow of
such environments. These emerging approaches referred as autonomic
networking is inspired from biological systems and aims to consider the
network as a biological system that has the capabilities of being
self-defining, self-healing, self-configuring, self-optimizing,
self-protecting, etc. Why biological system? Because nature has
intrinsically evolved to cope with such a complexity: heterogeneity,
scalability, unpredictability, uncertainty, etc. Therefore, following the
nature, it will be possible to design more reliable networks. These
networks are able to automatically adapt their behaviour and corresponding
configuration to varying contexts and circumstances to fulfil the goals
for which they have been deployed. This approach will have an important
impact on how network equipments, services and applications will be
designed, composed and managed. This presentation will cover the evolution
of network management and control architectures towards this new paradigm
of autonomic networking and present the ongoing directions in this area
from various labs worldwide including the University of Evry (LRSM Lab).
Attention: Malgré le titre
et le résumé,
cette conférence sera donnée en français /
Despite the title, this talk will be given in French
Plus de détails sur le laboratoire de Nazim Agoulmine
Closest Substrings Problems with Small Distances
Dániel Marx
Humboldt Universität (Berlin) et
University of Technology and Economics (Budapest)
Le jeudi 20 avril 2006 : 15h30, 6214 PAA
We study biologically-motivated pattern matching problems where the task
is to find a short string that appears (possibly with some errors) in
every input string. As the problem is NP-hard, we will investigate the
problem from the parameterized complexity point of view, which gives a
more detailed analysis of the hardness of the problem. The main focus
will be the case where the maximum error can be considered to be
small.
It turns out the problems we consider have nice combinatorial
structure
when the maximum distance is small, which has interesting algorithmic
consequences.
The talk will begin with a brief overview of parameterized complexity.
No previous knowledge is required.
Plus de détails sur Dániel Marx
Ten Trends That Will Reshape E-Commerce in the Next Five Years
Sandeep Krishnamurthy
University of Washington, Bothell
Business Administration Program
Le jeudi 4 mai 2006 : 15h30, 6214 PAA
E-Commerce continues to grow and evolve in interesting directions. Consider
a recent innovation by Amazon.co.jp.
It now allows
Japanese consumers to walk into a store, scan a UPC code into their cell
phone and access Amazon.com's
page for that product. Customers can easily
compare prices and if they like what they see, they can place an order with
Amazon.co.jp instantly.
The product is delivered to
the consumer's doorstep- most likely with zero shipping cost. This simple
example shows us how important E-Commerce has become in our daily lives. It
seems like we do everything online nowadays. We shop. We sell. We trade. We
communicate. We interact. We socialize. We consume content. Companies such as
Amazon,
eBay,
Google,
Yahoo! and
NTT DoCoMo
are household names. Exciting
new applications continue to sprout. In this talk, using important case
studies, I will highlight ten important trends that will reshape how
B2C (Business-to-Consumer) and B2B (Business-to-Business)
E-Commerce works in the next five years. These trends will challenge us
while enabling us to build a stronger online future at the same time.
Plus de détails
sur Sandeep Krishnamurthy
The PunchScan Voting System: Practical Voter-Verifiable Elections
Le lundi 8 mai 2006 : 15h30, 6214 PAA
-- Attention au jour inhabituel
So-called “encrypted vote” election systems hold unmatched promise for
allowing all voters to be able to verify that their votes have been
included in the final tally -- even if those running the election try to
cheat and have unlimited computing power. All previous approaches to
realizing such encrypted vote systems, however, have relied on
technology that proved to be too costly or required extraordinary
efforts by voters, while they also failed to meet various practical
requirements for public sector elections. Also, the sophisticated
cryptography relied on has proven difficult to explain.
PunchScan adapts the encrypted vote concept to optical scan ballots and
achieves a low cost, easy to use and to understand system that meets the
practical requirements. It works for mail in ballots and polling places
with or without automation. It allows “vote from any precinct,”
thwarting discrimination and intimidation. And it accommodates voter
disabilities beyond those accommodated by any current systems, while
offering such voters indistinguishable ballots and security and privacy
comparable to that for other voters.
The full system details will be presented for the basic system and
demonstrated with a complete mock election including voters from the
audience. Some examples from the current effort to build a student
voting system will be shown.
Plus de détails
sur David Chaum
Plus de détails sur les IACR Fellows
Music Plus One
Colloque du DIRO / MITACS / BRAMS (BRAin Music and Sound)
Christopher Raphael
Indiana University School of Informatics
Le mercredi 17 mai 2006 : 15h30, 6214 PAA -- Attention au jour inhabituel
I will discuss my ongoing work in creating a computer system that
simulates a sensitively conducted orchestra in a non-improvisatory
composition for soloist and orchestra.
My accompaniment system synthesizes a number of knowledge sources
including the musical score, on-line analysis of the soloist's
performance, and the musical interpretations demonstrated by both the
soloist and orchestra in rehearsal. I present a probabilistic model
--- a Bayesian Belief Network that represents these disparate
knowledge sources in a coherent framework.
During live performance, my system "listens" to the soloist by using
a hidden Markov model and conducts the orchestra through principled
real-time decision-making engine that incorporates all currently
available information for each decision. I will provide a live
demonstration of my system.
Plus de détails
sur Christopher Raphael
Un outil pour la mise au point de systèmes embarqués,
fondé sur les assertions
Le mercredi 24 mai 2006 : 14h30, 5340 PAA -- Attention au jour, à l'heure et au local inhabituels!
Parmi les travaux sur la conception de systèmes sur la puce,
le groupe VDS
de TIMA
a développé une méthode originale pour produire des modules matériels
qui surveillent ou produisent les valeurs de signaux, à partir de
spécifications logiques et temporelles en PSL. Un observateur se
déroule en parallèle avec la production des signaux, et ses sorties
permettent de savoir si le calcul de la propriété est en cours ou terminé.
Un générateur permet de restreindre les vecteurs de test à ceux qui
reproduisent le comportement de l'environnement du circuit testé.
Notre réalisation est basée sur une bibliothèque de composants primitifs,
et une méthode d'interconnexion, tous deux prouvés corrects vis à vis
de la sémantique de PSL à l'aide du démonstrateur de théorèmes PVS.
Les modules matériels résultants sont ensuite interconnectés au circuit
en cours de conception. Un prototype a été réalisé sur FPGA ;
l'efficacité est suffisante pour permettre d'émuler le circuit
exécutant son logiciel de base. Le surcoût des moniteurs et générateurs
en surface de circuit augmente proportionnellement au nombre d'opérateurs
de la formule PSL, et à la borne supérieure de l'intervalle temporel
d'observation après déclenchement de la propriété.
Plus de détails
sur Dominique Borrione
.