%\RequirePackage{atbegshi}
\documentclass[french]{beamer}
\usepackage{etex}

\usepackage[beamer,utf8x]{preambuleTrm}



\usepackage{iwona}


\mode<presentation>
{
  %\usetheme{Bergen}%Montpellier
  % or ...Frankfurt, 
  \usetheme[secheader]{Madrid}

  \setbeamercovered{highly dynamic}
  % or whatever (possibly just delete it)
  \usefonttheme{progressbar}
  \useoutertheme{progressbar}
  %\useinnertheme{progressbar}
  \progressbaroptions{% titlepage=normal,
    imagename=/home/moi/Photos/Maths/typewriter
}
}

\usepackage{elephantbird}


%\usepackage[french,vlined,boxed]{algorithm2e}
\usepackage{bookmark,multido}
%\usepackage{xlop}

\ifpdf \DeclareGraphicsRule{*}{mps}{*}{} \fi
\usepackage{tikz}
\usetikzlibrary{automata,fit,trees,matrix,arrows,decorations.pathmorphing,shapes,arrows,chains,positioning,intersections,backgrounds,calc,through,mindmap,shadows,patterns}
\newcommand{\myunit}{1.1cm}
\usepackage{tkz-graph}
\usepackage{circuitikz}
\hypersetup{pdfpagemode=FullScreen}

\usepackage[detect-all]{siunitx}

\usepackage{caption}
\captionsetup{labelformat=empty,font=footnotesize}

\usepackage{scalefnt}

%\usepackage{multimedia}
% \usepackage{cclicenses}
% \usepackage{cclicence}
\setbeamertemplate{theorems}[numbered]

\usepackage[square]{daedale}
\bibliographystyle{cyclope}


\usepackage{algo}

\renewcommand{\algocommentfont}{\tiny\ttfamily\itshape}


\newtheorem{exercice}{Exercice}


\setlength{\columnseprule}{0pt}

%\setlength{\parskip}{0pt}


\graphicspath{{/home/moi/IUT/Figures/}{/home/moi/VISA_III/figures_visa/}{/home/moi/Lycee/TDmaple/2006_7/}{/home/moi/Figures/Arbres_Graphes/}{/home/moi/Figures/FigSTI/}{/home/moi/Figures/FigMaple/}{/home/moi/Photos/Maths/}{/home/moi/Photos/Tehessin/}{/home/moi/Figures/FigSTI/}{/home/moi/Figures/FigSeconde/}{/home/moi/Lycee/Informatique/XCAS/2008_9/}{/home/moi/Lycee/TDmaple/2008_9/}{/home/moi/IUT/Thierry/Conversions/}{/home/moi/Photos/informathix/}{/home/moi/Lycee/Informatique/PafAlgo/}{/home/moi/Figures/figuresAlice/}{/home/moi/Figures/FigSeconde/}{/home/moi/Biocam/robot/}{/home/moi/Biocam/CoursIni3d/}{/home/moi/Biocam/central/figures/}{/home/moi/Biocam/central/}{/home/moi/IUT/INFO2/Images/}{/home/moi/IUT/INFO2/2011_12/graphes/}{/home/moi/IUT/INFO1/CM1/}{/home/moi/Figures/figuresTS/}{/home/moi/Photos/Tehessin/}{/home/moi/Figures/FigSTI/}{/home/moi/Alice/figures3/}{/home/moi/Alice/figures3/newcourbes/}{/home/moi/Alice/figures/}{/home/moi/Figures/figuresAlice/}{/home/moi/Photos/Maths/}{/home/moi/Lycee/TS/}{/home/moi/Lycee/TS/2009_10/}{/home/moi/Figures/FigMaple/}{/home/moi/Figures/figuresTS/newcourbes/}{/home/moi/Figures/FigEspace/}{/home/moi/PROG/HASKELL/FLOAT/}{/home/moi/PREPA/IPT/2014_15/Poly/}}




\setcounter{tocdepth}{2} %\setcounter{page}{0}


\newcommand{\triangleup}{\Delta}













\begin{document}


\title[]% (optional, use only with long paper titles)
{Probabilités et informatique I \\ Aléatoire et machine}

\subtitle{INFO2 - semaines 36 à 37}

\author[] % (optional, use only with lots of authors)
{Guillaume CONNAN }
% - Give the names in the same order as the appear in the paper.
% - Use the inst{?} command only if the authors have different
%   affiliation.

