modif presentation

[16dcc.git] / main.tex

diff --git a/main.tex b/main.tex
index 465fbf5a2d179b15236d958a0c98136a958c0de4..01df881d93f81117dbb0800edf5f71ed81702134 100644 (file)
--- a/main.tex
+++ b/main.tex
@@ -1,21 +1,22 @@
-\documentclass{ita}
+
+\documentclass{ws-ijbc}

 \usepackage{graphicx}
 \usepackage{graphicx}

-\usepackage{caption}
-\usepackage{subcaption}
+%\usepackage{amsthm}

 
 

+%\usepackage{subcaption}
+\usepackage{subfigure}

 \usepackage{dsfont}
 \usepackage{stmaryrd}
 %\usepackage[font=footnotesize]{subfig}
 \usepackage{ifthen}
 \usepackage{color}
 \usepackage{dsfont}
 \usepackage{stmaryrd}
 %\usepackage[font=footnotesize]{subfig}
 \usepackage{ifthen}
 \usepackage{color}

+%\usepackage{subfigure}

 \usepackage{algorithm2e}
 \usepackage{epstopdf}
 \usepackage{algorithm2e}
 \usepackage{epstopdf}

-%\usepackage{ntheorem}
-

 \usepackage[utf8]{inputenc}
 \usepackage[T1]{fontenc} 
 \usepackage[english]{babel}
 \usepackage[utf8]{inputenc}
 \usepackage[T1]{fontenc} 
 \usepackage[english]{babel}

-\usepackage{amsmath,amssymb,latexsym,eufrak,euscript}
+%\usepackage{amsmath,amssymb,amsthm,latexsym,eufrak,euscript}

 \usepackage{pstricks,pst-node,pst-coil}
 
 
 \usepackage{pstricks,pst-node,pst-coil}
 
 


@@ -35,16 +36,17 @@
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 
 \definecolor{bleuclair}{rgb}{0.75,0.75,1.0}
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 
 \definecolor{bleuclair}{rgb}{0.75,0.75,1.0}

+\newcommand{\danger}{!!}

 \newcommand{\ANNOT}[1]{
   ~\linebreak
   \centerline{
 \newcommand{\ANNOT}[1]{
   ~\linebreak
   \centerline{

-    {\Huge{\danger}}
+    {\Huge{$\Rightarrow$}}

     \large\fcolorbox{black}{bleuclair}{
       \begin{minipage}[h]{.8\linewidth}
         #1
       \end{minipage}
     }
     \large\fcolorbox{black}{bleuclair}{
       \begin{minipage}[h]{.8\linewidth}
         #1
       \end{minipage}
     }

-    {\Huge{\danger}}
+    {\Huge{$\Leftarrow$}}

   }
 }
 
   }
 }
 


@@ -58,7 +60,16 @@
 \def \ts {\tau_{\rm stop}}
 
 
 \def \ts {\tau_{\rm stop}}
 
 

