\def\NomChapitre{2}
\def\Type{DL}
\LeTitre{\NomChapitre}{Pour le Jeudi 9 janvier}

Les fichiers Python sont à envoyer à l'adresse \url{dconduche@gmail.com}
%(avec votre nom dedans, en commentaire).

Les programmes doivent être {\bf abondamment commenté}, pour expliquer ce que
l'on fait. Les noms des fonctions et des variables doivent être
raisonnablement explicite.

\begin{exo}[Test : la liste est-elle triée ?]
On se donne en entrée une liste \texttt{L} contenant des entiers.

\begin{enumerate}
\item À partir des opérations sur les listes vues en cours, écrire une
  fonction qui teste si une liste \texttt{L} d'entiers est triée du plus petit
  (en \texttt{L[0]}) au plus grand. La fonction répondra par un booléen.
\item Tester sur divers exemples (on pourra mettre en commentaire (\texttt{\#})
  les différentes listes essayée, ainsi que le résultat de la fonction).
\item Faire une preuve de la terminaison de la boucle (i.e., que la fonction
  va bien s'arrêter).
\item (bonus) Prouver la correction de la fonction à l'aide d'un invariant.
\end{enumerate}
\end{exo}


\begin{exo}[Nombres premiers]
\begin{enumerate}
\item \'Ecrire une fonction \texttt{EstPremier} qui teste si un entier $n$ est
  un nombre premier.
\item \'Ecrire une fonction \texttt{ListePremiers1} qui prend en argument un entier $n$ et rends la
  liste des nombres premier plus petits que $n$, à l'aide de la fonction
  précédente.
\item \'Ecrire une fonction \texttt{ListePremiers2} qui fait la même chose,
  mais en partant de la liste \texttt{L=range(n)} et en \og{} rayant \fg{} les
  multiples de $2$, puis les multiples de $3$, etc...
\item (bonus) Comparer la complexité des fonctions \texttt{ListePremiers1} et \texttt{ListePremiers2}.
\end{enumerate}
\end{exo}

\begin{rappel}
Un nombre premier est un nombre entier positif divisible uniquement par $1$ et
par lui-même. 
\end{rappel}

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