Exploration optimale d'un arbre par un essaim d'agents mobiles

Roy, Mélanie (2012). Exploration optimale d'un arbre par un essaim d'agents mobiles. Mémoire. Gatineau, Université du Québec en Outaouais, Département d'informatique et d'ingénierie, 69 p.

Prévisualisation

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

Résumé

Ce mémoire propose une étude complète de l’exploration optimale d’un arbre enraciné par un essaim d’agents mobiles. L’arbre est connu. L’essaim dispose d’un nombre illimité d’agents qui commencent tous dans le même nœud (la racine) et se déplacent de façon synchrone. Les agents doivent visiter l’arbre le plus rapidement possible. Ils ont une restriction : à chaque ronde, il doit y avoir un maximum une distance de d entre les agents les plus éloignés les uns des autres. Le travail consiste à construire un algorithme optimal d’exploration et à faire trois preuves : la preuve de l’exactitude de l’algorithme, la preuve de son temps d’exécution et la preuve de l’optimalité. D’autre part nous montrons que tous nos algorithmes peuvent être adaptés à la situation où le nombre d’agents est égal au nombre de feuilles de l’arbre. Nous construisons aussi un simulateur qui illustre le fonctionnement de l’algorithme.

Type de document:	Thèse (Mémoire)
Directeur de mémoire/thèse:	Pelc, Andrzej
Co-directeurs de mémoire/thèse:	Czyzowicz, Jurek
Informations complémentaires:	Comprend des références bibliographiques : p. [66]-69
Mots-clés libres:	Agents mobiles; Réseaux d'ordinateurs
Départements et école, unités de recherche et services:	Informatique et ingénierie
Date de dépôt:	06 déc. 2012 16:14
Dernière modification:	23 oct. 2015 13:12
URI:	https://di.uqo.ca/id/eprint/522

Gestion Actions (Identification requise)

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