Nous proposons plusieurs techniques visant à résoudre en pratique le problème NP-complet de satisfaction de contraintes de manière générique. Nous distinguons deux grands axes de techniques de résolution de CSP : l'infrence et la recherche. Nous avons contribué l'amélioration des techniques d'inférence en nous concentrant sur la propriété centrale qu'est la consistance d'arc : optimisations des algorithmes de consistance d'arc, comportement de plusieurs algorithmes d'inférence aux bornes de domaines discrets, et enfin une alternative intéressante à la consistance de chemin : la consistance duale. Cette propriété nous a amené à concevoir des algorithmes de consistance de chemin forte très efficaces. La variante conservative de cette consistance est de plus plus forte que la consistance de chemin conservative, tout en restant plus rapide à établir en pratique.<br />Par ailleurs, nous avons également cherché à améliorer MGAC, tout d'abord en équipant celui-ci d'heuristiques de choix de valeurs. Nous nous sommes pour cela basés sur l'heuristique de Jeroslow-Wang, issue du problème SAT. En utilisant deux techniques de conversion de CSP vers SAT, nous montrons comment cette heuristique se comporterait sur un CSP. Enfin, nous avons cherché à utiliser une hybridation entre un algorithme de recherche locale basé sur la pondération des contraintes et un algorithme MGAC équipé de l'heuristique dom/wdeg, en exploitant les possibilités d'apprentissage de l'un et l'autre algorithmes.<br />De manière transversale, l'ensemble des techniques développées dans le cadre de cette thèse a amené à la réalisation d'une API pour le langage Java, capable de résoudre un CSP au sein d'une application Java quelconque. Cette API a été développée dans l'optique "boîte noire" : le moins de paramètres et d'expertise possibles sont demandés à l'utilisateur. Un prouveur basé sur CSP4J a concouru lors les compétitions internationales de prouveurs CSP avec des résultats encourageants.

Le contexte de notre travail s'intéresse à l'ordonnancement des activités de maintenance dans les systèmes de production. L'objectif de la thèse concerne l'élaboration de méthodes de résolution minimisant un critère regroupant les deux aspects production et maintenance. Les règles de priorité ainsi que les algorithmes génétiques ayant fait leur preuve dans le domaine seront à la base de notre étude. Etude faite tout d'abord sur un problème à une machine puis étendue au cas du Flow Shop. Notre contribution comporte tois volets. Le premier volet prend appui sur les solutions générées à l'aide d'une règle de dominance reliant les tâches de production et les tâches de maintenance. Le deuxième volet propose un algorithme par séparation et évaluation permettant de générer des ordonnancements de permutation du problème conjoint de la production et de la maintenance au sein du FLow Shop à deux machines. Le troisième volet étend l'étude au cas du Flow Shop à plusieurs machines. Nous proposons dans ce cas un algorithme génétique avec un codage approprié. Cet algorithme a l'avantage de balayer tout l'espace de recherche et par conséquent de générer des ordonnancements de très bonne qualité. Nous optons pour la maintenance préventive systématique pour l'appliquer dans notre étude. L'une des difficultés majeures de ce type de maintenance est le choix des périodes d'interventions optimales. Nous proposons dans ce cadre une méthode de choix de périodes systématiques.

Le contexte de notre travail s'intéresse à l'ordonnancement d'un atelier de type job shop. L'objectif de la thèse concerne l'élaboration d'une méthode de résolution aussi bien dans le cas classique d'un ordonnancement relatif à la production que dans le cas beaucoup moins étudié touchant l'ordonnancement conjoint de la production et de la maintenance. Les algorithmes génétiques ayant fait leur preuve dans le domaine aussi bien mono objectif que multiobjectif seront à la base de notre étude. Etude faite tout d'abord sur un problème classique de job shop noté J / / Cmax , en ne tenant pas compte des contraintes de disponibilité des machines, puis en introduisant dans un deuxième temps l'aspect de maintenance préventive ayant des objectifs parfois antagonistes avec la production et qui nécessite une résolution multiobjectif. Notre contribution comporte deux volets. Le premier volet prend appui sur les solutions générées par un algorithme génétique qui sont étudiées par des méthodes d'apprentissage. Méthodes qui seront resituées dans le processus d'Extraction de Connaissance à partir des Données (ECD). Dans un soucis de validation et de comparaison par rapport aux travaux faits dans la communauté, la démarche proposée a été élaborée sur un problème classique de type J / / Cmax et sur des benchmarks connus. Le deuxième volet propose un algorithme génétique Pareto optimal résolvant le problème d'ordonnancement conjoint de la production et de la maintenance au sein du job shop. Cet algorithme génétique génère des solutions Pareto optimales. Solutions que nous validerons par des bornes inférieures. Nous optons pour la maintenance préventive systématique pour l'appliquer dans l'atelier de job shop. L'une des difficultés majeures de ce type de maintenance est le choix des périodes d'interventions. Nous proposons dans ce cadre deux méthodes de choix de périodes systématiques.

