\documentclass[11pt,landscape]{report}
\usepackage[height=170mm,width=265mm,left=1.5cm]{geometry}
\usepackage{preambule-utf8}
\usepackage{listings,luximono}
%\usepackage[upright]{fourier}
\usepackage[boldsans]{ccfonts}
\usepackage{beton,euler}
\graphicspath{{/home/moi/Figures/}}


\fancyfoot[C]{Page \thepage}
\fancyhead[R]{{\scriptsize\textsl{  2\textsuperscript{nde}  4  -  Lycée
       Jean \textsc{Perrin} - 2009/2010 }}}
\renewcommand{\headrulewidth}{0.4pt}
 \pagestyle{fancy}



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



\newcommand\xc{\lstset{numbers=none,language=C,xleftmargin=10pt,%
keywordstyle=\color{black}%\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}
}


\newcommand\caml{\lstset{numbers=none,language=caml,xleftmargin=10pt,%
keywordstyle
=\color{black}
%\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{creme}}
}

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


\fbox{%
\begin{minipage}{\textwidth}
\smallskip
{\LARGE\bfseries \begin{center} TP algorithmique 1 - PGCD et fractions -
    2\up{nde} 4
\end{center}}
\smallskip
\end{minipage}
}
\vspace{1cm}



\begin{multicols}{2}

\section{Division}

\subsection{Comme en primaire}

Vous voulez  diviser 37 par 4~:~à  l'école primaire, vous  avez appris à
vous poser la question~:

\begin{center}
  \emph{En 37 combien de fois 4~?}
\end{center}

Puis vient le temps du calcul~:

\begin{itemize}
\item \emph{une fois 4, 4~:~trop petit...}
\item \emph{2 fois 4, 8~:~trop petit...}
\item \emph{3 fois 4, 12~:~trop petit...}
\item $\cdots$
\item  \emph{9 fois 4, 36~:~trop petit...}
\item \emph{10 fois 4, 40~:~Ah~! Trop grand~!}
\end{itemize}


\og Il y va\fg{} donc 9 fois mais on n'y est pas encore~:~il me reste un
petit pas à faire de 36 jusqu'à 37.

\begin{center}
  \includegraphics[width=.75\linewidth]{Nombres}
\end{center}



Comment traduire cette division à l'aide d'une somme et d'un produit~?

Comment s'appelle chaque membre de cette division~?

