\documentclass[11pt,a4paper]{../../template/template_cours}
\usepackage{enumitem} % pour reprendre des énums en cours

\title{Contrôle}
\author{Adrian Amaglio}
\def\thesequence{Les algorithmes}
\def\thelevel{NSI première}

\begin{document}
\maketitle
Tout moyen de communication, appareil électronique ou document est interdit. Toute triche engendrera des points en moins sur la note finale.\\

\subsection*{Moyenne d’un tableau}
\terseQ{Écrivez un algorithme permettant de calculer la moyenne des éléments d’un tableau.}\\
\terseQ{Quelle est sa complexité dans le meilleur cas, le pire cas et en moyenne ?}

\subsection*{Tri par sélection}
\terseQ{Expliquez le principe du tri par sélection.}\\
\terseQ{Écrivez un algorithme de tri par sélection.}\\
\terseQ{Quelle est sa complexité dans le meilleur cas, le pire cas et en moyenne ?}\\
\terseQ{Montrez la correction de cet algorithme de tri.}
Vous utiliserez comme invariant le fait que la partie gauche du tableau est toujours triée.
Si votre boucle principale va de i à N (la taille du tableau), l’invariante sera la proposition suivante :\\
Le tableau est trié entre les indices 0 et i.

\subsection*{Recherche dichotomique}
\terseQ{Expliquez le principe de la recherche dichotomique.}\\
\terseQ{Écrivez l’algorithme de recherche dichotomique.}\\
\terseQ{Montrer la terminaison de cet algorithme.}
Vous pourrez utiliser le variant suivant :  borne\_max - borne\_min décroit strictement à chaque tour de boucle.

\subsection*{K plus proches voisins}
\terseQ{Expliquez le principe de l’algorithme des K plus proches voisins.}\\
\terseQ{Écrivez l’algorithme des K plus proches voisins.}
Vous pouvez rester vague dans les instructions comme vu en cours.\\
\terseQ{Quelle est sa complexité dans le meilleur, le pire cas et en moyenne ?}

\subsection*{Rendu de monnaie}
\terseQ{Expliquez le principe de l’algorithme du rendu de monnaie.}\\
\terseQ{Écrivez cet algorithme.}\\
\terseQ{\textit{Bonus} Lorsqu’on l’implémente ne python quel problème rencontre-t-on si l’on souhaite rendre 2,85 € ?}

\end{document}