]> AND Private Git Repository - hdrcouchot.git/blob - annexecontinuite.tex
Logo AND Algorithmique Numérique Distribuée

Private GIT Repository
ajout des sources bittar
[hdrcouchot.git] / annexecontinuite.tex
1 Montrons que pour toute fonction booléenne 
2 $f$ de $\Bool^n$ dans lui même,  $G_f$ est continue sur $(\mathcal{X},d)$.
3
4 Soit donc $(s_t,x^t)^{t \in \Nats}$ une suite de points de
5 l'espace $\mathcal{X}$ qui converge vers $(s,x)$.
6 Montrons que $(G_f (s_t,x^t))^{t \in \Nats}$ converge vers $G_f (s,x)$.
7  
8 La distance $d((s_t,x^t), (s,x))$ tend vers 0. 
9 Il en est donc de même pour $d_H(x^t, x)$ et $d_S(s_t, s)$.
10 Or, $d_H(x^t, x)$ ne prend que des valeurs entières.
11 Cette distance est donc nulle à partir d'un certain $t_0$.
12 Ainsi, à partir de $t>t_0$, on a  $x^t = x$ . 
13 De plus, $d_S(s_t, s)$ tend vers $0$ donc $d_S(s_t, s) < 10^{-1}$ 
14 à partir d'un certain rang $t_1$. 
15 Ainsi, à partir de $t>t_1$, les suites $(s_t)_{t \in \Nats}$ 
16 ont toutes le même premier terme, qui est celui
17 de $s$ pour $t$ supérieur à $t_1$. 
18 Pour $t > \max(t_0,t_1)$, les configurations $x^t$ et $x$
19 sont les mêmes, 
20 et les stratégies $s_t$ et $s$ ont le même premier terme 
21 ($s_0^t = s_0$), donc les configurations 
22 de $F_f(s_0^t,x^t)$ et de $F_f (s_0,x)$ sont égales et donc la distance 
23 entre $G_f(s_t,x^t)$ et $G_f (s,x)$  est inférieure à 1.
24
25 Montrons maintenant que la distance entre
26 $G_f (s_t,x^t)$ et  $G_f (s,x)$
27 tend bien vers 0 quand $t$ tend vers $+\infty$. Soit $\epsilon > 0$.
28 \begin{itemize}
29   \item Si $\epsilon \ge 1$. Comme la distance $d(G_f(s_t,x^t), G_f (s,x))<1$
30     pour $t >  \max(t_0, t_1)$, alors 
31     $d(G_f(s_t,x^t), G_f (s,x))<\epsilon$
32   \item Si $\epsilon < 1$, alors $\exists k \in  \Nats \textrm{ tel que } 
33     10^{-k} > \epsilon > 10^{-(k+1)}$. 
34     Comme $d_S(s_t, s)$ tend vers 0, il existe
35 un rang $t_2$ à partir duquel 
36 $\forall t > t_2 ,  d_S(s_t, s) < 10^{-(k+2)}$:
37 à partir de ce rang, les $k+2$ premiers termes de $s_t$ sont ceux de $s$.
38 Donc les $k + 1$ premiers termes des stratégies de 
39 $G_f (s_t,x^t)$ et de
40 $G_f (s,x)$ sont les mêmes (puisque $G_f$ 
41 opère un décalage sur les stratégies), et vue la
42 définition de $d_S$, la partie décimale de la distance entre les points 
43 $(s_t,x^t)$ et $(s,x)$ est
44 inférieure à $10^{-(k+1)} \le \epsilon$.
45 \end{itemize}
46 Pour conclure, pour tout $\epsilon > 0$, 
47 $\exists~T_0 = \max(t_0, t_1, t_2) \in \Nats \textrm{ tel que } 
48 \forall t > T_0 , d (Gf (s_t,x^t),G_f (s,x))< \epsilon$.