\documentstyle[a4,french]{article}
\newtheorem{theoreme}{Théorème}
\def\thesubsection{\arabic{subsection}.}
%% 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
\textheight 230mm
\advance\textheight by \topskip
 
\begin{document}
\centerline{\Huge Corrigé du partiel}
\section*{Première partie}
\subsection{Déclaration du tableau}
\begin{tabbing}
\hspace*{3em} \= \hspace*{3em} \= \hspace*{3em} \= \kill
VAR TAB : ARRAY[1..Nmax,1..2] OF INTEGER; \\
\end{tabbing}

\subsection{Lecture des données}
\begin{tabbing}
\hspace*{3em} \= \hspace*{3em} \= \hspace*{3em} \= \kill
PROGRAM Lecture; \\
VAR
\> TAB : ARRAY[1..Nmax,1..2] OF INTEGER; \\
\> n : INTEGER; \\
\> i : INTEGER; \\
BEGIN \\
\> FOR i := 1 TO n DO \\
\> BEGIN \\
\> \> WriteLn('Entrez u',i,', deux entiers séparés par un espace'); \\
\> \> ReadLn(TAB[i,1],TAB[i,2]); \\
\> END \\
END. \\
\end{tabbing}

\subsection{Calcul de S}
\begin{tabbing}
\hspace*{3em} \= \hspace*{3em} \= \hspace*{3em} \= \kill
PROGRAM Calcule\_S; \\
VAR
\> TAB : ARRAY[1..Nmax,1..2] OF INTEGER; \\
\> n : INTEGER; \\
\> S, i : INTEGER; \\
BEGIN \\
\> \{ On suppose que TAB est déjà rempli avec les valeurs de u \} \\
\> S := 0; \{ Initialisation \} \\
\> FOR i := 1 TO n DO \\
\> \> S := S + i*TAB[i,1]; \\
\> WriteLn('S vaut ',S); \\
END. \\
\end{tabbing}

\subsection{Calcul de S, fonction {\tt SOM1}}
\begin{tabbing}
\hspace*{3em} \= \hspace*{3em} \= \hspace*{3em} \= \kill
TYPE Suite = ARRAY[1..Nmax,1..2] OF INTEGER; \\
FUNCTION SOM1(n : INTEGER; TAB : Suite) : INTEGER; \\
VAR
\> S, i : INTEGER; \\
BEGIN \\
\> S := 0; \{ Initialisation \} \\
\> FOR i := 1 TO n DO \\
\> \> S := S + i*TAB[i,1]; \\
\> SOM1 := S; \\
END; \\
\end{tabbing}

\subsection{fonction {\tt SOM2}}
\begin{tabbing}
\hspace*{3em} \= \hspace*{3em} \= \hspace*{3em} \= \kill
FUNCTION SOM2(n : INTEGER; TAB : Suite) : INTEGER; \\
VAR
\> S, i : INTEGER; \\
BEGIN \\
\> S := 0; \{ Initialisation \} \\
\> FOR i := 1 TO n DO \\
\> \> S := S + (n+1-i)*TAB[i,2]; \\
\> SOM2 := S; \\
END; \\
\end{tabbing}

\subsection{fonction {\tt HOM}}
\begin{tabbing}
\hspace*{3em} \= \hspace*{3em} \= \hspace*{3em} \= \kill
FUNCTION HOM(n : INTEGER; TAB : Suite) : INTEGER; \\
BEGIN \\
\> HOM := SOM1(n,TAB) - SOM2(n,TAB); \\
END; \\
\end{tabbing}

\section*{Seconde partie}
\subsection{fonction {\tt DERN}}
\begin{tabbing}
\hspace*{3em} \= \hspace*{3em} \= \hspace*{3em} \= \kill
TYPE Permutation = ARRAY[1..n] OF INTEGER; \\
FUNCTION DERN(sigma : Permutation) : BOOLEAN; \\
VAR
\> i : INTEGER; \\
BEGIN \\
\> DERN := True; \\
\> FOR i := 1 TO n DO \\
\> \> IF sigma[i] <>{} n+1-i THEN \\
\> \> \> DERN := False; \\
END; \\
\end{tabbing}

