Définition probabiliste d'un segment de droite discrète et automates cellulaires


Robert French, Université de Bourgogne. 9 avril 2015 10:00 limd
Abstract:

Cette présentation montrera un lien théorique entre les segments de droite discrète (DSS) et la théorie probabiliste des chemins possibles. Un DSS entre deux points est généralement défini comme la meilleure approximation discrète de la droite continue sous-jacente entre les deux points. Dans cet article, nous introduisons une autre définition qui fait écho à des approches dites de tous les chemins possibles de la physique des particules. Le cosmologiste George Ellis a récemment fait remarquer, Une particule prend tous les chemins qu'elle peut, et ce que nous voyons est la moyenne pondérée de toutes ces possibilités.'' Dans une veine similaire, nous définissons un segment de droite discrète entre deux points comme l'ensemble de pixels le plus rapproché de la moyenne pondérée de tous les chemins discrets possibles de longueur minimale entre les deux points. Cette définition est uniquement destinée à démontrer une relation théorique entre la théorie probabiliste des chemins discrets possibles et les DSSs. Elle n’a pas vocation à remplacer l’algorithme standard de Bresenham (1963) comme moyen pratique pour tracer les segments de droite dans le plan, mais de le justifier par une autre approche. Nous présentons également brièvement l’extension de cette définition dans l’espace à 3 dimensions. Nous présenterons également un nouvel algorithme récursif pour tracer un type de DSS présentant une meilleure autosimilarité que la DSS standard et qui est plus rapide que l'algorithme classique de Bresenham. Pour finir, nous implémenterons l’algorithme de tous les chemins possibles au moyen des automates cellulaires que nous appelons «Mants» (M-fourmis équipées de mémoires mais non réalistes). Il s’avère que le chemin qui est localement le plus probable entre lamanthill'' et une source d'alimentation pour un individu de la colonie n’est, en général, pas identique à la trajectoire optimale pour la colonie dans son ensemble.