\chapterimage{typewriter}
\chaptertext{}

\chapter{Aléatoire?}

% \section{Promenade informatico-aléatoire }

% \subsection{Premier exemple d'utilisation du hasard en informatique}

% Souvenez-vous,  juste  avant  les  vacances,  vous  aviez  étudié  les
% graphes et  en particulier leur  coloration ce qui permet  de résoudre
% des problèmes concrets d'organisation.

% Un  algorithme glouton  facile  à fabriquer  consiste  à affecter  une
% couleur à un premier sommet  puis itérativement d'affecter à un sommet
% non encore coloré  la plus petite couleur disponible  non utilisée par
% ses voisins (la couleur sera ici un entier).

% Illustrons ceci  avec Haskell  en fabriquant  très rapidement  un type
% \texttt{Graphe}  pas très  optimisé mais  suffisamment simple  pour se
% remettre dans le bain et observer quelques phénomènes:


% \haskell
% \begin{lstlisting}
% module Graphe where
    
%     import qualified Data.Map as Map
%     import qualified Data.List as List
%     import qualified System.Random as R

%     type Sommet  = Int
%     type Couleur = Int
%     type Graphe  = Map.Map Sommet [Sommet]

%     -- construit un graphe à partir d'une liste [(Sommet,Adjacents)]
%     graphe2liste :: [(Int,[Int])] -> Graphe
%     graphe2liste g = Map.fromList g

%     -- la liste des voisins de n dans g
%     voisins :: Graphe -> Sommet -> [Sommet]
%     voisins g n = Map.findWithDefault [] n g

%     -- les sommets de g
%     sommets :: Graphe -> [Sommet]
%     sommets g = Map.keys g

%     -- le nombre de sommets de g (son ordre quoi)
%     ordre :: Graphe -> Int
%     ordre g = List.length $ sommets g 

%     -- une fonction de coloration gloutonne
%     coloration :: Graphe -> Int -> [(Sommet,Couleur)]
%     coloration g k =
%         let ss    = sommets g
%             -- on permutte les sommets
%             s     = (List.permutations ss) List.!! k  
%             couls = [1 .. (List.length s)]
%         in
%           List.foldl
%              (\ acc x ->
%                  (x,List.minimum (couls List.\\
%                      (List.map  snd [(som,coul)  | (som,coul)  <- acc,
%                      List.elem som (voisins g x)]))) : acc
%              ) [] s

%     -- nb de couleurs utilisées pour une permutation donnée
%     nbCoul :: Graphe -> Int -> Int
%     nbCoul g k = List.maximum $ List.map snd (coloration g k)

%     -- une estimation du nb chromatique obtenu sur un échantillon 
%     chromaProba :: Graphe -> Int
%     chromaProba g = List.minimum [nbCoul g (3*k - 1) | k <- [1 .. (div (ordre g) 3)]]

%     -- la graîne est calculée modulo 2^31 en fonction d'un paramètre n
%     sGen :: Int -> R.StdGen
%     sGen n = R.mkStdGen n

%     -- liste de booléens qui valent True avec une proba de p
%     bern :: Float -> Int -> [Bool]
%     bern p n = List.map (< p) $ R.randomRs (0, 1) $ sGen n 

%     -- un graphe de taille n construit aléatoirement à l'aide de la fonction bern
%     grapheRand :: Int -> Float -> Graphe
%     grapheRand n p =
%         let b = take ((n + 1)*n + 1) $ bern p n in
%         graphe2liste [(i,[k | k <- [1..n], b !! (k + n*i)]) | i <- [1..n]]
% \end{lstlisting}

% (\textit{Ici : commentaires éclairés de votre professeur adoré})

% \subsection{Comment devenir riche?}


% %\begin{figure}
% \begin{center}
%   \includegraphics[width=\linewidth]{pokerSite}
% \end{center}
% %\end{figure}

% En   1999,   cinq   informaticiens   se  sont   intéressés   au   site
% \textit{PlanetPoker} et  plus particulièrement  à la manière  dont les
% \og cartes\fg{} étaient  mélangées. Avec un peu  d'observation ils ont
% pu produire une application qui donnait en temps réel l'état du jeu de
% 52  cartes utilisé  et pouvait  donc connaître  exactement les  cartes
% cachées...Nous explorerons ce problème en détail.

% (\textit{Ici : commentaires éclairés de votre professeur adoré})




\section{Une machine peut-elle être aléatoire?}

L'informatique a besoin  d'aléatoire dans de nombreux  domaines: tri, recherche,
réseau, test, infographie, jeux, cryptographie, etc.

Le problème est d'abord de savoir  ce que veut dire \og être aléatoire
\fg{}.

Par exemple, voici une suite de 0 et de 1:

\begin{center}
  01010101010101010101010101010101
\end{center}

Il y a autant de 0 que de 1. Qu'en dites-vous?


Est-ce qu'une  machine a  une pièce  de monnaie pour  tirer à  pile ou
face?

Est-ce que tirer à pile ou face est une expérience aléatoire?


(\textit{Ici : commentaires éclairés de votre professeur adoré})


Le  problème de  base est  d'étudier des  \textit{suites aléatoires  de nombres}
  choisis indépendamment selon une \textit{distribution}.

La distribution de  base sur machine est la  distribution \textit{uniforme}: par
exemple, vous voulez  choisir au hasard un  million de bits. Il se  peut que les
\num{999999} premiers soient des 1.  Cependant, la probabilité que le milionième
soit encore 1 est toujours 1/2.


Depuis les années  quarante, on tente de générer des  suites aléatoires avec des
machines.

John \textsc{Von Neumann}, qui a donné  son nom à l'architecture des ordinateurs
qui prévaut encore  aujourd'hui, a proposé le premier un  algorithme en 1946 qui
consistait à prendre le carré du nombre  aléatoire précédent et à en extraire le
mileu.

Par exemple, si on est en train de  générer une suite de nombres de 10 chiffres,
que l'actuel est \num{5772156649},  son carré vaut \num{33317792380594909201} et
le nouveau nombre est donc \num{7923805949}.




%\begin{figure}
\begin{center}
  \includegraphics[height=6cm]{vonNeumanRandom}
\end{center}
%\end{figure}

Pour ce module, nous  allons passer du côté obscur de la  force et illustrer nos
propos en Python.

Pour vous, je suis prêt à tous les sacrifices.

\pythonc

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

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

Alors:

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

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


Nous verrons en exercice quelques failles de la méthode \textit{middle-square}.

Cependant, en cherchant bien,  on a pu trouver en 1956  un suite de \num{750000}
nombres de 38 bits sans dégénérescence. 

On  peut donc  avoir de  bons  résultats, le  problème  c'est qu'on  ne peut  le
vérifier qu'a posteriori...

Jusqu'à  la  fin des  années  70,  les programmeurs  ont  eu  tendance à  éviter
d'étudier ces algos et ont utilisé des générateurs sans les vérifier. Mais
l'avènement du RSA et l'importance accrue de la sécurité et des algos aléatoires
a changé la donne.

\section{Générateur congruentiel linéaire}


\vspace{-1cm}
\setindent{0cm}
\begin{flushleft}
\begin{minipage}[t]{3cm}
\begin{figure}
  \includegraphics[width=3cm]{ehmer}
\caption{D. H. \textsc{Lehmer} \\ 1905-1991}
\end{figure}
\end{minipage}
\end{flushleft}
\setindent{\indentationcours}
\vspace{-5cm}
\begin{minipage}[t]{\linewidth}
\end{minipage}

En  1949,  D. H.  \textsc{Lehmer}  propose  un  générateur dépendant  de  quatre
paramètres:

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

Les quatre paramètres entiers seront appelés ainsi:
\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}


