ajout d'intro et de conclusion

[hdrcouchot.git] / 15RairoGen.tex

diff --git a/15RairoGen.tex b/15RairoGen.tex
index 06f84b1889cafed48dad42d9b8049dbfd0981dfb..432991fb638780d70496df8040141d53282eeb99 100644 (file)
--- 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. 
 
 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. 
 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}
 
 
 \section{ Nombres pseudo aléatoires construits par itérations unaires}\label{sub:prng:algo}
 
 


@@ -304,7 +296,7 @@ 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 annexes~\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$  
   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.
   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}
 
 
 \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.
 
 
 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 
 
 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 


@@ -661,9 +653,11 @@ 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 annexes~\ref{anx:generateur}.

-\begin{lemma}
+
+
+\begin{restatable}[Une distance dans $\mathcal{X}_{\mathsf{N},\mathcal{P}}$]{theorem}{distancedsxnp}

 $d$ est une distance sur $\mathcal{X}_{\mathsf{N},\mathcal{P}}$.
 $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)$}
 
 
 \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 
 \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)$.
 $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)$.


@@ -743,24 +737,33 @@ Le dernier donnerait le comportement d'un générateur qui s'autoriserait
 Le théorème suivant, similaire à ceux dans $\mathcal{X}_u$ et dans $\mathcal{X}_g$
 est prouvé en annexes~\ref{anx:generateur}.
 
 Le théorème suivant, similaire à ceux dans $\mathcal{X}_u$ et dans $\mathcal{X}_g$
 est prouvé en annexes~\ref{anx:generateur}.
 

-\begin{theorem}
+\begin{restatable}[Conditions pour la choticité 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 

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

 est fortement connexe.
 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.

 
 

+ 
+