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

Private GIT Repository
r
authorcouchot <jf.couchot@gmail.com>
Mon, 20 Jul 2015 12:44:39 +0000 (14:44 +0200)
committercouchot <jf.couchot@gmail.com>
Mon, 20 Jul 2015 12:44:39 +0000 (14:44 +0200)
15RairoGen.tex
annexePreuveDistribution.tex
images/texput.log
main.tex

index 4c9a25b340f43c7876454cf8b8411547c3595121..d71c0d3acc5091a5815dc5736d5968ea9ac8d7d9 100644 (file)
@@ -670,7 +670,7 @@ Il n'est pas difficile de constater que $\textsc{giu}_{\{1\}}(f)$ est $\textsc{g
     \subfigure[$\textsc{giu}_{\{2\}}(h)$]{
       \begin{minipage}{0.30\textwidth}
         \begin{center}
     \subfigure[$\textsc{giu}_{\{2\}}(h)$]{
       \begin{minipage}{0.30\textwidth}
         \begin{center}
-          \includegraphics[height=4cm]{images/h2prng.pdf}
+          \includegraphics[height=4cm]{images/h2prng}
         \end{center}
       \end{minipage}
       \label{fig:h2prng}
         \end{center}
       \end{minipage}
       \label{fig:h2prng}
@@ -678,7 +678,7 @@ Il n'est pas difficile de constater que $\textsc{giu}_{\{1\}}(f)$ est $\textsc{g
     \subfigure[$\textsc{giu}_{\{3\}}(h)$]{
       \begin{minipage}{0.40\textwidth}
         \begin{center}
     \subfigure[$\textsc{giu}_{\{3\}}(h)$]{
       \begin{minipage}{0.40\textwidth}
         \begin{center}
-          \includegraphics[height=4cm]{images/h3prng.pdf}
+          \includegraphics[height=4cm]{images/h3prng}
         \end{center}
       \end{minipage}
       \label{fig:h3prng}
         \end{center}
       \end{minipage}
       \label{fig:h3prng}
@@ -686,7 +686,7 @@ Il n'est pas difficile de constater que $\textsc{giu}_{\{1\}}(f)$ est $\textsc{g
     \subfigure[$\textsc{giu}_{\{2,3\}}(h)$]{
       \begin{minipage}{0.40\textwidth}
         \begin{center}
     \subfigure[$\textsc{giu}_{\{2,3\}}(h)$]{
       \begin{minipage}{0.40\textwidth}
         \begin{center}
-          \includegraphics[height=4cm]{images/h23prng.pdf}
+          \includegraphics[height=4cm]{images/h23prng}
         \end{center}
       \end{minipage}
       \label{fig:h23prng}
         \end{center}
       \end{minipage}
       \label{fig:h23prng}
@@ -720,7 +720,7 @@ 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 à celui dans $\mathcal{X}_u$ et dans $\mathcal{X}_g$
 \subsection{le PRNG de l'algorithme~\ref{CI Algorithm} est chaotique sur $\mathcal{X}_{\mathsf{N},\mathcal{P}}$}
 
 Le théorème suivant, similaire à celui dans $\mathcal{X}_u$ et dans $\mathcal{X}_g$
-est prouvé en annexes~\ref{}.
+est prouvé en annexes~\ref{anx:generateur}.
 
 \begin{theorem}
 La fonction $G_{f_u,\mathcal{P}}$ est chaotique sur 
 
 \begin{theorem}
 La fonction $G_{f_u,\mathcal{P}}$ est chaotique sur 
@@ -728,6 +728,18 @@ La fonction $G_{f_u,\mathcal{P}}$ est chaotique sur
 graphe d'itération $\textsc{giu}_{\mathcal{P}}(f)$ 
 est fortement connexe.
 \end{theorem}
 graphe d'itération $\textsc{giu}_{\mathcal{P}}(f)$ 
 est fortement connexe.
 \end{theorem}
-
+On alors corollaire suivant 
+
+\begin{corollary}
+  Le générateur de nombre pseudo aléatoire détaillé 
+  à l'algorithme~\ref{CI Algorithm}
+  n'est pas chaotique 
+  sur $(\mathcal{X}_{\mathsf{N},\{b\}},d)$ pour la fonction négation.
+\end{corollary}
+\begin{proof}
+  Dans cet algorithme, $\mathcal{P}$ est le singleton $\{b\}$.
+  Que $b$ soit pair ou impair,  $\textsc{giu}_{\mathcal{b}}(f)$
+  n'est pas fortement connexe.
+\end{proof}
 
 
 
 
index 878b3170f013948a58ac33e53d1e43e2568b32ce..f53e3b9f7d3f277ff2224884968a6abbfec21280 100644 (file)
@@ -88,94 +88,99 @@ aussi.
 
 
 
 
 
 
-\begin{theorem}
-La fonction $G_{f_u,\mathcal{P}}$ est chaotique sur 
- $(\mathcal{X}_{\mathsf{N},\mathcal{P}},d)$ si et seulement si 
-graphe d'itération $\textsc{giu}_{\mathcal{P}}(f)$ 
-est fortement connexe.
-\end{theorem}
+Montrons que: 
+\begin{lemma}
+Le graphe d'itération $\textsc{giu}_{\mathcal{P}}(f)$ 
+est fortement connexe si et seulement si 
+la fonction $G_{f_u,\mathcal{P}}$ est topologiquement transitive sur
+$(\mathcal{X}_{\mathsf{N},\mathcal{P}},d)$. 
+\end{lemma}\label{prop:trans}
 
 \begin{proof}
 
 \begin{proof}
-Suppose that $\Gamma_{\mathcal{P}}(f)$ is strongly connected. 
-Let $x=(e,(u,v)),\check{x}=(\check{e},(\check{u},\check{v})) 
-\in \mathcal{X}_{\mathsf{N},\mathcal{P}}$ and $\varepsilon >0$.
-We will find a point $y$ in the open ball $\mathcal{B}(x,\varepsilon )$ and
-$n_0 \in \mathds{N}$ such that $G_f^{n_0}(y)=\check{x}$: this strong transitivity
-will imply the transitivity property.
-We can suppose that $\varepsilon <1$ without loss of generality. 
-
-Let us denote by $(E,(U,V))$  the elements of $y$. As
-$y$ must be in $\mathcal{B}(x,\varepsilon)$ and  $\varepsilon < 1$,
-$E$ must be equal to $e$. Let $k=\lfloor \log_{10} (\varepsilon) \rfloor +1$.
-$d_{\mathds{S}_{\mathsf{N},\mathcal{P}}}((u,v),(U,V))$ must be lower than
-$\varepsilon$, so the $k$ first digits of the fractional part of 
-$d_{\mathds{S}_{\mathsf{N},\mathcal{P}}}((u,v),(U,V))$ are null.
-Let $k_1$ the smallest integer such that, if $V^0=v^0$, ...,  $V^{k_1}=v^{k_1}$,
- $U^0=u^0$, ..., $U^{\sum_{l=0}^{k_1}V^l-1} = u^{\sum_{l=0}^{k_1}v^l-1}$.
-Then $d_{\mathds{S}_{\mathsf{N},\mathcal{P}}}((u,v),(U,V))<\varepsilon$.
-In other words, any $y$ of the form $(e,((u^0, ..., u^{\sum_{l=0}^{k_1}v^l-1}),
-(v^0, ..., v^{k_1}))$ is in $\mathcal{B}(x,\varepsilon)$.
-
-Let $y^0$ such a point and $z=G_f^{k_1}(y^0) = (e',(u',v'))$. $\Gamma_{\mathcal{P}}(f)$
-being strongly connected, there is a path between $e'$ and $\check{e}$. Denote
-by $a_0, \hdots, a_{k_2}$ the edges visited by this path. We denote by
-$V^{k_1}=|a_0|$ (number of terms in the finite sequence $a_1$),
-$V^{k_1+1}=|a_1|$, ..., $V^{k_1+k_2}=|a_{k_2}|$, and by 
+Supposons tout d'abord que  $G_{f_u,\mathcal{P}}$ fortement connexe.
+Soit $x=(e,(u,v)),\check{x}=(\check{e},(\check{u},\check{v})) 
+\in \mathcal{X}_{\mathsf{N},\mathcal{P}}$ et $\varepsilon >0$.
+On cherche un point $y$ dans une boule ouverte $\mathcal{B}(x,\varepsilon )$ 
+et un nombre 
+$n_0 \in \mathds{N}$ tels que $G_{f_u,\mathcal{P}}^{n_0}(y)=\check{x}$: 
+Cette transitivité forte entrainera la propriété de transitivité classique.
+On peut supposer que $\varepsilon <1$ sans perte de généralité.
+
+Soit $(E,(U,V))$ les éléments de  $y$. Comme 
+$y$ doit appartenir à $\mathcal{B}(x,\varepsilon)$ et  $\varepsilon < 1$,
+$E$ est égal à $e$. 
+Soit $k=\lfloor \log_{10} (\varepsilon) \rfloor +1$.
+La distance $d_{\mathds{S}_{\mathsf{N},\mathcal{P}}}((u,v),(U,V))$ est inférieure à 
+$\varepsilon$: les  $k$ premiers éléments de la partie décimale de 
+$d_{\mathds{S}_{\mathsf{N},\mathcal{P}}}((u,v),(U,V))$ sont nuls.
+Soit $k_1$ le plus petit entier tel que, si $V^0=v^0$, ...,  $V^{k_1}=v^{k_1}$,
+alors $U^0=u^0$, ..., $U^{\sum_{l=0}^{k_1}V^l-1} = u^{\sum_{l=0}^{k_1}v^l-1}$.
+Alors $d_{\mathds{S}_{\mathsf{N},\mathcal{P}}}((u,v),(U,V))<\varepsilon$.
+En d'autres mots, chaque $y$ de la forme $(e,((u^0, ..., u^{\sum_{l=0}^{k_1}v^l-1}),
+(v^0, ..., v^{k_1}))$ est dans $\mathcal{B}(x,\varepsilon)$.
+
+Soit $y^0$ un tel point et $z=G_{f_u,\mathcal{P}}^{k_1}(y^0) = (e',(u',v'))$. 
+$G_{f_u,\mathcal{P}}$ étant fortement connexe,
+il existe un chemin entre $e'$ et $\check{e}$. 
+Soit $a_0, \hdots, a_{k_2}$ les arêtes visitées le long de ce chemin. 
+On fixe $V^{k_1}=|a_0|$ 
+(le nombre de termes dans la séquence finie $a_1$),
+$V^{k_1+1}=|a_1|$, ..., $V^{k_1+k_2}=|a_{k_2}|$, et 
 $U^{k_1}=a_0^0$, $U^{k_1+1}=a_0^1$, ..., $U^{k_1+V_{k_1}-1}=a_0^{V_{k_1}-1}$,
 $U^{k_1}=a_0^0$, $U^{k_1+1}=a_0^1$, ..., $U^{k_1+V_{k_1}-1}=a_0^{V_{k_1}-1}$,
-$U^{k_1+V_{k_1}}=a_1^{0}$, $U^{k_1+V_{k_1}+1}=a_1^{1}$,...
+$U^{k_1+V_{k_1}}=a_1^{0}$, $U^{k_1+V_{k_1}+1}=a_1^{1}$,\ldots
 
 
-Let $y=(e,((u^0, ..., u^{\sum_{l=0}^{k_1}v^l-1}, a_0^0, ..., a_0^{|a_0|}, a_1^0, ..., a_1^{|a_1|},..., 
+Soit $y=(e,((u^0, ..., u^{\sum_{l=0}^{k_1}v^l-1}, a_0^0, ..., a_0^{|a_0|}, a_1^0, ..., a_1^{|a_1|},..., 
  a_{k_2}^0, ..., a_{k_2}^{|a_{k_2}|},$ \linebreak
  $\check{u}^0, \check{u}^1, ...),(v^0, ..., v^{k_1},|a_0|, ...,
  a_{k_2}^0, ..., a_{k_2}^{|a_{k_2}|},$ \linebreak
  $\check{u}^0, \check{u}^1, ...),(v^0, ..., v^{k_1},|a_0|, ...,
- |a_{k_2}|,\check{v}^0, \check{v}^1, ...)))$. So $y\in \mathcal{B}(x,\varepsilon)$
- and $G_{f}^{k_1+k_2}(y)=\check{x}$.
+ |a_{k_2}|,\check{v}^0, \check{v}^1, ...)))$. 
+Ainsi
+ $y\in \mathcal{B}(x,\varepsilon)$
+ et $G_{f}^{k_1+k_2}(y)=\check{x}$.
  
  
-Conversely, if $\Gamma_{\mathcal{P}}(f)$ is not strongly connected, then there are 
-2 vertices $e_1$ and $e_2$ such that there is no path between $e_1$ and $e_2$.
-That is, it is impossible to find $(u,v)\in \mathds{S}_{\mathsf{N},\mathcal{P}}$
-and $n \mathds{N}$ such that $G_f^n(e,(u,v))_1=e_2$. The open ball $\mathcal{B}(e_2, 1/2)$
-cannot be reached from any neighborhood of $e_1$, and thus $G_f$ is not transitive.
+Réciproquement, si  $G_{f_u,\mathcal{P}}$ n'est pas fortement connexe,
+il y a donc deux n{\oe}uds 
+$e_1$ et $e_2$ sans chemins entre eux.
+Il n'est ainsi pas possible de trouver un couple $(u,v)\in \mathds{S}_{\mathsf{N},\mathcal{P}}$
+et $n \mathds{N}$ tel que  $G_{f_u,\mathcal{P}}^n(e,(u,v))_1=e_2$. 
+La boule ouverte  $\mathcal{B}(e_2, 1/2)$ ne peut ainsi pas être atteinte
+depuis n'importe quel voisins de $e_1$: 
+$G_{f_u,\mathcal{P}}$ n'est pas transitive.
 \end{proof}
 
 
 \end{proof}
 
 
-We show now that,
-\begin{prpstn}
-If $\Gamma_{\mathcal{P}}(f)$ is strongly connected, then $G_f$ is 
-regular on $(\mathcal{X}_{\mathsf{N},\mathcal{P}}, d)$.
-\end{prpstn}
+Montrons maintenant que 
+\begin{lemma}
+Si $G_{f_u,\mathcal{P}}$ est fortement connexe, alors $G_{f_u,\mathcal{P}}$ est  
+régulière sur  $(\mathcal{X}_{\mathsf{N},\mathcal{P}}, d)$.
+\end{lemma}
 
 \begin{proof}
 
 \begin{proof}
-Let $x=(e,(u,v)) \in \mathcal{X}_{\mathsf{N},\mathcal{P}}$ and $\varepsilon >0$. 
-As in the proofs of Prop.~\ref{prop:trans}, let $k_1 \in \mathds{N}$ such
-that 
+Soit $x=(e,(u,v)) \in \mathcal{X}_{\mathsf{N},\mathcal{P}}$ et $\varepsilon >0$. 
+Comme dans la preuve du lemme~\ref{prop:trans}, soit $k_1 \in \mathds{N}$ tel
+que 
 $$\left\{(e, ((u^0, ..., u^{v^{k_1-1}},U^0, U^1, ...),(v^0, ..., v^{k_1},V^0, V^1, ...)) \mid \right.$$
 $$\left.\forall i,j \in \mathds{N}, U^i \in \llbracket 1, \mathsf{N} \rrbracket, V^j \in \mathcal{P}\right\}
 \subset \mathcal{B}(x,\varepsilon),$$
 $$\left\{(e, ((u^0, ..., u^{v^{k_1-1}},U^0, U^1, ...),(v^0, ..., v^{k_1},V^0, V^1, ...)) \mid \right.$$
 $$\left.\forall i,j \in \mathds{N}, U^i \in \llbracket 1, \mathsf{N} \rrbracket, V^j \in \mathcal{P}\right\}
 \subset \mathcal{B}(x,\varepsilon),$$
-and $y=G_f^{k_1}(e,(u,v))$. $\Gamma_{\mathcal{P}}(f)$ being strongly connected,
-there is at least a path from the Boolean state $y_1$ of $y$ and $e$.
-Denote by $a_0, \hdots, a_{k_2}$ the edges of such a path.
-Then the point:
+et $y=G_{f_u,\mathcal{P}}^{k_1}(e,(u,v))$. 
+$G_{f_u,\mathcal{P}}$ étant fortement connexe,
+il existe au moins un chemin entre l'état booléen $y_1$ de $y$ et $e$.
+Nommons $a_0, \hdots, a_{k_2}$ les arêtes d'un tel chemin.
+Le point
 $$(e,((u^0, ..., u^{v^{k_1-1}},a_0^0, ..., a_0^{|a_0|}, a_1^0, ..., a_1^{|a_1|},..., 
  a_{k_2}^0, ..., a_{k_2}^{|a_{k_2}|},u^0, ..., u^{v^{k_1-1}},$$
 $$a_0^0, ...,a_{k_2}^{|a_{k_2}|}...),(v^0, ..., v^{k_1}, |a_0|, ..., |a_{k_2}|,v^0, ..., v^{k_1}, |a_0|, ..., |a_{k_2}|,...))$$
 $$(e,((u^0, ..., u^{v^{k_1-1}},a_0^0, ..., a_0^{|a_0|}, a_1^0, ..., a_1^{|a_1|},..., 
  a_{k_2}^0, ..., a_{k_2}^{|a_{k_2}|},u^0, ..., u^{v^{k_1-1}},$$
 $$a_0^0, ...,a_{k_2}^{|a_{k_2}|}...),(v^0, ..., v^{k_1}, |a_0|, ..., |a_{k_2}|,v^0, ..., v^{k_1}, |a_0|, ..., |a_{k_2}|,...))$$
-is a periodic point in the neighborhood $\mathcal{B}(x,\varepsilon)$ of $x$.
+est un point périodique dans le voisinage $\mathcal{B}(x,\varepsilon)$ de $x$.
 \end{proof}
 
 \end{proof}
 
-$G_f$ being topologically transitive and regular, we can thus conclude that
-\begin{thrm}
-The function $G_f$ is chaotic on $(\mathcal{X}_{\mathsf{N},\mathcal{P}},d)$ if
-and only if its iteration graph $\Gamma_{\mathcal{P}}(f)$ is strongly connected.
-\end{thrm}
+$G_{f_u,\mathcal{P}}$ étant topologiquement transitive and regulière, 
+on peut conclure le théorème:
+
+
+\begin{theorem}
+La fonction $G_{f_u,\mathcal{P}}$ est chaotique sur 
+ $(\mathcal{X}_{\mathsf{N},\mathcal{P}},d)$ si et seulement si 
+graphe d'itération $\textsc{giu}_{\mathcal{P}}(f)$ 
+est fortement connexe.
+\end{theorem}
+
 
 
-\begin{crllr}
-  The pseudorandom number generator $\chi_{\textit{14Secrypt}}$ is not chaotic
-  on $(\mathcal{X}_{\mathsf{N},\{b\}},d)$ for the negation function.
-\end{crllr}
-\begin{proof}
-  In this context, $\mathcal{P}$ is the singleton $\{b\}$.
-  If $b$ is even, any vertex $e$ of $\Gamma_{\{b\}}(f_0)$ cannot reach 
-  its neighborhood and thus $\Gamma_{\{b\}}(f_0)$ is not strongly connected. 
-  If $b$ is even, any vertex $e$ of $\Gamma_{\{b\}}(f_0)$ cannot reach itself 
-  and thus $\Gamma_{\{b\}}(f_0)$ is not strongly connected.
-\end{proof}
index dfb78d356596094ece230c369a9ee45491e7bcf9..9503c0cebbd387b4b3917c3213f43950f81860e3 100644 (file)
@@ -1,4 +1,4 @@
-This is pdfTeX, Version 3.1415926-2.5-1.40.14 (TeX Live 2013/Debian) (format=pdflatex 2014.4.22)  1 JUL 2014 08:43
+This is pdfTeX, Version 3.14159265-2.6-1.40.15 (TeX Live 2015/dev/Debian) (preloaded format=pdflatex 2015.4.24)  17 JUL 2015 16:13
 entering extended mode
  restricted \write18 enabled.
  %&-line parsing enabled.
 entering extended mode
  restricted \write18 enabled.
  %&-line parsing enabled.
@@ -11,10 +11,10 @@ End of file on the terminal!
 
  
 Here is how much of TeX's memory you used:
 
  
 Here is how much of TeX's memory you used:
- 3 strings out of 494999
- 105 string characters out of 6180228
- 46040 words of memory out of 5000000
- 3324 multiletter control sequences out of 15000+600000
+ 3 strings out of 494991
+ 113 string characters out of 6180055
+ 46069 words of memory out of 5000000
+ 3329 multiletter control sequences out of 15000+600000
  3640 words of font info for 14 fonts, out of 8000000 for 9000
  14 hyphenation exceptions out of 8191
  0i,0n,0p,1b,6s stack positions out of 5000i,500n,10000p,200000b,80000s
  3640 words of font info for 14 fonts, out of 8000000 for 9000
  14 hyphenation exceptions out of 8191
  0i,0n,0p,1b,6s stack positions out of 5000i,500n,10000p,200000b,80000s
index 9713260e28e93c4b290b67156c9f656f8c122c6d..8a06e6313825b8854c5c334d18da25931de7a27d 100644 (file)
--- a/main.tex
+++ b/main.tex
 
 \newtheorem{theorem}{Théorème}
 \newtheorem{lemma}{Lemme}
 
 \newtheorem{theorem}{Théorème}
 \newtheorem{lemma}{Lemme}
+\newtheorem{corollary}{Corollaire}
 \newtheorem*{xpl}{Exemple}
 \newtheorem*{Proof}{Preuve}
 \newtheorem{Def}{Définition}
 \newtheorem*{xpl}{Exemple}
 \newtheorem*{Proof}{Preuve}
 \newtheorem{Def}{Définition}
@@ -210,20 +211,25 @@ On montre qu'on a des résultats similaires.
 \chapter{Caractérisation des générateurs chaotiques}
 \input{15RairoGen}
 
 \chapter{Caractérisation des générateurs chaotiques}
 \input{15RairoGen}
 
-\chapter{Fonctions dont les graphes 
+\chapter{Engendrer une classe de générateurs}
+
+\section{Fonctions dont les graphes 
   $\textsc{giu}(f)$ 
   $\textsc{gig}(f)$ 
   sont fortement connexes}
 % Secrypt 14
   $\textsc{giu}(f)$ 
   $\textsc{gig}(f)$ 
   sont fortement connexes}
 % Secrypt 14
-% TSI 2015
 
 
-\chapter{Quantifier l'écart par rapport à la distribution uniforme} 
+
+\section{Quantifier l'écart par rapport à la distribution uniforme} 
 %15 Rairo
 
 
 
 \part{Conclusion et Perspectives}
 
 %15 Rairo
 
 
 
 \part{Conclusion et Perspectives}
 
+
+
+
 \JFC{Perspectives pour SDD->Promela}
 Among drawbacks of the method,  one can argue that bounded delays is only 
 realistic in practice for close systems. 
 \JFC{Perspectives pour SDD->Promela}
 Among drawbacks of the method,  one can argue that bounded delays is only 
 realistic in practice for close systems. 
@@ -249,9 +255,11 @@ will then be stated.
 Ajouter lefait que le codede gray n'est pas optimal.
 On pourrait aussi travailler à établir un classement qui préserverait 
 le fait que deux configurations voisines seraient représentées 
 Ajouter lefait que le codede gray n'est pas optimal.
 On pourrait aussi travailler à établir un classement qui préserverait 
 le fait que deux configurations voisines seraient représentées 
-par deux entiers voisins.
+par deux entiers voisins. Par optimisation? 
  
  
-
+\JFC{Perspectives pour les générateurs} : marcher ou sauter... comment on 
+pourrait étendre, ce que l'on a déjà, ce qu'il reste à faire.
+% TSI 2015