Mémoire numérisé par la Direction des bibliothèques de l'Université de Montréal.

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

L'objectif de ce mémoire de maîtrise en informatique est de présenter une méthode générique de gestion des tests d'unités logiciel utilisable par la très petite entreprise (2 à 10 programmeurs). Cette méthode répond aux contraintes que rencontrent ces entreprises : faible budget et développement/maintenance en plusieurs langages informatiques ou environnements. De même, cette méthode est simple à implémenter et à enseigner aux nouveaux programmeurs. Pour ce faire, ce document regroupe les informations pertinentes menant à la compréhension de la place qu'occupent les tests dans les différentes méthodes de développement de logiciel. De même, il montre un échantillonnage de plusieurs méthodes usuelles de tests qui peuvent être utiles aux programmeurs. La méthode de gestion de tests développée dans ce document est basée sur une utilisation des logiciels de tests et sur les tests de régression. De plus, cette méthode est générique car elle s'adresse à tous les langages informatiques de par l'utilisation des logiciels de tests et dû au fait que ('implémentation du prototype du logiciel de gestion est en langage Java. Cette méthode crée une hiérarchie des tests à effectuer en fonction des projets, du logiciel et de ses multiples variantes de paramètres utilisés. La méthode prévoit la possibilité de lancer en séquence les tests d'un logiciel ou de lancer simultanément des logiciels avec chacun leurs tests. De même, elle permet de simplifier la création de fichiers étalons et elle inclut plusieurs options qui gèrent leur comparaison avec des fichiers textuels ou binaires. Une de ces options est particulièrement intéressante. Il s'agit de la possibilité d'inclure des outils qui peuvent servir à valider les fichiers de sortie ou encore transformer un fichier binaire en fichier texte pour visualisation. La méthode prévoit la transmission de rapports de tests aux divers intervenants dans l'organisation de l'entreprise de même que l'archivage de ces rapports. La méthode proposée se veut une nouvelle approche simple et réaliste au problème de la gestion des tests dans les très petites équipes de développement informatique.

Une des problématiques dans le domaine des systèmes multi-agents est la reconnaissance de plan. Celle-ci peut être vue comme le fait de recevoir une série d'actions, en entrée, puis d'inférer le but poursuivi par l'acteur de cette série. Dès lors, les résultats obtenus peuvent être employés à de multiples fins. Par exemple, nous pouvons prendre le cas des domaines de la médecine (pour assister des personnes en perte d'autonomie) ou de l'aviation (pour le pilote automatique). L'objectif général de ce travail de recherche est d'élaborer un ensemble d'outils servant de base à la conception d'un modèle de reconnaissance de plan fondé sur la logique de description. Cette logique est une extension des réseaux sémantiques pour la représentation des connaissances. Elle est basée sur la relation de subsomption qui est une méthode d'inférences pour la classification de concepts à travers une ontologie. Le but étant de ramener la problématique de la reconnaissance de plan à un problème de classification. En somme, nous proposons un modèle de classification de plan d'action, servant de support au processus de la reconnaissance de plan. La démarche consiste, en premier lieu à clarifier la notion de reconnaissance de plan, ainsi, que les éléments essentiels, la constituant. Puis, lors d'une deuxième étape de redéfinir ses éléments à travers la logique de description. Ce mémoire se veut une première phase d'un projet de recherche beaucoup plus large, visant le développement d'un projet d'assistance aux personnes à mobilité réduite. Il doit donc être considéré comme un pas en avant vers la réalisation de ce projet d'envergure.

Ce mémoire porte sur la fragmentation de graphes et ses applications au génie logiciel. Après une présentation du domaine d'application et de la problématique, nous traitons d'un certain nombre d'algorithmes de fragmentation. Ces algorithmes, issus de la littérature scientifique, sont analysés selon notre problématique. Pour répondre à nos besoins, nous introduisons la fragmentation par noyaux. Cette approche produit une partition en identifiant des sommets jugés centraux à des sous-graphes possibles afin de construire des noyaux. Les différents sommets du graphe sont ensuite distribués dans la partition selon leur relation avec les noyaux. La dernière partie de ce mémoire aborde la mise en oeuvre et l'utilisation de la fragmentation par noyaux. La méthode est appliquée au génie logiciel. Nous obtenons des partitions sur des graphes de systèmes logiciels. Les partitions sont analysées pour trouver les points forts et les défaillances de la fragmentation par noyaux, ainsi que les améliorations possibles.