Nous  allons créer  des  générateurs conguentiels  en  utilisant les  générateurs
 de  Python  qui   sont  des  itérateurs  particuliers  car   ils  sont  évalués
 parésseusement...comme en Haskell ;-)

Il  suffit de  créer  une fonction  et de  remplacer  le \lstinline{return}  par
\lstinline{yield}: l'exécution n'est alors  pas arrêtée mais seulement suspendue
et prête à reprendre au même point.


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


Choisissons $ m=10$ et $ X_0=a=c=7$:

\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}




\begin{DANGER}
Tel qu'il est construit, le générateur \lstinline{gen} 
est infini!

Il ne faudra pas demander \lstinline{[x for x in gen]}!
\end{DANGER}


\begin{aparte}
Les générateurs sont  beaucoup plus rapides que les listes  sur Python et donnent
accès aux fonctions de la  bibliothèque \lstinline{itertools} qui sont largement
inspirées de ce qui est disponible sur Haskell...\ ;-)

Ils ont été généralisés sur Python depuis les versions 3.x

\end{aparte}


Revenons à nos moutons: cette suite n'a pas l'air très aléatoire...

Pouvez-vous faire le lien avec la \vref{knuth::3.1.6}?

Il va falloir réfléchir pour trouver une bonne période.
Malheureusement, il faudrait faire pas mal d'arithmétique.

Il  existe  aussi  des  critères  d'efficacité sur  machine:  une  division  est
relativement coûteuse sauf  si on divise par $ 2^{\text{La  longueur des mots du
    système}}$, par exemple $ 2^{64}$ sur 64 bits...

Il existe alors des théorèmes du style:

\begin{theoreme}
  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{theoreme}

Mais il nous faudrait  plus de temps pour pouvoir le prouver.  Passons donc à la
prochaine étape...

Cela nous  permettrait par  exemple de dire  qu'avec $  X_0=\num{5772156648}$, $
a=\num{3141592621}$, $ c=\num{2718281829}$ et $  m=10^{10}$ on obtient une suite
de période $ m$ (ces nombres font sourire les mathématiciens...).

\section{Tests statistiques}


\subsection{Pi}

Regardez ces premières décimales de $ π$. Y trouvez-vous une certaine symétrie?

$$3,14159\; 26\; 53589\; 79\; 32\; 38\; 46\; 26\; 43\; 38\; 32\; 79\;... $$


On peut  aller un peu plus  loin dans l'exploration en  allant voir \num{100000}
décimales de $ π$ et compter combien il y en a de chaque sorte. On peut utiliser
la fonction  \lstinline{Counter} de la bibliothèque  \lstinline{collections}, la
constante \lstinline{pi} et la  fonction \lstinline{N} de \lstinline{sympy} pour
afficher des décimales de $ π$:

\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}

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

\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}


On peut aussi  chercher par paquets de  2. Pour cela, voici  une pure pythonerie
qui  permet de  grouper  efficacement les  éléments d'une  liste  par groupe  de
longueur n:

