1. Titre

Construction d'une application pour la visualisation
de treillis de Galois.

2. Responsable

Petko Valtchev

3. Contexte

La théorie des treillis de Galois ont largement démontré son potentiel comme
cadre formel pour la résolution d'un grand nombre de problèmes
pratiques ayant trait à la constitution d'abstractions au-dessus
d'un ensemble d'entités concrètes.
Par exemple, les treillis ont été appliqués avec succès à
la résolution d'un problème classique du génie logiciel OO,
qui est la réorganisation (refactoring) d'une
hiérarchie de classes existante. Celle-ci vise les définition d'un ensemble
hiérarchisé de classes abstraites maximalement factorisées
à partir d'une collection de classes instanciables.

Malgré l'intérêt grandissant que portent aux treillis de Galois
les communautés scientifique et industrielle, le nombre d'outils
dédiés à la manipulation de treillis, c'est-à-dire à la construction,
la visualisation, le maintient par rapport à l'évolution des données initiales,
etc., est négligeable. Cela est à expliquer par la complexité structurelle
du treillis qui résulte même d'un jeux de données de taille modeste,
qui pose des défis réels pour les mécanismes de stockage et l'exploration.

4. Constat

Un problème qui reste ouvert à nos jours est la visualisation ergonomique de
grands treillis. Pour palier à la confusion résultant du grand nombre
de noeuds et d'arrêts dans le diagramme de Hasse d'un treillis, plusieurs méthodes
ont été proposées, dont celle basée sur la technique des diagrammes imbriqués.
Un tel diagramme (nested line diagramme ou NLD en angl.) se base sur la séparation
d'un treillis en plusieurs treillis-facteurs de taille raisonnable qui seront
par la suite 'combinés' dans une structure graphique multi-niveaux.

La méthode NLD n'admet pas de réalisation effective que si les combinaisons
de treillis-facteurs puissent être calculées de manière rapide.
Très récemment nous avons développé une approche de fusion de treillis
qui permet, entre autre, ce genre de combinaisons.
Le but du stage sera de développer une application de visualisation
en s'appuyant sur les logiciels de fusion déjà existant.

5. Travail demandé

Les étudiants seront mis dans le contexte d'un projet réel
de développement logiciel
avec la conduite de toutes les phases du cycle de vie
(acquisition des besoins, analyse, conception, codage, tests, etc.)

Les tâches à accomplir incluent le
rassemblement et la complétion des algorithmes de fusion de treillis
déjà produits par mon équipe (code en Java).
Des aspects d'optimisation du code récupéré
(du point de vue de l'implémentation) pourraient être examinés aussi.

L'accent sera mis sur:
(i) la conception d'une méthode de visualisation
qui mette à contribution la fusion de treillis
pour les aspects d'imbrication entre diagrammes;
(ii) l'application de diverses techniques heuristiques
de visualisation d'ordres partiels dans le cas d'un diagramme
de Hasse simple (c'est-à-dire non-imbriqué).

Une interface graphique de manipulation ergonomique et une documentation détaillée
de l'ensemble du code produit seront également demandées.

6. Environnement de travail

Modélisation à l'aide du CASE tool Rose de Rational.
Programmation en Java (J2EE), utilisation des APIs Swings et, possiblement, JDBC.
Utilisation d'un environnement de programmation intégré, JBuilder.
Je fournirai les documentations nécessaires sur les APIs et Rose.
Équipe de 2-3 étudiants.

7. Contact:

Adressez-vous à Petko Valtchev <valtchev@iro.umontreal.ca> pour plus d'information.