% classe du document
\documentclass[12pt]{article}

% mise en page
\usepackage[paper=a4paper, portrait=true, twoside=false, left=1cm,
top=1cm, nohead, nomarginpar, includefoot, centering=true]{geometry}

% changer "utf8" en "latin1" selon la configuration
%\usepackage[utf8]{inputenc}
\usepackage[applemac]{inputenc}
 \usepackage[frenchb]{babel}
%\frenchbsetup{og = ¬´, fg = ¬ª}
\DecimalMathComma

% fontes latin modern
\usepackage[T1]{fontenc}
\usepackage{lmodern}

\usepackage[french,boxruled,inoutnumbered]{algorithm2e}

% pas d'entête
% num\' ero de page centr\' e en pied de page
\usepackage{fancyhdr} \pagestyle{fancy} \fancyhead{} \fancyfoot{}
\lfoot{} \cfoot{\thepage} \rfoot{}
\renewcommand{\headrulewidth}{0pt}
\renewcommand{\footrulewidth}{0.4pt}

% paquet multicols pour la pr\' esentation de l'activit\' e
\usepackage{multicol}

% inclusion de graphiques
\usepackage{graphicx}

% nouvelle commande pour les titres : en gras
\newcommand{\titre}[1]{{\bf #1 :}}

% nouvel environnement pour les listes d'items : puce particuli\` ere
\usepackage{pifont}
\newenvironment{tickliste}{\renewcommand{\labelitemi}{\ding{51}}\begin{itemize}}{\end{itemize}}

\begin{document}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%% Cadre de pr\' esentation %%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% pas d'alin\' ea en d\' ebut de paragraphe
\setlength{\parindent}{0mm}
% \`a gauche : logo AMECI 
\begin{minipage}{2.5cm}
  \begin{flushleft}
    \includegraphics[width=2.5cm]{amecmi}
  \end{flushleft}
\end{minipage}
% au centre : titre de l'activit\' e
\begin{minipage}{14cm}
  \begin{center}
    {\bf \Huge Algorithmique : le tri à bulles}

    Fiche professeur
  \end{center}
\end{minipage}
% \`a droite : niveau
\begin{minipage}{2.5cm}
  \begin{flushright}
    {\Huge 2\ieme}
  \end{flushright}
\end{minipage}
% en-dessous, \`a droite : auteur
\begin{flushright}
  Auteur : Jean-Marc Duquesnoy et Raymond Moché
\end{flushright}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%% Cadre de renseignements %%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% si une rubrique ne comporte qu'un \' el\' ement,
% on peut se d\' ebarasser de la liste d'item
\titre{But de l'activit\' e} Activité d'initiation à l'algorithmique. Programmer et tester le tri à bulles permet d'aborder simplement les instructions d'affectation et les boucles \og pour\fg et \og si\ldots alors fin\fg. L'essentiel de cette activité se fait en langage naturel. Rappelons que des tris interviennent obligatoirement dans les calculs de médiane, quartiles, déciles et boîtes à moustaches.
\begin{multicols}{2}
  \titre{Comp\' etences engag\' ees}
  \begin{tickliste}
  \item Gestion des entrées et sorties.
  \item Instructions d'affectation.
  \item Boucle pour.
  \item Boucle si ... alors ... fin.
   \item Comprendre un algorithme en langage naturel.
  \item Tester un algorithme donné sur  \og Scilab pour les lyc\' ees \fg ou \og Xcas \fg.
  \item Comparer les vitesses d'ex\' ecution de divers algorithmes.
   \item Simulation d'entiers au hasard entre 2 bornes
  \item Simulation de réels au hasard sur un intervalle
  \end{tickliste}

  \titre{Pr\' e-requis}
   \begin{tickliste}
  \item La simulation de nombres au hasard a été rencontrée en 3\up{\`eme}.
  \end{tickliste}
  
  \titre{Mat\' eriels utilis\' es}
  \begin{tickliste}
  \item Salle informatique (de préférence) ou salle de classe
  \item Un vidéo-projecteur et un ordinateur muni de \og Scilab pour les lyc\' ees \fg ou \og Xcas\fg pour le professeur, si l'activité est faite en classe.
  \end{tickliste}

  \titre{Dur\' ee indicative} 2 heures

  \titre{Noms des logiciels utilis\' es} \og Scilab pour les lyc\' ees \fg ou \og Xcas\fg.

  \titre{Documents utiles \`a t\' el\' echarger}
  \begin{tickliste}
  \item \og Fiche Élève\fg.
  \item \og TriBulles.sci\fg  (fichier scilab).
  \item \og TriBullesXcas.xws\og  (fichier Xcas).
  
  \end{tickliste}
\end{multicols}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%% Corps de la fiche prof %%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\titre{D\' eroulement de la s\' eance}

Les 4 premières questions (sur 5) concernent d'élaboration de l'algorithme du \og tri à bulles\fg en langage naturel. Elles peuvent se faire en classe. Une bonne partie de ce travail consistera à comprendre l'algorithme, qui est décrit soigneusement (?). 
Il serait préférable que la 5\up{\`eme} question soit faite individuellement par les élèves devant un ordinateur. Mais on peut aussi imaginer que le professeur manipule lui-m\^eme et montre ses calculs \`a ses \' el\`eves \`a l'aide d'un vidéo-projecteur. Dans ce cas, il serait utile de leur  distribuer des photocopies de \og TriBulles.sci\fg ou de \og TriBullesXcas.xws\fg  suivant le cas. Ces algorithmes ex\' ecutables sont donn\' es parce que cette activit\' e est une activité d'initiation. Traduire l'algorithme {\bf 4} en un algorithme exécutable est un exercice plut\^ot difficile, surtout avec \og Xcas\fg qui demande un investissement plus important. Les élèves devront  enfin les tester dans divers cas. Ils constateront qu'utiliser des fonctions pr\' e-programm\' ees est beaucoup plus rapide. Il y a plusieurs raisons :\vspace{1mm}\\
- d'abord, on pourrait optimiser \og TriBulles.sci\fg ou \og TriBullesXcas.xws\fg  (par exemple, il est inutile de ré-éxaminer les couples qui sont dans leur position définitive). L'algorithme optimisé resterait médiocre (voir l'article \og Tri à bulles\fg de Wikipedia).\vspace{1mm}\\
- il y a des algorithmes dont la conception est meilleure ;\vspace{1mm}\\
- \og scilab\fg ou \og Xcas\fg  sont des langages interpr\' et\' es. Il y a des langages plus efficaces.

\titre{Solution, autres commentaires}

{\bf 1 -} l'algorithme 1 produit $b,\,b$\vspace{1mm}\\
{\bf 2 -} \fbox{
\begin{minipage}{1.5cm}
$c\;\leftarrow a$ ;
$a\;\leftarrow b$ ;
$b\;\leftarrow c$ ;
\end{minipage}
}\vspace{1mm}\\
{\bf 3 -} Il en faut 4 : c'est le cas le plus défavorable. Au contraire, pour ranger dans l'ordre croissant $1,\,2,\,3,\,4,\,5$, il n'y a rien à faire, mais l'algorithme imposera quand même 4 manipulations de base.\vspace{1mm}\\
{\bf 4 -} Il suffit d'ajouter l'instruction \og  Aoriginal=A;\fg juste après début et donc avant que ne commencent les transformations de $A$. Ensuite, remplacer \og Afficher $A$\fg par \og Afficher $Aoriginal,\,A$\fg.\vspace{1mm}\\
{\bf 5 -}  Voir les commentaires dans \og TriBulles.sci\fg ou \og TriBullesXcas.xws\fg. Les g\' en\' erateurs de nombres al\' eatoires sont indiqu\' es. \vspace{1mm}\\
Les élèves ont dû rencontrer des simulations de nombres au hasard en 3\up{\`eme} (fonctions ALEA ou\\ ALEA.ENTRE.BORNES du tableur Calc d'OOo). Ceci dit, le Calcul des probabilités intervient ici pour l'unique raison qu'il permet d'écrire instantanément de longues listes de nombres, dont la signification ne nous intéresse pas et qui servent à tester les algorithmes. On n'imagine pas saisir une liste de 100000 nombres à la main !\vspace{1mm}\\
Bien entendu, il est important de manipuler d'aussi longues listes pour convaincre les élèves que le calcul automatique est indispensable dans les applications.\vspace{1mm}\\
Les fonctions de tri \og trier\fg ou \og SortD\fg ordonnant dans l'ordre d\' ecroissant, il faut faire une petite astuce : comme 
$$x=1-(1-x),$$
en ordonnant dans l'ordre d\' ecroissant les valeurs de $1-x$, on récupère au premier membre les valeurs de $x$ rang\' ees dans l'ordre croissant.


\end{document}
