Université de Montréal Faculté des Arts et des Sciences
Département d'Informatique et recherche opérationnelle
IFT6090, Automne 2000

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 5 septembre 2000 : 11h30
Adam Finkelstein (Princeton University), Three Applications of Computer Graphics in Cel Animation

Mardi le 19 septembre 2000 : 11h30
Matthias Felleisen (Rice University), How to Produce the Best Object-Oriented Programmers: By Teaching Program Design from the Beginning

Mardi le 26 septembre 2000 : 11h30     Séminaire conjoint DIRO-CRT
Alain Hertz (EPFL) A graph transformation which preserves the clique number

Mardi le 3 octobre 2000 : 11h30
Petko Valchev (INRIA, France et UQAM), Une stratégie basée sur la décomposition pour la construction de hiérarchies de concepts formels

Mardi le 17 octobre 2000 : 11h30
Jacqueline MORGAN (Università di Napoli "Federico II"), Optimisation à deux niveaux et régularisation de Tykhonov

Mardi le 24 octobre 2000 : 11h30
Michael McCord (Laboratoire IBM T.J. Watson), Slot Grammar and Machine Translation at IBM.

Mardi le 7 novembre 2000 : 11h30
Florence D'Alche-Buc (Université Pierre et Marie Curie, Paris), Machines à données de support et noyaux "sémantiques" pour la catégorisation de textes

Mardi le 14 novembre 2000 : 11h30
Beat Hirsbrunner (Universite de Fribourg, Suisse), The Welcome Project

Mardi le 21 novembre 2000 : 11h30
Stephen Thomas (National Center for Atmospheric Research, Boulder), Spectral Element Methods in Geophysical Fluid Dynamics

Jeudi le 14 décembre 2000 : 11h30, salle 3195   Horaire spécial
Philippe Galinier (Ecole Polytechnique) Programmer avec des contraintes par la recherche locale : le système CoLoSS (COnstraint LOcal Search Solver)

Three Applications of Computer Graphics in Cel Animation

Adam Finkelstein (Princeton University)

Traditional cel animation (the kind of animation for which Walt Disney is famous) combines several different forms of artwork to produce the final frames of the movie. Background scenery is laboriously hand-painted in exquisite detail, because it may be re-used for many frames. In contrast, foreground characters, which are re-drawn for every frame, are painted with flat, constant colors. Finally, tone mattes and shadow mattes, which are drawn for every frame, darken areas of the foreground and background (respectively) in order to anchor the movements of the character to the background. The goal of our project is to remove some of the tedious or difficult aspects of creating these forms of artwork, while retaining the expressive nature of the medium. In this talk I will describe three applications of 3D computer graphics in cel animation. First, we have developed an automatic method for designing a "multiperspective panorama" -- a single background painting that incorporates multiple views of a 3D environment as seen from a moving camera. When viewed through a small moving window, the panorama produces the illusion of 3D camera motion. Second, I will describe a method for applying a complex texture to a foreground character, as opposed to the flat, constant colors that are typically painted on an animated figure. Finally, we have devised a scheme for semi-automatic creation of tone and shadow mattes based on the hand-drawn foreground character. The work I will describe is the result of collaborations with Wagner Correa, Brian Fujito, John Hughes, Rob Jensen, Lena Petrovic, David Salesin, Craig Thayer, Lance Williams, and Daniel Wood.

Biography: Adam Finkelstein joined the faculty of the Computer Science Department at Princeton University in 1997. From 1990 to 1997 he lived the good life of a graduate student at the University of Washington, where he received an Intel Corporation Graduate Fellowship and drank a lot of coffee. From 1987 to 1990, Adam was a software engineer at TIBCO in Palo Alto, where he developed software for the financial industry and windsurfed in the San Francisco Bay. He was an undergraduate student at Swarthmore College (class of 87) studying physics, occasionally. Adam's research focuses on animation, non-photorealistic rendering, and the use of multiresolution analysis in computer graphics.

How to Produce the Best Object-Oriented Programmers: By Teaching Program Design from the Beginning

Matthias Felleisen (Rice University)

