La chaîne de Markov associée converge vers la distribution uniforme et
\[
-\forall \varepsilon >0,\, t_{\rm mix}(\varepsilon) \le 32 {\mathsf{N}}^2+ 16{\mathsf{N}}\ln ({\mathsf{N}}+1) = O(N^2).
+\forall \varepsilon >0,\, t_{\rm mix}(\varepsilon) \le
+x
+\leq \lceil\log_2(\varepsilon^{-1})
+(32 {\mathsf{N}}^2+ 16{\mathsf{N}}\ln ({\mathsf{N}}+1))
\]
\end{restatable}
Cela s'explique assez simplement. Depuis une configuration initiale, le nombre
de configurations qu'on ne peut pas atteindre en une itération est de:
\begin{itemize}
-\item $2^n-n$ en unaire. Ceci représente un rapport de
- $\dfrac{2^n-n}{2^n} = 1-\dfrac{n}{2^n}$
+\item $2^n-n-1$ en unaire. Ceci représente un rapport de
+ $\dfrac{2^n-n-1}{2^n} = 1-\dfrac{n-1}{2^n}$
de toutes les configurations; plus $n$ est grand,
plus ce nombre est proche de $1$, et plus grand devient le nombre
d'itérations nécessaires pour atteinte une déviation faible;
Parmi les suites simples classiquement embarquées dans les CPRNGs, on trouve principalement
-la suite logistique et
-la suite de Hénon. La suite logistique~\cite{may1976simple} est définie de $[0;1]$ dans lui même par $x_{t+1} = r \times x_t(1-x_t)$
+la suite logistique,
+la suite de Hénon.
+La suite logistique~\cite{may1976simple} est définie de $[0;1]$ dans lui même par $x_{t+1} = r \times x_t(1-x_t)$
avec $x_0 \in [0;1]$ et $3,57<r<4,0$.
La suite de Hénon~\cite{henon1976two} de $A \times B$ dans lui même, avec $A$ et $B$ deux sous-ensembles de $\R$,
est définie par
$f$ est une adaptation de la suite logistique au cas discret,
la graine $(X_0(0),\dots, X_0(L-1))$ et la pondération $\varepsilon$ sont fournies par l'utilisateur.
+
+René Lozi a aussi étudié la construction de PRNGs en couplant
+des suites de Lozi~\cite{espinelrojas:hal-00622989} (qui sont une variation des suites de Hénon: $x^2_t$ est remplacé par $| x_t|$),
+la suite tente~\cite{DBLP:journals/ijbc/Lozi12} et en extrayant des
+sous-suites pour construire la sortie du PRNG~\cite{lozi:hal-00813087}.
+
+
+
+
Certaines équations différentielles ont été à la base de PRNGs chaotiques.
On pense aux équations de Lorenz~\cite{Lorenz1963}, à celles de Rössler~\cite{Rossler1976397}\ldots
Celles-ci ont par exemple embarquées dans les PRNG dans les articles~\cite{Silva:2009:LLP:1592409.1592411}
et~\cite{mansingka2013fibonacci} respectivement.
-\section{ Nombres pseudo-aléatoires construits par itérations unaires}\label{sub:prng:algo}
+
+
+\section{Nombres pseudo-aléatoires construits par itérations unaires}\label{sub:prng:algo}
On énonce directement le théorème suivant dont la preuve est donnée en annexe~\ref{anx:generateur}.
\begin{restatable}[Uniformité de la sortie de l'algorithme~\ref{CI Algorithm}]{theorem}{PrngCIUniforme}\label{thm:prng:u}
- Soit $f: \Bool^{n} \rightarrow \Bool^{n}$, $\textsc{giu}(f)$ son
+ Soit $f: \Bool^{\mathsf{N}} \rightarrow \Bool^{\mathsf{N}}$, $\textsc{giu}(f)$ son
graphe d'itérations , $\check{M}$ sa matrice d'adjacence
et $M$ une matrice $2^n\times 2^n$
définie par
- $M = \dfrac{1}{n} \check{M}$.
+ $M = \dfrac{1}{\mathsf{N}} \check{M}$.
Si $\textsc{giu}(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
colonne utilisé comme le paramètre $b$
dans l'algorithme~\ref{CI Algorithm}.
-Soit $e_i$ le $i^{\textrm{ème}}$ vecteur de la base canonique de $\R^{2^{n}}$.
-Chacun des éléments $v_j$, $1 \le j \le 2^n$,
+Soit $e_i$ le $i^{\textrm{ème}}$ vecteur de la base canonique de $\R^{2^{\mathsf{N}}}$.
+Chacun des éléments $v_j$, $1 \le j \le 2^{\mathsf{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é à $\textsc{giu}(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})$
+ce vecteur au vecteur $\pi=(\frac{1}{2^{\mathsf{N}}},\ldots,\frac{1}{2^{\mathsf{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
\begin{equation}
-b = \max\limits_{i \in \llbracket 1, 2^n \rrbracket}
+b = \max\limits_{i \in \llbracket 1, 2^{\mathsf{N}} \rrbracket}
\left\{
\min \left\{
t \mid t \in \Nats, \vectornorm{e_i M_f^t - \pi} < 10^{-4}
\rightarrow \mathds{B}^\mathsf{N}$ définie par
$$
-F_{f_u,p_i} (x,(u^0, u^1, \hdots, u^{p_i-1})) \mapsto
+F_{f_u,p_i} (x,(u^0, u^1, \hdots, u^{p_i-1})) =
F_{f_u}(\hdots (F_{f_u}(F_{f_u}(x,u^0), u^1), \hdots), u^{p_i-1}).
$$
Ainsi, les sorties $(y^0, y^1, \hdots )$ produites par le générateur détaillé dans
l'algorithme~\ref{CI Algorithm}
sont les premiers composants des itérations $X^0 = (x^0, (u,v))$ et $\forall n \in \mathds{N},
-X^{n+1} = G_{f_u,\mathcal{P}}(X^n)$ dans $\mathcal{X}_{\mathsf{N},\mathcal{P}}$ où
+X^{n+1} = G_{f_u,\mathcal{P}}(X^{\mathsf{N}})$ dans $\mathcal{X}_{\mathsf{N},\mathcal{P}}$ où
$G_{f_u,\mathcal{P}}$ est définie par:
Soit alors $G_{f_g}$ une fonction de $\Bool^{\mathsf{N}} \times \mathcal{P}(\{1, \ldots, {\mathsf{N}}\})^{\Nats}$
dans lui-même définie par
\[
- G_{f_g}(S,x)=(\sigma(S),F_{f_g}(s_0,x)),
+ G_{f_g}(x,S)=(F_{f_g}(x,s_0),\sigma(S)),
\]
où la fonction $\sigma$ est définie comme à la section précédente.
A nouveau, les itérations généralisées
+Ce travail a été guidé par la volonté de
+comprendre une partie des avancées théoriques et pratiques autour des systèmes discrets,
+de formuler de nouvelles propositions dans ce champ thématique et
+de les démontrer lorsque nos connaissances le permettaient.
+Ce travail est le fruit d'une équipe et nombreux sont ceux qui y ont pris part.
-\subsection{Synthèses des contributions}
+Ce chapitre en présente tout d'abord une synthèse (section~\ref{sec:concl:synth}).
+Quelques perspectives qui s'en dégagent sont ensuite esquissées (section~\ref{sec:concl:persp}).
+
+
+\section{Synthèses des contributions}\label{sec:concl:synth}
Les principales contributions gravitent autour des mathématiques discrètes et plus particulièrement
les itérations de systèmes dynamiques discrets.
ou de matrice Hessienne. Grâce à l'étude de ces matrices, nous avons proposé un nouveau schéma de
stéganographie sécurisé (chapitre~\ref{chap:th:yousra}).
-\subsection{Quelques perspectives}
-
-\subsubsection{Étendons les PRNGs}
+\section{Quelques perspectives}\label{sec:concl:persp}
+Les expériences, résultats et connaissances acquises lors de ce travail conduisent vers de nouvelles perspectives présentées ci-après.
+\subsection{Autour des PRNGs}
La démarche actuelle de génération de nombres pseudo-aléatoires
consiste à marcher dans une partie d'un $\mathsf{N}$-cube en choisissant son chemin
à l'aide d'un générateur fourni en entrée. Or ces générateurs sont tous des
qu'on pouvait modifier plusieurs bits
en une seule itération. Les premiers travaux pratiques réalisés ont montré
que le nombre d'itérations suffisant pour converger vers une distribution uniforme
-est plus petit que celui obtenu en marchant et qu'il diminue à mesure que $\mathsf{N}$
+est plus petit que celui obtenu en marchant et, plus intéressant encore,
+qu'il diminue à mesure que $\mathsf{N}$
augmente. Pour l'instant, nous n'avons pas réussi à obtenir une majoration du nombre d'itérations
-pour le temps d'arrêt, ce qui pourrait être une perspective.
+pour le temps d'arrêt ce que nous pourrons faire dans un avenir proche.
+
+Il nous paraît aussi important de déployer tout le travail fait autour des PRNG sur des plates-formes physiques.
+On pense aux circuits logiques programmables (FPGA) ou aux circuits intégrés dédiés à une application (ASIC).
+Un premier travail~\cite{DBLP:conf/secrypt/MohammedCG16} a été réalisé en ce sens et a consisté à comparer, sur FPGA uniquement,
+les implantations existantes de PRNGs de la littérature ainsi que celles à base d'itérations unaires.
+Poursuivre le déploiement sur ces deux familles d'architecture, intégrer les itérations généralisées et les combiner nous
+est une piste de recherche que nous allons poursuivre.
+
-\subsubsection{Des codes de Gray localement et globalement équilibrés}
+
+
+
+\subsection{Des codes de Gray localement et globalement équilibrés}
Enfin, pour générer une fonction dont la matrice de Markov est doublement
stochastique
--condition nécessaire pour fournir une sortie uniformément distribuée--,
Un second verrou consistera à adapter ces algorithmes pour proposer des codes possédant les
deux propriétés d'équilibrage.
-\subsubsection{Stéganalyse par deep learning}
+\subsection{Stéganalyse par deep learning}
Les démarches de stéganalyse sont souvent composées de 2 étapes:
caractérisation puis classification.
à adapter l'outil de deep learning aux caractéristiques restantes ce qui est un autre challenge
scientifique.
-\subsection{}
\ No newline at end of file
+
+
&
% conf inter
-\cite{accfg15:ip,ccfg16:ip,kcm16:ip}
+\cite{accfg15:ip,DBLP:conf/secrypt/MohammedCG16,ccfg16:ip,kcm16:ip}
%%--------------------
%% Add a member of the jury
%% \addjury{Firstname}{Lastname}{Role in the jury}{Position}
-\addjury{First}{Name}{Rapporteur}{Professeur à l'Université de XXX}
-\addjury{First}{Name}{Examinateur}{Professeur à l'Université de XXX}
+\addjury{Olivier}{Bournez}{Rapporteur}{Professeur à l'Ecole Polytechnique}
+\addjury{Jean-Paul}{Comet}{Rapporteur}{Professeur à l'Université de Nice Sophia Antipolis}
+\addjury{Juan-Pablo}{Ortega}{Rapporteur}{Professeur à l'Université de St. Gallen--Suisse}
+\addjury{Sylvain}{Contassot-Vivier}{Examinateur}{Professeur à l'Université de Lorraine}
+\addjury{Raphaël}{Couturier}{Examinateur}{Professeur à l'Université de Bourgogne Franche-Comté}
+\addjury{Christophe}{Guyeux}{Examinateur}{Professeur à l'Université de Bourgogne Franche-Comté}
+
+
%%--------------------
%% Change the style of the text in the list of the members of the jury.
%%--------------------
%% Set the University where HDR was made
-\hdrpreparedin{Université Bourgone Franche-Comté}
+\hdrpreparedin{Université Bourgogne Franche-Comté}
%%--------------------
-\part*{Conclusion et Perspectives}
+\part{Conclusion}
+\chapter{Conclusion et Perspectives}
\input{conclusion}
x^{t+1}_i= \left\{
\begin{array}{l}
f_i( x_1^{D_{i1}^t},\ldots, x_{n}^{D_{i{n}}^t})
- \textrm{ si } \textit{bin}(s^t)[i] = 1\\
- x^{t}_i \textrm{ sinon }
+ \textrm{ si } i \in s^t \\
+ x^{t}_i \textrm{ sinon.}
\end{array}
\right.
\end{equation}
\item Deux modes:
\begin{itemize}
\item
- \emph{synchrone}: chaque élément attend la valeur des élements dont il dépend;
+ \emph{Synchrone}: chaque élément attend la valeur des élements dont il dépend.
\item
- \emph{asynchrone}: chaque élément met à jour sa valeur sans attendre.
+ \emph{Asynchrone}: chaque élément met à jour sa valeur sans attendre.
\end{itemize}
\item $(D^{t})^{t \in \Nats}$: suite de matrices de taille $\mathsf{N} \times \mathsf{N}$ t.q.
\end{itemize}
\vspace{-1em}
-\begin{exampleblock}{Attracteurs de
+\begin{block}{Attracteurs de
$(x_1, x_2, x_3) \mapsto
((\overline{x_1} + \overline{x_2}).x_3,
x_1.x_3,
}
\end{center}
\end{figure}
-\end{exampleblock}
+\end{block}
--- /dev/null
+\begin{definition}[Chaos selon Devaney]
+$k$ continue sur $(\mathcal{X},d)$ est chaotique si elle est transitive,
+régulière et fortement sensible aux conditions initiales.
+
+\begin{itemize}
+\item \emph{Transitivitivé}: pour chaque point, chacun de ses voisinages
+ a un futur pouvant contenir tout point de l'espace.
+\item \emph{Régularité}: l'ensemble de ses points
+périodiques est dense dans $\mathcal{X}$.
+\item \emph{Forte sensibilité aux cond. initiales}: pour chaque point,
+ chacun de ses voisinages a un point dont un futur est éloigné.
+\end{itemize}
+\end{definition}
+
+
--- /dev/null
+\begin{itemize}
+\item Vers une fonction de
+$\mathcal{X}_g =\Bool^{\mathsf{N}}
+\times \left(\mathcal{P}([{\mathsf{N}}]\right)^{\Nats}$
+dans lui même:
+\begin{itemize}
+\item $F_{f_g}: \Bool^{\mathsf{N}} \times \mathcal{P}([{\mathsf{N}}])
+ \rightarrow \Bool^{\mathsf{N}}$ par
+ $
+ F_{f_g}(x,s)_i=\left\{
+ \begin{array}{l}
+ f_i(x) \textrm{ si $i \in s$;}\\
+ x_i \textrm{ sinon.}
+ \end{array}\right.
+ $
+\item $\sigma:
+ \mathcal{P}([{\mathsf{N}}])^{\Nats}
+ \rightarrow
+ \mathcal{P}([{\mathsf{N}}])^{\Nats}$
+ t.q. $\forall t\in\Nats,\sigma(s)_t=s_{t+1}$
+\item $G_{f_g}$ définie par
+ $
+ G_{f_g}(x,S)=(F_{f_g}(x,s_0),\sigma(S)),
+ $
+
+\end{itemize}
+
+\item Distance $d$: $d((x,s),(x',s'))= d_H(x,x')+d'_S(s,s')$
+\end{itemize}
+
+\begin{theorem}[Fonctions t.q. $G_{f_g}$ est chaotique]
+\label{Th:CaracIC}
+Soit $f:\Bool^{\mathsf{N}}\to\Bool^{\mathsf{N}}$.
+Les itérations de la fonction $G_{f_g}$ sont chaotiques
+si et seulement si $\textsc{gig}(f)$ est fortement connexe.
+\end{theorem}
--- /dev/null
+\begin{definition}[Chaos selon Devaney]
+$k$ continue sur $(\mathcal{X},d)$ est chaotique si elle est transitive,
+régulière et fortement sensible aux conditions initiales.
+
+\begin{itemize}
+\item \emph{Transitivitivé}: pour chaque point, chacun de ses voisinages
+ a un futur pouvant contenir tout point de l'espace.
+\item \emph{Régularité}: l'ensemble de ses points
+périodiques est dense dans $\mathcal{X}$.
+\item \emph{Forte sensibilité aux cond. initiales}: pour chaque point,
+ chacun de ses voisinages a un point dont un futur est éloigné.
+\end{itemize}
+\end{definition}
+
+\begin{itemize}
+\item Vers une fonction de
+$\mathcal{X}_u =\Bool^{\mathsf{N}} \times \llbracket1;{\mathsf{N}}\rrbracket^\Nats$
+dans lui même
+\begin{itemize}
+\item $F_{f_u}: \mathcal{X} \rightarrow \Bool^{\mathsf{N}}$,
+$(x,i) \mapsto (x_1,\dots,x_{i-1},f_i(x),x_{i+1},\dots,x_{\mathsf{N}})$
+\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}$
+\item $G_{f_u}$ définie par
+ $G_{f_u}(s,x)=(F_{f_u}(x,s_0),\sigma(s))$
+\end{itemize}
+
+\item Distance $d$: $d((x,s),(x',s'))= d_H(x,x')+d_S(s,s')$
+\end{itemize}
+
--- /dev/null
+\begin{itemize}
+\item Vers une fonction de
+$\mathcal{X}_u =\Bool^{\mathsf{N}} \times [{\mathsf{N}}]^\Nats$
+dans lui même~\cite{guyeuxphd}:
+\begin{itemize}
+\item $F_{f_u}: \Bool^{\mathsf{N}} \times [{\mathsf{N}}] \rightarrow \Bool^{\mathsf{N}}$,
+$(x,i) \mapsto (x_1,\dots,x_{i-1},f_i(x),x_{i+1},\dots,x_{\mathsf{N}})$
+\item $\sigma: [{\mathsf{N}}]^\Nats \rightarrow [{\mathsf{N}}]^\Nats$ t.q. $\forall t\in\Nats,\sigma(s)_t=s_{t+1}$
+\item $G_{f_u}$ définie par
+ $G_{f_u}(x,s)=(F_{f_u}(x,s_0),\sigma(s))$
+\end{itemize}
+
+\item Distance $d$: $d((x,s),(x',s'))= d_H(x,x')+d_S(s,s')$
+\end{itemize}
+
+\begin{theorem}[Fonctions t.q. $G_{f_u}$ est chaotique~\cite{bcg11:ij}]
+\label{Th:CaracIC}
+Soit $f:\Bool^{\mathsf{N}}\to\Bool^{\mathsf{N}}$.
+Les itérations de la fonction $G_{f_u}$ sont chaotiques
+si et seulement si $\textsc{giu}(f)$ est fortement connexe.
+\end{theorem}
--- /dev/null
+ \begin{theorem}[Uniformité de la sortie~\cite{bcgr11:ip}]
+ Soit $f: \Bool^{\mathsf{N}} \rightarrow \Bool^{\mathsf{N}}$, $\textsc{giu}(f)$ son
+ graphe d'itérations , $\check{M}$ sa matrice d'adjacence.
+ Si $\textsc{giu}(f)$ est fortement connexe, alors
+ la sortie du générateur de nombres pseudo-aléatoires suit une loi qui
+ tend vers la distribution uniforme ssi $\dfrac{1}{\mathsf{N}} \check{M}$ est doublement stochastique.
+\end{theorem}
+
+
+\begin{minipage}[b]{0.45\textwidth}
+\begin{block}{}
+ \begin{minipage}[b]{0.15\textwidth}
+ \includegraphics[height=3cm]{../images/g.pdf}
+ \end{minipage}
+ \begin{minipage}[b]{0.80\textwidth}
+ \begin{itemize}
+ \item $g(x_1,x_2)=(\overline{x_1},x_1\overline{x_2})$
+ \item $M_g = \dfrac{1}{2}\left(
+ \begin{array}{c}
+ 1 0 1 0 \\
+ 1 0 0 1 \\
+ 1 0 0 1 \\
+ 0 1 1 0
+ \end{array}
+ \right)$
+ \item $\pi_g=(\frac{4}{10}, \frac{1}{10},\frac{3}{10},\frac{2}{10})$
+ \end{itemize}
+ \end{minipage}
+\end{block}
+\end{minipage}
+\quad
+\begin{minipage}[b]{0.50\textwidth}
+ \begin{block}{}
+ \begin{minipage}[b]{0.15\textwidth}
+ \includegraphics[height=3cm]{../images/h.pdf}
+ \end{minipage}
+ \begin{minipage}[b]{0.82\textwidth}
+ \vspace{-2em}
+ \begin{itemize}
+ \item $h(x_1,x_2)=(\overline{x_1},x_1\overline{x_2}+\overline{x_1}x_2)$
+ \item $M_h = \dfrac{1}{2}\left(
+ \begin{array}{c}
+ 1 0 1 0 \\
+ 0 1 0 1 \\
+ 1 0 0 1 \\
+ 0 1 1 0
+
+ \end{array}
+ \right)
+ $
+ \item $\pi_h=(\frac{1}{2}, \frac{1}{2},\frac{1}{2},\frac{1}{2})$
+ \end{itemize}
+\end{minipage}
+\end{block}
+\end{minipage}
+
-\begin{exampleblock}{Utilisation des nombres aléatoires}
+\begin{block}{Utilisation des nombres aléatoires}
\begin{itemize}
\item Vie courante: localisation GPS, cryptage de données (RSA);
\item Science: statistiques, en probabilité, en simulation numérique.
\end{itemize}
-\end{exampleblock}
+\end{block}
-\begin{exampleblock}{Génération}
+\begin{block}{Génération}
\begin{itemize}
\item Réellement aléatoire: processus physique $\leadsto$ non reproductible.
\item Pseudo-aléatoire (PRNG): algorithme $\leadsto$ reproductible, quid de la sécurité?
\end{itemize}
-\end{exampleblock}
+\end{block}
\begin{alertblock}{Problématique}
Les systèmes dynamiques sont-ils un bon outil mathématique pour
-\begin{exampleblock}{Graphes des itérations de
+\begin{block}{Graphes des itérations de
$(x_1, x_2, x_3) \mapsto
((\overline{x_1} + \overline{x_2}).x_3,
x_1.x_3,
\end{center}
%\caption{}
\end{figure}
-\end{exampleblock}
+\end{block}
% On remarque le cycle $((101,111),(111,011),(011,101))$
% à la \textsc{Figure}~(\ref{fig:fsig}).
\ No newline at end of file
--- /dev/null
+\begin{itemize}
+\item Intuition de convergence rapide vers la distribution uniforme:
+ supprimer un cycle hamiltonien équilibré (chaque bit nié autant de fois).
+\item
+ Extension de \emph{Robinson-Cohn} \cite{ZanSup04}:
+ preuve de l'existence (sans construction) de cycle hamiltonien équilibré.
+
+\begin{theorem}[Constr. de cycles hamiltonien équilibré~\cite{ccgh16}]
+Il existe une séquence (et construction de celle-ci) dans de l'extension
+de l'algorithme de \emph{Robinson-Cohn} telle que le cycle est équilibré.
+\end{theorem}
+
+\item Pratique: grande famille de cycles hamiltonien équilibrés
+ ($\mathsf{N} \le 16$).
+\end{itemize}
--- /dev/null
+\begin{block}{}
+\begin{itemize}
+\item CLPFD: approche de type \og générer, tester\fg{}.
+\item $f^*(x_1,x_2,x_3) =
+(x_2 \oplus x_3, \overline{x_1}\overline{x_3} + x_1\overline{x_2},
+\overline{x_1}\overline{x_3} + x_1x_2)$: très faible $b$.
+\item $f^*$: $3$-cube ss le \emph{cycle hamiltonien}
+$000,100,101,001,011,111,110,010,000$.
+
+\end{itemize}
+\vspace{-1em}
+\begin{minipage}{0.49\textwidth}
+%\includegraphics[scale=0.5]{iter_f0c}
+ \includegraphics<1>[scale=0.4]{../images/iter_f0c}
+ \includegraphics<2>[scale=0.4]{../images/iter_f0d}
+\end{minipage}
+\begin{minipage}{0.49\textwidth}
+\vspace{-1em}
+
+\[
+M=\dfrac{1}{3} \left(
+\begin{array}{llllllll}
+1&1&1&0&0&0&0&0 \\
+1&1&0&0&0&1&0&0 \\
+0&0&1&1&0&0&1&0 \\
+0&1&1&1&0&0&0&0 \\
+1&0&0&0&1&0&1&0 \\
+0&0&0&0&1&1&0&1 \\
+0&0&0&0&1&0&1&1 \\
+0&0&0&1&0&1&0&1
+\end{array}
+\right)
+\]
+\end{minipage}
+\end{block}
+
+
+\begin{theorem}[ $\mathsf{N}$-cube privé d'un cycle hamiltonien ~\cite{chgw+14:oip}]
+ Dans un $\mathsf{N}$-cube, dans lequel un cycle hamiltonien a été enelvé:
+ \begin{itemize}
+ \item La matrice de Markov engendrée est doublement stochastique.
+ \item Le graphe $\textsc{giu}$ correspondant est fortement connexe.
+ \end{itemize}
+\end{theorem}
+
+
--- /dev/null
+
+\begin{theorem}[Temps de mixage sans chemin hamiltonien~\cite{ccgh16}]
+On considère un $\mathsf{N}$-cube dans lequel un chemin hamiltonien a été supprimé et la fonction de
+probabilités $p$ définie sur l'ensemble des arcs comme suit:
+\[
+p(e) \left\{
+\begin{array}{ll}
+= \frac{1}{2} + \frac{1}{2\mathsf{N}} \textrm{ si $e=(v,v)$ avec $v \in \Bool^{\mathsf{N}}$,}\\
+= \frac{1}{2\mathsf{N}} \textrm{ sinon.}
+\end{array}
+\right.
+\]
+
+La chaîne de Markov associée converge vers la distribution uniforme et
+
+\[
+ \, t_{\rm mix}(\varepsilon)
+\leq \lceil\log_2(\varepsilon^{-1})\rceil
+4(8{\mathsf{N}}^2+ 4{\mathsf{N}}\ln ({\mathsf{N}}+1))
+\]
+
+\end{theorem}
+\begin{itemize}
+\item Remarques sur la preuve:
+\begin{itemize}
+\item Itérations paresseuses $\not \equiv$ algorithme.
+\item Hypothèse très faible: suppressions d'un arc entrant et d'un arc sortant
+par n{\oe}ud.
+\item Pratiquement:
+$
+4(8{\mathsf{N}}^2+ 4{\mathsf{N}}\ln ({\mathsf{N}}+1))
+\leadsto
+4(2\mathsf{N}\ln(2\mathsf{N}+8)).
+$
+
+\end{itemize}
+\end{itemize}
$f'_{ij}=\dfrac{f_i(\overline{x}^j){-}f_i(x)}{\overline{x_j}{-}x_j}$.
\item Représentée par un \emph{graphe des interactions} orienté:
\begin{itemize}
-\item Sommets: $\{1, \ldots, {\mathsf{N}}\}$
+\item Sommets: $[{\mathsf{N}}]$
\item Arcs: $j \xrightarrow{s} i$ si $\exists x \in \Bool^{\mathsf{N}}$ tq.
$f'_{ij}(x)=s$,
$s\in\{-1,1\}$
\end{itemize}
\end{itemize}
-\begin{exampleblock}{Graphes des interractions de
+\begin{block}{Graphes des interractions de
$(x_1, x_2, x_3) \mapsto
((\overline{x_1} + \overline{x_2}).x_3,
x_1.x_3,
\begin{minipage}{0.2\textwidth}
\includegraphics[scale=0.4]{gf}
\end{minipage}
-\end{exampleblock}
+\end{block}
\@writefile{snm}{\beamer@slide {sec:sddchaos}{14}}
\@writefile{nav}{\headcommand {\slideentry {3}{0}{1}{14/14}{}{0}}}
\@writefile{nav}{\headcommand {\beamer@framepages {14}{14}}}
-\@writefile{toc}{\beamer@sectionintoc {4}{Applications \IeC {\`a} la g\IeC {\'e}n\IeC {\'e}ration de nombres pseudo-al\IeC {\'e}atoires}{15}{0}{4}}
-\@writefile{nav}{\headcommand {\sectionentry {4}{Applications \IeC {\`a} la g\IeC {\'e}n\IeC {\'e}ration de nombres pseudo-al\IeC {\'e}atoires}{15}{Applications \IeC {\`a} la g\IeC {\'e}n\IeC {\'e}ration de nombres pseudo-al\IeC {\'e}atoires}{0}}}
-\@writefile{nav}{\headcommand {\beamer@sectionpages {14}{14}}}
-\@writefile{nav}{\headcommand {\beamer@subsectionpages {14}{14}}}
-\newlabel{sec:prng}{{4}{15}{Applications à la génération de nombres pseudo-aléatoires}{Doc-Start}{}}
-\@writefile{snm}{\beamer@slide {sec:prng}{15}}
-\@writefile{nav}{\headcommand {\slideentry {4}{0}{1}{15/15}{}{0}}}
+\@writefile{nav}{\headcommand {\slideentry {3}{0}{2}{15/15}{}{0}}}
\@writefile{nav}{\headcommand {\beamer@framepages {15}{15}}}
-\@writefile{toc}{\beamer@sectionintoc {5}{Application au masquage d'information}{16}{0}{5}}
-\@writefile{nav}{\headcommand {\sectionentry {5}{Application au masquage d'information}{16}{Application au masquage d'information}{0}}}
-\@writefile{nav}{\headcommand {\beamer@sectionpages {15}{15}}}
-\@writefile{nav}{\headcommand {\beamer@subsectionpages {15}{15}}}
-\newlabel{sec:ih}{{5}{16}{Application au masquage d'information}{Doc-Start}{}}
-\@writefile{snm}{\beamer@slide {sec:ih}{16}}
-\@writefile{nav}{\headcommand {\slideentry {5}{0}{1}{16/16}{}{0}}}
+\citation{guyeuxphd}
+\citation{bcg11:ij}
+\newlabel{Th:CaracIC}{{4}{16}{Fonctions t.q. $G_{f_u}$ est chaotique~\cite {bcg11:ij}}{Doc-Start}{}}
+\@writefile{snm}{\beamer@slide {Th:CaracIC}{16}}
+\@writefile{nav}{\headcommand {\slideentry {3}{0}{3}{16/16}{}{0}}}
\@writefile{nav}{\headcommand {\beamer@framepages {16}{16}}}
-\@writefile{toc}{\beamer@sectionintoc {6}{Conclusion}{17}{0}{6}}
-\@writefile{nav}{\headcommand {\sectionentry {6}{Conclusion}{17}{Conclusion}{0}}}
-\@writefile{nav}{\headcommand {\beamer@sectionpages {16}{16}}}
-\@writefile{nav}{\headcommand {\beamer@subsectionpages {16}{16}}}
-\@writefile{nav}{\headcommand {\slideentry {6}{0}{1}{17/17}{}{0}}}
+\newlabel{Th:CaracIC}{{5}{17}{Fonctions t.q. $G_{f_g}$ est chaotique}{Doc-Start}{}}
+\@writefile{snm}{\beamer@slide {Th:CaracIC}{17}}
+\@writefile{nav}{\headcommand {\slideentry {3}{0}{4}{17/17}{}{0}}}
\@writefile{nav}{\headcommand {\beamer@framepages {17}{17}}}
-\@writefile{nav}{\headcommand {\slideentry {6}{0}{2}{18/18}{}{0}}}
+\citation{bcgr11:ip}
+\newlabel{th:Adrien}{{6}{18}{Fonctions avec $\textsc {giu}$ fort. connexe~\cite {bcgr11:ip}}{Doc-Start}{}}
+\@writefile{snm}{\beamer@slide {th:Adrien}{18}}
+\@writefile{nav}{\headcommand {\slideentry {3}{0}{5}{18/18}{}{0}}}
\@writefile{nav}{\headcommand {\beamer@framepages {18}{18}}}
+\@writefile{toc}{\beamer@sectionintoc {4}{Applications \IeC {\`a} la g\IeC {\'e}n\IeC {\'e}ration de nombres pseudo-al\IeC {\'e}atoires}{19}{0}{4}}
+\@writefile{nav}{\headcommand {\sectionentry {4}{Applications \IeC {\`a} la g\IeC {\'e}n\IeC {\'e}ration de nombres pseudo-al\IeC {\'e}atoires}{19}{Applications \IeC {\`a} la g\IeC {\'e}n\IeC {\'e}ration de nombres pseudo-al\IeC {\'e}atoires}{0}}}
+\@writefile{nav}{\headcommand {\beamer@sectionpages {14}{18}}}
+\@writefile{nav}{\headcommand {\beamer@subsectionpages {14}{18}}}
+\newlabel{sec:prng}{{4}{19}{Applications à la génération de nombres pseudo-aléatoires}{Doc-Start}{}}
+\@writefile{snm}{\beamer@slide {sec:prng}{19}}
+\@writefile{nav}{\headcommand {\slideentry {4}{0}{1}{19/19}{}{0}}}
+\@writefile{nav}{\headcommand {\beamer@framepages {19}{19}}}
+\citation{bcgw11:ip}
+\@writefile{nav}{\headcommand {\slideentry {4}{0}{2}{20/20}{}{0}}}
+\@writefile{nav}{\headcommand {\beamer@framepages {20}{20}}}
+\citation{bcgr11:ip}
+\@writefile{nav}{\headcommand {\slideentry {4}{0}{3}{21/21}{}{0}}}
+\@writefile{nav}{\headcommand {\beamer@framepages {21}{21}}}
+\@writefile{nav}{\headcommand {\slideentry {4}{0}{4}{22/22}{}{0}}}
+\@writefile{nav}{\headcommand {\beamer@framepages {22}{22}}}
+\citation{ccgh16}
+\citation{ccgh16}
+\@writefile{nav}{\headcommand {\slideentry {4}{0}{5}{23/23}{}{0}}}
+\@writefile{nav}{\headcommand {\beamer@framepages {23}{23}}}
+\citation{chgw+14:oip}
+\citation{chgw+14:oip}
+\@writefile{nav}{\headcommand {\slideentry {4}{0}{6}{24/25}{}{0}}}
+\@writefile{nav}{\headcommand {\beamer@framepages {24}{25}}}
+\citation{ZanSup04}
+\citation{ccgh16}
+\@writefile{nav}{\headcommand {\slideentry {4}{0}{7}{26/26}{}{0}}}
+\@writefile{nav}{\headcommand {\beamer@framepages {26}{26}}}
+\citation{ccgh16}
+\@writefile{nav}{\headcommand {\slideentry {4}{0}{8}{27/27}{}{0}}}
+\@writefile{nav}{\headcommand {\beamer@framepages {27}{27}}}
+\@writefile{nav}{\headcommand {\slideentry {4}{0}{9}{28/28}{}{0}}}
+\@writefile{nav}{\headcommand {\beamer@framepages {28}{28}}}
+\@writefile{nav}{\headcommand {\slideentry {4}{0}{10}{29/29}{}{0}}}
+\@writefile{nav}{\headcommand {\beamer@framepages {29}{29}}}
+\@writefile{toc}{\beamer@sectionintoc {5}{Application au masquage d'information}{30}{0}{5}}
+\@writefile{nav}{\headcommand {\sectionentry {5}{Application au masquage d'information}{30}{Application au masquage d'information}{0}}}
+\@writefile{nav}{\headcommand {\beamer@sectionpages {19}{29}}}
+\@writefile{nav}{\headcommand {\beamer@subsectionpages {19}{29}}}
+\newlabel{sec:ih}{{5}{30}{Application au masquage d'information}{Doc-Start}{}}
+\@writefile{snm}{\beamer@slide {sec:ih}{30}}
+\@writefile{nav}{\headcommand {\slideentry {5}{0}{1}{30/30}{}{0}}}
+\@writefile{nav}{\headcommand {\beamer@framepages {30}{30}}}
+\@writefile{toc}{\beamer@sectionintoc {6}{Conclusion}{31}{0}{6}}
+\@writefile{nav}{\headcommand {\sectionentry {6}{Conclusion}{31}{Conclusion}{0}}}
+\@writefile{nav}{\headcommand {\beamer@sectionpages {30}{30}}}
+\@writefile{nav}{\headcommand {\beamer@subsectionpages {30}{30}}}
+\@writefile{nav}{\headcommand {\slideentry {6}{0}{1}{31/31}{}{0}}}
+\@writefile{nav}{\headcommand {\beamer@framepages {31}{31}}}
+\@writefile{nav}{\headcommand {\slideentry {6}{0}{2}{32/32}{}{0}}}
+\@writefile{nav}{\headcommand {\beamer@framepages {32}{32}}}
\bibstyle{alpha}
\bibdata{abbrev,biblioand}
\bibcite{abcvs05}{\hyperlink {beamerbibabcvs05}{ABCVS05}}
+\bibcite{bcg11:ij}{\hyperlink {beamerbibbcg11:ij}{BCG12}}
+\bibcite{bcgr11:ip}{\hyperlink {beamerbibbcgr11:ip}{BCGR11}}
+\bibcite{bcgw11:ip}{\hyperlink {beamerbibbcgw11:ip}{BCGW11}}
\bibcite{BCVC10:ir}{\hyperlink {beamerbibBCVC10:ir}{BCVC10}}
+\bibcite{ccgh16}{\hyperlink {beamerbibccgh16}{CCVHG16}}
+\bibcite{chgw+14:oip}{\hyperlink {beamerbibchgw+14:oip}{CHG{$^{+}$}14}}
\bibcite{Cou10:ir}{\hyperlink {beamerbibCou10:ir}{Cou10}}
+\bibcite{guyeuxphd}{\hyperlink {beamerbibguyeuxphd}{Guy10}}
\bibcite{Hol03}{\hyperlink {beamerbibHol03}{Hol03}}
-\@writefile{nav}{\headcommand {\beamer@partpages {1}{20}}}
-\@writefile{nav}{\headcommand {\beamer@subsectionpages {17}{20}}}
-\@writefile{nav}{\headcommand {\beamer@sectionpages {17}{20}}}
-\@writefile{nav}{\headcommand {\beamer@documentpages {20}}}
-\@writefile{nav}{\headcommand {\def \inserttotalframenumber {18}}}
+\bibcite{ZanSup04}{\hyperlink {beamerbibZanSup04}{ZS04}}
+\@writefile{nav}{\headcommand {\beamer@partpages {1}{37}}}
+\@writefile{nav}{\headcommand {\beamer@subsectionpages {31}{37}}}
+\@writefile{nav}{\headcommand {\beamer@sectionpages {31}{37}}}
+\@writefile{nav}{\headcommand {\beamer@documentpages {37}}}
+\@writefile{nav}{\headcommand {\def \inserttotalframenumber {31}}}
-\begin{thebibliography}{ABCVS05}
+\newcommand{\etalchar}[1]{$^{#1}$}
+\begin{thebibliography}{CCVHG16}
\bibitem[ABCVS05]{abcvs05}
A.~Abbas, J.~M. Bahi, S.~Contassot-Vivier, and M.~Salomon.
Algorithms, DCDIS'2005}, pages 524--529, Guelph, Canada, July 2005.
\newblock ISSN 1492-8760.
+\bibitem[BCG12]{bcg11:ij}
+Jacques Bahi, Jean-Fran\c{c}ois Couchot, and Christophe Guyeux.
+\newblock Steganography: a class of secure and robust algorithms.
+\newblock {\em The Computer Journal}, 55(6):653--666, 2012.
+
+\bibitem[BCGR11]{bcgr11:ip}
+Jacques Bahi, Jean-Fran\c{c}ois Couchot, Christophe Guyeux, and Adrien Richard.
+\newblock On the link between strongly connected iteration graphs and chaotic
+ boolean discrete-time dynamical systems.
+\newblock In {\em FCT'11, 18th Int. Symp. on Fundamentals of Computation
+ Theory}, volume 6914 of {\em LNCS}, pages 126--137, Oslo, Norway, August
+ 2011.
+
+\bibitem[BCGW11]{bcgw11:ip}
+Jacques Bahi, Jean-Fran\c{c}ois Couchot, Christophe Guyeux, and Qianxue Wang.
+\newblock Class of trustworthy pseudo random number generators.
+\newblock In {\em INTERNET 2011, the 3-rd Int. Conf. on Evolving Internet},
+ pages 72--77, Luxembourg, Luxembourg, June 2011.
+
\bibitem[BCVC10]{BCVC10:ir}
J.~M. Bahi, S.~Contassot-Vivier, and J.-F. Couchot.
\newblock Convergence results of combining synchronism and asynchronism for
\newblock Research Report RR2010-02, LIFC - Laboratoire d’{I}nformatique de
l'{U}niversit\'{e} de {F}ranche {C}omt\'{e}, May 2010.
+\bibitem[CCVHG16]{ccgh16}
+Jean-Fran\c{c}ois Couchot, Sylvain Contassot-Vivier, Pierre-Cyrille H\'eam, and
+ Christophe Guyeux.
+\newblock Random walk in a n-cube without hamiltonian cycle to chaotic
+ pseudorandom number generation: Theoretical and practical considerations.
+\newblock {\em International Journal of Bifurcation and Chaos}, 2016.
+\newblock Accepted on Oct 2016.
+
+\bibitem[CHG{\etalchar{+}}14]{chgw+14:oip}
+Jean-Fran\c{c}ois Couchot, Pierre-Cyrille H\'eam, Christophe Guyeux, Qianxue
+ Wang, and Jacques Bahi.
+\newblock Pseudorandom number generators with balanced gray codes.
+\newblock In {\em Secrypt 2014, 11th Int. Conf. on Security and Cryptography},
+ pages 469--475, Vienna, Austria, August 2014.
+
\bibitem[Cou10]{Cou10:ir}
J.-F. Couchot.
\newblock Formal {C}onvergence {P}roof for {D}iscrete {D}ynamical {S}ystems.
\newblock Research Report RR2010-03, LIFC - Laboratoire d’{I}nformatique de
l'{U}niversit\'{e} de {F}ranche {C}omt\'{e}, May 2010.
+\bibitem[Guy10]{guyeuxphd}
+Christophe Guyeux.
+\newblock {\em Le désordre des it\'erations chaotiques et leur utilit\'e en
+ sécurit\'e informatique}.
+\newblock Th\`ese de {D}octorat, LIFC, Universit\'e de Franche-Comt\'e, 13
+ décembre 2010.
+\newblock Rapporteurs~: Pascale Charpin, Directrice de Recherche,
+ INRIA-Rocquencourt ; Eric Filiol, Professeur, ESIEA-Laval ; Pierre Spitéri,
+ Professeur Emérite, IRIT-ENSEEIHT. Examinateurs~: Michel de Labachelerie,
+ Directeur de recherche CNRS, Université de Franche-Comté ; Laurent Larger,
+ Professeur, Université de Franche-Comté ; Jean-Claude Miellou, Professeur,
+ Université de Franche-Comté ; Congduc Pham, Professeur, Université de Pau.
+ Directeur~: Jacques M. Bahi, Professeur, Université de Franche-Comté.
+
\bibitem[Hol03]{Hol03}
Gerard~J. Holzmann.
\newblock {\em The SPIN Model Checker: Primer and Reference Manual}.
\newblock Addison-Wesley, Pearson Education, 2003.
+\bibitem[ZS04]{ZanSup04}
+A.~J.~van Zanten and I.~N. Suparta.
+\newblock Totally balanced and exponentially balanced gray codes.
+\newblock {\em Discrete Analysis and Operational Research}, 11:81--98, 2004.
+
\end{thebibliography}
The style file: alpha.bst
Database file #1: abbrev.bib
Database file #2: biblioand.bib
-You've used 4 entries,
+You've used 11 entries,
2543 wiz_defined-function locations,
- 635 strings with 6070 characters,
-and the built_in function-call counts, 1552 in all, are:
-= -- 153
-> -- 72
-< -- 5
-+ -- 26
-- -- 25
-* -- 104
-:= -- 271
-add.period$ -- 13
-call.type$ -- 4
-change.case$ -- 24
-chr.to.int$ -- 4
-cite$ -- 4
-duplicate$ -- 67
-empty$ -- 104
-format.name$ -- 31
-if$ -- 312
+ 688 strings with 8219 characters,
+and the built_in function-call counts, 4929 in all, are:
+= -- 502
+> -- 252
+< -- 10
++ -- 92
+- -- 91
+* -- 361
+:= -- 819
+add.period$ -- 36
+call.type$ -- 11
+change.case$ -- 75
+chr.to.int$ -- 11
+cite$ -- 11
+duplicate$ -- 198
+empty$ -- 322
+format.name$ -- 104
+if$ -- 1005
int.to.chr$ -- 1
int.to.str$ -- 0
-missing$ -- 3
-newline$ -- 24
-num.names$ -- 12
-pop$ -- 27
+missing$ -- 9
+newline$ -- 62
+num.names$ -- 33
+pop$ -- 74
preamble$ -- 1
-purify$ -- 29
+purify$ -- 87
quote$ -- 0
-skip$ -- 50
+skip$ -- 159
stack$ -- 0
-substring$ -- 61
-swap$ -- 13
-text.length$ -- 5
-text.prefix$ -- 2
+substring$ -- 242
+swap$ -- 47
+text.length$ -- 10
+text.prefix$ -- 3
top$ -- 0
-type$ -- 28
+type$ -- 84
warning$ -- 0
-while$ -- 13
-width$ -- 8
-write$ -- 56
+while$ -- 46
+width$ -- 16
+write$ -- 155
-This is pdfTeX, Version 3.14159265-2.6-1.40.17 (TeX Live 2016/Debian) (preloaded format=pdflatex 2016.11.27) 6 JAN 2017 17:25
+This is pdfTeX, Version 3.14159265-2.6-1.40.17 (TeX Live 2016/Debian) (preloaded format=pdflatex 2016.11.27) 9 JAN 2017 14:31
entering extended mode
restricted \write18 enabled.
%&-line parsing enabled.
-**main.tex
+**main.tex bib
(./main.tex
LaTeX2e <2016/03/31> patch level 3
Babel <3.9r> and hyphenation patterns for 5 language(s) loaded.
File: listings.cfg 2015/06/04 1.6 listings configuration
))
Package: listings 2015/06/04 1.6 (Carsten Heinz)
- (./main.aux)
+ (./main.aux
+
+LaTeX Warning: Label `Th:CaracIC' multiply defined.
+
+)
\openout1 = `main.aux'.
LaTeX Font Info: Checking defaults for OML/cmm/m/it on input line 64.
LaTeX Font Info: Checking defaults for PD1/pdf/m/n on input line 64.
LaTeX Font Info: ... okay on input line 64.
LaTeX Font Info: Try loading font information for T1+phv on input line 64.
-
-(/usr/share/texlive/texmf-dist/tex/latex/psnfss/t1phv.fd
+ (/usr/share/texlive/texmf-dist/tex/latex/psnfss/t1phv.fd
File: t1phv.fd 2001/06/04 scalable font definitions for T1/phv.
)
*geometry* driver: auto-detecting
(pdftex.def) Requested size: 99.58464pt x 53.12378pt.
[7
- <../images/para_iterate_dec.pdf> <../images/chao_iterate_excerpt.pdf>] (./sddp
-roblematique.tex)
+ <../images/para_iterate_dec.pdf> <../images/chao_iterate_excerpt.pdf>] (./main
+.toc)
File: logo-FEMTO.jpg Graphic file (type jpg)
<use logo-FEMTO.jpg>
-Package pdftex.def Info: logo-FEMTO.jpg used on input line 119.
+Package pdftex.def Info: logo-FEMTO.jpg used on input line 120.
(pdftex.def) Requested size: 28.45274pt x 11.08414pt.
File: Hexagones.jpg Graphic file (type jpg)
-
-<use Hexagones.jpg>
-Package pdftex.def Info: Hexagones.jpg used on input line 119.
+ <use Hexagones.jpg>
+Package pdftex.def Info: Hexagones.jpg used on input line 120.
(pdftex.def) Requested size: 99.58464pt x 53.12378pt.
[8
-] (./main.toc)
+]
+(./main.toc)
File: logo-FEMTO.jpg Graphic file (type jpg)
<use logo-FEMTO.jpg>
-Package pdftex.def Info: logo-FEMTO.jpg used on input line 122.
+Package pdftex.def Info: logo-FEMTO.jpg used on input line 123.
(pdftex.def) Requested size: 28.45274pt x 11.08414pt.
File: Hexagones.jpg Graphic file (type jpg)
<use Hexagones.jpg>
-Package pdftex.def Info: Hexagones.jpg used on input line 122.
+Package pdftex.def Info: Hexagones.jpg used on input line 123.
(pdftex.def) Requested size: 99.58464pt x 53.12378pt.
-
-[9
+ [9
] (./synchronisons.tex)
File: logo-FEMTO.jpg Graphic file (type jpg)
- <use logo-FEMTO.jpg>
-Package pdftex.def Info: logo-FEMTO.jpg used on input line 123.
+<use logo-FEMTO.jpg>
+Package pdftex.def Info: logo-FEMTO.jpg used on input line 124.
(pdftex.def) Requested size: 28.45274pt x 11.08414pt.
File: Hexagones.jpg Graphic file (type jpg)
<use Hexagones.jpg>
-Package pdftex.def Info: Hexagones.jpg used on input line 123.
+Package pdftex.def Info: Hexagones.jpg used on input line 124.
(pdftex.def) Requested size: 99.58464pt x 53.12378pt.
[10
-]
-(./mixteexample.tex <../images/eval_sync.pdf, id=205, 1001.7425pt x 236.885pt>
+] (./mixteexample.tex
+<../images/eval_sync.pdf, id=201, 1001.7425pt x 236.885pt>
File: ../images/eval_sync.pdf Graphic file (type pdf)
<use ../images/eval_sync.pdf>
Package pdftex.def Info: ../images/eval_sync.pdf used on input line 5.
(pdftex.def) Requested size: 200.34494pt x 47.37616pt.
-<../images/eval_async.pdf, id=206, 1001.7425pt x 236.885pt>
+<../images/eval_async.pdf, id=202, 1001.7425pt x 236.885pt>
File: ../images/eval_async.pdf Graphic file (type pdf)
<use ../images/eval_async.pdf>
Package pdftex.def Info: ../images/eval_async.pdf used on input line 10.
(pdftex.def) Requested size: 200.34494pt x 47.37616pt.
-<../images/eval_mixte.pdf, id=207, 1001.7425pt x 236.885pt>
+<../images/eval_mixte.pdf, id=203, 1001.7425pt x 236.885pt>
File: ../images/eval_mixte.pdf Graphic file (type pdf)
<use ../images/eval_mixte.pdf>
Package pdftex.def Info: ../images/eval_mixte.pdf used on input line 16.
(pdftex.def) Requested size: 200.34494pt x 47.37616pt.
)
-Overfull \vbox (18.03525pt too high) detected at line 124
- []
-
File: logo-FEMTO.jpg Graphic file (type jpg)
-<use logo-FEMTO.jpg>
-Package pdftex.def Info: logo-FEMTO.jpg used on input line 124.
+ <use logo-FEMTO.jpg>
+Package pdftex.def Info: logo-FEMTO.jpg used on input line 125.
(pdftex.def) Requested size: 28.45274pt x 11.08414pt.
File: Hexagones.jpg Graphic file (type jpg)
<use Hexagones.jpg>
-Package pdftex.def Info: Hexagones.jpg used on input line 124.
+Package pdftex.def Info: Hexagones.jpg used on input line 125.
(pdftex.def) Requested size: 99.58464pt x 53.12378pt.
- [11
+
+[11
<../images/eval_sync.pdf> <../images/eval_async.pdf> <../images/eval_mixte.pdf
>] (./preuveconvmotiv.tex)
File: logo-FEMTO.jpg Graphic file (type jpg)
-
-<use logo-FEMTO.jpg>
-Package pdftex.def Info: logo-FEMTO.jpg used on input line 125.
+ <use logo-FEMTO.jpg>
+Package pdftex.def Info: logo-FEMTO.jpg used on input line 126.
(pdftex.def) Requested size: 28.45274pt x 11.08414pt.
File: Hexagones.jpg Graphic file (type jpg)
<use Hexagones.jpg>
-Package pdftex.def Info: Hexagones.jpg used on input line 125.
+Package pdftex.def Info: Hexagones.jpg used on input line 126.
(pdftex.def) Requested size: 99.58464pt x 53.12378pt.
[12
-] (./sdd2promela.tex
+]
+(./sdd2promela.tex
LaTeX Font Info: Try loading font information for T1+pcr on input line 8.
-
-(/usr/share/texlive/texmf-dist/tex/latex/psnfss/t1pcr.fd
+ (/usr/share/texlive/texmf-dist/tex/latex/psnfss/t1pcr.fd
File: t1pcr.fd 2001/06/04 font definitions for T1/pcr.
))
File: logo-FEMTO.jpg Graphic file (type jpg)
<use logo-FEMTO.jpg>
-Package pdftex.def Info: logo-FEMTO.jpg used on input line 126.
+Package pdftex.def Info: logo-FEMTO.jpg used on input line 127.
(pdftex.def) Requested size: 28.45274pt x 11.08414pt.
File: Hexagones.jpg Graphic file (type jpg)
<use Hexagones.jpg>
-Package pdftex.def Info: Hexagones.jpg used on input line 126.
+Package pdftex.def Info: Hexagones.jpg used on input line 127.
(pdftex.def) Requested size: 99.58464pt x 53.12378pt.
[13
File: logo-FEMTO.jpg Graphic file (type jpg)
<use logo-FEMTO.jpg>
-Package pdftex.def Info: logo-FEMTO.jpg used on input line 131.
+Package pdftex.def Info: logo-FEMTO.jpg used on input line 133.
(pdftex.def) Requested size: 28.45274pt x 11.08414pt.
File: Hexagones.jpg Graphic file (type jpg)
<use Hexagones.jpg>
-Package pdftex.def Info: Hexagones.jpg used on input line 131.
+Package pdftex.def Info: Hexagones.jpg used on input line 133.
(pdftex.def) Requested size: 99.58464pt x 53.12378pt.
[14
-] (./main.toc)
+] (./chaosDevaney.tex)
File: logo-FEMTO.jpg Graphic file (type jpg)
<use logo-FEMTO.jpg>
-Package pdftex.def Info: logo-FEMTO.jpg used on input line 135.
+Package pdftex.def Info: logo-FEMTO.jpg used on input line 134.
(pdftex.def) Requested size: 28.45274pt x 11.08414pt.
File: Hexagones.jpg Graphic file (type jpg)
<use Hexagones.jpg>
-Package pdftex.def Info: Hexagones.jpg used on input line 135.
+Package pdftex.def Info: Hexagones.jpg used on input line 134.
(pdftex.def) Requested size: 99.58464pt x 53.12378pt.
[15
-] (./main.toc)
+] (./chaosDevaneyUnaire.tex)
File: logo-FEMTO.jpg Graphic file (type jpg)
<use logo-FEMTO.jpg>
-Package pdftex.def Info: logo-FEMTO.jpg used on input line 140.
+Package pdftex.def Info: logo-FEMTO.jpg used on input line 135.
(pdftex.def) Requested size: 28.45274pt x 11.08414pt.
File: Hexagones.jpg Graphic file (type jpg)
<use Hexagones.jpg>
-Package pdftex.def Info: Hexagones.jpg used on input line 140.
+Package pdftex.def Info: Hexagones.jpg used on input line 135.
(pdftex.def) Requested size: 99.58464pt x 53.12378pt.
[16
-] (./main.toc)
+] (./chaosDevaneyGeneralisees.texpdfTeX warning (ext4): destination with the sa
+me identifier (name{Th:CaracIC}) has been already used, duplicate ignored
+<to be read again>
+ \relax
+l.32 \label{Th:CaracIC}
+ )
+File: logo-FEMTO.jpg Graphic file (type jpg)
+ <use logo-FEMTO.jpg>
+Package pdftex.def Info: logo-FEMTO.jpg used on input line 136.
+(pdftex.def) Requested size: 28.45274pt x 11.08414pt.
+File: Hexagones.jpg Graphic file (type jpg)
+ <use Hexagones.jpg>
+Package pdftex.def Info: Hexagones.jpg used on input line 136.
+(pdftex.def) Requested size: 99.58464pt x 53.12378pt.
+ [17
+
+]
+(./tipe12.tex
+LaTeX Font Info: Font shape `T1/phv/bx/sc' in size <12> not available
+(Font) Font shape `T1/phv/b/sc' tried instead on input line 8.
+LaTeX Font Info: Font shape `T1/phv/bx/n' in size <8> not available
+(Font) Font shape `T1/phv/b/n' tried instead on input line 8.
+LaTeX Font Info: Font shape `T1/phv/bx/n' in size <6> not available
+(Font) Font shape `T1/phv/b/n' tried instead on input line 8.
+LaTeX Font Info: Font shape `T1/phv/m/it' in size <9> not available
+(Font) Font shape `T1/phv/m/sl' tried instead on input line 12.
+ <../images/Gi.pdf, id=280, 291.0875pt x 134.5025pt>
+File: ../images/Gi.pdf Graphic file (type pdf)
+
+<use ../images/Gi.pdf>
+Package pdftex.def Info: ../images/Gi.pdf used on input line 25.
+(pdftex.def) Requested size: 116.43292pt x 53.80003pt.
+)
+LaTeX Font Info: Font shape `T1/phv/bx/sc' in size <14.4> not available
+(Font) Font shape `T1/phv/b/sc' tried instead on input line 137.
+LaTeX Font Info: Font shape `T1/phv/bx/n' in size <10> not available
+(Font) Font shape `T1/phv/b/n' tried instead on input line 137.
+LaTeX Font Info: Font shape `T1/phv/bx/n' in size <7> not available
+(Font) Font shape `T1/phv/b/n' tried instead on input line 137.
+
+Overfull \vbox (19.77614pt too high) detected at line 137
+ []
+
+File: logo-FEMTO.jpg Graphic file (type jpg)
+<use logo-FEMTO.jpg>
+Package pdftex.def Info: logo-FEMTO.jpg used on input line 137.
+(pdftex.def) Requested size: 28.45274pt x 11.08414pt.
+File: Hexagones.jpg Graphic file (type jpg)
+ <use Hexagones.jpg>
+Package pdftex.def Info: Hexagones.jpg used on input line 137.
+(pdftex.def) Requested size: 99.58464pt x 53.12378pt.
+ [18
+
+ <../images/Gi.pdf>] (./main.toc)
+File: logo-FEMTO.jpg Graphic file (type jpg)
+
+<use logo-FEMTO.jpg>
+Package pdftex.def Info: logo-FEMTO.jpg used on input line 141.
+(pdftex.def) Requested size: 28.45274pt x 11.08414pt.
+File: Hexagones.jpg Graphic file (type jpg)
+ <use Hexagones.jpg>
+Package pdftex.def Info: Hexagones.jpg used on input line 141.
+(pdftex.def) Requested size: 99.58464pt x 53.12378pt.
+ [19
+
+] (./prngualgo.tex)
File: logo-FEMTO.jpg Graphic file (type jpg)
<use logo-FEMTO.jpg>
+Package pdftex.def Info: logo-FEMTO.jpg used on input line 142.
+(pdftex.def) Requested size: 28.45274pt x 11.08414pt.
+File: Hexagones.jpg Graphic file (type jpg)
+ <use Hexagones.jpg>
+Package pdftex.def Info: Hexagones.jpg used on input line 142.
+(pdftex.def) Requested size: 99.58464pt x 53.12378pt.
+ [20
+
+] (./condunif.tex
+<../images/g.pdf, id=313, 84.315pt x 260.975pt>
+File: ../images/g.pdf Graphic file (type pdf)
+ <use ../images/g.pdf>
+Package pdftex.def Info: ../images/g.pdf used on input line 13.
+(pdftex.def) Requested size: 27.57701pt x 85.35826pt.
+
+Overfull \hbox (6.83594pt too wide) in paragraph at lines 13--14
+[][]
+ []
+
+<../images/h.pdf, id=314, 80.3pt x 260.975pt>
+File: ../images/h.pdf Graphic file (type pdf)
+ <use ../images/h.pdf>
+Package pdftex.def Info: ../images/h.pdf used on input line 35.
+(pdftex.def) Requested size: 26.26381pt x 85.35826pt.
+
+Overfull \hbox (3.21802pt too wide) in paragraph at lines 35--36
+[][]
+ []
+
+)
+File: logo-FEMTO.jpg Graphic file (type jpg)
+ <use logo-FEMTO.jpg>
Package pdftex.def Info: logo-FEMTO.jpg used on input line 143.
(pdftex.def) Requested size: 28.45274pt x 11.08414pt.
File: Hexagones.jpg Graphic file (type jpg)
<use Hexagones.jpg>
Package pdftex.def Info: Hexagones.jpg used on input line 143.
(pdftex.def) Requested size: 99.58464pt x 53.12378pt.
- [17
+ [21
+
+ <../images/g.pdf> <../images/h.pdf>] (./xplprngyestheorieko.tex
+File: ../images/Gi.pdf Graphic file (type pdf)
+ <use ../images/Gi.pdf>
+Package pdftex.def Info: ../images/Gi.pdf used on input line 3.
+(pdftex.def) Requested size: 99.58464pt x 46.01346pt.
+
+Overfull \hbox (41.19882pt too wide) in paragraph at lines 3--4
+[][]
+ []
+
+)
+File: logo-FEMTO.jpg Graphic file (type jpg)
+ <use logo-FEMTO.jpg>
+Package pdftex.def Info: logo-FEMTO.jpg used on input line 144.
+(pdftex.def) Requested size: 28.45274pt x 11.08414pt.
+File: Hexagones.jpg Graphic file (type jpg)
+ <use Hexagones.jpg>
+Package pdftex.def Info: Hexagones.jpg used on input line 144.
+(pdftex.def) Requested size: 99.58464pt x 53.12378pt.
+ [22
+
+] (./prngunauretheorieok.tex
+<../images/h2prng.pdf, id=338, 269.005pt x 378.41376pt>
+File: ../images/h2prng.pdf Graphic file (type pdf)
+
+<use ../images/h2prng.pdf>
+Package pdftex.def Info: ../images/h2prng.pdf used on input line 28.
+(pdftex.def) Requested size: 94.15315pt x 132.4468pt.
+
+Overfull \hbox (1.96526pt too wide) in paragraph at lines 28--29
+ []
+ []
+
+<../images/h3prng.pdf, id=339, 460.72125pt x 378.41376pt>
+File: ../images/h3prng.pdf Graphic file (type pdf)
+
+<use ../images/h3prng.pdf>
+Package pdftex.def Info: ../images/h3prng.pdf used on input line 33.
+(pdftex.def) Requested size: 161.25485pt x 132.4468pt.
+
+Overfull \hbox (38.34079pt too wide) in paragraph at lines 33--34
+ []
+ []
+
+)
+Overfull \vbox (39.68752pt too high) detected at line 147
+ []
+
+File: logo-FEMTO.jpg Graphic file (type jpg)
+<use logo-FEMTO.jpg>
+Package pdftex.def Info: logo-FEMTO.jpg used on input line 147.
+(pdftex.def) Requested size: 28.45274pt x 11.08414pt.
+File: Hexagones.jpg Graphic file (type jpg)
+ <use Hexagones.jpg>
+Package pdftex.def Info: Hexagones.jpg used on input line 147.
+(pdftex.def) Requested size: 99.58464pt x 53.12378pt.
+ [23
+
+ <../images/h2prng.pdf> <../images/h3prng.pdf
+
+pdfTeX warning: pdflatex (file ../images/h3prng.pdf): PDF inclusion: multiple p
+dfs with page group included in a single page
+>] (./hamiltonien1.tex
+<../images/iter_f0c.pdf, id=380, 350.30875pt x 260.975pt>
+File: ../images/iter_f0c.pdf Graphic file (type pdf)
+
+<use ../images/iter_f0c.pdf>
+Package pdftex.def Info: ../images/iter_f0c.pdf used on input line 14.
+(pdftex.def) Requested size: 140.12102pt x 104.38815pt.
+
+Overfull \hbox (6.79517pt too wide) detected at line 33
+\T1/phv/m/sl/8 M \OT1/cmss/m/n/8 = [] []
+ []
+
+)
+Overfull \vbox (5.38306pt too high) detected at line 148
+ []
+
+File: logo-FEMTO.jpg Graphic file (type jpg)
+<use logo-FEMTO.jpg>
+Package pdftex.def Info: logo-FEMTO.jpg used on input line 148.
+(pdftex.def) Requested size: 28.45274pt x 11.08414pt.
+File: Hexagones.jpg Graphic file (type jpg)
+ <use Hexagones.jpg>
+Package pdftex.def Info: Hexagones.jpg used on input line 148.
+(pdftex.def) Requested size: 99.58464pt x 53.12378pt.
+ [24
+
+ <../images/iter_f0c.pdf>]
+(./hamiltonien1.tex <../images/iter_f0d.pdf, id=393, 350.30875pt x 260.975pt>
+File: ../images/iter_f0d.pdf Graphic file (type pdf)
+
+<use ../images/iter_f0d.pdf>
+Package pdftex.def Info: ../images/iter_f0d.pdf used on input line 15.
+(pdftex.def) Requested size: 140.12102pt x 104.38815pt.
+
+Overfull \hbox (6.79517pt too wide) detected at line 33
+\T1/phv/m/sl/8 M \OT1/cmss/m/n/8 = [] []
+ []
+
+)
+Overfull \vbox (5.38306pt too high) detected at line 148
+ []
+
+File: logo-FEMTO.jpg Graphic file (type jpg)
+<use logo-FEMTO.jpg>
+Package pdftex.def Info: logo-FEMTO.jpg used on input line 148.
+(pdftex.def) Requested size: 28.45274pt x 11.08414pt.
+File: Hexagones.jpg Graphic file (type jpg)
+ <use Hexagones.jpg>
+Package pdftex.def Info: Hexagones.jpg used on input line 148.
+(pdftex.def) Requested size: 99.58464pt x 53.12378pt.
+ [25
+
+ <../images/iter_f0d.pdf>]
+(./gray.tex)
+File: logo-FEMTO.jpg Graphic file (type jpg)
+ <use logo-FEMTO.jpg>
+Package pdftex.def Info: logo-FEMTO.jpg used on input line 149.
+(pdftex.def) Requested size: 28.45274pt x 11.08414pt.
+File: Hexagones.jpg Graphic file (type jpg)
+ <use Hexagones.jpg>
+Package pdftex.def Info: Hexagones.jpg used on input line 149.
+(pdftex.def) Requested size: 99.58464pt x 53.12378pt.
+ [26
+
+] (./heam.tex)
+File: logo-FEMTO.jpg Graphic file (type jpg)
+
+<use logo-FEMTO.jpg>
+Package pdftex.def Info: logo-FEMTO.jpg used on input line 150.
+(pdftex.def) Requested size: 28.45274pt x 11.08414pt.
+File: Hexagones.jpg Graphic file (type jpg)
+ <use Hexagones.jpg>
+Package pdftex.def Info: Hexagones.jpg used on input line 150.
+(pdftex.def) Requested size: 99.58464pt x 53.12378pt.
+ [27
+
+] (./prnggeneralise.tex)
+File: logo-FEMTO.jpg Graphic file (type jpg)
+
+<use logo-FEMTO.jpg>
+Package pdftex.def Info: logo-FEMTO.jpg used on input line 151.
+(pdftex.def) Requested size: 28.45274pt x 11.08414pt.
+File: Hexagones.jpg Graphic file (type jpg)
+ <use Hexagones.jpg>
+Package pdftex.def Info: Hexagones.jpg used on input line 151.
+(pdftex.def) Requested size: 99.58464pt x 53.12378pt.
+ [28
+
+] (./prnggeneralise2.tex)
+File: logo-FEMTO.jpg Graphic file (type jpg)
+
+<use logo-FEMTO.jpg>
+Package pdftex.def Info: logo-FEMTO.jpg used on input line 152.
+(pdftex.def) Requested size: 28.45274pt x 11.08414pt.
+File: Hexagones.jpg Graphic file (type jpg)
+ <use Hexagones.jpg>
+Package pdftex.def Info: Hexagones.jpg used on input line 152.
+(pdftex.def) Requested size: 99.58464pt x 53.12378pt.
+ [29
+
+] (./main.toc)
+File: logo-FEMTO.jpg Graphic file (type jpg)
+
+<use logo-FEMTO.jpg>
+Package pdftex.def Info: logo-FEMTO.jpg used on input line 156.
+(pdftex.def) Requested size: 28.45274pt x 11.08414pt.
+File: Hexagones.jpg Graphic file (type jpg)
+ <use Hexagones.jpg>
+Package pdftex.def Info: Hexagones.jpg used on input line 156.
+(pdftex.def) Requested size: 99.58464pt x 53.12378pt.
+ [30
+
+] (./main.toc)
+File: logo-FEMTO.jpg Graphic file (type jpg)
+
+<use logo-FEMTO.jpg>
+Package pdftex.def Info: logo-FEMTO.jpg used on input line 161.
+(pdftex.def) Requested size: 28.45274pt x 11.08414pt.
+File: Hexagones.jpg Graphic file (type jpg)
+ <use Hexagones.jpg>
+Package pdftex.def Info: Hexagones.jpg used on input line 161.
+(pdftex.def) Requested size: 99.58464pt x 53.12378pt.
+ [31
] (./conclusion.tex)
File: logo-FEMTO.jpg Graphic file (type jpg)
<use logo-FEMTO.jpg>
-Package pdftex.def Info: logo-FEMTO.jpg used on input line 144.
+Package pdftex.def Info: logo-FEMTO.jpg used on input line 162.
(pdftex.def) Requested size: 28.45274pt x 11.08414pt.
File: Hexagones.jpg Graphic file (type jpg)
<use Hexagones.jpg>
-Package pdftex.def Info: Hexagones.jpg used on input line 144.
+Package pdftex.def Info: Hexagones.jpg used on input line 162.
(pdftex.def) Requested size: 99.58464pt x 53.12378pt.
- [18
+ [32
] (./main.bbl
LaTeX Font Info: Font shape `T1/phv/m/it' in size <10.95> not available
-(Font) Font shape `T1/phv/m/sl' tried instead on input line 7.
+(Font) Font shape `T1/phv/m/sl' tried instead on input line 8.
Underfull \vbox (badness 10000) has occurred while \output is active []
File: logo-FEMTO.jpg Graphic file (type jpg)
<use logo-FEMTO.jpg>
-Package pdftex.def Info: logo-FEMTO.jpg used on input line 24.
+Package pdftex.def Info: logo-FEMTO.jpg used on input line 25.
(pdftex.def) Requested size: 28.45274pt x 11.08414pt.
File: Hexagones.jpg Graphic file (type jpg)
<use Hexagones.jpg>
-Package pdftex.def Info: Hexagones.jpg used on input line 24.
+Package pdftex.def Info: Hexagones.jpg used on input line 25.
(pdftex.def) Requested size: 99.58464pt x 53.12378pt.
- [19
+ [33
+
+ </usr/share/texlive/texmf-dist/tex/latex/beamer/art/beamericonarticle.pdf>]
+Underfull \vbox (badness 10000) has occurred while \output is active []
+
+File: logo-FEMTO.jpg Graphic file (type jpg)
+
+<use logo-FEMTO.jpg>
+Package pdftex.def Info: logo-FEMTO.jpg used on input line 43.
+(pdftex.def) Requested size: 28.45274pt x 11.08414pt.
+File: Hexagones.jpg Graphic file (type jpg)
+ <use Hexagones.jpg>
+Package pdftex.def Info: Hexagones.jpg used on input line 43.
+(pdftex.def) Requested size: 99.58464pt x 53.12378pt.
+ [34]
+Underfull \vbox (badness 10000) has occurred while \output is active []
- </usr/share/texlive/texmf-dist/tex/latex/beamer/art/beamericonarticle.pdf>])
+File: logo-FEMTO.jpg Graphic file (type jpg)
+
+<use logo-FEMTO.jpg>
+Package pdftex.def Info: logo-FEMTO.jpg used on input line 59.
+(pdftex.def) Requested size: 28.45274pt x 11.08414pt.
+File: Hexagones.jpg Graphic file (type jpg)
+ <use Hexagones.jpg>
+Package pdftex.def Info: Hexagones.jpg used on input line 59.
+(pdftex.def) Requested size: 99.58464pt x 53.12378pt.
+ [35]
+Underfull \vbox (badness 10000) has occurred while \output is active []
+
+File: logo-FEMTO.jpg Graphic file (type jpg)
+
+<use logo-FEMTO.jpg>
+Package pdftex.def Info: logo-FEMTO.jpg used on input line 75.
+(pdftex.def) Requested size: 28.45274pt x 11.08414pt.
+File: Hexagones.jpg Graphic file (type jpg)
+ <use Hexagones.jpg>
+Package pdftex.def Info: Hexagones.jpg used on input line 75.
+(pdftex.def) Requested size: 99.58464pt x 53.12378pt.
+ [36])
File: logo-FEMTO.jpg Graphic file (type jpg)
<use logo-FEMTO.jpg>
-Package pdftex.def Info: logo-FEMTO.jpg used on input line 187.
+Package pdftex.def Info: logo-FEMTO.jpg used on input line 205.
(pdftex.def) Requested size: 28.45274pt x 11.08414pt.
File: Hexagones.jpg Graphic file (type jpg)
<use Hexagones.jpg>
-Package pdftex.def Info: Hexagones.jpg used on input line 187.
+Package pdftex.def Info: Hexagones.jpg used on input line 205.
(pdftex.def) Requested size: 99.58464pt x 53.12378pt.
- [20]
+ [37]
\tf@nav=\write7
\openout7 = `main.nav'.
\tf@snm=\write9
\openout9 = `main.snm'.
-Package atveryend Info: Empty hook `BeforeClearDocument' on input line 187.
-Package atveryend Info: Empty hook `AfterLastShipout' on input line 187.
+Package atveryend Info: Empty hook `BeforeClearDocument' on input line 205.
+Package atveryend Info: Empty hook `AfterLastShipout' on input line 205.
(./main.aux)
-Package atveryend Info: Executing hook `AtVeryEndDocument' on input line 187.
-Package atveryend Info: Executing hook `AtEndAfterFileList' on input line 187.
+Package atveryend Info: Executing hook `AtVeryEndDocument' on input line 205.
+Package atveryend Info: Executing hook `AtEndAfterFileList' on input line 205.
Package rerunfilecheck Info: File `main.out' has not changed.
(rerunfilecheck) Checksum: 42DC76BBFB38CF9DC81B59C3E1BC3FE7;471.
-Package atveryend Info: Empty hook `AtVeryVeryEnd' on input line 187.
+
+
+LaTeX Warning: There were multiply-defined labels.
+
+Package atveryend Info: Empty hook `AtVeryVeryEnd' on input line 205.
)
Here is how much of TeX's memory you used:
- 25971 strings out of 494916
- 485747 string characters out of 6179762
- 570134 words of memory out of 5000000
- 28553 multiletter control sequences out of 15000+600000
- 96440 words of font info for 113 fonts, out of 8000000 for 9000
+ 26154 strings out of 494916
+ 488035 string characters out of 6179762
+ 576534 words of memory out of 5000000
+ 28635 multiletter control sequences out of 15000+600000
+ 139211 words of font info for 132 fonts, out of 8000000 for 9000
14 hyphenation exceptions out of 8191
- 58i,21n,63p,413b,1128s stack positions out of 5000i,500n,10000p,200000b,80000s
-pdfTeX warning (dest): name{beamerbibCou10\\penalty\040\\@M\040\040:ir} has b
-een referenced but does not exist, replaced by a fixed one
-
-pdfTeX warning (dest): name{beamerbibBCVC10\\penalty\040\\@M\040\040:ir} has be
-en referenced but does not exist, replaced by a fixed one
-
-pdfTeX warning (dest): name{sec\\penalty\040\\@M\040\040:ih} has been reference
-d but does not exist, replaced by a fixed one
+ 58i,21n,63p,417b,1128s stack positions out of 5000i,500n,10000p,200000b,80000s
+pdfTeX warning (dest): name{sec\\penalty\040\\@M\040\040:ih} has been referen
+ced but does not exist, replaced by a fixed one
pdfTeX warning (dest): name{sec\\unskip\040\\penalty\040\\@M\040\040:prng} has
been referenced but does not exist, replaced by a fixed one
pdfTeX warning (dest): name{sec\\unskip\040\\penalty\040\\@M\040\040:sdd} has b
een referenced but does not exist, replaced by a fixed one
+pdfTeX warning (dest): name{beamerbibchgw+14\\penalty\040\\@M\040\040:oip} has
+been referenced but does not exist, replaced by a fixed one
+
+pdfTeX warning (dest): name{beamerbibbcgw11\\penalty\040\\@M\040\040:ip} has be
+en referenced but does not exist, replaced by a fixed one
+
+pdfTeX warning (dest): name{beamerbibbcgr11\\penalty\040\\@M\040\040:ip} has be
+en referenced but does not exist, replaced by a fixed one
+
+pdfTeX warning (dest): name{beamerbibbcg11\\penalty\040\\@M\040\040:ij} has bee
+n referenced but does not exist, replaced by a fixed one
+
+pdfTeX warning (dest): name{beamerbibCou10\\penalty\040\\@M\040\040:ir} has bee
+n referenced but does not exist, replaced by a fixed one
+
+pdfTeX warning (dest): name{beamerbibBCVC10\\penalty\040\\@M\040\040:ir} has be
+en referenced but does not exist, replaced by a fixed one
+
{/usr/share/texlive/texmf-dist/fonts/enc/dvips/base/8r.enc}</usr/share/texlive/
texmf-dist/fonts/type1/public/amsfonts/cmextra/cmex8.pfb></usr/share/texlive/te
xmf-dist/fonts/type1/public/amsfonts/cm/cmmi12.pfb></usr/share/texlive/texmf-di
/cmsy6.pfb></usr/share/texlive/texmf-dist/fonts/type1/public/amsfonts/cm/cmsy8.
pfb></usr/share/texlive/texmf-dist/fonts/type1/public/doublestroke/dsrom8.pfb><
/usr/share/texlive/texmf-dist/fonts/type1/public/amsfonts/symbols/msam10.pfb></
-usr/share/texlive/texmf-dist/fonts/type1/public/amsfonts/symbols/msbm7.pfb></us
-r/share/texlive/texmf-dist/fonts/type1/urw/courier/ucrr8a.pfb></usr/share/texli
-ve/texmf-dist/fonts/type1/urw/helvetic/uhvb8a.pfb></usr/share/texlive/texmf-dis
-t/fonts/type1/urw/helvetic/uhvr8a.pfb></usr/share/texlive/texmf-dist/fonts/type
-1/urw/helvetic/uhvro8a.pfb></usr/share/texlive/texmf-dist/fonts/type1/urw/times
-/utmr8a.pfb>
-Output written on main.pdf (20 pages, 451909 bytes).
+usr/share/texlive/texmf-dist/fonts/type1/public/amsfonts/symbols/msbm10.pfb></u
+sr/share/texlive/texmf-dist/fonts/type1/public/amsfonts/symbols/msbm7.pfb></usr
+/share/texlive/texmf-dist/fonts/type1/public/stmaryrd/stmary8.pfb></usr/share/t
+exlive/texmf-dist/fonts/type1/urw/courier/ucrr8a.pfb></usr/share/texlive/texmf-
+dist/fonts/type1/urw/helvetic/uhvb8a.pfb></usr/share/texlive/texmf-dist/fonts/t
+ype1/urw/helvetic/uhvr8a.pfb></usr/share/texlive/texmf-dist/fonts/type1/urw/hel
+vetic/uhvro8a.pfb></usr/share/texlive/texmf-dist/fonts/type1/urw/times/utmr8a.p
+fb></usr/share/texlive/texmf-dist/fonts/type1/urw/times/utmri8a.pfb>
+Output written on main.pdf (37 pages, 522078 bytes).
PDF statistics:
- 396 PDF objects out of 1000 (max. 8388607)
- 307 compressed objects within 4 object streams
- 67 named destinations out of 1000 (max. 500000)
- 198 words of extra memory for PDF output out of 10000 (max. 10000000)
+ 598 PDF objects out of 1000 (max. 8388607)
+ 465 compressed objects within 5 object streams
+ 114 named destinations out of 1000 (max. 500000)
+ 227 words of extra memory for PDF output out of 10000 (max. 10000000)
\headcommand {\beamer@subsectionpages {9}{13}}
\headcommand {\slideentry {3}{0}{1}{14/14}{}{0}}
\headcommand {\beamer@framepages {14}{14}}
-\headcommand {\sectionentry {4}{Applications \IeC {\`a} la g\IeC {\'e}n\IeC {\'e}ration de nombres pseudo-al\IeC {\'e}atoires}{15}{Applications \IeC {\`a} la g\IeC {\'e}n\IeC {\'e}ration de nombres pseudo-al\IeC {\'e}atoires}{0}}
-\headcommand {\beamer@sectionpages {14}{14}}
-\headcommand {\beamer@subsectionpages {14}{14}}
-\headcommand {\slideentry {4}{0}{1}{15/15}{}{0}}
+\headcommand {\slideentry {3}{0}{2}{15/15}{}{0}}
\headcommand {\beamer@framepages {15}{15}}
-\headcommand {\sectionentry {5}{Application au masquage d'information}{16}{Application au masquage d'information}{0}}
-\headcommand {\beamer@sectionpages {15}{15}}
-\headcommand {\beamer@subsectionpages {15}{15}}
-\headcommand {\slideentry {5}{0}{1}{16/16}{}{0}}
+\headcommand {\slideentry {3}{0}{3}{16/16}{}{0}}
\headcommand {\beamer@framepages {16}{16}}
-\headcommand {\sectionentry {6}{Conclusion}{17}{Conclusion}{0}}
-\headcommand {\beamer@sectionpages {16}{16}}
-\headcommand {\beamer@subsectionpages {16}{16}}
-\headcommand {\slideentry {6}{0}{1}{17/17}{}{0}}
+\headcommand {\slideentry {3}{0}{4}{17/17}{}{0}}
\headcommand {\beamer@framepages {17}{17}}
-\headcommand {\slideentry {6}{0}{2}{18/18}{}{0}}
+\headcommand {\slideentry {3}{0}{5}{18/18}{}{0}}
\headcommand {\beamer@framepages {18}{18}}
-\headcommand {\beamer@partpages {1}{20}}
-\headcommand {\beamer@subsectionpages {17}{20}}
-\headcommand {\beamer@sectionpages {17}{20}}
-\headcommand {\beamer@documentpages {20}}
-\headcommand {\def \inserttotalframenumber {18}}
+\headcommand {\sectionentry {4}{Applications \IeC {\`a} la g\IeC {\'e}n\IeC {\'e}ration de nombres pseudo-al\IeC {\'e}atoires}{19}{Applications \IeC {\`a} la g\IeC {\'e}n\IeC {\'e}ration de nombres pseudo-al\IeC {\'e}atoires}{0}}
+\headcommand {\beamer@sectionpages {14}{18}}
+\headcommand {\beamer@subsectionpages {14}{18}}
+\headcommand {\slideentry {4}{0}{1}{19/19}{}{0}}
+\headcommand {\beamer@framepages {19}{19}}
+\headcommand {\slideentry {4}{0}{2}{20/20}{}{0}}
+\headcommand {\beamer@framepages {20}{20}}
+\headcommand {\slideentry {4}{0}{3}{21/21}{}{0}}
+\headcommand {\beamer@framepages {21}{21}}
+\headcommand {\slideentry {4}{0}{4}{22/22}{}{0}}
+\headcommand {\beamer@framepages {22}{22}}
+\headcommand {\slideentry {4}{0}{5}{23/23}{}{0}}
+\headcommand {\beamer@framepages {23}{23}}
+\headcommand {\slideentry {4}{0}{6}{24/25}{}{0}}
+\headcommand {\beamer@framepages {24}{25}}
+\headcommand {\slideentry {4}{0}{7}{26/26}{}{0}}
+\headcommand {\beamer@framepages {26}{26}}
+\headcommand {\slideentry {4}{0}{8}{27/27}{}{0}}
+\headcommand {\beamer@framepages {27}{27}}
+\headcommand {\slideentry {4}{0}{9}{28/28}{}{0}}
+\headcommand {\beamer@framepages {28}{28}}
+\headcommand {\slideentry {4}{0}{10}{29/29}{}{0}}
+\headcommand {\beamer@framepages {29}{29}}
+\headcommand {\sectionentry {5}{Application au masquage d'information}{30}{Application au masquage d'information}{0}}
+\headcommand {\beamer@sectionpages {19}{29}}
+\headcommand {\beamer@subsectionpages {19}{29}}
+\headcommand {\slideentry {5}{0}{1}{30/30}{}{0}}
+\headcommand {\beamer@framepages {30}{30}}
+\headcommand {\sectionentry {6}{Conclusion}{31}{Conclusion}{0}}
+\headcommand {\beamer@sectionpages {30}{30}}
+\headcommand {\beamer@subsectionpages {30}{30}}
+\headcommand {\slideentry {6}{0}{1}{31/31}{}{0}}
+\headcommand {\beamer@framepages {31}{31}}
+\headcommand {\slideentry {6}{0}{2}{32/32}{}{0}}
+\headcommand {\beamer@framepages {32}{32}}
+\headcommand {\beamer@partpages {1}{37}}
+\headcommand {\beamer@subsectionpages {31}{37}}
+\headcommand {\beamer@sectionpages {31}{37}}
+\headcommand {\beamer@documentpages {37}}
+\headcommand {\def \inserttotalframenumber {31}}
\beamer@slide {fig:fgigb}{4}
\beamer@slide {sec:sdd}{9}
\beamer@slide {sec:sddchaos}{14}
-\beamer@slide {sec:prng}{15}
-\beamer@slide {sec:ih}{16}
+\beamer@slide {Th:CaracIC}{16}
+\beamer@slide {Th:CaracIC}{17}
+\beamer@slide {th:Adrien}{18}
+\beamer@slide {sec:prng}{19}
+\beamer@slide {sec:ih}{30}
\inputFrameb{Dépendance entre éléments}{jacobienne}
\inputFrameb{Mode asynchrone}{asynchrone}
\inputFrameb{Un exemple motivant}{xplsddasync}
-\inputFrameb{Problématique}{sddproblematique}
+%\inputFrameb{Problématique}{sddproblematique}
+\frame{\frametitle{Plan}\tableofcontents[hideallsubsections]}
\section{Réseaux booléens: des preuves de convergences}\label{sec:sdd}
\frame{\frametitle{Plan}\tableofcontents[currentsection]}
-\inputFrameb{Un peu de Synchronisme}{synchronisons}
+\inputFrameb{Suffisamment de synchronisme}{synchronisons}
\inputFrameb{Mode mixte avec $g$}{mixteexample}
\inputFrameb{Convergence par la pratique}{preuveconvmotiv}
\inputFrameb{Du système booléen au modèle PROMELA}{sdd2promela}
+
\section{Des systèmes dynamiques discrets au chaos}\label{sec:sddchaos}
\frame{\frametitle{Plan}\tableofcontents[currentsection]}
+\inputFrameb{Rappels sur les itérations chaotiques}{chaosDevaney}
+\inputFrameb{Espace pour itérations chaotiques (unaires)}{chaosDevaneyUnaire}
+\inputFrameb{Espace pour itérations chaotiques (généralisées)}{chaosDevaneyGeneralisees}
+\inputFrameb{Générer un graphe ${\textsc{giu}}$ fortement connexe}{tipe12}
\section{Applications à la génération de nombres pseudo-aléatoires}\label{sec:prng}
\frame{\frametitle{Plan}\tableofcontents[currentsection]}
+\inputFrameb{PRNG par itérations unaires}{prngualgo}
+\inputFrameb{Condition néc. suff. pour l'uniformité}{condunif}
+\inputFrameb{Succès pratiques et limites théoriques}{xplprngyestheorieko}
+\inputFrameb{Espace pour itérations chaotiques ($b$)}{prngunauretheorieok}
+\inputFrameb{$\textsc{giu}$ fortement connexe par construction}{hamiltonien1}
+\inputFrameb{Codes de Gray équilibrés}{gray}
+\inputFrameb{Evaluation de l'écart / ditribution uniforme}{heam}
+\inputFrameb{Et les itérations généralisées?}{prnggeneralise}
+\inputFrameb{Analyse pratique des deux classes de PRNGS}{prnggeneralise2}
\section{Application au masquage d'information}\label{sec:ih}
\frame{\frametitle{Plan}\tableofcontents[currentsection]}
+%\inputFrameb{Marquer un média: un processsus chaotique}{marquage}
+
\section{Conclusion}
\frame{\frametitle{Plan}\tableofcontents[currentsection]}
\beamer@sectionintoc {1}{Introduction: iterations de r\IeC {\'e}seaux bool\IeC {\'e}ens}{2}{0}{1}
\beamer@sectionintoc {2}{R\IeC {\'e}seaux bool\IeC {\'e}ens: des preuves de convergences}{9}{0}{2}
\beamer@sectionintoc {3}{Des syst\IeC {\`e}mes dynamiques discrets au chaos}{14}{0}{3}
-\beamer@sectionintoc {4}{Applications \IeC {\`a} la g\IeC {\'e}n\IeC {\'e}ration de nombres pseudo-al\IeC {\'e}atoires}{15}{0}{4}
-\beamer@sectionintoc {5}{Application au masquage d'information}{16}{0}{5}
-\beamer@sectionintoc {6}{Conclusion}{17}{0}{6}
+\beamer@sectionintoc {4}{Applications \IeC {\`a} la g\IeC {\'e}n\IeC {\'e}ration de nombres pseudo-al\IeC {\'e}atoires}{19}{0}{4}
+\beamer@sectionintoc {5}{Application au masquage d'information}{30}{0}{5}
+\beamer@sectionintoc {6}{Conclusion}{31}{0}{6}
-\begin{exampleblock}{}
+\begin{block}{}
\begin{figure}
\subfloat[Parallèle synchrone]{
\includegraphics[scale=0.2]{../images/eval_sync}
\class{4} $=\{4,5\}$.]{
\includegraphics[scale=0.2]{../images/eval_mixte}
}
-\caption{Graphes des itérations de $g$}
+%\caption{Graphes des itérations de $g$}
\end{figure}
-\end{exampleblock}
+\end{block}
\begin{itemize}
\item Conditions suffisantes de convergence: facile à appliquer,
- domaine restreint
-\item Recherche d'une métrique decroissante minorée: difficile
+ domaine restreint.
+\item Recherche d'une métrique decroissante minorée: difficile.
\item Simulations:
\begin{itemize}
\item Non exhaustives pour les schémas généralisés et asynchrones.
\item Verdict $\leftrightarrow$ vérité ssi divergence (contre-exemple).
\end{itemize}
-\item Souhait: exploiter un outil qui traiterait toutes les transitions
+\item Souhait: exploiter un outil qui traiterait toutes les transitions.
\begin{itemize}
-\item explosion combinatoire: par abstraction,
+\item Explosion combinatoire: par abstraction,
quotientage, ordre partiel\ldots
\item Model checker: SPIN~\cite{Hol03}.
\item Correction et complétude de la démarche.
--- /dev/null
+\begin{block}{}
+ \begin{algorithm}[H]
+\KwIn{une fonction $f$, un nombre d'itérations $b$,
+une configuration initiale $x^0$ (${\mathsf{N}}$ bits)}
+\KwOut{une configuration $x$ (${\mathsf{N}}$ bits)}
+$x\leftarrow x^0$\;
+$k\leftarrow b $\;
+\For{$i=1,\dots,k$}
+{
+$s\leftarrow{\textit{Set}(\textit{Random}(2^{\mathsf{N}}))}$\;
+$x\leftarrow{F_{f_g}(x,s)}$\;
+}
+return $x$\;
+\end{algorithm}
+\end{block}
+
+\begin{theorem}[Uniformité de la sortie ds le cas généralisé]
+ Soit $f: \Bool^{{\mathsf{N}}} \rightarrow \Bool^{{\mathsf{N}}}$ et
+ $\check{M}$ sa matrice d'adjacence.
+ Si $\textsc{gig}(f)$ est fortement connexe, alors
+ la sortie du PRNG suit une loi qui
+ tend vers la distribution uniforme si
+ et ssi $\dfrac{1}{2^{\mathsf{N}}} \check{M}
+$ est une matrice doublement stochastique.
+\end{theorem}
+
--- /dev/null
+\begin{block}{Nombre moyen d'appels à un générateur binaire par bit généré}
+$$
+\begin{array}{|l|l|l|l|l|l|}
+\hline
+\textrm{Itérations} & 4 & 5 & 6 & 7 & 8 \\
+\hline
+\textrm{Unaires} & 19.0 & 22.3 & 23.7 & 25.3 & 27.0\\
+\hline
+\textrm{Généralisées} & 17 & 13 & 11 & 10 & 9\\
+\hline
+\end{array}
+$$
+\end{block}
+
+
+\begin{itemize}
+\item Fréqence des configurations non accessibles en 1 itération:
+ \begin{itemize}
+\item Unaire: $1-\dfrac{n-1}{2^n}$ (croissant).
+\item généralisée: $1/2$ (constant), mais décroissance de la fréquence des
+ bits constants.
+\end{itemize}
+\item Test de NIST: succès dans tous les cas.
+\end{itemize}
+
--- /dev/null
+\begin{block}{Algorithme~\cite{bcgw11:ip}}
+\begin{algorithm}[H]
+%\begin{scriptsize}
+\KwIn{une fonction $f$, un nombre d'itérations $b$,
+une configuration initiale $x^0$ (${\mathsf{N}}$ bits)}
+\KwOut{une configuration $x$ (${\mathsf{N}}$ bits)}
+$x\leftarrow x^0$\;
+%$k\leftarrow b + \textit{XORshift}(b+1)$\;
+\For{$i=1,\dots,b$}
+{
+$s\leftarrow{\textit{Random}({\mathsf{N}})}$\;
+%$s\leftarrow{\textit{XORshift}(n)}$\;
+$x\leftarrow{F_{f_u}(x,s)}$\;
+}
+return $x$\;
+%\end{scriptsize}
+%\caption{PRNG basé sur les itérations unaires.}
+%\label{CI Algorithm}
+\end{algorithm}
+\end{block}
+
+\begin{itemize}
+\item \textit{Random}: un PRNG ($\mathsf{N}$ bits).
+\item Remarques:
+\begin{itemize}
+\item $b=1$ $\leadsto$ itérations (chaotiques) de $F_{f_u}$
+\item Quid de l'uniformité de la sortie?
+\end{itemize}
+\end{itemize}
--- /dev/null
+\begin{itemize}
+\item Vers une fonction de
+$\mathcal{X}_u =\Bool^{\mathsf{N}} \times \llbracket1;{\mathsf{N}}\rrbracket^\Nats$
+dans lui même~\cite{ccgh16}:
+\begin{itemize}
+\item $F_{f_u}: \Bool^{\mathsf{N}} \times \llbracket1;{\mathsf{N}}\rrbracket \rightarrow \Bool^{\mathsf{N}}$,
+$(x,i) \mapsto (x_1,\dots,x_{i-1},f_i(x),x_{i+1},\dots,x_{\mathsf{N}})$
+\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}$
+\item $G_{{f_u},b}$ définie par
+ $G_{{f_u},b}(x,s)=(F_{f_u}( \dots(F_{f_u}(x,s_0),\dots),s_{b-1}),\sigma^b(s))$
+\end{itemize}
+
+\item Distance $d((x,s),(x',s'))= d_H(x,x')+d''_S(s,s')$
+\end{itemize}
+
+\begin{theorem}[Fonctions t.q. $G_{{f_u},b}$ est chaotique~\cite{ccgh16}]
+La fonction $G_{f_u,b}$ est chaotique sur
+ $(\mathcal{X}_u,d)$ si et seulement si
+le graphe d'itérations $\textsc{giu}_{b}(f)$
+est fortement connexe.
+\end{theorem}
+
+
+\vspace{-4.5em}
+\begin{center}
+\begin{minipage}{0.30\textwidth}
+ \begin{center}
+ \includegraphics[scale=0.35]{../images/h2prng}
+ \end{center}
+\end{minipage}
+\begin{minipage}{0.40\textwidth}
+ \begin{center}
+ \includegraphics[scale=0.35]{../images/h3prng}
+ \end{center}
+\end{minipage}
+\end{center}
+
+
+
+% \begin{itemize}
+% \item Vers une fonction de
+% $\mathcal{X}_u$ dans lui même:
+% \begin{itemize}
+% \item
+% $F_{{f_u},b} : \mathds{B}^\mathsf{N} \times [\mathsf{N}]^{b}
+% \rightarrow \mathds{B}^\mathsf{N}$ définie par
+% $
+% F_{f_u,b} (x,(u^1, \hdots, u^{b})) =
+% F_{f_u}(\hdots (F_{f_u}(x,u^1), \hdots), u^{b}).
+% $
+
+
+
+% \item $\sigma:
+% \left(\mathcal{P}(\llbracket 1;{\mathsf{N}}\rrbracket)\right)^{\Nats}
+% \rightarrow
+% \left(\mathcal{P}(\llbracket 1;{\mathsf{N}}\rrbracket)\right)^{\Nats}$
+% t.q. $\forall t\in\Nats,\sigma(s)_t=s_{t+1}$
+% \item $G_{f_g}$ définie par
+% \[
+% G_{f_g}(x,S)=(F_{f_g}(x,s_0),\sigma(S)),
+% \]
+
+% \end{itemize}
+
+% \item Distance $d$: $d((x,s),(x',s'))= d_H(x,x')+d'_S(s,s')$
+% \end{itemize}
+
+% \begin{theorem}[Fonctions t.q. $G_{f_g}$ est chaotique]
+% \label{Th:CaracIC}
+% Soit $f:\Bool^{\mathsf{N}}\to\Bool^{\mathsf{N}}$.
+% Les itérations de la fonction $G_{f_g}$ sont chaotiques
+% si et seulement si $\textsc{gig}(f)$ est fortement connexe.
+% \end{theorem}
\item \emph{Parallèle synchrone:}
$x^{t+1}=f(x^t)$.
\item \emph{Unaire:} à partir de la \emph{stratégie unaire}
- $S = \left(s^t\right)^{t \in \mathds{N}}$,
+ $\left(s^t\right)^{t \in \mathds{N}} \in [\mathsf{N}]^{\Nats}$,
modification de l'élément $s^t$ de $x^t$
$$
\begin{array}{l}
$$
\item \emph{Généralisé:} à partir de la \emph{stratégie généralisée}
- $\left(s^t\right)^{t \in \mathds{N}}$,
- à chaque itération $t$,
- modification des éléments de $x^t$ dans $s^t\subset\{1,\ldots,n\}$
+ $\left(s^t\right)^{t \in \mathds{N}} \in \mathcal{P}([\mathsf{N}])^{\Nats} $,
+% à chaque itération $t$,
+ modification des éléments de $x^t$ dans $s^t\subset [\mathsf{N}]$
$$
\begin{array}{l}
x^{t+1}= (x^{t+1}_1,\dots,x^{t+1}_n) \textrm{ où }
\begin{itemize}
\item Stratégie: pseudo périodicité garantie par le choix indéterministe de
SPIN.
-\item Délais(bornés par construction): oubli de certaines valeurs grâce à l'indéterminisme de SPIN.
+\item Délais (bornés par construction): oubli de certaines valeurs grâce à l'indéterminisme de SPIN.
\end{itemize}
\item Convergence universelle: $\diamond (\Box \verb+Xp+ = \verb+X+)$.
-\end{itemize}
+
\begin{theorem}[Correction et complétude de la traduction vers Promela~\cite{Cou10:ir}]
Soit $\phi$ un modèle de système dynamique discret et $\psi$ sa traduction PROMELA.
$\psi$ vérifie
la propriété LTL sous hypothèse d'équité faible.
\end{theorem}
+
+% \item Equité faible grantie uniquement entre processus:
+% \begin{itemize}
+% \item L'imposer pour chaque choix où
+% \item Filtrer les traces non équitables retournée.
+% \end{itemize}
+\item Bilan:
+\begin{itemize}
+\item Preuve automatique de convergence de modèles indpt. schéma/mode.
+\item A pu décider de la convergence d'exemples simples.
+\item Ne passe pas à l'échelle.
+\end{itemize}
+\end{itemize}
\item Caractérisation d'un PRNG chaotique.
\item Générations et qualité.
\end{itemize}
-\item Du Chaos au masquage d'information (Sec.\ref{sec:ih}).
+\item Du Chaos au masquage d'information (Sec.~\ref{sec:ih}).
\begin{itemize}
\item D'un point de vue chaotique.
\item D'un point de vue analyse vectorielle discrète.
--- /dev/null
+\begin{itemize}
+\item Méthode naïve:
+ suppressions successives aléatoires d'arcs de
+ $\textsc{giu}(\neg)$.
+\item $\leadsto$ Vérification portant sur le graphe des iterations.
+
+\item Souhait: cond. suffisantes sur le graphe d'interactions.
+\begin{theorem}[Fonctions avec $\textsc{giu}$ fort. connexe~\cite{bcgr11:ip}]
+\label{th:Adrien}
+Soit $f$ une fonction de $\Bool^{\mathsf{N}}$ vers lui-même telle que $\Gamma(f)$:
+\begin{enumerate}
+\item
+ N'a pas de cycle de longueur supérieure ou égale à deux.
+\item
+ Chacun des sommets avec une boucle + a aussi une boucle -.
+\item
+Chacun des sommets est accessible depuis un sommet avec une boucle -.
+\end{enumerate}
+Alors, $\textsc{giu}(f)$ est fortement connexe.
+\end{theorem}
+\end{itemize}
+
+\begin{center}
+ \begin{minipage}{0.4\textwidth}
+ \includegraphics[scale=0.4]{../images/Gi.pdf}
+ \end{minipage}
+ \begin{minipage}{0.45\textwidth}
+ $\leadsto
+ \left \{
+ \begin{array}{l}
+ \textrm{ 34226 fonctions} \\
+ \textrm{ 520 non isomorphes}
+ \end{array}
+ \right.
+ $
+ \end{minipage}
+\end{center}
--- /dev/null
+\begin{block}{}
+\begin{minipage}{0.19\textwidth}
+ \includegraphics[width=3.5cm]{../images/Gi.pdf}
+\end{minipage}
+\begin{minipage}{0.8\textwidth}
+\begin{itemize}
+\item Seules 16 vérifient les hypothèses du théorème précédent.
+\item $b$: nombre d'itérations suffisant pour une déviation p.r. la distribution uniforme inf. à $10^{-4}$.
+
+\begin{center}
+ \begin{tiny}
+ \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
+ $\vdots$ & $\vdots$ & $\vdots$ \\
+ \hline
+ $\mathcal{F}_9$ &14, 15, 12, 13, 10, 11, 9, 8, 7, 6, 5, 4, 3, 2, 0, 1
+ & 42 \\
+ \hline
+ $\vdots$ & $\vdots$ & $\vdots$ \\
+ \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{tiny}
+\end{center}
+\item Succès de tous les PRNGs issus de ces fonctions
+aux tests du \emph{National Institute of Standards and Technology} (NIST).
+\end{itemize}
+\end{minipage}
+\end{block}
+\begin{itemize}
+\item Erreur de raisonnement:
+\begin{itemize}
+\item Générateur prouvé chaotique seulement pour $b=1$.
+\item Pas compatible avec la pratique: $b \geq 42$ nécessaire
+ pour suivre une loi uniforme (à $10^{-4}$ près).
+\item $\leadsto$ Etendre la théorie.
+\end{itemize}
+\end{itemize}
-\begin{exampleblock}{ $g(x_1,x_2,x_3,x_4,x_5) =
+\begin{block}{ $g(x_1,x_2,x_3,x_4,x_5) =
(x_1.\overline{x_2} + \overline{x_1}.x_2,\overline{x_1 + x_2}, x_3.\overline{x_1}, x_5, \overline{x_3} + x_4)$}
\begin{figure}
\centering
\caption{Graphes des itérations synchrones}
\begin{itemize}
\item Avec $D^t = t$ sauf $D^t_{12} = t-1$ pour $t$ impair,
- $g$ oscille entre $(0,0,0,1,1)$ et $(0,1,0,1,1)$
- \item Schéma parallèle: converge en synchrone, diverge en asynchrone
+ $g$ oscille entre $3$ et $11$.
+ \item $\leadsto$ Schéma parallèle: converge en synchrone, diverge en asynchrone
\end{itemize}
\end{figure}
-\end{exampleblock}
+\end{block}
