

%%
%% ArticleProgFonc.tex
%% 
%% Made by Guillaume Connan
%% Login   <moi@moi-portable>
%% 
%% Started on  Tue Apr  7 18:01:31 2009 Guillaume Connan





\documentclass[11pt,a4paper,twoside]{article}
\usepackage[height=250mm,width=183mm]{geometry}
\usepackage[T1]{fontenc}
\usepackage[latin1]{inputenc}
\usepackage[french]{babel}
\usepackage{amsmath}
\usepackage[upright]{fourier}
\usepackage{graphicx,color}
\usepackage[french]{varioref}
\usepackage{listings,xlop}
\usepackage[french,vlined,boxed]{algorithm2e}
%\usepackage{tex4ht}


\usepackage[dvips,ps2pdf,colorlinks,linkcolor=blue]{hyperref}



\newenvironment{Abstract}[1]    % résumé avant chapitre ou ds
{\begin{center}
\begin{minipage}{10cm}
\textbf{Résumé} \footnotesize{#1}} {\end{minipage}
\end{center}
\bigskip\bigskip}

\newcommand\Com[1]{%
\shorthandoff{;:}\textcolor{0.2white}{\bfseries \textsf{#1}}}

\definecolor{creme}{rgb}{0.448,0.999,0.5940}
\definecolor{ciel}{rgb}{0.220,0.890,0.999}
\definecolor{0.2white}{rgb}{0.2,0.2,0.2}
\definecolor{0.9white}{rgb}{0.9,0.9,0.9}

% \newcommand\caml{\lstset{numbers=none,language=XCAS,xleftmargin=10pt,%
% keywordstyle
% =\color{0.2white}\usefont{OT1}{cmtt}{b}{n},basicstyle=\ttfamily\color{0.2white},commentstyle=\normalfont\small\itshape,breaklines=true,frame=trBL,framerule=1pt,framesep=4pt,rulesep=1pt,backgroundcolor=\color{ciel}}
% }



\newcommand\caml{\lstset{numbers=none,language=caml,xleftmargin=10pt,%
keywordstyle
=\color{0.2white},basicstyle=\ttfamily\color{0.2white},commentstyle=\normalfont\small\itshape,breaklines=true,frame=trBL,framerule=1pt,framesep=4pt,rulesep=1pt,backgroundcolor=\color{creme}}
}

\newcommand\cas{\lstset{numbers=none,language=C++,xleftmargin=10pt,%
keywordstyle
=\color{0.2white},basicstyle=\ttfamily\color{0.2white},commentstyle=\itshape,breaklines=true,frame=trBL,framerule=1pt,framesep=4pt,rulesep=1pt,backgroundcolor=\color{ciel}}
}


% \newcommand\xc{\lstset{numbers=none,language=XCAS,xleftmargin=10pt,%
% keywordstyle
% =\color{0.2white}\usefont{OT1}{cmtt}{b}{n},basicstyle=\ttfamily\color{0.2white},commentstyle=\normalfont\small\itshape,breaklines=true,backgroundcolor=\color{ciel},frame=trBL,framerule=1pt,framesep=4pt,rulesep=1pt}
% }



\title{ Affecter ou ne pas affecter~?}

\author{Guillaume Connan - IREM de Nantes}

\date{\today}







\begin{document}
\setlength{\parindent}{0pt}
\thispagestyle{empty}

\incmargin{1em}
\dontprintsemicolon
%\SetCommentSty{\sffamily}}%\sffamily\color{0.4white}}

\maketitle


\begin{Abstract}
L'algorithmique fait  une entrée remarquée dans le  nouveau programme de
Seconde.  Il  y  est  fait  clairement  mention  de  l'apprentissage  de
l'affectation, des  entrées-sorties et des boucles comme  allant de soi,
ce    qui    sous-entend    que    seule   existe    la    programmation
impérative.    Cependant   la   programmation  fonctionnelle   est   une
alternative très proche des  mathématiques et de
leur enseignement  dans le secondaire.  Nous verrons dans  quelle mesure
l'enseignement   de  l'algorithmique   via  les   langages  fonctionnels
peut être enrichissant et complémentaire d'une approche purement impérative.\\
%De  nombreux  algorithmes pour  le  lycée  sont  catalogués à  l'adresse
%suivante :

\end{Abstract}






\section{Conventions}

L'objet  de cet  article n'est  pas d'envisager  ces  deux  modes de
programmation  avec le  point  de vue  de  l'informaticien cherchant  la
méthode  la  plus  rapide  mais  avec  celui  d'un  professeur  \emph{de
  mathématiques}  s'adressant  à  des  élèves \emph{débutants}  dans  ce
domaine\footnote{lui-même pouvant d'ailleurs appartenir à cette catégorie~!...}.


  Ce court
article ne fournit  pas d'activités  clé-en-main mais  donne des
éléments pour  alimenter la réflexion  du professeur, en  particulier en
montrant que  la programmation fonctionnelle, souvent  méconnue (même si
elle est implicite dans un tableur ou peut être utilisée en primaire avec la
tortue  Logo), est  très proche  des mathématiques.


Nous  ne parlerons  pas d'un  logiciel en  particulier.  Cependant, afin
d'illustrer de manière pratique notre propos, nous utiliserons XCAS, logiciel multifonctions
spécialement  conçu  pour  être   utilisé  en  classe  de  mathématiques
dont l'usage aujourd'hui est assez largement répandu et OCAML,
logiciel  utilisant  la programmation  fonctionnelle  (même s'il  permet
aussi d'avoir recours à un style impératif).



\section{Programmation impérative et affectations}

\subsection{Aspect technique}


La  programmation  impérative est  la  plus  répandue (Fortran,  Pascal,
C,...)  et la  plus proche  de la  machine réelle.  Son principe  est de
modifier   à   chaque   instant   l'état   de   la   mémoire   via   les
affectations.  Historiquement,  son  principe  a  été  initié  par  John
\textsc{Von Neumann} et Alan \textsc{Turing}.

Par exemple, lorsqu'on entre avec XCAS~:



\cas
\begin{lstlisting}
a:=2
\end{lstlisting}

cela  signifie que  la case  mémoire  portant le  petit \og  fanion\fg{}
\texttt{a} contient à cet instant la valeur 2.

On peut changer le contenu de cette case mémoire un peu plus tard~:

\begin{lstlisting}
a:=4
\end{lstlisting}


et cette fois la case \texttt{a} contient la valeur 4.

Le  caractère  chronologique  de  ce  type  de  programmation  est  donc
primordial. Regardons la suite d'instructions suivante~:

\begin{lstlisting}
a:=1;
b:=2;
a:=a+b; // maintenant a contient 3
b:=a-b; // maintenant b contient 3-2=1
a:=a-b; // maintenant a contient 3-1=2
\end{lstlisting}

Cela permet d'échanger les contenus des cases mémoire \verb+a+ et
\verb+b+.

Si l'on change l'ordre d'une  quelconque des trois dernières lignes, les
valeurs présentes  dans les cases mémoires nommées  \verb+a+ et \verb+b+
vont être différentes.

Si l'on regarde les deux dernières lignes, elles affectent apparemment
la même valeur  (\verb+a-b+) à \verb+a+ et à  \verb+b+ et pourtant c'est
faux car les variables \verb+a+ et \verb+b+ ne contiennent pas les mêmes valeurs
selon le moment où elles sont appelées.

Il faut donc être extrêmement attentif à la chronologie des instructions
données.  C'est un  exercice intéressant  en  soi mais  pas sans  danger
(c'est d'ailleurs la source de la plupart des \og bugs\fg{} en informatique).

La motivation première de ce type de fonctionnement a été pratique~:~les
ordinateurs  étant peu puissants,  le souci  principal du  concepteur de
programme a  longtemps été d'économiser  au maximum la mémoire.  Au lieu
d'accumuler  des   valeurs  dans  différents  endroits   de  la  mémoire
(répartition spatiale), on les stocke  au même endroit mais à différents
moments (répartition  temporelle). C'est le modèle des  machines à états
(machine de \textsc{Turing} et architecture de \textsc{Von Neumann}) qui
impose au programmeur  de connaître à tout instant  l'état de la mémoire
centrale. 


\subsection{Exploitation mathématique possible}

En classe  de mathématique,  cet aspect technique  nous importe  peu. Il
nous   permet   cependant  d'illustrer   dynamiquement   la  notion   de
fonction~:

\begin{lstlisting}
y:=x^2+1;

x:=1;   y;   // ici y=2
x:=-5;  y;   // ici y=26
x:=1/2; y;   // ici y=5/4
\end{lstlisting}

La fonction $f~:~x\mapsto x^2+1$ dépend de la variable $x$. On affecte une certaine
valeur à  la variable ce  qui détermine la  valeur de son image.  Il est
toutefois  à noter qu'en  fait on  a travaillé  ici sur  des expressions
numériques et non pas des fonctions.


On peut enchaîner des affectations~:

\begin{lstlisting}
y:=x^2+1;
z:=y+3;

x:=1;   y; z;  /* ici y:=2 et z=5 */
x:=-5   y; z;  // ici y=26  et z=29;
x:=1/2; y; z;  // ici y=5/4 et z=17/4;
\end{lstlisting}


et illustrer ainsi la composition de fonctions.


\medskip


Avec un peu de mauvaise foi  (car le cas est simple et artificiel) mais pas tant que
ça puisque  de tels problèmes  sont source de  milliers de bugs  sur des
milliers de  programmes plus compliqués, nous allons  mettre en évidence
un problème majeur de ce genre de programmation quand on n'est pas assez
attentif.

On créé à un certain moment  une variable \verb+a+ à laquelle on affecte
une valeur~:
\begin{lstlisting}
a:=2;
\end{lstlisting}

On   introduit  plus  tard   une  procédure   (une  sorte   de  fonction
informatique des  langages impératifs) qu'on  nomme $f$ et  qui effectue
certains calculs en utilisant $a$~:

\begin{lstlisting}
f(x):={
  a:=a+1;
  return(x+a)
}
\end{lstlisting}

Alors  $f(5)$ renvoie  $8$  mais si  on  redemande $f(5)$  on obtient  à
présent $9$ et si on recommence  on obtient $10$, etc. car à chaque appel
de  la  procédure  $f$,  la  variable $a$  est  modifiée~:~ici  $2\times
f(5)\neq f(5)+f(5)$~!


On  peut donc construire  un objet  qui \textbf{ressemble}  à une  fonction d'une
variable (mais qui  n'en est évidemment pas) et qui  à une même variable
renvoie  plusieurs valeurs.  En  effet, une  procédure\footnote{Certains
  langages  utilisent  le  terme  fonction  mais  nous  préférerons  \og
  procédure\fg{}   pour   ne    pas   confondre   avec   les   fonctions
  mathématiques. } 
ne dépend pas  uniquement des
arguments  entrés et  donc  peut  changer de  comportement  au cours  du
programme~:~c'est ce qu'on appelle en informatique des \emph{effets de  bord}.


On a en fait plutôt construit ici une fonction de deux variables~:

\[g~:~(a,x)->x+a\]

Le premier appel de $f(5)$ est en fait $g(3,5)$ et le deuxième $g(4,5)$,
etc. mais on a pu le faire en utilisant une forme qui \textbf{laisse à penser}
que $f$ est  une fonction qui renvoie une  infinité d'images différentes
d'un même nombre.

Informatiquement, $a$
 et $x$  jouent des rôles différents  puisque $x$ est un  argument de la
 procédure $f$ et $a$ est une variable globale donc \og extérieure\fg{}
 à  $f$ (on  dirait  un \emph{paramètre}).  D'ailleurs,  XCAS envoie  un
 avertissement pour nous le rappeler ~:

\verb+// Warning: a, declared as global variable(s) compiling f+

\subsection{Programmation fonctionnelle}



\textbf{Les  langages fonctionnels bannissent  totalement les  affectations.} Ils
utilisent   des  fonctions   \emph{au  sens   mathématique   du  terme},
c'est-à-dire qu'une fonction  associe une unique valeur de  sortie à une
valeur  donnée  en  entrée.  Les  fonctions peuvent être testées une  par une car
\emph{elles ne  changent pas  selon le  moment où elles  sont appelées  dans le
programme.}         On         parle        de        \emph{transparence
référentielle}. Le programmeur  n'a donc pas besoin de  savoir dans quel
état se trouve la mémoire. C'est  le logiciel qui s'occupe de la gestion
de la mémoire.



Historiquement, ce style de programmation est né du
$\lambda$-calcul  développé par  Alonzo \textsc{Church}  juste  avant la
publication   des    travaux   d'Alan   \textsc{Turing}\footnote{qui   a
  d'ailleurs été un étudiant de Church à Princeton...}.


Ce  principe  d'utilisation  de   fonctions  au  sens  mathématique  est
perturbant pour  des programmeurs formés aux langages  impératifs mais ne
devraient pas troubler des mathématiciens...


La  \textbf{récursivité} est  le  mode  habituel de  programmation  avec de  tels
langages~:~il s'agit  de fonctions qui  s'appellent elles-mêmes. Pendant
longtemps,  la  qualité des  ordinateurs  et  des langages  fonctionnels
n'était pas  suffisante et limitaient les domaines  d'application de ces
langages.

On  utilise  également  en  programmation  fonctionnelle  des  \textit{fonctions
d'ordre  supérieur}, c'est-à-dire  des fonctions  ayant  comme arguments
d'autres fonctions~:~cela permet par  exemple de créer des fonctions qui
à une fonction dérivable associe sa fonction dérivée.


\subsubsection{Un premier exemple d'algorithme récursif}


Si nous  reprenons notre exemple précédant, nous  pouvons faire exprimer
aux élèves  que l'entier  suivant $n$ est  égal à $1+$  l'entier suivant
$n-1$ : on ne  sort pas des limites du cours de  mathématiques et on n'a
pas besoin  d'introduire des  notions d'informatique en  travaillant sur
cette notion.

On peut écrire un algorithme ainsi~:


\begin{minipage}{\textwidth}
\begin{algorithm}[H]
%\caption{successeur d'un entier~-~version récursive}
\eSi{$n=0$}{1}{$1+$ successeur de $n-1$}
\end{algorithm}\end{minipage}



La  récursivité  n'est  pas  l'apanage des  langages  fonctionnels.  Par
exemple XCAS permet d'écrire des programmes récursifs.

En français~:


\cas
\begin{minipage}{\textwidth}
\begin{lstlisting}
successeur(k):={
 si k==0 alors 1
 sinon 1+successeur(k-1)
 fsi
}:;
\end{lstlisting}\end{minipage}


En anglais~:

\begin{minipage}{\textwidth}
\begin{lstlisting}
successeur(k):={
 if(k==0)then{1}
 else{1+successeur(k-1)}
}:;
\end{lstlisting}\end{minipage}


Que  se passe-t-il  dans  le  c\oe ur  de  l'ordinateur lorsqu'on  entre
\verb+successeur(3)+~?


\begin{itemize}


\item On entre comme argument 3~;

\item Comme 3  n'est pas  égal à 0,  alors \verb+successeur(3)+ est  stocké en
mémoire et vaut
\verb/1+successeur(2)/~;


\item Comme 2 n'est pas égal à 0, alors \verb+successeur(2)+ est stocké en
mémoire et  vaut
\verb/1+successeur(1)/~;


\item Comme 1 n'est pas égal à 0, alors \verb+successeur(1)+ est stocké en
mémoire et  vaut
\verb/1+successeur(0)/~;


\item Cette fois, \verb+successeur(0)+ est connu et vaut 1~;


\item \verb+successeur(1)+ est maintenant connu et vaut \verb/1+successeur(0)/
c'est-à-dire 2~;



\item \verb+successeur(2)+ est maintenant connu et vaut \verb/1+successeur(1)/
c'est-à-dire 3~;


\item \verb+successeur(3)+ est maintenant connu et vaut \verb/1+successeur(2)/
c'est-à-dire 4~:~c'est fini~!

\end{itemize}


C'est  assez  long  comme  cheminement  mais  ce  n'est  pas  grave  car
\emph{c'est  l'ordinateur qui  effectue  le \og  sale boulot\fg{}}~!  Il
stocke les  résultats intermédiaires  dans une \emph{pile}  et n'affiche
finalement que le résultat.

Comme il calcule  vite, ce n'est pas grave. L'élève  ou le professeur ne
s'est occupé que de la définition récursive (mathématique~!) du problème.



\smallskip


XCAS calcule facilement \Com{successeur(700)} mais
\Com{successeur(7000)} dépasse les possibilités de calcul du logiciel.


Et oui, un langage impératif ne traite pas efficacement le problème de pile, 
c'est pourquoi pendant longtemps  seuls les algorithmes
impératifs ont prévalus. 


\smallskip
{\itshape  {\bf Remarque~:}  par défaut,  XCAS  s'arrête au  bout de  50
  niveaux  de récursion.  Pour  aller  plus loin,  il  faut cliquer  sur
  \texttt{config}  à  côté de  \texttt{save}.  Régler  alors la  fenêtre
  \texttt{recurs} à 1000 par exemple}



\smallskip




Utilisons  à   présent  le  langage  fonctionnel   OCAML,  développé  par
l'INRIA\footnote{Institut  National  de  Recherche  en  Informatique  et
  Automatique}. Même s'il intègre  des aspects impératifs pour faciliter
l'écriture de  certains algorithmes, il  est en premier lieu  un langage
fonctionnel  qui en  particulier gère  très efficacement  la  mémoire de
l'ordinateur pour éviter sa saturation lors d'appels récursifs.


Le programme s'écrit comme en mathématique (mais en anglais...)~:


\caml
\begin{minipage}{\textwidth}
\begin{lstlisting}
# let rec successeur(k)=
  if k=0 then 1
  else 1+successeur(k-1);;  
\end{lstlisting}\end{minipage}



Alors par exemple~:

\begin{minipage}{\textwidth}
\begin{lstlisting}
# successeur(36000);;
- : int = 36001
\end{lstlisting}\end{minipage}

Mais

\begin{minipage}{\textwidth}
\begin{lstlisting}
# successeur(3600000);;
Stack overflow during evaluation (looping recursion?).
\end{lstlisting}\end{minipage}


La \emph{pile} où sont stockés les résultats intermédiaires créés par la
récursion est en effet saturée.

Aujourd'hui, les langages fonctionnels  sont très efficaces et gèrent de
manière  intelligente  la  \emph{pile}. Ils le font soit automatiquement,
soit si la fonction utilise une \emph{récursion terminale}, c'est-à-dire
si l'appel récursif à la fonction n'est pas \emph{enrobé} dans une autre
fonction. 

Ici, ce  n'est pas le  cas car l'appel récursif  \Com{successeur(k-1)} est
enrobé dans la fonction $x\mapsto 1+x$.


On peut y  remédier en introduisant une fonction  intermédiaire qui sera
récursive terminale~:

\begin{minipage}{\textwidth}
\begin{lstlisting}
# let rec successeur_temp(k,resultat)=
        if k=0 then resultat
        else successeur_temp(k-1,resultat+1);;
\end{lstlisting}\end{minipage}


puis on appelle cette fonction en prenant comme résultat de départ 1~:

\begin{minipage}{\textwidth}
\begin{lstlisting}
# let successeur_bis(k)=
  successeur_temp(k,1);;
\end{lstlisting}\end{minipage}

Alors~:


\begin{minipage}{\textwidth}
\begin{lstlisting}
# successeur_bis(360000000);;
- : int = 360000001
\end{lstlisting}\end{minipage}

Il n'y a donc aucun problème pour traiter 360 millions d'appels récursifs~!


{\large \bf Dans un premier temps,  on peut laisser de côté ce problème
de récursion terminale au lycée et se contenter de travailler sur de petits
entiers.  Ainsi, on peut  choisir de  travailler avec  OCAML ou  XCAS par
exemple, même si ce dernier n'est pas un langage fonctionnel.}









\subsection{Un premier exemple de fonction d'ordre supérieur}

Définissons  une fonction qui  à deux  fonctions $f$  et $g$  associe sa
composée $f\circ g$~:

\begin{lstlisting}
# let compose=function
   (f,g) -> function x->f(g(x));;
\end{lstlisting}

OCAML devine le type des objets introduits en répondant~:

\begin{lstlisting}
val compose : ('a -> 'b) * ('c -> 'a) -> 'c -> 'b = <fun>
\end{lstlisting}

Ceci signifie que  compose est une fonction (le  \verb+<fun>+ final) qui
prend  comme arguments deux  fonctions (la  première qui  transforme une
variable  de  type \verb+a+  en  une variable  de  type  \verb+b+ et  la
deuxième  qui  transforme une
variable  de type  \verb+c+ en  une variable  de type  \verb+a+)  et qui
renvoie une fonction  qui  transforme une
variable de type  \verb+c+ en une variable de  type \verb+b+. En résumé,
on peut schématiser ce qu'a compris OCAML~:

\[f~:~'a\mapsto  'b \qquad  g~:~'c\mapsto 'a\qquad  f\circ g~:~'c\mapsto
'b\]


Créons deux fonctions numériques~:

\begin{lstlisting}
# let carre = function
      x -> x*x;;

# let double = function
     x -> 2*x;;
\end{lstlisting}

Composons-les~:

\begin{lstlisting}
# compose(double,carre)(2);;
- : int = 8
# compose(carre,double)(2);;
- : int = 16
\end{lstlisting}

En effet, le double du carré de 2  est 8 alors que le carré du double de
2 vaut 16...


On peut faire la même chose avec XCAS~:

\cas

\begin{lstlisting}
compose(f,g):={
  x->f(g(x))
}
\end{lstlisting}

Puis par exemple~:

\begin{lstlisting}
compose(x->x^2,x->2*x)(2)
\end{lstlisting}





\section{Deux manières d'aborder un même problème}

\subsection{Les tours de Hanoï}

\subsubsection{Le principe}

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, $n$  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}


Essayez avec 2 puis 3 disques...  Nous n'osons pas vous demander de résoudre
le problème avec 4 disques~!



\subsubsection{Non pas comment mais pourquoi~:~version récursive}

 En  réfléchissant récursivement,  c'est enfantin~!...  Pour  définir un
 algorithme récursif, il nous
faut régler un cas simple et pouvoir simplifier un cas compliqué.


\begin{itemize}
\item \emph{cas simple}~: s'il y a zéro disque, il n'y a rien à faire~!
\item \emph{simplification d'un cas  compliqué}~: nous avons $n$ disques
  au départ  sur le premier disque  et nous savons  résoudre le problème
  pour $n-1$ disques. Appelons A, B et C les piquets de
  gauche à droite. Il suffit de déplacer les $n-1$ disques supérieurs de
  A vers B (hypothèse de récurrence) puis on déplace le plus gros disque resté sur A en C. Il ne
  reste  plus qu'à  déplacer vers  C les  $n-1$ disques  qui  étaient en
  B. (hypothèse de récurrence).
\end{itemize}

On voit bien  la récursion~:~le problème à $n$ disques  est résolu si on
sait résoudre le cas à $n-1$ disques  et on sait quoi faire quand il n'y
a plus de disques. 



On sait pourquoi  cet algorithme va réussir mais on  ne sait pas comment
s'y prendre étape par étape.

On va donc  appeler à l'aide l'ordinateur en  lui demandant d'écrire les
mouvements effectués à chaque étape.


\caml

On commence par créer une fonction qui affichera le mouvement effectué~:

\begin{lstlisting}
let mvt depart arrivee=
print_string
("Deplace un disque de la tige "^depart^" vers la tige "^arrivee);
print_newline();;
\end{lstlisting}


Le programme proprement dit~:

\begin{lstlisting}
let rec hanoi a b c= function
   | 0 -> ()  (*0 disque : on ne fait rien*)
   | n -> hanoi a c b (n-1); (*n-1 disques sont placés dans l'ordre de a vers b*)
          mvt a c; (*on deplace le disque restant en a vers c*)
          hanoi b a c (n-1) (*n-1 disques sont placés dans l'ordre de b vers c*);;
\end{lstlisting}

Les phrases entre \verb+(*+ et \verb+*)+ sont des commentaires.


Par exemple, dans le cas de 3 disques~:

\begin{lstlisting}
# hanoi "A" "B" "C" 3;;
Deplace un disque de la tige A vers la tige C
Deplace un disque de la tige A vers la tige B
Deplace un disque de la tige C vers la tige B
Deplace un disque de la tige A vers la tige C
Deplace un disque de la tige B vers la tige A
Deplace un disque de la tige B vers la tige C
Deplace un disque de la tige A vers la tige C
- : unit = ()
\end{lstlisting}

\subsubsection{Non pas pourquoi mais comment~:~version impérative}



Prenez un papier et  un crayon. Dessinez trois piquets A, C  et B et les
trois disques dans leur position initiale sur le plot A.

Déplacez alors les disques selon la méthode suivante~:

\begin{itemize}
\item  déplacez le  plus petit  disque vers  le plot  suivant  selon une
  permutation circulaire A-C-B-A ;
\item un seul des deux autres disques est déplaçable vers un seul piquet
  possible.
\end{itemize}

Réitérez (en  informatique à l'aide de boucles...)  ce mécanisme jusqu'à
ce que tous les disques soient sur C dans la bonne position.

On voit donc bien ici comment ça  marche ; il est plus délicat de savoir
pourquoi on arrivera au résultat.

Le programme est lui-même  assez compliqué à écrire~:~vous trouverez une
version en \texttt{C} (235 lignes...) à cette adresse~:

\begin{center}
  \href{http://files.codes-sources.com/fichier.aspx?id=38936\&f=HANOI\%5cHANOI.C}{http://files.codes-sources.com/fichier.aspx?id=38936\&f=HANOI\%5cHANOI.C}
\end{center}





% \section{Avec ou sans affectation~:~quelques exemples}\label{exemples}


\subsection{Suites définies par une relation $u_{n+1}=f(u_n)$}


\subsubsection{Sans affectations}


La relation $u_{n+1}=3u_n+2$ valable pour  tout entier naturel $n$ et la
donnée de $u_0=5$  constituent un algorithme de calcul  récursif de tout
terme de la suite $(u_n)$. 
 


\begin{function}[H]
\caption{u(n,uo)}
\eSi{n=0}{uo}{3$\times$u(n-1,uo)+2}
\end{function}


Sa traduction  dans des langages sachant  plus ou moins  traiter de tels
algorithmes est directe. 


Par exemple, en XCAS, cela devient en français~:

\cas


\begin{minipage}{\textwidth}
\begin{lstlisting}
u(n,uo):={
 si n==0 alors uo
 sinon 3*u(n-1,uo)+2
}
\end{lstlisting}\end{minipage}

et en anglais~:

\begin{minipage}{\textwidth}
\begin{lstlisting}
u(n,uo):={
if(n==0){return(uo)}
else{3*u(n-1,uo)+2}
}
\end{lstlisting}\end{minipage}


En OCAML~:

\caml
\begin{minipage}{\textwidth}
\begin{lstlisting}
# let rec u(n,uo)=
    if n=0 then uo
    else 3*u(n-1,uo)+2;;
\end{lstlisting}\end{minipage}

Ici encore, l'accent est mis sur  le \og pourquoi\fg{} et non pas le \og
comment\fg{} même s'il est beaucoup plus simple de le savoir que dans le
cas des tours de Hanoï. On illustre le cours de 1ère sur les suites.

\subsubsection{Avec affectations}

Au lieu de  stocker de nombreuses
valeurs dans une pile, on affecte  une seule case mémoire aux valeurs de
la suite qui sera \emph{ré-affectée},  au fur et à mesure du déroulement
du programme.




\begin{algorithm}[H]
\caption{Suite récurrente~:~version impérative}
\Entree{n,uo}\;
\Ini{temp\aff uo}\;
\Deb{
\Pour{k de 1 jusque n}{temp\aff 3$\times$ temp+2}
 } 
\end{algorithm}

Cela donne en français avec XCAS~:

\cas



\begin{minipage}{\textwidth}
\begin{lstlisting}
u_imp(n,uo):={
local k,temp;
temp:=uo;
 pour k de 1 jusque n faire
  temp:=3*temp+2;
 fpour
return(temp);
}
\end{lstlisting}\end{minipage}


En anglais~:


\begin{minipage}{\textwidth}
\begin{lstlisting}
u_imp(n,uo):={
local k,temp;
temp:=uo;
for(k:=1;k<=n;k:=k+1){
temp:=3*temp+2;
}
return(temp);
}
\end{lstlisting}\end{minipage}


Dans  ce cas,  on voit  comment faire  pour calculer  $u_n$ à  partir de
$u_0$. La méthode  peut paraître moins \og élégante\fg{}  mais elle est
sûrement plus \og concrètement\fg{} assimilable.

% Il y  avait  un problème  mathématique  et  s'y ajoute  un
% mécanisme  informatique,  l'affectation, qui  pourrait  dans un  premier
% temps s'avérer perturbant pour des élèves de Seconde.

% D'autant plus que la raison d'être informatique de l'affectation - l'économie de mémoire
% -  n'a plus  vraiment  lieu  d'être avec  le  développement de  langages
% fonctionnels  très puissants comme  CAML qui  se débrouillent  très bien
% avec un algorithme récursif.

\subsection{Calculs de sommes}

On veut  calculer la somme des entiers de 1 à $n$.

\subsubsection{Sans affectation}

 Il suffit de
remarquer que cela revient  à ajouter $n$ à la somme des  entiers de 1 à
$n-1$ sachant que la somme des entiers de 1 à 1 vaut... 1.

L'écriture est donc simple et mathématique~:

\begin{function}[H]
%\caption{som\_ent(n)}
\eSi{n=1}{1}{1+som\_ent(n-1)}
\end{function}



En français avec XCAS~:



\begin{minipage}{\textwidth}
\begin{lstlisting}
som_ent(n):={
  si n==1 alors 1
  sinon n+som_ent(n-1)
  fsi
}:;
\end{lstlisting}\end{minipage}


En anglais~:

\begin{minipage}{\textwidth}
\begin{lstlisting}
som_ent(n):={
if(n==1){1}
else{n+som_ent(n-1)}
}:;
\end{lstlisting}\end{minipage}


En OCAML~:


\caml
\begin{minipage}{\textwidth}
\begin{lstlisting}
# let rec som_ent(n)=
     if n=1 then 1
     else n+som_ent(n-1);;
\end{lstlisting}\end{minipage}
 

Par exemple~:

\begin{minipage}{\textwidth}
\begin{lstlisting}
# som_ent(100000);;
- : int = 705082704
\end{lstlisting}\end{minipage}


On peut même généraliser cette procédure à n'importe quelle somme
du type $\displaystyle\sum_{k=k_0}^nf(k)$~:


\begin{minipage}{\textwidth}
\begin{lstlisting}
# let rec som_rec(f,ko,n)=
     if n=ko then f(ko)
     else f(n)+som_rec(f,ko,n-1);;
\end{lstlisting}\end{minipage}



\subsubsection{Avec affectation}


\begin{minipage}{\textwidth}\begin{algorithm}[H]
%\caption{somme des entiers de 1 à n}
\Entree{$n$(entier naturel)}\;
\Ini{S\aff 0}\;
\Deb{
\Pour{k de 1 à n}{S\aff S+k}
\Retour{S}
 } 
\end{algorithm}\end{minipage}

Traduction XCAS en français~:


\cas
\begin{minipage}{\textwidth}
\begin{lstlisting}
som(n):={
local S;
S:=0;
pour k de 1 jusque n faire
  S:=S+k;
fpour;
return(S)
}
\end{lstlisting}\end{minipage}


En anglais~:

\begin{minipage}{\textwidth}
\begin{lstlisting}
som(n):={
local S;
S:=0;
for(k:=1;k<=n;k++){S:=S+k};
return(S)
}
\end{lstlisting}\end{minipage}

On a une approche physique avec l'algorithme impératif~:~S vaut
0  au départ  et on  demande S  en sortie~;  S ne  vaut donc  plus  0 en
général... Cela  peut être troublant  pour des élèves  qui ont du  mal à
résoudre des  équations simples  et oublient ce  qui se cache  derrière le
symbole  \og =\fg{}. Il  y aurait  une égalité  en mathématiques  et une
autre en informatique~!  

Cependant,  cette  manière de  voir  peut  être  plus intuitive~:~si  on
considère S  comme le solde  de son compte  en banque, on  surveille son
compte régulièrement en ajoutant $k$ à chaque visite. Le compte porte le
même nom, S, mais son contenu change régulièrement.

La version impérative peut de plus être directement liée à l'écriture~:

\[\sum_{k=1}^nk\]

qu'on lit  \og somme  des $k$  pour $k$ variant  de 1  à $n$\fg{}  où la
boucle \og pour\fg{} apparaît de manière naturelle.



\subsection{Partie entière}


On   définit la  partie entière  d'un réel $x$  comme étant  le plus
grand entier inférieur à $x$.




\subsubsection{Sans affectation}

On part du fait que la  partie entière d'un nombre appartenant à $[0;1[$
est nulle.

Ensuite, on \og  descend \fg{} de $x$ vers  0 par pas de 1  si le nombre
est positif en montrant que $\lfloor x\rfloor=1+\lfloor x-1\rfloor$.

Si le nombre est négatif, on \og monte\fg{} vers 0 en montrant que $\lfloor x\rfloor=-1+\lfloor x+1\rfloor$.





\begin{function}[H]
%\caption{partie\_entiere(x)}
\eSi{x est positif et x < 1}{0}{
  \eSi{x est positif}{1+partie\_entiere(x$-$1)}{$-1$+partie\_entiere(x+1)}
}
\end{function}



\cas


En français avec XCAS~:

\begin{minipage}{\textwidth}
\begin{lstlisting}
partie_entiere(x):={
  si ((x>=0) et (x<1)) alors 0
  sinon si (x>0)
        alors 1+partie_entiere(x-1)
        sinon -1+partie_entiere(x+1)
        fsi
  fsi   
}
\end{lstlisting}\end{minipage}


En anglais~:

\cas
\begin{minipage}{\textwidth}
\begin{lstlisting}
partie_entiere(x):={
 if((x>=0) and (x<1)){0}
 else{ if(x>0){1+partie_entiere(x-1)}
       else{-1+partie_entiere(x+1)}
    }
}:;
\end{lstlisting}\end{minipage}




En OCAML~:

\caml
\begin{minipage}{\textwidth}
\begin{lstlisting}
# let rec partie_entiere (x)=
        if x >= 0. && x < 1.
         then 0.
         else if x > 0.
               then   1. +. partie_entiere (x -. 1.) 
	       else -.1. +. partie_entiere (x +. 1.);;
\end{lstlisting}\end{minipage}


\textit{Remarque}~:  la  double  esperluette  correspond  à  l'opérateur
logique \og  ET\fg{}. OCAML travaille  avec deux types  de nombres~:~les
entiers et  les flottants. Les  opérations avec les entiers  suivent les
notations habituelles. Lorsqu'on travaille  avec des flottants (c'est le
cas  ici  car  $x$  est  un  réel quelconque)  le  symbole  habituel  de
l'opération est suivi d'un point.

\medskip





On notera que l'algorithme  récursif s'applique ici à des \textbf{réels}
et  non plus  à des  \textbf{entiers} :  on dépasse  ainsi le  cadre des
suites.   Pour  que l'algorithme  fonctionne,  on  raisonne sur  des
intervalles et non plus sur une valeur initiale. 



Ici,  on réfléchit à  la notion \emph{mathématique}  de partie
entière.   On   met   en   place  des   résultats   \emph{mathématiques}
intéressants.


\subsubsection{Avec affectation}


Pour les nombres positifs, on part de
0.  Tant qu'on  n'a  pas dépassé  $x$,  on avance  d'un  pas. La  boucle
s'arrête dès  que $k$ est strictement  supérieur à $x$.  La partie entière
vaut donc $k-1$.


Dans le  cas d'un réel  négatif, il faut  cette fois reculer d'un  pas à
chaque tour de boucle et la partie entière est la première valeur de $k$
à être inférieure à $x$~:


\begin{minipage}{\textwidth}\begin{algorithm}[H]
%\caption{partie entière d'un réel quelconque}
\Entree{$x$(réel)}\;
\Ini{k \aff 0}\;
\Deb{
\eSi{x>=0}{
\Tq{k<=x}{k\aff k+1}\;
\Retour{k-1}
}{
\Tq{k>x}{k\aff k-1}\;
\Retour{k}
}
}
\end{algorithm}\end{minipage}



Avec XCAS en Français~:






\cas
\begin{minipage}{\textwidth}
\begin{lstlisting}
pe(x):={
local k;
k:=0;
si x>=0 alors
   tantque k<=x faire
      k:=k+1;
   ftantque;
   return(k-1);
sinon 
   tantque k>x faire
      k:=k-1;
   ftantque;
   return(k); 
fsi;  
}:;
\end{lstlisting}\end{minipage}

Avec XCAS en anglais~:



\begin{minipage}{\textwidth}
\begin{lstlisting}
pe(x):={
local k;
k:=0;
if(x>=0){
   while(k<=x){k:=k+1};
   return(k-1);
        }
else{
   while(k>x){k:=k-1};
   return(k); 
    } 
}:;
\end{lstlisting}\end{minipage}




On utilise ici une affectation ($k$ devient $k+1$ ou
$k-1$)  et  une  \og  boucle  while\fg{}  avec un  test  et  une  action
d'affectation  tant que  le test  est  vrai. Il  s'agit d'un  traitement
physique de la mémoire. On perd un peu de vue la notion mathématique mais on donne
une  vision dynamique  de la  recherche de  la partie  entière~:~on peut
imaginer un  petit \og  personnage\fg{} se promenant  sur la  droite des
réels  en faisant  des  pas de  longueur  1 et  qui  continue à  avancer
\emph{tant qu'} il n'a pas dépassé le réel. 


\subsection{Développement en fractions continues}
\subsubsection{ Pratique du développement}

 \begin{itemize}
  
\item Vous connaissez l'algorithme suivant~:

\begin{minipage}{\textwidth}
\begin{eqnarray}
172&=&3\times\textcolor{0.2white}{51}+\textcolor{0.2white}{19}\\
\textcolor{0.2white}{51}&=&2\times\textcolor{0.2white}{19}+13\\
19&=&1\times13+6\\
13&=&2\times 6+1\\
6&=&6\times 1+0
\end{eqnarray}
\end{minipage}

\item On peut donc facilement compléter  la suite d'égalité suivante~:


\begin{minipage}{\textwidth}
\[\frac{172}{51}=3+\frac{19}{51}=3+\frac{1}{\frac{51}{19}}=3+\frac{1}{2+\frac{13}{19}}=\dots     \]
\end{minipage}

\item Quand tous les numérateurs sont égaux à 1, on dit qu'on a développé $\frac{172}{51}$ en
  fraction continue et pour simplifier l'écriture on note~:
\[\frac{172}{51}=[3; 2; \dots ]\]

\item Par exemple, on peut développer  $\frac{453}{54}$ en fraction continue.

\item Dans l'autre sens on peut écrire $[2; 5; 4]$ sous la forme d'une fraction irréductible.

  \end{itemize}

Nous allons construire les algorithmes correspondant.

\subsubsection{sans affectation}


On suppose connus les algorithmes  donnant le reste et le quotient d'une
division euclidienne.


\begin{minipage}{\textwidth}\begin{algorithm}[H]
%\caption{fractions continues : version récursive}\label{fc}
fc(a,b)\;
\eSi{b=0}{\Retour{liste vide}}{
\Retour{[quotient(a,b),fc(b,reste(a,b))]}
} 
\end{algorithm}\end{minipage}

En français en XCAS~:




\begin{minipage}{\textwidth}
\begin{lstlisting}
fc(a,b):={
  si b==0 alors [] 
  sinon concat(iquo(a,b),fc(b,irem(a,b)))
  fsi
}:;
\end{lstlisting}\end{minipage}



En anglais~:


\begin{minipage}{\textwidth}
\begin{lstlisting}
fc(a,b):={
  if(b==0)then{[]}
  else{concat(iquo(a,b),fc(b,irem(a,b)))}
}:;
\end{lstlisting}\end{minipage}


La commande \verb+concat(élément,liste)+  ajoute \verb+élément+ au début
de \verb+liste+.


Alors \verb+fc(172,51)+ renvoie \verb+[3,2,1,2,6]+


En OCAML

\caml

\begin{minipage}{\textwidth}
\begin{lstlisting}
# let rec fc (a,b) =
        if b = 0
         then []
         else  a/b :: fc(b,a-a/b*b);;
\end{lstlisting}\end{minipage}



Pour  ajouter  un  élément  à  une  liste  sur  OCAML,  la  syntaxe  est
\verb+élément::liste+.

\medskip

L'algorithme est très simple à écrire et à comprendre.

\subsubsection{Avec affectation}


\begin{minipage}{\textwidth}\begin{algorithm}[H]
%\caption{Fractions continues~:~version impérative}
\Entree{2 entiers a et b}\;
\Ini{\;
num\aff a\;
den\aff b\;
res\aff reste(num,den)\;
Liste\aff vide\;
}\;
\Deb{
\Tq{res$\neq$0}{
Liste\aff Liste,quotient(num,den)\;
num\aff den\;
den\aff res\;
res\aff reste(num,den)\;
}
 }
\Retour{[Liste,quotient(num,den)]} 
\end{algorithm}\end{minipage}

En français avec XCAS~:

\cas
\begin{minipage}{\textwidth}
\begin{lstlisting}
frac_cont(a,b):={
local num,den,res,Liste;
num:=a;
den:=b;
res:=irem(num,den);
Liste:=NULL;
 tantque res>0 faire
    Liste:=Liste,iquo(num,den);
    num:=den;
    den:=res;
    res:=irem(num,den);
 ftantque
return([Liste,iquo(num,den)]);
}:;
\end{lstlisting}\end{minipage}

En anglais~:

\cas
\begin{minipage}{\textwidth}
\begin{lstlisting}
frac_cont(a,b):={
local num,den,res,Liste;
num:=a;
den:=b;
res:=irem(num,den);
Liste:=NULL;
while(res>0){
    Liste:=Liste,iquo(num,den);
    num:=den;
    den:=res;
    res:=irem(num,den);
}
return([Liste,iquo(num,den)]);
}:;
\end{lstlisting}\end{minipage}


Ici, 
la manipulation de plusieurs niveaux d'affectation et d'une boucle while
est assez délicate. La chronologie des affectations est primordiale~:~on
ne peut proposer cette version à des débutants...

% \subsection{Décomposition en base 2}

% \subsubsection{Expérimentation}

% Une  méthode  pour  obtenir  l'écriture   en  base  2  d'un  nombre  est
% d'effectuer des divisions successives. Par exemple pour 11~:
% \begin{minipage}{\textwidth}
% \begin{center}
% \opidiv[remainderstyle=\bfseries\large\color{0.2white},resultstyle=\color{blue}]{11}{2}\hspace{1cm}
% \opidiv[remainderstyle=\bfseries\large\color{0.2white},resultstyle=\color{blue}]{5}{2}
% \hspace{1cm}
% \opidiv[remainderstyle=\bfseries\large\color{0.2white},resultstyle=\color{blue}]{2}{2}
% \hspace{1cm}
% \opidiv[remainderstyle=\bfseries\large\color{0.2white},resultstyle=\color{blue}]{1}{2}

% \end{center}
% \end{minipage}


% \begin{minipage}{\textwidth}
% \begin{align*}
% 11 &=\Bigl(2\times5+1\Bigr)
% \\ &=\Bigl(2\times\bigl(2\times2+1\bigr)+1\Bigr)
% \\ &=\Bigl(2\times\bigl(2\times(2\times 1)+1\bigr)+1\Bigr)
% \\ &=\Bigl(2\times (2^2+1)+1\Bigr)
% \\ &=2^3+2+1
% \\ &=1\times 2^3+0\times 2^2+1\times 2^1+1\times 2^0 
% \end{align*}
% \end{minipage}


% L'écriture de  11 en base  2 est donc  1011~:~c'est la liste  des restes
% obtenus mais dans l'ordre inverse.


% La méthode est facilement généralisable.



% \subsubsection{Version récursive}

% Notons $q_n$ et $r_n$ le quotient et le reste après $n$ divisions.

% $q_{n+1}$ est le quotient entier de  $q_n$ par 2 et on rajoute $r_{n+1}$
% à notre liste de restes.




% Après  un certain  nombre  de divisions,  le  quotient sera  strictement
% inférieur à 2.



% \begin{minipage}{\textwidth}\begin{function}[H]
% \caption{Binaire(n)}
% \eSi{n<2}{n}{Binaire(quotient(n,2)),reste(n,2)} 
% \end{function}\end{minipage}




% Ce qui donne en français avec XCAS~:




% \begin{minipage}{\textwidth}
% \begin{lstlisting}
% Binaire(n):={
%     si n<2 alors n
%     sinon Binaire(iquo(n,2)),irem(n,2)
%     fsi
% }
% \end{lstlisting}\end{minipage}









% En anglais~:

% \begin{minipage}{\textwidth}
% \begin{lstlisting}
% Binaire(n):={
%     if (n<2){ n}
%     else{Binaire(iquo(n,2)),irem(n,2)}
% }
% \end{lstlisting}\end{minipage}


% et en CAML~:
% \caml

% \begin{minipage}{\textwidth}
% \begin{lstlisting}
% # let rec binaire n =
%         if n<2 
%           then [n]
%         else  binaire(n/2) @ [n mod 2];;
% \end{lstlisting}\end{minipage}


% {\itshape    On utilise \verb+liste  1 @ liste 2+ pour  concaténer deux listes et
%     \verb+ élément :: liste+ pour rajouter un élément en début de liste.
%  } 


% \subsubsection{Version impérative}


% \begin{minipage}{\textwidth}\begin{algorithm}[H]
% %\caption{décomposition en base 2}
% \Entree{un entier $n$}\;
% \Ini{\;
% $r$\aff le reste de la division de $n$ par 2\;
% $q$\aff le quotient de la division de $n$ par 2\;
% R une liste contenant $r$ au départ.
% }\;
% \Deb{
% \Tq{q>0}{
% r\aff le reste de la division de $q$ par 2\;
% $q$\aff le quotient de la division de $q$ par 2\;
% On ajoute r au début de la liste R.
% }
% \Retour{R}
%  } 
% \end{algorithm}\end{minipage}

% En XCAS~:


% Comme dans la plupart des langages de calcul, le reste et le quotient de la division
% euclidienne   de   a   par    b   sont   obtenus   respectivement   avec
% \texttt{irem(a,b)} et \texttt{iquo(a,b)}.

% On concatène deux listes avec \texttt{concat(L1,L2)}.


% En français avec XCAS~:

% \cas
% \begin{minipage}{\textwidth}
% \begin{lstlisting}
% base_deux(n):={
% local r,R,q;
% r:=irem(n,2);
% q:=iquo(n,2);
% R:=[r];
%  tantque q>0 faire
%   r:=irem(q,2);
%   q:=iquo(q,2);
%   R:=concat([r],R); 
%  ftantque
% return(R)
% }
% \end{lstlisting}\end{minipage}



% En anglais~:


% \begin{minipage}{\textwidth}
% \begin{lstlisting}
% base_deux(n):={
% local r,R,q;
% r:=irem(n,2);
% q:=iquo(n,2);
% R:=[r];
%  while(q>0){
%    r:=irem(q,2);
%    q:=iquo(q,2);
%    R:=concat([r],R); 
%  }
% return(R)
% }
% \end{lstlisting}\end{minipage}




% On peut bien sûr généraliser ceci à n'importe quelle base.



\subsection{Dichotomie}


Pour résoudre une équation  du type $f(x)=0$, on recherche graphiquement
un intervalle $[a,b]$ où la fonction semble changer de signe.

On note ensuite $m$ le milieu du segment $[a,b]$. On évalue le signe de $f(m)$.

Si c'est  le même  que celui  de $f(a)$ on  remplace $a$  par $m$  et on
recommence.  Sinon, c'est $b$  qu'on remplace  et on  recommence jusqu'à
obtenir la précision voulue.





\subsubsection{Sans affectation}

On appellera \texttt{eps} la précision voulue.


\begin{minipage}{\textwidth}\begin{function}[H]
%\caption{dicho\_rec(f,a,b,eps)}
\eSi{b-a est plus petit que la précision eps}{
(b+a)/2}{
\eSi{f(a) et f((b+a)/2) sont de même signe }
{dico\_rec(f,(b+a)/2,b,eps)}
{dicho\_rec(f,a,(b+a)/2,eps)}
} 
\end{function}\end{minipage}

On  remarquera  ici que  la  récursion  se  fait sans  faire  intervenir
d'entier~:~le test d'arrêt est effectué sur la précision du calcul.

On va rajouter justement un  compteur pour savoir combien de calculs ont
été effectués.


\cas

En français avec XCAS~:



\begin{lstlisting}
dicho_rec(f,a,b,eps,compteur):={
 si evalf(b-a)<eps alors 0.5*(b+a),compteur+1
 sinon si f(a)*f(0.5*(b+a))>0
       alors dicho(f,0.5*(b+a),b,eps,compteur+1)
       sinon dicho(f,a,0.5*(b+a),eps,compteur+1)
       fsi
 fsi
}:;
\end{lstlisting}






\begin{lstlisting}
dicho_rec(f,a,b,eps,compteur):={
if(evalf(b-a)<eps){0.5*(b+a),compteur+1};
if(f(a)*f(0.5*(b+a))>0){dicho(f,0.5*(b+a),b,eps,compteur+1)}
                   else{dicho(f,a,0.5*(b+a),eps,compteur+1)}
}:;
\end{lstlisting}

En OCAML~:

\caml

\begin{lstlisting}
# let rec dicho_rec(f,a,b,eps,compteur)=
    if abs_float(b-.a)<eps then 0.5*.(b+.a),compteur+1
    else if f(a)*.f(0.5*.(b+.a))>0. then dicho_rec(f,0.5*.(b+.a),b,eps,compteur+1)
         else  dicho_rec(f,a,0.5*.(b+.a),eps,compteur+1);;
\end{lstlisting}



ce qui donne~:


\begin{lstlisting}
# dicho_rec( (fun x->(x*.x-.2.)),1.,2.,0.00001,0);;
- : float * int = (1.41421127319335938,18)
\end{lstlisting}

\cas



\subsubsection{Avec affectation}

\begin{algorithm}[H]
%\caption{dichotomie}
\Entree{une fonction f, les bornes a et b, une précision p}\;
\Ini{aa\aff a, bb\aff b}\;
\Deb{
\Tq{bb-aa>p}{
\eSi{signe  de  f((aa+bb)/2) est  le  même  que  celui de  f(bb)}{bb\aff
  (aa+bb)/2}{aa\aff (aa+bb)/2}
}
\Retour{(aa+bb)/2}
 } 
\end{algorithm}


Avec XCAS, il faut juste ne  pas oublier de régler quelques problèmes de
précision. On  rajoute aussi pour le  plaisir un compteur  qui nous dira
combien de \og tours de boucles\fg{} le programme aura effectué.



\begin{lstlisting}
dicho(F,p,a,b):={
local aa,bb,k,f;
aa:=a;
bb:=b;
epsilon:=1e-100; 
f:=unapply(F,x);
compteur:=0; 
 while(evalf(bb-aa,p)>10^(-p)){
    if( f(0.5*(bb+aa))*f(bb)>0 )
      then{bb:=evalf((aa+bb)/2,p+1)}
      else{aa:=evalf((aa+bb)/2,p+1)}
      k:=k+1; 
    }
return evalf((bb+aa)/2,p+1)+" est la  solution trouvée après " +(k+1)+ "itérations";
}:;
\end{lstlisting}

En reprenant le même exemple~:

\begin{lstlisting}
dicho(x^2-2,5,1,2)
\end{lstlisting}

On obtient la même réponse~:

\begin{center}
  \verb+1.414211273 est la solution trouvee  apres 18 iterations+
\end{center}

Les deux versions sont ici  assez similaires avec toujours peut-être une
plus grande simplicité d'écriture dans le cas récursif.



% \subsection{Méthode des rectangles}


% \subsubsection{Version récursive}

% On  veut  calculer une  intégrale  d'une  fonction  par la  méthode  des
% rectangles. La  définition récursive  est assez naturelle,  dynamique et
% permet de bien comprendre la construction de l'intégrale~:



% \begin{minipage}{\textwidth}\begin{function}[H]
% \caption{integ(f,a,b,dx)}
% \eSi{a>b}{0}{f(a)$\times$ dx+integ(f,a+dx,b,dx)} 
% \end{function}\end{minipage}


% Cela donne en CAML~:

% \caml

% \begin{lstlisting}
% # let rec integ(f,a,b,dx)=
%       if a>b then 0.
%       else f(a)*.dx+.integ(f,a+.dx,b,dx);;
% \end{lstlisting}

% Par exemple~:

% \begin{lstlisting}
% # let g(x)=x;;

% # integ(g,0.,1.,0.0001);;
% \end{lstlisting}

% donne~:

% \begin{lstlisting}
% - : float = 0.500049999999960249
% \end{lstlisting}

% C'est-à-dire $\displaystyle\int_0^1x{\rm d }x\approx 0.5$


% Pour améliorer l'approximation, il faudrait en fait améliorer la méthode
% mathématique... 


% \subsubsection{Version impérative}


% \begin{algorithm}[H]
% \caption{Méthode des rectangles}
% \Entree{f,a,b,dx}\;
% \Ini{S\aff 0\;
% an\aff a}\;
% \Deb{
% \Tq{an<b}{S\aff S+f(an)$\times$ dx\;
%           an\aff an+dx}
% \Retour S
%  } 
% \end{algorithm}


% \cas

% Avec XCAS en français~:


% \begin{lstlisting}
% integ(f,a,b,dx):={
% local S,an;
% S:=0;
% an:=a;
%  tantque an<b faire
%    S:=S+f(an)*dx;
%    an:=an+dx;
%  ftantque
% return(S)
% }
% \end{lstlisting}

% En anglais~:


% \begin{lstlisting}
% integ(f,a,b,dx):={
% local S,an;
% S:=0;
% an:=a;
%  while(an<b){
%    S:=S+f(an)*dx;
%    an:=an+dx;
%  }
% return(S)
% }:;
% \end{lstlisting}

% \section{Calcul  du  PGCD  par  l'algorithme  d'Euclide  et  un  exemple
%   d'application au calcul avec des fractions}



% Un  sujet  phare  de  la  future Seconde  est  l'étude  de  l'algorithme
% d'Euclide.   Il   permet   d'écrire   que,   si   $b$   est   non   nul,
% $PGCD(a,b)=PGCD(b,reste(a,b))$~:~c'est  un  mécanisme  récursif  qui  se
% traduit naturellement.




% \begin{minipage}{\textwidth}\begin{function}[H]
% \caption{pgcd(a,b)}
% \eSi{b=0}{a}{Binaire(quotient(n,2)),reste(n,2)} 
% \end{function}\end{minipage}







% En CAML~:

% \caml
% \begin{minipage}{\textwidth}
% \begin{lstlisting}
% # let rec pgcd (a,b) =
%          if b=0
%           then a
%           else  pgcd(b,a-a/b*b);;
% \end{lstlisting}
% \end{minipage}

% CAML  travaille par défaut  avec des  entiers donc  a/b est  le quotient
% entier de la division de a par  b. Ainsi a-a/b*b est en fait le reste de
% la division euclidienne de a par b. 



% En français avec XCAS~:



% \cas
% \begin{minipage}{\textwidth}
% \begin{lstlisting}
% pgcd(a,b):={
%  si b==0 alors  a
%  sinon pgcd(b,irem(a,b))
%  fsi
% }
% \end{lstlisting}
% \end{minipage}




% En anglais~:

% \cas
% \begin{minipage}{\textwidth}
% \begin{lstlisting}
% pgcd(a,b):={
%  if(b==0)then{a}
%  else{pgcd(b,irem(a,b))}
% }
% \end{lstlisting}
% \end{minipage}


% Cela   va  nous  permettre   de  construire   les  opérations   sur  les
% fractions. Voyons comment procéder avec CAML.


% On va représenter une fraction par une liste du type [numérateur;dénominateur].

% Pour prévenir toute division par  zéro on va créer une  \emph{exception}  qu'on  nommera  \texttt{Division\_par\_zero}  et  qui  nous
% servira de garde-fou~:
% \caml
% \begin{lstlisting}
% # exception Division_par_zero;;
% \end{lstlisting}


% On invoquera cette exception avec la commande \texttt{raise}~:~étant
% donné le niveau d'anglais des élèves, cette commande est naturelle...

% On peut créer un opérateur qui simplifie les fractions~:

% \begin{minipage}{\textwidth}
% \begin{lstlisting}
% # let simp([a;b]) = 
%  if b=0 then raise Division_par_zero
%  else [a/pgcd(a,b);b/pgcd(a,b)];;
% \end{lstlisting}
% \end{minipage}

% Ne pas tenir compte du \og  Warning\fg{} qui indique juste que le cas où
% on entre une liste vide n'a pas été prévu.

% On crée ensuite une somme simplifiée de fractions~:

% \begin{minipage}{\textwidth}
% \begin{lstlisting}
% # let som([a;b],[c;d]) =
%   if b=0 or d=0 then raise Division_par_zero else
%   simp([a*d+b*c;b*d]);;
% \end{lstlisting}
% \end{minipage}



% Par exemple~:

% \begin{minipage}{\textwidth}
% \begin{lstlisting}
% # som([2;3],[1;6]);;
% - : int list = [5; 6]
% \end{lstlisting}
% \end{minipage}

% Une multiplication~:

% \begin{minipage}{\textwidth}
% \begin{lstlisting}
% #  let mul([a;b],[c;d]) =
%   if b=0 or d=0 then raise Division_par_zero else
%   simp([a*c;b*d]);;
% \end{lstlisting}
% \end{minipage}


% Par exemple~:

% \begin{minipage}{\textwidth}
% \begin{lstlisting}
% # mul([3;2],[2;9]);;
% - : int list = [1; 3]
% \end{lstlisting}
% \end{minipage}


% Un inverse~:

% \begin{minipage}{\textwidth}
% \begin{lstlisting}
% #  let inv([a;b]) =
%   if b=0 or a=0 then raise Division_par_zero else
%   simp([b;a]);;
% \end{lstlisting}
% \end{minipage}


% Une division~:

% \begin{minipage}{\textwidth}
% \begin{lstlisting}
% # let div([a;b],[c;d])=mul([a;b],inv([c;d]));;
% \end{lstlisting}
% \end{minipage}



% Par exemple, comment entrer 

% \begin{minipage}{\textwidth}
% \[1+\frac{2+\frac{3}{4}}{1-\frac{5}{6}}\]
% \end{minipage}

% \begin{minipage}{\textwidth}
% \begin{lstlisting}
% # som([1;1],div(som([2;1],[3;4]),som([1;1],[-5;6])));;
% - : int list = [35; 2]
% \end{lstlisting}
% \end{minipage}

% Évidemment,  c'est moins  pratique  que  de taper  le  résultat sur  une
% machine mais  ça permet  de réfléchir aux  différentes opérations,  à la
% notion de fonction,...

% On aurait pu écrire les même instructions en XCAS.



\section{Algorithme récursif ne signifie pas \boldmath$u_{n+1}=f(u_n)$\unboldmath}

Si les suites définies par une relation $u_{n+1}=f(u_n)$ sont facilement
décrites par un algorithme récursif,  ce n'est pas le seul champ d'action
de la récursion.

Dès  qu'on  connaît  une  situation  simple  et  qu'on  est  capable  de
simplifier une situation compliquée, on peut utiliser la récursion.


\subsection{Longueur d'une liste}

Par exemple, si on veut calculer la longueur d'une liste~:

\begin{itemize}
\item la liste vide est de longueur nulle (cas simple)~;
\item la longueur d'une liste est égale à 1+la longueur de la liste sans
  son premier élément.
\end{itemize}



Cela donne en traduction directe~:

\caml
\begin{lstlisting}
# let rec longueur = function
              [] -> 0
   | tete::corps -> 1+longueur(corps);;
\end{lstlisting}

La  barre verticale  permet  de  définir une  fonction  par morceaux  en
distinguant les cas.

L'écriture  \verb+x::liste+ signifie  qu'on rajoute  $x$ en  tête  de la
liste \texttt{liste}.

CAML trouvant lui-même le type des variables utilisées sait qu'on va lui
entrer  une liste  de n'importe  quoi (puisqu'on  peut l'écrire  sous la
forme \texttt{tete} rajoutée à \texttt{corps}) et que \texttt{longueur} sera un entier
(puisqu'on lui ajoute 1).

C'est mathématique...


\subsection{Somme et multiplication d'entiers}


Supposons  que  nous  ne  sachions  que  trouver  le  successeur  ou  le
prédécesseur d'un
entier. Comment additionner deux entiers quelconques~?


\begin{lstlisting}
# let rec add = function
          (0,x) -> x
  |       (x,y) -> add((x-1),y)+1;;
\end{lstlisting}


Additionner  $x$ et  $y$ c'est  prendre le  successeur de  l'addition du
prédécesseur de $x$ et de $y$...c'est-à-dire~:~$x+y=\big((x-1)+y\big)+1$
sachant que $0+x=x$.

\medskip

Pour la multiplication~:


\begin{lstlisting}
# let rec mult = function
     (0,x)->0
  | (x,y)->add(mult(x-1,y),y);;
\end{lstlisting}

C'est-à-dire~:~$0\times x=0$ et $x\times y=\big((x-1)\times y\big)+y$


C'est mathématique...




\section{Alors : avec ou sans affectation~?} 


Beaucoup de  professeurs (et donc  d'élèves...) sont habitués  à traiter
certains    problèmes   à    l'aide   d'un    tableur...qui   fonctionne
récursivement~!

En   effet,  pour   étudier  par   exemple  les   termes  de   la  suite
$u_{n+1}=3u_n+2$ de $n=1$ à $n=30$ avec $u_1=7$, on entre $=7$ dans la cellule $A1$
et $=3*A29+2$ dans la cellule $A30$ et on \og
fait  glisser\fg{} de la  cellule $A30$  jusqu'à la  cellule $A2$.  On a
plutôt l'habitude de faire glisser vers le bas mais pourquoi pas vers le
haut~!

Passer  d'un  \og  faire   glisser\fg{}  à  l'écriture  de  l'algorithme
correspondant  est une  évolution naturelle  ce que  l'introduction d'un
langage impératif n'est pas.

La  notion de  fonction est  naturellement illustrée  par l'utilisation
d'un  langage   fonctionnel  alors  que  les   procédures  des  langages
impératifs peuvent prêter à confusion.

\medskip

Comme  de nombreux  collègues,  j'assure des  \og  colles MAPLE\fg{}  en
classes préparatoires scientifiques  depuis plusieurs années. Les élèves
de ces  classes ont habituellement un niveau  en mathématiques supérieur
au niveau moyen rencontré en Seconde et pourtant la plupart des étudiants
éprouve de  réelles difficultés à maîtriser un  langage de programmation
impératif  comme MAPLE  et certains  n'y  arrivent pas  après une  année
d'initiation~!


Évidemment, nous  n'aborderons pas les mêmes problèmes en Seconde
mais pouvoir se concentrer  sur les mathématiques et simplement traduire
nos idées  grâce au clavier de  manière assez directe  nous permettra de
préserver nos  élèves de nombreux  pièges informatiques sans  parler des
notions trompeuses que l'affectation peut introduire dans leurs esprits.


Cependant, utiliser des algorithmes  récursifs nécessite de maîtriser un
tant soit peu...  la notion de récurrence. Or cette étude a été réservée
jusqu'à maintenant aux  seuls élèves de Terminale S.  L'étude des suites
débute depuis de nombreuses années en Première et chaque professeur a fait
l'expérience des difficultés des élèves à maîtriser cette notion.

Ainsi, même si  (ou plutôt parce que) les  algorithmes récursifs peuvent
apparaître   proches  des   notions   mathématiques  qu'ils   permettent
d'étudier, ils demandent de comprendre une notion mathématique délicate,
la récurrence,  même si l'étude  des phénomènes évolutifs  modélisés par
une  relation   $u_{n+1}=f(u_n)$  a   failli  entrer  au   programme  de
Seconde~!...

Il  faut surtout  noter que  le  champ  d'action des  algorithmes
récursifs  dépasse  largement la  notion  de  suite  numérique. On  peut
raisonner récursivement dès  qu'on connaît un état simple  et qu'on peut
simplifier un état compliqué.

D'un autre côté, les algorithmes utilisant les affectations contournent la difficulté de
la récurrence, facilitent l'étude de certains mécanismes comme le calcul
matriciel, permettent souvent une illustration \og physique\fg{}
d'un phénomène  mathématique et en tous cas  complémentaire des versions
sans affectation.

Ils doivent de plus être étudiés car ils sont largement répandus dans
le monde informatique.



\medskip


Il ne faut enfin pas oublier les difficultés que pourraient rencontrer des
professeurs  de  mathématiques n'ayant  pas  réfléchi  à ces  problèmes
d'algorithmique et  qui ne pourront  pas être formé(e)s avant  de devoir
enseigner une notion méconnue, sans manuels et sans le recul nécessaire.


\medskip

Mais  il ne  faudrait pas  pour autant  abandonner l'idée  d'initier les
élèves à  une \og  algorithmique raisonnée\fg{}. La  notion de  test par
exemple (SI...ALORS...SINON) est tout à fait abordable par le plus grand
nombre... et  dans tout  style de programmation.  La notion  de fonction
peut  être étudiée  sans  danger  avec un  langage  fonctionnel et  avec
prudence avec un langage impératif. D'un point de vue plus informatique,
faire découvrir aux  élèves que le \og dialogue\fg{}  avec la machine ne
se réduit pas à des \og clics\fg{} mais que chacun peut \og parler\fg{}
presque  directement à  la machine  en lui  tapant des  instructions est
également un apprentissage enrichissant.


Quant au match avec ou sans affectation, il ne peut se terminer par
l'élimination d'un des participants~:~il faut savoir que l'un ou l'autre
sera plus adapté à la résolution d'un 
problème et
l'emploi \textbf{combiné}  des deux types de  programmation abordés dans
cet article peut surtout permettre d'illustrer sous des angles différents une
même notion mathématique et  donc illustrer de manière enrichissante nos
cours,
 ce qui induit la nécessité de connaître différentes manières de
procéder pour choisir la plus efficace. Cela accroît d'autant plus la
difficulté d'une introduction improvisée de l'algorithmique au lycée...





Mais les difficultés rencontrées par les
étudiants débutants  de l'enseignement supérieur doivent  nous inciter à
la prudence et à nous demander si un enseignement informatique optionnel
en seconde et plus poussé  dans les classes scientifiques supérieures ne
serait  pas plus souhaitable.  On pourra  lire à  ce sujet  l'opinion de
Bernard \textsc{Parisse}, développeur de XCAS\footnote{\href{http://www-fourier.ujf-grenoble.fr/~parisse/irem.html\#algo}{http://www-fourier.ujf-grenoble.fr/~parisse/irem.html\#algo}}.


% Il  est  sûr qu'il  ne  s'agit  pas de  bannir  les  boucles et  les
% affectations  d'une  quelconque   initiation  à  la  programmation.  Par
% exemple,  de nombreux  algorithmes  sur le  calcul  matriciel sont  plus
% facilement exprimables  à l'aide d'un langage  impératif. Cependant, les
% notions mathématiques abordées en Seconde sont suffisamment simples pour
% être naturellement  traitées récursivement ce  qui permettra de  plus de
% travailler  sur une  notion importante  jusqu'ici abordée  par  tous les
% élèves du Lycée général et technologique.



% Pourquoi  alors  ne  pas  réserver  une initiation  à  la  programmation
% impérative à un enseignement optionnel ou à des élèves
% ayant choisi  un cursus scientifique  à partir de  la première ou  de la
% terminale~?  

% Après avoir  découvert la programmation dans un  cadre mathématique, les
% esprits  des  élèves  (et   des  professeurs...)  seront  sûrement  plus
% à même de l'aborder dans un cadre purement informatique.



\section{Documentation et prolongements}

De  nombreux  algorithmes pour  le  lycée  sont  catalogués à  l'adresse
suivante :

\href{http://download.tuxfamily.org/tehessinmath/les\%20pdf/PafAlgo.pdf}{http://download.tuxfamily.org/tehessinmath/les\%20pdf/PafAlgo.pdf}


Liens pour CAML : 

\begin{itemize}
\item Une     passionnante
  introduction à OCAML par deux de ses papas...
\href{http://caml.inria.fr/pub/distrib/books/llc.pdf}{http://caml.inria.fr/pub/distrib/books/llc.pdf}

\item Le     manuel
  de référence de CAML par Xavier \textsc{Leroy} et Pierre \textsc{Weis}
\href{http://caml.inria.fr/pub/distrib/books/manuel-cl.pdf}{http://caml.inria.fr/pub/distrib/books/manuel-cl.pdf}

\item            Une            introduction           à            CAML
  \href{http://fr.wikibooks.org/wiki/Objective\_Caml}{http://fr.wikibooks.org/wiki/Objective\_Caml}

\item Ressources OCAML \href{http://www.pps.jussieu.fr/Livres/ora/DA-OCAML/}{http://www.pps.jussieu.fr/Livres/ora/DA-OCAML/}
\end{itemize}



Liens pour XCAS : 

\begin{itemize}
\item la maison mère 
\href{http://www-fourier.ujf-grenoble.fr/\%7Eparisse/giac\_fr.html}{http://www-fourier.ujf-grenoble.fr/\%7Eparisse/giac\_fr.html}
\item de nombreux exemples d'utilisation au lycée
\href{http://tehessin.tuxfamily.org}{http://tehessin.tuxfamily.org}
\end{itemize}


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

