Université de Montréal Faculté des Arts et des Sciences
Département d'Informatique et recherche opérationnelle
SEMINAIRES du DIRO
IFT6090, Hiver 2001

Felisa J. Vázquez-Abad et Marc Feeley

Salle 3195, Pavillon mathématiques et informatique, Université de Montréal

Nos séminaires sont d'habitude tous les mardis, mais exceptionnellement certaines présentations ont lieu à des jours et salles différentes.
Pour avoir plus de détailes sur chaque présentation, appuyer sur le bouton rouge.

Page principale des séminaires
Mardi le 16 janvier 2001 : 12h30
Karima Benslafa, Synchronisation Temporelle dans un Scénario Multimédia


Vendredi le 19 janvier 2001 : 11h30
Petko Valtchev, Construction flexible de hiérarchies de concepts formels


Mardi le 23 janvier 2001 : 12h30
Julie Vachon, COALA: un langage pour la conception de systèmes distribués fiables


Jeudi le 25 janvier 2001 : 11h30
Jean-François Perrot (Laboratoire d'Informatique de Paris 6) Traduction de méta-modèles


Vendredi le 26 janvier 2001 : 11h30
Alain Tapp (CACR, University of Waterloo) Complexité de la communication quantique


Mardi le 30 janvier 2001 : 12h30
Philippe Langlais, Intégration d'un modèle d'unités dans un prototype d'aide à la traduction


Vendredi le 2 février 2001 : 11h30
Vladimir Makarenkov (Sciences Biologiques, Université de Montréal) Reconstruction du processus d'évolution à l'aide d'arbres phylogénétiques et de réticulogrammes


Mardi le 6 février 2001 : 12h00
Yves Kodratoff (Université Paris-Sud), Extraction de connaissances à partir de textes (ECT = « Text Mining »)


Vendredi le 16 février 2001 : 11h30
Miklós Csürös (Yale University) Fast recovery of evolutionary trees with thousands of nodes


Mardi le 20 février 2001 : 12h30
Etienne Gagnon (Université McGill) SableVM, un cadre de recherche sur l'exécution du code-octet Java


Vendredi le 23 février 2001 : 11h30
Stefan Wolf (University of Waterloo) Information-Theoretic Cryptography: Linking Classical and Quantum Private-Key Generation


Mardi le 27 février 2001 : 11h30
Salah Sadou (Université de Bretagne Sud, France), Réutilisation dynamique de services


Mardi le 27 mars 2001 : 11h30
Doina Precup (School of Computer Science, McGill University), Off-Policy Temporal Difference Learning with Function Approximation


Vendredi le 6 avril : 11h00 salle 5441 PAA Séminaire conjoint CRT-DIRO
Steven Chamberland (Ecole Polytechnique de Montreal) Planification des reseaux IP fiables avec performance garantie


Mardi le 10 avril : 11h30 salle 5441 PAA Séminaire conjoint CRT-DIRO
Alain Veilleux (Université de Sherbrooke) Projet Mammouth


Mardi le 17 avril : 11h30
Flavien Serge Mani (Delta Informatique, Douala - Cameroun) Quel E-commerce pour le tiers monde ?


Mardi le 8 mai : 11h30
Brigitte Jaumard Optimisation des réseaux de télécommunications



Synchronisation Temporelle dans un Scénario Multimédia

Karima Benslafa (IRIN, Nantes)

Nous présenterons notre contribution au domaine de la création et de la présentation des scènes multimédias, en considérant un modèle étendu des réseaux de Petri. Notre objectif est de répondre aux "vrais" besoins des auteurs qui doivent exprimer la synchronisation temporelle des données multimédias (audio, vidéo, image et texte). De plus, le système doit offrir le moyen de stocker, simuler, valider et exécuter les scènes. Pour atteindre cet objectif, nous nous appuyons sur les notions suivantes:


Construction flexible de hiérarchies de concepts formels

Petko Valtchev (INRIA - UQAM)

L'analyse formelle de concepts et les treillis de Galois constituent une base théorique pour la résolution de problèmes ayant trait à la formation d'abstractions (concepts) à partir d'individus et provenant de domaines comme le génie logiciel ou la fouille de données (data mining). Cependant, les outils actuels de construction de treillis ne répondent que partiellement aux besoins des applications en matière de flexibilité. Ainsi, une pratique aussi usuelle que la décomposition d'un problème en sous-problèmes, par exemple, le développement dit par aspects ou par points de vue en génie logiciel, nous a emmenés à concevoir un cadre algorithmique pour la supporter. Au centre de ce cadre basé sur le découpage de relations binaires, nous présentons deux procédures originales de fusion de treillis partiels et les résultats structurels sur lesquels celles-ci reposent. Nous discutons de l'efficacité de notre approche, de son impact sur le domaine de l'analyse formelle ainsi que des applications qu'elle admet en modélisation, en ré-ingénierie ou en migration de code.

Les transparents de cette présentation sont disponibles.

COALA: un langage pour la conception de systèmes distribués fiables

Julie Vachon (EPFL - Lausanne)

Nous présentons COALA (COordinated Atomic action LAnguage), un nouveau langage pour la conception de systèmes distribués fiables basé sur deux principes: les "Coordinated Atomic Actions" (CA actions), un modèle de transaction avancé utilisé pour structurer la conception des systèmes; CO-OPN/2, un langage de spécification formelle orienté-objet (basé sur les réseaux de Petri et les spécifications algébriques) définissant la sémantique de COALA.

Nous expliquerons le concept de "CA action" à la base du langage COALA. Nous présenterons la syntaxe de COALA et les principes de sa sémantique en CO-OPN/2. Nous discuterons également d'une étude de cas, réalisée en COALA, portant sur la conception d'un service de vente aux enchères électronique. Nous terminerons en donnant un aperçu de nos projets futurs.


Traduction de méta-modèles

Jean-François Perrot (Laboratoire d'Informatique de Paris 6)

Résumé : La montée en puissance de l'approche du génie logiciel par méta-modélisation se traduit par l'émergence du standard MOF (Meta Object Facility) promulgué par l'OMG. Mais pour avoir de expériences substantielles, il faut encore se tourner vers divers outils de méta-modélisation qui existent depuis pluis longtemps, comme MétaGen ou MetaEdit. Cette constatation amène à comparer le MOF et les méta-formalismes utilisés dans ces outils (un méta-formalisme est un formalisme servant à définir des méta-modèles), et à chercher à traduire de l'un vers l'autre. Nous présentons une expérience de traduction du MOF vers le méta-formalisme de MétaGen. Ce dernier ne comporte pas de lien de généralisation, au contraire du MOF. Nous surmontons cette difficulté en réemployant une technique issue des bases de données. Grâce à notre dispositif, qui fait lui-même appel à la machinerie de MétaGen,un méta-modèle écrit en MOF est traduit automatiquement en un méta-modèle équivalent utilisable en MétaGen.


Complexité de la communication quantique

Alain Tapp (CACR, University of Waterloo)

Nous présenterons les ressources nécessaires aux calculs de fonctions dont les données sont distribuées. Par ressource, on entend par exemple la communication d'information classique, la communication d'information quantique, une source aléatoire, mais aussi et surtout l'intrication quantique. Nous discuterons de ce qui est possible de faire dans le monde classique et nous montrerons une série de tâches possibles avec des ressources quantiques mais que l'on peut prouver comme étant impossibles à faire autrement.

Aucune connaissance particulière en informatique quantique ne sera supposée.


Intégration d'un modèle d'unités dans un prototype d'aide à la traduction

Philippe Langlais (RALI-DIRO)

Nous présentons notre contribution au projet TransType, un prototype novateur d'aide à la traduction. Le moteur de traduction probabiliste embarqué dans cette application est premièrement décrit puis critiqué. Nous présentons ensuite un modèle de traduction capable de mettre automatiquement en correspondance des groupes de mots sources et cibles. Ce modèle offre des perspectives intéressantes dans des applications telles que l'extraction terminologique bilingue, la recherche d'information inter-langues ou encore les mémoires de traduction. L'intégration d'un tel modèle dans TransType est finalement discutée.


Reconstruction du processus d'évolution à l'aide d'arbres phylogénétiques et de réticulogrammes

Vladimir Makarenkov (Sciences Biologiques, Université de Montréal)

Un réticulogramme est un réseau de liens entre les espèces. Il représente un modèle formel pour visualiser le processus d'évolution réticulée. Je vais présenter une nouvelle méthode de reconstruction de réticulogrammes basée l'ajout de branches supplémentaires à un arbre phylogénétique classique. Nous présenterons notre programme T-Rex (tree and reticulogram reconstruction) qui est l'un des premiers programmes permettant de reconstruire et de visualiser des structures réticulées.


Extraction de connaissances à partir de textes (ECT = « Text Mining »)

Yves Kodratoff (Université Paris-Sud)

En début de séminaire, nous ferons une très courte démo du logiciel industriel TROPES de la société Acetic, dans le seul but d'illustrer l'importance de travailler avec la « bonne » taxonomie de concepts pour détecter les occurrences de concepts dans les textes . Nous ferons aussi une démonstration rapide du logiciel ROWAN que nous sommes en train de développer pour caractériser la position syntaxique d?un mot, position associée à une appartenance à un concept particulier.

Nous discuterons en détail le problème de la détection des associations (= implications à l'ordre 0), en insistant sur le fait que les méthodes classiques fondées sur une forte couverture conduisent à découvrir des associations sans intérêt. Cela nous amènera à discuter la méthode de l'intensité de l'implication (qui détecte aussi les associations à couverture très faible), et à la comparer aux mesures de dépendance, et à Bayes naïf. Nous discuterons enfin de la nécessité, de construire des réseaux bayésiens « non naïfs » à partir des données, et des problèmes particuliers posés par cette approche.


Fast recovery of evolutionary trees with thousands of nodes

Miklós Csürös (Yale University)

I will present a novel distance-based algorithm for evolutionary tree reconstruction. In the general Markov model of evolution, the algorithm recovers the topology of a tree with N leaves successfully with 1-o(1) probability from sequences with polynomial length in N. The algorithm runs in O(N^2) time using O(N) working space, which makes it the fastest known topology reconstruction algorithm with polynomial sample length requirements. The theoretical results are supported by simulation experiments involving trees with 500, 1895, and 3135 leaves.


SableVM, un cadre de recherche sur l'exécution du code-octet Java

Etienne Gagnon (Université McGill)

SableVM est une machine virtuelle conçue spécifiquement pour étudier des techniques de haut niveau menant à une exécution rapide du code-octet. Le coeur de cette machine est un interpréteur utilisant des techniques de pointe tout en étant facilement extensible et portable. Nous introduisons de nouvelles structures de données pour la représentation interne des instances d'objets et des tables virtuelles. Il en résulte (1) un coût d'invocation d'interfaces réduit à celui d'appel normal de méthode virtuelle, (2) un ramassage de miettes plus rapide, (3) une synchronisation légère améliorée et (4) une gestion efficace de la mémoire.
Sable CC, Sable VM.


Information-Theoretic Cryptography: Linking Classical and Quantum Private-Key Generation

Stefan Wolf (University of Waterloo)

Virtually all cryptographic schemes used today can, in principle, be broken by exhaustive key search. This is unsatisfactory both from a theoretical and practical viewpoint and motivates the search for a different quality of secrecy, based on information rather than computation. Shannon showed, however, that this type of confidentiality can only be achieved between parties who share an unconditionally secure key. Two important approaches to generating such a key are based on noise in classical communication channels and on the laws of quantum mechanics. We show that they are more closely related than previously believed.


Réutilisation dynamique de services

Salah Sadou (Université de Bretagne Sud, France)

La phase de déploiement d'une application ne se limite pas à la création de chaque instance de chaque composant de l'application. Il s'agit aussi de se connecter à des services offerts dans l'environnement d'accueil qui soient utilisables par des applications différentes.

Par ailleurs, après la phase de déploiement d'une application de grande taille, il est souvent difficile de l'arrêter pour prendre en compte des évolutions. Ces évolutions sont de différents types : Il peut s'agir de considérer de nouveaux besoins et d'étendre le système en place, comme il peut s'agir de prendre en compte de nouvelles contraintes de qualité de service en terme de disponibilité et de fiabilité accrue des composants. L'administration des applications à composants doivent donc fournir un support pour la reconfiguration dynamique, c'est-à-dire une capacité à modifier le système par ajout, suppression ou changement d'une partie de l'application à la volée tout en conservant la cohérence de l'application.

Nous nous sommes intéressés dans notre travail à ce point modeste de la (re)configuration dynamique, à savoir la réutilisation dynamique de services, (i.e. la capacité d'une application à se lier à l'exécution à des composants qui sont instanciés avant ou après le déploiement de l'application et qui proposent les services dont elle a besoin). La réutilisation dynamique doit permettre de se lier à n'importe quel objet proposant des services équivalents. Ce mode de réutilisation devrait aussi permettre une liaison à la volée entre des composants en dépit de l'incompatibilité de leurs protocoles d'interconnexion.


Off-Policy Temporal Difference Learning with Function Approximation

Doina Precup (School of Computer Science, McGill University)

In reinforcement learning, an agent generally learns from experience, that is, from the sequence of states actions and rewards generated by the agent's interaction with its environment. This data is affected by the decision-making policy used by the agent to select its actions, and thus the result of learning is often a function of the agent's policy. For example, the common subproblem of policy evaluation is to learn the expected future reward available to the agent from each state, when the agent is following its policy. In general, however, it can be useful to learn about policies that are different from the current behavior. This process is called off-policy learning.

Off-policy learning can speed up learning significantly, because the agent can use its experience to learn about many different policies in parallel, even though it can only follow one policy at a time. However, off-policy methods have been known to diverge when the value function is represented using a function approximator.

In this talk, I will introduce the first algorithm for off-policy reinforcement learning that is stable with linear function approximation. The main idea is to use importance sampling corrections in order to account for the difference between the agent's behavior policy and the policy about which it is trying to learn. Our convergence result is currently limited to episodic tasks.

This is joint work with Dr. Richard S. Sutton from AT&T Research Labs.


Planification des reseaux IP fiables avec performance garantie

Steven Chamberland (Ecole Polytechnique de Montreal)

Dans cette présentation nous traiterons de la planification des réseaux IP fiables avec performance garantie (en terme de la capacité). Dans un premier temps, nous ferons un survol rapide des mécanismes améliorant la qualité de service dans les réseaux IP comme IntServ, DiffServ, WFQ et MPLS. Par la suite, nous modéliserons le problème de planification des réseaux IP concerné en considérant l'utilisation du protocol OSPF pour le routage et du mécanisme FB-WFQ avec LQD pour assurer une capacité (en bps) minimale par flot IP. Un algorithme de résolution du modèle sera présenté ainsi qu'un exemple pratique.

Responsable - Organizer Bernard Gendron [1-514-343-7479]


Le projet Mammouth

Alain Veilleux (Université de Sherbrooke)

Le projet Mammouth est le nom du projet de grappe Linux, constituée de 1024 processeurs AMD/Intel, que le RQCHP veut implanter à Sherbrooke. Cette présentation portera sur la configuration proposée, les performances espérées, les applications potentielles et les collaborations à établir avec les autres membres du RQCHP (CRT, UdeM et CERCA).


Quel E-commerce pour le tiers monde ?

Flavien Serge Mani Onana (Delta Informatique, Douala - Cameroun)

Le tiers monde constitué des pays sous-développés, pauvres et fortement endettés, continue à courir derrière les grandes innovations socio-politiques, techniques et technologiques. Ici, les habitants restent convaincus de leurs capacités à côtoyer naturellement les progrès divers des pays dits du Nord. Globalisation ou mondialisation aidant, il faut se frayer un chemin pour atteindre un sommet sans cesse ascendant puisque le développement n'attend personne.

Dans cette optique, sous l'impulsion des Nouvelles Technologies de l'Information et de la Communication (NTIC), il faut quitter toute une civilisation pour entrer dans une autre; partir d'une économie industrielle basée sur la maîtrise de la matière pour une économie de services ayant pour centre d'intérêt l'intelligence.

De nos jours, l'Internet ravit la vedette en terme d'économie de services avec ses échanges, son partage, sa communication pleine, son commerce dit électronique, etc. Si le courrier électronique, la consultation des sites, la téléphonie connaissent un succès certain dans tous les pays en général, et ceux en voie de développement en particulier, un service comme le E-commerce reste surtout d'actualité. Il y a certes de sérieuses entraves à sa mise en place (absence de cartes de crédit, problèmes de communications, manque d'infrastructures adéquates, etc.), mais il est possible de mettre sur pied un système qui tienne compte des limites, naturelles ou non, observées, donc des réalités locales; et qui exploite à fond les petites potentialités qui s'offrent pour permettre la pratique du commerce électronique dans le tiers monde.


Optimisation des réseaux de télécommunications

Brigitte Jaumard (Génie Électrique et de Génie Informatique, Ecole Polytechnique)

Nous présentons trois problèmes d¹optimisation apparaissant dans la conception ou la gestion des réseaux de télécommunications. Le premier problème concerne l¹affectation de fréquences (FDMA) ou de PN-codes (CDMA) dans les réseaux de téléphonie cellulaire: nous discuterons et comparerons diverses approches de résolution exacte utilisant les techniques de génération de colonnes. Le deuxième problème concerne la conception de règles de Golomb optimales, aussi connue sous le nom de numérotation optimale d¹un graphe en optimisation combinatoire, et qui apparaît comme un problème de base dans la conception des codes doublement orthogonaux en télécommunications. Nous présenterons une famille générale de bornes inférieures permettant de comparer les diverses bornes inférieures de la littérature et nous discuterons de la recherche de la meilleure borne possible de cette famille. Enfin, le troisième problème concerne les procédures de contrôle d¹admission dans les réseaux 3G multimédias.