\begin{pythoncode}
def parPaquets(iterable, n):
    """
      iter transforme un itérable en itérateur : on utilise son côté pile
     * 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}


\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}

C'est assez homogène.

Explorer les décimales de $ π$ est assez rigolo: on y trouve tout ce qu'on veut.

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}

qui permet de trouver James \textit{Bond}:

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


Votre code secret:

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



Mais tout  ceci est  un peu  du bricolage  au petit  bonheur: nous  avons besoin
d'effectuer des tests avec un peu plus de méthode.

N'oubliez  pas que  passer des  tests signifie  qu'on n'a  pas encore  trouvé la
faille.

Nous nous contenterons  d'étudier des tests \textit{empiriques}  qui implique la
manipulation de groupes de nombres par  la machine. Les tests théoriques sont un
peu plus compliqués à étudier: vous les verrez quand vous serez plus grands...

\begin{aparte}
Quand on peut reconnaître des motifs dans  une série de nombre, cela nous permet
de compresser l'information. La notion moderne permettant de mesurer le degré de
hasard  d'une suite  de nombre  fait référence  à cette  notion informatique  de
compression: une suite est  aléatoire si on ne peut pas  la compresser plus mais
c'est assez compliqué à mettre en \oe  uvre. Nous allons explorer des voies plus
classiques.
\end{aparte}


\subsection{Rappel express: démonbrement for dummies}


\subsubsection{Nombre de permutations}


  \begin{definition}[Permutation]
    Soit  E  un ensemble.  Une  permutation  de  E est  une  application
    bijective  de E  sur  E. On  note  $\mathfrak{S}(E)$ l'ensemble  des
    permutations de E.
  \end{definition}



Généralement, on  note les permutations  sous forme d'une matrice  où la
première  ligne correspond aux  éléments de  E et  où la  deuxième ligne
correspond aux images des éléments de E.


Par exemple, les permutations de  $\bigl\{a,b,c\bigr\}$ sont:


$$
\begin{pmatrix}
  a&b&c\\
  a&b&c
\end{pmatrix}
\begin{pmatrix}
  a&b&c\\
  a&c&b
\end{pmatrix}
\begin{pmatrix}
  a&b&c\\
  b&a&c
\end{pmatrix}
\begin{pmatrix}
  a&b&c\\
  b&c&a
\end{pmatrix}
\begin{pmatrix}
  a&b&c\\
  c&a&b
\end{pmatrix}
\begin{pmatrix}
  a&b&c\\
  c&b&a
\end{pmatrix}
$$

On peut même se contenter d'écrire $(a,b,c)$,
$(a,c,b)$, $(b,a,c)$,  $(b,c,a)$, $(c,a,b)$,  $(c,b,a)$ si l'on  est sûr
que la première ligne est toujours $(a,b,c)$. 



\begin{theoreme}[Nombre de permutations]
    Il y a $n!$ permutations d'un ensemble de $n$ éléments.
    \end{theoreme}




La démonstration  s'effectue par  récurrence. Il y  a bien sûr  1! façon
de permuter 1 élément.

On peut  donc supposer qu'il existe au  moins un entier $k$  tel qu'il y
ait $k!$ permutations d'un ensemble à $k$ éléments.

Considérons un ensemble à $k+1$ éléments. On en choisit 1~:~il y a $k+1$
choix possibles. Ensuite, il  s'agit d'ordonner les $k$ éléments restant
ce qui laisse $k!$ possibilités.

Il y a donc finalement $(k+1)\times k!=(k+1)!$ permutations au total.


On retrouve  dans l'exemple précédent  qu'il y a $3!=6$  permutations de
$\bigl\{a,b,c\bigr\}$.


{On conviendra que $0!=1$.}

On  a déjà rencontré  les permutations  lors de  notre découverte  de la
cryptographie.  Elles  jouent  également  un  rôle  important  dans  les
algorithmes  de  tri par  exemple  et  aussi  dans certains  algorithmes
concernant les  graphes que vous  étudierez en deuxième année,  dans les
mélanges  de cartes,  dans l'étude  du  Rubik's cube,  et bien  d'autres
domaines encore...


\begin{remarque}[Formule de \textsc{Stirling}]
  Pour $n$ \og grand\fg{}, on peut estimer que:

  $$n! \displaystyle\underset{+\infty}\sim \sqrt{2\pi n}\left(\frac{n}{\mathrm{e}}\right)^n$$



\end{remarque}

\subsubsection{Nombre d'applications injectives - arrangements sans répétitions}



Une source veut envoyer à chacun de ses cinq clients 
un fichier différent parmi les vingt-six situés dans un certain répertoire.

Combien de possibilités a la source pour envoyer un fichier à chacun des
26 clients?

On peut modéliser cette situation: il s'agit de compter les applications injectives
(pourquoi \og injectives\fg{}?)
de l'ensemble E des clients vers l'ensemble F des fichiers.  Il ne peut y
avoir  répétition donc  il y  a  26 choix  de fichiers  pour le  premier
client,  25 pour  le deuxième,  etc.   ce qui  donne $26\times  25\times
24\times 22\times 21$ possibilités.

On peut généraliser.

\begin{definition}[Arrangement sans répétition]
 Une  application injective  d'un ensemble  E  de cardinal  $p$ dans  un
 ensemble F de cardinal $n$ (avec $p \leqslant n$) est appelée un arrangement sans répétition
 de $p$ parmi $n$.
\end{definition}


Un exemple fameux est la  recherche de tiercés dans l'ordre (sans ex-\ae
quo...): pourquoi?




Nous pouvons formuler cette propriété plus synthétiquement. En
effet
$$A_n^p=n(n-1)(n-2)\cdots(n-p+1)\times
\frac{(n-p)(n-p-1)(n-p-2)\times\cdots\times 2\times
1}{(n-p)(n-p-1)(n-p-2)\times\cdots\times 2\times
1}=\frac{n!}{(n-p)!}$$ d'où


\begin{theoreme}[Nombre d'arrangements]
  Le nombre d'arrangements sans répétition de $p$ parmi $n$ est 
$$A_n^p =n(n-1)(n-2)\cdots(n-p+1)= \frac{n!}{(n-p)!}$$
\end{theoreme}

Preuve?



\subsubsection{Combinaisons sans répétition}


Il n'y a pas assez de gagnants au loto. Les règles en sont donc
modifiées. Il s'agit maintenant de trouver 3 numéros parmi 5.
Combien y a-t-il de grilles (combinaisons) possibles~?

Par exemple, on pourrait dire que j'ai cinq manières de choisir le
premier numéro, quatre choix pour le deuxième et trois choix pour
le troisième, donc il y a $5\times 4\times 3$ grilles différentes
mais  dans  ce cas,  je  compte des  3-listes  ordonnées  alors que  les
3-listes  $(1,2,3)$  et $(3,2,1)$  correspondent  à  la  même grille  ou
combinaison $\bigl\{1,2,3\bigr\}$.  

 


Posons une petite définition pour clarifier les débats. Donnons en
fait un nom à une grille du loto, c'est à dire à un sous-ensemble
(une partie) contenant $p$ éléments d'un plus grand ensemble
contenant $n$ éléments.


\begin{definition}[Combinaison sans répétition]
    Soit $n$ et $p$ deux entiers naturels et $E$ un ensemble contenant $n$ éléments. Un sous-ensemble de $E$ contenant $p$
éléments est appelé  une \textbf{combinaison} de $p$ éléments  de $E$ ou
encore une {$\boldmath p\unboldmath$}\textbf{-combinaison} d'éléments de
\unboldmath${E}$.
    \end{definition}

Or ce qui nous intéresse, c'est le nombre de ces combinaisons,
donc introduisons une notation:


\begin{definition}[Nombre de combinaisons sans répétitions]
     Le nombre de $p$-combinaisons d'un ensemble E contenant $n$ éléments
     est noté ${E\choose p}$ ou encore $C_{|E|}^p=C_n^p$
    \end{definition}

Revenons à notre mini-loto. Considérons une grille quelconque
(i.e. une 3-combinaison de l'ensemble des 5 numéros)~: par
exemple $\{2,4,5\}$. Nous  avons vu dans un paragraphe précédent
qu'il y a $3!$ facons d'ordonner ces nombres. Finalement, il y a
$C_5^3  \times  3!$ suites  de  3  nombres  ordonnées: c'est  le  nombre
d'arrangements de $p$ parmi $n$. Or nous en
avons comptées $5\times 4\times 3$ tout à l'heure. Nous en
déduisons finalement que
$$C_5^3=\frac{A_5^3}{3!}=\frac{5\times 4\times 3}{3!}$$

Il est alors possible de généraliser la formule suivante:


\begin{theoreme}[]
     $$C_n^p=\frac{A_n^p}{p!}=\frac{n\big(n-1\big)\big(n-2\big)\cdots\big(n-(p-1)\big)}{p!}=\frac{n!}{p!(n-p)!}$$
    \end{theoreme}

Preuve?




\subsubsection{Triangle de Pascal - Binôme de Newton}

%\subsection{Raisonnement calculatoire}

À l'aide des formules précédentes, on prouve facilement (faites-le~!) le
résultat suivant~:


\begin{theoreme}[]
    $$C_n^p=C_{n}^{n-p}$$
    \end{theoreme}





On établit ensuite, toujours par le calcul, la relation suivante, dite \textbf{Relation de Pascal} même si les mathématiciens chinois l'avaient
mise en évidence avant lui~:


\begin{theoreme}[Relation de \textsc{Pascal}]\label{fpascal}
     $$C_{n}^{p}=C_{n-1}^{p}+C_{n-1}^{p-1}$$
    \end{theoreme}


%\vspace{-6.2cm}
\setindent{0cm}
\begin{flushleft}
\begin{minipage}[t]{4.2cm}
%\begin{figure}
  \includegraphics[width=3cm]{pascal500}
%\end{figure}
\end{minipage}
\end{flushleft}
\setindent{\indentationcours}
\vspace{-2.5cm}
\begin{minipage}[t]{\linewidth}


\end{minipage}


Il est  possible de démontrer  cette formule à l'aide  d'un raisonnement
ensembliste~:~pour former  des groupes de $p$ éléments  dans un ensemble
en contenant $n$, on distingue un élément $n_0$ quelconque~:
\begin{itemize}
\item soit le groupe le contient et alors il y a $C_{n-1}^{p-1}$
  choix des $p-1$ éléments distincts de $n_0$ parmi les $n-1$ restant~;
\item soit  le groupe  ne le contient  pas et  il faut donc  choisir $p$
  éléments parmi  les $n-1$  éléments distincts de  $n_0$~:~il y  a donc
  cette fois $C_{n-1}^{p}$.
\end{itemize}


Cette   relation  permet   de  démontrer   la  formule   du   binôme  de
Newton (que nous admettrons):

\begin{theoreme}[Formule du binôme]
 Soit $\bba$ un anneau commutatif. Dans $\bba[X]$, pour tout entier naturel non nul $n$:

$$(1+X)^n=\displaystyle\sum_{k=0}^{n}C_n^kX^k$$

et plus généralement:

$$\forall (a,b)\in\bba^2,\quad (a+b)^n=\displaystyle\sum_{k=0}^{n}C_n^ka^kb^{n-k}$$
\end{theoreme}







































\vfill

\eject




%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\modeexercice
\section{RECHERCHES}


\begin{exercice}[Middle-square (1)]

  Quel nombre suit \num{1010101010} par la méthode du \textit{middle-square}.
\end{exercice}




\begin{exercice}[Permutations]
On   peut   être   amené   à  rechercher   les   \textit{cycles}   d'une
permutations.   Il  est   aisé  de   les  représenter   à   l'aide  de
\textit{graphes} orientés...cycliques.

Par exemple, si l'on considère la permutation:

$$
\begin{pmatrix}
1&2&3&4&5&6&7&8&9\\
4&8&3&5&2&9&6&1&7
\end{pmatrix}
$$


alors on trouve trois cycles:


\begin{center}
  \begin{tikzpicture}
    \SetGraphUnit{1.2}
    \Vertices{circle}{1,4,5,2,8};
    \Edges[style={->}](1,4,5,2,8,1);
  \end{tikzpicture}

\hspace{1cm}

\begin{tikzpicture}
  \SetGraphUnit{1.2}
  \Vertices{circle}{6,7,9};
  \Edges[style={->}](6,7,9,6);
  \end{tikzpicture}

\hspace{1cm}

\begin{tikzpicture}
  \SetGraphUnit{1.2}
  \Vertex{3};
  \Loop[dist=1cm,dir=NO,style={->}](3);
  \end{tikzpicture}

\end{center}


\begin{enumerate}

\item Décomposez $\pi=(2\ 1\ 3\ 5\ 4\ 7\ 9\ 6\ 8)$ en cycles.

\item La \textit{longueur} d'un cycle est le nombre de ses sommets.

Soit $p$  une permutation. On  note $p^k=p\circ p^{k-1}$  avec $p^0={\rm
id}$, la permutation identité.

 Soit  $p\in\mathfrak{S}_n$. On  définit  une  relation $\RR$  sur
      $E=\{1,2,...,n\}$  par:  $$i \RR  j  \Leftrightarrow  \exists k  \in
      \bbn^\star, \ p^k(i)=j$$

Est-ce que $\RR$ est une relation d'équivalence? Quels sont ses classes?



\item L'\textit{ordre}  d'une permutation  est  le plus  petit entier  naturel
strictement positif $k$ tel que $p^k={\rm id}$.

Déterminez l'ordre  de $\pi$.  Est-ce que toute  permutation a  un ordre
fini? Comment le calculer?
\end{enumerate}





\end{exercice}







\begin{exercice}[Middle-square (2)]\label{knuth::3.1.6}
Observons quelques suites obtenues par  ma méthode du middle-square en modifiant
la dernière ligne de \lstinline{longVonNeumann} ainsi: \lstinline{return (L,k)}. 



\begin{pythoncode}
[([500,0], 0),
 ([501,100,0], 0),
 ([502,200,0], 0),
 ([503,300,0], 0),
 ([504,401,80,40,60], 60),
 ([505,502,200,0], 0),
 ([506,603,360,960,160,560], 360),
 ([507,704,561,472,278,728,998,600,0], 0),
 ([508,806,963,736,169,856,273,452,430,490,10], 10),
 ([509,908,446,891,388,54,91,28,78,8,6,3,0], 0),
 ([510,10], 10),
 ([511,112,254,451,340,560,360,960,160], 560),
 ([512,214,579,524,457,884,145,102,40,60], 60),
 ([513,316,985,22,48,30,90,10], 10),
 ([514,419,556,913,356,673,292,526,667,488,814,259,708,126,587,456,793,884,145,102,40,60], 60),
 ([515,522,248,150,250], 250),
 ([516,625,62,84,5,2,0], 0),
 ([517,728,998,600,0], 0),
 ([518,832,222,928,118,392,366,395,602,240,760], 760),
 ([519,936,609,88,74,47,20,40,60], 60),
 ([520,40,60], 60),
 ([521,144,73,32,2,0], 0),
 ([522,248,150,250], 250),
 ([523,352,390,210,410,810,610], 210),
 ([524,457,884,145,102,40,60], 60),
 ([525,562,584,105,102,40,60], 60),
 ([526,667,488,814,259,708,126,587,456,793,884,145,102,40,60], 60),
 ([527,772,598,760], 760),
 ([528,878,88,74,47,20,40,60], 60),
 ([529,984,825,62,84,5,2,0], 0),
 ([530,90,10], 10),
 ([531,196,841,728,998,600,0], 0),
 ([532,302,120,440,360,960,160,560], 360),
 ([533,408,646,731,436,9,8,6,3,0], 0),
 ([534,515,522,248,150,250], 250),
 ([535,622,688,334,155,402,160,560,360,960], 160),
 ([536,729,144,73,32,2,0], 0),
 ([537,836,889,32,2,0], 0),
 ([538,944,113,276,617,68,62,84,5,2,0], 0),
 ([539,52,70,90,10], 10),
 ([540,160,560,360,960], 160),
 ([541,268,182,312,734,875,562,584,105,102,40,60], 60),
 ([542,376,137,876,737,316,985,22,48,30,90,10], 10),
 ([543,484,425,62,84,5,2,0], 0),
 ([544,593,164,689,472,278,728,998,600,0], 0),
 ([545,702,280,840,560,360,960,160], 560),
 ([546,811,772,598,760], 760),
 ([547,920,640,960,160,560,360], 960),
 ([548,30,90,10], 10),
 ([549,140,960,160,560,360], 960)]
\end{pythoncode}

Essayons  de  généraliser.  Supposons  que  l'on  veuille  engendrer  une  suite
d'entiers $ X_0,X_1,...$ tous compris entre 0  et un certain entier $ m$. Soit $
f$ une fonction  \textit{stable} sur $\llbracket 0,m\rrbracket$.  On fabrique la
suite $ (X_n)$ selon le mécanisme $ X_{n+1}=f(X_n)$.

\begin{enumerate}
\item Est-ce que  la méthode \textit{middle-square} vérifie  ces conditions? Que
  vaut $ m$ dans le cas précédent?
\item Démontrez que la suite est forcément périodique, c'est-à-dire qu'il existe
  deux entiers $ μ$ et $ λ$ tels que les entiers:
$$X_0,X_1,...,X_{μ},...,X_{μ+λ-1} $$

soient distincts  mais que $X_{n+λ}=X_n$  dès que $  n \geqslant μ$  (la période
est  alors $  λ$). Essayez  d'abord de  déterminer $  λ$ et  $ μ$  dans les  cas
observés. Est-ce que vous  pouvez trouver les valeurs maxi et mini de  $ μ$ et $
λ$?
\item Démontrez qu'il exste un entier $n>0$ tel que $ X_n=X_{2n}$ et que le plus
  petit $ n$ est compris entre $μ$ et $ μ+λ$.
\item Déterminez un algorithme qui calcule $ λ$ et $ μ$ pour toute fonction $ f$
  et toute graine $ X_0$ utilisant  seulement $O(λ+μ)$ étapes et traduisez-le en
  Python. 

  \begin{pythoncode}
In [62]: trouvePeriode(prendMilieu,511)
Out[62]: ([511,112,254,451,340,560,360,960,160], 560, 'mu = 5, lambda = 4')
  \end{pythoncode}

On  pourra par  exemple  tirer  parti du  type  \lstinline{dict}  de Python.  Un
dictionnaire est un ensemble de couples (clé,valeur) indexé par la clé.

Par exemple:

\begin{pythoncode}
In [67]: rep
Out[67]: {'A': 45, 'B': 72, 'Z': 789, 'C': 93}

In [68]: rep = {'A':45, 'B':72 ,'C' :93}

In [69]: rep['B']
Out[69]: 72

In [70]: rep['Z'] = 789

In [71]: rep
Out[71]: {'A': 45, 'B': 72, 'Z': 789, 'C': 93}
\end{pythoncode}


\end{enumerate}
  
\end{exercice}


% \begin{exercice}[Une pensée pour LL]
%   A sequence  generated as in \ref{knuth::3.1.6}  must begin to repeat  after at
%   most $ m$ values have been generated. Suppose we generalize the method so that
%   $ X_{n+1}$ depends on $ X_{n-1}$ as well as on $ X_n$; formally, let $ f(x,y)$
%   be a  function such that $  0 \leqslant x,y  <m$ implies $ 0  \leqslant f(x,y)
%   <m$. The sequence  is constructed by selecting $ X_0$  and $ X_1$ arbitrarily,
%   and then letting

% $$X_{n+1}=f(X_n,X_{n-1})\quad \text{ for n >0}$$

% What is the maximum period conceivably attainable in this case?
% \end{exercice}


\begin{exercice}[GCL: disparition de la graine]

Dans le premier  exemple de GCL du  cours, $ X_0=X_4$. Donner  un exemple (voire
une infinité...)  avec $  m=10$ tel que  $ X_0$ n'apparaît  plus jamais  dans la
liste.

\tikz\node[rotate=180]{\tiny Pensez parité}
  
\end{exercice}

\begin{exercice}[GCL: cas particuliers]
\begin{enumerate}

\item Que pensez-vous d'un GCL où $ a=0$ ou $ a=1$?

\item On note $ b=a-1$.

Démontrez que  pour tous  entiers naturels  $ k$  et $  n$, et  tout entier  $ a
\geqslant 2$, on a:

$$X_{n+k}=(a^kX_n + (a^k-1)c/b) \mod m$$

\item Que se passe-t-il si $ m$ est une puissance de 2 et si $a$ est pair?
  



\end{enumerate}
\end{exercice}




\begin{exercice}[/dev/urandom et /dev/random]
  Regarder l'aide de \mintinline{bash}{/dev/random} et \mintinline{bash}{/dev/urandom} puis l'aide de
  \mintinline{bash}{od}.

Que fait \mintinline{bash}{od -An -N 1 -t u2 /dev/random}?

Créez n  fichier texte qui contient  100000 tirages de nombres  aléatoires (quel
format?) et tracez l'histogramme correspondant puis animez-le...

Un peu d'aide:

\begin{pythoncode}
import os
import numpy as np
import matplotlib.pyplot as plt

def tirage_uni(i):
    fichier_alea = open('fichier_alea.dat', 'w+')
    os.system('od ????????? | cat > fichier_alea.dat')
    tirage = np.array(fichier_alea.read().split()).astype(np.int)
    plt.hist(tirage, bins=256, histtype='step', normed=True)
    fichier_alea.close()


for k in range(2,8):
    fig = plt.figure()
    tirage_uni(k)
    plt.savefig('./animHistoRand' + str(k) + '.jpg')
    plt.close() 

os.system('animate animHistoRand*.jpg') #nécessite imagemagick. On freine avec >
\end{pythoncode}

Expliquez et complétez les différentes lignes ainsi que les résultats obtenus.

Adaptez ce code pour tester le générateur RANDU utilisé dans les années 1960:

$$
X_{n+1} \equiv (65539 \times X_n) \mod 2^{31}$$

avec $X_0$ impair.

Que pensez-vous de RANDU?  Il a été introduit à l'époque  car $65539=2^{16} + 3$
ce qui facilite les calculs: pourquoi?

Calculez $m^2$ modulo $2^{31}$ en fonction de $m$.

Déduisez-en une relation simple entre $X_{n+2}$, $X^{n+1}$ et $X_n$.

Si on normalise les $X_n$ en posant $r_n=X_n/2^{31}$ qu'obtient-on?

Si on change $r_n$  et $r_{n+1}$ de 1\%, quel est  l'amplitude du changement sur
$r_{n+2}$? Que peut-on en dire point de vue sécurité?
\end{exercice}









\begin{exercice}[Comment tricher au Poker en ligne...]
  
...quand les programmeurs ne sont pas des inforMATHiciens :-)


Voici   l'implémentation   de    \lstinline{Random()}   sur   les   compilateurs
\textit{Borland}:

\begin{ccode}
long long RandSeed = #### ;

unsigned long Random(long max)
{
 long long x ;
 double i ;
 unsigned long final ;
 x = 0xffffffff;
 x += 1 ;

 RandSeed *= ((long long)134775813);
 RandSeed += 1 ;
 RandSeed = RandSeed % x ;
 i = ((double)RandSeed) / (double)0xffffffff ;
 final = (long) (max * i) ;

 return (unsigned long)final;
}
\end{ccode}

Commentez...

Souvent, le  graine utilisée est  la valeur  renvoyée par l'horloge  du système,
dans le cas du jeu de Poker de \textit{PlanetPoker}, il s'agissait du nombre de
millisecondes écoulées depuis minuit.


L'algo de  mélange partait d'un  jeu de 52  cartes ordonné: combien  de mélanges
sont possibles? Cela fait à peu près combien exprimé en puissance de 2?

Mais à  chaque mélange,  le jeu est  ré-ordonné et on  choisit une  graine selon
l'algo \lstinline{Random()}: combien de mélanges sont alors en fait possibles?

Il faut  aussi tenir  compte du  choix de  la graine  comme temps  écoulé depuis
minuit. Si  on se  donne une fourchette  de 3 minutes,  combien de  mélanges sont
maintenant possibles?

Comment allez-vous  organiser votre appli  de triche  sachant que vous  jouez au
\textit{Texas  Hold'em}:  vous recevez  deux  cartes  et  il  y a  trois  cartes
affichées sur la table?





\end{exercice}





\begin{exercice}[Poker sur Python]


 Une main au poker est constituée de 5 cartes tirées d'un jeu de 52
 cartes. Deux lettres identiques (par exemple XX) correspondent à deux
 cartes de même hauteur (par exemple deux dames). 


\begin{enumerate}
\item 

\illmpl{
\begin{enumerate}
\item Combien y a-t-il de mains contenant des carrés (XXXXY) ?  
\item des fulls (XXXYY) ?
\item des brelans (XXXYZ) ? 
\item des doubles paires (XXYYZ) ? 
\item des paires (XXYZA) ?
\item des quintes (cinq cartes dont les niveaux se suivent)?
\item des couleurs (5 cartes de la même couleurs quine soient pas des quintes)?
\item des quintes flush (des quintes d'une même couleur)?
\end{enumerate}
}{pokerMains}{0.6}{0.3}
\item 

Nous pouvons calculer tout ça avec Python (ou Haskell ou ...)

On rentre d'abord la liste des symboles et la liste des valeurs: 

\begin{pythoncode}
# Liste des symboles des cartes
symboles = ['Trefle','Carreau','Coeur','Pique']
 
# Liste des valeurs dans un jeu de 32 cartes
vals_32 = ['Sept','Huit','Neuf','Dix','Valet','Dame','Roi','As']
 
# Ensemble des valeurs dans un jeu de 52 cartes
vals_52 = ['Deux','Trois','Quatre','Cinq','Six'] + vals_32
\end{pythoncode}

Il s'agit  ensuite de  créer l'ensemble  de toutes les  mains possibles  de cinq
cartes. 

On pourrait faire ça:

\begin{pythoncode}
[(valeur,couleur) for valeur in vals_32 for couleur in symboles]
\end{pythoncode}

mais on va plutôt utiliser des itérateurs: c'est plus rapide.

\begin{pythoncode}
from itertools import product
 
def jeu(vals):
    """Ensemble des cartes selon les valeurs choisies (2 -> As ou 7 -> As) """
    return product(vals,symboles)
\end{pythoncode}


On lit un peu la doc:

\begin{pythoncode}
itertools.product(*iterables, repeat=1)
 
Cartesian product of input iterables.
 
Equivalent to nested for-loops in a generator expression. 
For example, product(A, B) returns the same as ((x,y) for x in A for y in B).
 
The nested loops cycle like an odometer with the rightmost element advancing 
on every iteration. 
This pattern creates a lexicographic ordering so that if the input's iterables 
are sorted, the product tuples are emitted in sorted order.
 
To compute the product of an iterable with itself, specify the number of 
repetitions with the optional repeat keyword argument. 
For example, product(A, repeat=4) means the same as product(A, A, A, A).
 
This function is equivalent to the following code, except that the actual 
implementation does not build up intermediate results in memory:
 
    def product(*args, repeat=1):
        # product('ABCD', 'xy') --> Ax Ay Bx By Cx Cy Dx Dy
        # product(range(2), repeat=3) --> 000 001 010 011 100 101 110 111
        pools = [tuple(pool) for pool in args] * repeat
        result = [[]]
        for pool in pools:
            result = [x+[y] for x in result for y in pool]
        for prod in result:
            yield tuple(prod)
\end{pythoncode}



Python lorgne un peu sur l'évaluation parésseuse de Haskell.

Pour   créer   l'ensemble   des   mains    de   5   cartes,   on   va   utiliser
\lstinline{combinations}:

\begin{pythoncode}
itertools.combinations(iterable, r)
 
Return r length subsequences of elements from the input iterable.
 
Combinations are emitted in lexicographic sort order. So, if the input iterable is sorted, 
the combination tuples will be produced in sorted order.
 
Elements are treated as unique based on their position, not on their value. 
So if the input elements are unique, there will be no repeat values in each combination.
 
The number of items returned is n! / r! / (n-r)! when 0 <= r <= n or zero when r > n.
\end{pythoncode}

\lstinline{itertools} contient  aussi une  fonction \lstinline{map}  qui reprend
les caractéristiques du \lstinline{map} de Haskell.

Cela nous permet d'avoir les hauteurs d'une main:

\begin{pythoncode}
def hauteurs(main):
    """Liste des hauteurs d'une main"""
    return map(hauteur,main)
