% This  work is licensed under  the Creative Commons  GNU General Public
% License License.  To view a copy of this license, visit
%  http://creativecommons.org/licenses/GPL/2.0/   or  send  a   letter  to
%  Creative  Commons,  171  Second   Street,  Suite  300,  San  Francisco,
%  California, 94105, USA. 
% Copyleft Guillaume CONNAN http://tehessin.tuxfamily.org

\documentclass[11pt,a4paper,svgnames]{report}
\usepackage{etex}
\usepackage[height=256mm,width=185mm]{geometry}
\usepackage[french,vlined,boxed]{algorithm2e}
\usepackage[kpfonts,biblio]{preambule}
\usepackage{cclicenses}
\usepackage{xlop}
\usepackage{keystroke}

%\usepackage[colorlinks=true,citecolor=red,dvips]{hyperref}

%\usepackage[Lenny]{fncychap}








 % \DeclareMathSymbol{\mthdotlessiup}{\mathalpha}{operators}{16}%
\definecolor{0.1white}{rgb}{.1,.1,.1}

%\usepackage[upright]{fourier}
%\usepackage[upright]{kpfonts}
%\usepackage[scaled=0.85]{luximono}
%\usepackage{lmodern}
% \usepackage[boldsans]{ccfonts}
% \usepackage{beton,euler,luximono}

\graphicspath{{/home/moi/Lycee/2nde/2009_10/}{/home/moi/Photos/Maths/}{/home/moi/Figures/FigSTI/}{/home/moi/Figures/FigSeconde/}{/home/moi/Figures/figuresTS/}{/home/moi/Lycee/TDmaple/2007_8/}{/home/moi/IREM/IREM10_06_09/}{/home/moi/Lycee/TS/}{/home/moi/Lycee/Informatique/XCAS/2008_9/}}

\entete{\leftmark}{\rightmark}{\href{http://tehessin.tuxfamily.org/fr.html}{Licence
    Creative Commons}\byncsa}%g,d,b

% \sectionfont{\LARGE\color{0.2white}}
% \renewcommand\thesection{\Roman{section} }
% \subsubsectionfont{\large\color{0.6white}}
% \subsectionfont{\Large\color{0.4white}}
% \renewcommand\thesubsubsection{\roman{subsubsection}. }



\setlength{\headheight}{15.2pt}
\usepackage{cclicence}
\setcounter{secnumdepth}{3}
\setcounter{tocdepth}{1}

\title{\fontfamily{ugq}\selectfont FAIRE DES MATHÉMATIQUES AU LYCÉE EN PROGRAMMANT
\\ {\itshape Quelques exercices de programmation avec XCAS et CAML}
 \\
\href{http://tehessin.tuxfamily.org/fr.html}{ \fontfamily{ugq}\selectfont
  Licence Creative Commons}
\CcGroupByNcSa{1.25}{1.25ex}
%\CcNote{\CcLongnameByNcSa}		
}

\author{\fontfamily{ugq}\selectfont    Guillaume    \textsc{Connan}    -
  \textsc{IREM} de Nantes\\\fontfamily{ugq}\selectfont Courriel~:~\href{mailto:gconnan@free.fr}{\fontfamily{ugq}\selectfont gconnan - at - free.fr}}

\date{\fontfamily{ugq}\selectfont Stage PAF du 25 mars 2010}

%\thanks{\CcNote{\CcLongnameByNcSa}}

% \thanks{Merci  à  René  \textsc{Thoraval}  d'avoir  eu  la  patience  de
%   m'initier   au    merveilleux   langage   CAML,    si   puissant,   si
%   intelligent....si mathématique}

% \newcommand\xc{\lstset{numbers=none,language=XCAS,xleftmargin=10pt,%
% keywordstyle=\color{black}\bfseries,
% ,basicstyle=\ttfamily\color{0.4white},commentstyle=\normalfont\small\itshape,breaklines=true,backgroundcolor=\color{ciel},frame=trBL,framerule=1pt,framesep=4pt,rulesep=1pt,extendedchars=true}
% }



