\documentclass{tpcaml}

\title{DL option informatique}

\begin{document}

\maketitle

\bigskip
\soustitre{Exercice 1 : recherches dans une liste d'entiers}
On considère une liste d'entiers \texttt{l=[n1;\dots,np]}. On souhaite
rechercher des éléments particuliers de cette liste.
\begin{enumerate}
\item Ecrire deux fonctions renvoyant le minimum (resp. le maximum) de
  la liste $l$.
\item On recherche simultanément le minimum et le maximum de la liste
  $l$.
  \begin{enumerate}
  \item Trouver un algorithme renvoyant le minimum et le maximum d'une
    liste d'entiers en réalisant au plus $2n-2$ comparaisons.
  \item On adopte la stratégie suivante : on traite les éléments par
    paires : on commence par les comparer entre eux, puis on compare
    le plus petit au minimum et le plus grand au maximum.

    Ecrire une fonction implémentant cet algorithme.

    Calculer le nombre de comparaisons effectuées. Peut-on faire mieux ?
  \end{enumerate}
\item Ecrire une fonction recherchant le deuxième plus petit élément.
\item On recherche ici le $i$ème \emph{rang statistique} de la liste
  $l$, c'est-à-dire l'élément $x\in l$ qui est plus grand que $i-1$
  autres éléments de $l$ exactement. Pour cela, on utilise la statégie
  <<diviser pour régner>> suivante, inspirée de l'algorithme de tri
  rapide (\emph{quick sort}) :
  \begin{itemize}
  \item On partitionne la liste $l$ en deux sous-liste $l_1$ et $l_2$
    de sorte que tous les éléments de $l_1$ soient inférieurs à tous
    les éléments de $l_2$.
  \item Compter le nombre $k$ d'éléments de la liste $l_1$. Si ce
    nombre est inférieur à $i$, on cherchera le $i-k$ème rang
    statistique de $l_2$, sinon on cherchera le $i$ème rang
    statistique de $l_1$.
  \end{itemize}
  \begin{enumerate}
  \item Ecrire une fonction \texttt{partition} réalisant la
    partition. On utilisera un pivot (par exemple le premier élément
    de la liste), on rangera dans les deux listes les éléments moins
    grands (respectivement plus grand) que le pivot.
  \item Ecrire la fonction \texttt{selection} renvoyant le $i$ème rang
    statistique d'une liste.
  \item Evaluer la complexité temporelle de \texttt{selection} dans le
    pire cas.
  \item On suppose que la fonction de partition découpe la liste $l$
    en deux listes dont la longueur est égale ($p$ est une puissance
    de $2$). Evaluer la complexité dans ce cas.
  \item Que se passe-t-il si la fonction de partition découpe la liste
    $l$ de longueur $p$ en deux listes de longueurs respectives $p/10$
    et $9p/10$ ?
  \end{enumerate}
\end{enumerate}

\bigskip
\soustitre{Exercice 2 : calculs en multiprécision}

Les opérations arithmétiques en multiprécision se réalisent de la
façon suivante. Soient $N>0$ et $b\ge2$ des entiers~; $b$ est la
\emph{base}, $N$ est le nombre de \emph{chiffre} dans cette base. Un
nombre décimal $u$ à $N$ chiffres après la virgule, tel que $-b<u<b$,
s'écrit de façon unique
$$u=\sum_{i=0}^{N} u_ib^{-i}$$
où $0\le u_i<b$ pour
$i\in\entint{1,N}$, et $0\le \abs{u_0}<b$. La suite $(u_0,\dots,u_N)$
est la \emph{représentation de $u$ en base $b$}, les $u_i$ en sont les
\emph{chiffres}. On écrira $u=(u_0,\dots,u_n)$. La représentation de
$0$ est $(0)$.

Les opérations arithmétiques sont à implémenter dans cette
représentation. Pour cet exercice, on prendra $b=1000$ et $N=10$ (ou
plus). Les nombres en multiprécision seront représentés par un tableau
d'entiers de taille $N+1$.
\begin{enumerate}
\item Ecrire une procédure pour l'addition des nombres en
  multiprécision.
\item Ecrire des procédures pour la soustraction de deux nombres.
  
  En déduire une procédure réalisant la comparaison de deux nombres.
\item Ecrire une procédure réalisant la multiplication de deux nombres
  en multiprécision. On pourra commencer par écrire une procédure
  réalisant le produit d'un chiffre par un nombre, et une autre
  réalisant la multiplication d'un nombre par $1/b$ (décalage).
\item On souhaite calculer un grand nombre de décimales de $\pi$ au
  moyen de la formule suivante, dûe à Machin :
  $$\frac{\pi}{4} = 4\Arctan\frac{1}{5}-\Arctan\frac{1}{239}$$

  On pose $$S_n(u) = \sum_{k=0}^n (-1)^k\frac{u^{2k+1}}{2k+1}
  \quad\text{et}\quad R_n(u) = \abs{\Arctan u - S_n(u)}$$
  \begin{enumerate}
  \item Montrer que $R_n(u) \le \frac{\abs{u}^{2n+3}}{2n+3}$.
  \item En déduire que pour avoir $p$ <<chiffres>> (en base $b$) de
    $\Arctan\frac{1}{x}$, où $x>1$ est un entier, il suffit de
    calculer $S_n(\frac{1}{x})$ avec $n>\frac{1}{2}(\frac{p\ln b}{\ln
      x}-3)$.
  \item Montrer que si $x<b$ et $2n+1<b$, $S_n(\frac{1}{x})$ peut
    être évalué par le schéma de Hörner, et que seules des
    multiplications ou divisions par des entiers $<b$ sont
    nécessaires.
  \item Ecrire une fonction qui prend en argument un entier $x>1$ et
    un entier $N$, et qui calcule $N$ chiffres en base $b$ de
    $\Arctan\frac{1}{x}$.
  \item Ecrire une fonction calculant $p$ chiffres (en base $10$,
    cette fois !) de $\pi$.
  \end{enumerate}
\end{enumerate}

\end{document}

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