Les problèmes d'optimisation combinatoire faisant partie de la classe de problèmes NP-difficiles sont abordés et traités de nombreuses manières dans la littérature. Lorsqu'il s'agit de résoudre ces problèmes, les méta-heuristiques sont des algorithmes bien adaptés aux conditions de résolution rencontrées dans les domaines pratiques. Elles offrent un compromis intéressant entre la qualité des solutions et le temps nécessaire à leur obtention. C'est en partie pourquoi le domaine des méta-heuristiques a pris beaucoup d'ampleur depuis les dernières années. De nombreuses méthodes y ont été introduites, dont l'Optimisation par Colonie de Fourmis (OCF) (Ant Colony Optimization) qui est un algorithme dont le comportement est basé sur celui des fourmis réelles. Depuis son introduction au début des années '90, l'OCF s'est montrée efficace pour la résolution de nombreux problèmes. Parmi les problèmes d'optimisation combinatoire, on retrouve le Problème d'Ordonnancement de Voitures (POV) (Car Sequencing Problem). Ce problème théorique présente une problématique qui est également rencontrée dans les usines de production automobile. Le POV consiste à déterminer, à l'aide d'un carnet de commandes définissant les options requises pour chaque voiture à assembler, l'ordre dans lequel produire ces véhicules afin de minimiser les dépassements de capacité des postes de la chaîne de montage. Les véhicules sont produits en séquences dont l'ordre ne peut être modifié une fois le processus enclenché. Certaines options, comme le toit ouvrant, la traction intégrale ou les freins anti-blocage, nécessitent un temps de traitement plus important. Ces différences dans les temps de traitement impliquent des contraintes de capacité pour les postes de la chaîne qui y sont associés. Si, à un moment dans la séquence, la demande pour une option dépasse la capacité du poste qui la traite, il y a retard sur la chaîne et des coûts supplémentaires sont impliqués. En raison de sa structure et de ses contraintes globales de séquencement, le POV représente un défi intéressant en optimisation. Ce travail de recherche propose un nouvel algorithme d'OCF spécifiquement adapté pour la résolution du POV. Un algorithme tiré de la littérature et conçu pour le POV sert à la fois de base de comparaison et d'algorithme de départ pour la réalisation du projet. La démarche consiste à modifier cet algorithme de départ, étape par étape et de manière incrémentale, afin de le bonifier de certains éléments spécialisés pour résoudre le POV. Ces bonifications sont au nombre de trois : la première concerne les mécanismes d'apprentissage de l'algorithme, alors que les deux autres apportent une plus grande variation dans le comportement des fourmis. Premièrement, la nature des contraintes du POV a inspiré une modification importante de la trace de phéromone. Cette trace est une mémoire collective à l'intérieur de laquelle est consignée l'apprentissage accumulé par la colonie. Un nouvel élément y est apporté afin de mieux l'adapter à la forme des contraintes du POV. Deuxièmement, des mécanismes permettant de diversifier la recherche de solutions sont proposés. Lorsqu'elle fait un choix, une fourmi cherche un compromis entre l'apprentissage et sa vision locale du problème. Les paramètres définissant l'importance relative de ces éléments sont ceux touchés par cette seconde modification. Finalement, un nouveau mode de construction des solutions est proposé. Une fourmi construit normalement sa solution de manière séquentielle, de la première position à la dernière. La bonification proposée permet à une fourmi de revenir sur des parties de solutions déjà fixées pour y insérer de nouveaux éléments. Nous verrons que les trois éléments modifiés ou ajoutés à l'algorithme de départ contribuent à améliorer la performance générale. La nouvelle trace de phéromone permet d'identifier et d'encourager les motifs à répéter dans les solutions. Les variations des valeurs de paramètres aident à la diversification de la recherche dans l'espace de solutions et à mieux utiliser l'effort de calcul alloué. Quant au nouveau mode de construction, il se montre profitable dans certaines conditions et constitue une idée novatrice et généralisable pour traiter d'autres problèmes. Les éléments proposés sont novateurs. Ce travail de recherche, loin de se prétendre exhaustif, apporte de nouveaux concepts avec un bon potentiel d'exploration. Les éléments présentés se sont montrés efficaces et pourraient aisément faire l'objet de travaux futurs pour en trouver des variantes encore plus intéressantes. Finalement, bien que le problème traité ici soit de nature théorique, les idées apportées sont transférables à la problématique industrielle pratique rencontrée par les fabricants automobiles.

