From: couchot Date: Mon, 9 Jan 2017 13:39:14 +0000 (+0100) Subject: une version de plus X-Git-Url: https://bilbo.iut-bm.univ-fcomte.fr/and/gitweb/hdrcouchot.git/commitdiff_plain/44a56c5eb4a1dfdf7dc67735c5c00f478cef2ede?ds=inline une version de plus --- diff --git a/14Secrypt.tex b/14Secrypt.tex index 84b5302..b499f1b 100644 --- a/14Secrypt.tex +++ b/14Secrypt.tex @@ -566,7 +566,10 @@ p(e) \left\{ 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} @@ -853,8 +856,8 @@ l'on marche. 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; diff --git a/15RairoGen.tex b/15RairoGen.tex index c1cf7d3..6832d33 100644 --- a/15RairoGen.tex +++ b/15RairoGen.tex @@ -31,8 +31,9 @@ Réduire ces critiques est l'objectif de nombreux travaux de recherche reportés 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[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} + + diff --git a/talk/heam.tex b/talk/heam.tex new file mode 100644 index 0000000..451b6ac --- /dev/null +++ b/talk/heam.tex @@ -0,0 +1,37 @@ + +\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} diff --git a/talk/jacobienne.tex b/talk/jacobienne.tex index b76dbc7..144bfdc 100644 --- a/talk/jacobienne.tex +++ b/talk/jacobienne.tex @@ -3,14 +3,14 @@ $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, @@ -50,4 +50,4 @@ f' = \left( \begin{minipage}{0.2\textwidth} \includegraphics[scale=0.4]{gf} \end{minipage} -\end{exampleblock} +\end{block} diff --git a/talk/main-nup.pdf b/talk/main-nup.pdf index 091dd3b..ae74de8 100644 Binary files a/talk/main-nup.pdf and b/talk/main-nup.pdf differ diff --git a/talk/main.aux b/talk/main.aux index 891b673..2409d8b 100644 --- a/talk/main.aux +++ b/talk/main.aux @@ -93,38 +93,89 @@ \@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}}} diff --git a/talk/main.bbl b/talk/main.bbl index 0765a59..ef7c33d 100644 --- a/talk/main.bbl +++ b/talk/main.bbl @@ -1,4 +1,5 @@ -\begin{thebibliography}{ABCVS05} +\newcommand{\etalchar}[1]{$^{#1}$} +\begin{thebibliography}{CCVHG16} \bibitem[ABCVS05]{abcvs05} A.~Abbas, J.~M. Bahi, S.~Contassot-Vivier, and M.~Salomon. @@ -8,6 +9,25 @@ 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 @@ -15,15 +35,49 @@ J.~M. Bahi, S.~Contassot-Vivier, and J.-F. Couchot. \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} diff --git a/talk/main.blg b/talk/main.blg index cca2e0e..efed21f 100644 --- a/talk/main.blg +++ b/talk/main.blg @@ -4,44 +4,44 @@ The top-level auxiliary file: main.aux 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 diff --git a/talk/main.log b/talk/main.log index d7c0659..b989fad 100644 --- a/talk/main.log +++ b/talk/main.log @@ -1,8 +1,8 @@ -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. @@ -1304,7 +1304,11 @@ File: lstmisc.sty 2015/06/04 1.6 (Carsten Heinz) 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. @@ -1322,8 +1326,7 @@ LaTeX Font Info: ... okay 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 @@ -1751,104 +1754,100 @@ Package pdftex.def Info: Hexagones.jpg used on input line 118. (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) -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) - - -Package pdftex.def Info: Hexagones.jpg used on input line 119. + +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) -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) -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) - -Package pdftex.def Info: logo-FEMTO.jpg used on input line 123. + +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) -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) 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) 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) 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) - -Package pdftex.def Info: logo-FEMTO.jpg used on input line 124. + +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) -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) - - -Package pdftex.def Info: logo-FEMTO.jpg used on input line 125. + +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) -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) -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) -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 @@ -1856,90 +1855,409 @@ Package pdftex.def Info: Hexagones.jpg used on input line 126. File: logo-FEMTO.jpg Graphic file (type 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) -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) -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) -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) -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) -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 + + \relax +l.32 \label{Th:CaracIC} + ) +File: logo-FEMTO.jpg Graphic file (type 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) + +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) + + +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) + +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) + +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) + + +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) + +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) +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) + +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) + +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) + +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) + 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) 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) + +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) + +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) + +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) + + +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) + + +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) + +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) + +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) + + +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) + +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) + +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) + + +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) + +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) + +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) + +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) + +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) + + +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) + +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) + + +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) + +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) + + +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) + +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) + + +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) + +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) + + +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) + +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) -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) -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) -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) -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 + + ] +Underfull \vbox (badness 10000) has occurred while \output is active [] + +File: logo-FEMTO.jpg Graphic file (type 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) + +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 [] - ]) +File: logo-FEMTO.jpg Graphic file (type 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) + +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) + + +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) + +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) -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) -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'. @@ -1949,31 +2267,29 @@ Package pdftex.def Info: Hexagones.jpg used on input line 187. \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 @@ -1984,6 +2300,24 @@ 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/symbols/msam10.pfb> -Output written on main.pdf (20 pages, 451909 bytes). +usr/share/texlive/texmf-dist/fonts/type1/public/amsfonts/symbols/msbm10.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) diff --git a/talk/main.nav b/talk/main.nav index 3f00c15..6b8ec85 100644 --- a/talk/main.nav +++ b/talk/main.nav @@ -36,25 +36,51 @@ \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}} diff --git a/talk/main.pdf b/talk/main.pdf index 699e511..48e175b 100644 Binary files a/talk/main.pdf and b/talk/main.pdf differ diff --git a/talk/main.snm b/talk/main.snm index 014cdff..6dd371c 100644 --- a/talk/main.snm +++ b/talk/main.snm @@ -6,5 +6,8 @@ \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} diff --git a/talk/main.tex b/talk/main.tex index 66ed27c..b6a1a15 100644 --- a/talk/main.tex +++ b/talk/main.tex @@ -116,28 +116,45 @@ \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]} diff --git a/talk/main.toc b/talk/main.toc index fbd10b8..8766313 100644 --- a/talk/main.toc +++ b/talk/main.toc @@ -3,6 +3,6 @@ \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} diff --git a/talk/mixteexample.tex b/talk/mixteexample.tex index 0617945..b240c40 100644 --- a/talk/mixteexample.tex +++ b/talk/mixteexample.tex @@ -1,4 +1,4 @@ -\begin{exampleblock}{} +\begin{block}{} \begin{figure} \subfloat[Parallèle synchrone]{ \includegraphics[scale=0.2]{../images/eval_sync} @@ -14,6 +14,6 @@ \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} diff --git a/talk/preuveconvmotiv.tex b/talk/preuveconvmotiv.tex index b3e38d4..f6540e9 100644 --- a/talk/preuveconvmotiv.tex +++ b/talk/preuveconvmotiv.tex @@ -1,16 +1,16 @@ \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. diff --git a/talk/prnggeneralise.tex b/talk/prnggeneralise.tex new file mode 100644 index 0000000..49152b8 --- /dev/null +++ b/talk/prnggeneralise.tex @@ -0,0 +1,26 @@ +\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} + diff --git a/talk/prnggeneralise2.tex b/talk/prnggeneralise2.tex new file mode 100644 index 0000000..9a900d9 --- /dev/null +++ b/talk/prnggeneralise2.tex @@ -0,0 +1,25 @@ +\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} + diff --git a/talk/prngualgo.tex b/talk/prngualgo.tex new file mode 100644 index 0000000..3111738 --- /dev/null +++ b/talk/prngualgo.tex @@ -0,0 +1,29 @@ +\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} diff --git a/talk/prngunauretheorieok.tex b/talk/prngunauretheorieok.tex new file mode 100644 index 0000000..38ec70d --- /dev/null +++ b/talk/prngunauretheorieok.tex @@ -0,0 +1,74 @@ +\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} diff --git a/talk/rb.tex b/talk/rb.tex index ad0d751..2a6c33d 100644 --- a/talk/rb.tex +++ b/talk/rb.tex @@ -9,7 +9,7 @@ $ \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} @@ -25,9 +25,9 @@ $ $$ \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ù } diff --git a/talk/sdd2promela.tex b/talk/sdd2promela.tex index 4676dfa..9389fc3 100644 --- a/talk/sdd2promela.tex +++ b/talk/sdd2promela.tex @@ -3,10 +3,10 @@ \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. @@ -15,3 +15,16 @@ $\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} diff --git a/talk/sddproblematique.tex b/talk/sddproblematique.tex index 960b079..c317a97 100644 --- a/talk/sddproblematique.tex +++ b/talk/sddproblematique.tex @@ -15,7 +15,7 @@ \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. diff --git a/talk/tipe12.tex b/talk/tipe12.tex new file mode 100644 index 0000000..0747529 --- /dev/null +++ b/talk/tipe12.tex @@ -0,0 +1,37 @@ +\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} diff --git a/talk/xplprngyestheorieko.tex b/talk/xplprngyestheorieko.tex new file mode 100644 index 0000000..64ca989 --- /dev/null +++ b/talk/xplprngyestheorieko.tex @@ -0,0 +1,44 @@ +\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} diff --git a/talk/xplsddasync.tex b/talk/xplsddasync.tex index f7211bf..610a1af 100644 --- a/talk/xplsddasync.tex +++ b/talk/xplsddasync.tex @@ -1,4 +1,4 @@ -\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 @@ -11,9 +11,9 @@ \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}