Dépôt institutionnel de l'UQO
RECHERCHER

Rendez-vous synchrone dans les grilles

Tiane, Anas (2013). Rendez-vous synchrone dans les grilles. Mémoire. Gatineau, Université du Québec en Outaouais, Département d'informatique et d'ingénierie, 51 p.

Le plein texte n'est pas disponible pour ce document.

Résumé

Deux agents mobiles qui commencent à deux nœuds arbitraires dans une grille de taille m x k, avec 1 < m ≤ k, doivent réaliser un rendez-vous en se retrouvant en même temps dans le même nœud. Les agents ont des étiquettes différentes et se déplacent de façon synchrone : dans chaque ronde un agent peut rester dans le même nœud ou aller à un nœud adjacent. Le temps du rendez-vous c’est le nombre de rondes entre le début du deuxième agent et le rendez-vous. Les nœuds de la grilles sont anonymes et les ports locaux de chaque nœud de la gille sont libellés de façon arbitraire avec des numéros distincts { 0,…, d–1 }. d est appelé le degré du nœud v avec d = 2,3,4. La numérotation des ports est locale, cela veut dire qu’il n’existe aucune relation entre les numéros de ports de deux nœuds distincts de la grille. Lorsqu’un nœud est visité, l’agent reconnait son degré. L’agent mémorise le numéro de port par lequel il est entré dans le nœud et peut choisir le numéro de port par lequel il quittera le nœud. On considère deux catégories d’algorithmes, la première aléatoire et la deuxième déterministe. Pour les algorithmes aléatoires, on présente deux variantes, à savoir le rendez-vous aléatoire avec retour et sans retour. Pour les algorithmes déterministes, on présente deux variantes pour les grilles de taille m x k pour 1 < m ≤ k, à savoir le rendez-vous déterministe sur le bord de la grille et le rendez-vous déterministe au centre de la grille. Nous présentons deux algorithmes déterministes de rendez-vous pour les grilles m x k, où 2 < m ≤ k : un qui fonctionne en temps O (2ᵐ + m² k) et l’autre qui fonctionne en temps O ((2ᵐ + k² )l), où l est la plus petite des étiquettes. Ce premier fonctionne pour les grilles des dimensions impairs. Pour les grilles de taille 2 x k on présente un algorithme déterministe qui se réalise en temps de O(2ᵏ l) où l est la plus petite des étiquettes. Mots clés : algorithmes, rendez-vous, agent mobile, grille.

Type de document: Thèse (Mémoire)
Directeur de mémoire/thèse: Pelc, Andrzej
Informations complémentaires: Comprend des références bibliographiques : p. [50-51]
Mots-clés libres: Algorithmes; Rendez-vous; Agent mobile; Grille
Départements et école, unités de recherche et services: Informatique et ingénierie
Date de dépôt: 07 nov. 2014 18:47
Dernière modification: 23 oct. 2015 13:12
URI: http://di.uqo.ca/id/eprint/711

Actions (Identification requise)

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