Marie-Claude Gaudel
Test de logiciels
Cette conférence a pour objectif de presenter plusieurs problèmes et résultats de
recherche dans le domaine du test de logiciel.
Il s'agit d'un sujet difficile théoriquement et important pratiquement, sur lequel
il existe relativement peu de recherche.
Après un rapide rappel des définitions de base, on présentera rapidement les travaux
fondateurs de Goodenough et Gerhart (1975), et de Chow (1978).
L'exposé sera consacré ensuite à des recherches plus récentes sur le test de types
de données (Gaudel & al.), de protocoles (Brinksma, Tretmans,...), et sur les méthodes
probabilistes.
Plusieurs questions ouvertes seront présentées : comment tester des systèmes très
distribués, donc indéterministes ? Comment contrôler et observer des systèmes
complexes ? Comment évaluer la qualité d'une stratégie de test ? Sur quels critères
décider de l'arrêt d'une série de tests?
Philippe Robert
Algorithmes, Structures de Données et Modèles Probabilistes
On présente les aspects algorithmiques et mathématiques liés la résolution de
problèmes en informatique théorique et en mathématiques appliquées. À travers
plusieurs exemples liés aux réseaux de communication et aux systèmes distribués, on
s'attachera à mettre en évidence
- 1) La Conception Algorithmique;
Déterminer dans un cadre donné les algorithmes assurant le comportement optimal
d'un système pour un ensemble de critères fixé. Structures de données associées.
- 2) La Modélisation mathématique;
Décrire mathématiquement l'évolution dynamique des structures de données associées à une
classe d'algorithmes fixée. Prise en compte la nature statistique éventuelle de la
dynamique. Résolution des problèmes d'optimisation.
Les exemples traités concernent les réseaux téléphoniques, les systèmes distribués avec un
canal commun de communication, les algorithmes de séparation et le réseau Internet.
Xavier Goaoc
De la géométrie algorithmique au calcul géométrique
Le monde physique dans lequel nous vivons est essentiellement géométrique. Calculer sur des
objets du
monde réel implique donc souvent de manipuler des données géométriques. Le traitement algorithmique des
problèmes géométriques est ainsi devenu incontournable dans des domaines aussi divers que la CAO,
l'infographie, la robotique, la biologie moléculaire, les systèmes d'information géographiques,
l'astrophysique, la vision par ordinateur... Les progrès rapides des moyens de calcul, de communication et
de visualisation accentuent encore l'ubiquité du calcul géométrique.
Depuis bientot 30 ans, la géometrie algorithmique a pour objet d'établir des bases théoriques solides au
traitement algorithmique des problèmes géométriques. Cet exposé propose un tour d'horizon de cette
discipline et esquisse son évolution actuelle.
Serge Abiteboul
Xml, services Web et données actives
XML: le modele de données émergeant comme standard pour le Web
Services Web: vers des standards pour le calcul distribué
Active XML: des recherches dans ces directions
Denis Lugiez
Automates d'Arbres et Contraintes
Les automates d'arbres finis sont une généralisation des automates de mots
aux arbres et conservent les propriétés essentielles de ceux-ci: ils ont
donc de bonnes propriétés logiques et ensemblistes et une algorithmique
efficace. Ces caractéristiques amènent à de nombreuses applications
particulièrement pour le typage et l'analyse de programme. Mais manipuler
des arbres et non des mots donne une expressivité supplémentaire: la
structure de mot est unidimensionnelle (un mot est un fil) ce qui n'est pas le
cas des arbres. On peut alors se demander si on peut
étendre les automates d'arbres en rajoutant des opérations spécifiques
à l'objet sur lequel ils travaillent tout en gardant de bonnes
propriétés. Je vais présenter plusieurs extensions de ce modèle:
-
L'une consiste à rajouter des contraintes qui permettent d'identifier deux
sous-arbres (ou plus). Dans ce cas, l'extension mène à
l'indécidabilité pour le cas général, mais le cas d'égalité entre
frère reste décidable. Je ferai le lien avec la logique monadique du
premier ordre et certains types de contraintes ensemblistes. Je citerai au
passage certaines applications pour l'analyse de programme et la
démonstration automatique.
-
La seconde consiste à modifier l'objet. Au lieu de travailler sur des arbres
d'arité fixe (qu'on devrait appeler termes et non arbres), on considère
qu'un noeud peut avoir un nombre arbitraire (mais fini) de fils (qui sont
ordonnés ou non). Je donnerai le lien entre les langages obtenus et la
logique monadique du second ordre. Ce type de langage et les automates
correspondants sont très étudiés car ils servent à définir ou
comparer des langages de requête pour les documents XML.
-
Enfin nous verrons comment enrichir la seconde extension en ajoutant plusieurs
types de contraintes: formule de logique monadique, égalités, formule de
comptage,... La encore, l'étude des requêtes XML a souvent été la
source de ces travaux mais d'autres applications comme le typage ou la
vérification de protocoles doivent aussi être citées.
Dominique Rossin
Autour des permutations : Une introduction à la combinatoire
Apres une courte introduction aux permutations, nous
montrerons dans un premier temps quelques résultats
à propos de leur énumération.
Ensuite, nous étudierons le groupe des permutations
et plus précisement le groupe du Rubik's Cube.
Finalement nous esquisserons la preuve d'une conjecture
sur l'énumération des permutations à motifs exclus.
Christophe Fouqueré
Autour de la programmation logique
L'intérêt pour la programmation logique s'est trouvé relancé
depuis une dizaine d'années après la mise à jour de propriétés
structurelles des preuves en logique linéaire (polarisation,
focalisation).
Après un rappel des principes de base de la programmation logique par
clauses de Horn en logique classique, nous indiquerons comment la
logique linéaire a pû servir de support à une nouvelle forme de
programmation logique. Nous verrons comment en retour les propriétés
fondamentales à la base de ces avancées permettent une nouvelle
réflexion sur la structure de la logique en explicitant brièvement la
ludique de J.-Y. Girard.
Nous terminerons en mentionnant les domaines d'applications ainsi que
les développements récents en programmation logique concurrente en
adoptant une représentation par réseaux.
Anne-Marie Kermarrec
Diffusion fiable dans les systèmes large échelle
La communication de groupe, l'aptitude à diffuser une information à un
large nombre d'entités, est un
paradigme de communication particulièrement important et très utilisé
dans les systèmes et applications distribués.
L'échelle des systèmes distribués a subi une explosion au cours de
la dernière décennie en particulier due à l'avènement d'Internet, et
ce tant
au niveau du nombre d'entités impliquées dans un système que de leur
dispersion géographique. Cette évolution a rendu caduque bon
nombre de solutions adoptées dans des systèmes distribués de taille
plus modeste.
Pour répondre à ces besoins de passage à l'échelle, le paradigme de
communication pair à pair s'est imposé et se caractérise
essentiellement
par le fait que chaque pair participant est simultanément un client et
un serveur. Les systèmes distribués reposant sur ce modèle de
communication
sont robustes, auto organisants et assurent que la charge reste
équilibrée entre pairs.
Au cours de cet exposé, nous étudierons les algorithmes de diffusion
fiable dans les réseaux pairs à pairs existants, mis en oeuvre au
niveau applicatif.
À cette occasion, nous dresserons un panorama des systèmes pairs à
pairs existants et présenterons des protocoles de diffusion reposant
sur ces systèmes.
Contacter le Département InformatiqueDernières modifications : le 10/11/2008