% \newcommand\xc{\lstset{numbers=none,language=XCAS,xleftmargin=10pt,%
% keywordstyle=\bfseries\color{black},basicstyle=\ttfamily\color{0.1white},commentstyle=\normalfont\scriptstyle\slshape,breaklines=true,frame=trBL,framerule=1pt,framesep=4pt,rulesep=1pt,backgroundcolor=\color{ciel}}
% }

\lstset{numberbychapter=false}


\newcommand\xc{\lstset{numbers=none,language=XCAS,xleftmargin=10pt,%
keywordstyle =\ttfamily\color{bleu}\bfseries,basicstyle=\ttfamily\color{0.1white},commentstyle=\normalfont\scriptsize\slshape,breaklines=true,backgroundcolor=\color{green!20},frame=trBL,framerule=1pt,framesep=4pt,rulesep=1pt,showstringspaces=false,stringstyle=\slshape,captionpos=b}
}

\newcommand\caml{\lstset{numbers=none,language=Caml,xleftmargin=10pt,%
keywordstyle =\ttfamily\color{MidnightBlue}\bfseries,basicstyle=\ttfamily\color{0.1white},commentstyle=\normalfont\scriptsize\slshape,breaklines=true,backgroundcolor=\color{blue!10},frame=trBL,framerule=1pt,framesep=4pt,rulesep=1pt,showstringspaces=false,stringstyle=\slshape,captionpos=b}
}


\renewcommand\lstlistingname{Programme}
\renewcommand\lstlistlistingname{Liste des programmes}
% \newcommand\caml{\lstset{language=Caml,backgroundcolor=\color{creme},numbers=none,xleftmargin=10pt,%
% keywordstyle=\bfseries\color{black},basicstyle=\ttfamily\color{0.1white},commentstyle=normalfont\scriptstyle\color\slshape\color{0.1white},breaklines=true,frame=trBL,framerule=1pt,framesep=4pt,rulesep=1pt}
% }

%\lstMakeShortInline+

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