Cette thèse aborde deux domaines de l'algorithmique: la fouille de données et l'arithmétique. Le point de vue adopté est celui de l'analyse en moyenne et, plus précisément, celui de l'analyse dynamique, qui combine des méthodes d'analyse d'algorithmes et des systèmes dynamiques. Les algorithmes de type Euclide calculent le pgcd de deux nombres; ce sont donc des briques de base du calcul formel, mais leur comportement probabiliste fin reste encore mal connu. Tout récemment, les méthodes dynamiques ont permis des avancées significatives dans ce domaine. Nous étendons cette approche à l'analyse fine d'autres paramètres, comme la complexité binaire et la taille des restes. Ces paramètres s'avèrent essentiels pour l'analyse de l'algorithme de type diviser pour régner introduit par Knuth et Schönhage. Nous utilisons également l'analyse dynamique dans le calcul prouvé de grandeurs spectrales. L'approche dynamique s'adapte aussi à l'algorithme d'Euclide sur les polynômes, même si, dans ce cas, les méthodes de la combinatoire analytique classique s'appliquent déjà. Nous abordons également la fouille de données. Nous nous limitons à des bases de données binaires où la connaissance se représente sous forme de 'motifs fréquents'. Le nombre de ces motifs est un paramètre essentiel pour les algorithmes. D'après les expérimentations, il varie considérablement selon les paramètres de la base, et l'analyse dans le pire des cas n'est donc pas significative en pratique. Dans cette thèse, nous élucidons le comportement moyen du nombre de motifs fréquents dans un modèle très général, où les bases sont contruites à partir de sources possiblement corrélées.

Contexte: Bien que plusieurs algorithmes pharmacogénétiques de prédiction de doses de warfarine aient été publiés, peu d’études ont comparé la validité de ces algorithmes en pratique clinique réelle. Objectif: Évaluer trois algorithmes pharmacogénomiques dans une population de patients qui initient un traitement à la warfarine et qui souffrent de fibrillation auriculaire ou de problèmes de valves cardiaques. Analyser la performance des algorithmes de Gage et al., de Michaud et al. ainsi que de l’IWPC quant à la prédiction de la dose de warfarine permettant d’atteindre l’INR thérapeutique. Méthodes: Un devis de cohorte rétrospectif fut utilisé afin d’évaluer la validité des algorithmes chez 605 patients ayant débuté une thérapie de warfarine à l’Institut de Cardiologie de Montréal. Le coefficient de corrélation de Pearson ainsi que l’erreur absolue moyenne ont été utilisés pour évaluer la précision des algorithmes. L’exactitude clinique des prédictions de doses fut évaluée en calculant le nombre de patients pour qui la dose prédite était sous-estimée, idéalement estimée ou surestimée. Enfin, la régression linéaire multiple a été utilisée pour évaluer la validité d’un modèle de prédiction de doses de warfarine obtenu en ajoutant de nouvelles covariables. Résultats : L’algorithme de Gage a obtenu la proportion de variation expliquée la plus élevée (R2 ajusté = 44 %) ainsi que la plus faible erreur absolue moyenne (MAE = 1.41 ± 0.06). De plus, la comparaison des proportions de patients ayant une dose prédite à moins de 20 % de la dose observée a confirmé que l’algorithme de Gage était également le plus performant. Conclusion : Le modèle publié par Gage en 2008 est l’algorithme pharmacogénétique le plus exact dans notre population pour prédire des doses thérapeutiques de warfarine. / Background: Although numerous genotype-based warfarin dosing algorithms have been published, there is little data comparing the predictive ability of these algorithms in real clinical practice. Objectives: Our goal was to evaluate the performance of pharmacogenetic algorithms in an unselected patient population initiating warfarin treatment for atrial fibrillation or valve disease in a real-world clinical setting. The principal objective of the analysis was to determine if Gage’s, Michaud’s, and IWPC algorithms could predict the dose achieving the therapeutic International normalized ratio (INR). Methods: Data from a retrospective cohort study of 605 patients initiating warfarin therapy at the Montreal Heart Institute was used. We compared the dose predicted by the algorithms to the dose achieving the therapeutic INR. Pearson’s correlation coefficient and mean absolute error (MAE) were used to evaluate the predictive accuracy of the algorithms. Clinical accuracy of the predictions was assessed by computing the proportion of patients in which the predicted dose was under-estimated, ideally estimated, or overestimated. Finally, we used multiple linear regression analysis to evaluate the accuracy of a predictive model obtained by adding additional covariables in predicting therapeutic warfarin doses. Results: The proportion of variation explained (adjusted R2) was the highest for Gage’s algorithm (R2 = 44 %) and the mean absolute error was the smallest for the predictions made by Gage’s algorithm (MAE = 1.41 ± 0.06). Moreover, when we compared the proportion of patients whose predicted doses are within ± 20 % of the observed stable dose, Gage’s algorithm also performed the best overall. Conclusion: The algorithm published by Gage et al. in 2008 is the most accurate pharmacogenetically based equation in predicting therapeutic warfarin dose in our study population.

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

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

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