\institute{\textsc{Iut} de Nantes - Dpt d'informatique}% (optional, but mostly needed)

\logo{\includegraphics[width=0.1\textwidth]{logo_iut}}

%\logo{\includegraphics[scale=0.15]{big_connan}}

\date[] % (optional, should be abbreviation of conference name)
{septembre 2015}
% - Either use conference name or its abbreviation.
% - Not really informative to the audience, more for people (including
%   yourself) who are reading the slides online

\subject{ }


\beamerdefaultoverlayspecification{<+->}

% \AtBeginSubsubsection[]
% {
%   \begin{frame}<beamer>
%     \frametitle{Sommaire}
%  {\scriptsize
% \begin{multicols}{2}
%     \tableofcontents[currentsection,currentsubsection]
%        \end{multicols}
% }

%   \end{frame}
% }




% \AtBeginSubsection[]
% {\scriptsize
%   \begin{frame}<beamer>
%     \frametitle{Sommaire}
%  {\tiny
% \begin{multicols}{2}
%     \tableofcontents[currentsection,currentsubsection]
%        \end{multicols}
% }

%   \end{frame}
% }





% \AtBeginSection[]
% {
%   \begin{frame}<beamer>
%     \frametitle{Sommaire}
%  {\scriptsize
% \begin{multicols}{2}
%     \tableofcontents[currentsection]
%        \end{multicols}
% }

%   \end{frame}
% }


% If you wish to uncover everything in a step-wise fashion, uncomment
% the following command: 

\beamerdefaultoverlayspecification{<+->}




\newcommand{\TR}{\mathcal{T}}


\begin{frame}
%\ThisCenterWallPaper{1}{logoiremBigInv}
 \Large \titlepage 
\end{frame}

% \begin{frame}
%  \frametitle{Sommaire}
% {\scriptsize
% \begin{multicols}{2} 
%  \tableofcontents
% \end{multicols}
% }

 
%  \end{frame}



\footnotesize

\begin{frame}[fragile]
  \begin{verbatim}
$ ssh-keygen -t rsa
Generating public/private rsa key pair.
Enter file in which to save the key (/home/moi/.ssh/id_rsa): /tmp/id_rsa
Enter passphrase (empty for no passphrase): 
Enter same passphrase again: 
Your identification has been saved in /tmp/id_rsa.
Your public key has been saved in /tmp/id_rsa.pub.    
  \end{verbatim}
\end{frame}

\tiny

\begin{frame}[fragile]

\begin{verbatim}
----BEGIN RSA PRIVATE KEY-----
MIIEpQIBAAKCAQEAyq/yDe2K8EGOEYfj3YBqtjPWeVEUcEiNv6EFxEf17bQlUr1z
UBPxs5uWPFkR8lKKoW+pipAmrM9mgJc/wQz3VoNO6xqic7XAjeTcHRyUmf0kHFAb
0FDzpAzDQMguLzhoKm5ac6u91kxL8pKLvrgDc1HVhHXild8pkjtVgGJFpOYu2av+
PwbAd0IdgIyfatOtlQJjjNi/X+jlcP7+SmEkdutft7ZieBkEYoJddYQBllzGsgVS
vvwZFwDY3DcVoCndeSDy7vdEXdXGw7HQGZd2y2xlxeoTNSTCxUibjWtBkQTuFK52
9g5HCg3PDJk+qB0b0Z5FT2beomimpsJdLq5BhQIDAQABAoIBABUVQidiux4Mo5t9
OB2VOwRi1f9eiLK5SU1SkYf+OD2WjH9Tx4ff2zdkircSSMSdA2CRfeA06GD3XeEo
WnBZSe0M0YuxBI7mq/XWhXLdwzNVWok7Z/k+QmmhDjpR2EP/KQ6o1e3MQn3lB81e
ovyepXU8YOpbXMtcIDXeyCEHl9j0DQii1RgqL1BKxQz2ubcIWBlx4Foyvlgmx0Vs
us3f2T5yKBPgOdP3reZ4OoSJFq4vWQxIzOHl59lPNU4zG0z9vEOsNAbRbjZkqm4W
3dtPDVnUonGn+kSiDOuI+P7jShHVKVSahEmMMoxUGoPkUbIfTq9gKSCs8IkOLqlp
mUajVSECgYEA9l97nC2OaFMdywrKPunitI43+MR8g4KVmAeeZYIoMEtasrg/twRt
TiVuhu6j+NxaZoRuZxaIHPvc9YoPhyrjidnSwBeM23wVU3GSObr3pCcwBZniuWJa
WMjMKTArqdWMPqTFWhfHb7Ig0YpxLtWWy5Lo4+Cv2hHVZoZlWkbE4JkCgYEA0pt3
VMZHNO+aE3StvBremrNsbdv1nkIAOAlHWju/w+c9qeE4yxB5SG1w7suJgOLw8Tjm
E40CeJYzJiZ29nBt0q/ZTo4OoOr09NnUVTVRuZkVRcLdLnbPnPYkxxbmjkOrCblL
lM+JpQo9xeRwetUUAkJIKDUks+aVI4avmjx+/80CgYEA3UDcemIzHJ9gByLWg+94
55s8ysxx4YyZGWHmLtTXkJ9rgUqT9aElJGPbQZP4b5o8GQrfNvb2H8lUIrHsxf+P
PhH/AQFlPwrNABXjMrMkiCelKbKL+N5JsqgJKQgYfjnH683/aawnL7jxXhyNDnlE
Jef1/AehBR603ZDeXldloSkCgYEAxFUoBoCdCw0+flqsR4po8KDJORTvwWvX1mVX
/hdrKs6cXozWK/+cgNd9iy91bRCi+s1HNvyiTBYBctQy3IRs7Rb/psqpenvuhX+4
AQMmv7Wk7ha9qL4bx0BzgqGnpwIQJY12lzBuKcwFUEEoVmnjMEPoDouUPp17dNXv
SAKThhUCgYEAkqDr3LeWh6tLxcfWlcdE5/ukZcaKNKH1w2ShyBbHB9I7UJFl0yoZ
uGUp9yLftgg2eBECwzeRisdoDQSRtPofF8zMBTBV43xV58RdA0BgJ3NZxq7f2Stv
vJW53PNT8udYFLh5lnaVfli05J11lboO3KWGfFfWM3bYcVMvbda16zQ=
-----END RSA PRIVATE KEY-----
\end{verbatim}

\end{frame}

\normalsize



\begin{frame}
  \begin{itemize}
  \item réseau
  \item cryptographie
  \item test
  \item jeux
  \item infographie
  \item tri - recherche
  \item langues naturelles
  \item ...
  \end{itemize}
\end{frame}

\begin{frame}\frametitle{Aléatoire?}
  
%\begin{figure}
\begin{center}
  \includegraphics[width=0.9\linewidth]{coinFlip}
\end{center}
%\end{figure}

\end{frame}

\begin{frame}[fragile]
  \frametitle{Sur machine?}
  \begin{ccode}
int getRandomNumber()
{
      return 4 ; // J'ai trouvé 4 en lançant un dé
                 // Hasard assuré, j'le jure
}
  \end{ccode}
\end{frame}



\begin{frame}
  \begin{center}
  \includegraphics[height=0.8\textheight]{vonNeumanRandom}
\end{center}
\end{frame}


\begin{frame}
  \begin{itemize}
  \item On veut générer une suite pseudo-aléatoire de 10 chiffres
  \item L'actuel est \num{5772156649}
  \item Son carré vaut \num{33317792380594909201}
  \item Le nouveau nombre est donc \num{7923805949}
  \end{itemize}

  


\end{frame}



\begin{frame}\frametitle{Python}
  
%\begin{figure}
\begin{center}
  \includegraphics[height=0.8\textheight]{serpent}
\end{center}
%\end{figure}

\end{frame}


\begin{frame}[fragile]
\begin{pythoncode}
def prendMilieu(nb):
    lnb = len(str(nb))
    return((nb**2 // 10**(max(1,lnb // 2)) ) % 10**lnb)  
\end{pythoncode}

\pause

\begin{pythoncode}
def longVonNeumann(graine):
    L = []
    k = graine
    while k not in L:
        L.append(k)
        k = prendMilieu(k)
    return(len(L))  
\end{pythoncode}


\end{frame}


\begin{frame}[fragile]
\begin{pythoncode}
In [45]: prendMilieu(5772156649)
Out[47]: 7923805949
\end{pythoncode}
\pause

\begin{pythoncode}
In [48]: max([longVonNeumann(k) for k in range(900000,1000000)])
Out[48]: 119  
\end{pythoncode}  
\end{frame}




\begin{frame}
\begin{figure}
  \includegraphics[width=0.4\linewidth]{ehmer}
\caption{D. H. \textsc{Lehmer} \\ 1905-1991}
\end{figure}
\end{frame}



\begin{frame}
  
1949:

$$X_{n+1} = (aX_n+c) \mod m$$

\begin{itemize}
\item $m$, le module, vérifiant $ 0<m$,
\item $ a$, le facteur, vérifiant $ 0 \leqslant a <m$,
\item $ c$, l'incrément, vérifiant $ 0 \leqslant c <m$,
\item $ X_0$, la graine, vérifiant $ 0 \leqslant X_0 <m$,
\end{itemize}


\end{frame}




\begin{frame}\frametitle{Python c'est facile}
  
%\begin{figure}
\begin{center}
  \includegraphics[height=0.8\textheight]{serpent}
\end{center}
%\end{figure}

\end{frame}



\begin{frame}[fragile]
\begin{pythoncode}
 def gcm(m,a,c,x):
    while True:
        yield x
        x = (a*x + c) % m 
\end{pythoncode}


\end{frame}


\begin{frame}[fragile]

\begin{pythoncode}
In [105]: gen = gcm(10,7,7,7)

In [106]: gen
Out[106]: <generator object gcm at 0x7fc4dfd56678>

# Sur Python 2.7 next est une méthode : gen.next()
In [107]: next(gen)
Out[107]: 7

In [108]: next(gen)
Out[108]: 6

In [109]: next(gen)
Out[109]: 9

In [110]: [next(gen) for k in range(20)]
Out[110]: [0, 7, 6, 9, 0, 7, 6, 9, 0, 7, 6, 9, 0, 7, 6, 9, 0, 7, 6, 9]

In [111]: [x for x in itertools.islice(gen,10)]
Out[111]: [0, 7, 6, 9, 0, 7, 6, 9, 0, 7]
\end{pythoncode}

\end{frame}




\begin{frame}
  
\begin{theorem}
  Le GCM est de période $ m$ si, et seulement si:
  \begin{enumerate}
  \item $ c$ est premier avec $ m$;
  \item $ a-1$ est un multiple de tous les diviseurs premiers de $ m$;
\item $ a-1$ est un multiple de 4 si $ m$ est un multiple de 4.
  \end{enumerate}
\end{theorem}
\end{frame}



\begin{frame}[fragile]
  \begin{itemize}
  \item \texttt{/dev/random}
  \item \texttt{/dev/urandom}
  \end{itemize}
\end{frame}

\begin{frame}
  
%\begin{figure}
\begin{center}
  \includegraphics[height=\textheight]{urandom}
\end{center}
%\end{figure}

\end{frame}


\begin{frame}\frametitle{$\pi$}
  
$$3,14159\; 26\; 53589\; 79\; 32\; 38\; 46\; 26\; 43\; 38\; 32\; 79\;... $$

\end{frame}


\begin{frame}[fragile]
  
\begin{pythoncode}
In [9]: ?Counter
Type:            type
String form:     <class 'collections.Counter'>
File:            /usr/local/lib/python3.4/collections/__init__.py
Init definition: Counter(self, iterable=None, **kwds)
Docstring:
Dict subclass for counting hashable items.  Sometimes called a bag
or multiset.  Elements are stored as dictionary keys and their counts
are stored as dictionary values.
\end{pythoncode}
\end{frame}


\begin{frame}[fragile]

\begin{pythoncode}
stats1Pi = Counter(str(N(pi,10**5)))
\end{pythoncode}


\pause

\begin{pythoncode}
In [8]: stats1Pi
Out[8]: Counter({'1': 10137, '6': 10028, '5': 10026, '3': 10026, '7': 10025, '0': 9999, '8': 9978, '4': 9971, '2': 9908, '9': 9902, '.': 1})
\end{pythoncode}

\end{frame}



\begin{frame}[fragile]

\begin{pythoncode}
def parPaquets(iterable, n):
    """
      iter transforme un itérable en itérateur
     * n répète n fois la liste
     * iters découpe la liste iters en une suite d'arguments
     zip crée une liste de n-uplets à partir de n listes
    """
    iters = [iter(iterable)] * n
    return zip_longest(* iters)

stats2Pi = Counter( parPaquets( str( N(pi, 10**5) ), 2 ) ).values()
\end{pythoncode}

\end{frame}

\begin{frame}[fragile]

\begin{pythoncode}
In [59]: stats2Pi
Out[59]: dict_values([506, 440, 483, 499, 523, 469, 522, 517, 556, 491, 469, 511, 491, 538, 498, 489, 510, 488, 503, 509, 558, 536, 509, 511, 494, 523, 505, 499, 504, 498, 474, 459, 518, 492, 485, 494, 462, 507, 487, 491, 536, 558, 529, 499, 493, 537, 549, 465, 522, 487, 472, 498, 517, 521, 482, 483, 482, 494, 503, 498, 494, 452, 501, 490, 491, 512, 514, 470, 456, 484, 515, 527, 479, 512, 502, 490, 473, 468, 530, 509, 484, 1, 488, 513, 520, 556, 445, 491, 1, 505, 475, 494, 463, 463, 468, 507, 501, 510, 551, 512, 534, 507])
\end{pythoncode}

\end{frame}


\begin{frame}[fragile]

Voici un code naïf:
\begin{pythoncode}
def chercheMotif(motif,chaine):
    en = enumerate(chaine)
    deb = motif[0]
    n = len(motif)
    for i,k in en:
        if k == deb and chaine[i:i+n] == motif:
            return i
    return 'Pas trouvé'
\end{pythoncode}

\pause

\begin{pythoncode}
In [10]: chercheMotif('007',str(N(pi,10**7)))
Out[10]: 2807
\end{pythoncode}

\pause

\begin{pythoncode}
In [12]: chercheMotif('1234567',str(N(pi,10**7)))
Out[12]: 9470345
\end{pythoncode}

\end{frame}



\end{document}
%%% Local Variables: 
%%% mode: latex
%%% TeX-master: t
%%% End: 
