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

diff --git a/15RairoGen.tex b/15RairoGen.tex
index 0519ecb..f2b9243 100644
--- a/15RairoGen.tex
+++ b/15RairoGen.tex
@@ -1 +1,461 @@
- 
\ No newline at end of file
+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}), 
+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}
+
+
+
+
+
+On peut penser Ã  construire un gÃ©nÃ©rateur de nombres pseudo 
+alÃ©atoires comme dans l'algorithme~\ref{CI Algorithm} donnÃ© ci-dessous.
+
+\begin{algorithm}[h]
+%\begin{scriptsize}
+\KwIn{une fonction $f$, un nombre d'itÃ©rations $b$, 
+une configuration initiale $x^0$ ($n$ bits)}
+\KwOut{une configuration $x$ ($n$ bits)}
+$x\leftarrow x^0$\;
+$k\leftarrow b + \textit{Random}(b+1)$\;
+%$k\leftarrow b + \textit{XORshift}(b+1)$\;
+\For{$i=0,\dots,k-1$}
+{
+$s\leftarrow{\textit{Random}(n)}$\;
+%$s\leftarrow{\textit{XORshift}(n)}$\;
+$x\leftarrow{F_f(s,x)}$\;
+}
+return $x$\;
+%\end{scriptsize}
+\caption{Algorithme de gÃ©nÃ©ration de nombres pseudo alÃ©atoires 
+Ã  l'aide de la fonction chaotique $G_f$}
+\label{CI Algorithm}
+\end{algorithm}
+
+
+Celui-ci prend en entrÃ©e: une fonction $f$;
+un entier $b$, qui assure que le nombre d'itÃ©rations
+est compris entre $b+1 $ et  $2b+1$ et une configuration initiale $x^0$.
+Il retourne une nouvelle configuration $x$.
+En interne, il exploite un algorithme de gÃ©nÃ©ration
+de nombres pseudo alÃ©atoires
+\textit{Random}$(l)$. 
+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 
+\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 {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 decalages 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{}).
+Une instance de cette classe est donnÃ©e dans l'algorithme~\ref{XORshift} donnÃ© 
+ci-dessous.
+
+\begin{algorithm}[h]
+%\SetLine
+\KwIn{la configuration interne $z$ (un mot de 32-bit)}
+\KwOut{$y$ (un mot de 32-bits)}
+$z\leftarrow{z\oplus{(z\ll13)}}$\;
+$z\leftarrow{z\oplus{(z\gg17)}}$\;
+$z\leftarrow{z\oplus{(z\ll5)}}$\;
+$y\leftarrow{z}$\;
+return $y$\;
+\medskip
+\caption{Une boucle de l'algorithme de \textit{XORshift}}
+\label{XORshift}
+\end{algorithm}
+
+
+
+Il reste Ã  instancier une fonction $f$ dans 
+l'algorithme~\ref{CI Algorithm} 
+en adÃ©quation avec  l'approche dÃ©veloppÃ©e 
+en section~\ref{sec:sccg}.
+La section suivante montre comment l'uniformitÃ© de la distribution a
+contraint cette instanciation.
+
+\subsection{Un gÃ©nÃ©rateur Ã  sortie uniformÃ©ment distribuÃ©e}\label{sub:prng:unif}
+
+Une matrice stochastique est une matrice carrÃ©e
+dont tous les Ã©lÃ©ments sont positifs ou nuls et dont
+la somme de chaque ligne
+vaut 1. 
+Une matrice stochastique l'est doublement si la somme de chaque colonne est 1.
+Enfin, une matrice stochastique de taille $n \times n$ est rÃ©guliÃ¨re 
+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 
+vecteurDeProbabilite 
+et les chaineDeMarkov:
+
+
+ 
+\begin{Theo}\label{th}
+  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} 
+ 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$
+  converge vers $\pi$ lorsque $k$ tend vers l'infini.
+\end{Theo}
+
+
+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$
+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}
+vÃ©rifient les hypothÃ¨ses du thÃ©orÃ¨me~\ref{th:Adrien}. 
+Leurs graphes d'itÃ©rations
+sont donc fortement connexes, ce que l'on a pu dÃ©jÃ  vÃ©rifier aux figures
+\ref{fig:g:iter} et \ref{fig:h:iter}.
+\textit{A priori}, ces deux fonctions pourraient Ãªtre intÃ©grÃ©es
+dans un gÃ©nÃ©rateur de nombres pseudo alÃ©atoires. Montrons que ce n'est pas le cas pour $g$ et 
+que cela l'est pour $h$.
+
+
+Comme le gÃ©nÃ©rateur \textit{Random} possÃ¨de une sortie uniformÃ©ment 
+distribuÃ©e,  la  stratÃ©gie est uniforme sur $\llbracket 1, 2 \rrbracket$,
+et donc, 
+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 {matriceDeTransitions}
+d'un tel processus 
+est $M_g   = \frac{1}{2} \check{M}_g$, 
+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]
+  \begin{center}
+    \subfloat[$\check{M}_g $.]{
+      \begin{minipage}{0.25\textwidth}
+        \begin{center}
+          % \vspace{-3cm}
+          $\left( 
+            \begin{array}{cccc} 
+              1 & 0 & 1 & 0 \\ 
+              1 & 0 & 0 & 1 \\ 
+              1 & 0 & 0 & 1 \\ 
+              0 & 1 & 1 & 0 
+            \end{array}
+          \right)
+          $
+        \end{center}
+      \end{minipage}
+      \label{fig:g:incidence}
+    }
+    \subfloat[$\check{M}_h $.]{
+        \begin{minipage}{0.25\textwidth}
+          \begin{center}
+            $\left( 
+              \begin{array}{cccc} 
+                1 & 0 & 1 & 0 \\ 
+                0 & 1 & 0 & 1 \\ 
+                1 & 0 & 0 & 1 \\ 
+                0 & 1 & 1 & 0 
+              \end{array}
+            \right)
+            $
+          \end{center}
+        \end{minipage}
+        \label{fig:h:incidence}
+      }
+    \end{center}
+    \caption{Graphe des fonctions candidates avec $n=2$}
+    \label{fig:xplgraph}
+  \end{figure}
+
+Les deux matrices $M_g$ et $M_h$ sont  stochastiques. Pour
+montrer qu'elles sont rÃ©guliÃ¨res il suffit de constater qu'aucun Ã©lÃ©ment de 
+$M^5_g$ ni de  $M^3_h$ n'est nul.
+De plus, les vecteurs de probabilitÃ©s 
+$\pi_g=(\frac{4}{10}, \frac{1}{10},\frac{3}{10},\frac{2}{10})$ et
+$\pi_h=(\frac{1}{4},\frac{1}{4},\frac{1}{4},\frac{1}{4})$ 
+vÃ©rifient $\pi_g M_g = \pi_g$ et 
+$\pi_h M_h = \pi_h$. 
+Alors d'aprÃ¨s le thÃ©orÃ¨me~\ref{th}, 
+pour n'importe quel vecteur initial de probabilitÃ©s $\pi^0$, on a 
+$\lim_{k \to \infty} \pi^0 M^k_g = \pi_g$ et 
+$\lim_{k \to \infty} \pi^0 M^k_h = \pi_h$. 
+Ainsi la chaÃ®ne de Markov associÃ© Ã  $h$ tend vers une 
+distribution uniforme, contrairement Ã  celle associÃ©e Ã  $g$.
+On en dÃ©duit que $g$ ne devrait pas Ãªtre itÃ©rÃ©e dans 
+un gÃ©nÃ©rateur de nombres pseudo alÃ©atoires.
+Au contraire, 
+$h$ devrait pouvoir Ãªtre embarquÃ©e dans l'algorithme~\ref{CI Algorithm}, 
+pour peu que le nombre $b$ d'itÃ©rations entre deux mesures successives 
+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.
+
+
+ConsidÃ©rons le lemme technique suivant:
+\begin{Lemma}\label{lem:stoc}
+Soit $f: \Bool^{n} \rightarrow \Bool^{n}$, $\Gamma(f)$ son graphe d'itÃ©rations, $\check{M}$ la matrice d'adjacence de $\Gamma(f)$, et  $M$  la matrice 
+$2^n\times 2^n$  dÃ©finie par
+$M = \frac{1}{n}\check{M}$.
+Alors $M$ est une matrice stochastique rÃ©guliÃ¨re si et seulement si
+$\Gamma(f)$ est fortement connexe.
+\end{Lemma}
+
+\begin{Proof}  
+On remarque tout d'abord que $M$ 
+est une matrice stochastique par construction.
+Supposons $M$ rÃ©guliÃ¨re. 
+Il existe donc  $k$ tel que $M_{ij}^k>0$ pour chaque $i,j\in \llbracket
+1;  2^n  \rrbracket$. L'inÃ©galitÃ©  $\check{M}_{ij}^k>0$  est alors Ã©tablie.
+Puisque $\check{M}_{ij}^k$ est le nombre de chemins de  $i$ Ã  $j$ de longueur $k$
+dans $\Gamma(f)$ et puisque ce nombre est positif, alors 
+$\Gamma(f)$ est fortement connexe.
+
+RÃ©ciproquement si $\Gamma(f)$ 
+est fortement connexe, alors pour tous les sommets $i$ et $j$, un chemin peut Ãªtre construit pour atteindre  $j$  depuis $i$ en au plus $2^n$ Ã©tapes.
+Il existe donc 
+$k_{ij} \in \llbracket 1,  2^n \rrbracket$ tels que $\check{M}_{ij}^{k_{ij}}>0$.  
+Comme tous les  multiples $l \times k_{ij}$ de $k_{ij}$ sont tels que 
+$\check{M}_{ij}^{l\times  k_{ij}}>0$, 
+on peut conclure que, si 
+$k$ est le plus petit multiple commun de $\{k_{ij}  \big/ i,j  \in \llbracket 1,  2^n \rrbracket  \}$ alors
+$\forall i,j  \in \llbracket  1, 2^n \rrbracket,  \check{M}_{ij}^{k}>0$. 
+Ainsi, $\check{M}$ et donc $M$ sont rÃ©guliÃ¨res.
+\end{Proof}
+
+Ces rÃ©sultats permettent formuler et de prouver le thÃ©orÃ¨me suivant:
+
+\begin{Theo}
+  Soit $f: \Bool^{n} \rightarrow \Bool^{n}$, $\Gamma(f)$ son 
+  graphe d'itÃ©rations , $\check{M}$ sa matrice d'adjacence
+  et $M$ une matrice  $2^n\times 2^n$  dÃ©finie comme dans le lemme prÃ©cÃ©dent.
+  Si $\Gamma(f)$ est fortement connexe, alors 
+  la sortie du gÃ©nÃ©rateur de nombres pseudo alÃ©atoires dÃ©taillÃ© par 
+  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{Theo}
+\begin{Proof}
+  $M$ est une matrice stochastique rÃ©guliÃ¨re (Lemme~\ref{lem:stoc}) 
+  qui a un unique vecteur de probabilitÃ©s stationnaire
+  (ThÃ©orÃ¨me \ref{th}).
+  Soit $\pi$  dÃ©fini par 
+  $\pi = \left(\frac{1}{2^n}, \hdots, \frac{1}{2^n} \right)$.
+  On a  $\pi M = \pi$ si et seulement si
+  la somme des valeurs de chaque colonne de $M$  est 1, 
+  \textit{i.e.} si et seulement si 
+  $M$ est  doublement  stochastique.
+\end{Proof}
+
+
+\subsection{ExpÃ©rimentations}
+
+On considÃ¨re le graphe d'interactions $G(f)$ donnÃ© en figure~\ref{fig:G}. 
+Il vÃ©rifie le thÃ©orÃ¨me~\ref{th:Adrien}: 
+toutes les fonctions $f$ possÃ©dant un tel graphe d'interactions
+ont un graphe d'itÃ©rations  $\Gamma(f)$ fortement connexe.
+Pratiquement, un algorithme simple de satisfaction de contraintes
+a trouvÃ©  520 fonctions $f$ non isomorphes de graphe d'interactions  $G(f)$, 
+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
+0, 1, 2,\ldots, 14, 15 en respectant  l'ordre.
+Expliquons enfin comment a Ã©tÃ© calculÃ© le nombre de la troisiÃ¨me 
+colonne utilisÃ© comme le paramÃ¨tre $b$ 
+dans l'algorithme~\ref{CI Algorithm}.
+
+Soit $e_i$ le $i^{\textrm{Ã¨me}}$ vecteur la base canonique de $\R^{2^{n}}$. 
+Chacun des Ã©lÃ©ments $v_j$, $1 \le j \le 2^n$, 
+du vecteur $e_i M_f^t$ reprÃ©sente la probabilitÃ© 
+d'Ãªtre dans la configuration $j$ aprÃ¨s $t$ Ã©tapes du processus de Markov 
+associÃ© Ã  $\Gamma(f)$ en partant de la configuration $i$.   
+Le nombre $\min \{
+ t \mid t \in \Nats, \vectornorm{e_i M_f^t - \pi} < 10^{-4}
+\}$ reprÃ©sente le plus petit nombre d'itÃ©rations oÃ¹ la distance de 
+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
+ $b$. Ainsi, on a 
+$$
+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}
+\}
+\}. 
+$$
+
+\begin{figure}%[h]
+  \begin{center}
+  \subfloat[Graphe d'interactions]{
+    \begin{minipage}{0.20\textwidth}
+      \begin{center}
+        \includegraphics[width=3.5cm]{images/Gi.pdf}
+      \end{center}
+    \end{minipage}
+    \label{fig:G}
+  }\hfill
+  \subfloat[Fonctions doublement stochastiques]{
+    \begin{minipage}{0.75\textwidth}
+      \begin{scriptsize}
+        \begin{center}
+          \begin{tabular}{|c|c|c|}
+\hline
+{Nom}& {DÃ©finition}&{$b$} \\
+\hline 
+$\mathcal{F}_1$ & 14, 15, 12, 13, 10, 11, 8, 9, 6, 7, 4, 5, 2, 3, 1, 0  & 206\\
+\hline
+$\mathcal{F}_2$ &14, 15, 12, 13, 10, 11, 8, 9, 6, 7, 5, 4, 3, 2, 0, 1  
+ & 94 \\
+\hline
+$\mathcal{F}_3$ &14, 15, 12, 13, 10, 11, 8, 9, 6, 7, 5, 4, 3, 2, 1, 0
+ & 69 \\
+\hline
+$\mathcal{F}_4$ &14, 15, 12, 13, 10, 11, 9, 8, 6, 7, 5, 4, 3, 2, 0, 1
+ & 56 \\
+\hline
+$\mathcal{F}_5$ &14, 15, 12, 13, 10, 11, 9, 8, 6, 7, 5, 4, 3, 2, 1, 0
+ & 48 \\
+\hline
+$\mathcal{F}_6$ &14, 15, 12, 13, 10, 11, 9, 8, 7, 6, 4, 5, 2, 3, 0, 1
+ & 86 \\
+\hline
+$\mathcal{F}_7$ &14, 15, 12, 13, 10, 11, 9, 8, 7, 6, 4, 5, 2, 3, 1, 0
+ & 58 \\
+\hline
+$\mathcal{F}_8$ &14, 15, 12, 13, 10, 11, 9, 8, 7, 6, 4, 5, 3, 2, 1, 0
+ & 46 \\
+\hline
+$\mathcal{F}_9$ &14, 15, 12, 13, 10, 11, 9, 8, 7, 6, 5, 4, 3, 2, 0, 1
+ & 42 \\
+\hline
+$\mathcal{F}_{10}$ &14, 15, 12, 13, 10, 11, 9, 8, 7, 6, 5, 4, 3, 2, 1, 0
+ & 69 \\
+\hline
+$\mathcal{F}_{11}$ &14, 15, 12, 13, 11, 10, 9, 8, 7, 6, 5, 4, 2, 3, 1, 0
+ & 58 \\
+\hline
+$\mathcal{F}_{12}$ &14, 15, 13, 12, 11, 10, 8, 9, 7, 6, 4, 5, 2, 3, 1, 0
+ & 35 \\
+\hline
+$\mathcal{F}_{13}$ &14, 15, 13, 12, 11, 10, 8, 9, 7, 6, 4, 5, 3, 2, 1, 0
+ & 56 \\
+\hline
+$\mathcal{F}_{14}$ &14, 15, 13, 12, 11, 10, 8, 9, 7, 6, 5, 4, 3, 2, 1, 0
+ & 94 \\
+\hline
+$\mathcal{F}_{15}$ &14, 15, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 0, 1
+ & 86 \\ 
+\hline
+$\mathcal{F}_{16}$ &14, 15, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 0
+  & 206 \\
+ \hline
+\end{tabular}
+\end{center}
+\end{scriptsize}
+\end{minipage}
+\label{fig:listfonction}
+}
+\end{center}
+\caption{Candidates pour le gÃ©nÃ©rateur  avec $n=4$}
+ \end{figure}
+
+
+La qualitÃ© des sÃ©quences alÃ©atoires a Ã©tÃ© Ã©valuÃ©e Ã  travers la suite 
+de tests statistiques dÃ©veloppÃ©e pour les gÃ©nÃ©rateurs de nombres 
+pseudo alÃ©atoires par le 
+\emph{National Institute of Standards and Technology} (NIST).
+% Pour les 15 tests, le seuil $\alpha$ est fixÃ© Ã  $1\%$:
+% une  valeur  
+% qui est plus grande que $1\%$  signifie 
+% que la chaÃ®ne est considÃ©rÃ©e comme alÃ©atoire avec une confiance de $99\%$.
+% Le tableau~\ref{fig:TEST} donne une vision synthÃ©tique de toutes 
+% les expÃ©rimentations. 
+L'expÃ©rience a montrÃ© notamment que toutes ces fonctions
+passent avec succÃ¨s cette batterie de tests.
+
+
+
+
+% \begin{table}[th]
+% \begin{scriptsize}
+% \begin{tabular}{|*{17}{c|}}
+% \hline
+% {PropriÃ©tÃ©}& $\mathcal{F}_{1}$ &$\mathcal{F}_{2}$ &$\mathcal{F}_{3}$ &$\mathcal{F}_{4}$ &$\mathcal{F}_{5}$ &$\mathcal{F}_{6}$ &$\mathcal{F}_{7}$ &$\mathcal{F}_{8}$ &$\mathcal{F}_{9}$ &$\mathcal{F}_{10}$ &$\mathcal{F}_{11}$ &$\mathcal{F}_{12}$ &$\mathcal{F}_{13}$ &$\mathcal{F}_{14}$ &$\mathcal{F}_{15}$ &$\mathcal{F}_{16}$ \\
+% \hline
+% FrÃ©quence &77.9 &15.4 &83.4 &59.6 &16.3 &38.4 &20.2 &29.0 &77.9 &21.3 &65.8 &85.1 &51.4 &35.0 &77.9 &92.4 \\ 
+%  \hline 
+% FrÃ©quence / bloc &88.3 &36.7 &43.7 &81.7 &79.8 &5.9 &19.2 &2.7 &98.8 &1.0 &21.3 &63.7 &1.4 &7.6 &99.1 &33.5 \\ 
+%  \hline 
+% Somme cummulÃ©e &76.4 &86.6 &8.7 &66.7 &2.2 &52.6 &20.8 &80.4 &9.8 &54.0 &73.6 &80.1 &60.7 &79.7 &76.0 &44.7 \\ 
+%  \hline 
+% ExÃ©cution &5.2 &41.9 &59.6 &89.8 &23.7 &76.0 &77.9 &79.8 &45.6 &59.6 &89.8 &2.4 &96.4 &10.9 &72.0 &11.5 \\ 
+%  \hline 
+% Longue exÃ©cution &21.3 &93.6 &69.9 &23.7 &33.5 &30.4 &41.9 &43.7 &30.4 &17.2 &41.9 &51.4 &59.6 &65.8 &11.5 &61.6 \\ 
+%  \hline 
+% Rang &1.0 &41.9 &35.0 &45.6 &51.4 &20.2 &31.9 &83.4 &89.8 &38.4 &61.6 &4.0 &21.3 &69.9 &47.5 &95.6 \\ 
+%  \hline 
+% Fourrier Rapide &40.1 &92.4 &97.8 &86.8 &43.7 &38.4 &76.0 &57.5 &36.7 &35.0 &55.4 &57.5 &86.8 &76.0 &31.9 &7.6 \\ 
+%  \hline 
+% Sans superposition &49.0 &45.7 &50.5 &51.0 &48.8 &51.2 &51.6 &50.9 &50.9 &48.8 &45.5 &47.3 &47.0 &49.2 &48.6 &46.4 \\ 
+%  \hline 
+% Avec Superposition &27.6 &10.9 &53.4 &61.6 &16.3 &2.7 &59.6 &94.6 &88.3 &55.4 &76.0 &23.7 &47.5 &91.1 &65.8 &81.7 \\ 
+%  \hline 
+% Universelle &24.9 &35.0 &72.0 &51.4 &20.2 &74.0 &40.1 &23.7 &9.1 &72.0 &4.9 &13.7 &14.5 &1.8 &93.6 &65.8 \\ 
+%  \hline 
+% Entropie approchÃ©e &33.5 &57.5 &65.8 &53.4 &26.2 &98.3 &53.4 &63.7 &38.4 &6.7 &53.4 &19.2 &20.2 &27.6 &67.9 &88.3 \\ 
+%  \hline 
+% Suite alÃ©atoire &29.8 &35.7 &40.9 &36.3 &54.8 &50.8 &43.5 &46.0 &39.1 &40.8 &29.6 &42.0 &34.8 &33.8 &63.0 &46.3 \\ 
+%  \hline 
+% Suite alÃ©atoire variante &32.2 &40.2 &23.0 &39.6 &47.5 &37.2 &56.9 &54.6 &53.3 &31.5 &23.0 &38.1 &52.3 &57.1 &47.7 &40.8 \\ 
+%  \hline 
+% SÃ©rie &56.9 &58.5 &70.4 &73.2 &31.3 &45.9 &60.8 &39.9 &57.7 &21.2 &6.4 &15.6 &44.7 &31.4 &71.7 &49.1 \\ 
+%  \hline 
+% ComplexitÃ© linÃ©aire &24.9 &23.7 &96.4 &61.6 &83.4 &49.4 &49.4 &18.2 &3.5 &76.0 &24.9 &97.2 &38.4 &38.4 &1.1 &8.6 \\ 
+%  \hline
+% \end{tabular}
+% \end{scriptsize}
+% \caption{Test de NIST rÃ©alisÃ© sur des instances de gÃ©nÃ©rateurs}\label{fig:TEST}  
+% \end{table}
+
+
+
