\chapterimage{hasselhoff-0}
\chaptertext{L'une des  méthodes d'écritures d'algorithmes la  plus répandue est
  la  réduction: on  transforme  un gros  problème en  un  problème plus  simple
  utilisant une boîte noire.

La récursion en est un exemple. La méthode est simple:
\begin{itemize}
\item si l'instance du problème est suffisamment simple, on le résout directement;
\item sinon, on la réduit en une instance plus simple du même problème.
\end{itemize}

Il s'agit  simplement de simplifier  un problème et  ensuite de faire  appel aux
petits lutins récursifs qui font le boulot pour vous...

}

\chapter{Récursion, récurrence, itération}

\section{Récursion et itération linéaire}

Nous  allons étudier  le plus  classique des  problèmes: il  s'agit de
calculer la somme des entiers de 1 à un entier naturel $ n$ non nul donné.

La  \textit{spécification}  est immédiate:  on  crée  une fonction  ayant  pour
argument  l'entier   naturet  $  n$  et   renvoyant  l'entier  naturel
correspondant à la somme des entiers de 1 à $ n$.

Il reste à s'occuper de la \textit{réalisation}.

\subsection{Procédure et processus}

Appelons  $  S(n)$  la  somme  des  entiers   de  1  à  $  n$  avec  $
n\in\bbn\setminus \bigl\{0\bigr\}$.

On a $ S(1)=1$ et $ S(n) = n + S(n-1)$.

\begin{lstlisting}
def s1(n):
    if n == 1:
        return 1
    elif n > 1:
        return s1(n - 1) + n
    else:
        raise ValueError("l'argument doit être un entier naturel non nul")
\end{lstlisting}

Que  se passe-t-il  quand  on calcule  \texttt{s1(5)}?  On utilise  le
modèle de \textit{substitution}:



{\ttfamily
s1(5)\\
5 + s1(4)\\
5 + (4 + s1(3))\\
5 + (4 + (3 + s1(2)))\\
5 + (4 + (3 + (2 + s1(1))))\\
5 + (4 + (3 + (2 + 1)))\\
5 + (4 + (3 + 3))\\
5 + (4 + 6)\\
5 + 10\\
15
}


On commence par quatre expansions suivies de cinq réductions.

La  \textit{procédure} est  récursive  car syntaxiquement  \texttt{s1}
apparaît dans sa propre définition (\texttt{return s1(n - 1) + n}).

Le  \textit{processus} est  également récursif:  les évaluations  sont
retardées.  Intuitivement, cela  est le  cas car  on progresse  du cas
compliqué vers le cas simple: on \og descend\fg{} ici de $ n$ vers 1.
L'interpréteur doit \textit{empiler} les résultats des expansions tant
qu'il ne peut pas les réduire.
La taille de  la pile nécessaire étant proportionnelle  à l'argument $
n$, on dit qu'il s'agit d'un processus linéairement récursif.

\bigskip

