X-Git-Url: https://bilbo.iut-bm.univ-fcomte.fr/and/gitweb/hdrcouchot.git/blobdiff_plain/523864c862215a63c5133568a9771f5b8f60c89e..d33e664452e3655370cbe069e3f6fbd16842c818:/15RairoGen.tex diff --git a/15RairoGen.tex b/15RairoGen.tex index 432991f..a57e19f 100644 --- a/15RairoGen.tex +++ b/15RairoGen.tex @@ -59,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)$. @@ -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$ -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. @@ -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 -vecteur de probabilités +vecteurs de probabilités et les chaînes de Markov. @@ -140,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} @@ -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. -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 @@ -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 @@ -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$. -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})$. @@ -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}|$, -$\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. @@ -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 -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 @@ -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} @@ -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 -$\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} @@ -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$ -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 -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