\documentclass[a4paper,11pt]{amsart}
\usepackage{kb}
\usepackage{kbexo}
\course{MAO -- Maîtrise / K. Belabas}
\def\ANNEE{2003--2004}
\university{Université Paris 11 (Orsay)}
\num{0}
\def\theexoname{}

\def\bprog{\begingroup\tt\obeylines\obeyspaces}
\def\eprog{\endgroup}

\begin{document}
\mapletitle{Introduction à \Maple}
\medskip

{\tiny\leftskip = 4cm\noindent
Wir waren kompliziert genug, die Maschine zu bauen, und wir sind zu primitiv,
uns von ihr bedienen zu lassen.

%Nous avons été assez compliqués pour construire la machine, et nous sommes
%trop primitifs pour nous faire servir par elle.

\begin{flushright}
Karl Kraus, \emph{Untergang der Welt durch schwartze Magie}, 1922.
\end{flushright}}

{\tiny\leftskip = 4cm\noindent
Any sufficiently advanced technology is indistinguishable from magic. 

\begin{flushright}
Artur C. Clarke, \emph{«Technology and the Future». Report on Planet Three},
1972.
%  Benford's Corollary to Clarke's Third Law: 
%  Any technology distinguishable from magic is insufficiently advanced.
% Gregory Benford. Foundation's Fear. 1997
\end{flushright}}
\section{Introduction}

\noindent Le but de ce module est d'apprendre à utiliser un système de
calcul formel pour
\begin{enumerate}
\item consolider des connaissances acquises en les voyant sous un jour
pratique.
\item expérimenter pour «découvrir» des conjectures et les tester, avant de
tenter de les démontrer.
\end{enumerate}
On s'initiera au passage aux méthodes du calcul formel et à l'analyse de
leurs performances. Les thèmes étudiés seront essentiellement arithmétiques.
C'est en partie un cours d'algorithmique, puisqu'on ne s'interdira pas de
comparer diverses solutions, ni d'en rechercher qui soient efficaces. Ce
n'est pas un cours de programmation.

Nous utiliserons le système \Maple\footnote{pour 'érable' ou MA{\sl
thematical} PLE{\sl asure}.}, qui est un logiciel de calcul formel puissant
et d'utilisation simple, créé en 1981 par l'université de Waterloo (Canada).
Il est recommandé de connaître l'anglais pour s'en servir, en particulier
pour utiliser l'aide en ligne. Ce système n'est pas parfait: il est assez
lent et il arrive fréquemment qu'un bug fasse perdre une session (sauver
fréquemment!); il est inadapté au calcul numérique ou à la réalisation de
grands projets. Mais il offre un langage relativement intuitif permettant de
manipuler facilement les objets mathématiques courants, d'écrire et de tester
rapidement de petits programmes.

\medskip Nous allons survoler divers aspects de \Maple dans les pages
suivantes. Le but étant de poser (et résoudre) des problèmes mathématiques le
plus vite possible, on sera bref. Pour chaque nouvelle commande ou objet
introduit au cours des TP, il est conseillé de
\begin{enumerate}
\item lire l'aide en ligne.
\item l'essayer sur des exemples, y compris pathologiques, en essayant de
prévoir les résultats et de comprendre les réactions du système.
\end{enumerate}
Il existe des heures de libre-service. Il faudra en profiter pour se
familiariser aussi vite que possible avec \Maple et sa syntaxe, ainsi
qu'avec les notions introduites en TP~: MAO = Mathématiques \emph{Assistées}
(pas Asservies ou Aseptisées) par l'Ordinateur.

\nocite{Map1}
\nocite{Map2}
\nocite{Map3}
\nocite{Map4}
\bibliographystyle{kbplain}
\bibliography{kb}

\section{Prise en main}
\noindent \emph{Ces notes sont valables pour Maple V et plus, interface
graphique \kbd{xmaple}.}

\misctitle{Prompt} l'invite \kbd{>} (prompt) indique que \Maple attend
une instruction.