Cette thèse traite l’utilisation des agents mobiles dans le domaine des algo- rithmes distribués en les déplaçant de manière aléatoire dans le réseau. Initialement k agents mobiles ayant les identités uniques sont placés dans le réseau. On décrit un algorithme distribué pour calculer un arbre couvrant dans les réseaux dynamiques en utilisant les agents mobiles. Les agents marquent les noeuds sur les quelles ils arrivent. Ils utilisent deux techniques di?érentes : le clonage dans lequel un agent crée son propre clone pour faire quelques tâches et le marquage sur la tableau de bord (un espace mémoire sur les noeuds). Ces techniques sont utilisés dans les applications comme l’arbre couvrant, le rassemblement et la collecte d’information. Chacun des agents détient une information partielle. Quand deux ou plusieurs agents se rencontrent sur un noeud, ils fusionnent en un seul agent. On s’intéresse alors au temps nécessaire ou tous les k agents fusionnent en un seul et unique agent. On présent une chaîne de Markov pour le comportement des agents, et on montre comment on peut utiliser cette technique pour calculer la bourne supérieur. On étudie le même problème quand les agents mobile commencent la marche aléatoire sous un régime stationnaire. On a aussi étudié le problème de Handshake et on l’a analysé en utilisant les agents mobiles. / This thesis deals with the use of mobile agents in distributed algorithms by performing random walks in the network. k mobile agents having unique identities are placed initially in a network. We describe a distributed algorithm for computing spanning trees in dynamic networks by using mobile agents. The agents mark the nodes on which they arrive. They use two di?erent techniques. In one problem they use the cloning in which an agent creates its own clone to do some task assigned. In the second, the mobile agents mark on the whiteboard (a memory location on the nodes). These techniques are used in applications such as spanning tree, gathering and collecting information. The mobile agents have limited knowledge and hence, they are not intelligent and do not have computational capabilities. When two or more agents meet at a node of the underlying graph, they merge into a single agent. The parameter of interest is the expected time for all the agents to merge into a single agent. We present a Markov chain, modelling the agents behavior, and show how this can be used to upper bound the expected time for all the k agents to merge into a single agent. We study the same problem when the mobile agents start their walk directly under stationary regime. Handshake problem is also studied and analyzed using mobile agents.

Le dernier rapport du GIEC souligne que le rôle de la stratosphère dans le changement climatique est mal connu et invite à poursuivre son étude. Les mesures d'occultation solaire et in situ sont appropriées à cette étude mais il est nécessaire de les valider. Nous avons tout d'abord développé notre propre algorithme d'inversion des transmissions de SAGE III et avons comparé nos produits (profils verticaux des concentrations en O3 et en NO2 et coefficients d'extinction des aérosols (CEA)) à ceux issus de l'algorithme officiel et d'un troisième algorithme. De bons accords ont été obtenus entre ces inversions pour toutes les espèces. Nous avons poursuivi avec des comparaisons à des mesures corrélatives obtenues à l'aide d'instruments spatiaux et d'un instrument sous ballon (SPIRALE) déjà validés. Si on exclut les CEA, les résultats sont satisfaisants. Toutefois, la comparaison aux mesures in situ de SPIRALE obtenues aux abords du vortex polaire donne un désaccord pour NO2 démontrant ainsi les limites de l'occultation solaire dans la mesure d'espèces réactives dans des conditions dynamiques complexes. Une fois ces validations réalisées, nous nous sommes intéressés aux intrusions dans la stratosphère d'aérosols issus de feux de forêt et nous avons montré qu'elles conduisent à une forte augmentation du nombre de particules. Enfin, dans un cadre international, nous avons participé à la validation des instruments de la mission ACE (FTS, MAESTRO, Imager) à l'aide de SAGE III et de SPIRALE. Cela nous a permis de valider certains produits (O3 et NO2 de FTS et MAESTRO), d'en invalider d'autres (CEA d'Imager) et de confirmer le désaccord pour NO2 entre mesures in situ et à distance. / One of the conclusions of the last IPCC reports is that the role of the stratosphere in the current climate change is not weil known. Consequently, stratospheric studies must continue. Solar occultation and in situ measurements are weil suited to these studies but it is necessary to validate them. First, we have developed our inversion algorithm of the SAGE III transmissions and we have compared our products (vertical profiles of O3 and N02 concentrations and of aerosol extinction coefficients (AEC)) to those from the officiaI algorithm and from a third algorithm. Good agreements are obtained between these inversions for ail species. Then, we have compared our products to those from correlative validated measurements obtained by satellite and balloon borne instrument (SPIRALE). Except CEA, results are satisfying. However, the comparison with in situ measurements from SPIRALE obtained on the edge of the polar vortex exhibits a disagreement for NO2 proving that the solar occultation method are not weil suited for reactive species in complex dynamical situation. Once these validations carried out, we have studied the stratospheric intrusions of aerosols resulting from forest fires and we have shown that they lead to a strong increase in the number of particles. Finally, in an international framework, we have taken part in the validation of the instruments of the ACE mission (FTS, MAESTRO and Imager) with SAGE III and SPIRALE data. That enabled us to validate sorne products (O3 and NO2 from FTS and MAESTRO), to invalidate others (CEA from Imager) and to confirm the discrepancy for NO2 between in situ and remote measurements