X-Git-Url: https://bilbo.iut-bm.univ-fcomte.fr/and/gitweb/hdrcouchot.git/blobdiff_plain/2bf0bca226facdce323e96552021bf90952eefce..020defdbb2ac938563eba1071c78520973093e4b:/15RairoGen.tex?ds=inline

diff --git a/15RairoGen.tex b/15RairoGen.tex
index aff664f..63eb23b 100644
--- a/15RairoGen.tex
+++ b/15RairoGen.tex
@@ -146,8 +146,8 @@ et $h(x_1,x_2)=(\overline{x_1},x_1\overline{x_2}+\overline{x_1}x_2)$.
 Leurs graphes d'interactions donnés en figure \ref{fig:g:inter} et \ref{fig:h:inter}
 vérifient les hypothèses du théorème~\ref{th:Adrien}. 
 Leurs graphes d'itérations
-sont donc fortement connexes, ce que l'on peut vérifier aux figures
-\ref{fig:g:iter} et \ref{fig:h:iter}.
+sont donc fortement connexes, ce que l'on peut vérifier aux figures~\ref{fig:g:iter} 
+et~\ref{fig:h:iter}.
 \textit{A priori}, ces deux fonctions pourraient être intégrées
 dans un générateur de nombres pseudo aléatoires. Montrons que ce n'est pas le cas pour $g$ et 
 que cela l'est pour $h$.
@@ -332,15 +332,21 @@ ce vecteur au vecteur $\pi=(\frac{1}{2^n},\ldots,\frac{1}{2^n})$
 -- autrement dit, où la déviation par rapport à la distribution uniforme --
  est inférieure 
 à $10^{-4}$. En prenant le max pour tous les $e_i$, on obtient une valeur pour
- $b$. Ainsi, on a 
-$$
+ $b$. 
+Ainsi, on a 
+\begin{equation}
 b = \max\limits_{i \in \llbracket 1, 2^n \rrbracket} 
 \{
 \min \{
  t \mid t \in \Nats, \vectornorm{e_i M_f^t - \pi} < 10^{-4}
 \}
 \}. 
-$$
+\label{eq:mt:ex}
+\end{equation}
+
+\noindent Par la suite, ce nombre sera appelé \emph{temps de mélange}.
+
+
 
 \begin{figure}%[h]
   \begin{center}
@@ -648,5 +654,98 @@ $d$ est une distance sur $\mathcal{X}_{\mathsf{N},\mathcal{P}}$.
 
 \subsection{Le graphe $\textsc{giu}_{\mathcal{P}}(f)$ étendant  $\textsc{giu}(f)$}
 
