

\chapterimage{girl_robot}


\chapter{Programmer avec Maple}

\section{Quelques rappels}



Quelques rappels avant de travailler. Commencez chaque nouvel
exercice par un 

\begin{lstlisting}
> restart;
\end{lstlisting}
 pour <<~désaffecter~>> toutes les
variables éventuellement utilisées dans un calcul précédent.

Si vous avez lancé un calcul qui a l'air de ne pas vouloir se
terminer, cliquez sur l'icône \verb+STOP+ qui n'est active que lorsqu'un
calcul est en cours.

Chacune de vos entrées débute après un $prompt$ \texttt{>}, se
termine par un \texttt{;}\footnote{si vous voulez que le résultat
soit affiché.} ou un \texttt{:}\footnote{si vous voulez que MAPLE
exécute sans afficher.} puis appuyez sur la touche
\Enter. Si vous voulez passer à la ligne sans valider la
ligne précédente, tapez \Shift + \Enter. Pour revenir
plus haut, utilisez la souris ou les flèches de déplacement.






\section{Listes et séquences}



\subsection{Listes}

Les  listes  sont un  type  de  variable  particulier que  peut  manipuler
MAPLE.  Une  liste se  présente sous la  forme d'une suite  d'objets
séparés par des virgules entre crochets~:

\begin{lstlisting}
> L:=[1,2,a,g,maman,ln(5),3/2,x->3*x+2,[7,9]]
\end{lstlisting}

Cette suite est ORDONNÉE. Ses éléments sont donc numérotés.
On peut en extraire un élément particulier~:

\begin{lstlisting}
> L[5]
\end{lstlisting}


ou bien tous les éléments de la liste~:

\begin{lstlisting}
op(L)
\end{lstlisting}

ou bien une sous-liste~:

\begin{lstlisting}
> L[3..6];
\end{lstlisting}


On peut connaître la taille d'une liste~:

\begin{lstlisting}
> nops(L);
\end{lstlisting}

On peut ajouter un élément à une liste~:

\begin{lstlisting}
> L:=[op(L),nouveau]
\end{lstlisting}


On peut \emph{concaténer} deux listes~:

\begin{lstlisting}
> L1:=[1,2,3,4];
> L2:=[a,b,c];
> L:=[op(L1),op(L2)]
\end{lstlisting}



La liste vide se note~:

\begin{lstlisting}
> V:=[];
> nops(V);
\end{lstlisting}

On peut  effectuer des  opérations sur  une liste car  c'est un  type de
variable comme un autre~:


\begin{lstlisting}
> S:=L1+[op(L2),d];
> P:=3*L1;
\end{lstlisting}


\subsection{Les séquences}

Elles ressemblent aux listes mais sans les crochets. La différence majeure
est pourtant  qu'on ne peut pas  créer des séquences  de séquences alors
qu'on peut créer des listes de listes.

Plus accessoirement,  on peut modifier  un élément d'une liste  à l'aide
d'une affectation mais ce n'est pas possible pour une séquence~:

\begin{lstlisting}
> S:=a,b,c,d,e,f;
> S[3];
> S[3]:=4;
> L:=[S];
> L[3]:=4;
> L;
\end{lstlisting}


En général, elles servent à fabriquer des listes...


\begin{lstlisting}
> S1:=10,20,30,40,50,60;
> S2:=seq(10*k,k=3..10);
> S3:=10*k $ k=2..9;
> S4:= m $ 5;
\end{lstlisting}




\section{Algorithme et programme}




\ill{Un algorithme est une description  rigoureuse en un nombre fini d'étapes
de la résolution d'un problème.

La  notion  d'algorithme  existe   depuis  bien  avant  l'existence  des
ordinateurs et  même bien avant  la naissance du mot  lui-même puisqu'il
est tiré du nom du célèbre mathématicien persan \begin{otherlanguage}{farsi}
أبو عبد الله محمد بن موسى الخوارزمي
\end{otherlanguage} ou si vous préférez 
Abu  'Abdallah Muhammad  ibn  Musa al-Khwarizmi  qui  vécut au  IX\up{e}
siècle de  notre ère, c'est-à-dire près  de 3000 ans  après les premiers
algorithmes de calcul connus mis au point en Mésopotamie.}{al-khwarizmi}