\end{pythoncode}


Ensuite, il faut compter les sorties  identiques. Il existe un outil Python tout
fait pour ça : la fonction Counter de la bibliothèque collections. Par exemple: 


\begin{pythoncode}
In [62]: from collections import Counter
 
In [63]: Counter("maman papa")
Out[63]: Counter({'a': 4, 'p': 2, 'm': 2, ' ': 1, 'n': 1})
\end{pythoncode}


Un carré au poker  contient donc un 4 dans son ensemble  de valeurs (obtenu avec
la méthode values en Python).  


\begin{pythoncode}
def est_carre(main):
    """Teste si une main contient quatre cartes de même hauteur"""
    return 4 in Counter(hauteurs(main)).values()
\end{pythoncode}


On aurait pu faire autrement:

\begin{pythoncode}
def est_carre2(main):
    return {1,4} == set(Counter(hauteurs(main)).values())

def est_carre3(main):
    return [1,4] == sorted(list(Counter(hauteurs(main)).values()))
\end{pythoncode}

Déterminez les fonctions pour les full houses, double-paires, brelans, paires.


\begin{pythoncode}
In [79]: compte_mains(est_full,vals_32)
Out[79]: 1344
 
In [80]: compte_mains(est_brelan,vals_32)
Out[80]: 10752
 
