\documentclass[a4paper,12pt]{amsart}
\usepackage{kbexo}


%%%%%%%%%%%%%%%%%%%%%
%% Alice's packages
%%%%%%%%%%%%%%%%%%%%%
\usepackage{xcolor}

%%%%%%%%%%%%%%%%%%%
%% Alice's macros
%%%%%%%%%%%%%%%%%%%
\newcommand{\comment}[1]{{\color{gray}#1}}

\def\pow{\^{}\hskip0pt}

\course{Algèbre et calcul formel -- Agrégation}
\num{1}

\begin{document}
\exotitle[Initiation à Sage]

\section{Introduction}
Sage est un logiciel libre de calcul, accessible sur
\url{http://www.sagemath.org}, qui utilise le langage \texttt{Python}.
Il existe trois façons de l'utiliser.

\begin{itemize}
\item En utilisant l'interface graphique, ou \emph{notebook}.

\item Par la ligne de commande interactive, en appelant éventuellement des
programmes écrits sur un éditeur de texte. Pour cela, il suffit de taper la
commande {\tt sage} sur une fenêtre terminal.

\item En écrivant des scripts python indépendants qui font appel à la
  bibliothèque {\tt sage}.
\end{itemize}
Nous utiliserons essentiellement le \emph{notebook}


\section{Quelques commandes utiles}
- Pour ouvrir {\tt sage}: {\tt sage} dans une fenêtre Terminal,
puis {\tt notebook()}.

- Pour quitter  {\tt sage}: fermer le notebook, puis {\tt <Ctrl-d>}.

- Dernier résultat : {\tt \_}

- Complétion : {\tt <Tab>}

- Commentaire : {\tt \#} pour une ligne, {\tt '{}'{}'} blablabla {\tt '{}'{}'}
pour un bloc.

- Informations sur une fonction : {\tt Nom\_de\_fonction?} (par exemple {\tt
factor?}). Pour quitter l'aide ainsi activée, taper {\tt q}. (Nous verrons
d'autres moyens pour obtenir de l'aide.)

\section{Opérations de base, tests et affectations}

Lancez le notebook et ouvrez une session en cliquant sur {\tt New
worksheet}. Donnez un nom à cette session, en suivant les instructions à
l'écran.

Cliquez ensuite sur {\tt Help} (en haut de la feuille), puis {\tt Work trough the tutorial},
puis {\tt Assignment, equality and arithmetic}. Lisez le tutoriel et copiez-collez les exemples dans le notebook pour vérifier que tout fonctionne bien.
Pour évaluer une ligne dans le notebook, on peut soit cliquer sur
{\tt evaluate} soit utiliser {\tt shift} {\tt enter}.


Une fois finie la lecture du tutoriel, tapez

{\tt a=9}

\noindent{} et validez, puis tapez

{\tt a.}

\noindent{} et actionnez la touche {\tt Tab}. Alors, la liste des fonctions
pouvant s'appliquer à {\tt a} apparaît. Ici, {\tt a} est un entier. Cliquez
par exemple sur {\tt a.n}. Normalement, cette expression apparaît sur votre
ligne de commande. Si vous voulez savoir à quoi correspond cette commande, tapez

{\tt a.n?}

Plus généralement, pour tout objet préalablement défini (par exemple un
entier, un polynôme, un anneau, etc.), la complétion {\tt Tab} permet de
lister les méthodes qui peuvent lui être appliquées. C'est utile pour
chercher le nom d'une fonction.

\section{Listes, ensembles, dictionnaires}

\Q Sur la même session, expérimentez les commandes suivantes (ne pas hésiter
à évaluer $S$ après chaque commande pour vérifier son effet).

{\tt S=[1,2,3,12]}

{\tt len(S)}

{\tt \_} \comment{(dernier résultat obtenu)}

{\tt S[0]}

{\tt S[3]}

{\tt S[1]=6}

{\tt S.append(10)} \comment{(ajout d'un élément à la liste $S$)}

{\tt S.extend([18,19])} \comment{(concaténation)}

{\tt S=S+[3,4,5]} \comment{(autre syntaxe pour la concaténation)}

{\tt S[2:4]}

{\tt S[2:]}

{\tt S[:-1]}

\medskip
{\tt S=range(1,10)} 

\comment{(remarquez que la liste n'est pas vraiment créée, elle sera créée à la volée lorsque l'utilisateur le demandera (c'est une nouveauté de python 3 par rapport à python~2))}

\medskip
{\tt S=list(range(1,10))}

\comment{(cette fois la liste est créée; remarquez qu'elle s'arrête à $9$)}

{\tt S=[0..10]} 

\comment{(avec cette syntaxe, la liste est créée automatiquement et va jusqu'à $10$)}

{\tt S=list(range(1,6,2))} \comment{(le troisième argument est le pas de l'énumération)}

{\tt S=list(range(6,1,-1))} \comment{(le pas peut être négatif)}

{\tt S=list(range(6))}

{\tt S=[1,5,..33]}

{\tt 29 in S}

{\tt S[1]=50}

{\tt S.sort()}

{\tt S=[i\pow2 for i in [1..10]]}

{\tt S=[i\pow2+1 for i in range(2,11) if is\_prime(i\pow2+1)]}

{\tt S=[(i,j) for i in range(4)  for j in range(3)]}

{\tt S=[[i**j for i in range(3)] for j in range(1,5)]}

{\tt flatten(S)}


{\tt S=set([1,1,2,2,5,5,4,4])} \comment{(C'est un ensemble: il n'y a pas de répétition
et les entrées sont triées.)}

\misctitle{Remarque}
La commande {\tt set(\dots)} donne l'ensemble défini par {\tt '\dots'}. De
même, {\tt list(S)} produit la liste des éléments de l'ensemble {\tt S},
c'est-à-dire ici la liste {\tt [1,2,4,5]}. Plus généralement, si $A$ est un
objet, définit comme un ensemble, ou un ensemble muni d'une structure, comme un
anneau, un corps, etc. et si $a$ est un objet susceptible de définir un élément
de $A$, alors la commande {\tt A(a)} définit cet élément; par exemple, l'entier
$1$ définit l'élément $\bar{1}$ de $\ZM/3\ZM$. Nous verrons d'autres exemples
de ce principe plus tard.


\Q Taper

{\tt sum(S)}

La fonction {\tt sum} additionne donc les éléments d'une liste, ou d'un
ensemble. Elle peut être utilisée autrement:

{\tt sum(k\pow2,k,0,4)}

\noindent Il y a un problème : il faut déclarer la variable $k$.
 Dans Sage, il
faut toujours déclarer les objets sur lesquels on travaille. 
\footnote{Il y a une exception à cette règle: {\tt x} est considéré par défaut comme une variable. Il n'y a donc pas besoin de le définir comme variable en faisant {\tt x=var('x')}. Par contre, si à un moment vous assignez quelque chose à {\tt x}, en faisant {\tt x = 9} par exemple, alors {\tt x} ne sera plus considéré comme une variable. Dans le doute, ça ne coûte pas cher de redéfinir {\tt x = var('x')} avant de l'utiliser (ou de vérifier son type grâce à {\tt type(x)}), et ça évite des soucis.}
Faire plutôt

{\tt k=var('k'); sum(k\pow2,k,0,4)}

En utilisant {\tt sum}, retrouver l'expression de la somme des carrés des
entiers compris entre $1$ et $n$ (pour obtenir la forme factorisée de cette
expression, utiliser la fonction {\tt factor}).

\misctitle{Remarque} Dans la commande {\tt k = var('k')}, le premier {\tt k} définit le nom de la variable pour sage, et le second définit la façon dont sage affichera la variable pour vous. Essayez par exemple de taper {\tt k = var('a'); print(k+1)}. En général on utilise le même nom pour les deux, ce qui permet d'éviter les confusions.

\Q Dans sage, on peut définir des dictionnaires, c'est-à-dire des collections
non ordonnées d'objets. On accède aux différentes valeurs classées dans le
dictionnaire par des clefs. Taper par exemple les commandes suivantes.

{\tt dico=\{\}}

{\tt dico["clef"]=421}

{\tt dico["seconde clef"]=0}

{\tt dico["clef"]}

{\tt dico["troisieme clef"]} 

\comment{(vous obtenez une erreur parce que "troisieme clef" n'est pas dans {\tt dico})}

{\tt "troisieme clef" in dico}

{\tt "clef" in dico}


\Q Construire la liste $L=[1,2,3,4,5,6]$. Quels sont les éléments $L[3]$,
$L[0]$, $L[-1]$, $L[-3]$? Comment obtenir la liste $[2,3,4]$ directement à
partir de la liste $L$?

\Q À l'aide de {\tt range}, construire la liste des entiers compris entre $0$
et $20$. Que donne la commande {\tt L[3:15:2]}? Construire la liste
$[15,14,13,12]$ à partir de $L$ par une commande similaire.

\section{Boucles, fonctions}

\Q Dans le {\tt tutorial}, faire les exercices de {\tt functions, indentation
and counting} jusqu'à {\tt list(range(2,10))}.


\Q On résume ci-dessous quelques commandes utiles pour la programmation. La
syntaxe est celle de Python. La structure des programmes (le découpage en
«blocs») est déterminée par l'\emph{indentation}.

\noindent $\bullet$ Pour créer une fonction {\tt f} dont les paramètres
formels sont {\tt a}, {\tt b}, {\tt c} :

\begin{verbatim}
  def f(a,b,c):
    Instruction 1
    Instruction 2
    ...
    return ``résultat''
\end{verbatim}

\medskip

Expérimenter la fonction suivante.

\begin{verbatim}
  def pair(n):
    v = []
    for i in range(3,n):
      if i % 2 == 0:
        v.append(i)
    return v
\end{verbatim}

\noindent $\bullet$ Pour les tests, on utilise la syntaxe suivante:

\begin{verbatim}
  if condition:
    Instruction 1
    Instruction 2
    ...
  elif condition 2:
    Instruction 1
    ...
  elif condition 3:
    Instruction 1
    ...
  else:
    Instruction 1
    ...
\end{verbatim}

\noindent $\bullet$ Boucles:

\begin{verbatim}
  while condition:
    Instruction 1
    Instruction 2
    ...
\end{verbatim}

\begin{verbatim}
  for i in L:
    Instruction 1
    Instruction 2
    ...
\end{verbatim}

\noindent Ici, {\tt L} peut être une liste, ou bien un $n$-uplet, ou bien un
ensemble, ou toute autre structure pouvant être énumérée.

\misctitle{Remarque} Pour les boucles {\tt for} avec {\tt i} variant entre {\tt x} et {\tt y}, il vaut mieux utiliser {\tt range(x,y+1)} plutôt que {\tt [x..y]}. En effet, à chaque itération, on n'a besoin que de la valeur courante de {\tt i}, il n'y a donc pas besoin de créer la liste complète. Si vous utilisez {\tt [x..y]}, vous pourriez vous retrouver avec un programme plus lent que nécessaire, voire faire planter votre ordinateur parce que vous utiliserez trop de mémoire.
Pour le tester sur un exemple, sauvegardez tous vos documents (si jamais l'ordinateur plante et qu'il faut le redémarrer) et tapez ensuite les deux exemples suivants

\begin{verbatim}
x = 0
for i in range(10^6):
    x = x+1
print(x)
\end{verbatim}

\noindent Puis
\begin{verbatim}
x = 0
for i in [1..10^6]:
    x = x+1
print(x)
\end{verbatim}
\noindent Si les deux exemples sont rapides, augmentez le $10\hat{\ }6$ en $10\hat{\ }7$, puis en $10\hat{\ }8$. \comment{(Chez moi, l'ordi plante à $10\hat{\ }8$ pour le deuxième exemple.)}

\Q Expérimenter par exemple :

\begin{verbatim}
  k.<a>=GF(3)
  for i in VectorSpace(k,2)
    print i
\end{verbatim}

\Q Pour chacun des exemples suivants, écrire une fonction dépendant de $n$
permettant de calculer la liste $L(n)$. Pour les quatre premières questions,
on donnera deux méthodes: l'une utilisera une boucle, l'autre une liste «à
formule» (c'est-à-dire du style {\tt [i\pow2 for i in range(n)]} pour la
liste des carrés des entiers strictement inférieurs à $n$), ou une simple
commande {\tt range}.

\qq $L(n)$ est la liste des $n$ premiers termes de la série harmonique
$$\sum_{i=1}^n\frac{1}{i}$$

\qq $L(n)$ est la liste des entiers impairs compris entre $1$ et $n$.

\qq $L(n)$ est la liste des $n$ premiers entiers impairs.

\qq $L(n)$ est la liste des entiers compris entre $1$ et $n$ qui ne sont
divisibles ni par $2$, ni par $3$, ni par $5$.

\Q Calculer la somme de tous les multiples de $3$ ou $5$ inférieurs ou égaux à
1000.

\Q On appelle triplet pythagoricien tout triplet $(x,y,z)$ d'entiers
naturels non nuls tels que
$$x^2+y^2=z^2.$$

\qq Faire la liste de tous les triplets pythagoriciens dont toutes les
composantes sont inférieurs ou égales à $50$.

\qq Déterminer les triplets pythagoriciens $(a,b,c)$ tel que $a+b+c=1000$ (il
n'y en a qu'un, à permutation près de $a$ et $b$).

\Q Écrire une fonction qui calcule le $n$-ème terme $F_n$ de la suite de
Fibonacci définie par~: $F_0=0$, $F_1=1$, $F_{n}=F_{n-1}+F_{n-2}$ pour
$n\geq2$ (on donnera deux fonctions~: l'une sera récursive et l'autre
utilisera une boucle).
Comparez l'efficacité des deux fonctions en calculant $F_{40}$. \comment{(La fonction récursive devrait être très lente alors que la fonction itérative devrait être rapide si vous vous y êtes bien pris. Savez-vous expliquer pourquoi?)}

\Q Soit $n$ un entier naturel. On note $E(n)$ l'ensemble des entiers naturels
compris entre $1$ et $n$.

\qq Écrire une fonction qui, étant donné un entier $n$, donne la liste des
parties de $E(n)$ à $2$ éléments. Pour cela, on peut écrire la liste des
$[i,j]$ tels que $i$ est dans $E(n)$ et $i<j$.

\qq Écrire une fonction qui, étant donnés $n$, $k$ un entier tel que $1\leq
k<n$ et la liste des parties de $E(n)$ à $k$ éléments (sous la forme
$[i_1,\dots,i_k]$ où $i_1<\dots<i_k$), donne la liste des parties de $E(n)$ à
$k+1$ éléments.

\qq Écrire une fonction qui, étant donnés $n$ et $k$, donne la
liste des parties de $E(n)$ à $k$ éléments.
\end{document}
