Dépôt institutionnel de l'UQO
RECHERCHER

Rendez-vous synchrone dans les graphes avec traces distinctes

Téléchargements

Téléchargements par mois depuis la dernière année

Plus de statistiques...

Boutahar, Issam (2018). Rendez-vous synchrone dans les graphes avec traces distinctes. Mémoire. Gatineau, Université du Québec en Outaouais, Département d'informatique et d'ingénierie, 117 p.

[thumbnail of Boutahar_Issam_2018_mémoire.pdf]
Prévisualisation
PDF
Télécharger (963kB) | Prévisualisation

Résumé

Ce mémoire aborde le sujet du rendez-vous synchrone de deux agents mobiles avec des traces distinctes (jetons). Les deux agents, identifiés par des étiquettes différentes, sont placés sur des noeuds différents dans un graphe anonyme. L’exploration de ce dernier est nécessaire pour avoir une carte complète. Dans une ronde, l’agent mobile peut aller dans un des noeuds adjacents à son noeud actuel ou rester immobile dans ce dernier. Nous présentons des algorithmes déterministes qui permettent de faire le rendez-vous dans un temps optimal pour les trois scénarios suivants :
- Chaque agent mobile laisse un jeton d’une couleur différente sur son noeud initial. Les agents résolvent le rendez-vous dans un temps optimal O(Exp + DlogL), où Exp est le temps d’exploration, D est la distance entre les positions initiales des agents et L est la grandeur de l’espace des étiquettes.
- Chaque agent mobile laisse deux jetons sur son noeud initial et au plus un jeton sur les autres noeuds. Les agents résolvent le rendez-vous dans un temps optimal O(e + DLogL), où e est le nombre d’arêtes, D est la distance entre les positions initiales des agents et L est la grandeur de l’espace des étiquettes. - Chaque agent mobile laisse un nombre illimité de jetons sur son noeud initial et au plus un jeton sur les autres noeuds. Les agents résolvent le rendez-vous dans un temps optimal O(e) où e est le nombre d’arêtes.

Type de document: Thèse (Mémoire)
Directeur de mémoire/thèse: Pelc, Andrzej
Mots-clés libres: Agent mobile; Rendez-vous; Traces distinctes; Algorithme déterministe
Départements et école, unités de recherche et services: Informatique et ingénierie
Date de dépôt: 20 juin 2018 13:02
Dernière modification: 20 juin 2018 13:02
URI: https://di.uqo.ca/id/eprint/995

Gestion Actions (Identification requise)

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