-\newtheorem*{xpl}{Running Example}
+%\newtheorem*{xpl}{Running Example}
+\newenvironment{xpl}[1][Running Example]{\textbf{#1.} }{\ \rule{0.5em}{0.5em}}
+
+%\newtheorem{definition}{Definition}
+\newtheorem{prpstn}{Proposition}
+\newtheorem{thrm}{Theorem}
+\newtheorem{crllr}{Corollary}
+\newtheorem{lmm}{Lemma}
+
+

 
 \newcommand{\vectornorm}[1]{\ensuremath{\left|\left|#1\right|\right|_2}}
 %\newcommand{\ie}{\textit{i.e.}}
 
 \newcommand{\vectornorm}[1]{\ensuremath{\left|\left|#1\right|\right|_2}}
 %\newcommand{\ie}{\textit{i.e.}}


@@ -80,44 +91,235 @@
 
 
 
 
 
 

+
+% Some very useful LaTeX packages include:
+% (uncomment the ones you want to load)
+
+
+% *** MISC UTILITY PACKAGES ***
+%
+%\usepackage{ifpdf}
+% Heiko Oberdiek's ifpdf.sty is very useful if you need conditional
+% compilation based on whether the output is pdf or dvi.
+% usage:
+% \ifpdf
+%   % pdf code
+% \else
+%   % dvi code
+% \fi
+% The latest version of ifpdf.sty can be obtained from:
+% http://www.ctan.org/pkg/ifpdf
+% Also, note that IEEEtran.cls V1.7 and later provides a builtin
+% \ifCLASSINFOpdf conditional that works the same way.
+% When switching from latex to pdflatex and vice-versa, the compiler may
+% have to be run twice to clear warning/error messages.
+
+
+
+
+
+
+% *** CITATION PACKAGES ***
+%
+%\usepackage{cite}
+% cite.sty was written by Donald Arseneau
+% V1.6 and later of IEEEtran pre-defines the format of the cite.sty package
+% \cite{} output to follow that of the IEEE. Loading the cite package will
+% result in citation numbers being automatically sorted and properly
+% "compressed/ranged". e.g., [1], [9], [2], [7], [5], [6] without using
+% cite.sty will become [1], [2], [5]--[7], [9] using cite.sty. cite.sty's
+% \cite will automatically add leading space, if needed. Use cite.sty's
+% noadjust option (cite.sty V3.8 and later) if you want to turn this off
+% such as if a citation ever needs to be enclosed in parenthesis.
+% cite.sty is already installed on most LaTeX systems. Be sure and use
+% version 5.0 (2009-03-20) and later if using hyperref.sty.
+% The latest version can be obtained at:
+% http://www.ctan.org/pkg/cite
+% The documentation is contained in the cite.sty file itself.
+
+
+
+
+
+
+\begin{document}
+%
+% paper title
+% Titles are generally capitalized except for words such as a, an, and, as,
+% at, but, by, for, in, nor, of, on, or, the, to and up, which are usually
+% not capitalized unless they are the first or last word of the title.
+% Linebreaks \\ can be used within to get better formatting as desired.
+% Do not put math or special symbols in the title.

 \title{Random Walk in a N-cube Without Hamiltonian Cycle 
   to Chaotic Pseudorandom Number Generation: Theoretical and Practical 
   Considerations}
 
 \title{Random Walk in a N-cube Without Hamiltonian Cycle 
   to Chaotic Pseudorandom Number Generation: Theoretical and Practical 
   Considerations}
 

-\begin{document}
+%
+%
+% author names and IEEE memberships
+% note positions of commas and nonbreaking spaces ( ~ ) LaTeX will not break
+% a structure at a ~ so this keeps an author's name from being broken across
+% two lines.
+% use \thanks{} to gain access to the first footnote area
+% a separate \thanks must be used for each paragraph as LaTeX2e's \thanks
+% was not built to handle multiple paragraphs
+%
+\author{Sylvain Contassot-Vivier}
+\address{LORIA, Université de Lorraine, Nancy, France\\
+sylvain.contassotvivier@loria.fr}
+
+\author{Jean-François Couchot}
+\address{FEMTO-ST Institute,  CNRS, Univ. Bourgogne Franche-Comté (UBFC), France\\
+jean-francois.couchot@univ-fcomte.fr}
+
+\author{Christophe Guyeux}
+\address{FEMTO-ST Institute,  CNRS, Univ. Bourgogne Franche-Comté (UBFC), France\\
+christophe.guyeux@univ-fcomte.fr}
+
+\author{Pierre-Cyrille Heam}
+\address{FEMTO-ST Institute,  CNRS, Univ. Bourgogne Franche-Comté (UBFC), France\\
+pierre-cyrille.heam@univ-fcomte.fr}
+
+
+
+% \author{Michael~Shell,~\IEEEmembership{Member,~IEEE,}
+%         John~Doe,~\IEEEmembership{Fellow,~OSA,}
+%         and~Jane~Doe,~\IEEEmembership{Life~Fellow,~IEEE}% <-this % stops a space
+% \thanks{M. Shell was with the Department
+% of Electrical and Computer Engineering, Georgia Institute of Technology, Atlanta,
+% GA, 30332 USA e-mail: (see http://www.michaelshell.org/contact.html).}% <-this % stops a space
+% \thanks{J. Doe and J. Doe are with Anonymous University.}% <-this % stops a space
+% \thanks{Manuscript received April 19, 2005; revised August 26, 2015.}}
+
+% note the % following the last \IEEEmembership and also \thanks - 
+% these prevent an unwanted space from occurring between the last author name
+% and the end of the author line. i.e., if you had this:
+% 
+% \author{....lastname \thanks{...} \thanks{...} }
+%                     ^------------^------------^----Do not want these spaces!
+%
+% a space would be appended to the last name and could cause every name on that
+% line to be shifted left slightly. This is one of those "LaTeX things". For
+% instance, "\textbf{A} \textbf{B}" will typeset as "A B" not "AB". To get
+% "AB" then you have to do: "\textbf{A}\textbf{B}"
+% \thanks is no different in this regard, so shield the last } of each \thanks
+% that ends a line with a % and do not let a space in before the next \thanks.
+% Spaces after \IEEEmembership other than the last one are OK (and needed) as
+% you are supposed to have spaces between the names. For what it is worth,
+% this is a minor point as most people would not even notice if the said evil
+% space somehow managed to creep in.
+
+
+
+% The only time the second header will appear is for the odd numbered pages
+% after the title page when using the twoside option.
+% 
+% *** Note that you probably will NOT want to include the author's ***
+% *** name in the headers of peer review papers.                   ***
+% You can use \ifCLASSOPTIONpeerreview for conditional compilation here if
+% you desire.
+
+
+
+
+% If you want to put a publisher's ID mark on the page you can do it like
+% this:
+%\IEEEpubid{0000--0000/00\$00.00~\copyright~2015 IEEE}
+% Remember, if you use this you must call \IEEEpubidadjcol in the second
+% column for its text to clear the IEEEpubid mark.
+
+
+
+% use for special paper notices
+%\IEEEspecialpapernotice{(Invited Paper)}

 
 

-\author{Jean-François Couchot, Christophe Guyeux, Pierre-Cyrille Heam}
-\address{FEMTO-ST Institute, University of Franche-Comté, Belfort, France}

 
 

-\keywords{Pseudorandom Number Generator, Theory of Chaos, Markov Matrice, Hamiltonian Path, Mixing Time, Stopping Time, Statistical Test}

 
 

-\subjclass{34C28, 37A25,11K45}
+
+% make the title area
+%\maketitle
+
+% As a general rule, do not put math, special symbols or citations
+% in the abstract or keywords.
+
+
+% \begin{abstract}
+% This paper is dedicated to the design of chaotic random generators
+% and extends previous works proposed by some of the authors.
+% We propose a theoretical framework proving both the chaotic properties and
+% that the limit distribution is uniform.
+% A theoretical bound on the stationary time is given and
+% practical experiments show that the generators successfully pass
+% the classical statistical tests.
+% \end{abstract}
+
+
+% Note that keywords are not normally used for peerreview papers.
+% \begin{IEEEkeywords}
+% IEEE, IEEEtran, journal, \LaTeX, paper, template.
+% \end{IEEEkeywords}
+
+
+
+
+
+
+% For peer review papers, you can put extra information on the cover
+% page as needed:
+% \ifCLASSOPTIONpeerreview
+% \begin{center} \bfseries EDICS Category: 3-BBND \end{center}
+% \fi
+%
+% For peerreview papers, this IEEEtran command inserts a page break and
+% creates the second title. It will be ignored for other modes.
+\maketitle

 
 \begin{abstract}
 
 \begin{abstract}

-This paper is dedicated to the design of chaotic random generators
-and extends previous works proposed by some of the authors.
-We propose a theoretical framework proving both the chaotic properties and
-that the limit distribution is uniform.
-A theoretical bound on the stationary time is given and
-practical experiments show that the generators successfully pass
-the classical statistical tests.
+  Designing a pseudorandom number generator (PRNG) is a
+difficult  and complex  task.  Many  recent works  have considered  chaotic
+functions as the basis of built PRNGs: the quality of the output would
+indeed
+be an obvious consequence of some chaos properties.  However, there is
+no  direct  reasoning that  goes  from  chaotic functions  to  uniform
+distribution of the output.  
+Moreover,  
+embedding such kind of functions into a PRNG does not necessarily
+allow to get a  chaotic output,
+which could be required for simulating some chaotic behaviors.
+
+In a  previous work,  some of  the authors have  proposed the  idea of
+walking into  a $\mathsf{N}$-cube  where a balanced  Hamiltonian cycle
+has been removed as the basis of  a chaotic PRNG. In this article, all
+the  difficult  issues  observed  in   the  previous  work  have  been
+tackled.  The  chaotic behavior  of  the  whole  PRNG is  proven.  The
+construction of  the balanced  Hamiltonian cycle is  theoretically and
+practically solved. An upper bound of  the expected length of the walk
+to  obtain a  uniform distribution  is calculated.   Finally practical
+experiments show  that the generators successfully  pass the classical
+statistical tests.

 \end{abstract}
 
 \end{abstract}
 

-\maketitle
+
+\keywords{Pseudorandom Numbers Generator, Chaotic iterations, Random Walk}
+

 
 \section{Introduction}
 \input{intro}
 
 
 \section{Introduction}
 \input{intro}
 

- \section{\uppercase{Preliminaries}}\label{sec:preliminaries}
+\section{Preliminaries}\label{sec:preliminaries}

 \input{preliminaries}
 
 \input{preliminaries}
 

-\section{Proof Of Chaos}\label{sec:proofOfChaos}
+\section{Proof of Chaos}\label{sec:proofOfChaos}

 \input{chaos}
 
 \section{Functions with Strongly Connected $\Gamma_{\{b\}}(f)$}\label{sec:SCCfunc}
 \input{generating}
 
 \input{chaos}
 
 \section{Functions with Strongly Connected $\Gamma_{\{b\}}(f)$}\label{sec:SCCfunc}
 \input{generating}
 

-\section{Stopping Time}\label{sec:hypercube}
+\section{Balanced Hamiltonian Cycle}\label{sec:hamilton}
+\input{hamilton}
+
+
+\section{Mixing Time}\label{sec:hypercube}

 \input{stopping}
 
 \section{Experiments}\label{sec:prng}
 \input{stopping}
 
 \section{Experiments}\label{sec:prng}


@@ -130,7 +332,267 @@ the classical statistical tests.
 
 %\acknowledgements{...}
 
 
 %\acknowledgements{...}
 

-\bibliographystyle{alpha}
+\section*{Acknowledgements}
+This work is partially funded by the Labex ACTION program (contract ANR-11-LABX-01-01). 
+Computations presented in this article were realised on the supercomputing
+facilities provided by the M\'esocentre de calcul de Franche-Comt\'e.
+
+
+
+
+\bibliographystyle{ws-ijbc} 

 \bibliography{biblio}
 
 \bibliography{biblio}
 

+
+%\section{Introduction}
+% The very first letter is a 2 line initial drop letter followed
+% by the rest of the first word in caps.
+% 
+% form to use if the first word consists of a single letter:
+% \IEEEPARstart{A}{demo} file is ....
+% 
+% form to use if you need the single drop letter followed by
+% normal text (unknown if ever used by the IEEE):
+% \IEEEPARstart{A}{}demo file is ....
+% 
+% Some journals put the first two words in caps:
+% \IEEEPARstart{T}{his demo} file is ....
+% 
+% Here we have the typical use of a "T" for an initial drop letter
+% and "HIS" in caps to complete the first word.
+% \IEEEPARstart{T}{his} demo file is intended to serve as a ``starter file''
+% for IEEE journal papers produced under \LaTeX\ using
+% IEEEtran.cls version 1.8b and later.
+% % You must have at least 2 lines in the paragraph with the drop letter
+% % (should never be an issue)
+% I wish you the best of success.
+
+% \hfill mds
+ 
+% \hfill August 26, 2015
+
+% \subsection{Subsection Heading Here}
+% Subsection text here.
+
+% % needed in second column of first page if using \IEEEpubid
+% %\IEEEpubidadjcol
+
+% \subsubsection{Subsubsection Heading Here}
+% Subsubsection text here.
+
+
+% % An example of a floating figure using the graphicx package.
+% % Note that \label must occur AFTER (or within) \caption.
+% % For figures, \caption should occur after the \includegraphics.
+% % Note that IEEEtran v1.7 and later has special internal code that
+% % is designed to preserve the operation of \label within \caption
+% % even when the captionsoff option is in effect. However, because
+% % of issues like this, it may be the safest practice to put all your
+% % \label just after \caption rather than within \caption{}.
+% %
+% % Reminder: the "draftcls" or "draftclsnofoot", not "draft", class
+% % option should be used if it is desired that the figures are to be
+% % displayed while in draft mode.
+% %
+% %\begin{figure}[!t]
+% %\centering
+% %\includegraphics[width=2.5in]{myfigure}
+% % where an .eps filename suffix will be assumed under latex, 
+% % and a .pdf suffix will be assumed for pdflatex; or what has been declared
+% % via \DeclareGraphicsExtensions.
+% %\caption{Simulation results for the network.}
+% %\label{fig_sim}
+% %\end{figure}
+
+% % Note that the IEEE typically puts floats only at the top, even when this
+% % results in a large percentage of a column being occupied by floats.
+
+
+% % An example of a double column floating figure using two subfigures.
+% % (The subfig.sty package must be loaded for this to work.)
+% % The subfigure \label commands are set within each subfloat command,
+% % and the \label for the overall figure must come after \caption.
+% % \hfil is used as a separator to get equal spacing.
+% % Watch out that the combined width of all the subfigures on a 
+% % line do not exceed the text width or a line break will occur.
+% %
+% %\begin{figure*}[!t]
+% %\centering
+% %\subfloat[Case I]{\includegraphics[width=2.5in]{box}%
+% %\label{fig_first_case}}
+% %\hfil
+% %\subfloat[Case II]{\includegraphics[width=2.5in]{box}%
+% %\label{fig_second_case}}
+% %\caption{Simulation results for the network.}
+% %\label{fig_sim}
+% %\end{figure*}
+% %
+% % Note that often IEEE papers with subfigures do not employ subfigure
+% % captions (using the optional argument to \subfloat[]), but instead will
+% % reference/describe all of them (a), (b), etc., within the main caption.
+% % Be aware that for subfig.sty to generate the (a), (b), etc., subfigure
+% % labels, the optional argument to \subfloat must be present. If a
+% % subcaption is not desired, just leave its contents blank,
+% % e.g., \subfloat[].
+
+
+% % An example of a floating table. Note that, for IEEE style tables, the
+% % \caption command should come BEFORE the table and, given that table
+% % captions serve much like titles, are usually capitalized except for words
+% % such as a, an, and, as, at, but, by, for, in, nor, of, on, or, the, to
+% % and up, which are usually not capitalized unless they are the first or
+% % last word of the caption. Table text will default to \footnotesize as
+% % the IEEE normally uses this smaller font for tables.
+% % The \label must come after \caption as always.
+% %
+% %\begin{table}[!t]
+% %% increase table row spacing, adjust to taste
+% %\renewcommand{\arraystretch}{1.3}
+% % if using array.sty, it might be a good idea to tweak the value of
+% % \extrarowheight as needed to properly center the text within the cells
+% %\caption{An Example of a Table}
+% %\label{table_example}
+% %\centering
+% %% Some packages, such as MDW tools, offer better commands for making tables
+% %% than the plain LaTeX2e tabular which is used here.
+% %\begin{tabular}{|c||c|}
+% %\hline
+% %One & Two\\
+% %\hline
+% %Three & Four\\
+% %\hline
+% %\end{tabular}
+% %\end{table}
+
+
+% % Note that the IEEE does not put floats in the very first column
+% % - or typically anywhere on the first page for that matter. Also,
+% % in-text middle ("here") positioning is typically not used, but it
+% % is allowed and encouraged for Computer Society conferences (but
+% % not Computer Society journals). Most IEEE journals/conferences use
+% % top floats exclusively. 
+% % Note that, LaTeX2e, unlike IEEE journals/conferences, places
+% % footnotes above bottom floats. This can be corrected via the
+% % \fnbelowfloat command of the stfloats package.
+
+
+
+
+% \section{Conclusion}
+% The conclusion goes here.
+
+
+
+
+
+% % if have a single appendix:
+% %\appendix[Proof of the Zonklar Equations]
+% % or
+% %\appendix  % for no appendix heading
+% % do not use \section anymore after \appendix, only \section*
+% % is possibly needed
+
+% % use appendices with more than one appendix
+% % then use \section to start each appendix
+% % you must declare a \section before using any
+% % \subsection or using \label (\appendices by itself
+% % starts a section numbered zero.)
+% %
+
+
+% \appendices
+% \section{Proof of the First Zonklar Equation}
+% Appendix one text goes here.
+
+% % you can choose not to have a title for an appendix
+% % if you want by leaving the argument blank
+% \section{}
+% Appendix two text goes here.
+
+
+% % use section* for acknowledgment
+% \section*{Acknowledgment}
+
+
+% The authors would like to thank...
+
+
+% Can use something like this to put references on a page
+% by themselves when using endfloat and the captionsoff option.
+
+
+
+% trigger a \newpage just before the given reference
+% number - used to balance the columns on the last page
+% adjust value as needed - may need to be readjusted if
+% the document is modified later
+%\IEEEtriggeratref{8}
+% The "triggered" command can be changed if desired:
+%\IEEEtriggercmd{\enlargethispage{-5in}}
+
+% references section
+
+% can use a bibliography generated by BibTeX as a .bbl file
+% BibTeX documentation can be easily obtained at:
+% http://mirror.ctan.org/biblio/bibtex/contrib/doc/
+% The IEEEtran BibTeX style support page is at:
+% http://www.michaelshell.org/tex/ieeetran/bibtex/
+%\bibliographystyle{IEEEtran}
+% argument is your BibTeX string definitions and bibliography database(s)
+%\bibliography{IEEEabrv,../bib/paper}
+%
+% <OR> manually copy in the resultant .bbl file
+% set second argument of \begin to the number of references
+% (used to reserve space for the reference number labels box)
+% \begin{thebibliography}{1}
+
+% \bibitem{IEEEhowto:kopka}
+% H.~Kopka and P.~W. Daly, \emph{A Guide to \LaTeX}, 3rd~ed.\hskip 1em plus
+%   0.5em minus 0.4em\relax Harlow, England: Addison-Wesley, 1999.
+
+% \end{thebibliography}
+
+% biography section
+% 
+% If you have an EPS/PDF photo (graphicx package needed) extra braces are
+% needed around the contents of the optional argument to biography to prevent
+% the LaTeX parser from getting confused when it sees the complicated
+% \includegraphics command within an optional argument. (You could create
+% your own custom macro containing the \includegraphics command to make things
+% simpler here.)
+%\begin{IEEEbiography}[{\includegraphics[width=1in,height=1.25in,clip,keepaspectratio]{mshell}}]{Michael Shell}
+% or if you just want to reserve a space for a photo:
+
+% \begin{IEEEbiography}{Michael Shell}
+% Biography text here.
+% \end{IEEEbiography}
+
+% % if you will not have a photo at all:
+% \begin{IEEEbiographynophoto}{John Doe}
+% Biography text here.
+% \end{IEEEbiographynophoto}
+
+% % insert where needed to balance the two columns on the last page with
+% % biographies
+% %\newpage
+
+% \begin{IEEEbiographynophoto}{Jane Doe}
+% Biography text here.
+% \end{IEEEbiographynophoto}
+
+% You can push biographies down or up by placing
+% a \vfill before or after them. The appropriate
+% use of \vfill depends on what kind of text is
+% on the last page and whether or not the columns
+% are being equalized.
+
+%\vfill
+
+% Can be used to pull up biographies so that the bottom of the last one
+% is flush with the other column.
+%\enlargethispage{-5in}
+
+
+
+% that's all folks

 \end{document}
 \end{document}