talk/prngunauretheorieok.tex

   1 \begin{itemize}
   2 \item Vers une fonction de
   3 $\mathcal{X}_u =\Bool^{\mathsf{N}} \times \llbracket1;{\mathsf{N}}\rrbracket^\Nats$
   4 dans lui même~\cite{ccgh16}:
   5 \begin{itemize}
   6 \item $F_{f_u}: \Bool^{\mathsf{N}} \times \llbracket1;{\mathsf{N}}\rrbracket \rightarrow \Bool^{\mathsf{N}}$,
   7 $(x,i) \mapsto (x_1,\dots,x_{i-1},f_i(x),x_{i+1},\dots,x_{\mathsf{N}})$
   8 \item $\sigma: \llbracket1;{\mathsf{N}}\rrbracket^\Nats \rightarrow \llbracket1;{\mathsf{N}}\rrbracket^\Nats$ t.q. $\forall t\in\Nats,\sigma(s)_t=s_{t+1}$
   9 \item $G_{{f_u},b}$ définie par
  10   $G_{{f_u},b}(x,s)=(F_{f_u}( \dots(F_{f_u}(x,s_0),\dots),s_{b-1}),\sigma^b(s))$
  11 \end{itemize}
  12
  13 \item Distance $d((x,s),(x',s'))= d_H(x,x')+d''_S(s,s')$
  14 \end{itemize}
  15
  16 \begin{theorem}[Fonctions t.q.  $G_{{f_u},b}$ est chaotique~\cite{ccgh16}]
  17 La fonction $G_{f_u,b}$ est chaotique sur
  18  $(\mathcal{X}_u,d)$ si et seulement si
  19 le graphe d'itérations $\textsc{giu}_{b}(f)$
  20 est fortement connexe.
  21 \end{theorem}
  22
  23
  24 \vspace{-4.5em}
  25 \begin{center}
  26 \begin{minipage}{0.30\textwidth}
  27   \begin{center}
  28     \includegraphics[scale=0.35]{../images/h2prng}
  29   \end{center}
  30 \end{minipage}
  31 \begin{minipage}{0.40\textwidth}
  32   \begin{center}
  33     \includegraphics[scale=0.35]{../images/h3prng}
  34   \end{center}
  35 \end{minipage}
  36 \end{center}
  37
  38
  39
  40 %  \begin{itemize}
  41 % \item Vers une fonction de
  42 %   $\mathcal{X}_u$ dans lui même:
  43 % \begin{itemize}
  44 % \item
  45 % $F_{{f_u},b} :  \mathds{B}^\mathsf{N} \times [\mathsf{N}]^{b}
  46 % \rightarrow \mathds{B}^\mathsf{N}$ définie par
  47 % $
  48 % F_{f_u,b} (x,(u^1, \hdots, u^{b})) =
  49 % F_{f_u}(\hdots (F_{f_u}(x,u^1), \hdots), u^{b}).
  50 % $
  51
  52
  53
  54 % \item $\sigma:
  55 %  \left(\mathcal{P}(\llbracket 1;{\mathsf{N}}\rrbracket)\right)^{\Nats}
  56 %  \rightarrow
  57 %  \left(\mathcal{P}(\llbracket 1;{\mathsf{N}}\rrbracket)\right)^{\Nats}$
  58 %  t.q. $\forall t\in\Nats,\sigma(s)_t=s_{t+1}$
  59 % \item $G_{f_g}$ définie par
  60 %    \[
  61 %   G_{f_g}(x,S)=(F_{f_g}(x,s_0),\sigma(S)),
  62 %   \]
  63
  64 % \end{itemize}
  65
  66 % \item Distance $d$: $d((x,s),(x',s'))= d_H(x,x')+d'_S(s,s')$
  67 % \end{itemize}
  68
  69 % \begin{theorem}[Fonctions t.q.  $G_{f_g}$ est chaotique]
  70 % \label{Th:CaracIC}
  71 % Soit $f:\Bool^{\mathsf{N}}\to\Bool^{\mathsf{N}}$.
  72 % Les itérations de la fonction $G_{f_g}$ sont chaotiques
  73 % si et seulement si $\textsc{gig}(f)$ est fortement connexe.
  74 % \end{theorem}