La conception de site Web a évoluée de façon significative depuis l'arrivée de l'Internet. Après la conception de page Web statique et la conception de site Web dynamique, la gestion et l'interaction avec le contenu via une base de données deviennent une préoccupation plus importante. L'interaction offerte à l'internaute est donc différente d'il y a quelques années. Il n'est plus seulement le navigateur des années 90, mais un auteur potentiel de contenu qui peut être diffusé sur le Web. Le travail du Webmestre peut, grâce à l'évolution des outils de conception de sites Web, se rapprocher d'avantage de sa vraie mission qui est de concevoir et réaliser un site alors que la tache de l'alimenter en contenu retourne aux gens qui détiennent les informations pertinentes à y diffuser. Dans ce mémoire, notre attention sera porté vers l'évolution de l'interaction dans les sites Web, les contextes d'interaction (babillard, interface de gestion de contenu, etc.), la méthode et les éléments requis au niveau techniques (langages de programmation serveur, base de données, etc.) de même que certaines notions d'interface utilisateur/système à observer. Une implantation concrète sera aussi réalisée, décrite et commentée. Le présent travail de recherche, loin d'être une fin en soi, est en fait une exploration des tendances, des possibilités et des contraintes rencontrées dans le développement d'outils de communication vraiment interactifs déployés sur un site Web.

Plusieurs avenues existent dans la littérature pour la résolution des problèmes d'ordonnancement de la production. La complexité de ces problèmes rend nécessaire l'emploi de stratégies de recherche de solutions évoluées. Parmi celles-ci figurent leur modélisation sous la forme de problème de satisfaction de contraintes (CSP). Ce travail de recherche a pour but d'intégrer les formalismes des méthodes de résolution des CSP pour la résolution d'un problème d'ordonnancement de la production soit le problème de "carsequencing". Les travaux effectués s'inscrivent dans une optique d'exploration des algorithmes de résolution de CSP et de leur application aux problèmes d'ordonnancement de la production. Dans un premier temps, les algorithmes de résolution de CSP existants sont étudiés et une comparaison entre ceux-ci est effectuée afin de déceler les avantages et les inconvénients de chacune des différentes méthodes de résolution suggérées dans la littérature. Entre autres, les algorithmes basés sur un principe de retour en arrière lors des situations d'inconsistance tels le BackTracking et le BackJumping sont étudiés. De plus, l'ajout d'heuristiques guidant la recherche de solutions ainsi que les méthodes d'apprentissage lors de la recherche sont exposées dans ce mémoire. Les algorithmes de diminution de domaines développés dans la littérature tels le Forward-Checking et les algorithmes de propagation de contraintes (AC) sont décrits et leurs implications sur la recherche sont quantifiées. Finalement, quelques méthodes de parallélisation de la recherche sont définies dans le cadre du présent travail de recherche. Suite à l'énumération des méthodes de résolution développées et à leur comparaison, ce travail de recherche couvre le développement d'un algorithme de résolution de CSP appliqué au problème de "car-sequencing". Premièrement, une étude de ce problème ainsi que des formulations possibles pour celui-ci est effectuée. Par la suite, le graphe de contraintes associé au problème de "car-sequencing" est défini et une stratégie de résolution du problème est décrite. Plus particulièrement, une méthode de diminution de l'espace de recherche de solutions possibles induit par les contraintes de ce problème est définie. L'algorithme de Forward-Checking est alors utilisé pour la résolution de ce problème particulier. De plus, une étude sur l'utilisation d'heuristiques guidant la recherche de solutions est effectuée. Finalement, une méthode de subdivision du problème initial en sous-problèmes indépendants a été développée afin de favoriser la diversification de la recherche de solutions lors d'une résolution concurrente. Les instances de problèmes suggérées dans la librairie de problèmes CSPLib sont utilisées comme base d'évaluation des méthodes développées. Les résultats obtenus dans le cadre de ce projet de recherche ont été comparés aux meilleurs résultats obtenus dans la littérature sur ces instances de problème. De plus, les résultats ont été comparés avec un outil de résolution commercial soit ILOG Solver 6.O. Les méthodes développées ont obtenu des résultats intéressants. En effet, pour un premier groupe de 70 instances du problème de "car-sequencing", le Forward-Checking développé a permis de surpasser les résultats obtenus par le solveur commercial ILOG Solver 6.O. Par contre, sur un deuxième groupe de problèmes, certaines bonifications des méthodes développées s'avèrent nécessaires. La diminution de l'espace de recherche représente une voie à explorer dans des recherches futures pour ainsi favoriser la résolution d'instances de problèmes non-satisfiables.

