Retour à l'index du GREYC

Séminaire Algorithmique

Site du CNRS

Séminaire Algorithmique

Le séminaire a lieu le mardi à 11 h 45 (sauf modification exceptionnelle), au campus Côte de Nacre, bâtiment Sciences 3, salle S3 351, 3ème étage.

Résumé du séminaire du Mardi 30 Mars 2010

Navigation dans le plan : résultats asymptotiques

par Jean-François Marckert (LABRI, Bordeaux)

Soit G=(V,E) un graphe ; un algorithme de navigation/routage (sans mémoire) sur G est la donnée d'une application N de V x V dans V qui à (s,t) associe un point s' (et qui vérifie N(s, s) = s ).

On peut interpréter les choses comme suit : s est le point de départ, t celui d'arrivée. Le noeud N(s,t)=s' nous donne la première étape du parcours d'un voyageur.

La condition N(s, s) = s signifie qu'une fois arrivé, s'il arrive, le voyageur s'arrête.

Si on pose, s0 = s et pour i > 0, si = N(s(i-1), t), la suite des points si donne la suite des étapes du voyageur.

Nous nous intéressons ici à des algorithmes de navigation dans le plan : les étapes possibles sont un ensemble de points S, et les algorithmes de navigation considérés sont construits en utilisant des critères géométriques (il s'agit de navigation à la boussole).

Nous montrons que si les points de S sont aléatoires, et si le nombre de points n de S tend vers l'infini, alors la distance parcourue par le voyageur converge lorsque n vers l'infini, vers une valeur que l'on détermine. D'autres résultats asymptotiques seront également proposés.

(travail commun avec Nicolas Bonichon, LaBRI).

GREYC
Campus Côte de Nacre, boulevard du Maréchal Juin
BP 5186
14032 Caen Cedex
FAX : +33 (0)2 31 56 73 30
http://www.greyc.fr