\documentclass[12pt,a4paper,twoside]{article}
\usepackage[latin1]{inputenc}
\usepackage{amsmath,amssymb}
\usepackage{aafrench}
\input{c:/tex/aaa/oi/exs/exs} %inclue ifthen

\usepackage{alltt}                          %DECOMMENTER CETTE LIGNE
\input{c:/ocaml/lib/mlgraph.lib/mlg/mlg}    %DECOMMENTER CETTE LIGNE
\input{c:/ocaml/lib/mlgraph.lib/mlg/mlpic}  %DECOMMENTER CETTE LIGNE
\input{c:/ocaml/lib/mlgraph.lib/mlg/mlpicf} %DECOMMENTER CETTE LIGNE
%\newcommand{\FigMlPic}[3]{\mbox{}\\FIGURE\\} %COMMENTER CETTE LIGNE
%\newcommand{\MlPic}[1]{\mbox{}\\FIGURE\\}    %COMMENTER CETTE LIGNE

\renewcommand{\u}{\mathbf{u}}
\renewcommand{\v}{\mathbf{v}}
\newcommand{\w}{\mathbf{w}}
\newcommand{\x}{\mathbf{x}}
\newcommand{\ps}[2]{\langle#1|#2\rangle}

\begin{document}
 \setlength{\parindent}{7mm}
 \setlength{\abovedisplayskip}{0.5mm}
 \setlength{\belowdisplayskip}{0.5mm}\begin{parenthese}
 \thispagestyle{empty}
  \sujet{Réduction de réseau (ENS 2002)%
   \footnote{%
    D'après \texttt{http://pauillac.inria.fr/\~{}quercia/papers/lll.tgz}}}
   \texte
    $E=\R^2$ est muni de sa structure euclidienne canonique.
    Un \emph{réseau} est une partie de $E$ de la forme
    $G=\{\lambda\u+\mu\v\,|\,\lambda,\mu\in\Z\}$ où
    $(\u,\v)$ est une base de $E$;
    $(\u,\v)$ est alors appelée une \emph{base} du réseau  $G$.
   \question
    Analyser l'algorithme suivant:\nf 
    \numeroter%
    \begin{algorithm}
     {\soitrec} \emph{Gauss}$(\u,\v)=$\ls
     (* $(\u,\v)$ est une base d'un réseau $G$
     telle que $\|\u\|\geq\|\v\|$ *)\ii\ii\ls
       $q$ {\affecte} $\left\lfloor\ps{\v}{\u}/\|\v\|^2+1/2\right\rfloor$\ls
       $\w$  {\affecte} $\u-q\v$\ls
       {\si} $\|\w\|\geq\|\v\|$ {\alors}\ii\ii\ls 
           {\renvoyer} $(\w,\v)$\di\di\ls
       {\sinon}\ii\ii\ls 
           {\renvoyer} \emph{Gauss}$(\v,\w)$ 
    \end{algorithm}
   \question 
    Etudier le problème de trouver un point $x'$ de $G$ le plus proche
    d'un point donné $x$ de $E$. 
\paragraph*{Corrigé}\setcounter{questions}{0}\mbox{}
 \cquestion
  En ligne 3, $q$ est l'entier (ou l'un des deux entiers) le plus proche
  de $a=\ps{\v}{\u}/\|\v\|^2$. Le vecteur $\u-a\v$ est la projection de $\u$
  sur $\v^\perp$; c'est donc le vecteur de norme minimum de
  la droite $\u+\text{Vect}(\v)$.
  Le vecteur
  $\w$ défini ligne 4 est un vecteur de norme minimum de
  $G\cap(\u+\text{Vect}(\v))$;
  en effet, si $\lambda\in\Z$, la quantité
  $\|\u-\lambda\v\|^2=\v^2(\lambda-a)^2+\u^2-a^2\v^2$ est minimum pour
  $\lambda=q$.\par Sur la figure suivante, $\u$, $\v$ et $\w$ sont appelés
  respectivement $\u_1$, $\u_2$ et $\u_3$.
  \begin{center}\MlPic{cl007-01}\end{center}
  \mbox{\hspace{\parindent}}%
  L'algorithme termine. En effet, lors de l'appel récursif
  \emph{Gauss}$(\v,\w)$, la norme de $\w$ est $<$ à celle du vecteur
  $\v$ de l'appel principal \emph{Gauss}$(\u,\v)$; or
  tous les vecteurs considérés appartiennent au groupe discret $G$ de sorte
  qu'un ensemble borné ne contient qu'un nombre fini de points de $G$.
  On vérifie que $G$ est discret en notant que si $(\u,\v)$ en est une base,
  alors $\|\ \|\geq kN$ où $N$ est la norme euclidienne associée
  au produit scalaire sur $E$ pour lequel $(\u,\v)$ est une base
  orthonormale, donc, pour tout $\x=\lambda\u+\mu\v\in G\setminus\{0\}$,
  $\|\x\|\geq kN(\x)=k\sqrt{\lambda^2+\mu^2}\geq k$.
  \par
  Par exemple, sur la figure, \emph{Gauss}$(\u_1,\u_2)$
  donne lieu à l'appel récursif \emph{Gauss}$(\u_2,\u_3)$ qui renvoie
  $(\u_4,\u_3)$.
  \evp
  Le couple $(\u,\v)$ retourné par l'algorithme est une base de $G$ et
  vérifie
  $$\|\u\|\geq\|\v\|\text{ et }\|\u\|=\min_{\lambda\in\Z}\|\u-\lambda\v\|
   \text{.}$$
  On en déduit que $|2\ps{\u}{\v}|\leq\v^2$ puis que, pour tout
  $\x=\lambda\u+\mu\v\in G\setminus\{0\}$,
  $\x^2=\lambda^2\u^2+\mu^2\v^2+2\lambda\mu\ps{\u}{\v}\geq
   (\lambda^2+\mu^2-|\lambda\mu|)\v^2\geq\v^2$.\par
  $\v$ est donc un vecteur non nul de $G$ de norme minimum.
 \cquestion
  On utilise la base $(\u,\v)$ trouvée par l'algorithme de Gauss.
  Soit $\u^*$ le projeté de $\u$ sur $\v^\perp$.
  Le rectangle $R$ centré à l'origine et construit sur
  $(\u^*,\v)$ pave l'espace $E$ selon $G$; {\cad} que tout point $x$ de $E$
  appartient à un translaté de $R$ centré en un point de $G$.
  On en déduit la majoration
  ${\displaystyle d^2(\x,G)\leq\frac{1}{4}\left({\u^*}^2+\v^2\right)}$.
  \begin{center}\MlPic{cl007-02}\end{center}
  Or ${\displaystyle\u^*=\u-\frac{\ps{\u}{\v}}{\v^2}\v}$; donc, à l'aide de
  $\|\u\|\geq\|\v\|$ et
  $|2\ps{\u}{\v}|\leq\v^2$, il vient
  ${\displaystyle{\u^*}^2=\u^2-\frac{\ps{\u}{\v}^2}{\v^2}\geq
   \v^2-\frac{\v^2}{4}=\frac{3}{4}\v^2}$, puis
  ${\displaystyle d^2(\x,G)\leq\frac{7}{12}{u^*}^2}$.
  \evp
  Soit maintenant $\x=\lambda\u+\mu\v\in E$; $\lambda,\mu\in\R$.
  Si $\x'=\lambda'\u+\mu'\v$ est un point de $G$ le plus proche de $\x$,
  alors $\lambda$ et $\lambda'$ sont aussi les composantes de $\x$ et
  $\x'$ sur $\u^*$ dans
  la base orthogonale $(\u^*,\v)$. Donc
  ${\displaystyle(\lambda-\lambda')^2{\u^*}^2\leq\|\x-\x'\|^2
   \leq\frac{7}{12}{u^*}^2}$, puis
  ${\displaystyle|\lambda-\lambda'|<0,8}$.
  Ou bien cette condition détermine $\lambda'$, ou bien
  les seules valeurs possibles de $\lambda'$ sont
  $\left\lfloor\lambda\right\rfloor$ ou $\left\lceil\lambda\right\rceil$.
  Pour chacune de ces valeurs de $\lambda'$, il est alors facile de
  calculer le $\mu'$ optimal.
\end{parenthese}\end{document}
