![]() |
Séminaire du LaBRI 2000-2001Le jeudi, à 14h, amphithéâtre du LaBRI. |
Les activités du groupe de recherche "Tolérance aux fautes et sûreté de fonctionnement" du LAAS-CNRS à Toulouse couvrent la tolérance aux fautes, l'élimination des fautes et la prévision des fautes. Leur finalité est de développer des méthodes et de les concrétiser par des outils.
Après un rapide survol des activités, la présentation se focalisera sur la problématique très actuelle de l'utilisation de logiciels exécutifs commerciaux (COTS) dans des systèmes sûrs de fonctionnement. Bien que ce type de stratégie présente un intérêt économique (réduction du coût de développement, du temps de mise sur le marché), la sélection des composants impose une évaluation quantitative de leur comportement en présence de fautes. Les travaux du LAAS ont conduit à la conception et à la réalisation d'un environnement de caractérisation par injection de fautes ainsi qu'au développement de techniques de protection complémentaires (notion de wrapper). La présentation décrira les grands principes ainsi que des exemples de résultats expérimentaux obtenus sur des cibles de type micronoyaux COTS. Les perspectives de ces travaux, en particulier en ce qui concerne les intergiciels de type CORBA, seront abordés en conclusion.
Dans cet exposé, nous étudierons les problèmes algorithmiques qui se posent dans le cadre de la réalisation de bibliothèques d'algèbre linéaire, quand on essaye de prendre en compte l'hétérogénéité des processeurs. Nous montrerons que le problème de l'équilibrage de la charge entre les processeurs, qui se résout très facilement dans le cas homogène avec une distribution bloc-cyclique, devient étonnamment difficile dans le cas hétérogène. Plus précisément, nous montrerons que les problèmes d'optimisation associés à différents modèles de communication sont tous NP-Complets. Pour tous ces problèmes, nous proposerons des algorithmes d'approximation garantis. Nous évoquerons (peut être) également les problèmes liés à la prise en compte de l'hétérogénéité du réseau d'interconnexion. Enfin, nous nous intéresserons à l'adaptation du modèle maître-esclave dans le cas de processeurs hétérogènes et de liens de communications en mode exclusif
L'énumération de graphes étiquetés trouve ses origines quand, vers 1880, A. Cayley compta le nombre d'étiquetages d'arbres pouvant être construits sur n sommets. Depuis, les graphes multicycliques connexes (possédant n sommets et n+k arêtes) ont été énumérés par E.M. Wright de manière exacte et asymptotiquement par E.A. Bender et al. Toutefois, les problèmes combinatoires soulevés par les énumérations des graphes connexes sans triangle (sans carré, ...) s'avèrent très difficiles et remontent à Harary et Palmer en 1973.
Etant donné un ensemble fini ξ de motifs interdits, le but de cet exposé est d'introduire une équation fonctionnelle (type conduction de la chaleur) satisfaite par les séries génératrices des graphes sans ξ. Nous montrerons sur quelques exemples, comment résoudre une telle équation et obtenir les séries génératrices des premiers multicycles sans ξ. Nous montrerons alors que ces séries génératrices se présentent toutes sous une forme particulière permettant de compter asymptotiquement les graphes connexes sans ξ avec n sommets et n+o(n1/3) arêtes. Nous verrons les conséquences de ces énumérations dans divers modèles de graphes aléatoires, notamment nous verrons que les approches énumératives pour résoudre ces problèmes peuvent donner des résultats d'une précision sans rivale. Pour conclure, nous verrons les perspectives engendrées par ces approches.
Nous commencerons par définir la carte topologique, un modèle topologique permettant de coder les frontières inter-pixels (inter-voxels) d'images segmentées en régions. Ensuite un algorithme optimal permettant de calculer cette carte à partir d'une image segmentée sera présenté.
En dimension 2, cette carte est équivalente au modèle défini par Brun et Braquelaire. Mais l'introduction de la notion de niveaux de simplification nous permet de donner une définition hiérarchique et intuitive de la carte topologique. Cette nouvelle approche nous a permis d'étendre aisément cette définition à la dimension 3 et même en dimension n.
L'algorithme optimal d'extraction de notre structure à partir d'une image se base sur la notion de précodes, configurations locales de pixels auxquelles on associe les traitements ad hoc. Les différents niveaux de simplification nous permettent d'obtenir une hiérarchie de précodes et de factoriser les traitements associés, réduisant ainsi la combinatoire du problème.
Ce modèle et cet algorithme ont fait l'objet d'une implantation complète dans une plateforme logicielle apportant une validation pratique des résultats théoriques.
Le problème traité dans cet exposé est celui de la transformation d'une expression rationnelle, avec multiplicité, en un automate, avec multiplicité. La méthode de dérivation des expressions (en anglais: derivatives) due à John Brzozowski doit être adaptée pour traiter de telles expressions et est transformée de telle sorte que la dérivée d'une expression par rapport à une lettre, ou par rapport à un mot, devient un polynôme d'expressions.
Les résultats antérieurs d'Antimirov s'interprètent naturellement dans ce cadre et se généralisent très directement. On a là encore un exemple où la prise en compte des multiplicités et la généralisation aux séries simplifient et éclairent des constructions et résultats sur les langages.
Travail réalisé en collaboration avec Sylvain Lombardy.
Une méthode pour optimiser la construction d'un réseau de télécommunications est présentée. Un modèle de programmation mathématique de grande taille a été conçu pour traiter ce problème. Chaque colonne générée est associée à un anneau. Une technique du type "branch-and-price" est employée. Des résultats numériques sont aussi présentés.
De plus en plus d'utilisateurs accèdent au WWW grâce à des calculateurs portables par l'intermédiaire de connexions sans fils comme le réseau GSM. Si une qualité appréciable de ce dernier est certainement l'étendue de sa couverture, ses principaux défauts sont probablement son coût d'utilisation et sa faible bande passante puisque son débit n'est actuellement que de 9,6 Kb/s. Il faut aussi constater que les calculateurs nomades utilisés peuvent avoir des performances très variées, allant des caractéristiques d'un portable haut de gamme aux possibilités réduites des petits assistants électroniques. Afin d'utiliser au mieux les ressources réseau, il peut être judicieux de mettre en oeuvre des mécanismes système et applicatifs adaptant les données à transférer aux possibilités du matériel utilisé. Le travail présenté, réalisé en 1998 au laboratoire LSR de l'IMAG (Grenoble), propose une approche originale de ce problème : l'utilisation d'agents mobiles travaillant directement sur les hôtes fixes du réseau, libérant ainsi les hôtes mobiles des tâches les plus lourdes telles que la collecte des pages WWW et la distillation de leur contenu.
GNU TeXmacs is a free what-you-see-is-what-you-get scientific text editor, which was both inspired by TeX and GNU Emacs. The program implements high quality mathematical typesetting using TeX fonts, but it is also provides a user friendly interface.
The high typesetting quality still goes through for automatically generated formulas, which makes TeXmacs suitable as an interface for computer algebra systems. TeXmacs also supports the Guile/Scheme extension language, which makes it possible to adapt the user interface to specific needs and even to extend the editor.
TeXmacs currently runs on PC's under Gnu-linux (a >200MHz processor and >32Mb of memory are recommended) and on sun computers. The editor is more or less compatible with the TeX system and we are improving our interface with computer algebra systems. Subsequently, TeXmacs should also support graphics and hypertext features.