![]() |
Séminaire du LaBRI 1999-2000Le jeudi, à 14h, amphithéâtre du LaBRI. |
Les microprocesseurs et les architectures parallèles lancent de nouveaux défis aux techniques de compilation. En présence de parallélisme, les optimisations deviennent trop spécifiques et complexes pour être laissées au soin du programmeur. Les techniques de parallélisation automatique dépassent donc le cadre traditionnel des applications numériques et abordent de nouveaux modèles de programmes, tels que les nids de boucles non affines, les appels récursifs et les structures de données dynamiques. Des analyses précises sont au coeur de la détection du parallélisme, elles rassemblent des informations à la compilation sur les propriétés des programmes à l'exécution. Ces informations valident des transformations utiles pour l'extraction du parallélisme et la génération de code parallèle. Cet exposé aborde principalement des analyses et des transformations avec une vision par instances, c'est-à-dire considérant les propriétés individuelles de chaque instance d'une instruction à l'exécution. Une nouvelle formalisation à l'aide de langages formels nous permet tout d'abord d'étudier une analyse de dépendances et de définitions visibles par instances pour programmes récursifs. L'application de cette analyse à l'expansion et la parallélisation de programmes récursifs dévoile des résultats encourageants.
L'objectif de cet exposé est de traiter le problème de la simulation d'éclairage pour des environnements complexes tels que des bâtiments composés de plusieurs centaines ou plusieurs milliers de pièces. Pour cela, je présenterai nos algorithmes, basés sur le principe "diviser pour règner", et j'aborderai les points suivants :
Work with Marcelo Walter and Daniel Meneveaux. The giraffe and its patches, the leopard and its spots, the tiger and its stripes are spectacular examples of the integration of a pattern and a body shape. We propose in this paper a system which combines and integrates a pattern generation system which can effectively deliver a variety of patterns characteristic of mammalian coats, and a body growth and animation system that can use experimental growth data to produce individual bodies and their associated patterns totally automatically. We use the example of the giraffe to illustrate how the models take us from a canonical embryo to a full adult giraffe in a continuous way, with results that are not only realistic looking, but also objectively validated. The flexibility of the system is demonstrated by examples of several big cat patterns, including an interpolation between patterns. The method also allows a considerable amount of user control to generate un-natural patterns and/or shapes and to animate the resulting body with the pattern.
Graph partitions generalize graph homomorphisms and encompass many graph theoretic partition problems including clique cutsets, split graphs, homogeneous sets, and skew cutsets. Recent results will be discussed, with emphasis on polynomial and quasi-polynomial algorithms for graph partitions, as well as some NP-completeness results. They are due to Tomas Feder, Sulamita Klein, Rajeev Motwani, Celina de Figueiredo, Yoshiharu Kohayakawa, Bruce Reed, and the speaker.
Dans une première partie, nous étudions une forme de stabilité pour une famille très générale de processus markoviens de type non diffusion connue dans la littérature comme les processus déterministes par morceaux (PDpM). Nous montrons que l'existence de loi de probabilité invariante pour cette classe de processus est liée à l'existence d'une mesure $\sigma$-finie invariante satisfaisant une condition de majoration pour un noyau markovien G défini à partir de la résolvante. Il est important de souligner le fait que ce résultat est obtenu sans aucune hypothèse sur le processus.
De plus, nous montrons qu'il existe une bijection entre l'ensemble des lois invariantes pour les PDpM et l'ensemble des mesures invariantes positives $\sigma$-finies de la chaine de Markov associée a G. Une question importante est de fournir des critères pour que le problème équivalent ait une solution. Nous donnons deux conditions qui s'inspirent du critère de Foster-Lyapunov dans le cas où la chaîne de Markov associée à G est récurrente ou de type Feller (au sens faible).
Dans une seconde partie, nous montrons que sous certaines hypothèses, le critère de Foster-Lyapunov fournit une condition nécessaire et suffisante pour assurer l'existence d'une mesure de probabilité invariante pour les chaînes de Markov de type Feller définies sur un espace métrique, séparable et localement compact.
Le développement de logiciels est soumis à des objectifs importants mais contradictoires de généralité et de performance. En effet, un programme doit pouvoir s'adapter à une grande variété de situations (par exemple, divers problèmes d'un domaine particulier, des contextes d'utilisation différents et des évolutions rapides du matériel). Cependant, ce même programme doit être aussi compact et efficace qu'un programme conçu pour une situation spécifique.
Cet exposé montre comment la spécialisation de programmes réconcilie les objectifs contradictoires de généralité et de performance en permettant la conception de programmes hautement adaptables sans perte d'efficacité.
Nous présentons différentes stratégies de conception de programmes adaptables et montrons comment la spécialisation de programmes permet de transformer automatiquement un programme adaptable, mais lent, en un programme efficace et spécifique. Nous illustrons cette présentation par des applications de taille réelle dans divers domaines comme les systèmes d'exploitation et les applications scientifiques.
La visualisation de données équipées de relations se ramène la plupart du temps à la visualisation de graphes. Ce problème évoque les dessins de graphes comme on peut en voir dans la plupart des ouvrages. Il existe plusieurs approches pour visualiser les graphes, comme les représentations polaires ou radiales, les représentations 3D, les "cityscapes", les emboîtements de rectangles ou de cubes, et l'utilisation de géométries alternatives. Les problèmes qui se posent et qui sont propres à la visualisation sont, par exemple: comment définir des algorithmes de dessins qui puissent s'appliquer aux graphes de grande taille ? comment définir des indices contextuels ou visuels pour la navigation de manière à aider l'utilisateur à guider son exploration des données, ou à ajuster le niveau de détail de la représentation, etc. ?
L'exposé reprend le contenu d'une présentation "STAR" à Milan (EG'99) et fait un tour d'horizon sur les techniques de dessins et de navigation dans les graphes, dans le contexte de la visualisation d'information.