\subsection{Toutes les permutation}
\begin{tabbing}
\hspace*{3em} \= \hspace*{3em} \= \hspace*{3em} \= \kill
PROGRAM Permutations; \\
TYPE Permutation = ARRAY[1..n] OF INTEGER; \\
VAR
\> sigma : Permutation; \\
\> i : INTEGER; \\
\> Fini : BOOLEAN; \\
BEGIN \\
\> \{ Initialisation : première permutation \} \\
\> FOR i := 1 TO n DO \\
\> \> sigma[i] := i; \\
\> Fini := False; \\
\> \{ Écriture de toutes les permutations \} \\
\> WHILE NOT Fini DO \\
\> BEGIN \\
\> \> \{ Écriture de sigma \} \\
\> \> FOR i := 1 TO n DO \\
\> \> \> Write(sigma[i],' '); \\
\> \> WriteLn; \\
\> \> \{ Suivant \} \\
\> \> IF DERN(sigma) THEN \\
\> \> \> Fini := True \\
\> \> ELSE \\
\> \> \> sigma := SUIVANT(sigma); \\
\> END \\
END. \\
\end{tabbing}

\subsection{fonction {\tt THETA}}
Si $u = (u_i) = (u_1,...,u_n)$, on a
$\sigma(u) = (u_{\sigma(i)}) = (u_{\sigma(1)},...,u_{\sigma(n)})$.
\begin{tabbing}
\hspace*{3em} \= \hspace*{3em} \= \hspace*{3em} \= \kill
FUNCTION THETA(n : INTEGER; u : Suite; sigma : Permutation) : INTEGER; \\
VAR
\> TAB : Suite; \\
\> i : INTEGER; \\
BEGIN \\
\> \{ Calcul de TAB \} \\
\> FOR i := 1 TO n DO \\
\> \> TAB[i] := u[sigma[i]]; \\
\> \{ Calcul de H(TAB) \} \\
\> THETA := HOM(n,TAB); \\
END; \\
\end{tabbing}

\subsection{Maximum des THETA}
\begin{tabbing}
\hspace*{3em} \= \hspace*{3em} \= \hspace*{3em} \= \kill
FUNCTION MaxTheta(n : INTEGER; u : Suite) : INTEGER; \\
VAR
\> MaxActuel : INTEGER; \\
\> sigma : Permutation; \\
\> TH, i : INTEGER; \\
BEGIN \\
\> \{ Initialisation : première permutation \} \\
\> FOR i := 1 TO n DO \\
\> \> sigma[i] := i; \\
\> MaxActuel := THETA(n,u,sigma); \\
\> \{ Test pour toutes les permutations \} \\
\> REPEAT \\
\> \> sigma := SUIVANT(sigma); \\
\> \> TH := THETA(n,u,sigma); \\
\> \> IF TH >{} MaxActuel THEN \\
\> \> \> MaxActuel := TH; \\
\> UNTIL DERN(sigma); \\
\> MaxTheta := MaxActuel; \\
END; \\
\end{tabbing}

\subsection{Maximum des THETA, permutation où il est atteint}
\begin{tabbing}
\hspace*{3em} \= \hspace*{3em} \= \hspace*{3em} \= \kill
PROCEDURE MaxPermutation(n : INTEGER; u : Suite, VAR MaxSigma : Permutation); \\
VAR
\> MaxActuel : INTEGER; \\
\> sigma : Permutation; \\
\> TH, i : INTEGER; \\
BEGIN \\
\> \{ Initialisation : première permutation \} \\
\> FOR i := 1 TO n DO \\
\> \> sigma[i] := i; \\
\> MaxActuel := THETA(n,u,sigma); \\
\> MaxSigma := sigma; \\
\> \{ Test pour toutes les permutations \} \\
\> REPEAT \\
\> \> sigma := SUIVANT(sigma); \\
\> \> TH := THETA(n,u,sigma); \\
\> \> IF TH >{} MaxActuel THEN \\
\> \> BEGIN \\
\> \> \> MaxActuel := TH; \\
\> \> \> MaxSigma := sigma; \\
\> \> END; \\
\> UNTIL DERN(sigma); \\
END; \\
\end{tabbing}

\subsection{Nombre d'appels à {\tt HOM}}
Il y a $n!$ permutations différentes. Pour chaque permutation, {\tt THETA}
est appelée une fois. Cette fonction appelle {\tt HOM} une fois. Cela nous
fait donc $n!$ appels à {\tt HOM}.

\end{document}