On peut avoir une autre idée:  partir du cas simple et \og monter\fg{}
vers  le   cas  compliqué  (on   parle  dans  ce   cas  habituellement
d'\textit{induction}).

Ici, la somme vaut  0 puis on ajoute 1, puis on  ajoute au résultat 2,
puis on ajoute au résultat 3, etc jusqu'à atteindre $ n$.

Techniquement, on  entretient un  \textit{accumulateur} de  termes qui
évolue et un compteur qui va évoluer de 1 jusque $ n$.

L'accumulateur et le compteur évoluent selon la règle:

\begin{algo}
  accumulateur \recoit{} accumulateur + compteur\\
  compteur \recoit{} compteur + 1
\end{algo}

la  somme  cherchée  étant  la valeur  de  l'accumulateur  lorsque  le
compteur a dépassé $ n$.


\begin{lstlisting}
def s2(n):
    def s_iter(acc, compt):
        if compt > n:
            return acc
        else:
            return s_iter(acc + compt, compt + 1)
    return s_iter(0,1)
\end{lstlisting}


La procédure  \texttt{s\_iter} est  syntaxiquement récursive  car elle
est  définie  à  partir  d'elle-même  mais  le  processus  n'est  plus
récursif! les évaluations ne sont plus retardées:

{\ttfamily
s2(5)\\
s\_iter(0 , 1)\\
s\_iter(1 , 2)\\
s\_iter(3 , 3)\\
s\_iter(6 , 4)\\
s\_iter(10, 5)\\
s\_iter(15, 6)\\
15
}

Cette fois-ci, il  n'y a plus de phase d'expansion  suivie d'une phase
de réduction. À chaque étape, il  suffit de garder une trace des états
de  \texttt{acc}  et  \texttt{compt}.  On  parle  alors  de  processus
\textit{itératif}. 

En général, un processus itératif est un processus pouvant être décrit
par un nombre fixe de \textit{variables  d'état} et par une règle fixe
qui décrit l'évolution de chaque  variable à chaque étape du processus
ainsi qu'un éventuel test d'arrêt  qui indique sous quelles conditions
le processus doit s'arrêter. 

Ici, le  nombre d'étapes nécessaire  est proportionnel à la  taille de
l'argument $ n$. On parle de processus itératif linéaire.

En fait,  une autre manière  de distinguer un processus  itératif d'un
processu récursif  est de remarquer  que si le processus  itératif est
interrompu, on peut le relancer en donnant comme arguments les valeurs
des variables au moment de  l'interruption. Ce n'est pas possible pour
un processus  récursif car  l'interpréteur garde des  informations \og
cachées\fg{}  dans  une pile  non  accessibles  par les  variables  du
programme.


Attention!  Ici, les  deux procédures  sont syntaxiquement  récursives
mais les  processus sont  de nature  différentes. Cependant,  dans des
langages comme Pascal,  Ada, Python, un processus  itératif décrit par
une procédure récursive consommera malgré tout autant de mémoire qu'un
processus  récursif.   C'est  pourquoi  ces  langages   utilisent  des
\textit{boucles} (\texttt{for, while}).

\begin{lstlisting}
def s3(n):
    s = 0
    k = 1
    while k <= n:
        s += k
        k += 1
    return s

def s4(n):
    s = 0
    for k in range(1, n + 1):
        s += k
    return s
\end{lstlisting}
 
Python ne distingue pas les processus itératif et récursif lorsque les
procédures sont récursives:

\begin{lstlisting}
In [15]: %timeit s1(500)
10000 loops, best of 3: 106 μs per loop

In [16]: %timeit s2(500)
10000 loops, best of 3: 107 μs per loop

In [17]: %timeit s3(500)
10000 loops, best of 3: 27.2 μs per loop

In [18]: %timeit s4(500)
10000 loops, best of 3: 46.1 μs per loop
\end{lstlisting}

Ce n'est pas le cas d'Ocaml!

\caml

\begin{lstlisting}
let rec suma = function
      |1 -> 1
      |n -> n + (suma (n - 1));;

let sumb n =
  let rec siter acc compt =
    if compt > n then acc
    else siter (acc + compt) (compt + 1)
  in siter 0 1;;
\end{lstlisting}

qui donne:

\begin{lstlisting}
utop[1]> suma 1_000_000;;
Stack overflow during evaluation (looping recursion?).
utop[2]> sumb 100_000_000;;
- : int = 5000000050000000
\end{lstlisting}


\pythonc

Il y a des moyens plus directs  de calculer une somme avec Python mais
c'est un autre problème: 

\begin{lstlisting}
In [19]: %timeit sum(range(501))
100000 loops, best of 3: 7.39 μs per loop
\end{lstlisting}




\section{Récursions et itérations non linéaires}

\subsection{Fibonacci}

Tout le monde  connaît l'exemple classique de la suite  des nombres de
\textsc{Fibonacci} dans laquelle  chaque nombre est la  somme des deux
précédents:

$$0,1,1,2,3,5,8,13,21,34,... $$

On pense alors naturellement à:

\begin{lstlisting}
def F(n):
    if n == 0:
        return 0
    elif n == 1:
        return 1
    else:
        return F(n - 1) + F(n - 2)
\end{lstlisting}

et on observe:

\begin{lstlisting}
 In [19]: %timeit F(20)
100 loops, best of 3: 3.4 ms per loop

In [20]: %timeit F(25)
10 loops, best of 3: 36.7 ms per loop

In [21]: %timeit F(26)
10 loops, best of 3: 59.1 ms per loop

In [22]: %timeit F(27)
10 loops, best of 3: 95.9 ms per loop

In [23]: %timeit F(28)
10 loops, best of 3: 155 ms per loop
\end{lstlisting}

Construisez  les  appels générés  par  \texttt{F(5)}  sous forme  d'un
arbre. Des commentaires?


Mmmmm....

On peut avoir une autre idée en utilisant deux variables:

\begin{algo}
suivant \recoit{} suivant + courant \\
courant \recoit{} suivant
\end{algo}

Construisez  un  processus itératif  donnant  plus  efficacement le  $
n$-eme nombre de \textsc{Fibonacci} (avec et sans boucle).

\begin{lstlisting}
In [31]: %timeit Fi(27)
100000 loops, best of 3: 5.75 μs per loop

In [32]: %timeit Fi(28)
100000 loops, best of 3: 6.27 μs per loop

In [38]: %timeit Fip(1000)
10000 loops, best of 3: 81.1 μs per loop
\end{lstlisting}



\subsection{Mémoïsation}

Dans   la  version   récursive,   on   appelle  \texttt{fib(3)}   très
souvent.  Une  idée simple  mais  efficace  consiste à  mémoriser  les
calculs déjà effectués:

\begin{lstlisting}
fibcache = {0:0, 1:1}

def Fim(n):
    if n in fibcache:
        return fibcache[n]
    else:
        fibcache[n] = Fim(n-1) + Fim(n-2)
        return fibcache[n]
\end{lstlisting}


Plus techniquement, on peut utiliser un \textit{décorateur}:

\begin{lstlisting}
def enrobe(f):
    cache = {}
    def f_avec_cache(n):
        if n in cache:
            return cache[n]
        else:
            cache[n] = f(n)
            return cache[n]
    return f_avec_cache

@enrobe
def Fm(n):
    if n == 0:
        return 0
    elif n == 1:
        return 1
    else:
        return Fm(n - 1) + Fm(n - 2)
\end{lstlisting}


\begin{lstlisting}
In [30]: %timeit Fm(100)
10000000 loops, best of 3: 146 ns per loop
\end{lstlisting}


À chaque appel de la fonction \texttt{Fm}, elle est en fait 
substituée par  \texttt{enrobe(Fm)} (on  parle de  \textit{wrapper} en
anglais de spécialité).


On peut mettre un petit espion:

\begin{lstlisting}
def enrobe(f):
    cache = {}
    def f_avec_cache(n):
        if n in cache:
            print("rappel via le cache de f(" + str(n) + ")")
            return cache[n]
        else:
            cache[n] = f(n)
            print("calcul via la définition de f(" + str(n) + ")")
            return cache[n]
    return f_avec_cache
\end{lstlisting}

et on observe que \texttt{cache} est conservé d'un appel à l'autre:

\begin{lstlisting}
In [23]: Fm(5)
calcul via la définition de f(1)
calcul via la définition de f(0)
calcul via la définition de f(2)
rappel via le cache de f(1)
calcul via la définition de f(3)
rappel via le cache de f(2)
calcul via la définition de f(4)
rappel via le cache de f(3)
calcul via la définition de f(5)
Out[23]: 5

In [24]: Fm(8)
rappel via le cache de f(5)
rappel via le cache de f(4)
calcul via la définition de f(6)
rappel via le cache de f(5)
calcul via la définition de f(7)
rappel via le cache de f(6)
calcul via la définition de f(8)
Out[24]: 21

In [25]: Fm(9)
rappel via le cache de f(8)
rappel via le cache de f(7)
calcul via la définition de f(9)
Out[25]: 34
\end{lstlisting}

pourtant:

\begin{lstlisting}
In [26]: cache
---------------------------------------------------------------------------
NameError                                 Traceback (most recent call last)
<ipython-input-26-0a8bb56fc873> in <module>()
----> 1 cache

NameError: name 'cache' is not defined
\end{lstlisting}

On peut utiliser le décorateur spécialement dédié à la mémoïsation importé de la
bibliothèque \textit{functools}: 

\begin{lstlisting}
from functools import lru_cache

@lru_cache(maxsize = None)
def Fm(n):
    if n == 0:
        return 0
    elif n == 1:
        return 1
    else:
        return Fm(n - 1) + Fm(n - 2)
\end{lstlisting}


Alors:

\begin{lstlisting}
In [31]: %timeit Fm(100)
1000000 loops, best of 3: 814 ns per loop
\end{lstlisting}




%\section{Complexité}


\vfill

\eject



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



\begin{exercice}[CCP MP 2015]
{\itshape Non, non, ce n'est pas un extrait d'un livre de seconde, c'est un sujet 0
proposé pour l'épreuve de Math du concours CCP...}
  \begin{enumerate}
  \item Écrire une fonction factorielle qui  prend en argument un entier naturel
    $ n$ et renvoie $ n!$ (on n'accepetra pas bien sûr de réponse utilisant la
    propre fonction factorielle du module math de Python ou Scilab).
  \item Écrire une fonction  \lstinline{seuil} qui prend en argument un  entier $ M$ et renvoie
    le plus petit entier naturel $ n$ tel que $ n!>M$.
  \item Écrire une fonction booléenne nommée \lstinline{est_divisible}, qui pend
    en argument un entier naturel $ n$  et renvoie \lstinline{True} si $ n!$ est
    divisible par $ n+1$ et \lstinline{False} sinon.
  \item On considère la fonction suivante nommée \lstinline{mystere}:
    \begin{lstlisting}
def mystere(n):
    s = 0
    for k in range(1,n+1):
        s = s + factorielle(k)
    return s
    \end{lstlisting}
    \begin{enumerate}
    \item Quelle valeur renvoie \lstinline{mystere(4)}?
    \item Déterminer    le     nombre    de    multiplications    qu'effectue
      \lstinline{mystere(n)}.
    \item Proposer une amélioration du script de la fonction \lstinline{mystere}
      afin d'obtenir une complexité linéaire.
    \end{enumerate}
  \end{enumerate}
\end{exercice}








\begin{exercice}
Quel est ce mystere?

\begin{lstlisting}
def mystere(a,b):
    if a == 0:
        return b
    if b == 0:
        return a
    if b < 0:
        return - mystere(- a - 1, 1 - b)
    return mystere(a + 1, b - 1)
\end{lstlisting}

Que font les fonctions f et g?

\begin{lstlisting}
def f(n):
    return n == 0 or g(n - 1)

def g(n):
    return n !=0 and f(n - 1)
\end{lstlisting}

\end{exercice}








\begin{exercice}[Javanais for dummies]
On va simplifier le javanais habituel  sans tenir compte de la découpe
selon les syllabes.
On  introduit  les lettres  \og  av\fg{}  devant la  première  voyelle
rencontrée dans le mot en partant de la gauche.
Créez une foncton \texttt{javanais(mot)}:

\begin{lstlisting}
In [8]: javanais("chrome")
Out[8]: 'chravome'

In [9]: javanais("air")
Out[9]: 'avair'
\end{lstlisting}
  
\end{exercice}


\begin{exercice}[Sommes]
  On suppose  que l'on dispose  de deux fonctions  \texttt{succ} et
  \texttt{prec}  qui  calculent  respectivement le  successeur  et  le
  prédécesseur d'un entier.
  
  Voici deux fonctions:

  \begin{lstlisting}
def plusA(x,y):
    if x == 0:
        return y
    else:
        print(x,y)
        return succ(plusA(prec(x),y))

def plusB(x,y):
    if x == 0:
        return y
    else:
        print(x,y)
        return plusB(prec(x),succ(y))
  \end{lstlisting}

Sans  utiliser  la machine,  illustrer  le  processus d'évaluation  de
\texttt{plusA(4,5)} et \texttt{plusB(4,5)}.

Sont-ce des processus récursifs? Itératifs?

\end{exercice}



\begin{exercice}[Puissances itérées de Knuth]

La multiplication peut être vue comme une addition itérée et
l'exponentiation comme  une multiplication  itérée. Alors  pourquoi ne
pas concevoir une exponentiation itérée?

Don \textsc{Knuth} a introduit en 1976 la notation suivant:

$$a \uparrow\uparrow b = a\uparrow^2 b=
\underbrace{a^{a^{\iddots ^a}}}_{b\text{ exemplaires de }a}$$


et de même:

$$a\uparrow^3    b=    \underbrace{a\uparrow^2   a\uparrow^2    \cdots
  \uparrow^2 a}_{b\text{ exemplaires de }a}$$

etc.


On définit à présent la fonction suivante:

\begin{lstlisting}
def A(x,y):
    if y == 0:
        return 0
    elif x == 0:
        return 2*y
    elif y == 1:
        return 2
    else:
        return A(x - 1, A(x, y - 1))
\end{lstlisting}


Quelles  sont   les  valeurs  de   \texttt{A(1,10)},  \texttt{A(2,4)},
\texttt{A(3,3)}?

Donnez  une   définition  mathématique  plus  concise   des  fonctions
suivantes définie sur $ \bbn$ par:
\begin{itemize}
\item $ f(n) = A(0,n)$
\item $ g(n) = A(1,n)$
\item $ h(n) = A(2,n)$
\end{itemize}

Utilisez-les  pour  calculer  le  nombre  de  chiffres  de  l'écriture
décimale de \texttt{A(4,2)}

\end{exercice}



\begin{exercice}[Golden ratio]

Reprenons les observations faites en cours:

\begin{lstlisting}
 In [19]: %timeit F(20)
100 loops, best of 3: 3.4 ms per loop

In [20]: %timeit F(25)
10 loops, best of 3: 36.7 ms per loop

In [21]: %timeit F(26)
10 loops, best of 3: 59.1 ms per loop

In [22]: %timeit F(27)
10 loops, best of 3: 95.9 ms per loop

In [23]: %timeit F(28)
10 loops, best of 3: 155 ms per loop
\end{lstlisting}

et observons:

\begin{lstlisting}
In [24]: 59.1/36.7
Out[24]: 1.6103542234332424

In [25]: 95.9/59.1
Out[25]: 1.622673434856176

In [26]: 155/95.9
Out[26]: 1.6162669447340978
\end{lstlisting}


Voici à présent une fonction bavarde:
  \begin{lstlisting}
def F(n):
    if n == 0:
        print("Évaluation de F(0)")
        return 0
    elif n == 1:
        print("Évaluation de F(1)")
        return 1
    else:
        print("Appel de F(" + str(n) + ")")
        return F(n - 1) + F(n - 2)
  \end{lstlisting}
  Que  vous inspirent  les résultats  des évaluations  de \texttt{F(5)},
  \texttt{F(6)}? 

Établissez une relation entre le  nombre de feuilles de l'arbre d'appel
de \texttt{F(n)} et \texttt{F(n)}.

% Notons $Φ=\frac{1+\sqrt{5}}{2}$ et $Ψ=\frac{1-\sqrt{5}}{2}$.

% Démontrez que $F(n)=\frac{Φ^n-Ψ^n}{\sqrt{5}}$.

Exprimez $ F(n)$ en fonction uniquement d'un nombre bien connu...

Expliquez alors les temps de calcul observés.



\end{exercice}

\begin{exercice}[Pascal]

Calculez  une  fonction qui  donne  les  coefficients du  triangle  de
\textsc{Pascal}.

  
\end{exercice}

















\begin{exercice}[Petit jeu]
  

\pro Cet été, lors de la visite d'un musée, j'ai, pour une fois, impressionné mes
enfants en résolvant devant eux très rapidement le problème suivant:


%\begin{figure}
\begin{center}
  \includegraphics[angle=-1,scale=2]{hanoi3}
\end{center}
%\end{figure}


Ce casse-tête a été posé  par le  mathématicien
français Édouard \textsc{Lucas} en 1883.

Le  jeu  consiste  en  une  plaquette  de bois  où  sont  plantés  trois
piquets. Au  début du jeu, 4  disques de diamètres croissant  de bas en
haut sont placés  sur le piquet de  gauche. Le but du jeu  est de mettre
ces disques dans le même ordre sur le piquet de droite en respectant les
règles suivantes:

\begin{itemize}
\item on ne déplace qu'un disque à la fois;
\item on ne peut poser un disque que sur un disque de diamètre supérieur.
\end{itemize}

Je vous propose donc de jouer vous aussi avec moi...

\taupap{pauvres enfants,  passer des  vacances avec  un prof  de maths,  vois le
  cauchemar} Oh, comme je suis content!

\pro Essayez d'abord avec 2 puis 3 disques.


\taup  Bon, avec  deux, je  mets  le disque  là puis  l'autre là-bas  et
ensuite celui-ci ici. Ça marche.  Avec trois, je bouge celui-là, et puis
l'autre, celui-ci ici,  l'autre là, puis celui-là là  et l'autre là puis
le  dernier ici.  Ah,  c'est pas  le bon  piquet  mais ça  marche à  peu
près. Facile votre jeu.


\pro Alors essayez avec quatre, cinq, autant de disques que vous voulez.

\medskip

{\itshape Quelques minutes plus tard}

\taup Pénible votre jeu!

\pro Les  choses se compliquent.  Il est temps  de parler de  la légende
rapportée par \textsc{ Lucas} dans ses \og \textit{récréations mathématiques}\fg{}:

\begin{quote}
  \textit{N. Claus de Siam a vu, dans ses voyages pour la publication des écrits
de  l'illustre  Fer-Fer-Tam-Tam,  dans   le  grand  temple  de  Bénarès,
au-dessous du  dôme qui  marque le centre  du monde, trois  aiguilles de
diamant,  plantées  dans une  dalle  d'airain,  hautes  d'une coudée  et
grosses comme  le corps  d'une abeille. Sur  une de ces  aiguilles, Dieu
enfila au commencement  des siècles, 64 disques d'or  pur, le plus large
reposant  sur  l'airain,  et  les  autres,  de  plus  en  plus  étroits,
superposés  jusqu'au sommet.  C'est la  tour sacrée  du Brahmâ.  Nuit et
jour, les  prêtres se  succèdent sur les  marches de l'autel,  occupés à
transporter  la tour  de la  première  aiguille sur  la troisième,  sans
s'écarter des  règles fixes que nous  venons d'indiquer, et  qui ont été
imposées  par Brahma.  Quand  tout sera  fini,  la tour  et les  brahmes
tomberont, et ce sera la fin des mondes !}
\end{quote}



C'est un problème  posé par un mathématicien mais  nous allons l'étudier
en \emph{informathicien}. Nous voudrions répondre à plusieurs questions:
\begin{itemize}
\item peut-on résoudre le problème des 64 disques?
\item si oui, en combien de mouvements?
\item peut-on trouver une tactique la plus efficace possible?
\item est-ce que la fin du monde est pour bientôt?
\end{itemize}

Au lieu  d'étudier des  cas séparés, nous  allons généraliser un  peu et
considérer une  tour avec $n$ disques,  $n$ étant un  entier naturel non
nul.


\taup Cela va compliquer les choses. Pourquoi ne pas s'en tenir à un cas
précis? C'est une perversion de mathématicien.

\pro Détrompez-vous!  Au lieu d'étudier un  à un des cas  isolés, il est
bon pour  un informaticien  aussi de voir  qu'un programme  plus général
pourra traiter tous les cas.  Cependant, il sera utile d'étudier des cas
simples d'abord pour se donner une idée. 

Après une rapide exploration avec papier et crayon, il est temps pour un
\emph{informathicien} d'introduire des notations adéquates. 

Notons  $M_n$  le  nombre  minimum  de mouvements  pour  transférer  $n$
disques. Pouvez-vous donner les premières valeurs de $M_n$?

\taup Bon, s'il  n'y a qu'un disque, on ne pourra  pas faire mieux qu'un
déplacement: $M_1=1$. Avec deux disques, hop, hop, hop: trois mouvements;
$M_2=3$. Pour  trois, j'avais trouvé  sept déplacements mais je  ne suis
pas sûr que ça soit la meilleure solution.

\pro  C'est  ce  que nous  allons  prouver  mais  tout d'abord,  en  bon
mathématicien, rajoutons un cas extrême: s'il y a zéro disque, il faudra
zéro mouvement.

\taup C'est un peu tiré par les cheveux.

\pro  Mais  considérer les  cas  les  plus  triviaux permet  souvent  de
simplifier le cas général. Il est temps d'ailleurs de voir grand mais il
nous  faudrait une  idée. Essayons  de  trouver des  points communs  aux
déplacements de deux et trois disques respectivement. 

\taup Ben, je mets le petit sur  le piquet du milieu, le grand sur celui
d'arrivée puis le petit sur ce même piquet d'arrivée.

\pro  Pour trois  c'est pareil:  je mets  les deux  petits sur  celui du
milieu, le grand sur celui d'arrivée  puis les deux petits par dessus le
grand.

\taup Vous trichez! Vous avez bougé deux disques en même temps.

\pro En fait, j'ai vu que  je savais bouger deux disques d'un piquet vers
un autre. Cela me demande trois étapes qui se cachent derrière le \og\textit{je mets  les deux  petits sur  celui du
milieu} \fg{}.

Cela nous  donne en  fait la  solution: avec $n+1$  disques, je  bouge les
$n$ plus petits sur le piquet du milieu ($M_{n}$ mouvements), je bouge le plus grand sur le
piquet d'arrivée (1 mouvement) puis je redéplace les $n$ petits sur le
grand ($M_{n}$ mouvements). Ainsi:

$$M_{n+1} \leqslant 2M_n+1$$

\taup Pourquoi avoir utilisé $\leqslant $ et non pas $=$? Et puis, on ne
connaît pas $M_n$.

\pro Vous touchez du doigt deux problèmes essentiels qui vont guider bon
nombre de nos raisonnements. 

Pour  le $\leqslant $,  il est  essentiel de  comprendre que  nous avons
prouvé que $2M_n+1$ mouvements  étaient \textbf{suffisants} mais nous ne
savons    toujours    pas    si    ces    $2M_n+1$    mouvements    sont
\textbf{nécessaires}. C'est très important de comprendre la différence.

Par exemple, pour acheter un chocolat chaud à la cafétéria et l'offrir à
son professeur adoré, il est \textbf{suffisant} d'avoir 10 euros dans sa
poche   mais   ce   n'est   pas   nécessaire.    Inversement,   il   est
\textbf{nécessaire}  d'avoir   au  moins  20  centimes   mais  ce  n'est
malheureusement pas suffisant.

%Nous avons étudié cela en détail dans un précédent chapitre sur la logique.

% \begin{NB}
% On  considère P  et Q  deux propositions  (des énoncés,  des  faits, des
% formules).

% \begin{itemize}
% \item Q est une \textbf{condition nécessaire} pour avoir P si, dès que P
%   est  vraie,  alors nécessairement,  forcément,  obligatoirement, Q  est
%   vraie. On note souvent $P \limp Q$.
% \item Q est  une \textbf{condition suffisante} pour avoir  P s'il suffit
%   que  Q  soit  vraie  pour  que  P soit  vraie.   On  note  souvent  $P
%   \limp Q$.
% \item  Lorsque  P  est  à  la fois  condition  nécessaire  et  condition
%   suffisante de Q, on dit  que P est une \textbf{condition nécessaire et
%     suffisante} de Q ou encore  que P est vraie \textbf{si, et seulement
%     si,} Q est vraie. On note souvent $P \lequiv Q$.
% \end{itemize}

% Lorsque qu'une \og affirmation\fg{} du  type $P \lequiv Q$ ou $P
% \lequiv Q$ est vraie, on dit que c'est un \textbf{théorème}.
% \end{NB}

%Nous avons développé des méthodes de preuve dans un chapitre précédent.

Revenons à nos disques. Peut-on faire mieux que la solution
proposée?

À un moment donné, il \textit{faut}  bien bouger le plus grand disque puisqu'il
est sur le mauvais piquet. Il \textit{faut}  donc qu'il soit tout seul et il \textit{faut}
donc avoir  bougé auparavant  les $n$ autres  disques plus  petits. Cela
\textit{nécessite} \textit{au minimum}  $M_n$ mouvements. Après cela, on
peut bouger  le grand disque  autant de fois  qu'on le désire mais  à un
moment donné,  il \textit{faudra} le  placer sur le piquet  d'arrivée et
déplacer  les  $n$  autres  disques  sur  le  piquet  d'arrivée  ce  qui
\textit{nécessite} à nouveau $M_n$ mouvements. 

Ainsi, il \textit{faudra au minimum} effectuer $2M_n+1$ mouvements.

On a donc prouvé que:

$$M_{n+1}\geqslant 2M_n+1$$

Il  est donc  \textbf{nécessaire} d'effectuer  $2M_n+1$  mouvements pour
déplacer  les $n+1$  disques. Or  nous avons  montré auparavant  que ces
$2M_n+1$ mouvements étaient \textbf{suffisants}. On en déduit donc que:


$$
\begin{cases}
  M_0=0\\
  M_{n}=2M_{n-1}+1 \text{ pour tout } n>0
\end{cases}
$$


Est-ce que cette formule marche bien avec nos premiers exemples?

\taup  $M_1=2\cdot 0+1=1$:  OK. $M_2=2\cdot  1+1=3$:  OK. $M_3=2\cdot
3+1=7$: OK.

\pro Ça ne prouve pas grand  chose mais ça nous rassure. De toute façon,
nous avons prouvé que cette formule est bonne. Que vaut $M_{64}$?

\taup  Ben $M_{64}=2M_{63}+1$.  Le problème,  c'est qu'on  ne  connaît pas
$M_{63}$.

\pro  Et   oui:  on  définit  la  \textit{suite}   \textbf{M}  à  partir
d'elle-même, ce qui  n'est pas très pratique. On dit  qu'on a définit la
fonction \textbf{récursivement}.  Vous  verrez cette année en informatique
que  ce mode  de  calcul n'est  pas  réservé aux  suites  que vous  avez
peut-être  étudiées  au  lycée.  Par  exemple,  en  langage  formel,  on
travaille avec les  lettres d'un alphabet. On peut  alors définir un mot
comme étant soit le vide, soit une lettre suivi d'un mot.

\taup C'est un peu  idiot: en fait, vous me dites que  pour savoir si un
truc est un mot, faut déjà savoir si c'est un mot.

\pro Vous n'êtes  pas assez précis. Prenons notre  alphabet et la chaîne
de caractères \og math\fg{}.  C'est le vide suivi de la chaîne \og math\fg{} qui
est la lettre \og m\fg{} suivie de la
chaîne \og ath\fg{} qui est la lettre \og a\fg{} suivie de la chaîne \og
th\fg{} qui est la lettre \og  t\fg{} suivie de la lettre \og h\fg{} qui
est un  mot puisque c'est une  lettre. En remontant, on  obtient que \og
th\fg{} est  un mot puis que  \og ath\fg{} aussi et  enfin \og math\fg{}
est donc un mot.

\taupap{Ben  on le savait  avant. Si  c'est ça  c'qu'on apprend  en
  info, il est peut-être encore temps de m'inscrire en Khâgne.}
Fabuleux! Math est un mot! J'aurais pas cru, comme ça, a priori.

\pro Ah, comme quoi ce que nous faisons est utile.

\taupap{Complètement gâteux le gars} Je n'en doute pas.

\pro  Et la  fin du  monde  dans tout  ça? Pour  connaître $M_{64}$,  il
semblerait qu'il faille connaître tous les $M_k$ précédents.

Voyons voir, calculez jusqu'à $M_6$.

\taup Si vous voulez:
\begin{itemize}
\item $M_3=2\cdot 3+1=7$;
\item $M_4=2\cdot 7+1=15$;
\item $M_5=2\cdot 15+1=31$;
\item $M_6=2\cdot 31+1=63$;
\end{itemize}

Ouais, bof. Je ne vois pas trop où ça nous mène.


\pro  \og  \textit{Ils ont  des  yeux et  ils  ne  voient pas}\fg{}.  Et
pourtant, quand  j'étais jeune, un enfant  de six ans  aurait reconnu la
suite:

$$2^3-1,\ 2^4-1,\ 2^5-1, \ 2^6-1,...$$

\taupa{Ben  tiens!  Les   puissances  à  6  ans  et   pourquoi  pas  les
  logarithmes à 7.}


\pro Vous dites? 

\taup Je réfléchissais.

\pro Ah. Alors, vous avez sûrement envie de dire que tout prête à croire
que:

$$M_n=2^n-1, \text{ pour tout entier strictement positif } n$$

\taup Ben oui,  c'est vrai au début donc  y a pas de raison  pour que ça
s'arrête.

\pro  Encore  faudrait-il  le   prouver.  Par  exemple,  est-ce  que  la
proposition suivante est un théorème: 

\begin{center}
  \textit{Les entiers impairs supérieurs à 3 sont tous des nombres premiers.}
\end{center}

\taup 3 est premier, 5 est premier, 7 est premier...

\pro...donc c'est vrai! 

\taup Ben  non. 9  est impair mais  n'est pas premier...Ouais,  OK, j'ai
compris.

\pro  \og Vrai  pour  les premiers,  vrai  pour tous\fg{}  n'est pas  un
théorème! 

%Cela peut  par exemple se démontrer en \textit{raisonnant  par l'absurde}.
%comme nous l'avons déjà vu.

Ici,  pour  tout   entier  naturel  non  nul  $n$,   notons  $\PR_n$  la
proposition: $M_n=2^n-1$.

Cette proposition est vraie pour $n=1$ puisque $M_1=1=2^1-1$.


Il existe  donc au moins un entier  naturel non nul $k$  tel que $\PR_k$
soit vraie. 

Alors $M_{k+1}=2M_k+1=2(2^k-1)+1=2\cdot 2^k-2+1=2^{k+1}-1$.

Ainsi $\PR_k \limp \PR_{k+1}$ pour tout entier naturel non nul
$k$.

Le tour est joué. On peut donc affirmer que $M_n=2^n-1$ pour tout entier
naturel non nul $n$. 

\taup       Donc       $M_{64}=2^{64}-1$.        Je      prends       ma
calculatrice...$M_{64}=\numprint{18446744073709551615}$. Ça ne m'arrange
pas tellement pour connaître la date de la fin du monde.

\pro  C'est  pourtant simple.  Disons  que  les  moines sont  très  bien
entraînés et se relaient efficacement. Ils déplacent alors un disque par
seconde. Cela nous donne une durée de jeu de...


\taup              Ah,              ça             je              sais:
$\numprint{18446744073709551615}/\numprint{3600}/24/365,25/100$ ce qui fait en gros
$\numprint{5.8}$ milliards de siècles...

\pro  Et  comme  l'Univers  a   grosso  modo  140  millions  de  siècles
d'existence, cela nous laisse de la marge.

\taup  Ouf! Mais  cela ne  nous indique  pas comment  déplacer  les huit
disques du  jeu initial. On sait  juste qu'en étant  aussi efficaces que
les moines, cela nous
prendra $M_8=2^8-1=255$ secondes.

\pro Je vous laisse donc cinq minutes pour le faire.

\medskip

\textit{Cinq minutes plus tard}

\medskip

\taup Il  faut se  rendre à l'évidence:  je ne  suis pas fait  pour être
moine. Faut le faire pour chaque  $n$ jusqu'à 8 en fait et noter comment
on a fait. Pfff... C'est pénible.

\pro Et quand  un informathicien a bien réfléchi sur  le papier, il peut
laisser faire  le sale boulot  à la machine.  On a en effet  une méthode
qu'on sait être correcte. Mais il est très difficile de l'appliquer pour
un grand $n$ donné.  On sait que ça marche mais on  ne sait pas vraiment
comment ça marche. Et c'est  là qu'une programmation bien pensée devient
merveilleusement  efficace.  Si on  a  à  notre  disposition un  langage
sachant traiter  la récursion,  il va suffire  de lui donner  un minimum
d'instruction.

Rappelons ici notre méthode:  avec $n+1$  disques, je  bouge les
$n$ plus petits sur le piquet du milieu ($M_{n}$ mouvements), je bouge le plus grand sur le
piquet d'arrivée (1 mouvement) puis je redéplace les $n$ petits sur le
grand ($M_{n}$ mouvements). 



\textbf{Donnez  une  fonction  Python  de  trois  lignes  donnant  les
  différents  mouvements  nécessaires  pour résoudre  le  problème  de
  Hanoï:}

\begin{lstlisting}
In [1]: hanoi('A','C','B',2)
Out[1]: '(A -> B)(A -> C)(B -> C)'

In [2]: hanoi('A','C','B',3)
Out[2]: '(A -> C)(A -> B)(C -> B)(A -> C)(B -> A)(B -> C)(A -> C)'
\end{lstlisting}
\end{exercice}



\begin{exercice}[Rendu de monnaie]

Vous  diposez de  pièces de  1,  2, 5,  10,  50, 100  et 200  centimes
d'euro. 

Vous  devez rendre  un certain  montant avec  ces pièces.  Calculez de
combien de  manières différentes  on peut former  ce montant  avec ces
pièces (on en a autant que l'on veut...).
  
\end{exercice}




\begin{exercice}[Table de Poisson]


On veut simuler une v.a.r. $X$  qui suit une loi de Poisson de paramètre
$\lambda > 0$ en utilisant une  fonction du style \lstinline+random+ qui renvoie
une suite aléatoire de nombres selon une distribution uniforme.

Déterminez une fonction
      \textsf{Python}       \lstinline+poisson(l,n)+    qui    calcule
      $\Pr{}_X(n)$ de manière récursive avec \lstinline+lambda+ le 
      paramètre de la loi. Vous devez obtenir par exemple:

\begin{lstlisting}
In [1]: poisson(1,2)
Out[1]: 0.18393972058572117
\end{lstlisting}



   Fabriquez-vous une fonction \lstinline{poisson} afin d'obtenir une table:


\begin{lstlisting}
from math import exp
from numpy import array,vectorize

def poisson(l,k):
    ???

def table(deb,fin):
    t =  array([[poisson(j*0.1,i) for j in range(int(deb*10),int(fin*10)-1)] for i in range(8)])
    print(vectorize("%.3f".__mod__)(t))

In [2]: table(0.1,1)
[['0.905' '0.819' '0.741' '0.670' '0.607' '0.549' '0.497' '0.449']
 ['0.090' '0.164' '0.222' '0.268' '0.303' '0.329' '0.348' '0.359']
 ['0.005' '0.016' '0.033' '0.054' '0.076' '0.099' '0.122' '0.144']
 ['0.000' '0.001' '0.003' '0.007' '0.013' '0.020' '0.028' '0.038']
 ['0.000' '0.000' '0.000' '0.001' '0.002' '0.003' '0.005' '0.008']
 ['0.000' '0.000' '0.000' '0.000' '0.000' '0.000' '0.001' '0.001']
 ['0.000' '0.000' '0.000' '0.000' '0.000' '0.000' '0.000' '0.000']
 ['0.000' '0.000' '0.000' '0.000' '0.000' '0.000' '0.000' '0.000']]

\end{lstlisting}



\end{exercice}




% \begin{exercice}[Multiplication de plus de 2 matrices]


% \end{exercice}


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