15

[hdrcouchot.git] / 15RairoGen.tex

diff --git a/15RairoGen.tex b/15RairoGen.tex
index 835555e30d8a824611831230b94a2518bb3ea7f0..f2b9243846240ff1a26753e288cc6e53264479e5 100644 (file)
--- a/15RairoGen.tex
+++ b/15RairoGen.tex
@@ -1,10 +1,27 @@
- 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
+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^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 {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

 basé sur des fonctions chaotiques (section~\ref{sub:prng:algo}), 
 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.
 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}
  
 
 \subsection{ Générateur de nombres pseudo aléatoires basé sur le chaos}\label{sub:prng:algo}


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


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

 
 
  
 
 
  


@@ -110,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$).
   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$ 
  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}
 
   converge vers $\pi$ lorsque $k$ tend vers l'infini.
 \end{Theo}
 


@@ -142,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.
 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$, 
 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]
 figure~\ref{fig:g:incidence} (voir ci-après), et similairement pour $M_h$. 
 
 \begin{figure}[h]