Vous  utilisez  depuis  longtemps  des  algorithmes,  à  la  manière  de
M. Jourdain, sans toujours le savoir, par exemple lorsque vous lisez une
recette de cuisine, lorsque vous recherchez un mot dans le dictionnaire,
lorsque vous effectuez une addition posée.

Cependant, cette année, nous  nous contenterons d'algorithmes destinés à
être  utilisés  par un  ordinateur.  Nous  introduirons  donc un  langage
algorithmique  le moins  ambiguë possible  et le  plus standard  afin de
pouvoir mettre en \oe uvre ces algorithmes sur n'importe quelle machine.

Même si  nos algorithmes  doivent être indépendants  de tout  langage de
programmation, il sera  enrichissant de les tester \og  en vrai\fg{} sur
machine. Nous serons  donc amenés à parler à la  machine. Pour cela nous
utiliserons un langage servant d'interface  entre la machine et nous car
tout  être humain normalement  constitué ne  peut décemment  entamer une
longue conversation avec un ordinateur en langage machine. 


C'est  bien sûr  Maple qui  sera notre  langage. Ceux  d'entre  vous qui
choisirons l'option info utiliseront plutôt le langage Pascal.




\section{Quelques types prédéfinis}

Les  variables,  les  constantes,  les  arguments  introduits  dans  les
algorithmes peuvent être de types  différents. Tous les langages ont des
types prédéfinis à peu près communs.

Sur Maple, 
les principaux  types sont \verb+float+,  \verb+integer+, \verb+negint+,
\verb+nonnegint+, \verb+fraction+, \verb+list+, etc.

Consultez l'aide~:~\verb+?type;+



\subsection{Les entiers}

Un  entier naturel  est  un entier  positif  ou nul.  Le  choix à  faire
(c'est-à-dire  le  nombre  de  bits\footnote{Le  mot  «  bit  »  est  la
  contraction des  mots anglais binary  digit, qui signifient  « chiffre
  binaire »,  avec un jeu de  mot sur bit, «  morceau ». Il  ne faut pas
  confondre avec  le mot \og byte\fg{}, en  français \og multiplet\fg{},
  qui désigne un assemblage de bits, en général 8 (un octet).} à utiliser) dépend de la fourchette des
nombres  que  l'on  désire  utiliser.  Pour coder  des  nombres  entiers
naturels compris  entre 0 et 255, il  nous suffira de 8  bits (un octet)
car  $2^8=256$.  D'une  manière  générale  un codage  sur  $n$  bits  pourra
permettre de représenter des nombres entiers naturels compris entre 0 et
$2^{n-1}$.  Les  processeurs   disponibles  actuellement  proposent  des
codages  sur 32 ou  64 bits.  Cependant, les  logiciels ne  tiennent pas
toujours compte des  64 bits et vous avez  beau disposer d'un processeur
64 bits, il sera utilisé comme  s'il était de type 32 bits (notamment si
le système d'exploitation est microsoft-windows...).

Pour représenter un  nombre entier naturel après avoir  défini le nombre
de bits sur  lequel on le code,  il suffit de ranger chaque  bit dans la
cellule binaire correspondant  à son poids binaire de  la droite vers la
gauche, puis on « remplit » les bits non utilisés par des zéros. 

\medskip

Pour les  entiers relatifs, le bit  situé à l'extrême gauche  (le bit de
poids fort), représentera le signe: 0  pour un nombre positif, 1 pour un
nombre négatif. Cela restreint donc l'étendue des nombres disponibles.

Un entier  relatif positif  est donc codé  comme un entier  naturel mais
avec un 0 à gauche.


Pour les entiers  négatifs, on utilise une petite  ruse: le complément à
2 que nous étudierons à titre d'exercice.

Ainsi,  sur   les  ordinateurs  qui  sont  à   notre  disposition,  tout
introduction  d'un   entier  dépassant  $2^{31}-1=\numprint{2147483647}$
engendrera une erreur.



\subsection{Les flottants}

La norme IEEE définit la façon de coder un nombre réel.
Cette norme se  propose de coder le nombre sur 32  bits et définit trois
composantes : 

