X-Git-Url: https://bilbo.iut-bm.univ-fcomte.fr/and/gitweb/hdrcouchot.git/blobdiff_plain/d3ea167453c701385858e4db6c3dcd9df216701d..7b2f06062fc54db047de438cda35671608a1dc89:/15RairoGen.tex

diff --git a/15RairoGen.tex b/15RairoGen.tex
index 3c49eb6..f2b9243 100644
--- a/15RairoGen.tex
+++ b/15RairoGen.tex
@@ -1,99 +1,27 @@
-Pour dÃ©crire un peu plus prÃ©cisÃ©ment le principe de
-la gÃ©nÃ©ration pseudo-alÃ©atoire, considÃ©rons l'espace boolÃ©en 
-$\Bool=\{0,1\}$
-muni des lois \og +\fg{}, \og . \fg{} et \og $\overline{\mathstrut\enskip}$ \fg{} 
-dÃ©finies par les tableaux ci-dessous:
-
-\begin{minipage}{0.33\textwidth}
-  \begin{center}
-  \begin{tabular}{|c|c|c|}
-    \hline 
-    + & 0& 1 \\
-    \hline 
-    0 & 0& 1 \\
-    \hline 
-    1 & 1& 1 \\
-    \hline
-  \end{tabular}
-\end{center}
-\end{minipage}
-\begin{minipage}{0.33\textwidth}
-  \begin{center}
-  \begin{tabular}{|c|c|c|}
-    \hline 
-    . & 0& 1 \\
-    \hline 
-    0 & 0& 0 \\
-    \hline 
-    1 & 0& 1 \\
-    \hline
-  \end{tabular}
-\end{center}
-\end{minipage}
-\begin{minipage}{0.32\textwidth}
-  \begin{center}
-  \begin{tabular}{|c|c|c|}
-    \hline 
-     & 0& 1 \\
-    \hline 
-    $\overline{\mathstrut\enskip}$ & 1& 0 \\
-    \hline 
-   \end{tabular}
-\end{center}
-\end{minipage}
-
-
-La fonction itÃ©rÃ©e est
-une fonction $f$ de $\Bool^n$ dans lui-mÃªme qui Ã 
-un mot binaire $x = (x_1,\ldots,x_n)$ 
-associe le mot $(f_1(x),\ldots, f_n(x))$.
-Un exemple de fonction de $\Bool^n$ dans lui-mÃªme
-est la fonction nÃ©gation 
-dÃ©finie par  
-$\neg(x)=(\overline{x_1},\dots,\overline{x_n})$. 
-
-Le principe itÃ©ratif est le suivant: 
-Ã  chaque itÃ©ration $t$, on choisit un indice $i$ entre $1$ et $n$,
-et le mot $x^t = (x_1^t,\ldots,x_n^t)$ est remplacÃ© par
-$x^{t+1} = (x_1^t,\ldots , x_{i-1}^t, f_i(x^t), x_{i+1}^t,\ldots, x_n^t)$.
-
-Au bout d'un nombre $N$ d'itÃ©rations,
-si la fonction, notÃ©e $G_f$ dans ce document, 
-que l'on peut associer Ã  l'algorithme dÃ©crit ci-dessus
+Au bout d'un nombre $b$ d'itÃ©rations,
+si la fonction, notÃ©e $G_{f_u}$ (ou bien $G_{f_g}$) 
+prÃ©sentÃ©e au chapitre~\ref{chap:carachaos}, 
 a de \og bonnes\fg{} propriÃ©tÃ©s chaotiques, 
-le mot $x^N$ doit Ãªtre \og trÃ¨s diffÃ©rent\fg{} de $x^0$ 
-de faÃ§on Ã  mÃªme sembler ne plus dÃ©pendre de $x_0$:
-pour un gÃ©nÃ©rateur alÃ©atoire, il faut que la structure de 
-$x^N$ semble Ãªtre due au hasard; 
-pour une application cryptographique, il faut qu'il
-soit matÃ©riellement impossible (dans les conditions techniques actuelles) 
-de retrouver $x^0$ Ã  partir de $x^N$.
-
-Tous les mots de 
-$\Bool^n$ peuvent constituer les
-$2^n$ sommets d'un \gls{graphoriente} (cf. glossaire)
-dans lequel un arc relie deux sommets $x$ et $x'$ 
-s'il existe une itÃ©ration de l'algorithme
-de gÃ©nÃ©ration qui permet de passer de $x$ Ã  $x'$. 
-Ce graphe est appelÃ© le graphe d'itÃ©rations et 
-ce document montre que si l'on a un \gls{graphfortementconnexe} (cf. glossaire),
-alors la fonction $G_f$ est transitive, donc chaotique.
-
+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. 
 Enfin, un bon gÃ©nÃ©rateur alÃ©atoire se doit de 