Current introductory curricula focus on the mechanical aspects of programming. That typically means the details of syntax, the use of libraries, and possibly some algorithmic concepts. Furthermore, these courses rely on complex, professional programming environments instead of tools that are made for, and grow with, beginners. Rice's TeachScheme! project aims to renovate and expand the computing curriculum at the introductory level. Our project combats this image of computing as a syntactic swamp through a new curriculum, a new perspective of beginner programming languages, and a matching programming environment. (1) The main focus of the curriculum is a series of program design recipes. These recipes teach students how to produce a program in a step by step fashion by focusing on classes of data from the beginning. (2) Instead of a single programming language, the first semester uses a series of small subsets of Scheme. Indeed, the beginner language is not much more than arithmetic and algebra (in prefix form) with a rich sublanguage of data. The intermediate language extends the beginner language and the advanced language extends the intermediate language in carefully designed ways. (3) Finally, DrScheme, our programming environment, implements this tower of languages and thus succeeds in protecting beginners from inadvertent interference from advanced portions of the language. This trio of instructional material, language tower, and programming environment frees students from details and allows them to focus on the systematic design of programs. Over the past few years, I have trained several colleagues in the use of this curriculum as well as close to 100 teachers and professors from small colleges. We have regularly conducted observations and evaluated the situation. The results suggest that a first-year college introduction based on Scheme and Java (in the second semester) produces far better object-oriented programmers than a full year of conventional introduction to programming. My talk will describe the essential components of the TeachScheme! project and will explain the exact results observed at Rice.

A graph transformation which preserves the clique number

Michael U. Gerber et Alain Hertz (Ecole Polytechnique de Lausane)

We introduce a graph transformation which preserves the clique number. When applied to graphs containing no odd hole and no cricket (a particular graph on 5 vertices) the transformation also preserves the chromatic number. Using this transformation, we derive a polynomial algorithm for the computation of the clique number of all graphs in a class which strictly contains diamond-free graphs. Furthermore, the transformation leads to a proof that the Strong Perfect Graph Conjecture is true for a class of graphs that strictly contains claw-free graphs.

Une stratégie basée sur la décomposition pour la construction de hiérarchies de concepts formels

Petko Valchev (INRIA, France et UQAM)

L'analyse de concepts formels étudie la structure induite par une relation binaire sur un couple d'ensembles, souvent identifiés comme les objets et les attributs. Composée par des couples de sous-ensembles fermés, appelés les concepts formels, qui sont naturellement ordonnés par l'inclusion, la structure vérifie les propriétés d'un treillis complet (treillis de Galois). Chacun des concepts étant engendré par des fortes corrélations locales entre objets et attributs, leur ensemble constitue un cadre bien adapté aux problèmes d'identification de groupements intéressants qui se posent fréquemment en fouille de données (segmentation de marché, analyse du panier du consommateur, etc.) ou en génie logiciel (ré-ingénierie d'applications par objets, migration de code légué, découverte de modules, etc.).

Nonobstant les avantages appréciables à l'approche par treillis (fondement mathématique rigoureux, complétude du résultat, robustesse des algorithmes) à l'heure actuelle, l'application massive de ses techniques sur des très grands jeux de données se heurte à des obstacles majeurs, telle la complexité de la structure des treillis obtenus, mais aussi le manque de résultats fiables sur les performances pratiques et la scalabilité des algorithmes existants.

Les diagrammes imbriqués constituent un outil de visualisation de grands treillis de concepts qui repose sur la division successive d'une collection de données en parties dont les treillis correspondants peuvent être combinés pour reconstituer le treillis global. Sur la base des structures liées à l'imbrication, nous avons conçu une stratégie d'analyse de concepts par décomposition du problème à résoudre. La stratégie repose sur des liens structurels entre le treillis global et le produit direct des treillis sur les parties, qui ont été mis en évidence. En particulier, nous proposons une caractérisation de l'image homomorphe du treillis global dans le treillis produit qui permet une détection rapide de ses éléments et par là une construction efficace du treillis entier.

Mis à part la définition d'un nouvel algorithme de type "diviser-pour-régner" construisant le treillis qui se prêterait facilement à une distribution du calcul voire à une parallélisation, ce travail fourni le support nécessaire pour un futur outil performant de visualisation de treillis par imbrication. De plus, ils constitue un cadre englobant pour les nombreuses stratégies de construction existantes et par là facilite leur comparaison, mais aussi leur application conjointe.

Optimisation à deux niveaux et régularisation de Tykhonov

Jacqueline MORGAN (Dipartimento di Matematica e Applicazioni Università di Napoli "Federico II")

On considère des problèmes d'optimisation à deux niveaux dans le cas où il n'y a pas unicité de la solution au niveau infèrieur et on répond à la question suivante: si on utilise une méthode de type Tykhonov pour régulariser le problème et si les solutions du problème régularisé convergent, à quoi convergent-t'elles? Question non seulement d'interèt théorique mais dont la réponse fournit une méthode constructive pour l'approximation d'un concept fondamental de solution en théorie des jeux dans le cas continu.

Slot Grammar and Machine Translation at IBM

Michael C. McCord (IBM T. J. Watson Research Center)