\begin{itemize}
\item le  signe est  représenté par un  seul bit,  le bit de  poids fort
  (celui le plus à gauche);
\item l'exposant est codé sur les 8 bits consécutifs au signe;
\item la mantisse, c'est-à-dire le nombre \og sans la virgule\fg{}, sur les 23 bits restants.
\end{itemize}

   

La précision des  nombres réels est approchée. Elle  dépend du nombre de
positions décimales, suivant le type de réel elle sera au moins:

\begin{itemize}
\item de 6 chiffres après la virgule pour un système 32 bits;
\item de 15 chiffres après la virgule pour un système 64 bits.
\end{itemize}


Ces  limitations peuvent  causer quelques  surprises. Par  exemple, vous
pouvez tester sur Maple:


\begin{lstlisting}
> 100000+0.0000002;
\end{lstlisting}


\begin{boxedverbatim}
  100000
\end{boxedverbatim}


\begin{remarque}
Ces  problèmes   d'implémentation  des  entiers  et   des  flottants  ne
concernent pas l'algorithmique mais la 
programmation dans un  certain langage, sur un certain  système. 
\end{remarque}


\subsection{Les caractères et chaînes de caractères}


Le type \og caractère\fg{} permet de stocker le code d'un
caractère, c'est-à-dire  un nombre entier. Une chaîne  de caractères est
une  suite ordonnée de  caractères.  La  représentation d'une  chaîne de
caractères dépend d'un système à un autre. 

\subsection{Les booléens}
Avant  d'étudier  les  structures  conditionnelles, il  nous  faut  nous
habituer aux tests, aux booléens et  à leurs opérateurs, qui ne sont pas
d'un usage aussi naturel que les types flottants et entiers.

 \begin{itemize}
    \item Une variable de type booléen n'a que deux valeurs possibles: VRAI ou
FAUX.
\item Ces  booléens sont en  particulier les valeurs retournées  par les
  opérateurs  de comparaison:  \verb+=+, \verb+<+,  \verb+<=+, \verb+>+,
  \verb+>=+, \verb+<>+.
\item  Ils   ont  en   général  4  opérateurs:   \verb+ET+,  \verb+OU+,
  \verb+OUEX+, \verb+NON+.
  \end{itemize}


  \begin{recherche}
    
 

Par exemple, quelle sera la réponse à:

\begin{itemize}
\item $3>2$ ET $2>2$?
\item $3>2$ ET $2 \geqslant 2$?
\item $3>2$ OU $2>2$?
\item $3>2$ OU $2 \geqslant 2$?
\item $3>2$ OUEX $2 \geqslant 2$?
\item $3>2$ OUEX $2>2$?
\item NON $2>2$?
\item NON $3>2$?
\end{itemize}

 \end{recherche}


Sur Maple, les opérateurs logiques sont \verb+and+ et \verb+or+. Il y a aussi
\verb+not+ qui donne la négation.

\begin{recherche}
   Que dire du \verb+or+ de Maple?
\end{recherche}

Il existe une bibliothèque dédiée à la logique qui logiquement s'appelle \verb+logic+.


Quand  une   expression  ne   contient  pas  \verb+and+,   \verb+or+  ou
\verb+not+, il faut utiliser \verb+evalb+ ou \verb+is+~:



\begin{lstlisting}
> evalb(3>2);
\end{lstlisting}

%\begin{figure}[!h]
  \begin{DANGER}[type de nombre]
    On  ne  peut  comparer   que  des  nombres  de  type  \verb+numeric+
    (i.e. \verb+integer+, \verb+float+ et \verb+fraction+)~:

\begin{lstlisting}
> evalb(3>2.);
> evalb(3>7/2);
> evalb(sqrt(2)>1);
> evalb(sqrt(2.)>1);
\end{lstlisting}
    \end{DANGER}
%  \end{figure}

\section{Les structures conditionnelles}

Elles  sont   communes  aux  deux   types  de  programmation   que  nous
étudierons. C'est le fameux SI...ALORS...SINON...


Voici un bel algorithme:


