]> AND Private Git Repository - prng_gpu.git/commitdiff
Logo AND Algorithmique Numérique Distribuée

Private GIT Repository
Fin d'un premier jet des basic recalls
authorChristophe Guyeux <christophe.guyeux@univ-fcomte.fr>
Thu, 8 Sep 2011 15:05:23 +0000 (17:05 +0200)
committerChristophe Guyeux <christophe.guyeux@univ-fcomte.fr>
Thu, 8 Sep 2011 15:05:23 +0000 (17:05 +0200)
prng_gpu.tex

index 985faee77c6a470dbbb13b700daa18d934df7d4b..537feef1ed568e1d4c3c9891bef7af37510dd0c6 100644 (file)
@@ -163,6 +163,40 @@ X^{k+1}=G_{f}(X^k).%
 
 With this formulation, a shift function appears as a component of chaotic iterations. The shift function is a famous example of a chaotic map~\cite{Devaney} but its presence is not sufficient enough to claim $G_f$ as chaotic. 
 
+To study this claim, a new distance between two points $X = (S,E), Y = (\check{S},\check{E})\in
+\mathcal{X}$ has been introduced in \cite{guyeux10} as follows:
+\begin{equation*}
+d(X,Y)=d_{e}(E,\check{E})+d_{s}(S,\check{S}),
+\end{equation*}
+\noindent where
+\begin{equation*}
+\left\{
+\begin{array}{lll}
+\displaystyle{d_{e}(E,\check{E})} & = & \displaystyle{\sum_{k=1}^{\mathsf{N}%
+}\delta (E_{k},\check{E}_{k})}, \\
+\displaystyle{d_{s}(S,\check{S})} & = & \displaystyle{\dfrac{9}{\mathsf{N}}%
+\sum_{k=1}^{\infty }\dfrac{|S^k-\check{S}^k|}{10^{k}}}.%
+\end{array}%
+\right.
+\end{equation*}
+
+
+This new distance has been introduced to satisfy the following requirements.
+\begin{itemize}
+\item When the number of different cells between two systems is increasing, then their distance should increase too.
+\item In addition, if two systems present the same cells and their respective strategies start with the same terms, then the distance between these two points must be small because the evolution of the two systems will be the same for a while. Indeed, the two dynamical systems start with the same initial condition, use the same update function, and as strategies are the same for a while, then components that are updated are the same too.
+\end{itemize}
+The distance presented above follows these recommendations. Indeed, if the floor value $\lfloor d(X,Y)\rfloor $ is equal to $n$, then the systems $E, \check{E}$ differ in $n$ cells. In addition, $d(X,Y) - \lfloor d(X,Y) \rfloor $ is a measure of the differences between strategies $S$ and $\check{S}$. More precisely, this floating part is less than $10^{-k}$ if and only if the first $k$ terms of the two strategies are equal. Moreover, if the $k^{th}$ digit is nonzero, then the $k^{th}$ terms of the two strategies are different.
+
+Finally, it has been established in \cite{guyeux10} that,
+
+\begin{proposition}
+$G_{f}$ must be continuous in the metric
+space $(\mathcal{X},d)$.
+\end{proposition}
+
+The chaotic property of $G_f$ has been firstly established for the vectorial Boolean negation \cite{guyeux10}. To obtain a characterization, we have introduced the notion of asynchronous iteration graph recalled bellow.
+
 Let $f$ be a map from $\mathds{B}^n$ to itself. The
 {\emph{asynchronous iteration graph}} associated with $f$ is the
 directed graph $\Gamma(f)$ defined by: the set of vertices is
@@ -173,7 +207,7 @@ path from $x$ to $x'$ in $\Gamma(f)$ if and only if there exists a
 strategy $s$ such that the parallel iteration of $G_f$ from the
 initial point $(s,x)$ reaches the point $x'$.
 
-We have proven in \cite{FCT11} that,
+We have finally proven in \cite{FCT11} that,
 
 
 \begin{theorem}