\subsection{Parlons à l'ordinateur}

Imaginez maintenant que  vous devez expliquer ce calcul  à un ordinateur
en l'imaginant comme un petit lutin se promenant sur la droite des nombres.


Vous pourriez commencer par lui dire~:~

\og  tu pars  de 0  et tu  vas
compter tes enjambées\fg{}, 

puis 

\og
tu avances de 4 unités tant que tu n'auras pas dépassé 37\fg{}.

 Enfin,

 \og
dès  que tu  as dépassé  37, tu  t'arrêtes~:~le quotient  est  le nombre
d'enjambées moins une\fg{}.


Il  ne  reste plus  qu'à  lui dire  dans  sa  langue... Nous  étudierons
principalement deux  langues informatiques  cette année~:~le XCAS  et le
OCAML.


Par exemple, en XCAS, cela donne~:

\xc
\begin{lstlisting}
quotient(dividende,diviseur):={ 
enjambees:=0;
 while(enjambees*diviseur<=dividende){
  enjambees:=enjambees+1
 }
return(enjambees-1)
}
\end{lstlisting}


\textbf{Écrivez  un  script  qui  renvoie  cette fois  le  reste  de  la
  division euclidienne de deux nombres.}


\subsection{Parlons à un ordinateur plus malin}

Les mathématiques,  c'est pour les  fainéants... Le problème,  c'est que
pour  pouvoir  se  payer  le  luxe  d'être fainéant,  il  faut  pas  mal
réfléchir~!

Par exemple, je  suis malin et passablement fainéant.  Je dois diviser a
par b donc savoir \og en a combien de fois b\fg{}. Je me dis~:

\begin{center}
  \emph{Ben  déjà, si  a  est  plus petit  que  b, en  a  il  y va  zéro
    fois~:~le quotient vaut donc zéro}
\end{center}


Puis je me dis~:

\begin{center}
  \emph{Si je  recule de  b, il  ira une fois  de moins  b dans  a. Cela
    signifie que quotient(a,b)=1+quotient(a-b,b)}
\end{center}


Eh ben, avec ça, un ordinateur intelligent va se débrouiller...

On lui demande le quotient de 37 par 4~:~

\begin{itemize}
\item  est-ce que  37 est  plus petit  que 4~?   Non, donc  je  garde en
  mémoire que 
quotient(37,4)=1+quotient(37-4,4) et je m'occupe de quotient(33,4)~;
\item  est-ce que  33 est  plus petit  que 4~?   Non, donc  je  garde en
  mémoire que 
 quotient(33,4)=1+quotient(33-4,4) et je m'occupe de quotient(29,4)~;
\item etc.
\item  est-ce que  5 est  plus petit  que 4~?   Non, donc  je  garde en
  mémoire que 
 quotient(5,4)=1+quotient(5-4,4) et je m'occupe de quotient(1,4)~;
\item est-ce que 1 est plus petit que 4~?  Oui, donc je sais que 
 quotient(1,4)=0~;
\item  donc je  vais pouvoir  calculer quotient(5,4)  puis quotient(9,4)
  puis etc.
\end{itemize}


Ça paraît  plus long mais  ce sale boulot  de gestion de la  mémoire est
fait  par des  logiciels intelligents.  Nous pouvons  nous  contenter de
donner juste  à l'ordinateur un cas  simple et un moyen  pour aller d'un
cas compliqué vers le cas simple. 

Regardez plutôt~!

\begin{lstlisting}
quotient_malin(dividende,diviseur):={
 if(dividende<diviseur)
   then{0}
   else{1+quotient_malin(dividende-diviseur,diviseur)} 
}
\end{lstlisting}


OCAML parle à peu près le même langage~:

\caml
\begin{lstlisting}
let rec quotient_malin(dividende,diviseur)=
    if dividende<diviseur 
      then 0
      else 1+quotient_malin(dividende-diviseur,diviseur)
\end{lstlisting}



\textbf{Écrivez un script qui renvoie cette fois le reste malin de la
  division euclidienne de deux nombres.}


\section{PGCD}

\subsection{Diviseur}

Le PéGéCéDé de deux nombres, c'est leur plus grand diviseur commun.

D'abord, qu'est-ce qu'on appelle un diviseur dans ce contexte~?

Par exemple, 4  divise 80 car le reste  de la division de 80  par 4 vaut
0~:~\og la division tombe juste\fg{} comme vous disiez en CM1.

On  peut aussi  dire  que 4  divise  32~:~4 est  donc un  \emph{diviseur
  commun} de 32 et 80. Mais est-ce le plus grand~?

\subsection{Euclide}

Euclide, c'est un savant  grec qui a eu beaucoup de bonnes  idées il y a
2300 ans. On utilise encore largement ses résultats au lycée.

Bon, vous voulez connaître le plus grand diviseur commun de deux nombres
$a$ et $b$.

Est-ce qu'il en existe au moins un~?


L'idée d'Euclide a été  d'effectuer la division...euclidienne de $a$ par
$b$. Soit $a$ le plus grand des deux.

\[a=b\times q+r\qquad{\rm avec }\quad 0\ie r<b\]


Appelons $d$ un diviseur commun de $a$ et $b$.

Pourquoi $d$ est aussi un diviseur commun de $b$ et $r$~? 

Et vice-versa
et dans l'autre sens~?

Donc chercher le PGCD  de $a$ et $b$ revient à chercher  celui de $b$ et
$r$.

Quel est  l'avantage~? Qu'est-ce  qui se passe  au bout d'un  moment~? Y
a-t-il un cas simple~? Peut-on utiliser notre méthode de fainéant~?


Testez vos conjectures sur la machine.


\section{Opérations sur les nombres rationnels}


\subsection{Fraction simplifiée}


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.

Par exemple sur XCAS~:

\xc

\begin{lstlisting}
simp(Fraction):={
a:=Fraction[0]; // le premier terme de la fraction
b:=Fraction[1]; // le second
  if(b==0)
    then{"On peut po diviser par 0"}
    else{[a/pgcd(a,b),b/pgcd(a,b)]}
}:;
\end{lstlisting}

Des commentaires~?


Sur OCAML, on procède à quelques aménagements.

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



\subsection{Opérations sur les fractions}


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}}}}
\]
\vspace{10cm}
.
\end{multicols}
\end{document}



%%% Local Variables: 
%%% mode: latex
%%% TeX-master: t
%%% End: 
