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. / 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.
| Identifer | oai:union.ndltd.org:umontreal.ca/oai:papyrus.bib.umontreal.ca:1866/16162 |
| Date | 12 1900 |
| Creators | Milosz, Robin |
| Contributors | Hamel, Sylvie |
| Source Sets | Université de Montréal |
| Language | French |
| Detected Language | French |
| Type | Thèse ou Mémoire numérique / Electronic Thesis or Dissertation |
Page generated in 0.0124 seconds