Le temps du rendez-vous anonyme dans les arbres : algorithmes déterministes versus algorithmes aléatoires

Elouasbi, Samir (2012). Le temps du rendez-vous anonyme dans les arbres : algorithmes déterministes versus algorithmes aléatoires. Mémoire. Gatineau, Université du Québec en Outaouais, Département d'informatique et d'ingénierie, 63 p.

Prévisualisation

PDF Télécharger (418kB) | Prévisualisation

Résumé

Deux agents mobiles identiques (anonymes) démarrent à partir des nœuds arbitraires distincts d’un arbre inconnu et se déplacent le long de ses arêtes afin de se rencontrer dans un certain nœud. Les agents se déplacent durant des rondes synchrones : durant chaque ronde, un agent peut rester dans on nœud actuel et se déplacer vers un de ses voisins. Nous étudions le temps optimal nécessaire pour accomplir ce rendez-vous. Dans le cas déterministe, nous cherchons des algorithmes qui permettent d’accomplir le rendez-vous quand c’est possible, tandis que pour le cas aléatoire nous cherchons des algorithmes presque certains, qui permettent de faire le rendez-vous avec une probabilité de succès d’au moins 1 – 1/n dans des arbres d’ordre n, pour n suffisamment grand. Notre contribution pour le cas déterministe peut se résumer dans les points suivants : - Nous avons présenté un algorithme déterministe qui permet à des agents de faire un rendez-vous, lorsque c’est possible, dans n’importe quel arbre en temps optimal O (n) où n représente le nombre de nœuds de cet arbre. - Nous avons prouvé que le rendez-vous s’avère impossible si et seulement si les agents se trouvent sur des positions initiales symétriques et que leur départ est simultané. Pour ce qui est du cas aléatoire : - Nous avons réalisé un algorithme presque certain qui permet aux agents d’accomplir le rendez-vous en temps espéré optimal O (n) dans n’importe quel arbre d’ordre n quel que soit la situation dans laquelle se trouvent les agents. – Nous avons amélioré le coût espéré à O (log n) dans le cas où les agents connaissent la distance initiale D constante qui les séparent, Δ le degré maximum constant de l’arbre et le nombre de nœuds n de l’arbre. Mots clés : agent mobile, rendez-vous, algorithme déterministe, algorithme aléatoire.

Type de document:	Thèse (Mémoire)
Directeur de mémoire/thèse:	Pelc, Andrzej
Informations complémentaires:	Localisation : Bibliothèque L.-Brault QA 76 .9 M35 E46 2012
Mots-clés libres:	Agent mobile; Rendez-vous; Algorithme déterministe; Algorithme aléatoire
Départements et école, unités de recherche et services:	Informatique et ingénierie
Date de dépôt:	06 déc. 2012 16:01
Dernière modification:	15 nov. 2016 21:14
URI:	https://di.uqo.ca/id/eprint/521

Gestion Actions (Identification requise)

Dernière vérification avant le dépôt