RESUME:
L'objectif des méthodes de visualisation d'information est d'aider
l'utilisateur dans son exploration ou analyse des données. Pour
cela, la visualisation exploite les capacités de traitement du
système visuel humain, en proposant des représentations
interactives de l'information. La recherche de nouvelles méthodes
et techniques de représentation et d'interaction est d'autant plus
nécessaire que le flux de nouvelles données à analyser et
comprendre va croissant. Notamment en biologie, où le
séquençage du génome et la systématisation des
expérimentations automatiques fournissent des centaines de milliers
d'éléments de données.
La visualisation de données mutli-dimensionnelles est un
problème très étudié en visualisation d'information. Dans
ces données, chaque élément est associé à un ensemble
d'attributs numériques (par exemple des données financières :
débit, crédit ...). L'objectif des méthodes dites de mise
à l'échelle (Multi Dimensional Scaling) est de plonger ces
données dans un espace en deux ou trois dimensions. Plus
précisément les méthodes MDS visent à corréler les
similarités entre les éléments (proximité des attributs)
avec des distances dans l'espace de plongement. Pour intégrer ce
calcul à un outil de visualisation il faut pouvoir trouver un
plongement satisfaisant dans des temps raisonables (moins que
quadratiques). Nous verrons comment réduire ce temps de calcul dans
des heuristiques basées sur une analogie physique.
Cette approche MDS a été utilisée dans de nombreux
domaines, notamment pour l'analyse financière. Actuellement les
applications à la biologie se multiplient, notamment dans des
outils de visualisation dédiés à la classification. En
particulier quand une ditance peut être caculée entre chaque
paire d'éléments (par exemple pour des abres
phylogénétiques).
Programme
Résumé des exposés
L'objectif des méthodes de visualisation d'information est d'aider
l'utilisateur dans son exploration ou analyse des données. Pour
cela, la visualisation exploite les capacités de traitement du
système visuel humain, en proposant des représentations
interactives de l'information. La recherche de nouvelles méthodes
et techniques de représentation et d'interaction est d'autant plus
nécessaire que le flux de nouvelles données à analyser et
comprendre va croissant. Notamment en biologie, où le
séquençage du génome et la systématisation des
expérimentations automatiques fournissent des centaines de milliers
d'éléments de données.
La visualisation de données mutli-dimensionnelles est un
problème très étudié en visualisation d'information. Dans
ces données, chaque élément est associé à un ensemble
d'attributs numériques (par exemple des données financières :
débit, crédit ...). L'objectif des méthodes dites de mise
à l'échelle (Multi Dimensional Scaling) est de plonger ces
données dans un espace en deux ou trois dimensions. Plus
précisément les méthodes MDS visent à corréler les
similarités entre les éléments (proximité des attributs)
avec des distances dans l'espace de plongement. Pour intégrer ce
calcul à un outil de visualisation il faut pouvoir trouver un
plongement satisfaisant dans des temps raisonables (moins que
quadratiques). Nous verrons comment réduire ce temps de calcul dans
des heuristiques basées sur une analogie physique.
Cette approche MDS a été utilisée dans de nombreux
domaines, notamment pour l'analyse financière. Actuellement les
applications à la biologie se multiplient, notamment dans des
outils de visualisation dédiés à la classification. En
particulier quand une ditance peut être caculée entre chaque
paire d'éléments (par exemple pour des abres
phylogénétiques).
Travail en commun avec Etienne Grandjean (Caen)
Dans cet exposé, on s'intéresse à la complexité de l'évaluation de
requêtes dans les bases de données.
On commencera par rappeler la problématique générale et des résultats du
domaine. Puis, on introduira un langage de requêtes basé sur la logique
du premier-ordre utilisant des fonctions unaires. Les formules de ce
langage peuvent-être vues (entre autres mais pas seulement) comme
exprimant des contraintes avec l'égalité ('='), l'inégalité ('!=') ou
des comparaisons ('<' ou '>') sur les attributs (i.e. fonctions de
projection) d'un ensemble de tuples.
On exhibe ensuite une notion de requêtes acycliques analogue à celle
introduite dans les BD relationnelles dans les années 80 mais basée sur
des notions de graphes et plus d'hypergraphes. Puis, on montre que toute
requête acyclique est évaluable en temps f(|Q|).|BD|.|Q(BD)| où f(|Q|)
est une fonction en la taille de la requête, |BD| est la taille de la
base de données et |Q(BD)| la taille du résultat de la requête (la
valeur précise de la fonction 'f' dépendant du fragment du langage
considéré).
Ces résultats ont deux applications principales.
La première est, qu'en se replaçant dans le contexte des BD "classiques"
on améliore quelque peu les bornes de complexité prouvées pour les
analogues relationnelles de ces classes de requêtes.
La seconde applications est que ce langage fournit un cadre uniforme
pour exprimer un certain nombre de problèmes algorithmiques
classiques : problème du sous-graphe acyclique, couplage
multi-dimensionnel, etc... Là aussi, dans certains cas, les résultats
permettent de retrouver ou améliorer les bornes existantes.
Enfin on discutera des extensions possibles de ce travail aux requêtes
de largeurs d'arborescence bornées ainsi qu'à l'interrogation de
document XML.
Les mots (finis ou infinis) de Lyndon sont les mots plus petits
dans l'ordre lexicographique que leurs suffixes propres. Plusieurs
études autour de ces mots font usage de morphismes de monoïdes
libres ayant des propriétés particulières comme la
préservation des mots de Lyndon ou de l'ordre lexicographique. Nous
présentons des caractérisations de ces morphismes et montrons
des relations entre ces différents morphismes. Quelques
applications sont également abordées en particulier pour la
décomposition en mots de Lyndon de certains mots infinis.
L'exposé présentera les travaux menés à Bourges en sécurité dans
le cadre du LIFO. Il présentera les solutions mises en oeuvre et les
perspectives en matière d'approches formelles.
Le contexte du travail est
la sécurité des systèmes à très large échelle et à très haut débit
notamment celle des clusters de calcul. Nous présentons d'abord une
solution de gestion d'une politique de sécurité qui permet des mises à
jour entièrement réparties de la politique. Cette solution est basée sur
une méthode de déploiement pour des systèmes permettant du Mandatory
Access Control. Cette technique est ouverte sur des techniques de preuves
de propriétés qui sont développées dans le cadre de l'ACI SATIN. Ensuite,
nous exposons une nouvelle architecture de détection d'intrusion qui se
base sur une politique répartie et permet de détecter des attaques
potentielles de la politique. Cette solution permet une intégration d'outils classiques
de détection d'intrusion. Elle offre des perspectives en matière de
preuves et de techniques statistiques d'apprentissage et de fouille de
données.
D'abord, il s'agit d'etudier les dessins de graphes avec une structure logique concise
intermediaire entre la carte (qui determine le dessin d'un graphe planaire)
et le sketch de Bruno Courcelle (qui determine le dessin en general).
Ici on retient quelles aretes se coupent mais pas l'ordre des croisements.
Pour un graphe complet cela determine le dessin a une suite de mutations
de triangles pres que l'on sait calculer.
En particulier, cela s'applique aux projections de graphes spatiaux codes
par des matroides orientes (un m.o. est une structure combinatoire qui donne
les positions relatives des points, sans tenir compte des distances).
L'inconvenient de ce codage est son volume (n4 signes de determinants au pire)
mais son avantage est que, une fois la structure memorisee, de nombreuses informations
s'en deduisent et des modifications s'y font tres simplement.
Finalement on a un codage combinatoire a deux niveaux
de la visualisation en perspective des graphes spatiaux :
lorsque le point de vue est coince dans les plans de la configuration,
le m.o. ne change pas et seuls des triangles mutent, et lorsque le point de vue
traverse un plan, seuls certains signes changent dans le m.o.
Dans leur longue série d'articles sur les mineurs de graphes, Robertson et
Seymour on défini une nouvelle classe de décompositions des graphes -- les
décompositions en branches -- pour obtenir une obstruction aux
décompositions arborescente. Cette obstruction a permis à Seymour et Thomas,
en calculant exactement la largeur de branches des graphes planaires, de
donner la meilleure approximation de la largeur arborescente des graphes
planaires.
Je montrerai comment unifier ces deux types de décompositions à l'aide
d'un nouvel objet combinatoire: les matriochkas. Ces matriochkas permettent
de mieux comprendre les liens mais aussi les différences entre les
décompositions arborescentes et les décompositions en branches. En les
utilisant, il est aussi possible de transférer des résultats d'une des
décompositions à l'autre. Je présenterai une nouvelle démonstration du
fait que la largeur arborescente d'un graphe planaire et celle de son dual
diffèrent au plus d'un, démonstration que j'ai obtenue de cette façon.
Cet expose cherche a montrer comment on peut généraliser au cas des
sytèmes dynamiques symboliques la plupart
des notions et résultats de la combinatoire des mots. On rappellera
d'abord la terminologie de
la dynamique symbolique. Nous établissons d'abord une généralisation de
l'inégalité de Kraft-McMillan pour des codes dans des systèmes sofiques.
Le cas d'égalité correspond à des codes
qui sont complets au sens que tout bloc admissible admet une
interprétation.
Ce résultat est utilisé pour montrer que le polynome naturellement associé à
un code complet fini dans un système sofique est factorisable par le
polynome
de l'alphabet. Ceci résoud un problème soulevé par Christophe Reutenauer
qui a prouvé le même résultat avec des hypothèses plus
fortes.
To be finite automaton (FA)-presentable seems to be a
rather strong restriction on a countable structure in a finite
signature: the domain can be represented by a regular set, in a way
that finite automata can also verify that the atomic relations hold
(where the strings representing elements are written one below the
other, using symbols in a power alphabet).
For instance, the additive group of integers is FA-presentable:
numbers are represented in binary, and the correctness of the usual
carry bit addition algorithm can be verified by a finite automaton.
This notion was introduced by Khoussainov and Nerode, 1995. (There and
elsewhere, FA-presentable structures are called automatic structures,
however, for groups, the term ``automatic'' refers to a different
concept.)
For each FA-presentable structure one can also give an
FA-representation of all definable relations, effectively in the
defining formula. So FA-presentable structures are closed under
interpretations, and each one has a decidable theory.
When considering an elementary class of effectively given structures,
a good measure for its richness is the complexity of the isomorphism
problem. For instance, Khoussainov, Nies, Rubin and Stephan (LICS
2004) have proved that for FA-presentable graphs or even successor
trees, isomorphism is as complex as possible ($Sigma1_1$-complete),
so the class is quite rich after all. With little effort, the result
carries over to partial orders, lattices, and commutative semigroups.
One the other hand, the class of FA-presentable infinite Boolean
algebras is very limited: Khoussainov, Nies, Rubin and Stephan have
shown that they are just the finite powers of the Boolean algebra of
finite or cofinite subsets of a countable set.
The general program is to locate each interesting class somewhere
between those two possibilities. I discuss some new results for
abelian groups and groups in general, mostly on the limiting side.
Groups: Examples of non-abelian FA-presentable groups include
infinite direct powers of a finite
non-abelian group, and GL_n(R) for some FA-presentable ring, e.g. the
Boolean algebra mentioned before, viewed as a ring. Each finitely
generated FA-presentable group is abelian-by-finite (Oliver and
Thomas). A recent improvement of this (Nies and Thomas): if G is ANY
FA-presentable group, then each f.g. subgroup of G is
abelian-by-finite. Using similar methods, each FA- presentable
commutative ring with 1 is locally finite.
Abelian groups: Known examples are (Z,+), the Prufer groups, and
Z[1/p] for a prime p, and the obvious derived examples (like finite
direct products). While the multiplicative group of rationals is
not FA-presentable (Khoussainov e.a.), it is a major open question
whether the additive rationals are
FA-presentable.
Un système probabiliste est dit ``auto-stabilisant'' lorsque,
quelle que soit sa configuration de départ,
il atteint (presque sûrement) le sous-ensemble
donné des configurations légales.
Cette propriété fournit notamment un
intéressant modèle de résistance aux pannes.
Il est essentiel de pouvoir non seulement garantir
la propriété d'auto-stabilisation d'un algorithme donné,
mais également d'estimer le temps d'auto-stabilisation.
Nous montrons ici comment des méthodes mathématiques, telles que
le "coupling", développées pour simuler des chaines de
Markov, donnent
de nouveaux critères d'auto-stabilisation, ainsi
qu'une meilleure analyse de la vitesse de convergence.
Nous donnons quelques exemples de telles
méthodes et diverses applications, comme l'analyse de l'algorithme
du dilemme du prisonnier itéré.
Omega est un détecteur de défaillances qui réalise une élection
ultime de leader. Omega est particulièrement intéressant car dans un système
asynchrone avec des pannes de processus par arrêt définitif, en présence
d'une majorité de processus corrects, il est le plus faible détecteur de
défaillances qui permet de réaliser le consensus.
Dans cet exposé, on présente des systèmes partiellement synchrones avec des
hypothèses très faibles de synchronisme et de fiabilité. On montre comment,
dans ces systèmes, on peut réaliser des implémentations efficaces de Omega.
Les travaux présentés ont été réalisés en collaboration avec
Marcos Aguilera, Hugues Fauconnier et Sam Toueg.
A snark is a "non-trivial" cubic graph which has no
3-edge-colouring. Snarks are related to several important and
long-standing conjectures such as the Cycle-Double Cover Conjecture,
5-Flow Conjecture, Grunbaum's Conjecture and others. In spite of their
simple definition and over a century lasting investigation their
properties and structure are largely unknown.
In this talk we concentrate on highly non-trivial snarks such as
irreducible snarks. Their characteristic property is that the removal
of any non-trivial edge-cut results in a 3-edge-colourable graph. We
show that every irreducible snark G can be decomposed into a
collection {H1,H2,...,Hn} of cyclically 5-connected irreducible snarks
such that G can be reconstructed from them as a repeated
dot-product. Moreover every irreducible snark has only one such
collection up to isomorphism and ordering. This fact suggests that the
role of cyclically 5-connected irreducible snarks can be compared to
that of the prime numbers in the factorisation of integers.
On considère la probabilité que deux entiers choisis au hazard soient premiers
entre eux. A partir de cet exemple, on se pose le problème de savoir dans quels
groupes le choix d`un élément a un sens. Ceux groupes sont importants dans
plusieurs domaines, par exemple dans la théorie des automates cellulaires.
le sujet de mon exposé porte sur des applications des problèmes de
flots dans des réseaux modélisant des réseaux de distribution de
fluide ou d'énergie et des réseaux de télécommunication ou de
transports.
*La première application* consiste en une analyse de sensibilité des
flots sur les réseaux, c'est à dire, l'étude de l'impact de la
variation de la capacité d'une ou de plusieurs arêtes sur l'ensemble
des valeurs de flot maximum entre toutes les paires de sommets du
réseau. Nous montrons comment détecter en temps réel l'ensemble des
flots dont la valeur est affectée par les différentes variations de
capacités dans le réseau. Nos études sont basées sur les arbres de
coupes de Gomory et Hu (De tels arbres reflétent les valeurs de flot
maximum entre toutes les paires de sommets dans un réseau non
orienté.)
*La deuxième application* concerne l'allocation de ressources dans un
réseau de télécommunication pour la satisfaction de requête
d'utilisateurs. Pour ce faire, nous étudions ce problème par le biais
de la tarification pour gérer la congestion tout en tenant compte du
comportement des utilisateurs et de la volonté de profit de
l'opérateur. Nous avons utilisé une approche bi-niveaux pour résoudre
le problème. Par la méthode du Lagragien augmenté, nous résolvons le
problème d'allocation de ressources en associant les multiplicateurs
de Lagrange aux prix sur les liens du réseaux. Nous utilisons ensuite
les conditions d'optimalité de Karush-Kuhn-Tucker pour vérifier si les
multiplicateurs (prix) sont uniques ou pas. Au cas de non unicité
nous montrons comment on peut résoudre un deuxième problème
d'optimisation juste sur ces multiplicateurs (prix) afin d'améliorer
le revenu sur le réseau.
*Mots Clès 1 * : réseaux de flots, flots paramétrés, analyse de
sensibilité, capacité critique, arc vital
*Mots Clès 2 * : programmation bi-niveaux, affectation du traffic,
tarification, contrôle de congestion
On definit une famille de groupes discrets qui contient les groupes finis, les groupes libres et
qui est stable par produit libre. On montre que toute marche aleatoire transiente et au plus proche voisin
sur le (graphe de Cayley du) groupe
admet une mesure harmonique Markovienne. Cette mesure est entierement determine par la resolution
d'un systeme d'equations polynomiales. Une consequence est que la
derive (vitesse de fuite) ou encore l'entropie de la marche
aleatoire est `explicitement' calculable. Ainsi, si les probabilites de transition sont rationnelles, la
vitesse de fuite est un nombre algebrique. Le resultat s'etend, modulo quelques amenagements, au cas des
monoides. Dans le cas du groupe libre, on retrouve des resultats
classiques essentiellement dus Dynkin et Malyutov (1961).
Ensuite, on montre l'effectivite du resultat en calculant explicitement les
vitesses de fuite sur certains groupes interessants: le groupe modulaire (Z/2Z*Z/3Z) ou les groupes
d'Artin a 2 generateurs. On s'interesse egalement au calcul explicite de
l'entropie et au lien entre entropie, derive et volume logarithmique
du groupe. Travail commun avec F. Matheus (U. Bretagne-Sud).
Un "ensemble indepéndant" dans un graphe est un ensemble de sommets tel
qu'aucun de ces sommets ne sont voisins l'un de l'autre dans le graphe.
Quelles propriétés possède un ensemble indépendant "typique" d'un graphe
donné? Par typique on veut dire choisi uniformément parmi tous ces
ensembles. Comment généraliser au cas d'un graphe infini, où il y a
infiniment d'ensembles indépendants?
Ces questions nous conduisent à considerer le "hard-body model" (modèle
des particules dures), qui trouve sa motivation aussi bien en informatique
qu'en physique statistique.
Je donnerai une introduction à ce modèle, en me concentrant sur les cas où
le graphe est un trellis carré ou un arbre.
De nombreux problèmes de fouille de données tels la
recherche des motifs fréquents maximaux, des dépendances
fonctionnelles ou d'inclusion dans les bases de données peuvent se
formuler dans un cadre théorique général [Mannila et al,DMKD,1/3,
1997]: Etant donné un langage fini $\cal L$, une base de données
$d$, un ordre partiel $\preceq$ sur l'ensemble des phrases du
langage et un prédicat anti-monotone $Q$, trouver les phrases les
plus specifiques qui vérifient le prédicat $Q$ dans $d$, aussi
appelé \emph{bordure positive}.
Deux types de parcours de l'espace des solutions seront abordés.
Le premier est dit par niveaux, des éléments les plus généraux (de
petite taille) aux éléments les plus spécifiques (de grande
taille). Par anti-monotonie, dès qu'un élément ne vérifie pas $Q$,
toutes ses spécialisations ne le vérifient pas non plus. Ce type
de stratégie est néanmoins mis en échec dès lors que la bordure
positive possède au moins un élément de grande taille.
Nous présenterons une alternative à ce type d'approche qui
consiste à : 1) appliquer une stratégie par niveaux jusqu'à un
niveau k, fixé par ailleurs. 2) caractériser la \emph{bordure
positive optimiste} à partir des éléments qui n'ont pas vérifier
$Q$ jusqu'au niveau $k$. 3) estimer l'erreur commise en calculant
une distance entre les éléments de la bordure optimiste et ceux de
la bordure à découvrir. 4) proposer un mode de parcours adaptatif
en fonction de cette erreur : soit "top-down", i.e. l'erreur
commise n'est pas trop grande, soit "bottom-up", i.e. en repartant
au niveau $k+1$.
Une application de cette stratégie a été menée pour la découverte
des dépendances d'inclusion. De part le coût d'un accès à la base
de données et d'une propriété d'interaction entre DF et DI qui
permet de justifier les "sauts optimistes" dans l'espace des
solutions, les résultats expérimentaux sur des bases de données
réelles et synthétiques montrent que les temps de réponse sont
toujours meilleurs que les autres approches testées, même pour les
bordures positives composés d'éléments de petite taille. Quelques
points ouverts seront donnés pour conclure cet exposé.
Les radix trees, utilisés en combinatoire des mots pour
stocker des langages, peuvent servir à des algorithmes de recherche
opérationnelle puissants. On peut les utiliser en effet pour la
recherche de plus court chemin dans un graphe dirigé et valué par des
entiers, la gestion de bases de données, la recherche de motifs dans
des images, une aide à la traduction automatique, la recherche
sophistiquée de mots dans un texte, les calculs de maillages et
d'efforts dans des représentations de surfaces, des problèmes
d'optimisation de flots. Ils peuvent en outre aussi servir à un
problème classique de combinatoire des mots : le calcul de complexité
de facteurs.
L'objet de cet exposé est de présenter quelques uns de ces algorithmes
et leurs performances.
Dans une première partie de cet exposé de synthèse, on passe
en revue divers mécanismes de génération de mots infinis. Ensuite, on
decrit quelques résultqts plus ou moins récents concernant les
répétitions, au sens de puissances de mots, qui peuvent être évitées
ou non. Enfin, on mentionne quelques problèmes ouverts.
Motivated by a rapidly growing interest in Combinatorics
on Words, as shown, for example, by the fact that in the latest
classification of Mathematical Reviews the topic is a topic of
its own, we give a survey on several highlights of the theory, as
well as point out some challenging problems. Some of the problems
are amazingly simple looking. Rather than trying to be exhaustive we
concentrate to a few problems according to the taste of the speaker;
After considering some aspects of repetition-free words, we then
concentrate to periodicity from different perspectives. For exmample,
we look for local peirodity conditions which would imply the global
periodicity, that is the fact that the word is ultimately periodic.
We also consider questions connected to word equations.Finally, a few
words about extensions of the theory of words into that of finite sets
of words are said.
Un système de réécriture est, pour un informaticien, un modèle
de calcul qui indique comment remplacer certains objets par
d'autres dans une certaine structure S. Ces systèmes se
présentent sous la forme d'un ensemble de règles qu'on peut
interpréter comme des lois d'évolution locale de S. Par
exemple une règle de la forme