X-Git-Url: https://bilbo.iut-bm.univ-fcomte.fr/and/gitweb/hdrcouchot.git/blobdiff_plain/75aa438e61284f634375e2c1e62c79f2af12678f..d33e664452e3655370cbe069e3f6fbd16842c818:/15RairoGen.tex?ds=sidebyside

diff --git a/15RairoGen.tex b/15RairoGen.tex
index 06f84b1..a57e19f 100644
--- a/15RairoGen.tex
+++ b/15RairoGen.tex
@@ -6,25 +6,17 @@ le mot $x^b$ devrait  \og sembler ne plus dÃ©pendre\fg{} de $x^0$.
 On peut penser Ã  exploiter une de ces fonctions $G_f$ 
 comme un gÃ©nÃ©rateur alÃ©atoire. 
 
-Ce chapitre  prÃ©sente une application directe
+Ce chapitre  prÃ©sente donc une application directe
 de la thÃ©orie dÃ©veloppÃ©e ci-avant
 Ã  la gÃ©nÃ©ration de nombres pseudo alÃ©atoires. 
+La section~\ref{sub:prng:algo} 
+prÃ©sente tout d'abord l'algorithme de PRNG. La contrainte de  
+distribution uniforme de la sortie est discutÃ©e dans cette section.
+La chaoticitÃ© du gÃ©nÃ©rateur est ensuite Ã©tudiÃ©e en 
+section~\ref{prng:unaire:chaos}.
+La section~\ref{sub:prng:algo}  a Ã©tÃ© publiÃ©e Ã  ~\cite{bcgw11:ip,bcgr11:ip}.
 
 
-La suite de ce document donnera
-une condition nÃ©cessaire est suffisante pour que
-cette propriÃ©tÃ© soit satisfaite.
-
-
-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 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.
-\JFC{plan Ã  revoir}
- 
-
 \section{ Nombres pseudo alÃ©atoires construits par itÃ©rations unaires}\label{sub:prng:algo}
 
 
@@ -67,7 +59,7 @@ En interne, il exploite un algorithme de gÃ©nÃ©ration
 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Ã©.
+Notre approche vise a donner des propriÃ©tÃ©s de chaos Ã  ce gÃ©nÃ©rateur embarquÃ©.
 
 
 % \textit{Random}$(l)$. 
@@ -105,11 +97,11 @@ Notre approche vise a donner des propriÃ©tÃ©s de chaos a ce gÃ©nÃ©rateur embarqu
 
 Nous avons vu au chapitre~\ref{chap:carachaos} que 
 $G_{f_u}$ est chaotique dans l'espace $\mathcal{X}_u$ 
-si et seulement le graphe d'itÃ©rations $\textsc{giu}(f)$ 
+si et seulement si le graphe d'itÃ©rations $\textsc{giu}(f)$ 
 est fortement connexe.
 Pour $b=1$, l'algorithme itÃ¨re la fonction $F_{f_u}$.
 
-Pour simuler au mieux l'alÃ©a, un bon gÃ©nÃ©rateur de nombre pseudo-alÃ©atoires
+Pour simuler au mieux l'alÃ©a, un bon gÃ©nÃ©rateur de nombres pseudo-alÃ©atoires
 se doit de fournir  des nombres selon une distribution uniforme.
 Regardons comment l'uniformitÃ© de la distribution 
 contraint la fonction $f$ Ã  itÃ©rer.
@@ -126,7 +118,7 @@ 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 le thÃ©orÃ¨me classique suivant liant les 
-vecteur de probabilitÃ©s 
+vecteurs de probabilitÃ©s 
 et les chaÃ®nes de Markov.
 
 
@@ -148,7 +140,7 @@ et les chaÃ®nes de Markov.
 Montrons sur un exemple jouet Ã  deux Ã©lÃ©ments 
 que ce thÃ©orÃ¨me permet de vÃ©rifier si la sortie d'un gÃ©nÃ©rateur de 
 nombres pseudo alÃ©atoires est uniformÃ©ment distribuÃ©e ou non.