\newcommand{\reponse}[1]{
\begin{center}
\textcolor{blue}{\texttt{#1}}
\end{center}
}


\newcommand{\MarqueCommandeGiac}[1]{%
    \color{gray}$>\ $}
\newcommand{\MarqueLaTeXGiac}{%
    \color{blue}}
\newcommand{\InscriptionFigureGiac}[1]{%
    \begin{center}
	\includegraphics[width=7.5cm]{#1}
    \end{center}}



\usepackage{wallpaper}

%\lstMakeShortInline+

\begin{document}


%\input /home/moi/texmf/macros/plain/contrib/font-change/tex/macros/font_bera_concrete





\setlength{\parindent}{0pt}
%\thispagestyle{empty}

\incmargin{1em}
\dontprintsemicolon
%\SetCommentSty{\sffamily}}%\sffamily\color{0.4white}}
\ThisCenterWallPaper{1.33}{fractalenewton2}
% \begin{center}
%   \includegraphics[width=1.3\linewidth]{fractalenewton}
% \end{center}




\maketitle
\pagestyle{plain}

%\tableofcontents

\vfill

\eject

\xc


\pagestyle{fancy}

\chapter{Quelques exemples pour observer}

\section{Partie entière}



\subsection{Algorithme récursif}

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 montant 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$.


\subsubsection{Avec XCAS}\label{per}
\xc
\begin{lstlisting}[caption={partie entier en récursif}]
perx(r):={
  si(r>=0) et (r<1) 
      alors 0
      sinon si r>0
            alors 1+perx(r-1)
            sinon -1+perx(r+1)
            fsi       
  fsi
}:;
\end{lstlisting}


\subsubsection{Avec CAML}

\caml
\begin{lstlisting}[caption={partie entière en récursif (CAML)}]
# let perc (r)
        =
        if r >= 0. && r < 1.
         then 0.
         else if r > 0.
               then   1. +. perc (r -. 1.) 
	       else -.1. +. perc (r +. 1.)

\end{lstlisting}


\subsection{Algorithme impératif}





On peut  commencer par se restreindre  aux 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$.



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



Ce qui donne en XCAS

\xc

\begin{lstlisting}[caption={partie entière en impératif (cas $x$ positif)}]
pe(x):={
local k;
k:=0;
   tantque k<=x faire
      k:=k+1;
   ftantque;
retourne(k-1);
}:;
\end{lstlisting}





\section{Les réels et le processeur}


Ayez toujours en  tête qu'un ordinateur ne peut  pas travailler avec des
réels~! Par  essence, il a un nombre  fini de bits sur  lesquels il peut
coder des nombres...

Les nombres \textit{flottants} qu'il  manipule sont donc des classes qui
représentent chacune une infinité de  réels (mais tout en constituant un
intervalle cohérent).

Si on n'y fait pas attention, cela peut créer des surprises...

Entrons trois nombres sur XCAS~:
\xc
\begin{lstlisting}
x:=10;
y:=-5;
z:=5.00000001;
\end{lstlisting}


Alors

\begin{lstlisting}
(x*y)+(x*z)
\end{lstlisting}

renvoie~:

\reponse{1.000000012e-07}

Mais 

\begin{lstlisting}
x*(y+z)
\end{lstlisting}


renvoie~:

\reponse{9.999999939e-08}

Le problème est le même avec CAML~:

\caml

\begin{lstlisting}
# let x,y,z=10.,-5.,5.00000001;;
val x : float = 10.
val y : float = -5.
val z : float = 5.00000001

# (x*.y)+.(x*.z);;
- : float = 1.00000001168609742e-07

# x*.(y+.z);;
- : float = 9.99999993922529e-08
\end{lstlisting}


Ainsi l'addition  n'est pas toujours distributive  sur la multiplication
quand on travaille sur les flottants~!


Ces petites erreurs qui s'accumulent peuvent en créer de grandes~! 

Créons  une fonction  qui renvoie  l'approximation de  la  dérivée d'une
fonction en un nombre donné avec un \og \verb+dx+\fg{} valant $10^{-10}$~:

\begin{lstlisting}[caption={dérivation numérique}]
# let dernum(f)=function
          x->(f(x+.0.0000000001)-.f(x))/.0.0000000001;;
\end{lstlisting}

Dérivons le sinus  cinq fois de suite et évaluons  la fonction obtenue en
0~:

\begin{lstlisting}
# dernum(dernum(dernum(dernum(dernum(sin)))))(0.);;
- : float = -1.33226762955018773e+25
\end{lstlisting}

Oups !  On obtient  $\cos(0)\approx -10^{25}$...Ce n'est plus de l'ordre
de l'erreur négligeable~!





\section{Méthode d'\textsc{Euler}}

Supposons qu'on connaisse  $f'(x)$ en fonction de $x$  et de $f(x)$ sous
la forme $f'(x)=u\bigl(f(x),x\bigr)$.

On utilise le fait que $f'(x)\approx \frac{f(x+h)-f(x)}{h}$. Alors
$f(x+h)\approx h\cdot u\bigl(f(x),x\bigr)+f(x) $

La traduction algorithmique est alors directe.


\subsection{Version récursive}

Pour la liste des coordonnées de points~:
\xc

\begin{lstlisting}[caption={méthode d'Euler générale en récursif}]
Euler(u,x,xmax,y,h,liste):={
 if(x>=xmax)
   then{liste}
   else{ Euler(u,x+h,xmax,y+u(y,x)*h,h,[op(liste),[x,y]])}
}:;
\end{lstlisting}


Puis pour le tracé~:

\begin{lstlisting}
trace_euler(u,xo,xmax,yo,h):={
polygonplot([Euler(u,xo,xmax,yo,h,[])])
}:;
\end{lstlisting}


Alors, pour  résoudre graphiquement $y'=-y$ avec  $y(0)=1$, sur $[-2;2]$
avec un pas de $0,01$ on entre~:

\begin{lstlisting}
trace_euler((y,x)->-y,-2,2,1,0.01)
\end{lstlisting}


et on obtient~:


\begin{figure}
\begin{center}
  \includegraphics[scale=0.8]{euler.eps}
\end{center}
\end{figure}

\subsection{Version impérative}


On effectue une division régulière en découpant notre intervalle d'étude
$[a;b]$ en $N$ points~:

\begin{lstlisting}[caption={méthode d'Euler générale en impératif}]
EulerImp(u,N,a,b,yo):={
S:=NULL; 
X:=a;  
Y:=yo;  
h:=(b-a)/N  
 pour k de 0 jusque N pas 1 faire
  X:=a+k*h; 
  Y:=Y+u(Y,X)*h; 
  S:=S,[X,Y]; 
 fpour 
polygonplot([S]); 
}:;
\end{lstlisting}



Ensuite, pour avoir la solution  de $y'=-y+x$ sur $[-2;2]$ avec $y(0)=1$
on entre~:

\begin{lstlisting}
EulerExpo((y,x)->-y+x,100,-2,2,1)
\end{lstlisting}


et on obtient~:



\begin{figure}
\begin{center}
  \includegraphics[scale=0.8]{euler2}
\end{center}
\end{figure}

\section{Méthode des rectangles}



On  veut  calculer une  intégrale  d'une  fonction  par la  méthode  des
rectangles. 

\subsection{Version récursive}

La définition récursive est assez naturelle~:


\caml

\begin{lstlisting}[caption={méthode des rectangles en récursif}]
# 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 $\ds\int_0^1x\D{x}\approx 0.5$


Mais  la  récursion  n'est  pas  terminale.  Introduisons  une  fonction
intermédiaire~:



\begin{lstlisting}[caption={méthode des rectangle en récursif terminal étape 1}]
# let rec integ_temp(f,a,b,dx,res)=
     if a>b then res
     else integ_temp(f,a+.dx,b,dx,res+.f(a)*.dx);;
\end{lstlisting}

Puis~:

\begin{lstlisting}[caption={méthode des rectangles en récursif terminal étape 2}]
# let integrale(f,a,b,dx)=integ_temp(f,a,b,dx,0.);;
\end{lstlisting}


Alors on obtient~:


\begin{lstlisting}
# integrale(g,0.,1.,0.0000001);;
- : float = 0.500000049944005598
\end{lstlisting}


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


\subsection{Version impérative}


\xc

\begin{lstlisting}[caption={méthode des rectangles en impératif}]
integ_rectangle(f,a,b,dx):={
local aa,I;
aa:=a;
I:=0;
 while(aa<b){
 I:=I+f(aa)*dx;
 aa:=aa+dx;
 }
return(I)
}:;
\end{lstlisting}









\section{Les vecteurs, le renard et le lapin}


Un lapin court vers le nord en  ligne droite et un renard le poursuit en
bondissant toujours dans sa direction.

On suppose que le lapin et le renard fond des bonds de longueurs respectives
$bl$ et $br$, que le lapin part du point de coordonnées $(0;0)$ et le renard du
point de coordonnées $(x_0,y_0)$.

On  repérera ensuite  les  animaux par  le  point $R(x;y)$  et le  point
$L(0;z)$.

Calculons  la distance  Renard-Lapin~:~comme $\ve{RL}(-x;z-y)$  alors la
distance $d$ qui les sépare vaut \[d=\sqrt{x^2+(y-z)^2}\]


Il est alors pratique de travailler dans un espace affine. 

La position
suivante du renard, après un bond est $R+\frac{br}{d}\ve{RL}$

Celle du lapin est $L+bl \ve{\jmath}$.  Tout est en ordre pour pouvoir
programmer...


\begin{lstlisting}[caption={poursuite renard/lapin (1)}]
poursuite1(xo,yo,br,bl):={
local R,L,d,pR,Dir,nbsaut;
R:=[xo,yo];
L:=[0,0];
pR:=NULL;
Dir:=NULL;
nbsaut:=0;
d:=evalf(sqrt(xo^2+yo^2));
 while((nbsaut<1000) and (d>0)){
 pR:=R,pR;
 Dir:=Dir,segment(point(R),point(L));
 d:=evalf(sqrt((L[0]-R[0])^2+(L[1]-R[1])^2));
  if(d>br)then{
   R:=R+(br/d)*(L-R);
   L:=L+[0,bl];
  }else{R:=L}
 nbsaut:=nbsaut+1;
 }
print(if(nbsaut<1000)
      then{"Lapin attrapé en "+nbsaut+" bonds"}
      else{"Le lapin court toujours après 1000 bonds"})
return(display(polygonscatterplot([pR]),blue+line_width_3+point_width_3),Dir)
}:;
\end{lstlisting}


Par exemple, avec  des bonds du renard deux fois plus longs que ceux du
lapin~:

\begin{lstlisting}
poursuite1(6,4,1,0.5,7)
\end{lstlisting}


\begin{figure}
\begin{center}
  \includegraphics[width=0.8\linewidth]{lapin1}
\end{center}
\end{figure}












\section{Tirage de boules}

\xc


On dispose de trois urnes, la  première contenant 7 boules blanches et 4
noires, la deuxième 5 blanches et 2 noires, la troisième 6 blanches et 3
noires.

On  tire une  boule dans  chaque urne  et on  note le  nombre  de boules
blanches obtenues.

On adapte l'algorithme précédent~:

\begin{lstlisting}[caption={exemple de tirage de boules}]
boules(n):={
T:=NULL;
for(k:=1;k<=n;k:=k+1){
X:=0;
if(rand(11)<7){X:=X+1}
if(rand(7)<5){X:=X+1}
if(rand(9)<6){X:=X+1}
T:=T,X;
}
return(evalf([count_eq(0,[T])/n,count_eq(1,[T])/n,count_eq(2,[T])/n,count_eq(3,[T])/n])
)}:;
\end{lstlisting}

On obtient \texttt{[0.0358,0.2253818182,0.4453272727,0.2934909091]}


Or,      par     exemple,   $\frac{7}{11}\times     \frac{5}{7}\times
\frac{6}{9}\approx 0,303$ et $\frac{4}{11}\times \frac{2}{7}\times
\frac{3}{9}\approx 0,034$.




\section{Polygones de \textsc{Sierpinski}}

Waclaw \textsc{Sierpinski}  (1882 - 1969) fut  un mathématicien polonais
qui travailla sur des domaines mathématiques très ardus~:~fondements des
mathématiques,  construction  axiomatique  des ensembles,  hypothèse  du
continu, topologie, théorie des nombres...

Il a  également travaillé sur  les premiers objets  fractals qu'étudiera
plus tard  Benoît \textsc{Mandelbrot}, mathématicien  français d'origine
polonaise connu pour ses travaux dans ce domaine.

\subsection{Jouons aux dés}

Prenez un  dé à  6 faces,  un triangle ABC  et un  point G  quelconque à
l'intérieur du triangle.

Vous lancez le dé~:

\begin{itemize}
\item si la face supérieure est 1  ou 2, vous faites une petite croix au
  niveau du milieu de G et de A~;
\item si la face supérieure est 3  ou 4, vous faites une petite croix au
  niveau du milieu de G et de B~;
\item si la face supérieure est 5  ou 6, vous faites une petite croix au
  niveau du milieu de G et de C~;
\end{itemize}


Ah, zut, on n'a pas de dé dans la salle d'info...mais on a XCAS.



\begin{itemize}
\item \verb+hasard(0,1)+ renvoie un  nombre aléatoirement choisi entre 0
  et 1~;
\item  \verb+hasard(n)+ renvoie  un entier  aléatoirement  choisi entre
  $0$ inclus et $n$ exclus.
\end{itemize}



\xc

\begin{lstlisting}[caption={}]
dede(n):={
local P,r,t,d,G,L,k;
 P:=[[0,0],[1,0],[0.5,0.5*sqrt(3)]];
 t:=hasard(0,1);
 G:=t^2*P[0]+2*t*(1-t)*P[1]+(1-t)^2*P[2];
 L:=G;
  pour k de 1 jusque n faire
      G:=0.5*(G+P[hasard(3)]);
      L:=L,G;
  fpour;
 nuage_points([L]);
}:;  
\end{lstlisting}


ce qui donne en lançant \verb+dede(10000)+~:



\begin{figure}
\begin{center}
  \includegraphics{triserpi}
\end{center}
\end{figure}







\chapter{À vous de jouer}

\exot{Partie entière}

Écrivez un programme dans le cas général ($x$ de signe quelconque).



\exot{Taux de remise variable}

On entre un montant HT $ht$. On effectue une remise sur $ht$ selon la
régle suivante~:
\begin{itemize}
\item si $ht<2500$\texteuro{} alors il n'y a pas de remise~;
\item si $2500\leqslant ht<4000$\texteuro{} alors la remise est de 5\%~;
\item dans les autres cas la remise est de 8\%.
\end{itemize}

La TVA est de 19,6\%. On demande le prix TTC en fonction du prix HT.


On peut construire  une seule fonction ou une  seule procédure ou couper
en  deux~:~le  calcul  du  taux  puis  le calcul  du  prix.  Essayez  de
construire une procédure avec affectation et une fonction sans affectation.


\exot{Opérations sur les fractions}



Quelle différence existe-t-il entre $\frac{7}{3}$ et $\frac{21}{9}$~?

Quel rôle peut jouer le PGCD dans cette histoire~?

On va créer un programme simplifiant les fractions.

Au  lieu  d'écrire  un  nombre  rationnel  sous  la  forme  $\dfrac{{\rm
    numérateur}}{{\rm  dénominateur}}$, on va  l'entrer dans  la machine
sous la forme \texttt{[numérateur,dénominateur]}.

Ainsi $\frac{21}{9}$ s'écrira \texttt{[21,9]}.


On peut alors créer un programme qui simplifiera une fraction donnée.


\caml



On utilisera une fonction donnant le pgcd de deux naturels~:



\begin{lstlisting}[caption={calcul du PGCD en récursif}]
let rec pgcd (a,b) =
        if b=0 
        then a
        else pgcd(b,a mod b);;
\end{lstlisting}










Avec CAML, pour prévenir toute division par zéro on va créer un opérateur traitant les exceptions qu'on nommera \verb+Division_par_zero+ et qui nous servira de garde-fou :

\begin{lstlisting}
# exception Division_par_zero;;
\end{lstlisting}



On invoquera cette exception avec la commande \verb+raise+ : étant donné
votre 
niveau d'anglais, cette commande est naturelle !...



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

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


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


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



Par exemple~:


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


Bon~:~occupez-vous de la multiplication, du calcul de l'inverse et de la
division.



Quand tout sera prêt, comment entrer \[1+\frac{2+\frac{3}{4}}{1-\frac{5}{6}}\]

et 

\[
3+\frac{1}{2+\frac{1}{1+\frac{1}{2+\frac{1}{6}}}}
\]



\exot{Dichotomie}


Avec   XCAS,  l'approximation   d'un  nombre   formel  est   donnée  par
\verb+evalf(nombre)+.

Par exemple~:
\xc
\begin{lstlisting}[caption={}]
evalf(pi)
\end{lstlisting}


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.


Donnez un programme récursif en 4 lignes qui prend en entrée la fonction
$f$,  $a$, $b$  et la  précision et  qui renvoie  l'approximation  de la
solution de $f(x)=0$ sur $[a;b]$.


En impératif, l'algorithme peutr être le suivant~:


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



\exot{}

En vous inspirant  du cas général traitant la  méthode d'Euler, imaginez
une séance de TP qui construirait la courbe de la fonction dérivable sur
$\bbr$ vérifiant $f'=f$ et $f(0)=1$.

Imaginez-en une autre pour le logarithme népérien.



\exot{Méthode des trapèzes}


Déterminez des programmes qui calculent une intégrale sur un segment par
la méthode des trapèzes.

\exot{Systèmes 2x2}

Imaginez un TP  en 2\up{nde} qui permettrait de  construire un programme
résolvant de  manière exacte  un système de  deux équations  linéaires à
deux inconnues.





\exot{Algorithme de \textsc{Héron}}

\textsc{Héron}  d'Alexandrie n'avait pas  attendu \textsc{Newton}  et le
calcul différentiel  pour trouver  une méthode permettant  de déterminer
une approximation  de la racine  carrée d'un nombre positif.


Si  $x_n$  est une  approximation  strictement  positive  par défaut  de
$\sqrt{a}$, alors $a/x_n$ est  une approximation par excès de $\sqrt{a}$
(pourquoi~?) et vice-versa.

La    moyenne   arithmétique    de   ces    deux    approximations   est
$\frac{1}{2}\left(x_n+\frac{a}{x_n}\right)$  et constitue  une meilleure
approximation que les deux précédentes.

On  peut  montrer c'est  une  approximation  par  excès (en  développant
$\left(x_n-\sqrt{a}\right)^2$ par exemple).

On obtient naturellement un algorithme~:


\begin{algorithm}[H]
\caption{approximation de $\sqrt{a}$}
\Entree{le réel positif $a$, une première approximation par défaut
  strictement positive xo et une précision eps}
\Ini{
X\aff 0.5(xo+$a$/xo)}
\Deb{
\Tq{|xo-a/xo|<eps}
{X\aff 0.5(X+$a$/X)}

\Retour{X}
 } 
\end{algorithm}


On notera que cette méthode est un cas particulier de la méthode de
\textsc{Newton-Raphson} appliquée à une équation particulière~:~$x^2-a=0$.


Traduire cet algorithme en impératif avec XCAS et en récursif avec CAML.


\exot{Lapin malin}


Reprenez le problème du renard et du lapin qui fait maintenant des bonds
en zigue-zagant à angle droit.



\exot{Tirages de boules avec remise}


Simulons le tirage successif de  quatre boules avec remise dans une urne
contenant 7  boules blanches et 3  boules noires. Comptons  le nombre de
tirages contenant 

\begin{itemize}
\item exactement deux boules blanches~;
\item au moins une boule blanche.
\end{itemize}


\exot{Fonction mystérieuse}

Observez ces fonctions et décrivez leur action sachant que \verb+&&+ signifie \og et\fg{} et que \verb+||+ signifie \og ou\fg{}~:

\caml
\begin{lstlisting}[caption={fonction mystérieuse (1)}]
# let rec truc(n)   = n<>1 && ( n=0 || machin(n-1) )
    and   machin(n) = n<>0 && ( n=1 || truc(n-1) ) ;;
\end{lstlisting}

Pour vous  mettre sur  la voie, voici  trois fonctions  plus compliquées
mais aux noms plus explicites... 



\begin{lstlisting}[caption={fonction mystérieuse (2)}]
# let rec multiple_3(n) = n<>1 && n<>2 && ( n=0 || reste_3_2(n-1) )
  and     reste_3_2(n)  = n<>0 && n<>1 && ( n=2 || reste_3_1(n-1) ) 
  and     reste_3_1(n)  = n<>0 && n<>2 && ( n=1 || multiple_3(n-1) );; 
\end{lstlisting}



\exot{Algorithme glouton et rendu de monnaie}

Une première idée pour optimiser une certaine situation est d'effecteur,
étape par  étape un  choix optimum local  dans l'espoir que  le résultat
global   obtenu   soit    optimum~:~l'algorithme   obtenu   est   appelé
\emph{algorithme glouton}.

Une illustration  classique de ce problème  est le rendu  de monnaie qui
est lui-même un cas particulier du problème du sac à dos. On
dispose d'au moins deux types de pièces de valeurs premières entre elles
(pourquoi~?...) et  on veut rendre la  monnaie en utilisant  le moins de
pièces possibles.

Une première  idée est de  répéter le choix  de la pièce de  plus grande
valeur  qui  ne dépasse  pas  la  somme  restante~:~c'est un  algorithme
glouton.


\begin{algorithm}[H]
\caption{algorithme glouton de rendu de monnaie}
\Entree{somme n à rendre et liste L des pièces disponibles}\;
\Ini{\;
somme partielle\aff 0\;
liste des pièces\aff vide\;
}\;
\Deb{
\Tq{somme partielle < n}
   {k\aff taille de la liste\;
      \Tq{k>0 et pièce n° k est supérieure à la somme restante}
         {k\aff k-1 : on regarde la pièce de valeur inférieure}
}
\Retour{liste des pièces}
 } 
\end{algorithm}

Qu'est-ce que ça donne en XCAS~?


Ainsi,  pour   savoir  comment  former  39  centimes   avec  nos  pièces
européennes, on entrera~:
\xc

\begin{lstlisting}
piece_glouton(39,[1,2,5,10,20,50,100,200])
\end{lstlisting}


Commentez le résultat de~:


\begin{lstlisting}
piece_glouton(8,[1,4,5])
\end{lstlisting}

En fait,  l'algorithme glouton est optimum  si la suite  des valeurs des
pièces est \emph{super-croissante} (on peut s'amuser à le démontrer...), c'est-à-dire si chaque terme est
supérieur à la somme des précédents. 

Par exemple,  $20>10+5+2+1$ mais $5\leqslant  4+1$ et la deuxième  liste n'est
pas super-croissante. 


\exot{Suite de \textsc{Viète}}

François \textsc{Viète} proposa au XVI\up{e} siècle une approximation de
$\pi$ qui revient en langage moderne à étudier la suite~:

\[u_0=\frac{1}{\sqrt{2}}\qquad
u_n=\sqrt{\frac{1}{2}+\frac{1}{2}u_{n-1}}\qquad \pi=\frac{2}{\prod\limits_{n=0}^{+\infty}u_n}\]

Donnez  des  approximations  de  $\pi$  à l'aide  de  cette  méthode  en
programmant récursivement ou impérativement.









\exot{Dentelle de Varsovie}

Nous voudrions obtenir le joli napperon en dentelle suivant~:



\begin{figure}
\begin{center}
  \includegraphics[scale=1.1]{pentaserp}
\end{center}
\end{figure}




Déterminez le rapport des similitudes qui transforment le grand pentagone en
un des pentagones plus petit.

En  vous  inspirant   de  ce  qui  a  été  fait   pour  le  triangle  de
\textsc{Sierpinski}, faites tracer à XCAS ce joli napperon.




\exot{Végétation récursive}

Analysez cet algorithme~:

\begin{lstlisting}[caption={L-System}]
arbre(A,B,Rap,Ang,n):={
    si n>0 alors             
      segment(point(A),point(B)),seq(arbre(B,B+Rap[q]*exp(Ang[q]*i)*(B-A),Rap,Ang,n-1),q=0..size(Rap)-1)
      sinon  segment(point(A),point(B))
    fsi
}:;
\end{lstlisting}



sachant que 



\begin{lstlisting}[caption={}]
arbre(0,i,[0.7,0.8],[pi/5.,-pi/5.],7)
\end{lstlisting}




donne


\begin{figure}
\begin{center}
  \includegraphics{arbre1}
\end{center}
\end{figure}



Comment obtenir cette fougère et ce brocolis~?

\begin{minipage}[t]{0.45\textwidth}\vspace{0cm}\begin{flushleft}\includegraphics[width=0.9\linewidth]{arbre2}\end{flushleft}\end{minipage}\hspace{0.5cm}\begin{minipage}[t]{0.45\textwidth}\vspace{-0.7cm}
\hspace{5.5cm}
\begin{flushright}\includegraphics[width=0.9\linewidth]{arbre3}\end{flushright}\end{minipage}


\exot{Étoiles et espaces}



Que fait cette procédure~:


\begin{lstlisting}[caption={Tableau en triangle}]
pascal(n):={
local T,j,i;
 T:=[[0$n]$n];
 pour j de 0 jusque n-1 faire
   pour i de 0 jusque n-1 faire 
     si j>i alors T[i,j]:="" ;
     fsi;
   fpour;
 fpour;
retourne(T);
}:;
\end{lstlisting}




Transformez-la un peu pour obtenir ceci avec $n=10$ par exemple~:


\begin{Verbatim}
        1                                                                                            
        1    1                                                                                       
        1    2    1                                                      
        1    3    3     1                                      
        1    4    6     4      1                               
        1    5    10    10     5      1                        
        1    6    15    20    15      6     1                  
        1    7    21    35    35     21     7     1            
        1    8    28    56    70     56     28    8     1      
        1    9    36    84    126    126    84    36    9    1 

\end{Verbatim}
     

Complétez cette dernière procédure  afin de remplacer chaque nombre pair
par  une  espace \verb+`  `+  et chaque  nombre  impair  par une  étoile
\verb+`*`+. Lancez-la pour $n=48$~: incroyable, non~?




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