Cette thèse s'inscrit dans la problématique de la comparaison de graphes. Nous proposons dans la première partie de ce manuscrit plusieurs algorithmes de recherche de motifs similaires dans de grands graphes. La seconde partie de cette thèse traite de l'étude des arborescences de fichiers, structure de données pour laquelle la méthode initiale de reconnaissance de motifs a été développée. Nous présentons un modèle stochastique pour la génération aléatoire de structure arborescentes, basé sur les observations de l'étude statistique des données réelles. Enfin, nous détaillons deux adaptations de l'algorithme de reconnaissance de motifs similaires à des applications particulières. La première concerne la reconnaissance d'objets extraits de la video basse résolution pour l'indexation grossière. La deuxième application a été développée pour la visualisation de l'évolution de projets logiciels.

When an aircraft is aerodynamically or structurally damaged in battle, it may not able to complete the mission and the damage may cause its loss. The subject of aircraft battle survivability is one of critical concern to many disciplines, whether military or civil. This thesis considered and focused on Computational Fluid Dynamics [CFD] predictions and experimental investigations into the effects of simulated battle damage on the low-speed aerodynamics of a fmite aspect ratio wing. Results showed that in two-dimensional [2d] and three-dimensional [3D] CFD simulations, Fluent's® models work reasonably well in predicting jets flow structures, pressure distributions, and pressure-coefficient Cp's contours but not for aerodynamic coefficients. The consequences were therefore that CFD prediction was poor on aerodynamic-coefficients increments. The prediction of Cp's achieved good agreement upstream and near the damage hole, but showed poor agreement at downstream of the hole. For the flow structure visualisation, at both weak and strong jet incidences, the solver always predicted pressure-distribution-coefficient lower at upstream and higher at downstream. The results showed relatively good agreement for the case of transitional and strong jet incidences but slightly poor for weak jet incidences. From the experimental results of Finite Wing, the increments for Aspect-ratio, AR6, AR8 and ARIO showed that as damage moves out towards the tip, aerodynamic-coefficients increments i.e. lift-loss and drag-rise decreased, and pitching-moment-coefficient increment indicated a more positive value at all incidence ranges and at all aspect ratios. Increasing the incidence resulted in greater magnitudes of lift-loss and drag-rise for all damage locations and aspect ratios. At the weak jet incidence 4° for AR8 and in all of the three damage locations, the main characteristics of the weak-jet were illustrated clearly. The increments were relatively small. Whilst at 8°, the flow structure was characterised as transitional to stronger-jet. In Finite Wing tests and for all damage locations, there was always a flow structure asymmetry. This was believed to be due to gravity, surface imperfection, and or genuine feature. An 'early strong jet' that indicated in Finite Wing-AR8 at 'transitional' incidence of 8°, also indicated in twodimensional results but at the weak-jet incidence of 4°. For the application of 2d data to AR6, AR8, and ARIO, an assessment of 2d force results led to the analysis that the tests in the AAE's Low Turbulence Tunnel for 2d were under-predicting the damage effects at low incidence, and over-predicting at high incidences. This suggested therefore that Irwin's 2d results could not be used immediately to predict three-dimensional.

Neuroscientists are increasingly overwhelmed by new recordings of the nervous system. These recordings are significantly increasing in size due to new electrophysiological techniques, such as multi-electrode arrays. These techniques can simultaneously record the electrical activity (or spike trains) from thousands of neurons. These new datasets are larger than the traditional datasets recorded from single electrodes where fewer than ten spike trains are usually recorded. Consequently, new tools are now required to effectively analyse these new datasets. This thesis describes how techniques from the field of Visual Analytics can be applied to detect specific patterns in spike train data. These techniques are realised in a software tool called Neurigma. Neurigma is a collection of visual representations of spike train data that are unified to provide a coordinated representation of the data. The visual representations within Neurigma include: an interactive raster plot, an improved correlation grid, a novel representation called the correlation plot (which includes a novel coupling estimation algorithm), and a novel network diagram. These views provide insight into spike train data, and particularly, they identify correlated patterns, called functional connectivity. Within this thesis Neurigma is used to analyse synthetically generated datasets and experimental recordings. Three main findings are presented. First, propagating spiral patterns are identified within recordings from the neonatal mouse retina. Second, functional connectivity is identified within the cat visual cortex. Finally, the functional connectivity of a large synthetic dataset, of 1000 spike trains, is accurately classified into direct, indirect and common input coupling.

