info.tex

%% fichier 'info.tex'
%% macros pour décrire des programmes. ref pp 420--422 du TeXbook
%%
 
 
\def \|{\leavevmode \hbox{\tt \char`\|}} % vertical line
\def \°{\leavevmode \hbox{\tt \char23}} % ???
 
\newskip \ttglue \ttglue = .5em plus.25em minus .15em
 
\outer \def \begindisplay{%
   \obeylines
   \startdisplay}
{\obeylines \gdef \startdisplay#1
   {\catcode`\^^M=5%
   $$#1 %
      \halign\bgroup %
         \indent ## \hfil && \qquad ## \hfil \cr}}
\outer \def \enddisplay{%
   \crcr
   \egroup
   $$}
 
\chardef \other = 12
 
\def \ttverbatim{%
   \begingroup
      \catcode`\\=\other
      \catcode`\{=\other
      \catcode`\}=\other
      \catcode`\$=\other
      \catcode`\&=\other
      \catcode`\#=\other
      \catcode`\%=\other
      \catcode`\~=\other
      \catcode`\_=\other
      \catcode`\^=\other
      \obeyspaces
      \obeylines %
      \tt}
 
{\obeyspaces \gdef {\ }} % \obeyspaces now gives \ , not \space
 
\outer \def \begintt{%
   $$
   \let \par = \endgraf
   \ttverbatim %
   \parskip = 0pt %
   \catcode`\|=0 %
   \rightskip = -5pc %
   \ttfinish}
 
{\catcode`\| = 0 \catcode`\\=\other % | is temporary escape character
|obeylines %
|gdef |ttfinish#1^^M#2\endtt{%
   #1 %
   |vbox{#2} %
   |endgroup %
   $$}}
 
% ci-dessous une astuce remarquable pour permettre d'écrire '|something|' et
% d'avoir la phrase 'something' en ttverbatim.
 
\catcode`\@ = 11
 
\def \specialbar{%
   \ifmmode 
      \def \next{|}
   \else
      \let \next = \speci@lbar
   \fi
   \next}
\catcode`\|=\active \let| = \specialbar
{\obeylines \gdef \speci@lbar{%
   \ttverbatim %
   \spaceskip = \ttglue %
   \let^^M=\  %
   \let|=\endgroup}}
 
 
\catcode`\@ = 12
 
\endinput
 
% ======================= test ==================
 
|Sous plusieurs aspects, le problème du calcul du plus grand diviseur 
commun (pgcd) de deux polynômes est l'un des problèmes fondamentaux en ce 
qui concerne les manipulations algébriques. Les premiers systèmes de 
calcul formel (comme ALPAK ou PM) disposaient de routines pour les 
opérations sur les polynômes. La suite logique fût de développer des 
routines pour les manipulations de fractions rationnelles et donc des 
algorithmes de calcul de pgcd pour pouvoir simplifier au mieux ces 
fractions. 
|
 
ceci dit, en maths il vient $|x| \geq 0$
 
\begindisplay
   Pourquoi pas~?
\enddisplay
L'algorithme d'Euclide, connu depuis des siècles, est facilement compréhensible 
et implémentable. Cependant, cet algorithme pose un gros problème de 
taille des expressions intermédiaires, notamment pour les polynômes de 
$\zset [X_1, \ldots, X_n]$ puisqu'il faut travailler dans 
$(\zset[X_1, \ldots, X_{n-1}])[X_n]$. On retrouve ce même problème 
avec celui des algorithmes PRS (Polynomial Remainder Sequence) qui 
utilise une pseudo division et qui travaille uniquement dans l'anneau de 
base des coefficients sans passer par son corps des fractions 
(cf Naudin-Quitté ou Geddes, Czapor et Labahn). Plusieurs algorithmes ont 
été développés dans les 25 dernières années pour calculer le pgcd de deux 
polynômes~: l'algorithme de Collins (1967), la méthode des sous-résultants 
améliorée par Brown (1978), l'algorithme modulaire de Brown (1971), 
l'algorithme EZ-GCD de Moses \& Yun (1973) et l'algorithme probabiliste 
HEUGCD de Char, Geddes \& Gonnet (1989).
 
L'algorithme modulaire de Brown (MGCD) utilise le théorème chinois pour 
reconstituer le pgcd après un certain nombre d'évaluations--réductions 
des polynômes de départ et il est l'un des plus efficaces dans le cas des 
polynômes à une variable et à coefficients entiers. Pour les polynômes à 
plusieurs variables qui ne sont pas complètement denses, les techniques 
$p$-adiques pour la reconstruction du résultat peuvent être utilisées 
pour éviter le grand nombre d'images nécessaires à l'algorithme MGCD. 
Une des caractéristiques de cette technique $p$-adique est qu'elle ne 
nécessite qu'une seule évaluation en chacune des variables (sauf une) et 
une seule réduction pour pouvoir reconstruire le résultat. 
L'algorithme EZ-GCD développé par Moses \& Yun utilise cette technique et 
est particulièrement efficace pour les polynômes creux à plusieurs variables 
dont le coefficient dominant par rapport à l'une des variables est entier.
 
\bye