Le sujet de ce mémoire s'inscrit dans le cadre de la mesure de la confiance d'un agent logiciel. Les systèmes multi-agents actuels ne prennent pas en considération les problèmes de cohabitation entre un utilisateur et son agent virtuel agissant en son nom, telles que la confiance mutuelle et la délégation sécuritaire de tâches. Ainsi, la cohabitation utilisateur-agent nécessite une compréhension mutuelle, ce qui signifie que les deux entités devraient être aptes à comparer leurs points de vue ou opinions respectifs avant la délégation d'une tâche commune. Pour répondre à cette problématique, le modèle théorique proposé utilise la logique terminologique comme une approche ontologique pour garantir l'égalité sémantique de leurs opinions avant la mesure du degré de confiance mutuelle. Ce modèle non seulement réduit au minimum la communication entre l'usager et son agent mais aussi constitue une solution pour la délégation sécuritaire de tâches. Le cas concret servant de validation concerne le domaine du commerce électronique.

Dans de nombreux secteurs de l'industrie, les décideurs sont confrontés à des problèmes complexes, de grande dimension et multi-objectifs. Prendre une décision, pour ce genre de problèmes, nécessite en général l'optimisation simultanée de plusieurs objectifs souvent contradictoires. Malheureusement, la complexité des problèmes industriels, le nombre sans cesse croissant d'objectifs à optimiser simultanément et la rapidité des changements de l'environnement raccourcissent considérablement les délais de prise de décision tout en rendant cette tâche plus difficile pour les gestionnaires. Des outils informatiques comme les systèmes interactifs d'aide à la décision (SIAD) s'avèrent donc d'une grande utilité pour le décideur car ils favorisent une répartition évolutive des compétences entre l'utilisateur et la machine et offrent une bonne intégration de l'homme et de la machine dans le processus de décision. Les SIAD permettent donc au décideur d'évaluer la situation, les diverses alternatives et leurs impacts éventuels. Récemment, les techniques d'optimisation multi-objectifs à l'aide d'algorithmes évolutionnaires, et plus particulièrement d'algorithmes génétiques, suscitent de plus en plus d'intérêt auprès des chercheurs notamment à cause de leur faculté à exploiter de vastes espaces de recherche et à générer des compromis multiples en une seule étape d'optimisation. Les algorithmes génétiques tentent de simuler le processus de sélection naturelle dans un environnement hostile lié au problème à résoudre en s'inspirant des théories de l'évolution proposées par Darwin et des méthodes de combinaison de gènes introduites par Mendel. Ce mémoire propose d'intégrer les systèmes interactifs d'aide à la décision, l'optimisation multi-objectifs et les algorithmes génétiques afin de proposer un outil performant permettant la résolution de problèmes d'optimisation multi-objectifs. Dans le SIAD proposé, le traitement d'un problème multi-objectifs se fera en deux phases. La première phase consiste à approximer l'ensemble Pareto optimal. Cette étape sera réalisée à l'aide d'un nouvel algorithme génétique multi-objectifs hybride. Cette approche combine un algorithme génétique basé sur les concepts d'élitisme, de niche et de dominance Pareto avec des opérateurs de recherche locale. La deuxième phase utilise l'expérience du décideur afin d'approfondir la recherche dans une zone plus spécifique de l'ensemble pseudo Pareto Optimal en fonction des préférences exprimées par celui-ci. Pour cela, une approche générique de recherche de solutions de compromis est combinée avec un algorithme génétique. Le SIAD proposé est un outil flexible et facile d'utilisation grâce à son interface homme-machine conviviale. Cet outil ne constitue qu'un support à la prise de décision, la décision finale restant du ressort du planificateur. Un exemple d'application du SIAD proposé a été réalisé pour aborder un problème d'ordonnancement industriel rencontré dans une entreprise de production d'aluminium. Cette application montre bien l'intérêt pratique de ce genre de système. Bien qu'ayant produit des résultats très encourageants, ce travail de recherche représente surtout une première exploration des possibilités offertes par la combinaison de trois domaines de recherche en constante évolution : les SIAD, l'optimisation multi-objectifs et les algorithmes génétiques. L'union de ces trois champs de recherche laisse entrevoir des possibilités intéressantes pouvant mener à la conception de nouveaux outils de résolution permettant l'élaboration de scénarios pour éclairer la prise de décision. Ce travail peut donc être considéré comme une contribution vers l'élaboration et l'implantation de ce genre d'outils.