\documentstyle[a4,french]{article}
%% Pour un tabbing en choisissant la fonte
\makeatletter
\def\@startline{\footnotesize\tt\global\@curtabmar\@nxttabmar
   \global\@curtab\@curtabmar\global\setbox\@curline\hbox{}\@startfield\strut}
\makeatother
%% Mise en page
\topmargin 0pt
\headheight 0pt
\headsep 0pt
\marginparwidth 0mm
\oddsidemargin  0mm
\evensidemargin 0mm
\textwidth 170mm
\textheight 245mm
\advance\textheight by \topskip

\begin{document}

\section{Quelques applications directes du cours}
\subsection{Syntaxe générale du pascal}
\begin{enumerate}
\item Se rappeler la syntaxe de {\tt IF ... THEN ... ELSE}.
\item Se rappeler la syntaxe de {\tt WHILE ... DO ...} et
{\tt REPEAT ... UNTIL ...}.
\item Quand peut-on déclarer une variable, une fonction ou procédure ?
Qu'est-ce qu'un identificateur, quelle est la portée d'un identificateur ?
\end{enumerate}
\subsection{Déclaration de types}
\begin{enumerate}
\item Déclarer un type RECORD qui représente les nombres complexes.
\item Déclarer un type qui puisse représenter une date.
\item Deux façons de déclarer un type pour stocker les polynômes de
degré inférieur à 20.
\item Déclarer un type pour stocker les polynômes à coefficients complexes.
\end{enumerate}
\subsection{Passage par valeur ou par référence}
Rappel~: si lors de la déclaration d'une fonction ou procédure le nom
de l'argument est précédé du mot clé VAR, cet argument passe par référence
ce qui signifie qu'il est modifié par la procédure. Sinon, seule la valeur
de la variable passe à la procédure et la variable est inchangée après la
fin de la procédure.

Dans le programme ci-dessous, que faut-il passer par valeur ou par référence ?
\begin{tabbing}
\hspace*{3em} \= \hspace*{3em} \= \hspace*{3em} \= \kill
PROGRAM TraitementDeTableau;                            \\
CONST                                                   \\
\> Max = 20;                                            \\
TYPE                                                    \\
\> Indice = 1..Max;                                     \\
\> Tableau = ARRAY[Indice] OF BOOLEAN;                  \\
PROCEDURE Entre (t : Tableau);                          \\
VAR i : Indice;                                         \\
BEGIN                                                   \\
\> FOR i := 1 TO Max DO                                 \\
\> BEGIN                                                \\
\> \> Write('Entre l''élément ',i,' : ');               \\
\> \> ReadLn(t[i]);                                     \\
\> END;                                                 \\
END;                                                    \\
PROCEDURE Affiche (t : Tableau);                        \\
VAR i : Indice;                                         \\
BEGIN                                                   \\
\> FOR i := 1 TO Max DO                                 \\
\> \> WriteLn('Élément ',i,' : ',t[i]);                 \\
END;                                                    \\
PROCEDURE Échange (t : Tableau; pos1, pos2 : Indice);   \\
VAR Temporaire : BOOLEAN;                               \\
BEGIN                                                   \\
\> Temporaire := t[pos1];                               \\
\> t[pos1] := t[pos2];                                  \\
\> t[pos2] := Temporaire;                               \\
END;                                                    \\
VAR                                                     \\
\> UnTableau : Tableau;                                 \\
\> A, B : Indice;                                       \\
BEGIN                                                   \\
\> Entre(UnTableau);                                    \\
\> WriteLn('On échange'); ReadLn(A); ReadLn(B);         \\
\> Échange(UnTableau,A,B);                              \\
\> Affiche(UnTableau);                                  \\
END.                                                    \\
\end{tabbing}

\section{Exercices simples}
\subsection{Arithmétique}
\begin{enumerate}
\item Écrire un programme qui demande à l'utilisateur un nombre entier $n$ et
affiche les entiers de 1 à $n$.
\item Écrire un programme qui demande à l'utilisateur un nombre entier et
dit si ce nombre est pair.
\item Écrire un programme qui demande à l'utilisateur un nombre entier et
affiche tous les diviseurs de ce nombre.
\item Écrire un programme qui demande à l'utilisateur deux nombres entiers et
calcule leur PGCD. Attention, il existe plusieurs méthodes envisageables,
l'une d'entre elles effectue beaucoup moins d'opérations que les autres.
\end{enumerate}
\subsection{Gestion d'un tableau d'entiers}
\begin{enumerate}
\item Étant donné un tableau d'entiers $t_{initial}$, écrire une procédure
qui fabrique un tableau de même longueur $t_{final}$, où chaque élément
$t_{final}[n]$ est la somme $\sum_{k\leq n}t_{initial}[k]$ des $n$
premiers éléments de $t_{initial}$.
\item Étant donné un tableau d'entiers $t_{initial}$ et un entier $N$,
écrire une procédure qui donne le plus petit élément de $t_{initial}$
qui soit strictement plus grand que $N$.
\item Utiliser la réponse à la question précédente pour écrire une procédure
qui, étant donné un tableau d'entiers tous différents $t_{initial}$ fabrique
un tableau $t_{final}$ qui contienne les mêmes éléments que $t_{initial}$,
en ordre croissant. Cet algorithme de tri s'appelle {\bf tri par sélection}.
Réfléchir à ce qui se passe si $t_{initial}$ contient deux fois le même
nombre.
\end{enumerate}

\section{Problème~: tri par insertion}
\subsection{Présentation du problème}
On a une liste d'éléments, en ordre quelconque. On sait faire un test
qui, entre deux éléments, précise lequel est le plus petit (au sens large).
On veut trier cette liste en ordre croissant.

\subsection{Remarque initiale~: insertion}
Si on a trié toute la liste sauf le dernier élément, la seule opération
qu'il reste à faire est de savoir où placer cet élément dans la liste triée.

{\bf Exemple~:} Nous voulons trier {\tt 3 5 1 3 6 3 4}. Lorsque nous
avons trié les six premiers nombres, nous avons {\tt 1 3 3 3 5 6} et
il nous reste à insérer {\tt 4} entre {\tt 3} et {\tt 5}.

\subsection{Programmation du tri par insertion}
Puisqu'on va faire de nombreuses insertions, il est conseillé d'utiliser
une liste chaînée (avec des pointeurs) pour travailler avec la liste triée.
Il est quand même possible de représenter la liste triée avec un tableau.

On va faire un programme qui va demander les nombres un par un à l'utilisateur
et va afficher à chaque étape la liste triée.

{\bf Première étape~:} écrire une procédure qui prend en entrée une liste triée
et un nombre $N$, et qui se place après le dernier nombre plus petit que $N$.

{\bf Seconde étape~:} écrire une procédure qui prend en entrée une liste triée
et un nombre $N$, et modifie la liste pour y insérer $N$ à la bonne place.

{\bf Dernière étape~:} écrire le programme complet, qui utilise la procédure
ci-dessus.
\end{document}