-Soit alors $g$ et $h$ deux fonctions  de $\Bool^2$
+Soient alors $g$ et $h$ deux fonctions  de $\Bool^2$
 dÃ©finies par $g(x_1,x_2)=(\overline{x_1},x_1.\overline{x_2}) $
 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}
@@ -302,9 +294,9 @@ 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 Ã©nonce 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 annexe~\ref{anx:generateur}.
 
-\begin{theorem}\label{thm:prng:u}
+\begin{restatable}[UniformitÃ© de la sortie de l'algorithme~\ref{CI Algorithm}]{theorem}{PrngCIUniforme}\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$  
@@ -315,7 +307,7 @@ On Ã©nonce directement le thÃ©orÃ¨me suivant dont la preuve est donnÃ©e en annex
   l'algorithme~\ref{CI Algorithm} suit une loi qui 
   tend vers la distribution uniforme si 
   et seulement si  $M$ est une matrice doublement stochastique.
-\end{theorem}
+\end{restatable}
 
 
 \subsection{Quelques exemples}
@@ -454,7 +446,7 @@ Montrer que les sous-sÃ©quences de suites chaotiques ainsi gÃ©nÃ©rÃ©es  demeuren
 est l'objectif de la section suivante.
 
 
-\section{Un PRNG basÃ© sur des itÃ©rations unaires qui est chaotique }
+\section{Un PRNG basÃ© sur des itÃ©rations unaires qui est chaotique }\label{prng:unaire:chaos}
 
 Cette section prÃ©sente un espace mÃ©trique adaptÃ© au gÃ©nÃ©rateur de nombres pseudo-alÃ©atoires 
 prÃ©sentÃ© Ã  l'algorithme~\ref{CI Algorithm} et prouve ensuite que la fonction qu'il reprÃ©sente 
@@ -486,7 +478,7 @@ F_{f_u}(\hdots (F_{f_u}(F_{f_u}(x,u^0), u^1), \hdots), u^{p_i-1}).
 $$
 
 
-on construit l'espace 
+On construit l'espace 
  $\mathcal{X}_{\mathsf{N},\mathcal{P}}=  \mathds{B}^\mathsf{N} \times \mathds{S}_{\mathsf{N},\mathcal{P}}$, oÃ¹
 $\mathds{S}_{\mathsf{N},\mathcal{P}}=
 [\mathsf{N}]^{\Nats}\times 
@@ -536,7 +528,7 @@ oÃ¹ $s=(u,v)$ et $\check{s}=(\check{u},\check{v})$ sont dans $ \mathds{S}_{\math
 \mathcal{S}_{\llbracket 1, \mathsf{N} \rrbracket} \times \mathcal{S}_\mathcal{P}$. 
 \begin{enumerate}
 \item $e$ et $\check{e}$ sont des entiers appartenant Ã  $\llbracket 0, 2^{\mathsf{N}-1} \rrbracket$. 
-La distance de Hamming $d_{\mathds{B}^\mathsf{N}}$ sur entre les 
+La distance de Hamming $d_{\mathds{B}^\mathsf{N}}$ entre les 
 dÃ©compositions binaires de $e$ et de $\check{e}$ (\textit{i.e.}, le 
 le nombre de bits qu'elles ont de diffÃ©rent) constitue 
 la partie entiÃ¨re de $d(X,\check{X})$.
@@ -566,7 +558,7 @@ jusqu'Ã  atteindre
 $p+n\times \max{(\mathcal{P})}$ Ã©lÃ©ments.
 \item Si $v^0<\check{v}^0$, alors les $ \max{(\mathcal{P})}$  blocs de $n$
 Ã©lÃ©ments sont $|u^0-\check{u}^0|$, ..., $|u^{v^0-1}-\check{u}^{v^0-1}|$,
-$\check{u}^{v^0}$ (sur $n$ Ã©lÃ©ments), ..., $\check{u}^{\check{v}^0-1}$ (sur $n$ Ã©lÃ©ments), suivi par des 0, si besoin.
+$\check{u}^{v^0}$ (sur $n$ Ã©lÃ©ments), ..., $\check{u}^{\check{v}^0-1}$ (sur $n$ Ã©lÃ©ments), suivis par des 0, si besoin.
 \item Le cas $v^0>\check{v}^0$ est similaire, et donc omis
 \end{enumerate}
 \item Les $p$ suivants sont $|v^1-\check{v}^1|$, etc.
@@ -623,7 +615,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 chaÃ®ne obtenue a $n\times \max{(\mathcal{P})}=22$ Ã©lÃ©ments, soit:
+la chaÃ®ne obtenue ait $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 
@@ -660,10 +652,12 @@ la sÃ©quence.
 
 
 
-On a la proposition suivante, qui est dÃ©montrÃ©e en annexes~\ref{anx:generateur}.
-\begin{lemma}
+On a la proposition suivante, qui est dÃ©montrÃ©e en annexe~\ref{anx:generateur}.
+
+
+\begin{restatable}[Une distance dans $\mathcal{X}_{\mathsf{N},\mathcal{P}}$]{theorem}{distancedsxnp}
 $d$ est une distance sur $\mathcal{X}_{\mathsf{N},\mathcal{P}}$.
-\end{lemma}
+\end{restatable}
 
 
 \subsection{Le graphe $\textsc{giu}_{\mathcal{P}}(f)$ Ã©tendant  $\textsc{giu}(f)$}
@@ -677,7 +671,7 @@ dÃ©finit le graphe orientÃ© $\textsc{giu}_{\mathcal{P}}(f)$ de la maniÃ¨re suiva
 \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), et pour chaque 
 $k$, $0 \le k \le p_i-1$, on a 
- $u_k$ qui apaprtient Ã   $[\mathsf{N}]$ et 
+ $u_k$ qui 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)$.
@@ -728,12 +722,12 @@ $h(x_1,x_2)=(\overline{x_1},x_1\overline{x_2}+\overline{x_1}x_2)$ dÃ©jÃ  dÃ©tail
 
 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}. 