+A partir de  $\mathcal{P}=\{p_1, p_2, \hdots, p_\mathsf{p}\}$, on 
+definit le graphe orienté $\textsc{giu}_{\mathcal{P}}(f)$ de la manière suivante:
+\begin{itemize}
+\item les n{\oe}uds sont les  $2^\mathsf{N}$ configurations de $\mathds{B}^\mathsf{N}$,
+%\item Each vertex has $\displaystyle{\sum_{i=1}^\mathsf{p} \mathsf{N}^{p_i}}$ arrows, namely all the $p_1, p_2, \hdots, p_\mathsf{p}$ tuples 
+%  having their elements in $\llbracket 1, \mathsf{N} \rrbracket $.
+\item il y a un arc libellé $u_0, \hdots, u_{p_i-1}$, $i \in \llbracket 1, \mathsf{p} \rrbracket$ entre les n{\oe}uds $x$ et $y$ si et seulement si $p_i$ est un élément de 
+$\mathcal{P}$ (\textit{i.e.}, on peut itérer $p_i$ fois), 
+chaque $u_k$ de la suite appartient à $[\mathsf{N}]$ et 
+$y=F_{f_u,p_i} (x, (u_0, \hdots, u_{p_i-1})) $.
+\end{itemize}
+Il n'est pas difficile de constater que $\textsc{giu}_{\{1\}}(f)$ est $\textsc{giu}(f)$.
+
+
+
+
+
+\begin{figure}%[t]
+  \begin{center}
+    \subfigure[$\textsc{giu}_{\{2\}}(h)$]{
+      \begin{minipage}{0.30\textwidth}
+        \begin{center}
+          \includegraphics[height=4cm]{images/h2prng}
+        \end{center}
+      \end{minipage}
+      \label{fig:h2prng}
+    }
+    \subfigure[$\textsc{giu}_{\{3\}}(h)$]{
+      \begin{minipage}{0.40\textwidth}
+        \begin{center}
+          \includegraphics[height=4cm]{images/h3prng}
+        \end{center}
+      \end{minipage}
+      \label{fig:h3prng}
+    }
+    \subfigure[$\textsc{giu}_{\{2,3\}}(h)$]{
+      \begin{minipage}{0.40\textwidth}
+        \begin{center}
+          \includegraphics[height=4cm]{images/h23prng}
+        \end{center}
+      \end{minipage}
+      \label{fig:h23prng}
+    }
+
+    \end{center}
+    \caption{Graphes d'iterations $\textsc{giu}_{\mathcal{P}}(h)$ pour $h(x_1,x_2)=(\overline{x_1},x_1\overline{x_2}+\overline{x_1}x_2)$}
+    \label{fig:xplgraphIter}
+  \end{figure}
+
+
+
+
+\begin{xpl}
+On reprend l'exemple où $\mathsf{N}=2$ et 
+$h(x_1,x_2)=(\overline{x_1},x_1\overline{x_2}+\overline{x_1}x_2)$ déjà détaillé 
+à la section~\ref{sub:prng:unif}.
+
+Le graphe $\textsc{giu}_{\{1\}}(h)$ a déjà été donné à la figure~\ref{fig:h:iter}.
+Les graphes $\textsc{giu}_{\{2\}}(h)$, $\textsc{giu}_{\{3\}}(h)$  et
+$\textsc{giu}_{\{2,3\}}(h)$ sont respectivement donnés aux figure~\ref{fig:h2prng}, ~\ref{fig:h3prng} et ~\ref{fig:h23prng}. 
+Le premier (repsectivement le second) 
+illustre le comportement du générateur lorsque qu'on itère exactement 
+2 fois (resp. 3 fois) puis qu'on affiche le résultat.
+Le dernier donnerait le comportement d'un générateur qui s'autoriserait 
+à itérer en interne systématiquement 2 ou trois fois avant de retourner un résultat.
+
+\end{xpl}
+
+
 \subsection{le PRNG de l'algorithme~\ref{CI Algorithm} est chaotique sur $\mathcal{X}_{\mathsf{N},\mathcal{P}}$}
 
+Le théorème suivant, similaire à celui dans $\mathcal{X}_u$ et dans $\mathcal{X}_g$
+est prouvé en annexes~\ref{anx:generateur}.
+
+\begin{theorem}
+La fonction $G_{f_u,\mathcal{P}}$ est chaotique sur 
+ $(\mathcal{X}_{\mathsf{N},\mathcal{P}},d)$ si et seulement si 
+graphe d'itération $\textsc{giu}_{\mathcal{P}}(f)$ 
+est fortement connexe.
+\end{theorem}
+On alors corollaire suivant 
+
+\begin{corollary}
+  Le générateur de nombre pseudo aléatoire détaillé 
+  à l'algorithme~\ref{CI Algorithm}
+  n'est pas chaotique 
+  sur $(\mathcal{X}_{\mathsf{N},\{b\}},d)$ pour la fonction négation.
+\end{corollary}
+\begin{proof}
+  Dans cet algorithme, $\mathcal{P}$ est le singleton $\{b\}$.
+  Que $b$ soit pair ou impair,  $\textsc{giu}_{\mathcal{b}}(f)$
+  n'est pas fortement connexe.
+\end{proof}
+
+