\begin{algo}
\FUNC{zorg}{%
\pfarg{a,b,c}{entier}}{caractère}
\BEGIN
\IF{a<>b}
\IF{a+1=b}
\RETURN{'aarrgh'}
\ELSE
\IF{c<>7}
\RETURN{'glurp'}
\ELSE
\RETURN{'pas glop'}
\ENDIF
\ENDIF
\ELSE
\RETURN{'eviv bulgroz'}
\END 
\end{algo}

\begin{recherche}
Que répond 
\begin{itemize}
  \item \verb+zorg(4,5,7)+?
\item \verb+zorg(4,5,8)+?
\item \verb+zorg(4,6,7)+?
\end{itemize}
\end{recherche}




Sur Maple, on  utilise   la  valeur  d'un   test  pour  exécuter   une  instruction
conditionnelle dont la syntaxe est~:

\begin{center}

  \textbf{if} condition \textbf{then} instruction1 \textbf{else} instruction2 \textbf{fi};
\end{center}

Par exemple~:

\begin{lstlisting}
> if (3>2) then print('bonjour') else print('salut') fi;
> if (3<2) then print('bonjour') else print('salut') fi;
\end{lstlisting}



On peut écrire des instructions conditionnelles en cascade~:

\begin{center}

  \textbf{if}  condition1  \textbf{then} instruction1  \textbf{elif}
  condition2 \textbf{then} instruction2 \textbf{else} instruction3 \textbf{fi};

\end{center}


Par exemple~:

\begin{lstlisting}
> a:=1; b:=1; c:=1;

> if (b^2-4*a*c>0)
     then print(`2 solutions reelles`)
  elif (b^2-4*a*c=0)
     then print(`1 solution reelle`)
     else print(`2 solutions complexes conjuguees`)
  fi;
\end{lstlisting}


\section{Procédures}

Une  procédure est une  fonction à  la syntaxe  précise dépendant  de la
donnée d'une série d'arguments et d'une série d'instructions.

La syntaxe générale est~:

\begin{lstlisting}
> nom:=proc(argument1::type1,argument2::type2,.....)
  local var1, var2,... ;
  instructions
  end:
\end{lstlisting}


Les variables locales sont celles  introduites dans la procédure et dont
les noms seront \og désaffectés\fg{} à la fin de la procédure.



  \begin{DANGER}[première ligne]
    Pas de point-virgule sur la première ligne contenant \verb+proc+~!
    \end{DANGER}
  
Par exemple~:

\begin{lstlisting}
> Table:=proc(n::posint)
  local T,k;
  T:=[seq(n*k,k=1..10)];
  printf("La table de %a est %a",n,T)
  end:
\end{lstlisting}

Vous pourrez regarder la  syntaxe de \verb+printf+. L'usage des \verb+%a+
indique qu'on va les remplacer  dans l'ordre par les variables formelles
qui sont listées après les  guillemets. Pour avoir des nombres flottants
on utilise \verb+%f+.


Par exemple, pour obtenir la table de 5 on tape~:

\begin{lstlisting}
> Table(5);
\end{lstlisting}


On a souvent besoin du résultat  d'une procédure et la petite phrase \og
pour faire joli\fg{} peut être gênante.

On préférera une procédure de cette forme~:

\begin{lstlisting}
> Table:=proc(n::posint)
  local k;
  RETURN([seq(n*k,k=1..10)])
  end:
\end{lstlisting}

On peut ainsi afficher le deuxième élément de la table de 5~:

\begin{lstlisting}
> Table(5)[2];
\end{lstlisting}

\begin{recherche}
Que donne \verb+Table(-5)+~?  
\end{recherche}




On peut utiliser une structure conditionnelle~:

\begin{lstlisting}
> parite:=proc(n::integer)
   if (irem(n,2)=0)
     then RETURN(`pair`)
     else RETURN(`impair`)
   fi
  end:
\end{lstlisting}


\begin{recherche}
  À votre avis, que renvoie \verb+irem(a,b)+ ?
\end{recherche}





\section{La programmation impérative: au plus près de la machine}



