Le nombre de croisements d'un graphe est le plus petit nombre d'intersections des arêtes deux à deux dans une représentation planaire du graphe. Nous donnons un encadrement à un facteur constant multiplicatif près du nombre de croisements des grilles k-dimensionnelles, k > 1. En particulier nous prouvons que le nombre des croisements d'une grille torique $C_n \times C_m$ est d'ordre $\Theta(nm)$, ce qui répond à une question posée par Harary il y a 20 ans. Nous montrons de plus que le nombre de croisements de la grille $\bigoplus_k X_n$ où $\bigoplus$ est une somme cartésienne et $X_n$ est un cycle ou une chaîne de n sommets, est d'ordre $\Theta(n^{2k-2})$.
Ces résultats étendent les résultats connus pour les nombres de croisements des grilles toriques $C_m\times C_n$, m < 7, et pour les hypercubes.
Georg Casari et Reinhard Schneider étaient, récemment encore, chercheurs dans le département 'bioinformatique' du Centre Européen de Biologie Moléculaire (E.M.B.L.). Ils viennent de créer la société LION bioscience A.G. qui offre des services dans le domaine du séquencage des acides nucléiques (ADN/ARN) et de l'analyse des séquences biologiques.
Avec le développement du séquencage systématique des génomes, les biologistes sont confrontés à de nouvelles questions. Il s'agit, en particulier, de prédire la fonction d'un gène à partir de sa séquence et non plus d'identifier le gène responsable d'une "fonction" observée expérimentalement.
Les orateurs feront une présentation générale des principales problématiques liées à l'étude du chemin qui conduit de la séquence du gène à sa fonction et des méthodes informatiques mises en oeuvre. Ils expliqueront plus en détail le processus de séquencage lui-même et le système d'information qu'ils ont developpé pour l'analyse des séquences.
Sizes of things are usually measured by numbers. Kolmogorov proposed to measure by a number the complexity of a thing. In Kolmogorov's theory, the complexity of a thing is the length of its shortest description. So one needs a notion of a "good", or optimal, language of description. Each descriptional language produces its own complexity measure, or complexity function. For a reasonable variety of descriptional languages, any two complexity functions almost coincide; more exactly, their difference is bounded by a constant. Therefore Kolmogorov complexity of a thing is defined up to an additive constant not depending on that thing. It is true if the "reasonable variety" of languages is fixed. If one changes that variety, then a new additive term appears in the definition of complexity, and that term is a logarithmic one. Hovewer, many facts are invariant, i. e. do not depend on that logarithmic term.
In introducing the notion of complexity, Kolmogorov was motivated by the idea to replace Shannon's information theory (based on the notion of probability) by a new theory based on the notion of computability. That idea was justified by a theorem (very recently obtained in Moscow) : the basic inequalities for Kolmogorov complexity are the same as for Shannon's entropy. Another attempt is to introduce some complexity meaning of propositional formulae (follow Kolmogorov's idea of 30-ies to interprete propositional logic as logic of problems); but there are more questions than answers.
Je présenterai quelques développements récents dans le traitement de modèles booléens d'analyse du risque à l'aide des diagrammes binaires de décision. En particulier, j'introduirai la notion de p-coupe minimale, une nouvelle notion d'implicant premier, qui formalise celle de scénario de pannes. Je montrerai comment on peut calculer efficacement les p-coupes minimales via les diagrammes binaires de décision. Je donnerai des arguments pratiques et théoriques en faveur de cette nouvelle notion. L'exposé se terminera par une présentation rapide des travaux menés au LaBRI en sûreté de fonctionnement.
Dans le cadre d'une étude comparative de rifts terrestres et vénusiens par télédétection radar, une méthode de reconstruction du relief à partir d'images radar à ouverture de synthèse a été mise au point. Cette méthode stéréogrammétrique s'appuie sur l'utilisation d'un filtre gradient original particulièrement adapté aux caractéristiques des images radar. Après une phase de validation sur des sites terrestres, la génération de modèles numériques de terrain de la surface de Venus a été entreprise et les premiers résultats seront présentés dans ce séminaire.
Nous montrerons au travers d'exemples ce que les systèmes de calcul formel savent bien faire, ce qu'ils font mal, et ce qu'ils ne savent pas faire du tout. Nous présenterons aussi les principales différences entre les sept systèmes généraux actuels (Axiom, Derive, Macsyma, Maple, Mathematica, MuPAD, Reduce), et donnerons quelques indications pour utiliser efficacement ces systèmes. Enfin, nous mentionnerons les avancées récentes réalisées au niveau algorithmique en calcul symbolique, et quelques défis à relever pour les dix années à venir.
La maintenance des contraintes d'intégrité est un sujet majeur en bases de données en particulier dans la perspective de la mise en place de systèmes d'information complexes. Deux classes de contraintes sont en général identifiées (bien que la deuxième subsume la première):
L'exposé considère des contraintes dynamiques. Différentes approches ont été proposées et développées pour maintenir la cohérence d'une base de données. Les systèmes commerciaux, en général, proposent des mécanismes de vérification très rudimentaires pour des contraintes simples. L'exposé présente une approche basée sur la génération de schémas transactionnels (programmes de mise à jour). Intuitivement, notre approche consiste à dériver automatiquement à partir d'un ensemble de contraintes un ensemble de primitives de mise à jour ainsi qu'une discipline de programmation (sous forme d'expression régulière). Les propriétés de ces schémas de transaction permettent d'assurer que le développeur d'applications utilisant ces primitives et respectant les règles de programmation écrit des programmes corrects d'une part (validité) et a la possibilité de programmer toute modification valide de la base de données (complétude).
Le problème de l'équivalence des automates à pile déterministes, ou EQ(D,D) en abrégé, est le problème de décision suivant: étant donnés deux a.p.d. A et B, a-t-on L(A) = L(B) ? c'est-à-dire, les langages reconnus par A et B sont-ils égaux ?
Ce problème a été posé par Ginsburg et Greibach dans leur article fondateur sur les automates à pile déterministes (1966) et a fait depuis lors l'objet de nombreux travaux. Nous exposons ici notre solution (positive) de ce problème.
Nous ferons un tour d'horizon des principaux problèmes de décision reliés à EQ(D,D); certains ne présentent qu'une analogie, d'autres sont clairement ( ou moins clairement) plus généraux et quelques uns sont exactement Turing-équivalents à EQ(D,D).
Puis nous décrirons le plan de notre solution et nous en expliquerons les idées essentielles :
L'objectif de ce séminaire est de présenter les activités scientifiques menées au LaBRI autour de la technologie Java. Comme le montrera l'exposé, ces activités relèvent de plusieurs domaines de recherche.
Dans une première partie, je passe en revue divers algorithmes
de reconnaissance de droites discrètes, culminant dans l'algorithme
de Rennesson-Debled. Je parle ensuite rapidement
de la relation entre droites discrètes, mots de Sturm et suites de
Beatty.
Dans une deuxième partie, j'expose quelques résultats sur les plans
discrets, et notamment les propriétés combinatoires découvertes par
Vuillon.
Dans la dernière partie, je présente le pavage apériodique
de Kari et Culik qui est lié aux mots de Sturm.
CalICo est un logiciel développé au LaBRI permettant la visualisation
d'objets combinatoires : arbres, graphes, permutations, pavages du plan,...
Ce logiciel permet en particulier l'animation d'algorithmes sur ces objets
a partir d'un langage L,
L dans {Maple, Mathematica, CAML, C,
L'équilibrage de charge est un point crucial dans l'utilisation des
machines parallèles. Je présenterai dans un premier temps le partitionnement
rectilinéaire qui constitue une solution à l'équilibrage des charges
quand les données sont soumises à des contraintes de localité (le
calcul associé à une donnée fait intervenir des données voisines).
Basée sur des travaux précédents sur l'algorithme élastique
d'équilibrage de charge, notre approche a consisté à proposer une
légère modification de l'algorithme original. Nous nous attachons en
particulier à apprécier la qualité de l'équilibrage de deux
heuristiques de partitionnement. Nous en avons également étudié la
complexité et la comparons avec des algorithmes optimaux. Les
résultats théoriques et expérimentaux sur des données aléatoires comme
sur des données réelles issues de l'imagerie médicale 3D démontrent
que la qualité de nos heuristiques est très importante, pour un temps
de calcul bien plus faible que pour les algorithmes optimaux. Nous
expliquons néanmoins les limites de notre stratégie et ses extensions
dans le domaine des réseaux hétérogènes de machines.
La suite de l'exposé tend à montrer la pertinence de ces approches à
un équilibrage dynamique de la charge, et en particulier dans des
applications de imagerie. En effet, lorsque la scène (en imagerie)
n'est pas figée et qu'un mouvement d'animation est utilisé ou observé,
il est important que les performances de nos heuristiques ne
s'écroulent pas pour une qualité d'équilibrage toujours constante.
Deux applications dans le domaine de la synthèse d'images ont été
retenues pour étudier ce comportement. Le premier exemple est celui de
la parallélisation d'un système de particules. Les particules sont
soumises à des forces externes, des collisions, des transmutations qui
engendrent un déséquilibre constant de la charge travail et une
évolution dynamique du monde calculé. De plus, la structure de donnée
très irrégulière nécessaire à la prise en compte efficace des
interactions entre particules rend le travail d'équilibrage délicat.
Une étude sur la fréquence d'équilibrage a été menée, qui, en fonction
des caractéristiques physique de la machine parallèle utilisée, permet
de prédire le nombre optimal d'itérations entre deux équilibrages de
la charge successifs. Des résultats sur plusieurs machines parallèles
donnent des facteurs d'accélérations important. Un système de
visualisation parallèle a été développé pour suivre l'évolution du
système de particules au cours de son calcul. Nous exposons également
le travail fourni dans le développement et l'extension d'une
bibliothèque parallèle portable et son extension à un environnement
graphique distribué. La seconde application étudiée est la prise en
compte de la cohérence entre images lors de la production d'animation
par l'algorithme du tampon en profondeur (zbuffer). Cette étude a
permis de gagner un facteur 3 sur le temps de calcul de chaque image
de l'animation. Ces deux exemples d'application de l'algorithme
d'équilibrage (système de particules, calculs d'animations) montrent
l'adéquation de notre approche aux problèmes posés par des structures
de données irrégulières.
La complétion linéaire est un mécanisme d'exécution des programmes
logiques basé sur une extension de l'algorithme de complétion de
Knuth-Bendix. Cette méthode introduit des techniques de simplification qui
apportent deux atouts importants par rapport aux mécanismes usuels de
résolution (en particulier la SLD-résolution) :
Nous proposons d'étendre cette méthode à différents aspects de la
programmation logique:
La parallélisation efficace et l'optimisation des méthodes de calcul
numérique travaillant sur des structures irrégulières creuses
nécessite une distribution équilibrée des calculs, tout en minimisant
la communication induite par le parallélisme.
Lorsque l'on représente les structures de données manipulées sous forme
de graphes, les différents problèmes de distribution de données
rencontrés peuvent s'exprimer comme des partitionnements sous contraintes
de ces graphes :
Lorsque l'on souhaite prendre en compte les caractéristiques de la machine
cible, c'est-à-dire que l'on suppose que son réseau de communication n'est
ni complet, ni homogène, ce problème devient celui du placement
statique.
Les principales méthodes de chiffrage (substitution, Vigenere,
DES, RSA) seront présentées et classées en termes d'automates finis.
Seront également présentées quelques méthodes de
décryptage (lecture sans connaissance de la clef).
Consulter le
serveur EDF, et le projet
Image, synthèse et analyse (CRIN/CNRS et INRIA Lorraine).
La simulation du comportement et du transport de la lumière à partir de
méthodes analytiques fait l'objet de recherches actives depuis de
nombreuses années. Ces recherches permettent aujourd'hui d'envisager des
applications de taille industrielle dans divers domaines : conception
architecturale, applications de réalité virtuelle exigeantes au niveau du
réalisme des images, ingénierie de l'éclairage. L'exposé présentera une
évaluation des algorithmes qui ont été mis en oeuvre dans ces applications,
et plus précisément les modèles et méthodes de calculs qui ont été
développés pour pouvoir simuler l'illumination d'édifices architecturaux.
Les expérimentations réalisées dans le cadre du projet d'illumination du
Grand Louvre et des Ponts de l'île de la Cité (Paris) seront également
présentées.
Au plus bas niveau des communications, le routage consiste à décider de
la route des messages transitant par les noeuds intermédiaires. Cette
décision est réalisée, à chaque noeud, de façon automatique par un
processeur dédié, appelé routeur. Le routeur choisit une route
pour les messages le traversant en fonction d'une information transportée
par le message (le plus souvent l'adresse du destinataire) et d'une
connaissance locale détenue par le routeur (table ou algorithme spécifique
de routage).
Le problème du routage compact est de déterminer des méthodes requérant
localement peu de connaissance, c'est-à-dire peu de bits mémoire dans chacun
des routeurs du réseau.
Dans cet exposé je présenterai une méthode particulière de représentation
compacte des tables de routage : le routage par intervalles. Ensuite j'exposerai
les différentes réponses apportées au problème suivant : existe-t-il
une méthode de routage compact applicable à tous les réseaux ?
Cet exposé présente les résultats obtenus à ce jour au LaBRI, dans le
cadre du projet Scotch, sur le placement statique et le partitionnement
de graphes.
Nous commençons par décrire l'algorithme de placement statique que nous
avons développé, qui est basé sur la bipartition récursive conjointe
du graphe source modélisant le programme et du graphe cible représentant
la machine parallèle, et nous montrons comment les résultats obtenus
s'appliquent au partitionnement et à la renumérotation.
Nous décrivons ensuite les possibilités de Scotch 3.2, une
distribution logicielle de partitionnement et renumérotation de graphes et
de placement statique, développée au LaBRI, qui implémente ces
méthodes.
Scotch peut placer efficacement n'importe quel graphe source valué
sur n'importe quel graphe cible valué en un temps linéaire par rapport
au nombre d'arêtes du graphe source et logarithmique par rapport au
nombre de sommets du graphe cible; il fournit des résultats de qualité
équivalente, voire supérieure, aux meilleurs outils actuellement
disponibles, tels Chaco et MeTiS.
A titre d'exemple, nous illustrons les capacités de Scotch dans
le cadre de la décomposition de domaines pour un code parallèle
d'aérodynamique utilisé sur Cray T3D au CEA/CESTA. Nous présentons
également quelques exemples de renumérotation de matrices.