\documentclass{article} %\oddsidemargin 5 mm %\evensidemargin 5 mm %\textwidth 16cm \usepackage{graphicx} \usepackage[francais]{babel} \usepackage[T1]{fontenc} \usepackage{amsmath} \usepackage{amsfonts} \usepackage{latexsym} \usepackage{amssymb} \usepackage{times} \usepackage{ifpdf} \usepackage{makeidx} \ifpdf \usepackage[pdftex,colorlinks]{hyperref} \else \usepackage[ps2pdf,breaklinks=true,colorlinks=true,linkcolor=red,citecolor=green]{hyperref} \fi \newtheorem{rem}{Remarque} \newcommand{\R}{{\mathbb{R}}} \newcommand{\C}{{\mathbb{C}}} \newcommand{\Z}{{\mathbb{Z}}} \newcommand{\N}{{\mathbb{N}}} \newcommand{\faux}{$\square\;$} \newcommand{\vrai}{$\square\;$} %\newcommand{\vrai}{$\boxtimes\;$} \newcommand{\itemf}{\item\faux} \newcommand{\itemv}{\item\vrai} \newtheorem{exo}{Exercice}[section] \begin{document} \noindent UJF \hfill M1 Calcul formel / Agreg Option C \hfill 2011/12 \vspace{0.5cm} Il existe plusieurs logiciels de calcul formel, que l'on peut classer en deux grandes cat\'egories \begin{itemize} \item les commerciaux, dont les plus connus sont Maple et Mathematica, tous deux sont disponibles \`a l'\'epreuve de mod\'elisation de l'agr\'egation de maths. Maple est tr\'es r\'epandu dans l'enseignement en classes pr\'eparatoires et \`a l'Universit\'e en France. %la version 5.5 est install\'ee sur les PC de l'Institut Fourier. L'usage de ces logiciels sur votre ordinateur personnel n\'ecessite le paiement d'une licence, dont le prix peut varier d'une centaine d'euros pour des versions r\'eserv\'ees aux \'etudiants \`a 1000 euros ou plus sinon. \item les libres: certains sont g\'en\'eralistes comme Xcas, Axiom, Maxima, d'autres plus sp\'ecialis\'es comme Gap (groupes), Pari/Gp (th\'eorie des nombres), etc. La plupart sont disponibles \`a l'\'epreuve de mod\'elisation de l'agr\'egation de maths. L'usage de ces logiciels est bien sur gratuit. \end{itemize} Il est important d'au moins essayer un ou des logiciels libres de calcul formel. L'interface est parfois un peu moins intuitive, mais les performances dans certains domaines peuvent \^etre largement meilleures (par exemple test de primalit\'e ou factorisation d'entiers), ou les instructions plus faciles dans certains domaines (par exemple manipulation des corps finis), et il n'est jamais bon d'\^etre enti\`erement captif d'un logiciel commercial qui peut un jour cess\'e d'\^etre commercialis\'e (comme ce fut le cas des versions commerciales Macsyma de Maxima ou IBM Scratchpad d'Axiom) ou \^etre rachet\'e, comme Mupad par Matlab ou Maplesoft par la firme japonaise Cybernet Systems. Les sections 1 \`a 4 de ce document pr\'esentent Xcas, d\'evelopp\'e \`a l'Universit\'e de Grenoble I, qui propose un module de compatibilit\'e avec Maple, ce qui devrait faciliter la transition aux habitu\'es de Maple. %Bien entendu les candidats \`a l'agr\'egation %restent libres d'utiliser Xcas ou maple pendant la pr\'eparation \`a %l'option C. Les deux derni\`eres sections sont un TP de prise en main suivi par un TP sur les structures de donn\'ees et algorithmes fondementaux. \section{Premiers pas avec Xcas} Pour t\'el\'echarger Xcas, allez sur le site\\ \verb|http://www-fourier.ujf-grenoble.fr/~parisse/install_fr.html|\\ Pour traiter les exemples, il est conseill\'e d'ouvrir Xcas~: \begin{itemize} \item Sous Windows en installation locale, on clique sur l'icone \verb|xcasfr| du bureau. \item Sous Linux avec Gnome, on clique sur Xcas du menu Education. Sinon, ouvrir un terminal et taper \verb|xcas &|. \item sur Mac, cliquez sur Xcas dans le menu Applications du Finder. \end{itemize} Lors de la premi\`ere utilisation, choisissez {\tt Xcas} lorsqu'on vous demande de choisir une syntaxe (sauf si vous connaissez le langage Maple). Nous donnons ici seulement le minimum de l'interface \`a connaitre pour commencer \`a programmer. On consultera plutot le manuel D\'ebuter en calcul formel ou les autres manuels (menu Aide) pour apprendre \`a utiliser les fonctionnalit\'es de Xcas en calcul formel, g\'eom\'etrie, tableur, etc.. L'interface appara\^\i t comme suit au lancement de {\tt Xcas}. \vskip 2mm \centerline{ \includegraphics[width=\textwidth]{demarr1} } Vous pouvez la redimensionner. De haut en bas cette interface fait appara\^\i tre~: \begin{itemize} \item[$\bullet$] un barre de menu gris cliquable~: \verb@Fich@, \verb@Edit@, \verb@Cfg@, \verb@Aide@, \verb@CAS@, \verb@Tableur@, \verb@Graphe@, \verb@Geo@,\ldots \index{menus} \item[$\bullet$] un onglet indiquant le nom de la session, ou {\tt Unnamed} si la session n'a pas encore \'et\'e sauvegard\'ee, \item[$\bullet$] une zone de gestion de la session avec un bouton \verb|?| pour ouvrir l'index de l'aide un bouton \verb@Save@ pour sauvegarder la session, un bouton \verb@Config: exact real ...@ affichant la configuration et permettant de la modifier, un bouton \verb|STOP| permettant d'interrompre un calcul trop long, un bouton \verb|Kbd| pour faire apparaitre un clavier ressemblant \`a celui d'une calculatrice, qui peut faciliter vos saisies, et un bouton \verb|x| pour fermer la session \item[$\bullet$] une zone rectangulaire blanche num\'erot\'ee 1 (premi\`ere ligne de commande) dans laquelle vous pouvez taper votre premi\`ere commande (cliquez si n\'ecessaire pour faire apparaitre le curseur dans cette ligne de commande)~: \verb@1+1@, suivi de la touche "Entr\'ee" ("Enter" ou "Return" selon les claviers). Le r\'esultat appara\^it au-dessous, et une nouvelle ligne de commande s'ouvre, num\'erot\'ee 2. \end{itemize} Vous pouvez modifier l'aspect de l'interface et sauvegarder vos modifications pour les utilisations futures (menu \verb@Cfg@). \vskip 2mm Vous n'avez pour l'instant qu'\`a entrer des commandes dans les lignes de commandes successives. Si vous utilisez la version html de ce cours, vous pouvez copier-coller les commandes propos\'ees depuis votre navigateur. Chaque ligne de commande saisie est ex\'ecut\'ee par la touche "Entr\'ee". Essayez par exemple d'ex\'ecuter les commandes suivantes. \begin{verbatim} 1/3+1/4 sqrt(2)^5 solve(x+3=1,x) 50! \end{verbatim} Toutes les commandes sont gard\'ees en m\'emoire. Vous pouvez donc remonter dans l'historique de votre session pour modifier des commandes ant\'erieures. Essayez par exemple de changer les commandes pr\'ec\'edentes en~: \begin{verbatim} 1/3+3/4 sqrt(5)^2 solve(2*x+3=0) 500! \end{verbatim} Notez que \begin{itemize} \item pour effacer une ligne de commande, on clique dans le num\'ero de niveau \`a gauche de la ligne de commande, qui apparait alors en surbrillance. On appuie ensuite sur la touche d'effacement. On peut aussi d\'eplacer une ligne de commande avec la souris. \item Le menu \verb@Edit@ vous permet de pr\'eparer des sessions plus \'elabor\'ees qu'une simple succession de commandes. Vous pouvez cr\'eer des groupes de lignes de commandes (sections), ajouter des commentaires ou fusionner des niveaux en un seul niveau. \item Le menu \verb|Prg| permet d'ouvrir un niveau \'editeur de programmes et contient la plupart des instructions utiles pour programmer (cf. section \ref{sec:prog}). \end{itemize} \subsection{Aide en ligne} Les commandes de Xcas sont regroup\'ees par th\`emes dans les menus du bandeau gris sup\'erieur~: \verb|CAS|, \verb|Graphic|, \verb@Geo@, \verb@Cmds@, \verb@Phys@, \ldots~ Lorsqu'on s\'electionne une commande dans un menu, \begin{itemize} \item soit l'index de l'aide s'ouvre \`a la commande s\'electionn\'ee (par exemple pour les commandes du menu \verb|CAS|). Cliquez sur le bouton \verb|Details| pour afficher la page du manuel correspondant \`a la commande dans votre navigateur. \item soit une boite de dialogue s'ouvre vous permettant de sp\'ecifier les arguments de la commande (par exemple pour tracer une courbe depuis le menu \verb|Graphic|) \item soit la commande est recopi\'ee dans la ligne de commande. Pour connaitre la syntaxe de cette commande, appuyez sur le bouton \verb|?| en haut \`a gauche, ou faites afficher la zone de \verb@Messages@ (en utilisant le menu \verb@Cfg@,). Vous pouvez aussi configurer Xcas (menu \verb|Cfg| puis \verb|Configuration generale| puis cocher la case \verb@Aide HTML automatique@) pour que la page correspondante du manuel s'ouvre automatiquement dans votre navigateur. \end{itemize} Le menu \verb@Aide@ contient les diff\'erentes formes d'aide possible~: un guide de l'utilisateur (interface), un guide de r\'ef\'erence (\verb@Manuels->Calcul formel@, aide detaill\'ee sur chaque commande), un \verb@Index@ (liste des commandes class\'ees par ordre alphab\'etique avec une ligne d'entr\'ee permettant de se d\'eplacer facilement) et une recherche par mots clefs. \index{aide en ligne} \index{help@{\verb+help+}} Si vous connaissez d\'ej\`a le nom d'une commande et que vous d\'esirez v\'erifier sa syntaxe (par exemple \verb@factor@), vous pouvez saisir le d\'ebut du nom de commande (disons \verb|fact|) puis taper sur la touche de tabulation (situ\'ee \`a gauche de la touche A sur un clavier fran\c{c}ais) ou cliquer sur le bouton \verb|?| en haut \`a gauche. L'index des commandes appara\^\i t alors dans une fen\^etre, positionn\'e \`a la premi\`ere compl\'etion possible, avec une aide succinte sur chaque commande. Par exemple, vous voulez factoriser un polyn\^ome, vous supposez que le nom de commande commence par \verb|fact|, vous tapez donc \verb|fact| puis la touche de tabulation, vous s\'electionnez \`a la souris \verb|factor| (ou un des exemples) puis vous cliquez sur OK. Vous pouvez aussi saisir \verb@?factor@ pour avoir l'aide succinte en r\'eponse. Si le nom que vous avez saisi n'est pas reconnu, des commandes proches vous sont sugg\'er\'ees. \section{Les objets du calcul formel} % \subsection{Les nombres} % \index{nombre!exact} \index{nombre!approch\'e} Les nombres peuvent \^etre exacts ou approch\'es. Les nombres exacts sont les constantes pr\'ed\'efinies, les entiers, les fractions d'entiers et plus g\'en\'eralement toute expression ne contenant que des entiers et des constantes, comme \verb|sqrt(2)*e^(i*pi/3)|. Les nombres approch\'es sont not\'es avec la notation scientifique standard~: partie enti\`ere suivie du point de s\'eparation et partie fractionnaire (\'eventuellement suivie de \verb|e| et d'un exposant). Par exemple, \verb@2@ est un entier exact, \verb@2.0@ est la version approch\'ee du m\^eme entier; \verb@1/2@ est un rationnel, \verb@0.5@ est la version approch\'ee du m\^eme rationnel. {\tt Xcas} peut g\'erer des nombres entiers en pr\'ecision arbitraire~: essayez de taper \verb@500!@ et comptez le nombre de chiffres de la r\'eponse. On passe d'une valeur exacte \`a une valeur approch\'ee par \verb@evalf@, on transforme une valeur approch\'ee en un rationnel exact par \verb@exact@ \index{exact@{\verb+exact+}} \index{evalf@{\verb+evalf+}} Les calculs sont effectu\'es en mode exact si tous les nombres qui interviennent sont exacts. Ils sont effectu\'es en mode approch\'e si un des nombres est approch\'e. Ainsi \verb@1.5+1@ renvoie un nombre approch\'e alors que \verb@3/2+1@ renvoie un nombre exact. \begin{verbatim} sqrt(2) evalf(sqrt(2)) sqrt(2)-evalf(sqrt(2)) exact(evalf(sqrt(2)))*10^9 exact(evalf(sqrt(2)*10^9)) \end{verbatim} \index{sqrt@{\verb+sqrt+}} \index{precision@pr\'ecision} Pour les nombres r\'eels approch\'es, la pr\'ecision par d\'efaut est proche de 14 chiffres significatifs (la pr\'ecision relative est de 53 ou 45 bits pour les r\'eels flottants normalis\'es selon les versions de Xcas). Elle peut \^etre augment\'ee, en donnant le nombre de d\'ecimales d\'esir\'e comme second argument de \verb@evalf@. \begin{verbatim} evalf(sqrt(2),50) evalf(pi,100) \end{verbatim} On peut aussi changer la pr\'ecision par d\'efaut pour tous les calculs en modifiant \index{digits@{\verb+Digits+}} la variable \verb@Digits@. \begin{verbatim} Digits:=50 evalf(pi) evalf(exp(pi*sqrt(163))) \end{verbatim} \index{i@{\verb+i+}} La lettre \verb@i@ est r\'eserv\'ee \`a $\sqrt{-1}$\footnote{En mode maple, on utilise I}, il est d\'econseill\'e de la r\'eaffecter par exemple pour l'utiliser comme indice de boucle. \begin{verbatim} (1+2*i)^2 (1+2*i)/(1-2*i) e^(i*pi/3) \end{verbatim} \index{nombre!complexe} \index{infinity@{\verb+infinity+}} {\tt Xcas} distingue l'infini non sign\'e \verb@infinity@ ($\infty$), de \verb@+infinity@ ($+\infty$, raccourci \verb@inf@) et de \verb@-infinity@ ($-\infty$). \begin{verbatim} 1/0; (1/0)^2; -(1/0)^2 \end{verbatim} \vskip 2mm \begin{center} \begin{tabular}{|ll|} \hline \multicolumn{2}{|c|}{\bf Constantes pr\'ed\'efinies}\\ \hline\hline \verb@pi@&$\pi\simeq 3.14159265359$ \\ \verb@e@&$e\simeq 2.71828182846$ \\ \verb@i@&$i=\sqrt{-1}$ \\ \verb@infinity@&$\infty$ \\ \verb@+infinity@&$+\infty$ \\ \verb@-infinity@&$-\infty$ \\ \verb@euler_gamma@&$\gamma$ \\ \hline \end{tabular} \end{center} \index{e@{\verb+e+}} \index{pi@{\verb+pi+}} % \subsection{Les caract\`eres et les cha\^{i}nes} % \index{caract\`ere} \index{cha\^{i}ne} Une cha\^{i}ne est parenth\'es\'ee par des guillemets ({\tt "}). Un caract\`ere est une cha\^{i}ne ayant un seul \'el\'ement. \begin{verbatim} s:="azertyuiop" size(s) s[0]+s[3]+s[size(s)-1] concat(s[0],concat(s[3],s[size(s)-1])) head(s) tail(s) mid(s,3,2) l:=asc(s) ss:=char(l) string(123) expr(123) expr(0123) \end{verbatim} \vskip 2mm \begin{center} \begin{tabular}{|ll|} \hline \multicolumn{2}{|c|}{\bf Cha\^{i}nes}\\ \hline\hline \verb@asc@&cha\^{i}ne->liste des codes ASCII \\ \verb@char@&liste des codes ASCII->cha\^{i}ne \\ \verb@size@&nombre de caract\`eres \\ \verb@concat@ ou \verb@+@ &concat\'enation \\ \verb@mid@&morceau de cha\^{i}ne\\ \verb@head@&premier caract\`ere \\ \verb@tail@&cha\^{i}ne sans le 1ier caract\`ere\\ \verb@string@&nombre ou expression->cha\^{i}ne \\ \verb@expr@&cha\^{i}ne->nombre (base 10 ou 8) ou expression \\ \hline \end{tabular} \end{center}% \subsection{Les variables} % \index{variable!formelle} \index{variable!affect\'ee} On dit qu'une variable est formelle si elle ne contient aucune valeur~: toutes les variables sont formelles tant qu'elles n'ont pas \'et\'e affect\'ees (\`a une valeur). \index{affectation} L'affectation est not\'ee \verb@:=@. Au d\'ebut de la session \verb@a@ est formelle, elle devient affect\'ee apr\`es l'instruction \verb@a:=3@, \verb|a| sera alors remplac\'e par 3 dans tous les calculs qui suivent, et \verb|a+1| renverra 4. {\tt Xcas} conserve tout le contenu de votre session. Si vous voulez que la variable \verb@a@ apr\`es l'avoir affect\'ee, soit \`a nouveau une variable formelle, il faut la "vider" par \verb@purge(a)@. Dans les exemples qui suivent, les variables utilis\'ees sont suppos\'ees avoir \'et\'e purg\'ees avant chaque suite de commandes. \index{purge@{\verb+purge+}} \vskip 2mm\noindent Il ne faut pas confondre \begin{itemize} \item[$\bullet$] le signe \verb|:=| qui d\'esigne l'affectation \item[$\bullet$] le signe \verb|==| qui d\'esigne une \'egalit\'e bool\'eenne~: c'est une op\'eration binaire qui retourne 1 ou 0 (1 pour true qui veut dire Vrai et 0 pour false qui veut dire Faux) \item[$\bullet$] le signe \verb|=| utilis\'e pour d\'efinir une \'equation. \end{itemize} \index{egalite@\'egalit\'e} \index{equation@\'equation} \begin{verbatim} a==b a:=b a==b solve(a=b,a) solve(2*a=b+1,a) \end{verbatim} \index{assume@{\verb+assume+}} \index{hypoth\`ese} On peut faire certains types d'hypoth\`eses sur une variable avec la commande \verb|assume|, par exemple \verb|assume(a>2)|. Une hypoth\`ese est une forme sp\'eciale d'affectation, elle efface une \'eventuelle valeur pr\'ec\'edemment affect\'ee \`a la variable. Lors d'un calcul, la variable n'est pas remplac\'ee mais l'hypoth\`ese sera utilis\'ee dans la mesure du possible, par exemple \verb|abs(a)| renverra \verb|a| si on fait l'hypoth\`ese \verb@a>2@. \begin{verbatim} sqrt(a^2) assume(a<0) sqrt(a^2) assume(n,integer) sin(n*pi) \end{verbatim} \index{subst@{\verb+subst+}} La fonction \verb@subst@ permet de remplacer une variable dans une expression par un nombre ou une autre expression, sans affecter cette variable. \begin{verbatim} subst(a^2+1,a=1) subst(a^2+1,a=sqrt(b-1)) a^2+1 \end{verbatim} {\bf Remarque}~: pour stocker une valeur dans une variable par r\'ef\'erence, par exemple pour modifier une valeur dans une liste (un vecteur, une matrice), sans recr\'eer une nouvelle liste mais en modifiant en place la liste existante, on utilise l'instruction \verb|=<| au lieu de \verb|:=|. Cette instruction est plus rapide que l'instruction \verb|:=|, car elle \'economise le temps de copie de la liste. % \subsection{Les expressions} % \subsubsection{D\'efinition} \index{expression} Une expression est une combinaison de nombres et de variables reli\'es entre eux par des op\'erations~: par exemple \verb@x^2+2*x+c@. Lorsqu'on valide une commande, {\tt Xcas} remplace les variables par leur valeur si elles en ont une, et ex\'ecute les op\'erations. \begin{verbatim} (a-2)*x^2+a*x+1 a:=2 (a-2)*x^2+a*x+1 \end{verbatim} \index{simplifications automatiques} Certaines op\'erations de simplification sont ex\'ecut\'ees automatiquement lors d'une \'evaluation~: \begin{itemize} \item[$\bullet$] les op\'erations sur les entiers et sur les fractions, y compris la mise sous forme irr\'eductible \item[$\bullet$] les simplifications triviales comme $x+0=x$, $x-x=0$, $x^1=x$\ldots \item[$\bullet$] quelques formes trigonom\'etriques~: $\cos(-x)=\cos(x)$, $\cos(\pi/4)=\sqrt{2}/2$, $\tan(\pi/4)=1$\ldots \end{itemize} Nous verrons dans la section \ref{sec:simplify} comment obtenir plus de simplifications. \subsubsection{D\'evelopper et simplifier une expression} \label{sec:simplify} % \index{developper@d\'evelopper} \index{simplifier@simplifier} En-dehors des r\`egles de la section pr\'ec\'edente, il n'y a pas de simplification syst\'ematique. Il y a deux raisons \`a cela. La premi\`ere est que les simplifications non triviales sont parfois co\^uteuses en temps, et le choix d'en faire ou non est laiss\'e \`a l'utilisateur~; la deuxi\`eme est qu'il y a en g\'en\'eral plusieurs mani\`eres de simplifier une m\^eme expression, selon l'usage que l'on veut en faire. Les principales commandes pour transformer une expression sont les suivantes~: \begin{itemize} \item[$\bullet$] \index{expand@{\verb+expand+}} \verb|expand|~: d\'eveloppe une expression en tenant compte uniquement de la distributivit\'e de la multiplication sur l'addition et du d\'eveloppement des puissances enti\`eres. \item[$\bullet$] \index{normal@{\verb+normal+}} \index{ratnormal@{\verb+ratnormal+}} \verb|normal| et \verb|ratnormal|~: d'un bon rapport temps d'ex\'ecution-simplification, elles \'ecrivent une fraction rationnelle (rapport de deux polyn\^omes) sous forme de fraction irr\'eductible d\'evelopp\'ee; \verb|normal| tient compte des nombres alg\'ebriques (par exemple comme \verb|sqrt(2)|) mais pas \verb|ratnormal|. Les deux ne tiennent pas compte des relations entre fonctions transcendantes (par exemple comme \verb|sin| et \verb|cos|). \item[$\bullet$] \index{factor@{\verb+factor+}} \verb|factor|~: un peu plus lente que les pr\'ec\'edentes, elle \'ecrit une fraction sous forme irr\'eductible factoris\'ee. \item[$\bullet$] \index{simplify@{\verb+simplify+}} \verb|simplify|~: elle essaie de se ramener \`a des variables alg\'ebriquement ind\'ependantes avant d'appliquer \verb|normal|. Ceci est plus co\^uteux en temps et "aveugle" (on ne contr\^ole pas les r\'e\'ecritures interm\'ediaires). Les simplifications faisant intervenir des extensions alg\'ebriques (par exemple des racines carr\'ees) n\'ecessitent parfois deux appels et/ou des hypoth\`eses (\verb|assume|) pour enlever des valeurs absolues avant d'obtenir la simplification souhait\'ee. \item[$\bullet$] \index{tsimplify@{\verb+tsimplify+}} \verb|tsimplify| essaie de se ramener \`a des variables alg\'ebriquement ind\'ependantes mais sans appliquer \verb|normal| ensuite. \end{itemize} Dans le menu \verb@Math@ du bandeau sup\'erieur, les 4 sous-menus de r\'e\'ecriture contiennent d'autres fonctions, pour des transformations plus ou moins sp\'ecialis\'ees. \begin{verbatim} b:=sqrt(1-a^2)/sqrt(1-a) ratnormal(b) normal(b) tsimplify(b) simplify(b) simplify(simplify(b)) assume(a<1) simplify(b) simplify(simplify(b)) \end{verbatim} \index{convert@{\verb+convert+}} La fonction \verb@convert@ permet de passer d'une expression \`a une autre \'equivalente, sous un format qui est sp\'ecifi\'e par le deuxi\`eme argument. \begin{verbatim} convert(exp(i*x),sincos) convert(1/(x^4-1),partfrac) convert(series(sin(x),x=0,6),polynom) \end{verbatim} \vskip 2mm \begin{center} \begin{tabular}{|ll|} \hline \multicolumn{2}{|c|}{\bf Transformations}\\ \hline\hline \verb@simplify@& simplifier\\ \verb@tsimplify@& simplifier (moins puissant)\\ \verb@normal@& forme normale\\ \verb@ratnormal@& forme normale (moins puissant)\\ \verb@expand@& d\'evelopper\\ \verb@factor@& factoriser\\ \verb@assume@& rajout d'hypoth\`eses\\ \verb@convert@& transformer en un format sp\'ecifi\'e\\ \hline \end{tabular} \end{center} % \subsection{Les fonctions} % \subsubsection{Fonctions usuelles} De nombreuses fonctions sont d\'ej\`a d\'efinies dans {\tt Xcas}, en particulier les fonctions classiques. Les plus courantes figurent dans le tableau ci-apr\`es; pour les autres, voir le menu \verb@Math@. \vskip 2mm \begin{center} \begin{tabular}{|ll|} \hline \multicolumn{2}{|c|}{\bf Fonctions classiques}\\ \hline\hline \verb@abs@ & valeur absolue\\ \verb@round@ & arrondi \\ \verb@floor@ & partie enti\`ere (plus grand entier $\leq$)\\ \verb@ceil@ & plus petit entier $\geq $\\ \hline \verb@abs@ & module\\ \verb@arg@ & argument\\ \verb@conj@ & conjugu\'e\\ \hline \verb@sqrt@ & racine carr\'ee\\ \verb@exp@ & exponentielle\\ \verb@log@ & logarithme naturel\\ \verb@ln@ & logarithme naturel\\ \verb@log10@ & logarithme en base 10\\ \hline \verb@sin@ & sinus\\ \verb@cos@ & cosinus\\ \verb@tan@ & tangente\\ \verb@asin@ & arc sinus\\ \verb@acos@ & arc cosinus\\ \verb@atan@ & arc tangente\\ \hline \verb@sinh@ & sinus hyperbolique\\ \verb@cosh@ & cosinus hyperbolique\\ \verb@tanh@ & tangente hyperbolique\\ \verb@asinh@ & argument sinus hyperbolique\\ \verb@acosh@ & argument cosinus hyperbolique\\ \verb@atanh@ & argument tangente hyperbolique\\ \hline \end{tabular} \end{center} \index{abs@{\verb+abs+}} \index{valeur absolue} \index{round@{\verb+round+}} \index{arrondi} \index{floor@{\verb+floor+}} \index{ceil@{\verb+ceil+}} \index{partie enti\`ere} \index{re@{\verb+re+}} \index{partie r\'eelle} \index{im@{\verb+im+}} \index{partie imaginaire} \index{conj@{\verb+conj+}} \index{conjugu\'e} \index{sqrt@{\verb+sqrt+}} \index{racine carr\'ee} \index{exp@{\verb+exp+}} \index{log@{\verb+log+}} \index{ln@{\verb+ln+}} \index{logarithme!naturel} \index{logarithme!en base 10} \index{log10@{\verb+log10+}} \index{sin@{\verb+sin+}} \index{sinus} \index{cos@{\verb+cos+}} \index{cosinus} \index{tan@{\verb+tan+}} \index{tangente} \index{sinh@{\verb+sinh+}} \index{sinus!hyperbolique} \index{cosh@{\verb+cosh+}} \index{cosinus!hyperbolique} \index{tanh@{\verb+tanh+}} \index{tangente!hyperbolique} \index{asin@{\verb+asin+}} \index{arc!sinus} \index{acos@{\verb+acos+}} \index{arc!cosinus} \index{atan@{\verb+atan+}} \index{arc!tangente} \index{asinh@{\verb+asinh+}} \index{argument!sinus hyperbolique} \index{acosh@{\verb+acosh+}} \index{argument!cosinus hyperbolique} \index{atanh@{\verb+atanh+}} \index{argument!tangente hyperbolique} \subsubsection{Fonctions alg\'ebriques d\'efinies par l'utilisateur} Pour cr\'eer une nouvelle fonction, il faut la d\'eclarer \`a l'aide d'une expression contenant la variable. Par exemple l'expression $x^2-1$ est d\'efinie par \verb@x^2-1@. Pour la transformer en la fonction $f$ qui \`a $x$ associe $x^2-1$, trois possibilit\'es existent~: \begin{verbatim} f(x):= x^2-1 f:=x->x^2-1 f:=unapply(x^2-1,x) f(2); f(a^2) \end{verbatim} \index{fonction!d\'efinition d'une} \index{fonction} \index{expression} \index{unapply@{\verb+unapply+}} On peut d\'efinir des fonctions de plusieurs variables \`a valeurs dans $\mathbb R$ comme \verb@f(x,y):=x+2*y@ et des fonctions de plusieurs variables \`a valeurs dans $\mathbb R^p$ par exemple \verb@f(x,y):=(x+2*y,x-y)@ \subsubsection{Distinguer expression et fonction} Si \verb@f@ est une fonction d'une variable et \verb@E@ est une expression, \verb@f(E)@ est une autre expression. Il est essentiel de ne pas confondre fonction et expression. Si on d\'efinit : \verb@E:=x^2-1@, alors la variable \verb@E@ contient l'expression $x^2-1$. Pour avoir la valeur de cette expression en $x=2$ il faut \'ecrire \verb@subst(E,x=2)@ et non \verb@E(2)@ car \verb@E@ n'est pas une fonction. Lorsqu'on d\'efinit une fonction, le membre de droite de l'affectation n'est pas \'evalu\'e. Ainsi l'\'ecriture \verb@E:=x^2-1; f(x):=E@ d\'efinit la fonction $f: x \mapsto E$ car \verb@E@ n'est pas \'evalu\'e. Par contre \verb@E:= x^2-1; f:=unapply(E,x)@ d\'efinit bien la fonction $f: x\mapsto x^2-1$ car \verb@E@ est \'evalu\'e. La fonction \verb@diff@ (ou l'apostrophe postfix\'ee) permet de calculer la d\'eriv\'ee d'une expression par rapport \`a une ou plusieurs de ses variables. Pour d\'eriver une fonction $f$, on peut appliquer \verb@diff@ \`a l'expression $f(x)$, mais alors le r\'esultat est une expression. Si on souhaite d\'efinir la fonction d\'eriv\'ee, il faut utiliser \verb@function_diff@. \begin{verbatim} E:=x^2-1 diff(E); E' f:=unapply(E,x) f' diff(f(x)) f1:=function_diff(f) \end{verbatim} Il ne {\bf faut pas} d\'efinir la fonction d\'eriv\'ee par \verb|f1(x):=diff(f(x))|, car \verb|x| aurait dans cette d\'efinition deux sens incompatibles~: c'est d'une part la variable formelle de d\'erivation et d'autre part l'argument de la fonction \verb|f1|. D'autre part, cette d\'efinition \'evaluerait \verb|diff| \`a chaque appel de la fonction (car le membre de droite d'une affectation n'est jamais \'evalu\'e), ce qui serait inefficace. Il faut donc soit utiliser \verb|f1:=function_diff(f)|, soit \verb|f1:=unapply(diff(f(x)),x)|. \subsubsection{Op\'erations sur les fonctions} \index{fonction!composition des} \index{compos\'ee} On peut ajouter et multiplier des fonctions, par exemple \verb@f:=sin*exp@. Pour composer des fonctions, on utilise l'op\'erateur \verb|@| et pour composer plusieurs fois une fonction avec elle-m\^eme, on utilise l'op\'erateur \verb|@@|. \begin{verbatim} f:=x->x^2-1 f1:=f@sin f2:=f@f f3:=f@@3 f1(a) f2(a) f3(a) \end{verbatim} % \subsection{Listes, s\'equences, ensembles, vecteurs, matrices, polyn\^omes} % \index{liste} \index{sequence@s\'equence} \index{ensemble} \index{vecteur} \index{matrice} {\tt Xcas} distingue plusieurs sortes de collections d'objets, s\'epar\'es par des virgules~: \begin{itemize} \item[$\bullet$] les listes (entre crochets) \item[$\bullet$] les s\'equences (entre parenth\`eses) \item[$\bullet$] les ensembles (entre pourcentage-accolades) \end{itemize} \begin{verbatim} liste:=[1,2,4,2] sequence:=(1,2,4,2) ensemble:=%{1,2,4,2%} \end{verbatim} Les listes peuvent contenir des listes (c'est le cas des matrices), alors que les s\'equences sont plates (un \'el\'ement d'une s\'equence ne peut pas \^etre une s\'equence). Dans un ensemble, l'ordre n'a pas d'importance et chaque objet est unique. Il existe une autre structure, appel\'ee table (ou annuaire ou dictionnaire), dont nous reparlerons plus loin. Il suffit de mettre une s\'equence entre crochets pour en faire une liste ou entre accolades pr\'ec\'ed\'ees de \verb@%@ pour en faire un ensemble. On passe d'une liste \`a sa s\'equence associ\'ee par \verb@op@, d'une s\'equence \`a sa liste associ\'ee en la mettant entre crochets ou avec la fonction \verb@nop@. Le nombre d'\'el\'ements d'une liste est donn\'e par \verb@size@ (ou \verb@nops@). \index{op@{\verb+op+}} \index{nop@{\verb+nop+}} \index{nops@{\verb+nops+}} \index{size@{\verb+size+}} \index{nombre!d'\'el\'ements} \begin{verbatim} se:=(1,2,4,2) li:=[se] op(li) nop(se) nops(se) %{se%} size([se]) size(%{se%}) \end{verbatim} \index{it\'eration} \index{seq@{\verb+seq+}} \index{makelist@{\verb+makelist+}} Pour fabriquer une liste ou une s\'equence, on utilise des commandes d'it\'eration comme {\tt \$} ou \verb@seq@ (qui it\`erent une expression) ou \verb@makelist@ (qui d\'efinit une liste \`a l'aide d'une fonction). \begin{verbatim} 1$5 k^2 $ (k=-2..2) seq(k^2,k=-2..2) seq(k^2,k,-2..2) [k^2$(k=-2..2)] seq(k^2,k,-2,2) seq(k^2,k,-2,2,2) makelist(x->x^2,-2,2) seq(k^2,k,-2,2,2) makelist(x->x^2,-2,2,2) \end{verbatim} \index{NULL@{\verb+NULL+}} \index{liste!vide} \index{sequence@s\'equence!vide} La s\'equence vide est not\'ee \verb|NULL|, la liste vide \verb|[]|. Pour ajouter un \'el\'ement \`a une s\'equence il suffit d'\'ecrire la s\'equence et l'\'el\'ement s\'epar\'es par une virgule. \index{append@{\verb+append+}} Pour ajouter un \'el\'ement \`a une liste on utilise \verb|append|. On acc\`ede \`a un \'el\'ement d'une liste ou d'une s\'equence gr\^ace \`a son indice mis entre crochets, le premier \'el\'ement \'etant d'indice 0 (en mode Xcas, dans les autres modes les indices commencent \`a 1).\footnote{On peut aussi utiliser les parenth\`eses au lieu des crochets en mode Xcas pour indicier en commencant \`a 1} \begin{verbatim} se:=NULL; se:=se,k^2$(k=-2..2); se:=se,1 li:=[1,2]; (li:=append(li,k^2))$(k=-2..2) li[0],li[1],li[2] \end{verbatim} On peut modifier un \'el\'ement d'une liste, s\'equence, ensemble en utilisant l'op\'erateur d'affectation \verb|:=|. Une copie de la liste modifi\'ee est alors cr\'e\'ee. Pour des raisons d'efficacit\'e (temps de copie) on peut aussi utiliser l'op\'erateur d'affectation par r\'ef\'erence (en place) \verb|=<| mais attention cela modifiera toutes les variables pointant sur la liste originale. Par exemple \verb|li[1]:=3| ou \verb|li[1]=<4|. Les vecteurs sont repr\'esent\'es par des listes, les matrices par des listes de listes de m\^eme longueur repr\'esentant les lignes de la matrice. Vous trouverez dans le menu \verb|Cmds->Alglin| de nombreuses commandes pour manipuler vecteurs et matrices. Les polyn\^omes sont souvent d\'efinis par une expression, mais ils peuvent aussi \^etre repr\'esent\'es par la liste de leurs coefficients par ordre de degr\'e d\'ecroissant, avec comme d\'elimiteurs \verb|poly1[| et \verb|]|. Il existe aussi une repr\'esentation pour les polyn\^omes \`a plusieurs variables. Les fonctions \verb|symb2poly| et \verb|poly2symb| permettent de passer de la repr\'esentation expression \`a la repr\'esentation par liste et inversement, le deuxi\`eme argument d\'etermine s'il s'agit de polyn\^omes en une variable (on met le nom de la variable) ou de polyn\^omes \`a plusieurs variables (on met la liste des variables). \vskip 2mm \begin{center} \begin{tabular}{|ll|} \hline \multicolumn{2}{|c|}{\bf S\'equences et listes}\\ \hline\hline \verb@E$(k=n..m)@ &cr\'eer une s\'equence\\ \verb@seq(E,k=n..m)@ &cr\'eer une s\'equence\\ \verb@[E$(k=n..m)]@ & cr\'eer une liste\\ %$ \verb@makelist(f,k,n,m,p)@ & cr\'eer une liste\\ \verb@op(li)@ & passer de liste \`a s\'equence\\ \verb@nop(se)@ & passer de s\'equence \`a liste\\ \verb@nops(li)@ & nombre d'\'el\'ements\\ \verb@size(li)@ & nombre d'\'el\'ements\\ \verb@sum@ & somme des \'el\'ements\\ \verb@product@ & produit des \'el\'ements\\ \verb@cumSum@ & sommes cumul\'ees des \'el\'ements\\ \verb@apply(f,li)@ & appliquer une fonction \`a une liste\\ \verb@map(li,f)@ & appliquer une fonction \`a une liste\\ \verb@poly2symb@ & polyn\^ome associ\'e \`a une liste\\ \verb@symb2poly@ & coefficients d'un polyn\^ome\\ \hline \end{tabular} \end{center} \index{sum@{\verb+somme+}} \index{somme} \index{product@{\verb+product+}} \index{produit} \index{cumsum@{\verb+cumSum+}} \index{sommes cumul\'ees} \index{apply@{\verb+apply+}} \index{fonction!appliqu\'ee \`a une liste} \index{map@{\verb+map+}} \index{poly2symb@{\verb+poly2symb+}} \index{symb2poly@{\verb+symb2poly+}} \index{liste!des coefficients} % \subsection{Les tables} Il s'agit de conteneurs associatifs permettant de cr\'eer des tableaux indici\'es par n'importe quel type d'indice ordonn\'e et non d'un indice entier compris entre 0 et la taille de la table. C'est typiquement ce qu'on utilise pour un annuaire. Par exemple\\ \verb|tel["gaston"]:=123456789; tel["lagaffe"]:=987654321|\\ cr\'ee une table contenant deux entr\'ees dont les indices sont des chaines de caract\`eres. Attention, c'est ce type de conteneur qui est cr\'e\'e par d\'efaut lorsqu'on \'ecrit une affectation comme \verb|t[0]:=5| lorsque \verb|t| n'a pas \'et\'e initialis\'e \`a un type liste auparavant. \subsection{Instructions graphiques} \label{sec:graphique} Toutes les instructions du menu \verb|Geo| ont un r\'esultat graphique, par exemple \verb|point(1,2)| affiche le point de coordonn\'ees 1 et 2, \verb|droite(A,B)| la droite passant par deux points $A$ et $B$ d\'efinis auparavant. On peut donner des attributs graphiques aux objets graphiques en ajoutant \`a la fin de l'instruction graphique l'argument \verb|affichage=...| dont la saisie est facilit\'ee par le menu \verb|Graphic->Attributs|. Lorsqu'une ligne de commande contient une instruction graphique, le r\'esultat est affich\'e dans un rep\`ere 2-d ou 3-d selon la nature de l'objet g\'en\'er\'e. On peut controler le rep\`ere avec les boutons situ\'es \`a droite du graphique, par exemple orthonormaliser avec le bouton \verb@_|_@. Si une ligne de commande contient des instructions graphique et non graphiques, c'est la nature de la derni\`ere instruction qui d\'ecide du type d'affichage. L'instruction \verb|A:=click()| permet de d\'efinir une variable contenant l'affixe d'un point du plan que l'on clique avec la souris. \subsection{Temps de calcul, place m\'emoire} % Le principal probl\`eme du calcul formel est la complexit\'e des calculs interm\'ediaires. Elle se traduit \`a la fois par le temps n\'ecessaire \`a l'ex\'ecution des commandes et par la place m\'emoire requise. Les algorithmes impl\'ement\'es dans les fonctions de {\tt Xcas} sont performants, mais ils ne \index{time@{\verb+time+}} \index{temps de calcul} peuvent pas \^etre optimaux dans tous les cas. La fonction \verb@time@ permet de conna\^\i tre le temps d'ex\'ecution d'une commande (si ce temps est tr\`es court, {\tt Xcas} ex\'ecute plusieurs fois la commande pour afficher un r\'esultat plus pr\'ecis). La m\'emoire utilis\'ee appara\^\i t dans les versions Unix dans la ligne d'\'etat (en rouge \`a bas \`a gauche). Si le temps d'ex\'ecution d'une commande d\'epasse quelques secondes, il est possible que vous ayez commis une erreur de saisie. N'h\'esitez pas \`a interrompre l'ex\'ecution (bouton orange \verb@stop@ en bas \`a droite, il est conseill\'e de faire une sauvegarde de votre session auparavant). \section{Programmation} \label{sec:prog} Comme le texte d\'efinissant un programme ne tient en g\'en\'eral pas sur une ou deux lignes, il est commode d'utiliser un \'editeur de programmes. Pour cela, on utilise le menu \verb|Prg->Nouveau programme| de Xcas. Le menu \verb|Prg->Ajouter| facilite aussi la saisie des principales structures de controle de programmation. \subsection{Tests} On peut tester l'\'egalit\'e de 2 expressions en utilisant l'instruction \verb|==|, alors que \verb|!=| teste si 2 expressions ne sont pas \'egales. On peut aussi tester l'ordre entre 2 expressions avec \verb|<|, \verb|<=|, \verb|>|, \verb|>=|, il s'agit de l'ordre habituel sur les r\'eels pour des donn\'ees num\'eriques ou de l'ordre lexicographique pour les chaines de caract\`eres. Un test renvoie 1 s'il est vrai, 0 s'il est faux. On peut combiner le r\'esultat de deux tests au moyen des op\'erateurs logiques {\tt \&\&} (et logique), {\tt ||} (ou logique) et on peut calculer la n\'egation logique d'un r\'esultat de test {\tt !} (n\'egation logique). On utilise ensuite souvent la valeur du test pour ex\'ecuter une instruction conditionnelle \verb|if ... then ... else ... fi|. N.B.~: Xcas admet aussi une syntaxe compatible avec le langage C\\ \verb|if (condition) { bloc_vrai } else { bloc_faux }|. Par exemple, on pourrait stocker la valeur absolue d'un r\'eel $x$ dans $y$ par~: \begin{center} \verb|if x>0 then y:=x; else y:=-x; fi;| \end{center} (on peut bien sur utiliser directement \verb|y:=abs(x)|). Exemples~: Tester si un triangle dont on fait cliquer les 3 sommets \`a l'utilisateur est rectangle. \subsection{Boucles} On peut ex\'ecuter des instructions plusieurs fois de suite en utilisant une boucle d\'efinie (le nombre d'ex\'ecutions est fix\'e au d\'ebut) ou ind\'efinie (le nombre d'ex\'ecutions n'est pas connu). On utilise en g\'en\'eral une variable de controle (indice de boucle ou variable de terminaison). \begin{itemize} \item Boucle d\'efinie\\ \verb|for(init;condition;incrementation){ instructions }|\\ \verb|for ... from ... to ... do ... od|\\ Exemple, calcul de 10!\\ \verb|f:=1; for (j:=1;j<=10;j++){ f:=f*j; }|\\ \verb|f:=1; for j from 1 to 10 do f:=f*j; od;|\\ {\bf Attention} \`a ne pas utiliser \verb|i| comme indice de boucle, car \verb|i| est pr\'ed\'efini (comme $\sqrt{-1}$) \item Boucle ind\'efinie\\ \verb|while (...) { ... }|\\ Exemple, algorithme d'Euclide\\ \verb|while (b!=0){ r:=irem(a,b); a:=b; b:=r;}| \end{itemize} Xcas accepte aussi l'arr\^et de boucle en cours d'ex\'ecution (\verb|if (...) break;|) dont l'usage peut \'eviter l'utilisation de variables de controle compliqu\'ees. \subsection{Fonctions (non alg\'ebriques)} La plupart des fonctions ne peuvent avoir une d\'efinition par une formule alg\'ebrique. On doit souvent calculer des donn\'ees interm\'ediaires, faire des tests et des boucles. Il faut alors d\'efinir la fonction par une suite d'instructions, d\'elimit\'ees par \verb|{ ... }|. La valeur calcul\'ee par la fonction est alors la valeur calcul\'ee par la derni\`ere instruction ou peut \^etre explicit\'ee en utilisant le mot-clef \verb|return| suivi de la valeur \`a renvoyer (N.B.: l'ex\'ecution de \verb|return| met un terme \`a la fonction m\^eme s'il y a encore des instructions apr\`es). Pour \'eviter que les donn\'ees interm\'ediaires n'interf\`erent avec les variables de la session principale, on utilise un type sp\'ecial de variables, les variables locales, dont la valeur ne peut \^etre modifi\'ee ou acc\'ed\'ee qu'\`a l'int\'erieur de la fonction. On utilise \`a cet effet le mot-clef \verb|local| suivi par les noms des variables locales s\'epar\'es par des virgules. Si une fonction calcule plusieurs donn\'ees on peut les renvoyer dans une liste. \subsection{Exemple~: le PGCD} Ajouter un niveau programme (menu Prg, nouveau programme). \begin{verbatim} pgcd(a,b):={ local r; while (b!=0){ r:=irem(a,b); a:=b; b:=r; } return a; } \end{verbatim} On clique ensuite sur le bouton OK, si tout va bien, le programme \verb|pgcd| est d\'efini et on peut le tester dans une ligne de commande par exemple par \verb|pgcd(25,15)|. S'il y a des erreurs, la premi\`ere erreur rencontr\'ee est affich\'ee et la position de l'erreur est mise en surbrillance dans l'\'editeur de programmes. Dans la section suivante, on va voir comment ex\'ecuter en mode pas \`a pas un programme, ce qui peut servir \`a comprendre le d\'eroulement d'un algorithme, mais aussi \`a corriger un programme erron\'e. \subsection{Ex\'ecuter en pas \`a pas et mettre au point} La commande {\tt debug} permet de lancer un programme en mode d'ex\'ecution pas \`a pas. Elle ouvre une fen\^etre permettant de diriger l'ex\'ecution du programme pass\'e en argument. Par exemple, on entre le programme~: \begin{verbatim} carres(n):={ local j,k; k:=0; for (j:=1;jsin(x)}, une liste, une s\'equence, un vecteur, une matrice. Essayez d'acc\'eder aux parties de l'objet pour les objets composites (en utilisant {\tt op} par exemple). \item Comparer le type de l'objet \verb|t| si on effectue la commande \verb|t[2]:=0;| apr\`es avoir purg\'e \verb|t| ou apr\`es avoir affect\'e \verb|t:=[1,2,3]|~? \item Comparer l'effet de l'affectation dans une liste et dans un vecteur ou une matrice sur votre logiciel (en Xcas, on peut utiliser \verb|=<| au lieu de \verb|:=| pour stocker par r\'ef\'erence). \item Voici un programme qui calcule la base utilis\'ee pour repr\'esenter les flottants. \begin{verbatim} Base():={ local A,B; A:=1.0; B:=1.0; while (evalf(evalf(A+1.0)-A)-1.0=0.0) { A:=2*A;}; while (evalf(evalf(A+B)-A)-B<>0) { B:=B+1;} return B; } :; \end{verbatim} Testez-le et expliquez. \item D\'eterminer le plus grand r\'eel positif $x$ de la forme $2^{-n}$ ($n$ entier) tel que $(1.0+x)-1.0$ renvoie 0 sur PC avec la pr\'ecision par d\'efaut puis avec \verb|Digits:=30|. \item Calculer la valeur de $a:=\exp(\pi \sqrt{163})$ avec 30 chiffres significatifs, puis sa partie fractionnaire. Proposez une commande permettant de d\'ecider si $a$ est un entier. \item D\'eterminer la valeur et le signe de la fraction rationnelle \[ F(x,y)= \frac{1335}{4} y^6 + x^2 (11x^2 y^2-y^6 -121y^4-2) + \frac{11}{2} y^8 + \frac{x}{2y}\] en $x=77617$ et $y=33096$ en faisant deux calculs, l'un en mode approch\'e et l'autre en mode exact. Que pensez-vous de ces r\'esultats? Combien de chiffres significatifs faut-il pour obtenir un r\'esultat raisonnable en mode approch\'e? \item \`A quelle vitesse votre logiciel multiplie-t-il des grands entiers (en fonction du nombre de chiffres)? On pourra tester le temps de calcul du produit de $a(a+1)$ o\`u $a=10 000!$, $a=15000!$, etc. \item Comparer le temps de calcul de $a^n \pmod m$ par la fonction \verb|powmod| et la m\'ethode prendre le reste modulo $m$ apr\`es avoir calcul\'e $a^n$.\\ Programmez la m\'ethode rapide et la m\'ethode lente.\\ Que se passe-t-il si on essaie d'appliquer l'algorithme de la puissance rapide pour calculer $(x+y+z+1)^{32}$~? Calculer le nombre de termes dans le d\'eveloppement de $(x+y+z+1)^n$ et expliquez. \item D\'eterminer un entier $c$ tel que $c=1 \pmod 3$, $c=3 \pmod 5$, $c=5 \pmod 7$ et $c=2 \pmod 11$. \item Programmation de la m\'ethode de Horner\\ Il s'agit d'\'evaluer efficacement un polyn\^ome \[ P(X) = a_n X^n + ... + a_0 \] en un point. On pose $b_0=P(\alpha )$ et on \'ecrit~: \[ P(X)-b_0=(X-\alpha )Q(X) \] o\`u~: \[ Q(X) = b_n X^{n-1} + ... +b_2 X + b_1 \] On calcule alors par ordre d\'ecroissant $b_n$, $b_{n-1}$, ..., $b_0$. \begin{enumerate} \item Donner $b_n$ en fonction de $a_n$ puis pour $i\leq n-1$, $b_i$ en fonction de $a_i$ et $b_{i+1}$. Indiquez le d\'etail des calculs pour $P(X)=X^3-2X+5$ et une valeur de $\alpha $ non nulle. \item \'Ecrire un fonction \verb|horn| effectuant ce calcul: on donnera en arguments le polyn\^ome sous forme de la liste de ces coefficients (dans l'exemple \verb|[1,0,-2,5]|) et la valeur de $\alpha $ et le programme renverra $P(\alpha )$. (On pourra aussi renvoyer les coefficients de $Q$). \item En utilisant cette fonction, \'ecrire une fonction qui calcule le d\'eveloppement de Taylor complet d'un polyn\^ome en un point. \end{enumerate} \item Algorithmes fondementaux~: \'ecrire des programmes impl\'ementant \begin{enumerate} \item le pgcd de 2 entiers \item l'algorithme de B\'ezout \item l'inverse modulaire en ne calculant que ce qui est n\'ecessaire dans l'algorithme de B\'ezout \item les restes chinois \end{enumerate} \end{enumerate} \end{document}