après remarques tof

[hdrcouchot.git] / 15RairoGen.tex

diff --git a/15RairoGen.tex b/15RairoGen.tex
index 432991fb638780d70496df8040141d53282eeb99..38920d84a268272246b2ab2c3ac81a4112f58e3d 100644 (file)
--- a/15RairoGen.tex
+++ b/15RairoGen.tex
@@ -8,7 +8,7 @@ comme un générateur aléatoire.
 
 Ce chapitre  présente donc une application directe
 de la théorie développée ci-avant
 
 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 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 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.


@@ -17,7 +17,7 @@ section~\ref{prng:unaire:chaos}.
 La section~\ref{sub:prng:algo}  a été publiée à ~\cite{bcgw11:ip,bcgr11:ip}.
 
 
 La section~\ref{sub:prng:algo}  a été publiée à ~\cite{bcgw11:ip,bcgr11:ip}.
 
 

-\section{ Nombres pseudo aléatoires construits par itérations unaires}\label{sub:prng:algo}
+\section{ Nombres pseudo-aléatoires construits par itérations unaires}\label{sub:prng:algo}

 
 
 
 
 
 


@@ -44,8 +44,8 @@ return $x$\;
 \end{algorithm}
 
 \subsection{Algorithme d'un générateur}
 \end{algorithm}
 
 \subsection{Algorithme d'un générateur}

-On peut penser à construire un générateur de nombres pseudo 
-aléatoires comme dans l'algorithme~\ref{CI Algorithm} donné ci-dessous.
+On peut penser à construire un générateur de nombres 
+pseudo-aléatoires comme dans l'algorithme~\ref{CI Algorithm} donné ci-dessous.

 
 
 Celui-ci prend en entrée: une fonction $f$;
 
 
 Celui-ci prend en entrée: une fonction $f$;


@@ -56,10 +56,10 @@ la fonction $F_{f_u}$ (équation~\ref{eq:iterations:unaires}
 vue au chapitre~\ref{chap:carachaos}) et correspondant 
 à des itérations unaires.
 En interne, il exploite un algorithme de génération
 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 donné en paramètre.
+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.
 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)$. 
 
 
 % \textit{Random}$(l)$. 


@@ -97,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$ 
 
 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}$.
 
 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.
 se doit de fournir  des nombres selon une distribution uniforme.
 Regardons comment l'uniformité de la distribution 
 contraint la fonction $f$ à itérer.


@@ -118,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 
 $$\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.
 
 
 et les chaînes de Markov.
 
 


@@ -139,8 +139,8 @@ 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 
 
 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$
+nombres pseudo-aléatoires est uniformément distribuée ou non.
+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}
 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}


@@ -149,7 +149,7 @@ 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}.
 \textit{A priori}, ces deux fonctions pourraient être intégrées
 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 
+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$.
 
 
 que cela l'est pour $h$.
 
 


@@ -283,10 +283,10 @@ Alors d'après le théorème~\ref{th},
 pour n'importe quel vecteur initial de probabilités $\pi^0$, on a 
 $\lim_{k \to \infty} \pi^0 M^k_g = \pi_g$ et 
 $\lim_{k \to \infty} \pi^0 M^k_h = \pi_h$. 
 pour n'importe quel vecteur initial de probabilités $\pi^0$, on a 
 $\lim_{k \to \infty} \pi^0 M^k_g = \pi_g$ et 
 $\lim_{k \to \infty} \pi^0 M^k_h = \pi_h$. 

-Ainsi la chaîne de Markov associé à $h$ tend vers une 
+Ainsi la chaîne de Markov associée à $h$ tend vers une 

 distribution uniforme, contrairement à celle associée à $g$.
 On en déduit que $g$ ne devrait pas être itérée dans 
 distribution uniforme, contrairement à celle associée à $g$.
 On en déduit que $g$ ne devrait pas être itérée dans 

-un générateur de nombres pseudo aléatoires.
+un générateur de nombres pseudo-aléatoires.

 Au contraire, 
 $h$ devrait pouvoir être embarquée dans l'algorithme~\ref{CI Algorithm}, 
 pour peu que le nombre $b$ d'itérations entre deux mesures successives 
 Au contraire, 
 $h$ devrait pouvoir être embarquée dans l'algorithme~\ref{CI Algorithm}, 
 pour peu que le nombre $b$ d'itérations entre deux mesures successives 