Un algorithme impératif va  modifier chronologiquement l'état de la
mémoire (voir la section \vref{affectation}). Les valeurs des variables vont sans cesse évoluer. Cependant,
la plupart  du temps, les notations des  structures itératives utilisées
n'expriment pas  clairement l'état des  variables. Il faudra  donc, pour
bien  maîtriser  l'algorithme,  le  commenter  pour  décrire  les  états
parcourus par le système.



\begin{DANGER}
On veillera à ne pas  modifier les arguments d'une fonction avec quelque
chose du style:

\begin{lstlisting}[caption={}]
> non:=proc(a,b,c)
  a:=a+1;
  RETURN(a);
  end:
\end{lstlisting}

Il faut  introduire une variable locale  prenant au départ  la valeur de
l'argument puis la modifier:

\begin{lstlisting}[caption={}]
> oui:=proc(a,b,c)
  local temp;
  temp:=a;
  temp:=temp+1;
  RETURN(temp);
  end:
\end{lstlisting}


\end{DANGER}


\subsection{Structures itératives}

\begin{exemple}
Soit  deux entiers  naturels $n$  et $N$  tels que  $n \leqslant  N$. On
voudrait calculer la somme des entiers de $n$ à $N$.
\end{exemple}

Les  notations mathématiques peuvent  ici nous  guider. En  effet, cette
somme $S(n,N)$ s'écrit:

$$S(n,N)=\displaystyle\sum_{k=n}^{k=N}k=n+(n+1)+(n+2)+\cdots+(N-1)+N$$

\subsubsection{Tant que}


\begin{algo}
\FUNC{somme}{%
\pfarg{n,N}{entier}}{entier}
\COMMENT{On doit avoir n<=N. On  obtient la somme des entiers successifs
  de n à N compris}
