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 Informatique
Dernières modifications : le 10/11/2008