\documentclass[xcolor={hyperref,dvips,ps2pdf,dvipsnames},hyperef={naturalnames,pdfpagelabels},dvips]{beamer} 
\usepackage{etex}
\usepackage[baw]{fvrb-ex}
\fvset{xrightmargin=0cm,gobble=2}
\graphicspath{{/home/moi/Figures/FigSeconde/}}
%\usepackage{BeamerPolymaths}
\usepackage{amsmath,amssymb,amsbsy,amsfonts,amstext,amscd,amsopn,amsxtra}
\usepackage{textcomp,pst-all}
\usepackage[T1]{fontenc} 
\usepackage[utf8]{inputenc}
\usepackage[frenchb]{babel} 
\DeclareRobustCommand{\ve}[1]{%
\overrightarrow{\rule{0em}{1.8ex} #1 \rule{0.15em}{0ex}}}

\newcommand{\ds}{\displaystyle}
\newcommand{\Mathbold}[1]{\mbox{\boldmath$#1$\unboldmath}}
\usepackage{listings}
\newcommand\bbc{\mathbb{C}}
\newcommand\R{\mathbb{R}}
\newcommand{\CR}{\mathcal{C}}
\usepackage{listings,luximono,xlop,hhline}
\usepackage{multicol}   % Gestion des colonnes dans le texte
\setlength{\multicolsep}{3pt} 

\newenvironment{DeuxCols}[1][2]{%                             pour ï¿½rire en deux colonnes , 2 par dï¿½aut
	\setlength{\columnsep}{30pt}
	\setlength{\columnseprule}{.5pt}
	\begin{multicols}{#1}}%
	{\end{multicols}}
\setcounter{tocdepth}{3}
\usepackage[french]{varioref} 

\usepackage[french,vlined,boxed,slide,longend]{algorithm2e}
\setlength{\incmargin}{1cm}
\definecolor{creme}{rgb}{0.408,0.910,0.540}
\definecolor{ciel}{rgb}{0.200,0.810,0.999}
\definecolor{bleu_ciel}{rgb}{0.200,0.810,0.999}
\definecolor{vert_e}{rgb}{0,0.790002,0.340007}

\newcommand{\ie}{\leqslant}  % infï¿½ieur ou ï¿½al
\newcommand{\se}{\geqslant}  % supï¿½ieur ou ï¿½al

\renewcommand\FancyVerbFormatLine[1]{\color[HTML]{1E90FF}{#1}}

% \lstset{numbers=none,language=xcas,xleftmargin=10pt,%
% keywordstyle =\color[HTML]{8B7500}\usefont{OT1}{cmtt}{b}{n},basicstyle=\ttfamily\footnotesize\color[HTML]{8B7500},commentstyle=\normalfont\scriptsize\slshape,breaklines=true}


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



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


\newcommand{\bsys}{\begin{cases}}% systï¿½e sans alignement 
\newcommand{\esys}{\end{cases}}

\newenvironment{arrayl}[1][rcl]%
	{\setlength{\arraycolsep}{1.5pt}
	 $\begin{array}[t]{#1}}%
	{\end{array}$}%


\mode<presentation>
{
  \usetheme[secheader]{Madrid}
%  \usetheme{Darmstadt}
  % or ...Warsaw

  \setbeamercovered{highly dynamic}
  % or whatever (possibly just delete it)
}


\title[] % (optional, use only with long paper titles)
{Algorithmes de-ci de-là}

\subtitle{Journées académiques IREM/APMEP juin 2009}

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

\institute[IREM des Pays de la Loire]{Groupe logiciels libres}% (optional, but mostly needed)


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

\subject{Florilèges d'algorithmes utiles en mathématiques pour la plupart de niveau
  3\up{e}/2\up{e}. Illustration à l'aide de CAML et XCAS. Algorithmes récursifs/impératifs}

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

  \end{frame}
}




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

  \end{frame}
}





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

  \end{frame}
}


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

\beamerdefaultoverlayspecification{<+->}



\newcommand{\MarqueCommandeGiac}[1]{%
    \color[HTML]{8B7500}$\rightarrow$}
\newcommand{\MarqueLaTeXGiac}{%
    \color[HTML]{1E90FF}}
\newcommand{\InscriptionFigureGiac}[1]{%
    \begin{center}
	\includegraphics[width=0.7\linewidth]{#1}
    \end{center}}




\newcommand{\MarqueCommandeGiacN}[1]{%
    \color[HTML]{8B7500}$\rightarrow$}
\newcommand{\MarqueLaTeXGiacN}{%
    \color[HTML]{1E90FF}}
\newcommand{\InscriptionFigureGiacN}[1]{%
    \begin{center}
	\includegraphics[width=0.7\linewidth]{#1}
    \end{center}}









\begin{document}




\begin{frame}
  \titlepage
\end{frame}

\begin{frame}
 \frametitle{Sommaire}
{\scriptsize
\begin{DeuxCols}[2] 
 \tableofcontents
\end{DeuxCols}
}

 
\end{frame}




  
\section{Algorithme breton}



\begin{frame}
  
Ce  n'est  pas  très  mathématique  mais c'est  un  algorithme  et  pour
affronter  tous  ceux  qui  nous  attendent,  il  va  nous  falloir  des
forces....
\end{frame}

\xc

\begin{frame}[fragile]
\tiny
\begin{algorithm}[H]
\caption{algorithme breton pur beurre}
\Entree{masse m totale}
\Ini{\;
beurre\aff m/4\;
sucre\aff m/4\;
farine\aff m/4\;
\oe uf \aff m/4\;
}
\Deb{
 Couper le beurre en petits moreaux et le mettre à fondre doucement au bain-marie de préférence.
Dès qu'il est fondu arrêter. Laisser refroidir mais attention : le beurre doit être encore liquide ! Il ne doit pas redevenir solide\;

 Mettre le four à préchauffer à 160\textdegree (th 5)\;

 Mettre les oeufs entiers avec le sucre dans un saladier. Battre longuement le mélange pour qu'il blanchisse et devienne bien mousseux\;

 Y ajouter le beurre fondu ET FROID\;

 Rajouter progressivement à l'appareil la farine en l'incoporant bien. Cela doit donner une pâte élastique et un peu épaisse\;

 Verser la préparation dans un moule à manqué ou à cake bien beurré\;

 Laisser  cuire  environ  une   heure.  Il  faut  surveiller  le  gâteau
 régulièrement.\; 

\Si{ il  semble brunir  trop vite}{ il  faut baisser  un peu le  four et
  mettre une feuille d'aluminium sur le dessus.}

 Il  faut que  le  dessus du  gâteau  soit blond  foncé,  mais pas  trop
 coloré.\;

\Si{lorsqu'une pique plantée en son milieu ressort sèche}{le gâteau est cuit }

 } 
\end{algorithm}

\end{frame}

\normalsize



\section{Un algorithme à travers la scolarité}


\subsection{Sans l'ordinateur}

\begin{frame}
Les enfants apprennent à l'école primaire à poser \og verticalement\fg{} une multiplication
d'entier~:~ils utilisent un des  nombreux algorithmes utilisés à travers
les siècles et les continents pour effectuer ce type de calcul.


\pause

Celui-ci nous  intéresse car c'est une première  version d'un algorithme
plus général sur  le multiplication des polynômes et  même des fractions
rationnelles.




\end{frame}


\begin{frame}
  En  effet, derrière  l'algorithme vu  en  primaire se  cache celui  du
  produit des polynômes  etfaire le lien entre ces  deux applications de
  cet algorithme  nécessite une bonne compréhension de  la numération en
  base 10.



\end{frame}


\begin{frame}[fragile]


  \begin{center}
     \opmul[displayshiftintermediary=all]{4012}{102}
  \end{center}
 
\pause

\[\left(4\times   10^3+   10+2\right)\times(
10^2+2)=(8\times 10^3+2\times 10+4)+(4\times 10^5+10^3+2\times 10)\]


\pause


\[\left(4X^3+X+2\right)(
X^2+2)=(8X^3+2X+4)+(4X^5+X^3+2\times X)\]


\pause

et même


\[ 10\times 31,7=317 \parallel X(3X+1+\frac{7}{X}=3X^2+X+7)\]
\end{frame}




\subsection{Avec l'ordinateur}

\xc
\begin{frame}[fragile]
\begin{lstlisting}
4012*102
\end{lstlisting}

\pause

  \begin{center}
    \textcolor{blue}{409224}
  \end{center}

\pause

\begin{lstlisting}
f:=x->(4x^3+x+2)*(x^2+2):;
\end{lstlisting}

\pause

\begin{lstlisting}
f(10)
\end{lstlisting}

\pause

  \begin{center}
    \textcolor{blue}{409224}
  \end{center}



\end{frame}


\begin{frame}[fragile]
\xc

\begin{lstlisting}
produit(N,M,var):={
local PN,PM,Pro,k;
PN:=0;PM:=0;
 for(k:=0;k<size(N);k++){
    PN:=PN+N[k]*X^(size(N)-1-k)
  }
 for(k:=0;k<size(M);k++){
    PM:=PM+M[k]*X^(size(M)-1-k)
  }
Pro:=X->PM*PN;
return(simplify(expand(Pro(var))))
}:;
\end{lstlisting}

\end{frame}

\begin{frame}[fragile]
\xc

\begin{lstlisting}
 produit([4,0,1,2],[1,0,2],10)
\end{lstlisting}

\pause

 \begin{center}
    \textcolor{blue}{409224}
  \end{center}


\pause

\begin{lstlisting}
 produit([4,0,1,2],[1,0,2],x)
\end{lstlisting}

\pause


 \begin{center}
    \textcolor{blue}{$4x^5+9x^3+2x^2+2x+4$}
  \end{center}






\end{frame}

\section{Algorithmes récursifs / impératifs}

\begin{frame}
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)$.

\pause

Sa traduction  dans des langages sachant  plus ou moins  traiter de tels
algorithmes est directe. 
\end{frame}

\begin{frame}[fragile]

Par exemple, en XCAS cela devient~:

\pause

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

\pause

et en CAML~:

\pause

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

\end{frame}

\xc
\begin{frame}
Deux écoles de programmation~:

\begin{itemize}
\item programmation fonctionnelle~;
\item programmation impérative.
\end{itemize}
\end{frame}


\begin{frame}[fragile]
Cela donne en XCAS~:

\pause

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



\xc


%\section{Au rythme de la tortue}

\section{Dis monsieur, dessine-moi un icosagone..}

\begin{frame}
Certains  connaissent peut-être  le langage  Logo qui  avait  permis aux
petits  écoliers d'il  y  a une  vingtaine  d'années de  s'initier à  la
programmation.

Voyons par exemple un petit  algorithme permettant de tracer un polygone
fermé régulier quelconque.
\end{frame}




\begin{frame}[fragile]
\begin{algorithm}[H]
\caption{polygone}
\Entree{nombre N de côtés et longueur a d'un côté}
\Deb{
\Pour{k de 1 jusqu'à N }{
avance de a pas\;
tourne de 360/a degrés\;
}
 } 
\end{algorithm}
\end{frame}



\xc

\begin{frame}[fragile]
\frametitle{Avec XCAS}
XCAS comprend un module \emph{Tortue} très complet~:

\pause


\begin{lstlisting}
polylogo(N,a):={
local k;
pour k de 1 jusque N faire
avance(a);
tourne_droite(360/N);
fpour;
}:;
\end{lstlisting}

\end{frame}


\section{Outils mathématiques basiques}


\subsection{Valeur absolue}





\begin{frame}[fragile]

\frametitle{Algorithme}

On peut définir la valeur absolue  d'un réel $x$ de la manière suivante,
même si ce n'est pas l'usage en seconde~:

\pause

\begin{algorithm}[H]
  \caption{valeur absolue}
\Entree{$x$(un réel)}
\Deb{
\eSi{x positif}{\Retour{x}}{\Retour(-x)}
}
\end{algorithm}

\end{frame}



\begin{frame}[fragile]
\frametitle{Avec XCAS}
\begin{lstlisting}
va(x):={
  si x>0 alors 
    return(x) sinon  
    return(-x) 
  fsi;  
}
\end{lstlisting}

\end{frame}


\begin{frame}[fragile]

\pause

en anglais~:

\begin{lstlisting}
va(x):={
  if(x>0){return(x)}
  else{return(-x)}
}
\end{lstlisting}


\end{frame}


\begin{frame}[fragile]

en plus compact~:

\begin{lstlisting}
va(x):={
ifte(x>0,x,-x)
}
\end{lstlisting}


\end{frame}


\begin{frame}[fragile]
\frametitle{Avec CAML}

\caml

\begin{lstlisting}
# let va(x)=
    if x>0 then x else -x;;
\end{lstlisting}
\end{frame}


\xc


\subsection{Partie entière}




\begin{frame}
\frametitle{Algorithme récursif}
On part du fait que la  partie entière d'un nombre appartenant à $[0;1[$
est nulle.

\pause

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

\pause

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

\end{frame}




\begin{frame}[fragile]
\frametitle{Avec XCAS}
\begin{lstlisting}
partie_entiere_rec(r):={
  si(r>=0) et (r<1) 
      alors 0
      sinon si r>0
            alors 1+partie_entiere_rec(r-1)
            sinon -1+partie_entiere_rec(r+1)
            fsi       
      fsi
}:;
\end{lstlisting}
\pause

\begin{lstlisting}
partie_entiere_rec(r):={
  if((r>=0) and (r<1)){0}
  else{if(r>0){1+partie_entiere_rec(r-1)}
       else{-1+partie_entiere_rec(r+1)}       
      }
}:;
\end{lstlisting}
\end{frame}








\begin{frame}[fragile]
\frametitle{Avec CAML}

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

\end{lstlisting}
\end{frame}


\xc


%\subsubsection{Algorithme impératif}


%\subsubsection{Prérequis}

\begin{frame}
\frametitle{Algorithme impératif}
Test \og si...alors...sinon\fg{} et boucle \og tant que\fg{}


\pause

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

\end{frame}

\begin{frame}[fragile]
\frametitle{Algorithme impératif}
\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}

\end{frame}



\begin{frame}
\frametitle{Algorithme impératif}
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$~:

\end{frame}



\begin{frame}[fragile]
\frametitle{Algorithme impératif}
\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{frame}

%\subsubsection{Traduction XCAS}


\begin{frame}[fragile]
\frametitle{Algorithme impératif avec XCAS}
\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{frame}

\begin{frame}[fragile]

En anglais~:



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




\subsection{Arrondis}

\begin{frame}[fragile]

On veut arrondir un nombre réel à $10^{-2}$ près par défaut.  

\pause

On va
prendre la partie entière (avec l'algorithme créé précédemment) du nombre multiplié par $10^2$ puis le
rediviser par $10^{2}$~:

\pause

\begin{algorithm}[H]
              \caption{arrondi}
              \Entree{$x$(réel)}
              \Deb{
\Retour{(partie entière de $100x$) divisée par 100}
} 
               \end{algorithm}

\end{frame}

\begin{frame}[fragile]
  \frametitle{Traduction XCAS}
  
\begin{lstlisting}
arrondi(x):={
return(pe(100*x)/100.0)
}
\end{lstlisting}

\end{frame}


\caml

\begin{frame}[fragile]
  \frametitle{Traduction CAML}
  
\begin{lstlisting}
let arrondi_au_100_eme_par_defaut (r)
    =
    partie_entiere (100. *. r) /. 100.
\end{lstlisting}

\end{frame}





\subsection{Calculs de sommes}



\begin{frame}
  
On veut par exemple calculer la somme des entiers de 1 à n.


\end{frame}

\begin{frame}[fragile]
  \frametitle{Algorithme récursif}
  \xc

En XCAS~:

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

\pause


En CAML~:

\caml

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



\end{frame}

\begin{frame}[fragile]
  \frametitle{Algorithme impératif}
  

\begin{algorithm}[H]
\caption{somme des entiers de 1 à n}
\Entree{$n$(entier naturel)}
\Ini{S\aff 0\tcp*[r]{{\footnotesize \itshape la somme est nulle au départ}}}
\Deb{
\Pour{k de 1 à n}{S\aff S+k}
\Retour{S}
 } 
\end{algorithm}



\end{frame}


\begin{frame}[fragile]
 Traduction XCAS
\pause

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

\pause

en anglais~:

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

\end{frame}





\section{Algorithmes de calculs \og à la STG\fg{}}




\begin{frame}
  
Les sections STG sont initiées  à l'algorithmique en travaillant sur des
problèmes simples de gestion.

\end{frame}


\subsection{Taux de remise variable}


\begin{frame}
  
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\ie 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.

\end{frame}






\begin{frame}[fragile]
\frametitle{Algorithme}
\begin{algorithm}[H]
\caption{prix TTC selon remise}
\Entree{HT(réel positif)}
\Ini{ht\aff HT}
\Deb{
\Si{ht>=2500 et ht<4000}{ht\aff ht$\times$ 0,95}
\Si{ht>=4000}{ht\aff ht$\times$0,92}
\Retour{ht$\times 1.196$}
 } 
\end{algorithm}
\end{frame}


\xc

\begin{frame}[fragile]
\frametitle{XCAS}

\begin{lstlisting}
remise(HT):={
local ht;
ht:=HT;
si (ht>=2500) et (ht<4000) alors ht:=ht*0.95;fsi;
si ht>=4000 alors ht:=ht*0.92; fsi;
return(ht*1.196)
 }
\end{lstlisting}

\pause


\begin{lstlisting}
remise(HT):={
local ht;
ht:=HT;
 if( (ht>=2500) and (ht<4000)){ht:=ht*0.95};
 if(ht>=4000){ht:=ht*0.92};
return(ht*1.196)
 }
\end{lstlisting}

\end{frame}


\begin{frame}[fragile]
 \frametitle{CAML}
\caml
\begin{lstlisting}
let prix_ttc_apres_remise (prix_hors_taxe)
    =
    let
     taux_remise = if prix_hors_taxe < 2500.
                    then 0.
                    else if prix_hors_taxe < 4000.
                          then 0.05
                          else 0.08
    in
     (1. -. taux_remise) *. prix_hors_taxe *. 1.196

\end{lstlisting}

\pause

On  remarque au passage  comment définir  une fonction  locale imbriquée
dans une autre fonction.


\end{frame}

\xc


\section{Algorithmes en arithmétique}



\subsection{Quotient euclidien}

%\subsubsection{Quotient}


\begin{frame}[fragile]
  \frametitle{Version récursive}

\begin{algorithm}[H]
\caption{Quotient  : version récursive}
reste(a,b)
\Deb{
\Si{a<b}{\Retour{0}}
 } 
\Retour{1+quotient(a-b,b)}
\end{algorithm}
  
\end{frame}

\begin{frame}[fragile]
  \frametitle{Avec XCAS}
  
\begin{lstlisting}
quotient(a,b):={
if(a<b){return(0)};
return(1+quotient(a-b,b));
}
\end{lstlisting}

\end{frame}

\begin{frame}[fragile]
  \frametitle{Avec CAML}
  
\caml

\begin{lstlisting}
# let rec quotient (a,b)
        =
        if a<b 
         then 0
         else  1+quotient(a-b,b);;
\end{lstlisting}

\xc

\end{frame}

\begin{frame}[fragile]
\begin{block}{Remarque}
  CAML étant intelligemment typé, si on entre~:

\verb+ # 37/5;;+

On obtient

\verb+- : int = 7+

c'est-à-dire par  défaut le  quotient entier car  on travaille  avec des
entiers.

\pause

Pour avoir une approximation décimale, il faut entrer~:

\verb+ # 37./.5.;;+

et on obtient~:

\verb+- : float = 7.4+

\pause

Pour le reste, on peut donc entrer~:

\verb+ # 37-37/5*5;;+

ou utiliser la commande infixée \verb+ mod +

\verb+ # 37 mod 2 ;;+
\end{block}
\end{frame}


\begin{frame}[fragile]
  \frametitle{Version impérative}
  


\begin{algorithm}[H]
\caption{Quotient : version impérative}
\Entree{2 entiers a et b}
\Deb{
\Ini{k\aff 0}
\Tq{$k\times b\ie a$}{k\aff k+1}
 } 
\Retour{k-1}
\end{algorithm}

\end{frame}




\begin{frame}[fragile]
  \frametitle{Avec XCAS}
  
\begin{lstlisting}
quotient(a,b):={
local k;
k:=0;
while(k*b<=a){k:=k+1}
return(k-1)
}
\end{lstlisting}

\end{frame}


\subsection{Divisibilité}

\begin{frame}[fragile]
  
On peut créer une fonction qui testera si un nombre divise un autre.

\pause

\begin{algorithm}[H]
\caption{Test de divisibilité}
\Entree{2 entiers n et p}
\Deb{
(quotient entier n/p)$\times$ p == n
 } 
\end{algorithm}

\pause

On effectue  un test booléen  en utilisant l'opérateur  infixe \verb+==+
qui désigne la relation d'égalité. La réponse du programme sera donc \og
vrai\fg{} ou  \og faux\fg{} ( \og 1\fg{}  ou \og 0\fg{} sur  XCAS et \og true\fg{}  ou \og
false\fg{} sur CAML)

\end{frame}

\begin{frame}[fragile]
  \frametitle{Avec XCAS}
  
\begin{lstlisting}
divise(p,n):={iquo(n,p)*p==n}:;
\end{lstlisting}

\end{frame}



\begin{frame}[fragile]
  \frametitle{Avec CAML}
  

\caml
\begin{lstlisting}
# let divise p n = ((n/p)*p=n);;
\end{lstlisting}

\pause

Qui s'utilise ainsi~:

\begin{lstlisting}
# divise 4 13;;
- : bool = false
# divise 4 12;;
- : bool = true
\end{lstlisting}

\xc


\end{frame}



\subsection{PGCD}


\begin{frame}[fragile]
  
Nous allons  voir plusieurs  algorithmes pour calculer  le PGCD  de deux
entiers.

\pause

Le plus naturel est la version récursive de l'algorithme d'Euclide~:


\begin{algorithm}[H]
\caption{Version récursive de l'algorithme d'Euclide}
PGCD1(a,b)
\Entree{2 entiers a et b}
\Deb{
\eSi{b=0}{\Retour{a}}{\Retour{PGCD1(b,reste(a,b))}}
 } 
\end{algorithm}

\end{frame}




\begin{frame}[fragile]
  \frametitle{Avec XCAS}
  
\begin{lstlisting}
PGCD1(a,b):={
if(b==0){return(a)}
else{return(PGCD1(b,irem(a,b)))}
}
\end{lstlisting}

\end{frame}


\begin{frame}[fragile]
  \frametitle{Avec CAML}
  
\caml

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

\xc


\end{frame}



\begin{frame}[fragile]
  \frametitle{Version impérative}
  
En version impérative, c'est un peu plus long et moins naturel ;-)



\begin{algorithm}[H]
\caption{PGCD : version impérative de l'algorithme d'Euclide}
\Entree{2 entiers a et b}
\Deb{
\Tq{$b\neq0$}{
r\aff reste(a,b)\;
a\aff b\;
b\aff r\;
}
 }
\Retour{a} 
\end{algorithm}
\end{frame}


\begin{frame}[fragile]
  \frametitle{Avec XCAS}
  
\begin{lstlisting}
PGCD2(a,b):={
local r;
while(b!=0){
r:=irem(a,b);
a:=b;
b:=r;
}
return(a)
}:;
\end{lstlisting}

\end{frame}


\begin{frame}[fragile]
  \frametitle{Algorithme des différences}
  

On     peut    également     utiliser    le     fait     que    $a\wedge
b=a\wedge(b-a)=a\wedge(a-b)$, mais c'est plus (beaucoup trop) long...
Une idée de recherche peut être de comparer les deux algorithmes.


\pause

\begin{algorithm}[H]
\caption{PGCD par l'algorithme des différences en version récursive}\label{pgcddiff}
PGCD3(a,b)
\Entree{2 entiers a et b}
\Deb{
\Si{b=0}{\Retour{a}}
\eSi{a>=b}{\Retour{PGCD3(b,a-b)}}{\Retour{PGCD3(a,b-a)}} 

} 
\end{algorithm}
\end{frame}


\begin{frame}[fragile]
  \frametitle{Avec XCAS}
  
\begin{lstlisting}
PGCD3(a,b):={
if(b==0){return(a)}
if(a>=b){return(PGCD3(b,a-b))}
else{return(PGCD3(a,b-a))}
}
\end{lstlisting}

\end{frame}



\begin{frame}[fragile]
  \frametitle{Avec CAML}
  
\caml

\begin{lstlisting}
let rec pgcdif (a,b)
        =
        if b=0 
         then a
         else  if a>b 
                then pgcdif(b,a-b)
         else pgcdif(a,b-a);;
\end{lstlisting}

\xc
\end{frame}


\subsection{Algorithme d'Euclide étendu}

\begin{frame}[fragile]
  
Petit rappel sur cet algorithme qui permet de prouver le théorème de
Bézout et d'obtenir des coefficients vérifiant $au+bv=a\wedge b$~:

\pause

\begin{center}
\begin{tabular}{|c||c|c|c||c|}
\hline $k$ & $u_k$ & $v_k$ & $r_k$ & $q_k$ \\ 
\hhline{=====} 0 & 1 & 0 &$r_0=a$& /  \\ 
\hline 1 & 0 & 1 &$r_1=b$& $q_1$  \\
\hline 2 & $u_0-u_1q_1$ & $v_0-v_1q_1$ &$r_2=r_0-r_1q_1$& $q_2$  \\ 
\hline 3 & $u_1-u_2q_2$ & $v_1-v_2q_2$ & $r_3=r_1-r_2q_2$&$q_3$  \\ 
\hline $\vdots$ &  &  & $\vdots$ & $\vdots$ \\ 
\hline $p-1$ &  &  & $r_{p-1}=a\wedge b$ & $q_{p-1}$ \\ 
\hline $p$ &  &  &   $r_p=0$ &\\
\hline 
\end{tabular} 
\end{center}

\end{frame}

\begin{frame}[fragile]
  
Par exemple, pour 19 et 15~:

\pause

\begin{center}
\begin{tabular}{|c||c|c|c||c|l}
\hhline{-----} $k$ & $u_k$ & $v_k$ & $r_k$ & $q_k$ &  \\ 
\hhline{=====} 0 & \psframebox[fillstyle=solid,fillcolor=bleu_ciel]{ 1} & \psframebox[fillstyle=solid,fillcolor=bleu_ciel]{ 0} & \psframebox[fillstyle=solid,fillcolor=bleu_ciel]{ 19} & / & $L_0$ \\ 
\hhline{-----} 1 & \psframebox[fillstyle=solid,fillcolor=bleu_ciel]{ 0} & \psframebox[fillstyle=solid,fillcolor=bleu_ciel]{ 1} & \psframebox[fillstyle=solid,fillcolor=bleu_ciel]{ 15} & \psframebox[fillstyle=solid,fillcolor=vert_e]{1} & $L_1$ \\ 
\hhline{-----} 2 & 1 & $-1$ & 4 & 3 & $L_2\leftarrow L_0-\psframebox[fillstyle=solid,fillcolor=vert_e]{1}\times L_1$ \\ 
\hhline{-----} 3 & $-3$ & 4 & 3 & 1 & $L_3\leftarrow L_1-3\times L_2$ \\ 
\hhline{-----} 4 & $u=4$ & $v=-5$ & $19\wedge 15=1$ & 3 & $L_4\leftarrow L_2-1\times L_3$ \\ 
\hhline{-----} 5 &  &  & 0 &  & $L_5\leftarrow L_3-3\times L_4$ \\ 
\hhline{-----} 
\end{tabular} 
\end{center}

\pause

C'est-à-dire $4\times 19-5\times 15=1$ et  $19\wedge 15=1$.

\end{frame}

\begin{frame}[fragile]
  \frametitle{Version récursive}
  
En version récursive, on peut procéder en deux étapes~:


\begin{algorithm}[H]
\caption{algorithme d'Euclide étendu~:~version récursive}
aee(u,v,r,u',v',r')\;
\Entree{6 entiers u, v, r, u', v', r'}
\Deb{
\eSi{r'=0}{\Retour([u,v,r])}
{aee(u',v',r',u-quotient(r,r')$\times$u',v-quotient(r,r')$\times$v',r-quotient(r,r')$\times$r')
 }
}

AEE(a,b)
\Entree{2 entiers a et b}
 \Deb{
aee(1,0,a,0,1,b)
}
\end{algorithm}

\end{frame}



\begin{frame}[fragile]
  \frametitle{Avec XCAS}
  
\begin{lstlisting}
aee(u,v,r,u',v',r'):={
if(r'==0){return([u,v,r])};
aee(u',v',r',u-iquo(r,r')*u',v-iquo(r,r')*v',r-iquo(r,r')*r')
}:;

AEE(a,b):=aee(1,0,a,0,1,b):;
\end{lstlisting}

\pause

Par exemple,  \verb+AEE(19,15)+ renvoie \verb+[4,-5,1]+  ce qui signifie
que $4\times 19-5\times 15=1$ et que $19\wedge 15=1$.

\end{frame}




\begin{frame}[fragile]
  \frametitle{Avec CAML}
  
\caml

\begin{lstlisting}
# let rec aee(u,v,r,u',v',r')
    =
  if r'=0 
   then [u;v;r]
  else aee(u',v',r',u-r/r'*u',v-r/r'*v',r-r/r'*r');;

# let aet(a,b)
      = aee(1,0,a,0,1,b);;
\end{lstlisting}

\xc

\end{frame}


\begin{frame}[fragile]
  \frametitle{Version impérative}
  
\begin{algorithm}[H]
\caption{algorithme d'Euclide étendu~:~version impérative}
\Entree{2 entiers a et b}
\Ini{
liste a\aff (1,0,a)\;
liste b\aff (0,1,b)\;
reste\aff b\;
}
\Deb{
\Tq{reste$\neq$0}{
q\aff quotient(3\up{e}opérande de liste a, reste)\;
liste temp\aff liste a-q$\times$liste b\;
liste a\aff liste b\;
liste b\aff liste temp\;
reste\aff 3\up{e}opérande de liste b
}
 } 
\Retour{liste a}
\end{algorithm}
\end{frame}



\begin{frame}[fragile]
  \frametitle{Avec XCAS}
  
\begin{lstlisting}
bezout(a,b):={
local la,lb,lr,q,reste;
la:=[1,0,a];
lb:=[0,1,b];
reste:=b;
while (reste !=0){
q:=quotient(la[2],reste);
lr:=la+(-q)*lb;
la:=lb;
lb:=lr;
reste:=lb[2];
}
return(la);
}
\end{lstlisting}


\end{frame}



\subsection{Fractions continues}




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

\begin{eqnarray}
172&=&3\times\textcolor{gray}{51}+\textcolor{blue}{19}\\
\textcolor{gray}{51}&=&2\times\textcolor{blue}{19}+13\\
19&=&1\times13+6\\
13&=&2\times 6+1\\
6&=&6\times 1+0
\end{eqnarray}

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

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

\end{itemize}
\end{frame}

\begin{frame}[fragile]
  \frametitle{Algorithme récursif}
  
On suppose connus les algorithmes  donnant le reste et le quotient d'une
division euclidienne.


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

L'algorithme \og réciproque \fg{}
sera étudié plus loin \vref{fci}.
\end{frame}





\begin{frame}[fragile]
  \frametitle{Avec XCAS}
  
\begin{lstlisting}
fc(a,b):={
if(b==0){return([])};
return(concat(iquo(a,b),fc(b,irem(a,b))))
}:;
\end{lstlisting}

\pause

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


\end{frame}





\begin{frame}[fragile]
  \frametitle{Avec CAML}
  
\caml

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

\xc

\end{frame}

\begin{frame}[fragile]
  \frametitle{Algorithme impératif}
  
\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{frame}

\begin{frame}[fragile]
  \frametitle{Avec XCAS}
  \begin{lstlisting}
frac_cont(a,b):={
local num,den,res,Liste;
num:=a;
den:=b;
res:=remain(num,den);
Liste:=NULL;
while(res>0){
    Liste:=Liste,iquo(num,den);
    num:=den;
    den:=res;
    res:=remain(num,den);
}
[Liste,iquo(num,den)];
}:;
\end{lstlisting}
\end{frame}


\subsection{Tests de primalité}


\begin{frame}[fragile]
  \frametitle{Première version}
  \begin{algorithm}[H]
\caption{test de primalité 1}
\Entree{un entier n}
\Deb{
\Pour{k de 2 jusque partie entière de $\sqrt{n}$}{
\Si{reste de la division de n par k est nul}{\Retour{n n'est pas premier}}
}
\Retour{n est premier}
 } 
\end{algorithm}

\end{frame}


\begin{frame}[fragile]
  \frametitle{Avec XCAS}
  
\begin{lstlisting}
testPrem1(n):={
local k;
pour k de 2 jusque floor(sqrt(n)) faire
  si irem(n,k)==0 alors return(n+" n'est pas premier");
  fsi;
fpour;
return(n+" est premier");
}:;
\end{lstlisting}

\pause


\begin{lstlisting}
testPrem1(n):={
local k;
 for(k:=2;k<=floor(sqrt(n));k++){
   if(irem(n,k)==0){return(n+" n'est pas premier")};
 };
return(n+" est premier");
}:;
\end{lstlisting}


\pause


Cependant, il  faut parfois être patient~:~\verb|testPrem1(2^(10000)+1)|
a mis  près de 10  minutes avant de  répondre que ce nombre  n'était pas
premier...


\end{frame}



\begin{frame}[fragile]
  \frametitle{Avec CAML}
  

\caml


\begin{lstlisting}
# let test_naif n =
     let rec test_local(m,k)=
        if m*m>k then "premier"
	else if k/m*m =k then "compose"
        else test_local(m+1,k)
     in test_local(2,n);;  
\end{lstlisting}

\pause

On  note   au  passage  comment  utiliser  une   fonction  localement  à
l'intérieur d'une autre.
On aurait pu tout aussi bien les écrire séparément~:

\begin{lstlisting}
# let rec  test_local(m,k)=
        if m*m>k then "premier"
	else if k/m*m =k then "compose"
        else test_local(m+1,k);;

# let test_naif n = test_local(2,n);;  
\end{lstlisting}




\xc

\end{frame}



\begin{frame}[fragile]
  \frametitle{Deuxième version}
  
Une première  possibilité pour diviser le  nombre de tests par  2 est de
vérifier au départ si le nombre est pair. Dans le cas contraire, on peut
faire des sauts de 2 à partir de 3~:

\pause

\begin{algorithm}[H]
\caption{test de primalité 2}
\Entree{un entier n}
\Deb{
\Si{n est pair}{\Retour{n n'est pas premier}}
\Pour{k de 2 jusque partie entière de $\sqrt{n}$ avec un pas de 2}{
\Si{reste de la division de n par k est nul}{\Retour{n n'est pas premier}}
}
\Retour{n est premier}
 } 
\end{algorithm}
\end{frame}



\begin{frame}[fragile]
  \frametitle{Avec XCAS}
  
\begin{lstlisting}
testPrem1(n):={
local k;
si irem(n,2)==0 alors return(n+ " n'est pas premier"); fsi;
pour k de 3 jusque floor(sqrt(n)) pas 2 faire
  si irem(n,k)==0 alors return(n+" n'est pas premier");
  fsi;
fpour;
return(n+" est premier");
}:;
\end{lstlisting}
\end{frame}




\begin{frame}[fragile]
  \frametitle{Avec XCAS en anglais}
  

\begin{lstlisting}
testPrem1(n):={
local k;
 if(irem(n,2)==0){return(n+ " n'est pas premier")};
 for(k:=3; k<=floor(sqrt(n));k:=k+2){
    if(irem(n,k)==0){return(n+" n'est pas premier")};
 };
return(n+" est premier");
}:;
\end{lstlisting}

\pause

Plus que  291 secondes... On a  bien divisé le temps  de compilation par
deux. 

\end{frame}


\begin{frame}[fragile]
  \frametitle{Avec CAML}
  
\caml
\begin{lstlisting}
#  let test_naif_2 n =
     let rec test_local(m,k)=
      if k/2*2=k then "pair"
      else 
        if m*m>k then "premier"
	else if k/m*m =k then "compose"
        else test_local(m+2,k)
     in test_local(3,n);; 
\end{lstlisting}

\xc

\end{frame}



\begin{frame}
  On peut affiner en enlevant les multiples de 3.
\end{frame}



\subsection{Crible d'Ératosthène}

\begin{frame}[fragile]
  \frametitle{Version impérative avec XCAS}
  
\begin{lstlisting}
erato(n):={
local j,k,P;
P:=[seq(k,k=1..n)];
P[0]:=0;
pour j de 2 jusque floor(sqrt(n)) faire
  si P[j-1]>=1 alors
    pour k de 2 jusque floor(n/j) faire
      P[j*k-1]:=0;
    fpour;
  fsi;
fpour;
return(select(x->(x>=1),P));
}:;
\end{lstlisting}

\end{frame}


\begin{frame}[fragile]
  \frametitle{En anglais}
  \begin{lstlisting}
erato(n):={
local j,k,P;
P:=[seq(k,k=1..n)];
P[0]:=0;
for(j:=2;j<=floor(sqrt(n));j++){
  if(P[j-1]>=1){
     for(k:=2;k<=floor(n/j);k++){
         P[j*k-1]:=0;
      };
  };
};
return(select(x->(x>=1),P));
}:;
\end{lstlisting}

\end{frame}







\begin{frame}[fragile]
  \frametitle{Avec CAML}
  
En CAML, la récursion peut se faire en étapes pour plus de lisibilité.

\pause
\caml

On fabrique une fonction qui renvoie un intervalle entier dont on a entré les
bornes~:

\begin{lstlisting}
# let rec  inter(a,b)= if a>b then [] else a::inter(a+1,b);;
\end{lstlisting}

\pause

Ainsi~:


\begin{lstlisting}
# inter(2,12);;
- : int list = [2; 3; 4; 5; 6; 7; 8; 9; 10; 11; 12]
\end{lstlisting}

\end{frame}




\begin{frame}[fragile]
  \frametitle{Avec CAML}
  
\caml

Ensuite, on crée une fonction  qui retire les multiples d'un entier dans
une liste donnée~:

\begin{lstlisting}
# let rec retmultiples(l,n)=
        if l=[] then [] else
              if hd(l)/n*n<>hd(l) then hd(l)::(retmultiples(tl(l),n)) else retmultiples(tl(l),n);;
\end{lstlisting}

\pause

Ainsi on peut enlever les multiples de 3 compris entre 2 et 12~:

\begin{lstlisting}
# retmultiples(inter(2,12),3);;
- : int list = [2; 4; 5; 7; 8; 10; 11]
\end{lstlisting}


\end{frame}







\begin{frame}[fragile]
  \frametitle{Avec CAML}
  
Enfin, voici le c\oe ur de la procédure~:
\caml

\begin{lstlisting}
# let crible(m)=
      let rec crible_rec(l,n)=
        if n>m then []
        else
          if n*n>m then n::(crible_rec(l,n+1))
	  else n::retmultiples(crible_rec(l,n+1),n)
in crible_rec(inter(2,m),2);;
\end{lstlisting}

\pause

L'utilisation est simple~:



\begin{lstlisting}
# crible(100);;
- : int list =
[2; 3; 5; 7; 11; 13; 17; 19; 23; 29; 31; 37; 41; 43; 47; 53; 59; 61; 67; 71;
 73; 79; 83; 89; 97]
\end{lstlisting}

\pause

\xc

Comparons~:   \verb+erato(10000)+    répond   en   7,83    secondes   et
\verb+crible(10000)+ en 1,70 secondes.

On peut évidemment améliorer chacun des algorithmes avec du savoir-faire.



\end{frame}


\subsection{Nombre de chiffres d'un entier}


\begin{frame}[fragile]
  
On  pense au  logarithme ou  à  la rigueur  à une  ruse informatique  du
style~:\og  je transforme  mon  nombre  en chaîne  de  caractères et  je
demande au logiciel de compter le  nombre de caractères de la chaîne (ce
qu'ils savent tous faire)\fg{}. 

\pause

 La première solution est peu utilisable
en 2\up{nde} et la deuxième peu intéressante mathématiquement.

\pause

Alors on \og pense base 10\fg{}~:


\begin{algorithm}[H]
\caption{nombre de chiffres d'un entier naturel}
NbChiffres(n)
\Entree{un entier naturel n}
\Deb{
\eSi{n<10}{1}{1+NbChiffres(quotient\_entier(n,10))}
 } 
\end{algorithm}


\end{frame}


\begin{frame}[fragile]
  \frametitle{Avec XCAS}
  
\begin{lstlisting}
NbChiffres(n):={
if(n<10){1}else{1+NbChiffres(iquo(n,10))}
}:;
\end{lstlisting}

\end{frame}


\begin{frame}[fragile]
  \frametitle{Avec CAML}
  
\caml

\begin{lstlisting}
# let rec NbChiffres n = if n<10 then 1 else 1+NbChiffres(n/10);;
\end{lstlisting}

\xc

\end{frame}




\subsection{Décomposition en base 2}






\begin{frame}[fragile]
  
Une  méthode  pour  obtenir  l'écriture   en  base  2  d'un  nombre  est
d'effectuer des divisions successives. Par exemple pour 11~:

\begin{center}
\opidiv[remainderstyle=\bfseries\large\color{gray},resultstyle=\color{blue}]{11}{2}\hspace{1cm}
\opidiv[remainderstyle=\bfseries\large\color{gray},resultstyle=\color{blue}]{5}{2}
\hspace{1cm}
\opidiv[remainderstyle=\bfseries\large\color{gray},resultstyle=\color{blue}]{2}{2}
\hspace{1cm}
\opidiv[remainderstyle=\bfseries\large\color{gray},resultstyle=\color{blue}]{1}{2}

\end{center}

\pause

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

\pause

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


\end{frame}









\begin{frame}[fragile]
  
\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{frame}


\begin{frame}[fragile]
  \frametitle{Avec XCAS}
  
\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{frame}



\begin{frame}[fragile]
  \frametitle{Version récursive}
  
Notons $q_n$ et $r_n$ le quotient et le reste après $n$ divisions.

\pause

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

\pause


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

\pause

\begin{algorithm}[H]
\caption{Conversion binaire : version récursive}
Binaire(n)
\Entree{un entier n}
\Deb{
\eSi{n<2}{\Retour{n}}{\Retour{Binaire(quotient(n,2)),reste(n,2)}}
 } 
\end{algorithm}

\end{frame}

\begin{frame}[fragile]
  \frametitle{Avec XCAS}
  
\begin{lstlisting}
Binaire(n):={
    if (n<2){return n}
    else{
      return(Binaire(iquo(n,2)),irem(n,2));
    }
 }:;
\end{lstlisting}

\end{frame}


\begin{frame}[fragile]
  \frametitle{Avec CAML}
  
\caml

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


\pause
\begin{block}{Remarque}
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.

\end{block}
\xc
\end{frame}



\section{Opérations avec des fractions}


\subsection{Définitions des opérations}

\begin{frame}[fragile]

\caml
On travaillera avec CAML.
  
On aura besoin d'un algorithme de calcul du PGCD~:

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


\end{frame}



\begin{frame}[fragile]

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

\pause

On invoquera  cette exception  avec la commande  \verb+raise+ : étant  donné le
niveau d’anglais des élèves, cette commande est naturelle !...

\end{frame}



\begin{frame}[fragile]

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

\pause

Par exemple

\begin{lstlisting}
# simp([18;12]);;
- : int list = [3; 2]
\end{lstlisting}

\pause

Mais 

\begin{lstlisting}
# simp([1;0]);;
Exception: Division_par_zero.

\end{lstlisting}


\end{frame}



\begin{frame}[fragile]

\caml

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}

\pause

Par exemple~:


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


\end{frame}




\begin{frame}[fragile]

\caml


Une multiplication~:

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

\pause

Par exemple~:

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



\end{frame}




\begin{frame}[fragile]
\caml

Un inverse~:


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

\pause

Une division~:

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


\end{frame}


\begin{frame}[fragile]
\caml
Par exemple, comment entrer \[1+\frac{2+\frac{3}{4}}{1-\frac{5}{6}}\]


\pause

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

\pause

É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,...



\end{frame}






\subsection{Fractions continues~:~le retour}


\begin{frame}
  
Nous avions vu à l'algorithme~\vref{fc} comment, à partir d'un nombre écrit sous forme
fractionnaire, on  pouvait obtenir son  écriture sous forme  de fraction
continue.

\pause

Nous  allons  à  présent  voir comment  effectuer  l'opération  inverse,
c'est-à-dire comment  obtenir une fraction  irréductible à partir  de la
liste du développement en fraction continue.

\label{fci}

\pause

Souvenez-vous~:
\[
\frac{172}{51}=3+\frac{19}{51}=3+\frac{1}{\frac{51}{19}}=3+\frac{1}{2+\frac{13}{19}}=
3+\frac{1}{2+\frac{1}{1+\frac{1}{2+\frac{1}{6}}}}=[3;2;1;2;6]
\]
\end{frame}


\begin{frame}[fragile]
  \frametitle{L'algorithme}
  \caml

\begin{algorithm}[H]
\caption{Fractions continues~:~le retour récursif}
\texttt{frac\_inv(lx)}\;
\Entree{La liste lx du développement en fraction continue}
\Deb{
\eSi{lx ne contient qu'un seul élément }{\Retour{cet élément}
}{\Retour{le  premier élément  de  lx  +l'inverse de  {\rm\texttt{frac\_inv}}(lx  privé de  son
  premier élément)}}
 } 
\end{algorithm}


\pause


\begin{lstlisting}
# let rec frac_inv(lx)=
      if length lx=1 then [hd(lx);1]
      else som([hd(lx);1],inv(frac_inv(tl(lx))));;
\end{lstlisting}


\end{frame}




\begin{frame}[fragile]
  
Et voici comment l'utiliser~:

\begin{lstlisting}
# frac_inv([3;2;1;2;6]);;
- : int list = [172; 51]
\end{lstlisting}

\pause

Une petite curiosité au passage~:

\begin{lstlisting}
# frac_inv([0;3;2;1;2;6]);;
- : int list = [51; 172]
\end{lstlisting}


\xc
\end{frame}






\section{Algorithmes de calcul plus complexes}

\subsection{Algorithme de \textsc{Hörner}}


\begin{frame}
  
Prenons   l'exemple   de   $P(x)=3x^5-2x^4+7x^3+2x^2+5x-3$.  Le   calcul
classique nécessite 5 additions et 15 multiplications.


\pause

On peut faire pas mal d'économies de calcul en suivant le schéma suivant :

\begin{center}
\begin{arrayl}
P(x)&=&\ds\underbrace{a_nx^n+\cdots+a_2x^2+a_1x}_{\text{on met $x$ en facteur}}+a_0\\
            &=&\left(\ds\underbrace{a_nx^{n-1}+\cdots+a_2x}_{\text{on met $x$ en facteur}}+a_1\right)x+a_0\\
            &=& \cdots\\
            &=& \left(\cdots(((a_nx+a_{n-1})x+a_{n-2})x+a_{n-3})x+\cdots\right)x+a_0\\
\end{arrayl}
\end{center}

\pause

Ici   cela   donne   $P(x)=(((((3x)-2)x+7)x+2)x+5)x-3$  c'est-à-dire   5
multiplications et 5 additions. En fait il y a au maximum $2\times$degré
de P opérations (voire moins avec les zéros).

\end{frame}



\begin{frame}[fragile]
  \frametitle{Algorithme}
  
Il faut connaître les coefficients de P. 



\begin{algorithm}[H]
\caption{algorithme de \textsc{Hörner} : version récursive}
horner(P,x)
\Entree{les  coefficients $a_i$ dans  l'ordre décroissant  des exposants
  des monômes, le degré $n$ de P et le nombre $x$}
\Deb{
\eSi{P est vide}{\Retour{0}}
{\Retour{Tête de P + x$\times$ horner(P privé de sa tête, x)}
}
 } 
\end{algorithm}

\end{frame}




\begin{frame}[fragile]
  \frametitle{Avec XCAS}
  
\begin{lstlisting}
Horner(P,x):={
if(P=[]){return(0)}
else{return(P[0]+x*Horner(tail(P),x))}
}:;
\end{lstlisting}

\end{frame}


\begin{frame}[fragile]
  \frametitle{Avec CAML}
  
\caml

\begin{lstlisting}
# let rec horner(p,x) =
   if p=[] then 0
   else   List.hd(p)+x*(horner(List.tl(p),x));;
\end{lstlisting}

 


\xc

\end{frame}


\subsection{Exponentiation rapide}

\begin{frame}
  Étudions une méthode d'exponentiation rapide.

\pause

Voyons comment procéder sur $a^{11}$~:

$a^{11}=a\cdot   a^{10}=a\cdot   \left(a^5\right)^2=a\cdot  \left(a\cdot
  a^4\right)^2=a\cdot \left(a\cdot \left(a^2\right)^2\right)^2$

\end{frame}



\begin{frame}[fragile]
  \begin{algorithm}[H]
\caption{exponentiation rapide sans utiliser la base 2}
\Entree{un réel a et un entier n}
\Ini{
res\aff 1\;
puissance\aff n\;
temp\aff a}
\Deb{
\Tq{puissance non nulle}{
\Si{puissance est impaire}{
res\aff temp$\times$res\;
puissance\aff puissance $-$ 1
}
puissance\aff puissance $\div$ 2\;
temp\aff temp$\times$temp
 } 
}
\end{algorithm}

\end{frame}


\begin{frame}[fragile]
  \frametitle{Avec XCAS}
  \begin{lstlisting}
expo_rapido(a,n):={
local res,temp,Puissance;
res:=1;
Puissance:=n;
temp:=a;
tantque Puissance >0 faire
   si irem(Puissance,2)==1 alors
      res:=temp*res;
      Puissance:=Puissance-1;
   fsi;
Puissance:=Puissance/2;
temp:=temp*temp;
ftantque;
return(res);
}:;
\end{lstlisting}

\end{frame}


\begin{frame}[fragile]
  \frametitle{Avec CAML}
  
Avec CAML en version récursive c'est immédiat...

\caml
\begin{lstlisting}
# let rec pow_rap(a,n)=
         if n=0 then a
	 else if n/2*2=n then pow_rap(a,n/2)*pow_rap(a,n/2)
              else a*pow_rap(a,n/2);;
\end{lstlisting}
\xc


\end{frame}





\section{Algorithmes en analyse}



\subsection{Recherche de minimum}


\begin{frame}
  
On repère graphiquement qu'une  fonction semble atteindre par exemple un
minimum. Pour  obtenir une  approximation de ce  minimum, on  fournit un
point de départ et une précision.

\end{frame}


\begin{frame}[fragile]
  \frametitle{Version récursive avec XCAS}
  
\begin{lstlisting}
min_rec(f,xo,h):={
if(f(xo+h)>f(xo)){return(xo)}
else{min_rec(f,xo+h,h)}
}
\end{lstlisting}


\end{frame}




\begin{frame}[fragile]
  \frametitle{Version récursive avec CAML}
  

\caml

\begin{lstlisting}
# let rec min_rec(f,xo,h)=
    if f(xo+.h)>f(xo) then xo
    else min_rec(f,xo+.h,h);;
\end{lstlisting}


\xc



\end{frame}




\begin{frame}[fragile]
  \frametitle{Version impérative}
  
\begin{algorithm}[H]
\caption{approximation d'un minimum}
\Entree{fonction f, point de départ xo et incrément i}
\Ini{
Y\aff f(xo)\;
X\aff xo+i\;
}\;
\Deb{
\Tq{t(X)<Y}{
Y\aff evalf(t(X))\;
X\aff X+i\;
}
\Retour{X-i}
 } 
\end{algorithm}

\end{frame}



\begin{frame}[fragile]
  \frametitle{Version impérative avec XCAS}
  
\begin{lstlisting}
minimum(f,xo,p):={
local X,Y,compteur;
Y:=f(xo);
X:=xo+10^(-p);
compteur:=0 // on rajoute un compteur pour que la compilation ne dure pas trop longtemps
tantque evalf(f(X))<Y et compteur<10^p faire 
    Y:=evalf(f(X)); 
    X:=X+10^(-p);
    compteur:=compteur+1; 
ftantque:;
 X-10^(-p);
}:;
\end{lstlisting}

\end{frame}



\begin{frame}[fragile]
  

Par            exemple,            pour           la            fonction
$x\mapsto\sqrt{x^{2}+25}+\sqrt{\left(x-18\right)^{2}+49}  $,  il  semble
que le minimum soit vers 7.

\pause

Demandons une approximation du minimum à $10^{-5}$ près~:

\begin{lstlisting}
minimum(x->sqrt((x)^2+25)+sqrt((x-18)^2+49),7.0,5)
\end{lstlisting}

\pause

et on obtient 7.50000

\end{frame}


\subsection{Dichotomie}


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

\pause

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

\pause

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.



\end{frame}








\begin{frame}[fragile]
  \frametitle{Version récursive avec XCAS}
  
\begin{lstlisting}
dicho_rec(f,a,b,eps):={
if(evalf(b-a)<eps){return(0.5*(b+a))};
if(f(a)*f(0.5*(b+a))>0){return(dicho(f,0.5*(b+a),b,eps))}
                   else{return(dicho(f,a,0.5*(b+a),eps))}
}:;
\end{lstlisting}

\end{frame}





\begin{frame}[fragile]
  \frametitle{Version récursive avec CAML}
  
\caml

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


\pause

ce qui donne~:


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

\xc

\end{frame}



\begin{frame}[fragile]
  \frametitle{Version impérative}
  \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}

\end{frame}



\begin{frame}[fragile]
  \frametitle{Version impérative avec XCAS}

Avec XCAS, ne pas oublier de régler quelques problèmes de précision~:


\begin{lstlisting}
dicho(F,p,a,b):={
local aa,bb,k,f;
aa:=a;bb:=b;epsilon:=1e-100; 
f:=unapply(F,x);k:=0; 
 tantque evalf(bb-aa,p)>10^(-p) faire
    si sign(evalf(f((bb+aa)/2),p))==sign(evalf(f(bb),p))
      alors bb:=evalf((aa+bb)/2,p);
      sinon aa:=evalf((aa+bb)/2,p);
      k:=k+1; // un tour de plus au compteur
    fsi;
 ftantque;
return evalf((bb+aa)/2,p)+" est la solution trouvee  apres " +k+ " iterations";
}:;

\end{lstlisting}


\end{frame}





\subsection{Méthode des rectangles}




\begin{frame}
  
On  veut  calculer une  intégrale  d'une  fonction  par la  méthode  des
rectangles. La définition récursive est assez naturelle.

\end{frame}


\begin{frame}[fragile]
  
\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}

\pause

Par exemple~:

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

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

donne~:

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

\pause

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



\end{frame}




\section{Systèmes de \textsc{Cramer}}

\begin{frame}
  
Soit un système $\bsys a_{11}x+a_{12}y=b_1\\ a_{21}x+a_{22}y=b_2\esys$.

\pause

Soit D le déterminant du sytème : $D=a_{11}a_{22}-a_{21}a_{12}$. 

\pause

S'il
est non nul,  il est assez aisé de montrer en  Seconde que les solutions
sont~:

$$x=\frac{b_{1}a_{22}-b_{2}a_{12}}{D}\qquad y=\frac{a_{11}b_{2}-a_{21}b_{1}}{D}$$

\pause

Cela peut mettre en évidence les rôles différents joués par les inconnues (qui
n'apparaissent pas en entrée dans l'algorithme) et les coefficients.

\end{frame}




\begin{frame}[fragile]
  \begin{algorithm}[H]
\caption{système de \textsc{Cramer}}
\Entree{Les coefficients}\;
\Deb{
\eSi{D=0}{pas de solution unique}{$x=\frac{b_{1}a_{22}-b_{2}a_{12}}{D}\qquad y=\frac{a_{11}b_{2}-a_{21}b_{1}}{D}$}
 } 
\end{algorithm}

\end{frame}



\begin{frame}[fragile]
  \frametitle{Avec XCAS}
  \begin{lstlisting}
cramer(a11,a12,b1,a21,a22,b2):={
 si a11*a22-a21*a12==0 
   alors return("Pas de solution unique")
   sinon return((b1*a22-b2*a12)/(a11*a22-a21*a12), (a11*b2-a21*b1)/(a11*a22-a21*a12))
 fsi
}:;
\end{lstlisting}

\end{frame}






\section{Algorithme de \textsc{Héron}}
\begin{frame}
\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  puisqu'il a
vécu seize siècles avant Sir Isaac.


\pause

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.

\pause

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.

\pause

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

On obtient naturellement un algorithme.
\end{frame}


\begin{frame}[fragile]
  \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}

\end{frame}


\begin{frame}[fragile]
  \frametitle{Avec XCAS}
  \begin{lstlisting}
heron(a,xo,eps):={
local X;
X:=0.5*(xo+a/xo);
while(abs(evalf(X-a/X))>=eps){
  X:=0.5*(X+a/X);
}
return(X)
}:;
\end{lstlisting}

\end{frame}



\begin{frame}[fragile]
  \frametitle{Version récursive avec CAML}
  \caml
\begin{lstlisting}
# let rec heron(a,xo,eps)=
      if abs_float(xo-.a/.xo)<eps then xo
      else heron(a,0.5*.(xo+.a/.xo),eps);;
\end{lstlisting}
\xc
\end{frame}



\section{Algorithmes en probabilité}


\subsection{Pile ou face}



\begin{frame}
  
On lance trois fois de suite  une pièce de monnaie. On compte combien de
fois pile (ou face) tombe.

\end{frame}



\begin{frame}
  \frametitle{Avec XCAS}
  


\begin{itemize}
\item \texttt{rand(k)}  renvoie un entier aléatoirement compris  entre 0 et
  $k-1$~;
\item  \texttt{count\_eq(entier,liste)}  compte  le  nombre de  fois  ou
  \texttt{entier} apparaît dans \texttt{liste}
\end{itemize}

\end{frame}



\begin{frame}[fragile]
  \frametitle{Avec XCAS}
  \begin{lstlisting}
piece(n):={
T:=NULL;
for(k:=1;k<=n;k++){
X:=0;
if(rand(2)==1){X:=X+1}
if(rand(2)==1){X:=X+1}
if(rand(2)==1){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}


\end{frame}


\begin{frame}[fragile]
  \frametitle{Avec XCAS}
  
Par exemple~:

\begin{lstlisting}
piece(5000)
\end{lstlisting}

renvoie \texttt{[0.1262,0.387,0.366,0.1208]}.


\pause

En  effet, on  peut vérifier  avec \texttt{binomial(n,k,p)}  qui renvoie
$\binom{n}{k}p^k(1-p)^{n-k}$~:

\begin{lstlisting}
[seq(binomial(3,k,0.5),k=0..3)]
\end{lstlisting}

renvoie \texttt{[0.125,0.375,0.375,0.125]}

\end{frame}




\begin{frame}[fragile]
  \frametitle{Avec XCAS}
  
On peut faire la  moyenne sur une dizaine de séries de  5000 séries de 3
lancers~:

\begin{lstlisting}
mean([seq(piece(5000),k=0..10)])
\end{lstlisting}

\pause

et on obtient \texttt{[0.1272909091,0.3854,0.3637272727,0.1235818182]}


\end{frame}




\subsection{Tirage de boules}


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


\end{frame}



\begin{frame}[fragile]
  \begin{lstlisting}
boules(n):={
T:=NULL;
for(k:=1;k<=n;k++){
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}
\end{frame}

\begin{frame}[fragile]
  
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$.

\end{frame}



\subsection{Problème du Duc de Toscane}

\begin{frame}
  Cosme II de Médicis  (Florence 1590-1621), Duc de Toscane, fut le  protecteur de l'illustre Gallilée
(né à Pise le 15 février 1564 et mort à Florence le 8 janvier 1642) son ancien précepteur. Profitant
d'un moment de répit du savant entre l'écriture d'un théorème sur la chute des corps et la création
de la lunette astronomique, le Grand Duc lui soumet le problème suivant~:~il a observé qu'en lançant
trois dés cubiques et en  faisant la somme des numéros des faces, on obtient  plus souvent 10 que 9,
alors qu'il y a autant de façons d'obtenir 9 que 10, à savoir six. 

Après  quelques réflexions,  Galilée  rédigea  un petit  mémoire  sur les  jeux  de  hasard en  1620
expliquant le phénomène. 

\end{frame}


\begin{frame}[fragile]

On  utilise \texttt{ranm(lignes,colonnes,'expérience')} qui renvoie une
matrice \texttt{lignes}$\times$\texttt{colonnes} où  chaque terme est un
résultat de \texttt{expérience}.

\pause

  \begin{lstlisting}
toscane(n):={
T:=ranm(1,n,'rand(6)+rand(6)+rand(6)+3');
return("Obtenir 9 :"+count_eq(9,T)*100.0/n+"%"," Obtenir 10 :"+count_eq(10,T)*100.0/n+"%")
}:;
\end{lstlisting}


\pause



Alors, pour $100\,000$ tirages, on obtient \texttt{"Obtenir 9 :11.263\%"," Obtenir 10 :12.535\%"}




\end{frame}



\section{ Lancers d'une pièce et résultats égaux}

\begin{frame}
  
On lance  10 fois  de suite une  pièce de  monnaie et on  s'intéresse au
nombre maximal de résultats consécutifs  égaux. On crée un programme qui
simule autant  de séries de lancers  que l'on désire. C'est  un peu plus
compliqué à écrire...


\end{frame}



\begin{frame}[fragile]
  \footnotesize
\begin{lstlisting}
piece_max(essais):={
local S,k,P,j,H,m,M,s,p,h;
S:=NULL;
 for(k:=1;k<=essais;k++){ 
  s:=NULL; 
  P:=[seq(rand(2),m=0..9)];
  p:=0;
   while(p<9){
    j:=p+1; 
     while (P[j]==P[p] and j<9){j:=j+1}
    s:=s,j-p; 
    p:=j;
   }
  s:=SortD([s]); 
  h:=head(s); 
  S:=S,h; 
 }
m:=evalf(mean([S]));
return("Sur "+essais+" series de 10 lancers, la moyenne du nombre maximal de resultats consecutifs egaux est "+m)
}:;
\end{lstlisting}

\normalsize
\end{frame}






%\section{Fractales}

\section{Flocon de \textsc{Von Koch}}
\begin{frame}
  On peut définir récursivement le flocon de \textsc{Von Koch}.
\pause

Pour simplifier, on se contentera de \og floconiser\fg{} un segment.
\end{frame}

\begin{frame}[fragile]
  \frametitle{Avec la tortue}
\begin{lstlisting}
koch(long,n):={
si (n==0) alors
avance(long);
sinon
koch(long/3,n-1);tourne_gauche(60);
koch(long/3,n-1);tourne_droite(120);
koch(long/3,n-1);tourne_gauche(60);
koch(long/3,n-1);
fsi;
}:;
\end{lstlisting}


\end{frame}


\begin{frame}[fragile]
\begin{lstlisting}
koch(500,3)
\end{lstlisting}


\begin{figure}
\begin{center}
  \includegraphics[width=\textwidth]{koch1}
\end{center}
\end{figure}



\end{frame}



\begin{frame}[fragile]
\begin{lstlisting}
koch(500,6)
\end{lstlisting}


\begin{figure}
\begin{center}
  \includegraphics[width=\textwidth]{koch2}
\end{center}
\end{figure}



\end{frame}


\begin{frame}[fragile]
  \frametitle{Avec les outils géométriques de XCAS}
  
\begin{lstlisting}
KochBis(n,A,B):={
 if(n==0){segment(A,B)}
 else{
   KochBis(n-1,A,homothetie(A,1/3,B)),
   KochBis(n-1,homothetie(A,1/3,B),rotation(homothetie(A,1/3,B),pi/3,homothetie(A,2/3,B))),
   KochBis(n-1,rotation(homothetie(A,1/3,B),pi/3,homothetie(A,2/3,B)),homothetie(A,2/3,B)),
   KochBis(n-1,homothetie(A,2/3,B),B)
 }
}:;
\end{lstlisting}

\end{frame}


\begin{frame}[fragile]
  \frametitle{Flocon}
\begin{lstlisting}
KochBis(3,point(0,0),point(10,0)),KochBis(3,point(10,0),point(5,-10*sqrt(3.0)/2)),KochBis(3,point(5,-10*sqrt(3.0)/2),point(0,0))
\end{lstlisting}



\end{frame}



\begin{frame}
  \frametitle{Flocon}

\begin{figure}
\begin{center}
  \includegraphics[width=\textwidth]{koch3}
\end{center}
\end{figure}
  
\end{frame}














\end{document}