-fournir  des nombres selon une \gls{distributionuniforme} (cf. glossaire). 
-La derniÃ¨re partie de ce document donnera, 
+fournir  des nombres selon une {distributionuniforme} 
+La suite de ce document donnera, 
 dans le cas oÃ¹ le graphe d'itÃ©rations est fortement connexe, 
 une condition nÃ©cessaire est suffisante pour que
 cette propriÃ©tÃ© soit satisfaite.
 
 
- Cette section prÃ©sente une application directe de la thÃ©orie dÃ©veloppÃ©e ci-avant
-Ã  la gÃ©nÃ©ration de nombres pseudo alÃ©atoires. On prÃ©sente tout d'abord le gÃ©nÃ©rateur
+Cette section prÃ©sente une application directe de la thÃ©orie dÃ©veloppÃ©e ci-avant
+Ã  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 \gls{distributionuniforme} 
-(cf. glossaire) de la sortie 
+puis comment intÃ©grer la contrainte de distributionuniforme
+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}
  
 
 \subsection{ GÃ©nÃ©rateur de nombres pseudo alÃ©atoires basÃ© sur le chaos}\label{sub:prng:algo}
@@ -137,20 +65,20 @@ 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$ 
-selon une \gls{distributionuniforme} (cf. glossaire) et utilise 
+selon une distributionuniforme et utilise 
 \textit{XORshift} qui est une classe de gÃ©nÃ©rateurs de
 nombres pseudo alÃ©atoires
 trÃ¨s rapides conÃ§us par George Marsaglia. 
 
 % L'algorithme \textit{XORshift} exploite itÃ©rativement
-% la fonction \og \gls{xor}\fg{} $\oplus$ (cf. glossaire) 
-% sur des nombres obtenus grÃ¢ce Ã  des \glspl{decalageDeBits} (cf. glossaire).
+% la fonction \og {xor}\fg{} $\oplus$ (cf. glossaire) 
+% sur des nombres obtenus grÃ¢ce Ã  des pl{decalageDeBits} (cf. glossaire).
 
 L'algorithme \textit{XORshift} 
 exploite itÃ©rativement l'opÃ©rateur $\oplus$  
-sur des nombres obtenus grÃ¢ce Ã  des \glspl{decalageDeBits} (cf. glossaire).
+sur des nombres obtenus grÃ¢ce Ã  des decalages de bits.
 Cet opÃ©rateur, dÃ©fini dans $\Bool^{n}$, 
-applique la fonction \og  \gls{xor} \fg{} (cf. glossaire) 
+applique la fonction \og  xor \fg{} 
 aux bits de mÃªme rang de ses deux opÃ©randes (\og opÃ©ration bit Ã  bit \fg{}).
 Une instance de cette classe est donnÃ©e dans l'algorithme~\ref{XORshift} donnÃ© 
 ci-dessous.
@@ -190,8 +118,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 
-\glspl{vecteurDeProbabilite} (cf. glossaire) 
-et les \glspl{chaineDeMarkov} (cf. glossaire):
+vecteurDeProbabilite 
+et les chaineDeMarkov:
 
 
  
@@ -199,11 +127,11 @@ et les \glspl{chaineDeMarkov} (cf. glossaire):
   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 \gls{vecteurDeProbabilite} 
+  De plus, si $\pi^0$ est un {vecteurDeProbabilite} 
  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 \gls{chaineDeMarkov} $\pi^k$
+  alors la {chaineDeMarkov} $\pi^k$
   converge vers $\pi$ lorsque $k$ tend vers l'infini.
 \end{Theo}
 
@@ -231,10 +159,10 @@ pour tout sommet de $\Gamma(g)$ et de  $\Gamma(h)$,
 chaque arc sortant de ce sommet a, parmi l'ensemble des arcs sortant 
 de ce sommet, une probabilitÃ© $1/2$ dâÃªtre celui qui sera traversÃ©.
 En d'autres mots, $\Gamma(g)$ est le graphe orientÃ© d'une chaÃ®ne de Markov.
-Il est facile de vÃ©rifier que la \gls{matriceDeTransitions} (cf. glossaire)
+Il est facile de vÃ©rifier que la {matriceDeTransitions}
 d'un tel processus 
 est $M_g   = \frac{1}{2} \check{M}_g$, 
-oÃ¹ $\check{M}_g$ est la \gls{matriceDAdjacence} (cf. glossaire) donnÃ©e en 
+oÃ¹ $\check{M}_g$ est la {matriceDAdjacence}  donnÃ©e en 
 figure~\ref{fig:g:incidence} (voir ci-aprÃ¨s), et similairement pour $M_h$. 
 
 \begin{figure}[h]
