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