version vendredi soir après quelques refs

[hdrcouchot.git] / 15RairoGen.tex

diff --git a/15RairoGen.tex b/15RairoGen.tex
index 4c9a25b340f43c7876454cf8b8411547c3595121..a1b6b23f593a237557b641262d875ad73b252370 100644 (file)
--- 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}), 
 à 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.
 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}
 }
 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}
 
 \label{CI Algorithm}
 \end{algorithm}
 


@@ -69,14 +68,14 @@ de nombres pseudo aléatoires
 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$ 
 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 
+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$  
 \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.
+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{}).
 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{}).


@@ -118,8 +117,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 
 $$\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 +127,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$).
   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$ 
  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}
 
   converge vers $\pi$ lorsque $k$ tend vers l'infini.
 \end{theorem}
 


@@ -228,7 +227,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 
 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}
 
 \begin{figure}[h]
   \begin{center}


@@ -293,7 +292,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 é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}
   Soit $f: \Bool^{n} \rightarrow \Bool^{n}$, $\textsc{giu}(f)$ son 
 
 \begin{theorem}
   Soit $f: \Bool^{n} \rightarrow \Bool^{n}$, $\textsc{giu}(f)$ son 


@@ -311,7 +310,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)$, 
 
 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
 
 La figure~\ref{fig:listfonction} explicite ces 16 fonctions en 
 définissant les images des éléments de la liste


@@ -332,15 +331,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
 -- 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}
 \}
 \}. 
 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}
 
 \begin{figure}%[h]
   \begin{center}


@@ -426,8 +431,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 
 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.
 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 +443,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 
 \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}}
 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 +460,7 @@ Dans l'algorithme~\ref{CI Algorithm},
 $\mathsf{p}$ vaut 1 et  $p_1=b$. 
 
 
 $\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
 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 +484,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$).
 
 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}} \\
 $$\begin{array}{cccc}
 \Sigma:&\mathds{S}_{\mathsf{N},\mathcal{P}} &\longrightarrow
 &\mathds{S}_{\mathsf{N},\mathcal{P}} \\


@@ -487,7 +492,7 @@ $$\begin{array}{cccc}
 \end{array}
 $$
 En d'autres termes, $\Sigma$ reçoit deux suites $u$ et $v$ et 
 \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.
 
 
 sur la seconde.
 
 


@@ -528,7 +533,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.
 
 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}
 $p = \lfloor \log_{10}{(\max{\mathcal{P}})}\rfloor +1$ et 
 $n = \lfloor \log_{10}{(\mathsf{N})}\rfloor +1$.
 \begin{itemize}


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


@@ -649,7 +654,7 @@ $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 
 \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:
+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 
 \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 


@@ -670,7 +675,7 @@ Il n'est pas difficile de constater que $\textsc{giu}_{\{1\}}(f)$ est $\textsc{g
     \subfigure[$\textsc{giu}_{\{2\}}(h)$]{
       \begin{minipage}{0.30\textwidth}
         \begin{center}
     \subfigure[$\textsc{giu}_{\{2\}}(h)$]{
       \begin{minipage}{0.30\textwidth}
         \begin{center}

-          \includegraphics[height=4cm]{images/h2prng.pdf}
+          \includegraphics[height=4cm]{images/h2prng}

         \end{center}
       \end{minipage}
       \label{fig:h2prng}
         \end{center}
       \end{minipage}
       \label{fig:h2prng}


@@ -678,7 +683,7 @@ Il n'est pas difficile de constater que $\textsc{giu}_{\{1\}}(f)$ est $\textsc{g
     \subfigure[$\textsc{giu}_{\{3\}}(h)$]{
       \begin{minipage}{0.40\textwidth}
         \begin{center}
     \subfigure[$\textsc{giu}_{\{3\}}(h)$]{
       \begin{minipage}{0.40\textwidth}
         \begin{center}

-          \includegraphics[height=4cm]{images/h3prng.pdf}
+          \includegraphics[height=4cm]{images/h3prng}

         \end{center}
       \end{minipage}
       \label{fig:h3prng}
         \end{center}
       \end{minipage}
       \label{fig:h3prng}


@@ -686,15 +691,15 @@ Il n'est pas difficile de constater que $\textsc{giu}_{\{1\}}(f)$ est $\textsc{g
     \subfigure[$\textsc{giu}_{\{2,3\}}(h)$]{
       \begin{minipage}{0.40\textwidth}
         \begin{center}
     \subfigure[$\textsc{giu}_{\{2,3\}}(h)$]{
       \begin{minipage}{0.40\textwidth}
         \begin{center}

-          \includegraphics[height=4cm]{images/h23prng.pdf}
+          \includegraphics[height=4cm]{images/h23prng}

         \end{center}
       \end{minipage}
       \label{fig:h23prng}
     }
 
     \end{center}
         \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}
+    \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}
 
 
   \end{figure}
 
 


@@ -708,7 +713,7 @@ $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}. 
 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) 
+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 
 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 


@@ -720,7 +725,7 @@ 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 à celui 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 à celui dans $\mathcal{X}_u$ et dans $\mathcal{X}_g$

-est prouvé en annexes~\ref{}.
+est prouvé en annexes~\ref{anx:generateur}.

 
 \begin{theorem}
 La fonction $G_{f_u,\mathcal{P}}$ est chaotique sur 
 
 \begin{theorem}
 La fonction $G_{f_u,\mathcal{P}}$ est chaotique sur 


@@ -728,6 +733,18 @@ La fonction $G_{f_u,\mathcal{P}}$ est chaotique sur
 graphe d'itération $\textsc{giu}_{\mathcal{P}}(f)$ 
 est fortement connexe.
 \end{theorem}
 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}