@@ -294,7 +294,7 @@ 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.
 
 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{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 
 
 \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 


@@ -303,7 +303,7 @@ On énonce directement le théorème suivant dont la preuve est donnée en annex
   définie par 
   $M = \dfrac{1}{n} \check{M}$.
   Si $\textsc{giu}(f)$ est fortement connexe, alors 
   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 
+  la sortie du générateur de nombres pseudo-aléatoires détaillé par 

   l'algorithme~\ref{CI Algorithm} suit une loi qui 
   tend vers la distribution uniforme si 
   et seulement si  $M$ est une matrice doublement stochastique.
   l'algorithme~\ref{CI Algorithm} suit une loi qui 
   tend vers la distribution uniforme si 
   et seulement si  $M$ est une matrice doublement stochastique.


@@ -325,7 +325,7 @@ Expliquons enfin comment a été calculé le nombre de la troisième
 colonne utilisé comme le paramètre $b$ 
 dans l'algorithme~\ref{CI Algorithm}.
 
 colonne utilisé comme le paramètre $b$ 
 dans l'algorithme~\ref{CI Algorithm}.
 

-Soit $e_i$ le $i^{\textrm{ème}}$ vecteur la base canonique de $\R^{2^{n}}$. 
+Soit $e_i$ le $i^{\textrm{ème}}$ vecteur de la base canonique de $\R^{2^{n}}$. 

 Chacun des éléments $v_j$, $1 \le j \le 2^n$, 
 du vecteur $e_i M_f^t$ représente la probabilité 
 d'être dans la configuration $j$ après $t$ étapes du processus de Markov 
 Chacun des éléments $v_j$, $1 \le j \le 2^n$, 
 du vecteur $e_i M_f^t$ représente la probabilité 
 d'être dans la configuration $j$ après $t$ étapes du processus de Markov 


@@ -431,7 +431,7 @@ $\mathcal{F}_{16}$ &14, 15, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 0
 
 La qualité des séquences aléatoires a été évaluée à travers la suite 
 de tests statistiques développée pour les générateurs de nombres 
 
 La qualité des séquences aléatoires a été évaluée à travers la suite 
 de tests statistiques développée pour les générateurs de nombres 

-pseudo aléatoires par le 
+pseudo-aléatoires par le 

 \emph{National Institute of Standards and Technology} (NIST).
 L'expérience a montré notamment que toutes ces fonctions
 passent avec succès cette batterie de tests.
 \emph{National Institute of Standards and Technology} (NIST).
 L'expérience a montré notamment que toutes ces fonctions
 passent avec succès cette batterie de tests.


@@ -478,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 
  $\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 


@@ -528,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$. 
 \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})$.
 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})$.


@@ -558,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}|$,
 $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.
 \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.


@@ -615,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 
 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 
 0600000000000000000000. 
 De manière similaire, les $\check{v}^0=2$ premiers
 termes de $\check{u}$ sont représentés par 


@@ -652,7 +652,7 @@ la séquence.
 
 
 
 
 
 

-On a la proposition suivante, qui est démontrée en annexes~\ref{anx:generateur}.
+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}
 
 
 \begin{restatable}[Une distance dans $\mathcal{X}_{\mathsf{N},\mathcal{P}}$]{theorem}{distancedsxnp}


@@ -722,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
 
 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 
 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}
 
 
 \end{xpl}
 


@@ -735,12 +735,12 @@ 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$
 \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{restatable}[Conditions pour la choticité de $G_{f_u,\mathcal{P}}$]{theorem}{thmchoticitgfp}
+\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 
 La fonction $G_{f_u,\mathcal{P}}$ est chaotique sur 
  $(\mathcal{X}_{\mathsf{N},\mathcal{P}},d)$ si et seulement si 

-le graphe d'itération $\textsc{giu}_{\mathcal{P}}(f)$ 
+le graphe d'itérations $\textsc{giu}_{\mathcal{P}}(f)$ 

 est fortement connexe.
 \end{restatable}
 % On alors corollaire suivant 
 est fortement connexe.
 \end{restatable}
 % On alors corollaire suivant