In [81]: compte_mains(est_double_paire,vals_32)
Out[81]: 24192
 
In [82]: compte_mains(est_paire,vals_32)
Out[82]: 107520
\end{pythoncode}


Il ne reste plus qu'à s'occuper des couleurs et des quintes en faisant attention
aux quintes  flush : une couleur  ne doit pas être  une quinte en même  temps et
vice-versa. Pour trouver les quintes, on peut utiliser islice qui, comme son nom
l'indique, coupe un itérateur en tranches: 


\begin{pythoncode}
 itertools.islice(iterable, start, stop[, step])
 
 Make an iterator that returns selected elements from the iterable. 
 If start is non-zero, then elements from the iterable are skipped until 
 start is reached. 
 Afterward, elements are returned consecutively unless step is set higher 
 than one which results in items being skipped. If stop is None, then 
 iteration continues until the iterator is exhausted, if at all; otherwise, 
 it stops at the specified position. Unlike regular slicing, islice() does 
 not support negative values for start, stop, or step. Can be used to extract 
 related fields from data where the internal structure has been flattened 
 (for example, a multi-line report may list a name field on every third line). 
 
 Equivalent to:
 
    def islice(iterable, *args):
        # islice('ABCDEFG', 2) --> A B
        # islice('ABCDEFG', 2, 4) --> C D
        # islice('ABCDEFG', 2, None) --> C D E F G
        # islice('ABCDEFG', 0, None, 2) --> A C E G
        s = slice(*args)
        it = iter(range(s.start or 0, s.stop or sys.maxsize, s.step or 1))
        nexti = next(it)
        for i, element in enumerate(iterable):
            if i == nexti:
                yield element
                nexti = next(it)
 
    If start is None, then iteration starts at zero. 
    If step is None, then the step defaults to one.