+$\textsc{giu}_{\{2,3\}}(h)$ sont respectivement donnÃ©s aux figures~\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.
+Ã  itÃ©rer en interne systÃ©matiquement 2 ou 3 fois avant de retourner un rÃ©sultat.
 
 \end{xpl}
 
@@ -741,26 +735,35 @@ Le dernier donnerait le comportement d'un gÃ©nÃ©rateur qui s'autoriserait
 \subsection{le PRNG de l'algorithme~\ref{CI Algorithm} est chaotique sur $\mathcal{X}_{\mathsf{N},\mathcal{P}}$}
 
 Le thÃ©orÃ¨me suivant, similaire Ã  ceux dans $\mathcal{X}_u$ et dans $\mathcal{X}_g$
-est prouvÃ© en annexes~\ref{anx:generateur}.
+est prouvÃ© en annexe~\ref{anx:generateur}.
 
-\begin{theorem}
+\begin{restatable}[Conditions pour la chaoticitÃ© de $G_{f_u,\mathcal{P}}$]{theorem}{thmchoticitgfp}
 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)$ 
+le graphe d'itÃ©rations $\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}_{\{b\}}(f)$
-  n'est pas fortement connexe.
-\end{proof}
-
+\end{restatable}
+% 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}_{\{b\}}(f)$
+%   n'est pas fortement connexe.
+% \end{proof}
+
+
+\section{Conclusion}
+Ce chapitre a proposÃ© un algorithme permettant de construire un 
+PRNG chaotique Ã  partir d'un PRNG existant. Pour ce faire, il est nÃ©cessaire 
+et suffisant que la fonction $f$ qui est itÃ©rÃ©e un nombre $b$ de fois 
+possÃ¨de un $\textsc{giu}_{\{b\}}(f)$ fortement connexe et que sa matrice de Markov associÃ©e soit doublement stochastique.
+Le chapitre suivant montre comment construire une telle fonction.
 
+ 
+ 