\COMMENT{Nous  allons créer  une variable  provisoire qui  contiendra la
  somme en construction ainsi que l'entier provisoire qui va être itéré.}
\VAR
\DECLVAR{Stemp,ktemp}
\ENDVAR
\BEGIN
\STATE{Stemp\recoit{} 0}
\STATE{ktemp \recoit{} n}
\COMMENT{On choisit  d'initialiser la somme à 0  et l'indice d'itération
  à n.}
\WHILE{ktemp <= N}
\COMMENT{On entre dans la boucle jusqu'à la valeur N comprise}
\STATE{Stemp\recoit{} Stemp+ktemp}
\COMMENT{À l'état initial on commence donc par rajouter n à 0}
\STATE{ktemp\recoit{} ktemp+1}
\COMMENT{ktemp est incrémenté après la somme.}
\COMMENT{  À  la dernière  étape,
  ktemp vaut N,}
\COMMENT{ est rajouté à Stemp puis ktemp reçoit N+1}
\COMMENT{ et  on sort
  donc de la boucle.}
\COMMENT{ Dans l'état final  on a donc la  somme des entiers
  de n à N.}
\ENDWHILE
\RETURN{Stemp}
\END
\end{algo}


Avec Maple:



\begin{lstlisting}[caption={}]
> Somme:=proc(n,N)
   local Stemp,ktemp;
   Stemp:=0;
   ktemp:=n;

   while ktemp<=N do
     Stemp:=Stemp+ktemp;
     ktemp:=ktemp+1;
   od;

   RETURN(Stemp)
  end:
\end{lstlisting}



Vérifions que notre algorithme fait bien ce qu'on attend de lui.


La   propriété   $\PR(\verb+ktemp+)$:   \og   \verb+Stemp+$=S(n,$\verb+ktemp+)   et
\verb+ktemp+$\leqslant N$\fg{} est l'\textit{invariant de boucle}.

Au départ,  on a bien $\PR(n)$: \verb+Stemp+$=S(n,n)=n$  et $n \leqslant
N$.

À  chaque fin  d'occurrence de  la boucle,  cette propriété  reste vraie
ainsi qu'en sortie.



\begin{recherche}
On modifie légèrement l'ordre des instructions de cet algorithme:

\begin{algo}
\STATE{ktemp\recoit{} ktemp+1}
\STATE{Stemp\recoit{} Stemp+ktemp}
\end{algo}

Y a-t-il d'autres choses à modifier?
\end{recherche}



\subsubsection{Pour}

En anglais, c'est \og for\fg{}:


\begin{lstlisting}
for var from debut to fin by increment do 
    instructions;
od; 
\end{lstlisting}


Par exemple~:

\begin{lstlisting}
> Somme:=proc(n::posint)
  local S,k;
  S:=0;
   for k from 1 to n by 1 do
     S:=S+k; 
   od;
 RETURN(S)
 end:
\end{lstlisting}



On peut arrêter  l'itération dès qu'une condition a  été réalisée (et se
passer du \verb+to+)~:


\begin{lstlisting}
> Somme:=proc(n::posint)
  local P,k;
  S:=0;
   for k from 1 while P<=n do
     S:=S+k; 
   od;
 RETURN(S)
 end:
\end{lstlisting}

Expliquez....


\section{Au plus près de l'humain: la programmation récursive}


\subsection{Qu'est-ce que c'est?}

La récursion  est un  mécanisme puissant permettant,  comme l'itération,
d'exprimer la répétition des opérations, mais de manière plus concise et
en ayant la  possibilité de se passer d'affectation  et ainsi éviter les
problèmes de surveillance de l'état de la mémoire.

Il  ne se  limite pas  au  cas des  suites numériques  définies par  une
relation de récurrence. 

Par  exemple, définissons un  caractère comme  un élément  de l'ensemble
constitué des 26 lettres de l'alphabet latin:
$\Bigl\{\; '{\rm a}',\ '{\rm b}',\cdots,\ '{\rm z}'\; \Bigr\}$

On peut donner une définition récursive d'un mot:

\textit{Un mot est soit un caractère, soit un caractère suivi d'un mot.}


Sur Maple, reprenons un exemple du paragraphe précédent~:

\begin{lstlisting}
> Somme_r:=proc(n::posint)
    if n=1 then 1
    else Somme_r(n-1)+n;
    fi;
end:
\end{lstlisting}

Il  faut connaître  un  cas simple  et  un moyen  de  simplifier un  cas
compliqué...

On   peut   obtenir   les   résultats   intermédiaires   avec   l'option
\verb+remember+ et en demandant le quatrième opérande de la procédure~:

\begin{lstlisting}
> Somme_r:=proc(n::posint)
    option remember;
    if n=1 then 1
    else Somme_r(n-1)+n;
    fi;
end:
\end{lstlisting}

Puis~:

\begin{lstlisting}
Somme_r(9);
op(4,eval(Somme_r));
\end{lstlisting}


Cette option est malgré tout plus intéressante dans le cas de récursions
multiples~:~les calculs  intermédiaires étant  stockés, ils n'ont  pas à
être recalculés et cela gagne du temps.

Par  exemple,  pour la  suite  de  Fibonacci $u_{n+2}=u_{n+1}+u_n$  avec
$u_0=u_1=1$~:

\begin{lstlisting}
> fibo:=proc(n::nonnegint)
   option remember;
   if n=0 then RETURN(1);
     elif n=1 then RETURN(1);
     else RETURN(fibo(n-1)+fibo(n-2));
   fi
  end:
\end{lstlisting}


Sans l'option \texttt{remember}, \verb+fibo(30)+  prend pas mal de temps
mais est instantané quand on l'ajoute~:~à ne pas oublier...




\vfill

\eject


\modeexercice % entre en mode exercice
\section{EXERCICES}


\begin{listeexercices}


%\subsection{Structures conditionnelles}

\begin{exercice}[Valeur absolue]
  Écrivez un algorithme qui renvoie la valeur absolue d'un réel $x$.
\end{exercice}


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

Déterminez un algorithme  qui renvoie la solution de  ce système si elle
est unique.
\end{exercice}



  \begin{exercice}[Années bissextiles]
Une année bissextile est une année dont le millésime, supérieur à 1583, est divisible par
4, sauf les limites de siècles qui ne sont pas multiples de 400.

Ainsi   \numprint{2000}  et   \numprint{2008}   sont  bissextiles   mais
\numprint{2100} et \numprint{2011} ne le sont pas.

Définissez alors un  algorithme qui reconnaît si un  millésime est celui
d'une   année   bissextile.   Vous   pourrez  utiliser   la   fonction
 \verb+irem+ qui donne le reste de la division euclidienne.
  \end{exercice}



  \begin{exercice}[Conversion]
    Déterminez un algorithme qui reçoit  un nombre entier de secondes et qui
renvoie quatre  entiers correspondant à sa conversion  en jours, heures,
minutes et  secondes. On pourra  utiliser une fonction \og  quo\fg{} qui
renvoie le quotient entier de la division de deux entiers.
  \end{exercice}


  \begin{exercice}[Partie entière]
Donnez un algorithme impératif renvoyant la partie entière d'un réel $x$.
  \end{exercice}


  \begin{exercice}[Division euclidienne]
Déterminer  un algorithme   qui renvoie  le  quotient de  deux
entiers naturels non nuls $a$ et $b$.

Déterminer un  algorithme qui  renvoie le
reste entier de $a$ et $b$.
  \end{exercice}

  \begin{exercice}[Intégration numérique]
Déterminez  un algorithme  qui donne  une valeur  approchée de
$\displaystyle\int_{t=a}^{t=b}f(t)\;\mathrm{d}t$   pour   une   certaine
fonction  $f$ continue  sur un  intervalle  $[a;b]$ par  la méthode  des
rectangles puis celle des trapèzes.
  \end{exercice}




  \begin{exercice}[Suite]
On veut étudier la suite  de terme général $u_n=\frac{1}{n^2}$ ainsi que
la suite $v_n=\displaystyle\sum_{k=1}^{n}u_k$, avec
$n\in\bbn^*$.



Proposez un algorithme qui affiche $u_n$ et $v_n$ pour une valeur de $n$ donnée.
  \end{exercice}


  \begin{exercice}[Maximum]
    
Donner des procédures impératives  et récursives donnant le maximum d'une
liste de nombres réels quelconques.

  \end{exercice}


  \begin{exercice}[Tête et queue]
    
La tête d'une liste est son premier élément. La queue d'une liste est la
sous-liste  créée  en  lui  coupant  la  tête.  Donnez  deux  procédures
\verb+tete(liste)+ et \verb+queue(liste)+.


\end{exercice}


  \begin{exercice}[test de croissance]


Donner des procédures impératives et récursives déterminant si une liste
donnée est croissante. On pourra éventuellement utiliser \verb+tete+ et \verb+queue+.
  \end{exercice}





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

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

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

Donner  une procédure  récursive puis  une procédure  impérative prenant
comme arguments une fonction $f$, les bornes de l'intervalle d'étude $a$
 et $b$ et une précision de calcul $eps$.

  \end{exercice}



  \begin{exercice}[Héron]
    
\textsc{Héron} d'Alexandrie a trouvé une méthode permettant de déterminer
une approximation de la racine  carrée d'un nombre positif vingt siècles
avant l'apparition des ordinateurs.

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... Donnez  une version récursive
puis impérative prenant en argument  le nombre dont on cherche la racine
carrée, une première approximation $x_0$ et une précision \verb+eps+.


  \end{exercice}



  \begin{exercice}[Décimales de e]
    

Posons $e_n=1+\frac{1}{1!}+\frac{1}{2!}+\cdots+\frac{1}{n!}$

Alors on a aussi
$$e_n=1+1+\frac{1}{2}\left(1+\frac{1}{3}\left(1+\frac{1}{4}\left(\cdots \left(\frac{1}{n-1}\left(1+\frac{1}{n}\right)\right)\right)\right)\right)$$


Un           exercice           classique           montre           que
$e-e_n \ie \frac{n+2}{n+1}\frac{1}{(n+1)!}$.

Ainsi,   pour  $n=167$,   on   obtiendra  $300$   bonnes  décimales   au
moins~:~trouvez-les~!

  \end{exercice}

\begin{exercice}[Somme de chiffres]


Proposez un algorithme qui prend en  argument un entier écrit en base 10
et qui calcule la 
somme des chiffres composant cet entier.  

\emph{On pourra utiliser la fonction} \verb+irem+ 
    
 

\end{exercice}


\end{listeexercices}
\modenormal % restaure les définitions de sections, sous-sections, etc;




%%% Local Variables: 
%%% TeX-master: "PolyMaple10"
%%% End: 
