Étude de la médiane de permutations sous la distance de Kendall-Tau
dc.contributor.advisor | Hamel, Sylvie | |
dc.contributor.author | Milosz, Robin | |
dc.date.accessioned | 2016-11-09T17:28:17Z | |
dc.date.available | NO_RESTRICTION | fr |
dc.date.available | 2016-11-09T17:28:17Z | |
dc.date.issued | 2016-09-28 | |
dc.date.submitted | 2015-12 | |
dc.identifier.uri | http://hdl.handle.net/1866/16162 | |
dc.subject | algorithmes | fr |
dc.subject | bio-informatique | fr |
dc.subject | système de classements | fr |
dc.subject | heuristiques | fr |
dc.subject | optimisation combinatoire | fr |
dc.subject | médiane | fr |
dc.subject | permutation | fr |
dc.subject | contraintes | fr |
dc.subject | algorithms | fr |
dc.subject | bio-informatic | fr |
dc.subject | ranking systems | fr |
dc.subject | heuristic | fr |
dc.subject | combinatorial optimization | fr |
dc.subject | median | fr |
dc.subject | constraints | fr |
dc.subject.other | Applied Sciences - Computer Science / Sciences appliqués et technologie - Informatique (UMI : 0984) | fr |
dc.title | Étude de la médiane de permutations sous la distance de Kendall-Tau | fr |
dc.type | Thèse ou mémoire / Thesis or Dissertation | |
etd.degree.discipline | Informatique | fr |
etd.degree.grantor | Université de Montréal | fr |
etd.degree.level | Maîtrise / Master's | fr |
etd.degree.name | M. Sc. | fr |
dcterms.abstract | La distance de Kendall-τ compte le nombre de paires en désaccord entre deux permuta- tions. La distance d’une permutation à un ensemble est simplement la somme des dis- tances entre cette permutation et les permutations de l’ensemble. À partir d’un ensemble donné de permutations, notre but est de trouver la permutation, appelée médiane, qui minimise cette distance à l’ensemble. Le problème de la médiane de permutations sous la distance de Kendall-τ, trouve son application en bio-informatique, en science politique, en télécommunication et en optimisation. Ce problème d’apparence simple est prouvé difficile à résoudre. Dans ce mémoire, nous présentons plusieurs approches pour résoudre le problème, pour trouver une bonne solution approximative, pour le séparer en classes caractéristiques, pour mieux com- prendre sa compléxité, pour réduire l’espace de recheche et pour accélérer les calculs. Nous présentons aussi, vers la fin du mémoire, une généralisation de ce problème et nous l’étudions avec ces mêmes approches. La majorité du travail de ce mémoire se situe dans les trois articles qui le composent et est complémenté par deux chapitres servant à les lier. | fr |
dcterms.abstract | The Kendall-τ distance counts the number of pairwise disagreements between two permutations. The distance between a permutation and a set is simply the sum of the distances between the considered permutation and the permutations of the set. Given a set of permutations, we want to find the permutation, called median, that minimise that distance to the set. The problem of finding a median of permutations under the Kendall-τ distance, finds applications in bioinformatics, political science, telecommunications and optimization. This simple appearing problem is proven difficult to solve. In this master thesis, we present a few approaches to solve the problem, to find a good approximate solution, to separate it into caracteristic classes, to deepen our understanding of its complexity, to reduce the search space and to accelerate calculations. We also present, at the end of this thesis, a generalization of this problem and we study it with the same approaches. The majority of the work in this thesis is located in the three papers which compose it and is complemented by two chapters, that bound them all together. | fr |
dcterms.language | fra | fr |
Fichier·s constituant ce document
Ce document figure dans la ou les collections suivantes
Ce document diffusé sur Papyrus est la propriété exclusive des titulaires des droits d'auteur et est protégé par la Loi sur le droit d'auteur (L.R.C. (1985), ch. C-42). Il peut être utilisé dans le cadre d'une utilisation équitable et non commerciale, à des fins d'étude privée ou de recherche, de critique ou de compte-rendu comme le prévoit la Loi. Pour toute autre utilisation, une autorisation écrite des titulaires des droits d'auteur sera nécessaire.