Show item record

dc.contributor.advisorHamel, Sylvie
dc.contributor.authorMilosz, Robin
dc.date.accessioned2016-11-09T17:28:17Z
dc.date.availableNO_RESTRICTIONfr
dc.date.available2016-11-09T17:28:17Z
dc.date.issued2016-09-28
dc.date.submitted2015-12
dc.identifier.urihttp://hdl.handle.net/1866/16162
dc.subjectalgorithmesfr
dc.subjectbio-informatiquefr
dc.subjectsystème de classementsfr
dc.subjectheuristiquesfr
dc.subjectoptimisation combinatoirefr
dc.subjectmédianefr
dc.subjectpermutationfr
dc.subjectcontraintesfr
dc.subjectalgorithmsfr
dc.subjectbio-informaticfr
dc.subjectranking systemsfr
dc.subjectheuristicfr
dc.subjectcombinatorial optimizationfr
dc.subjectmedianfr
dc.subjectconstraintsfr
dc.subject.otherApplied 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-Taufr
dc.typeThèse ou mémoire / Thesis or Dissertation
etd.degree.disciplineInformatiquefr
etd.degree.grantorUniversité de Montréalfr
etd.degree.levelMaîtrise / Master'sfr
etd.degree.nameM. Sc.fr
dcterms.abstractLa 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.abstractThe 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.languagefrafr


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show item record