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.