\misctitle{Exécuter} chaque instruction se termine par \kbd{;} (résultat
affiché) ou \kbd{:} (résultat non affiché). Un retour chariot (\kbd{Enter})
déclenche l'exécution du groupe de commande en cours, \emph{i.e.}~le texte
délimité par un $\big[$ à gauche. Appuyer simultanément sur \kbd{Shift} et
\kbd{Enter} passe à la ligne \emph{sans} valider la commande: pratique pour
écrire lisiblement. Il est conseillé d'utiliser un maximum de \kbd{:} pour
cacher les résultats intermédiaires.

\misctitle{Charger un fichier} on peut lire/sauver un fichier au format
\kbd{mws} (Maple WorkSheet) à partir du menu \kbd{File}. Si vous avez
l'habitude d'un bon éditeur de textes (Emacs, Vim), il est préférable
d'écrire tout programme un peu long sous forme de fichier \emph{texte}, puis
de les charger dans la session via \kbd{read} : le comportement est le même
que si les commandes avaient été rentrées au clavier.

\misctitle{Aide en ligne}   \kbd{?}\var{commande}

\misctitle{Redémarrer} \kbd{restart;} (réinitialise tous les objets~:
variables globales, fonctions).

\misctitle{Commentaire} \kbd{\#}\emph{blabla} (le reste de la ligne est ignoré)

\misctitle{Dernière expression évaluée} \kbd{\%} (l'avant dernière est
\kbd{\%\%}, etc.).

\section{Constantes et opérations élémentaires}
Une suite de chiffres comportant un \kbd{.}~(remplace la virgule française)
ou un \kbd{e} (notation scientifique) est un réel. Si l'expression contient
\kbd{I} (pas~\kbd{i}!), c'est un complexe. Voir \kbd{type} et \kbd{whattype}.

Les opérations arithmétiques élémentaires sont notées \kbd{+}, \kbd{-},
\kbd{*}, \kbd{/}, \kbd{\pow} (exponentiation). Les fonctions mathématiques
usuelles (exp/log, trigonométrie) s'obtiennent de façon évidente.
Sauf valeurs particulières, si l'argument a des composantes exactes, le
résultat sera formel, parfois identique à la formule tapée \hint{comparer
\kbd{sin(1)}, \kbd{sin(1.)}, \kbd{sin(Pi/3)}, \kbd{sin(Pi*1.3)}}. La commande
\kbd{eval} et ses variantes, en particulier \kbd{evalf} pour une évaluation
numérique, forcent \Maple à évaluer plus on moins complètement une
expression. Essayer 
\bprog
> Pi; evalf(Pi); evalf(Pi, 100); 
\eprog
\noindent On peut modifier la variable globale \kbd{Digits} \hint{par
exemple, \kbd{Digits := 50}}, pour fixer la précision courante des calculs à
venir. En général, préférer \kbd{evalf}.

\misctitle{Exemples} À quoi correspond \kbd{pi}~? Obtenir une valeur
approchée de $\sin(\pi/13)$. Que se passe-t'il pour $\sin(\pi/12)$ ?

\section{Variables}

\misctitle{Affectation} \kbd{x := 1} pour `$x$ reçoit $1$'. La valeur à
droite du signe \kbd{:=} est associée au nom (identificateur) situé à gauche.

\misctitle{Quelques pièges}

\pt Ne pas oublier le '\kbd{\string:}', sinon (\kbd{x = 1}) c'est un test
d'égalité.

\pt Une variable libre $x$ (non affectée) est un symbole~: sa valeur est un
``pointeur sur elle-même'' (sera remplacée par le contenu de $x$ quand on
lui en donnera un). Essayer~:

\bprog
> restart;
> P := x\pow2; x := 2;
> P; Q := x - 1;
\eprog\noindent
Sauf exception\footnote{s'il n'est pas de type tableau ou dérivé (matrices,
etc.) ou fonction, auquel cas seul son nom apparaîtrait. Essayer
\kbd{A:=array([1,2,3]); A;}}, un résultat est complètement évalué: toutes les
variables sont remplacées par leurs valeurs. Utiliser \kbd{eval(P, 1)} pour
une évaluation au premier rang au lieu d'une évaluation complète (permet de
déterminer que \kbd{P = x\pow2}, même après l'affectation de~\kbd{x}).
\kbd{eval(A)} force au contraire une évaluation totale (par exemple pour le
tableau de la note).\smallskip

\misctitle{Empêcher l'évaluation}

Une expression entre \emph{guillemets simples} (accent aigu) retarde
l'évaluation~: \kbd{'x'} est évalué en la variable formelle \kbd{x}, même
si on a déjà donné une valeur à \kbd{x}. \hint{Expliquer l'effet de \kbd{x
:= 1; x := 'x';}. Vérifier avec \kbd{whattype}}. Prévoir le résultat de 
\bprog
> restart; x := y; y := x; x\pow2;
> restart; x := y; y := 'x'; x\pow2;
\eprog\noindent
De façon générale, pour éviter les problèmes: ne pas utiliser les mêmes
identificateurs pour les variables libres (polynômes, etc.) et les autres
(paramètres, compteurs, etc.); pour évaluer une expressions en un point,
utiliser \kbd{subs} plutôt qu'une affectation.

Une expression entre ``\emph{guillemets graves}'' (\kbd{`x`}) est un nom
(chaîne de caractères). Exemple: \kbd{print(`Bonjour`);}.
Pour concaténer objets ou noms, on peut utiliser '\kbd{.}'~:
\bprog
> x := 2;
> print(`la valeur de x est `~.~x)
\eprog
\noindent Pour des expressions plus complexes il est plus agréable
d'utiliser \kbd{printf}.

\section{Quelques objets utiles}
\misctitle{Intervalles} \kbd{1..100}

\misctitle{Séquences (\var{sequence})} suite (ordonnée) d'objets séparés
par des virgules. La séquence vide est appelée \kbd{NULL} (utile pour
initialiser), qui n'est pas affichée par \Maple. On peut concaténer deux
séquences en les séparant par une virgule: \kbd{s1, s2}.

Un constructeur utile~: \kbd{seq(f(i), i = 1..100)}. L'opérateur \kbd{\$} a une
fonction analogue, en moins lisible: \kbd{f(i) \$i=1..100}, mais
il peut aussi servir a initialiser une liste d'objets identiques
\kbd{1 \$ 100} ou un intervalle d'entiers \kbd{\$ 1..100}. \kbd{seq}
protège ses arguments contre une évaluation prématurée, \kbd{\$} non. En
conséquence son emploi est plus délicat, donc non recommandé; comparer
\bprog
> i:=10;
> seq(a[i], i = 1..10);
> a[i] \$ i = 1..10;
> a[i] \$ 'i' = 1..10;
> 'a[i]' \$ 'i' = 1..10;
\eprog

\misctitle{Listes (\var{list})} de la forme \kbd{[ \var{sequence} ]}. C'est
une séquence vue comme un seul objet, et non comme un agrégat. Réfléchir à la
différence entre \kbd{f(\var{liste})} et \kbd{f(\var{séquence})}.

\misctitle{Ensembles (\var{set})} de la forme \kbd{\{ \var{sequence} \}}.
C'est une liste non ordonnée (en particulier les éléments en double sont
éliminés). Attention~: l'ordre des éléments d'un ensemble est arbitraire et
peut changer d'une session sur l'autre.

\misctitle{Tableau (\var{array})} à une ou plusieurs dimensions. Par exemple,
\kbd{A := array(1..20, 1..10)} est une matrice $20\times 10$. Plus général
qu'une liste, et traité plus efficacement par le système. Il n'est pas facile
de déterminer automatiquement les dimensions d'un tableau \hint{\kbd{op(2,
eval(A))} renvoie la séquence d'intervalles qui les constitue}. On 
convertit un tableau en liste via \kbd{convert(A, list)}; l'opération inverse
est \kbd{convert(L, array)} ou plus simplement \kbd{array(L)}.

\misctitle{Tableau associatif (\var{hash table})} plus général qu'un tableau:
à des indices de type quelconque on associe une valeur. Par exemple, si on
assigne \kbd{A[1] := 0} sans définir \kbd{A} au préalable, ce dernier est de
type table. La \emph{remember table} d'une fonction est une table (voir plus
bas).\smallskip

Pour extraire le $i$-ème élément d'une séquence/liste/ensemble/tableau~:
\kbd{L[i]}, $i\geq 1$. On peut changer les valeurs d'une liste/tableau:
\kbd{L[i] := 1}. Si une liste a plus de 100 éléments \Maple refuse
\hint{essayer}~: utiliser un \kbd{array} ou lieu d'une liste.

Le nombre d'éléments d'une séquence/liste/ensemble est donné par
\kbd{nops(L)}, et les éléments eux-mêmes, c'est-à-dire la séquence
sous-jacente, par \kbd{op(L)}. On peut utiliser \kbd{op(i, L)} au lieu de
\kbd{L[i]}. On peut extraire des intervalles~: \kbd{op(3..10, L)}. De façon
générale, on peut compter ou extraire les sous-objets de n'importe quelle
expression. Par exemple 

\pt \kbd{a := (x\pow2 + 4*y\pow2 = (x+1)*(5*x-2)); }  \hint{analyser les
composants de \kbd{a} (et de ses sous-composants) avec \kbd{op}.
Extraire le 5 à l'aide d'une suite de \kbd{op}}

\pt Le quatrième ``élément'' d'une fonction contient la table des valeurs
spéciales (\var{remember table}). Essayer \kbd{op(4, eval(sin))}. Pour la
plupart des fonctions, \Maple va remplir cette table de lui-même à chaque
fois qu'un nouveau résultat est calculé. Il est possible de remplir cette
table soi-même ! \hint{essayer \kbd{sin(1)\string:=0;}~\emph{(!!!)}}.

Si vous voulez savoir comment sont définies les fonctions \Maple, vous pouvez
les «afficher»: \kbd{ interface(verboseproc = 3); print(sin); }

\section{Fonctions}
\noindent On peut évaluer une expression contenant des variables libres avec
\kbd{subs}.
\bprog
> f := x + log(y) + exp(z);
> subs(\{x=1, y=2\}, f);
\eprog
\noindent Mais \kbd{f} ne définit pas une fonction au sens habituel du terme
\hint{essayer \kbd{f(1)}}. Pour ce faire, on utilise la notation \kbd{->}~:
\kbd{ F := (x, y) -> x + log(y) + exp(z); } associe au nom \kbd{F} une
fonction de deux variables (dont la valeur est une expression formelle en
\kbd{z}) \hint{que se passe-t-il si on oublie les parenthèse autour de
\kbd{x,y} ?}. Un raccourci si l'expression existe déjà~: \kbd{F := unapply(f,
x,y);}

\noindent Dans l'autre sens, si \kbd{x} et \kbd{y} sont libres, \kbd{F(x, y)}
est une expression formelle égale à \kbd{f}.

\misctitle{Procédures} pour des fonctions plus compliquées, utiliser
\kbd{proc}:
\bprog
> f := proc(\var{séquence d'arguments})
    local \var{séquence de variable locales};
    global \var{séquence de variable globales};
    options \var{séquence d'options};
    \dots;
  end;
\eprog\noindent
\kbd{local}, \kbd{global} et \kbd{options} sont facultatives. La valeur de
retour est la dernière expression évaluée. Utiliser \kbd{RETURN($x$)} pour
quitter la procédure prématurément. Il est interdit de modifier un argument
d'une fonction dans le corps de celle-ci: \bprog
> f := proc(x); ... x := x+1; ...; end;
Illegal use of a formal parameter. \eprog

\misctitle{Remarque} les cas particuliers se codent facilement grâce à la
\emph{remember table}. Au lieu de
\bprog
f := proc(x)
  if (x = 0)  then
    RETURN (1);
  fi;
  sin(x) / x;
end;
\eprog
\noindent on peut écrire
\bprog
f := proc(x)
  sin(x) / x;
end;
f(0) := 1;
\eprog
\noindent ou plus simplement (\kbd{proc} ne se justifie pas ici)
\bprog
f := x -> sin(x) / x;
f(0) := 1;
\eprog
\noindent \hint{Que se passe-t-il si on intervertit ces deux lignes ?}.

\noindent Si \kbd{options} contient \kbd{remember}, la \emph{remember
table} se remplit toute seule à chaque appel de la fonction (utile pour
certaines fonctions récursives, mais gourmand en mémoire).

\misctitle{Graphe} pour un graphe simple~: \kbd{plot(f(x), x=-1..1)}. Comme
\kbd{plot} ne protège pas ses arguments, il peut être nécessaire d'empêcher
l'évaluation prématurée de la fonction~: expliquer
\bprog
> pi := x -> nops(select(isprime, [\$1..x]))
> plot(pi(x), x=1..100);
> plot('pi(x)', x=1..100);
\eprog

\section{Programmation}

\misctitle{Branchement conditionnel}

\bprog
  if $\var{test}_1$ then       \# {\rm si \dots alors}
    \dots
  elif $\var{test}_2$ then     \# {\rm sinon si \dots alors}
    \dots
  elif $\var{test}_n$ then
    \dots
  else               \# {\rm sinon}
    \dots
  fi;
\eprog\noindent
Un \var{test} est une expression à valeur ``booléenne'' (\kbd{true},
\kbd{false} ou \kbd{FAIL}). Seule la valeur \kbd{true} enclenche le
branchement. Le \kbd{else} et les \kbd{elif} (= else if) sont optionnels.
On peut utiliser les opérateurs logique \kbd{and}, \kbd{or}, ou \kbd{not}
pour les tests. Exemple de tests~:

$\bullet$ \kbd{x <= 0}\quad (pour $\leq$)

$\bullet$ \kbd{x <> y}\quad ou bien\quad \kbd{not(x = y)}\quad
(pour $\kbd{x} \neq \kbd{y}$)

$\bullet$ \kbd{(type(p, integer) and isprime(p))}.

\misctitle{Boucles}

\noindent Avec compteur numérique
\bprog
for $i$ from \var{min} to \var{max} by \var{pas}   \# $i = \var{min},%
\var{min}+\var{pas}$, \dots
do
  \dots
od;
\eprog\noindent
\kbd{from} et \kbd{by} sont optionnels (\var{min} et \var{pas} valent 1 par
défaut). \var{min}, \var{max}, \var{pas} ne sont pas nécessairement
entiers, ni \var{max} égale à la valeur finale de l'indice\footnote{en supposant
$\var{min} \leq \var{max}$, la valeur maximale atteinte est 
$\var{min} + \var{pas}
  \left\lfloor \dfrac{\var{max}-\var{min}}{\var{pas}}\right\rfloor$,
où $\lfloor x \rfloor$ désigne la partie entière. Il est agréable
de pouvoir utiliser \var{max} sans se poser de question!}. Si $\var{min} >
\var{max}$, la boucle n'est pas exécutée. Attention, \Maple n'est pas
capable d'évaluer tout seul une borne formelle, il faut parfois l'aider avec
\kbd{evalf}:
\bprog
> for i to exp(1) do print(i) od;
Error, final value in for loop must be numeric or character
> for i to evalf(exp(1)) do print(i) od;
                      1
                      2
\eprog

\noindent Avec liste (ou ensemble) de valeurs
\bprog
for $i$ in \var{liste}\q \# $i = \var{liste}[1], \var{liste}[2]\dots$
do
  \dots
od;
\eprog

\noindent Avec condition booléenne
\bprog
while \var{test}  \#\q {\rm tant que \var{test} vaut \kbd{true}}
do
  \dots
od;
\eprog \noindent
Pour toutes ces boucles, \kbd{RETURN} peut être utilisé pour interrompre
l'exécution et quitter la procédure courante. Plus finement:

\kbd{break} sort de la boucle en court (continue l'exécution juste après le
\kbd{od}).

\kbd{next} commence la prochaine itération (continue l'exécution juste
avant le \kbd{od}). 


\section{Quelques astuces en vrac}

\misctitle{Substitutions} \kbd{subs} (syntaxique, $\kbd{x} \rightarrow
\kbd{y}$, ne marche que sur un sous-objet qu'on peut obtenir avec une suite
d'instructions \kbd{op}), \kbd{algsubs} (algébrique, $\kbd{P(x)}\rightarrow y$,
\kbd{P} polynôme). Un exemple~:
\bprog
> a := \{x=1, y=1\}, \{x\pow2=2, y=3\};
> subs(a[1], [x,y]);
> subs(a[2], [x,y]);
> algsubs(a[2], [x\pow3,y]);
\eprog

\misctitle{Convertir une liste en somme / produit}
\bprog
> convert( [x, y, z], `+` );
> convert( [x, y, z], `*` );
> convert( seq(i, i = 1..200), `*` );
\eprog\noindent
\hint{voir aussi \kbd{mul(i, i = 1..200)} ou \kbd{add}}

\misctitle{Quelques commandes utiles} \kbd{map} (appliquer une fonction a
tous les opérandes d'un objet, i.e.~les éléments d'une liste),
\kbd{collect}/\kbd{expand} (pour réorganiser des polynômes),
\kbd{simplify}.

Pour la partie entière et ses variantes, voir \kbd{floor}, \kbd{ceil},
\kbd{round}.

\misctitle{Assignations multiples}
L'opérateur \kbd{\string:=} permet les assignations multiples pour deux
séquences de noms et de valeurs de même cardinal:
\bprog
> x,y := 1,2;
\eprog
\noindent Les assignations multiples sont simultanées: 
\bprog
> x,y := y,x;
\eprog
\noindent échange les valeurs de \kbd{x} et \kbd{y} et a le même effet que le
traditionnel
\bprog
tmp := x; x := y; y := tmp;
\eprog

\misctitle{Pour corriger un programme} \kbd{printlevel := 100;} (par
exemple), fait afficher toutes les étapes de l'exécution d'une fonction
(appels de sous-fonctions, affectations de variables). Plus
\kbd{printlevel} est élevé, plus il y a d'informations (5 = squelette,
1000 = tout). Plus généralement, voir \kbd{trace} et l'aide en ligne de
\kbd{debugger}.

\end{document}