\end{pythoncode}

Par exemple:

\begin{pythoncode}
def suites(vals):
    """Ensemble d'ensembles de hauteurs de mains contenant une quinte"""
    return [set(islice(vals,k,k+5,1)) for k in range(len(vals) - 4)] 
\end{pythoncode}


et vous devez obtenir:

\begin{pythoncode}
In [84]: compte_mains(est_quinte_32,vals_32)
Out[84]: 4080
 
In [85]: compte_mains(est_couleur_32,vals_32)
Out[85]: 208
 
In [86]: compte_mains(est_flush_32,vals_32)
Out[86]: 16
\end{pythoncode}






\end{enumerate}

Vous pouvez vous amuser à faire quelque chose de semblable (en mieux) en Haskell...

\end{exercice}






\begin{exercice}[Téléphone]

%\vspace{-6.2cm}
\setindent{0cm}
\begin{flushleft}
\begin{minipage}[t]{3cm}
%\begin{figure}
  \includegraphics[width=3cm]{telephone}
%\end{figure}
\end{minipage}
\end{flushleft}
\setindent{\indentationcours}
\vspace{-2.5cm}
\begin{minipage}[t]{\linewidth}


\end{minipage}
On suppose que les numéros  de téléphone sont de la forme 0Z-YX-XX-XX-XX
avec X un nombre entier entre 0 et 9, Y un nombre entier entre 2 et 9 et
Z un entier entre 1 et 9.