Slot Grammar (SG) is a grammatical theory and parser used for source analysis in several of IBM's MT systems. SG provides a deeper level of analysis than many current parsers, and delivers both logical-level and surface-level analyses of sentences in single, unified parse structures. Parsing is driven largely by *slot frame* descriptions of word senses in the lexicon; slots simultaneously represent logical and syntactic roles of word sense arguments. We are developing SGs for several languages, and aiming for very broad coverage, with large slot frame lexicons and linguistically adequate rule sets. SG aims to capture linguistic universals as much as possible, so that rules can be shared across as many languages as possible. Some of the generalizations apply to all languages, and others apply to families of languages. We are writing a single grammar module for all the Latin-based languages (currently covering French, Spanish, and Italian) with switches for the differences. SG is largely a knowledge-based system (with human-coded linguistic rules); but it also employs numerical scoring heuristics for disambiguation, and corpus analysis statistics can feed into this scoring system. I will briefly describe the way SG analysis is used in our MT systems, and illustrate the advantages that it offers for MT.

Machines à données de support et noyaux "sémantiques" pour la catégorisation de textes

F. d'Alché-Buc et G. Siolas (Laboratoire d'Informatique de Paris 6, université Pierre et Marie Curie, France)

L'algorithme d'apprentissage des machines à vecteurs de support peut s'appliquer à n'importe quelles données dès qu'elles peuvent être décrites sous forme de proximités par le biais d'un noyau. Cette remarque permet ouvre la porte à de nombreuses applications dans les domaines de la reconnaissance des formes où des représentations des données plus expressives que les vecteurs peuvent être utiles. La catégorisation de textes et plus généralement la recherche d'informations offrent un cadre prometteur pour tester ces idées. Nous proposons et discutons différentes définitions de noyaux entre documents en nous fondant sur la connaissance a priori fournie par un dictionnaire graphique sémantique (Wordnet pour l'anglais). De premiers résultats sur les bases Usenet et Reuters sont ensuite discutés. Enfin, nous indiquons les voies de recherche actuelles et futures, notamment la prise en compte du contexte dans les noyaux.

The Welcome Project

Beat Hirsbrunner (Universite de Fribourg, Suisse),

Le projet Welcome (www-iiuf.unifr.ch/pai) est un projet cadre des groupes de recherche PAI (Parallelism and Artificial Intelligence) et de Télécom de l¹Université de Fribourg (Suisse) pour la période 2000-03. Il est organisé autour de 3 pôles :

Dans cet exposé nous décrirons d¹une part les projets en cours de réalisation et d¹autre part nous montrerons nos résultats obtenus sur un système réel orienté vers des applications en robotique et qui illustrent l¹importante notion de coopération implicite (sans communication explicite).

Spectral Element Methods in Geophysical Fluid Dynamics

Stephen Thomas (National Center for Atmospheric Research, Boulder CO, USA)

Spectral element methods combine the accuracy and exponential convergence of conventional spectral methods and the geometric flexibility of finite element methods. In a spectral element discretisation, the computational domain is divided into rectangular or triangular elements, within which variables are approximated by a high-order polynomial expansion basis. The discrete equations are derived using a variational formulation of the equations and Gaussian quadrature rules. There are several practical advantages to using a new high-accuracy numerical method for geophysical fluid dynamics simulations over existing methods which lack inherent parallelism. In particular, the computations are naturally cache-blocked implying that the method is ideally suited to commodity RISC microprocessor architectures. Traditional spectral methods employ global spherical harmonic basis functions and therefore require O(N^3) data communication in the form of array transpositions. The Helmholtz problem arising from implicit time-stepping is trivial to solve in spectral space. However, the performance does not scale well on parallel machines with high latency or low-bandwidth networks. A spectral element general circulation model (GCM) demonstrates excellent parallel scalability at relatively low climate resolutions on distributed memory, distributed-shared memory and cluster type computers. Solution of the implicit Helmholtz problem is accomplished by a preconditioned conjugate gradient iteration using either deflation or Schwarz domain decomposition.

Programmer avec des contraintes par la recherche locale : le système CoLoSS (COnstraint LOcal Search Solver)

Philippe Galinier (Ecole Polytechnique)

Le système CoLoSS est un solveur (système générique de résolution) dédié à la résolution approchée de problèmes combinatoires. Le système propose un ensemble de primitives qui permettent d'exprimer différents types de contraintes. Ces primitives peuvent être utilisées comme des briques de base afin de représenter de nombreux problèmes. La résolution est effectuée par des méta-heuristiques de type recherche locale (tabou, recuit simulé, etc.) ou génétique hybride. L'utilisateur peut se servir des composants existants (contraintes, voisinages, méthodes de résolution), mais aussi ajouter de nouveaux composants. Des résultats expérimentaux partiels concernant plusieurs problèmes seront présentés :

Mots clés : optimisation combinatoire, solveur, méta-heuristiques, recherche locale, algorithmes génétiques, contraintes, CSP, programmation par contraintes