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

diff --git a/15RairoGen.tex b/15RairoGen.tex
index aff664f..a950d85 100644
--- a/15RairoGen.tex
+++ b/15RairoGen.tex
@@ -16,7 +16,7 @@ Cette section prÃ©sente une application directe de la thÃ©orie dÃ©veloppÃ©e ci-a
 Ã  la gÃ©nÃ©ration de nombres pseudo alÃ©atoires. 
 On prÃ©sente tout d'abord le gÃ©nÃ©rateur
 basÃ© sur des fonctions chaotiques (section~\ref{sub:prng:algo}), 
-puis comment intÃ©grer la contrainte de distributionuniforme
+puis comment intÃ©grer la contrainte de distribution uniforme
 de la sortie 
 dans le choix de la fonction Ã  itÃ©rer (section~\ref{sub:prng:unif}). 
 L'approche est Ã©valuÃ©e dans la derniÃ¨re section.
@@ -46,8 +46,7 @@ $x\leftarrow{F_{f_u}(s,x)}$\;
 }
 return $x$\;
 %\end{scriptsize}
-\caption{Algorithme de gÃ©nÃ©ration de nombres pseudo alÃ©atoires 
-Ã  l'aide de la fonction chaotique $G_f$}
+\caption{PRNG basÃ© sur les itÃ©rations unaires.}
 \label{CI Algorithm}
 \end{algorithm}
 
@@ -64,38 +63,43 @@ Il retourne une nouvelle configuration $x$ en appliquant
 la fonction $F_{f_u}$ vue au chapitre~\ref{chap:carachaos} et correspondant 
 Ã  des itÃ©rations unaires.
 En interne, il exploite un algorithme de gÃ©nÃ©ration
-de nombres pseudo alÃ©atoires
-\textit{Random}$(l)$. 
-Cet algorithme est utilisÃ©e dans notre gÃ©nÃ©rateur pour construire la longueur 
-de la stratÃ©gie ainsi que les Ã©lÃ©ments qui la composent.
-Pratiquement, il retourne des entiers dans $\llbracket 1 ; l \rrbracket$ 
-selon une distributionuniforme et utilise 
-\textit{XORshift} qui est une classe de gÃ©nÃ©rateurs de
-nombres pseudo alÃ©atoires conÃ§us par George Marsaglia. 
-
-
-L'algorithme \textit{XORshift} 
-exploite itÃ©rativement l'opÃ©rateur $\oplus$  
-sur des nombres obtenus grÃ¢ce Ã  des decalages de bits.
-Cet opÃ©rateur, dÃ©fini dans $\Bool^{n}$, 
-applique la fonction \og  xor \fg{} 
-aux bits de mÃªme rang de ses deux opÃ©randes (\og opÃ©ration bit Ã  bit \fg{}).
-Une instance de cette classe est donnÃ©e dans l'algorithme~\ref{XORshift} donnÃ© 
-ci-dessous.
-
-\begin{algorithm}[h]
-%\SetLine
-\KwIn{la configuration interne $z$ (un mot de 32-bit)}
-\KwOut{$y$ (un mot de 32-bits)}
-$z\leftarrow{z\oplus{(z\ll13)}}$\;
-$z\leftarrow{z\oplus{(z\gg17)}}$\;
-$z\leftarrow{z\oplus{(z\ll5)}}$\;
-$y\leftarrow{z}$\;
-return $y$\;
-\medskip
-\caption{Une boucle de l'algorithme de \textit{XORshift}}
-\label{XORshift}
-\end{algorithm}
+de nombres pseudo alÃ©atoires donnÃ© en paramÃ¨tre.
+Cela peut Ãªtre n'importe quel PRNG (XORshift, Mersenne-Twister) dont la 
+sortie est uniformÃ©ment distribuÃ©e.
+Notre approche vise a donner des propriÃ©tÃ©s de chaos a ce gÃ©nÃ©rateur embarquÃ©.
+
+
+% \textit{Random}$(l)$. 
+% Cet algorithme est utilisÃ©e dans notre gÃ©nÃ©rateur pour construire la longueur 
+% de la stratÃ©gie ainsi que les Ã©lÃ©ments qui la composent.
+% Pratiquement, il retourne des entiers dans $\llbracket 1 ; l \rrbracket$ 
+% selon une distribution uniforme et utilise 
+% \textit{XORshift} qui est une classe de gÃ©nÃ©rateurs de
+% nombres pseudo alÃ©atoires conÃ§us par George Marsaglia. 
+
+
+% L'algorithme \textit{XORshift} 
+% exploite itÃ©rativement l'opÃ©rateur $\oplus$  
+% sur des nombres obtenus grÃ¢ce Ã  des dÃ©calages de bits.
+% Cet opÃ©rateur, dÃ©fini dans $\Bool^{n}$, 
+% applique la fonction \og  xor \fg{} 
+% aux bits de mÃªme rang de ses deux opÃ©randes (\og opÃ©ration bit Ã  bit \fg{}).
+% Une instance de cette classe est donnÃ©e dans l'algorithme~\ref{XORshift} donnÃ© 
+% ci-dessous.
+
+% \begin{algorithm}[h]
+% %\SetLine
+% \KwIn{la configuration interne $z$ (un mot de 32-bit)}
+% \KwOut{$y$ (un mot de 32-bits)}
+% $z\leftarrow{z\oplus{(z\ll13)}}$\;
+% $z\leftarrow{z\oplus{(z\gg17)}}$\;
+% $z\leftarrow{z\oplus{(z\ll5)}}$\;
+% $y\leftarrow{z}$\;
+% return $y$\;
+% \medskip
+% \caption{Une boucle de l'algorithme de \textit{XORshift}}
+% \label{XORshift}
+% \end{algorithm}
 
 
 Nous avons vu au chapitre~\ref{chap:carachaos} que 
@@ -118,8 +122,8 @@ si  la propriÃ©tÃ© suivante est Ã©tablie:
 $$\exists k \in \mathds{N}^\ast, \forall i,j \in \llbracket 1; n \rrbracket, M_{ij}^k>0.$$
 
 On Ã©nonce enfin le thÃ©orÃ¨me suivant liant les 
-vecteur de probabilite 
-et les chaines de Markov.
+vecteur de probabilitÃ©s 
+et les chaÃ®nes de Markov.
 
 
  
@@ -128,11 +132,11 @@ et les chaines de Markov.
   Si $M$ est une matrice stochastique rÃ©guliÃ¨re, alors $M$ 
   possÃ¨de un unique vecteur stationnaire de probabilitÃ©s  $\pi$
   ($\pi.M = \pi$).
-  De plus, si $\pi^0$ est un {vecteurDeProbabilite} 
+  De plus, si $\pi^0$ est un {vecteur de probabilitÃ©s} 
  et si on dÃ©finit 
   la suite $(\pi^{k})^{k \in  \Nats}$ par 
   $\pi^{k+1} = \pi^k.M $ pour $k = 0, 1,\dots$ 
-  alors la {chaineDeMarkov} $\pi^k$
+  alors la {chaÃ®ne de Markov} $\pi^k$
   converge vers $\pi$ lorsque $k$ tend vers l'infini.
 \end{theorem}
 
@@ -146,8 +150,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$.
@@ -178,7 +182,8 @@ que cela l'est pour $h$.
       \end{minipage}
       \label{fig:h:iter}
     }    \end{center}
-    \caption{Graphes d'itÃ©rations de fonctions boolÃ©ennes dans $\Bool^2$}
+    \caption{Graphes des itÃ©rations unaires 
+      de fonctions boolÃ©ennes dans $\Bool^2$}
     \label{fig:xplgraphIter}
   \end{figure}
 
@@ -228,7 +233,7 @@ Il est facile de vÃ©rifier que la matrice de transitions
 d'un tel processus 
 est $M_g   = \frac{1}{2} \check{M}_g$, 
 oÃ¹ $\check{M}_g$ est la matrice d' adjacence  donnÃ©e en 
-figure~\ref{fig:g:incidence} (voir ci-aprÃ¨s), et similairement pour $M_h$. 
+figure~\ref{fig:g:incidence} (voir ci-aprÃ¨s), et  de maniÃ¨re similaire pour $M_h$. 
 
 \begin{figure}[h]
   \begin{center}
@@ -293,12 +298,14 @@ de valeurs  soit suffisamment grand de sorte que
 le vecteur dâÃ©tat de la chaÃ®ne de Markov
 ait une distribution suffisamment proche de la distribution uniforme.
 
-On Ã©nnonce directement le thÃ©orÃ¨me suivant dont la preuve est donnÃ©e en annexes~\ref{anx:generateur}.
+On Ã©nonce directement le thÃ©orÃ¨me suivant dont la preuve est donnÃ©e en annexes~\ref{anx:generateur}.
 
-\begin{theorem}
+\begin{theorem}\label{thm:prng:u}
   Soit $f: \Bool^{n} \rightarrow \Bool^{n}$, $\textsc{giu}(f)$ son 
   graphe d'itÃ©rations , $\check{M}$ sa matrice d'adjacence
-  et $M$ une matrice  $2^n\times 2^n$  dÃ©finie comme dans le lemme prÃ©cÃ©dent.
+  et $M$ une matrice  $2^n\times 2^n$  
+  dÃ©finie par 
+  $M = \dfrac{1}{n} \check{M}$.
   Si $\textsc{giu}(f)$ est fortement connexe, alors 
   la sortie du gÃ©nÃ©rateur de nombres pseudo alÃ©atoires dÃ©taillÃ© par 
   l'algorithme~\ref{CI Algorithm} suit une loi qui 
@@ -311,7 +318,7 @@ On Ã©nnonce directement le thÃ©orÃ¨me suivant dont la preuve est donnÃ©e en anne
 
 On reprend le graphe d'interactions $\Gamma(f)$ donnÃ© en figure~\ref{fig:G} Ã  la section~\ref{sec:11FCT}.
 On a vu qu'il y avait  520 fonctions $f$ non isomorphes de graphe d'interactions  $\Gamma(f)$, 
-dont seulement 16 d'entre elles possÃ©dent une matrice doublement stochastique.
+dont seulement 16 d'entre elles possÃ¨dent une matrice doublement stochastique.
 
 La figure~\ref{fig:listfonction} explicite ces 16 fonctions en 
 dÃ©finissant les images des Ã©lÃ©ments de la liste
@@ -332,15 +339,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}
@@ -426,8 +439,8 @@ L'expÃ©rience a montrÃ© notamment que toutes ces fonctions
 passent avec succÃ¨s cette batterie de tests.
 
 Pour conclure cette section, on remarque que le gÃ©nÃ©rateur de nombres pseudo-alÃ©atoires 
-a Ã©tÃ© prouvÃ© chaotique pour $b=1$, \textit{i.e.}, lorqu'il y a une sortie pour chaque itÃ©ration.
-Ceci est difficilement compatible avec la volontÃ© d'avoir une sortie uniformÃ©mement distribuÃ©e: 
+a Ã©tÃ© prouvÃ© chaotique pour $b=1$, \textit{i.e.}, lorsqu'il y a une sortie pour chaque itÃ©ration.
+Ceci est difficilement compatible avec la volontÃ© d'avoir une sortie uniformÃ©ment distribuÃ©e: 
 se rapprocher de cette distribution nÃ©cessite en effet un nombre plus Ã©levÃ©
 d'itÃ©rations $b$ entre chaque sortie. Par exemple, dans l'exemple prÃ©cÃ©dent, il est nÃ©cessaire 
 d'itÃ©rer au moins 42 fois entre chaque sortie pour suivre une loi uniforme Ã  $10^{-4}$ prÃ¨s.
@@ -438,7 +451,7 @@ est l'objectif de la section suivante.
 \section{Un PRNG basÃ© sur des itÃ©rations unaires qui est chaotique }
 
 Cette section prÃ©sente un espace mÃ©trique adaptÃ© au gÃ©nÃ©rateur de nombres pseudo-alÃ©atoires 
-pÃ©sentÃ© Ã  l'algorithme~\ref{CI Algorithm} et prouve ensuite que la fonction qu'il reprÃ©sente 
+prÃ©sentÃ© Ã  l'algorithme~\ref{CI Algorithm} et prouve ensuite que la fonction qu'il reprÃ©sente 
 est chaotique sur cet espace.
 
 \subsection{Un espace  $\mathcal{X}_{\mathsf{N},\mathcal{P}}$    pour le PRNG de l'algorithme~\ref{CI Algorithm}}
@@ -455,7 +468,7 @@ Dans l'algorithme~\ref{CI Algorithm},
 $\mathsf{p}$ vaut 1 et  $p_1=b$. 
 
 
-Cet  algorithme peut Ãªtre vu comme $b$ compostions de la function $F_{f_u}$.
+Cet  algorithme peut Ãªtre vu comme $b$ compostions de la fonction $F_{f_u}$.
 Ceci peut cependant se gÃ©nÃ©raliser Ã  $p_i$, $p_i \in \mathcal{P}$,
 compositions fonctionnelles de $F_{f_u}$.
 Ainsi, pour chaque $p_i \in \mathcal{P}$, on construit la fonction
@@ -479,7 +492,7 @@ Le second Ã©lÃ©ment est aussi une paire $((u^k)_{k \in \Nats},(v^k)_{k \in \Nats
 La suite $(v^k)_{k \in \Nats}$ dÃ©finit combien d'itÃ©rations sont exÃ©cutÃ©es au temps $k$ entre deux sorties.
 La sÃ©quence $(u^k)_{k \in \Nats}$ dÃ©finit quel Ã©lÃ©ment est modifiÃ© (toujours au temps $k$).
 
-DÃ©finissons la fonction de dÃ©callage  $\Sigma$ pour chaque  Ã©lÃ©ment de $\mathds{S}_{\mathsf{N},\mathcal{P}}$.
+DÃ©finissons la fonction de dÃ©calage  $\Sigma$ pour chaque  Ã©lÃ©ment de $\mathds{S}_{\mathsf{N},\mathcal{P}}$.
 $$\begin{array}{cccc}
 \Sigma:&\mathds{S}_{\mathsf{N},\mathcal{P}} &\longrightarrow
 &\mathds{S}_{\mathsf{N},\mathcal{P}} \\
@@ -487,7 +500,7 @@ $$\begin{array}{cccc}
 \end{array}
 $$
 En d'autres termes, $\Sigma$ reÃ§oit deux suites $u$ et $v$ et 
-effectue $v^0$ dÃ©callage vers la droite sur la premiÃ¨re et un dÃ©callage vers la droite 
+effectue $v^0$ dÃ©calage vers la droite sur la premiÃ¨re et un dÃ©calage vers la droite 
 sur la seconde.
 
 
@@ -528,7 +541,7 @@ $u^0, u^1, \hdots, u^{v^0-1}$ et  $\check{u}^0, \check{u}^1, \hdots, \check{u}^{
 suivie par les diffÃ©rences entre $u^{v^0}, u^{v^0+1}, \hdots, u^{v^1-1}$ et
 $\check{u}^{\check{v}^0}, \check{u}^{\check{v}^0+1}, \hdots, \check{u}^{\check{v}^1-1}$, etc.
 
-Plus prÃ©cisemment, soit 
+Plus prÃ©cisÃ©ment, soit 
 $p = \lfloor \log_{10}{(\max{\mathcal{P}})}\rfloor +1$ et 
 $n = \lfloor \log_{10}{(\mathsf{N})}\rfloor +1$.
 \begin{itemize}
@@ -603,7 +616,7 @@ On prend alors le $v^0=1$ premier terme de $u$,
 chaque terme Ã©tant codÃ© sur $n=2$ Ã©lÃ©ments, soit 06.
 Comme on itÃ¨re au plus $\max{(\mathcal{P})}$ fois, 
 on complÃ¨te cette valeur par des 0 de sorte que 
-la chaine obtenue a $n\times \max{(\mathcal{P})}=22$ Ã©lÃ©ments, soit:
+la chaÃ®ne obtenue a $n\times \max{(\mathcal{P})}=22$ Ã©lÃ©ments, soit:
 0600000000000000000000. 
 De maniÃ¨re similaire, les $\check{v}^0=2$ premiers
 termes de $\check{u}$ sont reprÃ©sentÃ©s par 
@@ -648,5 +661,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 
+dÃ©finit 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'itÃ©rations $\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 (respectivement 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}
+
+
