Liens externes
  • Répertoires
  • Facultés
  • Bibliothèques
  • Plan campus
  • Sites A-Z
  • Mon UdeM
    • Mon portail UdeM
    • Mon courriel
    • StudiUM
Dessin du pavillon Roger Gaudry/Sketch of Roger Gaudry Building
Site d'accueil de l'UniversitéSite d'accueil de l'UniversitéSite d'accueil de l'Université
Papyrus : Dépôt institutionnel
Papyrus
Dépôt institutionnel
Papyrus
    • français
    • English
  • français 
    • français
    • English
  • Ouvrir une session
  • français 
    • français
    • English
  • Ouvrir une session
Voir le document 
  •   Accueil
  • Faculté des arts et des sciences
  • Faculté des arts et des sciences – Département d'informatique et de recherche opérationnelle
  • Faculté des arts et des sciences – Département d'informatique et de recherche opérationnelle - Thèses et mémoires
  • Voir le document
  •   Accueil
  • Faculté des arts et des sciences
  • Faculté des arts et des sciences – Département d'informatique et de recherche opérationnelle
  • Faculté des arts et des sciences – Département d'informatique et de recherche opérationnelle - Thèses et mémoires
  • Voir le document
JavaScript is disabled for your browser. Some features of this site may not work without it.

Mon compte

Pour soumettre un document ou s'abonner à des alertes courriels
Ouvrir une session
Nouvel utilisateur?

Parcourir

Tout PapyrusCommunautés et CollectionsTitresDates de publicationAuteursDirecteurs de rechercheSujetsProgrammesAffiliationIndex des titresCette collectionTitresDates de publicationAuteursDirecteurs de rechercheSujetsProgrammesAffiliationIndex des titres

Statistiques

Données d'utilisation
Afficher les métadonnées
Permalien: http://hdl.handle.net/1866/16162

Étude de la médiane de permutations sous la distance de Kendall-Tau

Thèse ou mémoire
Vignette
Milosz_Robin_2015_memoire.pdf (1.545Mo)
2015-12 (octroi du grade: 2016-09-28)
Auteur(s)
Milosz, Robin
Directeur(s) de recherche
Hamel, Sylvie
Cycle d'études
Maîtrise
Programme
Informatique
Mots-clés
  • algorithmes
  • bio-informatique
  • système de classements
  • heuristiques
  • optimisation combinatoire
  • médiane
  • permutation
  • contraintes
  • algorithms
  • bio-informatic
  • ranking systems
  • heuristic
  • combinatorial optimization
  • median
  • constraints
  • Applied Sciences - Computer Science / Sciences appliqués et technologie - Informatique (UMI : 0984)
Résumé(s)
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.
Collections
  • Thèses et mémoires électroniques de l’Université de Montréal [17173]
  • Faculté des arts et des sciences – Département d'informatique et de recherche opérationnelle - Thèses et mémoires [732]

DSpace software [version 5.8 XMLUI], copyright © 2002-2015  DuraSpace
Contactez-nous | Faire parvenir un commentaire
Certificat SSL / SSL Certificate
les bibliothéques/UdeM
  • Urgence
  • Vie privée
  • Offres d'emploi
  • Mon courriel
  • StudiUM
  • iTunes U
  • Nous écrire
  • Facebook
  • YouTube
  • Twitter
  • Fils des nouvelles UdeM
 

 


DSpace software [version 5.8 XMLUI], copyright © 2002-2015  DuraSpace
Contactez-nous | Faire parvenir un commentaire
Certificat SSL / SSL Certificate
les bibliothéques/UdeM
  • Urgence
  • Vie privée
  • Offres d'emploi
  • Mon courriel
  • StudiUM
  • iTunes U
  • Nous écrire
  • Facebook
  • YouTube
  • Twitter
  • Fils des nouvelles UdeM