Die komplexe Analysen großer Datensätze stellt in der Informationsvisualisierung eine zunehmende Herausforderung dar. Mit Hilfe von Magic Lenses wird die teilweise unübersichtliche Visualisierung dieser Datensätze lokal manipuliert und vereinfacht. Dabei spielen besonders der Umfang an Filterfunktionen und wie sie verändert werden können eine Rolle. Die Vorteile eines Multitouchdisplays im Vergleich zu herkömmlicher Maus- oder Keyboardinteraktion kommen dabei zum Einsatz. Es treten jedoch stetig Probleme bei der Adaption bisheriger Menüdesigns auf. Da Magic Lenses über Menüs parametrisiert werden sollen, stellt sich die Frage welche Menü- und Interaktionsarten besser dazu geeignet sind. In dieser Arbeit wird ein Multitouch-basiertes Kontextmenü für Magic Lenses evaluiert. Es befindet sich direkt am Linsenrand und ist kompakt jedoch neuartig. Es wird die Konkurrenzfähigkeit zu einem speziell für die Studie entworfenen und implementierten klassischen, globalen Menü getestet. Dieses ist für Nutzer vertrauter, aber distanziert sich von der Linse. Die Ergebnisse werden anschließend unter quantitativen und qualitativen Punkten zusammengefasst und ausgewertet. Es zeigt sich, dass klassische Menüs mit Touchinteraktion performanter waren. Das Multitouch-basierte Kontextmenü war allerdings bei den Probanden beliebter und wurde für die Arbeit mit Linsen bevorzugt. / The complex analysis of huge data sets is an increasing challenge in information visualization. With the help of emph{Magic Lenses} the somtimes confusing visualization of those data sets is being locally manipulated and simplified. Especially the amount of filter functions and how they can be altered matter. The advantages of multitouch displays in comparison to conventional mouse and keyboard interaction are used. However, there occur continual problems with the adaption of existing menu designs. Since emph{Magic Lenses} have to be parameterized with those menus the question arises which kind of menu and interaction are more fitting. In this work we evaluate a multitouch based context menu for emph{Magic Lenses}. It is located directly at the lens and compact but new to users. We test its competitiveness to a classical global menu specifically designed and implemented for this study. Users are more familiar with it but it is distanced from the lens. Finally, the results are summarized and analyzed under quantitative and qualitative points. It turns out that classical menus with touch interaction performed best. The multitouch-based context menu though was more popular with probands and was preferred for the work with lenses.

Thèse numérisée par la Direction des bibliothèques de l'Université de Montréal.

Nous proposons une approche semi-automatique pour la rétro-ingénierie des diagrammes de séquence d’UML. Notre approche commence par un ensemble de traces d'exécution qui sont automatiquement alignées pour déterminer le comportement commun du système. Les diagrammes de séquence sont ensuite extraits avec l’aide d’une visualisation interactive, qui permet la navigation dans les traces d'exécution et la production des opérations d'extraction. Nous fournissons une illustration concrète de notre approche avec une étude de cas, et nous montrons en particulier que nos diagrammes de séquence générés sont plus significatifs et plus compacts que ceux qui sont obtenus par les méthodes automatisées. / We propose a semi-automated approach for the reverse engineering of UML sequence diagrams. Our approach starts with a set of execution traces that are automatically aligned to determine the common behavior. Sequence diagrams are then extracted with the help of an interactive visualization, which allows navigating though execution traces and performing extraction operations. We provide a concrete illustration of our approach with a case study, and show in particular that the resulting diagrams are more meaningful and more compact than those extracted by automated approaches.

Le développement du logiciel actuel doit faire face de plus en plus à la complexité de programmes gigantesques, élaborés et maintenus par de grandes équipes réparties dans divers lieux. Dans ses tâches régulières, chaque intervenant peut avoir à répondre à des questions variées en tirant des informations de sources diverses. Pour améliorer le rendement global du développement, nous proposons d'intégrer dans un IDE populaire (Eclipse) notre nouvel outil de visualisation (VERSO) qui calcule, organise, affiche et permet de naviguer dans les informations de façon cohérente, efficace et intuitive, afin de bénéficier du système visuel humain dans l'exploration de données variées. Nous proposons une structuration des informations selon trois axes : (1) le contexte (qualité, contrôle de version, bogues, etc.) détermine le type des informations ; (2) le niveau de granularité (ligne de code, méthode, classe, paquetage) dérive les informations au niveau de détails adéquat ; et (3) l'évolution extrait les informations de la version du logiciel désirée. Chaque vue du logiciel correspond à une coordonnée discrète selon ces trois axes, et nous portons une attention toute particulière à la cohérence en naviguant entre des vues adjacentes seulement, et ce, afin de diminuer la charge cognitive de recherches pour répondre aux questions des utilisateurs. Deux expériences valident l'intérêt de notre approche intégrée dans des tâches représentatives. Elles permettent de croire qu'un accès à diverses informations présentées de façon graphique et cohérente devrait grandement aider le développement du logiciel contemporain. / Nowadays, software development has to deal more and more with huge complex programs, constructed and maintained by large teams working in different locations. During their daily tasks, each developer may have to answer varied questions using information coming from different sources. In order to improve global performance during software development, we propose to integrate into a popular integrated development environment (Eclipse) our new visualization tool (VERSO), which computes, organizes, displays and allows navigation through information in a coherent, effective, and intuitive way in order to benefit from the human visual system when exploring complex data. We propose to structure information along three axes: (1) context (quality, version control, etc.) determines the type of information; (2) granularity level (code line, method, class, and package) determines the appropriate level of detail; and (3) evolution extracts information from the desired software version. Each software view corresponds to a discrete coordinate according to these three axes. Coherence is maintained by navigating only between adjacent views, which reduces cognitive effort as users search information to answer their questions. Two experiments involving representative tasks have validated the utility of our integrated approach. The results lead us to believe that an access to varied information represented graphically and coherently should be highly beneficial to the development of modern software.

