Le pouvoir séparateur dune pièce de monnaieReportar como inadecuado




Le pouvoir séparateur dune pièce de monnaie - Descarga este documento en PDF. Documentación en PDF para descargar gratis. Disponible también para leer online.

1 NPA - Networks and Performance Analysis LIP6 - Laboratoire d-Informatique de Paris 6 2 LINCS - Laboratory of Information, Network and Communication Sciences 3 IUF - Institut Universitaire de France

Résumé : Nous considérons le problème qui consiste à éparpiller n robots mobiles dans un plan Euclidien, à partir d-une situation initiale quelconque où en particulier, deux robots peuvent occuper la même position. Comme ce problème n-admet pas de solution déterministe deux robots identiques initialement à la même place ont un comportement identique et donc ne se séparent jamais, les solutions sont nécessairement probabilistes. Nous étudions le nombre de lancers de pièce de monnaie \emph{alias} le nombre de bits aléatoires nécessaire à une séparation totale des robots. Nous montrons tout d-abord que n log n lancers sont nécessaires pour éparpiller n robots. Puis, nous donnons une condition nécessaire et suffisante pour qu-un algorithme soit optimal en nombre de lancers. Comme il s-avère que les algorithmes existants vérifient cette condition, ils sont optimaux en nombre de lancers pour le problème de l-éparpillement. Ensuite nous étudions la complexité en temps des algorithmes d-éparpillement, lorsque la détection forte de la multiplicité i.e., la capacité à compter le nombre de robots sur une position précise n-est pas disponible. La séparation en temps constant étant impossible, nous présentons une famille d-algorithmes qui éparpille n robots en Ofn pour toute fonction f non bornée supérieurement et, parmi cette famille, nous proposons un algorithme qui est à la fois optimal en temps et en nombre de lancers. Le détail des résultats peut être trouvé dans le rapport technique associé.





Autor: Quentin Bramas - Sébastien Tixeuil -

Fuente: https://hal.archives-ouvertes.fr/



DESCARGAR PDF




Documentos relacionados