Université de  
Montréal

Faculté des arts et des sciences

Département d'informatique et de recherche opérationnelle

  

COLLOQUES du DIRO  

Responsables 2005-2006:  Gilles Brassard et Pierre L'Écuyer

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

David Chaum
IACR Fellow
Chaum, LLC

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

Dominique Borrione
Université Joseph Fourier, Grenoble

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
.