Mémoire numérisé par la Division de la gestion de documents et des archives de l'Université de Montréal.

De nos jours, les applications de grande taille sont développées à l’aide de nom- breux cadres d’applications (frameworks) et intergiciels (middleware). L’utilisation ex- cessive d’objets temporaires est un problème de performance commun à ces applications. Ce problème est appelé “object churn”. Identifier et comprendre des sources d’“object churn” est une tâche difficile et laborieuse, en dépit des récentes avancées dans les tech- niques d’analyse automatiques. Nous présentons une approche visuelle interactive conçue pour aider les développeurs à explorer rapidement et intuitivement le comportement de leurs applications afin de trouver les sources d’“object churn”. Nous avons implémenté cette technique dans Vasco, une nouvelle plate-forme flexible. Vasco se concentre sur trois principaux axes de con- ception. Premièrement, les données à visualiser sont récupérées dans les traces d’exécu- tion et analysées afin de calculer et de garder seulement celles nécessaires à la recherche des sources d’“object churn”. Ainsi, des programmes de grande taille peuvent être vi- sualisés tout en gardant une représentation claire et compréhensible. Deuxièmement, l’utilisation d’une représentation intuitive permet de minimiser l’effort cognitif requis par la tâche de visualisation. Finalement, la fluidité des transitions et interactions permet aux utilisateurs de garder des informations sur les actions accomplies. Nous démontrons l’efficacité de l’approche par l’identification de sources d’“object churn” dans trois ap- plications utilisant intensivement des cadres d’applications framework-intensive, inclu- ant un système commercial. / Nowadays, large framework-intensive programs are developed using many layers of frameworks and middleware. Bloat, and particularly object churn, is a common per- formance problem in framework-intensive applications. Object churn consists of an ex- cessive use of temporary objects. Identifying and understanding sources of churn is a difficult and labor-intensive task, despite recent advances in automated analysis tech- niques. We present an interactive visualization approach designed to help developers quickly and intuitively explore the behavior of their application with respect to object churn. We have implemented this technique in Vasco, a new flexible and scalable visualization platform. Vasco follows three main design goals. Firstly, data is collected from execu- tion traces. It is analyzed in order to calculate and keep only the data that is necessary to locate sources of object churn. Therefore, large programs can be visualized while keeping a clear and understandable view. Secondly, the use of an intuitive view allows minimizing the cognitive effort required for the visualization task. Finally, the fluidity of transitions and interactions allows users to mentally preserve the context throughout their interactions. We demonstrate the effectiveness of the approach by identifying churn in three framework-intensive applications, including a commercial system.

Nous proposons tout d'abord une étude de plusieurs problèmes de l'algorithmique distribuée. Nous fournissons un modèle formel appliqué aux réseaux de diffusion anonymes. Dans ce modèle, nous caractérisons les graphes dans lesquels il est possible de résoudre l'énumération et l'élection. Cette caractérisation se base sur la notion d'homomorphisme de graphes. Nous proposons deux algorithmes dont la complexité est polynomiale et qui améliorent les complexités exponentielles connues jusqu'à présent. Dans un second temps, nous étudions le problème du calcul de l'état global et nous introduisons la notion de weak snapshot. Nous montrons qu'il existe des solutions pour ce problème dans les réseaux anonymes. Nous présentons plusieurs résultats concernant le calcul de l'état global en liaison avec des applications telles que le calcul de points de reprise, la détection de la terminaison ou encore le calcul d'une cartographie du réseau. Dans un cadre plus pratique, nous présentons la conception, le développement et l'implémentation des algorithmes proposés pour le calcul de l'état global au sein du logiciel de simulation et de visualisation ViSiDiA. / In this thesis, we first present a study of several problems in the field of distributed algorithms. We provide a formal model that relies on anonymous networks. In this model, we characterize graphs in which it is possible to solve enumeration and leader election problems. This characterization is based on graph homomorphism. We introduce two algorithms with polynomial complexities that improve existing works with exponential complexities. On the other hand, we study the snapshot problem and we introduce the notion of weak snapshot. We show that there exist solutions for this problem in the context of anonymous networks. We present several results about distributed snapshots that deal with checkpoint and rollback recovery, termination detection or the cartography computation of a network. In a practical aspect, we present the conception, the development process and the implementation of these distributed snapshot algorithms within the simulation and visualization software ViSiDiA.