Le pouvoir séparateur d'une pièce de monnaie
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 O(f(n)) 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é.
Origine : Fichiers produits par l'(les) auteur(s)