annexePreuveMixage.tex

   1 Introduisons tout d'abord une relation d'ordre
   2 $\preceq$  entre les  classes d'équivalences.
   3 Formellement, \class{p}
   4 $\preceq$   \class{q}
   5 s'il existe un chemin de longueur   $\alpha$
   6 ($0\le\alpha<|\mathcal{K}|$)  entre un élément le la classe
   7 \class{p} vers un élément  de
   8 \class{q}.
   9
  10 \begin{lemma}
  11   Il existe un processus de renommage qui effecte un nouvel identifiant aux
  12   élément  $i\in$ \class{p}  et $j  \in$ \class{q}  tel que
  13   $i  \le  j$ si et seulement si
  14   \class{p} $\preceq$ \class{q}.
  15   \begin{Proof}
  16
  17     Tout d'abord,  soit  \class{p_1},   \ldots,  \class{p_l}  des   classes
  18     contenant respectivement les éléments $n_1$,\ldots,  $n_l$
  19     qui ne dépendent d'aucune autre classe.
  20     Les éléments de  \class{p_1} sont renommés par $1$, \ldots,  $n_1$,
  21     les elements  de \class{p_i},   $2  \le   i  \le   l$  sont renommés par
  22     $1+
  23     \Sigma_{k=1}^{i-1}  n_k$, \ldots, $\Sigma_{k=1}^{i}  n_k$.
  24     On considère maintenant les classes \class{p_1},  \ldots, \class{p_{l'}}
  25     dont les éléments ont été renommés et soit
  26     $m$ le plus grand indice des elements de \class{p_1}, \ldots,
  27     \class{p_{l'}}.
  28     Soit une autre classe \class{p} qui dépend exclusivement d'une classe
  29     \class{p_i}, $1 \le i \le l'$ et qui contient $k$ elements.
  30     Les éléments de \class{p} sont renommés par  $m+1$, \ldots, $m+k$.
  31     Ce processus a été appliqué sur  $l'+1$ classes. Il se termine
  32     puisqu'il diminue le nombre d'elements auquel il reste
  33     à affecter un numéro.
  34
  35     Il reste à montrer que cette méthode de renommage vérifie la propriété
  36     énoncée dans le lemme.
  37     Cette preuve se fait par induction sur la taille  $l$
  38     du plus grand chemin de dépendance entre les classes.
  39
  40     Tout d'abord, si \class{p} $\preceq$ \class{q} et \class{q}
  41     dépend immédiatement de
  42     \class{p},  \textit{i.e.}
  43     le chemin le plus long entre les éléments de   \class{p} et les
  44     elements de \class{q} est de longueur 1.
  45     En raison de la méthode renommage, chaque numéro d'élément
  46     \class{q}  est plus grand que tous ceux de  \class{p} et la preuve est
  47     établie.
  48     Soit \class{p} et  \class{q} tels que le plus long chemin de dépendance
  49     entre \class{p} et  \class{q} a une longueur de $l+1$.
  50     Il existe alors une classe
  51     \class{q'} telle que \class{q}
  52     dépend immédiatement de  \class{q'} et le chemin de dépendance le
  53     plus long entre \class{p} et  \class{q'} a pour longueur $l$.
  54     On a ainsi
  55     \class{q'}  $\preceq$ \class{q}
  56     et pour tout  $k$, $j$  tels que $k  \in$
  57     \class{q'} et $j  \in$  \class{q},  $k \le  j$.
  58     Par hypothèse d'induction,
  59     \class{p}  $\preceq$ \class{q'}  et pour chaque  $i$, $k$  tels que $i  \in$
  60     \class{p} et  $k \in$ \class{q'}, $i \le k$
  61     et le résultat est établi.
  62   \end{Proof}
  63 \end{lemma}
  64
  65 On peut remarquer que ce processus de renommage est inspiré des \emph{graphes
  66   par couches } de Golès et Salinas~\cite{GS08}.
  67
  68 % \begin{xpl}
  69 %   We  have \class{1}  $=\{1,2\}$, \class{3}  $=\{3\}$ and  \class{4} $=\{4,5\}$.
  70 %   Processes numbers are already compliant with the order $\preceq$.
  71 % \end{xpl}
  72
  73 \begin{Proof}[du théorème~\ref{th:cvg}]
  74
  75   Le reste de la preuve est fait par induction sur le numéro de classe.
  76   Considérons la première  classe \class{b_1} de $n_1$ éléments
  77   \textit{i.e.} la classe avec le plus petit identifiant.
  78
  79   D'après les hypothèses du  théorème, %following the strategy $(S^t)$,
  80   les itérations synchrones convergent vers un point fixe en un nombre
  81   fini d'itérations. %pseudo periods. % [[JFC : borner m1/n1]].
  82   Ainsi toutes les  \emph{classes sources}
  83   (indépendantes de toutes les  autres classes) vont aussi converger
  84   dans le mode mixe.
  85   On peut ainsi  supposer que le  mode d'itération mixe avec délais
  86   uniformes fait converger les classes \class{b_1},  \ldots, \class{b_k}
  87   en  un temps $t_k$.
  88   Par construction, la classe \class{b_{k+1}}  dépend uniquement
  89   de certaines classes de  \class{b_1}, \ldots,
  90   \class{b_k} et éventuellement d'elle-même.
  91   Il existe un nombre d'iteration suffisamment grand
  92   $t_0$  tel que  $D^{t_0}_{p_{k+1}p_j}$  est suppérieur ou égal à   $t_k$
  93   pour chaque
  94   $p_{k+1} \in$ \class{b_{k+1}} et $p_j \in$ \class{b_j}, $1 \le j \le k$.
  95
  96   Il ne reste donc que des itérations synchrones entre les
  97   elements  of \class{b_{k+1}} en démarant dans des configurations
  98   où tous les éléments de  \class{b_j}, $1 \le j
  99   \le k$, ont  des valeurs constantes.
 100   D'après les hypothèses du théorème, cela converge.
 101 \end{Proof}
 102
 103
 104