]> AND Private Git Repository - hdrcouchot.git/commitdiff
Logo AND Algorithmique Numérique Distribuée

Private GIT Repository
modif 15Rairo
authorcouchot <jf.couchot@gmail.com>
Wed, 15 Jul 2015 11:37:10 +0000 (13:37 +0200)
committercouchot <jf.couchot@gmail.com>
Wed, 15 Jul 2015 11:37:10 +0000 (13:37 +0200)
15RairoGen.tex

index 0519ecba6ea913e21689ec692e81e9e4973fbf73..835555e30d8a824611831230b94a2518bb3ea7f0 100644 (file)
@@ -1 +1,444 @@
\ No newline at end of file
+ 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 
+dans le choix de la fonction à itérer (section~\ref{sub:prng:unif}). 
+L'approche est évaluée dans la dernière section.
+
+\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 \gls{distributionuniforme} (cf. glossaire) 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).
+
+L'algorithme \textit{XORshift} 
+exploite itérativement l'opérateur $\oplus$  
+sur des nombres obtenus grâce à des \glspl{decalageDeBits} (cf. glossaire).
+Cet opérateur, défini dans $\Bool^{n}$, 
+applique la fonction \og  \gls{xor} \fg{} (cf. glossaire) 
+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 
+\glspl{vecteurDeProbabilite} (cf. glossaire) 
+et les \glspl{chaineDeMarkov} (cf. glossaire):
+
+
+\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 \gls{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$
+  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 \gls{matriceDeTransitions} (cf. glossaire)
+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 
+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}
+
+
+