En France, il  y a environ 35 millions d'abonnements  à un \og fixe\fg{}
et  79 millions  à un  \og mobile\fg{}  (données du  deuxième trimestre
2014).

Est-on tranquille? 

Supposons qu'en Syldavie, il y ait 109 millions d'abonnés à un téléphone fixe et que
le Y soit fixé par opérateur et qu'il n'y ait que deux opérateurs. De
combien de zones a-t-on besoin? 
\end{exercice}


\begin{exercice}[Barbie]

%\vspace{-6.2cm}
\setindent{0cm}
\begin{flushleft}
\begin{minipage}[t]{3cm}
%\begin{figure}
  \includegraphics[width=3cm]{chador}
%\end{figure}
\end{minipage}
\end{flushleft}
\setindent{\indentationcours}
\vspace{-3.4cm}
\begin{minipage}[t]{\linewidth}


\end{minipage}
  Un  étudiant de l'\textsc{Iut}  d'informatique de  Klow en  Syldavie a
  reçu pour Noël sept Barbie et sept séries de dix robes de couleurs différentes.
Il habille chaque Barbie d'une de ces robes.
\begin{enumerate}
\item Combien y a-t-il d'habillages possibles selon la couleur?
\item Combien y  a-t-il d'habillages de sorte que  chaque Barbie ait une
      robe de couleur différente des autres?
\item Combien  y a-t-il  d'habillages de sorte  qu'au moins  deux Barbie
      aient une robe de la même couleur?
\item Combien  y a-t-il  d'habillages de sorte  qu'exactement  deux Barbie
      aient une robe de la même couleur?

\end{enumerate}
\end{exercice}


\begin{exercice}[Jus]
  Lors de la soirée d'intégration de l'\textsc{Iut} de Klow, 9 étudiants
  ont bu un  verre d'eau, 25 un verre  de jus de tomate, 14  un verre de
  jus de betterave, 7 un verre de  jus de tomate et un verre d'eau, 4 un
  verre d'eau  et un verre de  jus de betterave,  10 un verre de  jus de
  betterave  et  un  verre  de  jus  de  tomate.  Les  étudiants  d'Info
  s'occupaient des boissons  et ceux de GEA des  entrées or ces derniers
  ont  perdu  leur liste  et  ne  savant  plus combien  d'étudiants  ont
  participé à la soirée.  Les étudiants d'Info, connaissant les
  statistiques sur les  consommations de boissons, pourront-ils corriger
  la gaffe  des GEA  sachant également  que lors de  la valse,  tous les
  participants dansaient en couple ?
\end{exercice}


\begin{exercice}[k-uplets]
   Soit $E$ un ensemble fini non vide de cardinal $n$.
\begin{itemize}
\item[a)] Combien y-a-t-il de parties de $E$ formées de $k$ éléments?
 \item[b)] Combien y-a-t-il de $k$-uplets d'éléments de $E$?
  \item[c)]  Combien  y-a-t-il  de  $k$-uplets d'éléments  deux  à  deux
distincts de $E$?
   \item[d)]  Combien  y-a-t-il de  $k$-uplets  d'éléments  deux à  deux
distincts de  $E$, tel que  le premier élément  est le plus petit  et le
dernier élément est le plus grand?
\item[e)] Combien y-a-t-il de $k$-uplets d'éléments de $E$ ordonnés dans
l'ordre strictement croissant?
\end{itemize} 

Déterminez  des fonctions  Python qui  effectuent ces  calculs en  fonction d'un
ensemble donné en paramètre.

\end{exercice}


\begin{exercice}[Arrangements]
  Comment modéliser le tiercé  brillamment organisé par le \textsc{Pmu}?
  (Qui est E? Qui est F? Quelle est l'application de E dans F?)
Combien y a-t-il  de tiercés possibles (sans ex-\ae  quo) dans
une course de 19 partants?

Modélisez  la recherche  du nombre  d'arrangements  de $p$  parmi $n$  à
l'aide d'un tirage de boules dans une urne.
\end{exercice}



\begin{exercice}[L'âge du capitaine]
  
 Le capitaine  des pompiers  de New-York est  marié et a  quatre enfants
 dont un mange un yaourt aux fruits tous les matins. Il ne fume pas, aime
 regarder des films de gladiateurs et réside \`a l'angle de la
 1\up{ère}
avenue et de  la 33\up{ème} rue. La caserne se trouve  \`a l'angle de la
9\up{ème} avenue et de la 40\up{ème} rue. Il s'y rend tous les jours \`a 
pied en sifflant \og $\mathfrak{O\ du\ schöner\ Westerwald}$\fg{} et sans perdre
de temps (i.e. dans le sens des numéros 
croissants aussi bien pour les rues que pour les avenues). Sachant qu'il
a commencé \`a travailler le jour  de ses 18 ans, et sachant qu'il n'est
jamais passé deux  fois par le m\^eme chemin,  qu'il boîte légèrement de
la  jambe  droite  après  avoir  participé au  championnat  d'Écosse  de
lancement d'enclume, qu'il est sourd  de l'oreille gauche depuis qu'il a
plongé dans  un lac gelé pour sauver  son petit frère John  qui était en
train de  se noyer après  que la glace  sur laquelle il  patinait craqua,
quel est l'\^age (maximum) du capitaine ?


\end{exercice}







\begin{exercice}[Mélange de cartes: épisode 1]


%\vspace{-6.2cm}
\setindent{0cm}
\begin{flushleft}
\begin{minipage}[t]{3cm}
%\begin{figure}
  \includegraphics[width=3cm]{melange}
%\end{figure}
\end{minipage}
\end{flushleft}
\setindent{\indentationcours}
\vspace{-2.6cm}
\begin{minipage}[t]{\linewidth}


\end{minipage}


On  dispose d'un  jeu de  52 cartes  et on  le mélange  en \textit{queue
d'aronde}:
% %\begin{figure}
% \begin{center}
%   \includegraphics[width=5cm]{melange}
% \end{center}
% %\end{figure}
on divise le jeu en deux parties de 26 cartes et on intercale les cartes
de  la moitié  gauche dans  la moitié  droite sans  modifier  l'ordre de
chaque partie bien sûr.
Est-ce que  quatre mélanges en  queue d'aronde successifs  permettent de
fournir un ordre aléatoire des cartes? 

Il  faudrait préciser d'abord  cette notion:  combien y  a-t-il d'ordres
possibles des cartes?

Existe-t-il  alors des  ordres qui  ne pourront  être obtenus  par notre
succession de mélanges?
i 
Pour répondre à cette question,  il faudrait calculer le nombre d'ordres
qu'on peut  obtenir par la succession de  quatre mélanges...Imaginez que
vous disposiez de 26 cartes bleues  et 26 rouges. Vous les mélangez avec
la  méthode  de  la  queue  d'aronde: pouvez-vous  reconstituer  le  jeu
initial? Combien y a-t-il alors d'ordres possibles après le premier mélange?
\end{exercice}



\begin{exercice}[Mélange de carte: le mélange de ASF Software]
  
Afin de convaincre  les utilsateurs que leur algorithme de  mélange était juste,
la société ASF Software, qui produit les logiciels utilisés par de nombreux sites
de jeu, avait publié cet algorithme:

\begin{pascalcode}
procedure TDeck.Shuffle;
var
    ctr: Byte;
    tmp: Byte;

    random_number: Byte;
begin
    { Fill the deck with unique cards }
    for ctr := 1 to 52 do
        Card[ctr] := ctr;

    { Generate a new seed based on the system clock }
    randomize;

    { Randomly rearrange each card }
    for ctr := 1 to 52 do begin
        random_number := random(51)+1;
        tmp := card[random_number];
        card[random_number] := card[ctr];
        card[ctr] := tmp;
    end;

    CurrentCard := 1;
    JustShuffled := True;
end;
\end{pascalcode}


\begin{enumerate}
\item  Considérez un  jeu de  3  cartes. Dressez  l'arbre de  tous les  mélanges
  possibles en suivant cet algorithme. Que remarquez-vous?
\item  Proposez  un   algorithme  qui  corrige  ce   problème.  Dressez  l'arbre
  correspondant pour un jeu de trois cartes.
\end{enumerate}
\end{exercice}









\begin{exercice}[Flavius Josèphe]


%\vspace{-6.2cm}
\setindent{0cm}
\begin{flushleft}
\begin{minipage}[t]{3cm}
%\begin{figure}
  \includegraphics[width=3.2cm]{quovadis}
%\end{figure}
\end{minipage}
\end{flushleft}
\setindent{\indentationcours}
\vspace{-3.1cm}
\begin{minipage}[t]{\linewidth}


\end{minipage}
  

Flavius Josèphe (37  - 100) ou plutôt Yossef  ben Matityahou HaCohen est
un  historien romain  d'origine juive  et de  langue grecque  et  qui ne
devait pas être trop mauvais en  mathématiques si on en croit la sinistre
anecdote suivante. Lors de  la première guerre judéo-romaine, Yossef fut
piégé dans une grotte avec 39 autres de ses compagnons en juillet 67. Ne voulant pas
devenir esclaves, ils mirent  au point un algorithme d'auto-destruction:
il s'agissait de se mettre en cercle et de se
numéroter de  1 à 40. Chaque  septième devait être tué  jusqu'à ce qu'il
n'en  reste plus  qu'un qui  devait alors  se suicider.  Ce  dernier fut
Yossef lui-même...et il ne se suicida  pas! Après deux ans de prison, il
fut libéré, il  entra au service des romains  comme interprète et acquit
la citoyenneté romaine deux ans plus tard.
Quel numéro portait Yossef? Créez un programme Python (ou Haskell..) qui donne l'ordre
des exécutions quelque soit le nombre de prisonniers et le nombre sinistre.



Dans une  autre situation (pour  ne pas  vous donner la  réponse quand
même...),  on  doit obtenir  avec  20  compagnons  et 6  comme  nombre
sinistre suite:

\begin{pythoncode}
La 1e victime est le no 6
La 2e victime est le no 12
La 3e victime est le no 18
La 4e victime est le no 4
La 5e victime est le no 11
La 6e victime est le no 19
La 7e victime est le no 7
La 8e victime est le no 15
La 9e victime est le no 3
La 10e victime est le no 14
La 11e victime est le no 5
La 12e victime est le no 17
La 13e victime est le no 10
La 14e victime est le no 8
La 15e victime est le no 2
La 16e victime est le no 9
La 17e victime est le no 16
La 18e victime est le no 13
La 19e victime est le no 1
Out[62]: 'Et le survivant est le no20'
\end{pythoncode}

Peut-on prévoir qui sera le survivant sans dresser de liste?





\end{exercice}






% \begin{exercice}[Dénombrer les Pour]
% Que vaut $k$ à la fin?
% \begin{multicols}{2}
%   \begin{algo}
%     \STATE{k\recoit{}0}
% \FOR{$i_1$}{1}{$n_1$}
% \FOR{$i_2$}{1}{$n_2$}
% \STATE{\hspace{1.5cm}$\vdots$}
% \FOR{$i_p$}{1}{$n_p$}
% \STATE{k\recoit{}k+1}
% \ENDFOR
% \ENDFOR
% \ENDFOR
% \RETURN{k}
%   \end{algo}

%  \begin{algo}
%     \STATE{k\recoit{}0}
% \FOR{$i_1$}{1}{$n_1$}
% \STATE{k\recoit{}k+1}
% \ENDFOR
% \FOR{$i_2$}{1}{$n_2$}
% \STATE{k\recoit{}k+1}
% \ENDFOR
% \STATE{\hspace{1.5cm}$\vdots$}
% \FOR{$i_p$}{1}{$n_p$}
% \STATE{k\recoit{}k+1}
% \ENDFOR
% \RETURN{k}
%   \end{algo}


% \end{multicols}


% \begin{multicols}{2}


%  \begin{algo}
%     \STATE{k\recoit{}0}
% \FOR{$i_1$}{1}{$n_1$}
% \STATE{k\recoit{}k+1}
% \FOR{$i_2$}{1}{$n_2$}
% \STATE{k\recoit{}k+1}
% \STATE{\hspace{1.5cm}$\vdots$}
% \FOR{$i_p$}{1}{$n_p$}
% \STATE{k\recoit{}k+1}

% \ENDFOR
% \ENDFOR
% \ENDFOR
% \RETURN{k}
%   \end{algo}

%  \begin{algo}
%     \STATE{k\recoit{}0}
% \FOR{$x$}{1}{$100$}
% \FOR{$y$}{1}{$x$}
% \FOR{$z$}{1}{$y$}
% \FOR{$t$}{1}{$z$}
% \STATE{k\recoit{}k+1}
% \ENDFOR
% \ENDFOR
% \ENDFOR
% \ENDFOR
% \RETURN{k}
%   \end{algo}



% \end{multicols}
% \end{exercice}


\modenormal
%%% Local Variables: 
%%% mode: latex
%%% TeX-master: "PolyProbas14"
%%% End: 
