% cours2tex (gH)
%
\documentclass[a4paper,12pt]{article}
%
\usepackage{maple2e}
%
\parskip    0.35cm
\parindent  0.00cm
%
\renewcommand{\thesection}{\arabic{section}. }
\renewcommand{\thesubsection}{\arabic{section}.\arabic{subsection}}
%
\def\C{\mbox{l\hspace{-0.43em}C}}
\def\Maple{\textit{Maple}}
\def\L{\ensuremath{\mathcal{L}}}
\def\dz{\texttt{\symbol{'043}}}      % di\`{e}se
%
% pour une matrice 2x2
%
\newcommand{\mat}[4]{\ensuremath{%
\left(\begin{tabular}{cc}%
#1&#2\\#3&#4\\\end{tabular}\right)}
}% fin de definition de \mat
%
% pour simuler une entr\'{e}e (ligne) Maple
%
\newcommand{\mapleIn}[1]{\textsf{
\begin{tabular}{ll}
 $ > $ &#1
\end{tabular}
}}
%
% pour simuler une sortee (ligne) Maple
%
\newcommand{\mapleOut}[1]{\texttt{
\begin{tabular}{ll}
 \hspace{1.3cm} & #1
\end{tabular}
}}
%
% une entr\'{e}e et une sortie pour Maple longue
%
\newcommand{\mapleInt}[1]{\textsf{#1}}
\newcommand{\mapleOutLong}[1]{\texttt{#1}}
%
% des macros "locales" au sujet
%
\def\sl{$sl(2,\C)$}
\def\slm{\textit{sl}-matrix}
\def\slms{\textit{sl}-matrices}
\newcommand{\sym}[1]{$Sym^{#1}(\C^ 2)$}
%
%
\begin{document}
%
\title{2. Structures de donn\'{e}es et d'actions}
\author{Gilles Hunault}
\date{}
\maketitle
%\tableofcontents
%
\section{Structures de donn\'{e}es}  % ##
%
Nous avons vu dans le chapitre 1 les objets \'{e}l\'{e}mentaires que sont
les nombres  (entiers, rationnel, r\'{e}els, complexes...)
et la notation fonctionelle \texttt{->} pour d\'{e}crire
une fonction \'{e}l\'{e}mentaire. Les notions de pr\'{e}cision, d'affectation et
de substitution sont \'{e}galement suppos\'{e}es connues pour ce chapitre.

\subsection{Suites d'expressions}

Une structure \'{e}l\'{e}mentaire en \Maple\ est celle de suite d'expressions
(\textit{exprseq} en anglais), c'est \`{a} dire une succession ordonn\'{e}e
d'expressions \Maple. Entour\'{e}e d'une accolades, c'est donc un
ensemble ; entour\'{e}e de crochets, c'est une liste.
Ainsi 3,2,3 est une \textit{exprseq}, \{3,2,3\} est l'ensemble \{2,3\},
[3,2,3] est une liste (ordonn\'{e}e).

Comme \Maple\ travaille au niveau
syntaxique, $\{x,y\}$ est donc \textit{a priori} incorrectement
interpr\'{e}t\'{e} comme un ensemble \`{a} deux \'{e}l\'{e}ments, ce que montrent les commandes
\footnote{~La commande \textit{restart} permet de vider la m\'{e}moire de \Maple.
On pourrait aussi quitter \Maple\ et relancer \Maple\ ou effectuer
un $\underline{N}ew$.}

\begin{mapleinput}\mapleinline{active}{1d}{restart ;
nops(\{x,y\}) ;}{}\end{mapleinput}
\mapleresult \begin{maplelatex}\[ 2\]\end{maplelatex}
\newpage
La fonction \textit{seq} permet de g\'{e}n\'{e}rer une suite s\'{e}quence d'expressions.
(ce qui parfois incorrectement \'{e}crit "s\'{e}quence d'expressions"
\`{a} cause du terme anglais $expression\ sequence$.
Par exemple :

\begin{mapleinput}
\mapleinline{active}{1d}{ a := seq(i*i,i=1..3)  ;}{}
\end{mapleinput}
\mapleresult \begin{maplelatex}\[ a := 1, \,4, \,9 \]\end{maplelatex}
\begin{mapleinput}
\mapleinline{active}{1d}{[a] , \{a\} ;}{}\end{mapleinput}
\mapleresult \begin{maplelatex}
\[  [1, \,4, \,9]\  , \ \{1, \,4, \,9\} \]
\end{maplelatex}

\textit{seq} a trois formes. Sa syntaxe est \textit{seq(x,y)} o\`{u}
$x$ est une expression ou une fonction et $y$ une plage de variation ou
une expression. Si $f$ est une fonctio d\'{e}finie par \texttt{f := x -> x+1} alors
les expressions $seq(i+1,i=1..n)$ et $seq(f(i),i=1..n)$ sont \'{e}quivalents. Pour la
troisi\`{e}me forme, on peut \'{e}crire $seq(f(i),i=[a,b,c])$ ou $seq(f(i),i=\{a,b,c\})$.
On obtient alors $f(a),f(b),f(c)$.

Il faut donc remarquer que $seq$ ne renvoie pas
de structure mais seulement une suite d'expression (on verra plus loin que ce n'est
pas le cas de $map$). Par contre, il n'est pas possible d'\'{e}crire\footnote{~Pourquoi~?}
\texttt{j:= i=1..n ; seq(f(i),j)}.

$seq$ s'utilise pour afficher des valeurs de fonction, de suite. Si on voulait
trouver une expression qui utilise $seq$ pour afficher $1, 3, 9, 12, 14$, il
faudrait faire des hypoth\`{e}ses sur le mod\`{e}le sous-jacent. Dire ce que ces valeurs
sont celles d'un polynome en $1,2,3,4,5$ d\'{e}boucherait sur une \textit{interpolation polynomiale},
par exemple celle de $Lagrange$. Sinon, on pourrait penser \`{a} d'autres types de fonctions...

La fonction \textit{convert} permet de transformer  les ensembles et listes en
d'autres structures. Ainsi :

\begin{mapleinput}
\mapleinline{active}{1d}{convert([seq(`i`,i=1..10)],`+` ) ; }{}
\end{mapleinput}
\mapleresult
\begin{maplelatex}\[ 55 \]\end{maplelatex}

D'autres fonctions calculent aussi la somme des $n$ premiers entiers. Ainsi
\texttt{sum(i,i=1..n)} et \texttt{add(i,i=1..n)} fournissent, si $n$
est connu et poss\`{e}de une valeur num\'{e}rique, le m\^{e}me r\'{e}sultat num\'{e}rique.
Si par contre $n$ n'a pas de valeur (ce qu'on peut reproduire avec
\texttt{n:='n':}) alors $add$ ne sait plus calculer et $sum$ affiche la
valeur formelle de la somme. Ou plutot le polynome correspondant. On le reconnaitra
mieux sous sa forme factoris\'{e}e.
\newpage
Voici ce que \Maple\ effectue dans ces trois cas~:

\begin{mapleinput}
\mapleinline{active}{1d}{convert(seq(i,i=1..n),`+`) ;}{%
}
\end{mapleinput}

\mapleresult
\begin{maplettyout}
Error, unable to execute seq
\end{maplettyout}

\begin{mapleinput}
\mapleinline{active}{1d}{add(i,i=1..n) ;}{%
}
\end{mapleinput}

\mapleresult
\begin{maplettyout}
Error, unable to execute add
\end{maplettyout}

\begin{mapleinput}
\mapleinline{active}{1d}{s := sum(i,i=1..n) ;}{%
}
\end{mapleinput}

\mapleresult
\begin{maplelatex}
\[
s := {\displaystyle \frac {1}{2}} \,(n + 1)^{2} - {\displaystyle
\frac {1}{2}} \,n - {\displaystyle \frac {1}{2}}
\]
\end{maplelatex}

\begin{mapleinput}
\mapleinline{active}{1d}{factor(s) ;}{%
}
\end{mapleinput}

\mapleresult
\begin{maplelatex}
\[
{\displaystyle \frac {1}{2}} \,n\,(n + 1)
\]
\end{maplelatex}

On prendra garde \`{a} la \textit{forme inerte} \texttt{Sum}. Elle permet
seulement \`{a} \Maple\ d'afficher une expression comme~:~
$$\sum _{i=1}^{n}\ i$$


\subsection{Evaluation du temps de calcul}

La fonction $time$ permet de compter la dur\'{e}e d'ex\'{e}cution d'une commande
et on peut donc comparer la conversion en somme des fonctions sum et product
gr\^{a}ce aux instructions

\begin{mapleinput}
\mapleinline{active}{1d}{n := 200 ; }{%
}
\end{mapleinput}

\mapleresult
\begin{maplelatex}
\[
n := 200
\]
\end{maplelatex}

\begin{mapleinput}
\mapleinline{active}{1d}{i
:='i':deb:=time():sum(`i`,`i`=1..n):time()-deb ;}{%
}
\end{mapleinput}

\mapleresult
\begin{maplelatex}
\[
0
\]
\end{maplelatex}

\begin{mapleinput}
\mapleinline{active}{1d}{i
:='i':deb:=time():convert([seq(`i`,`i`=1..n)],`+`):time() -deb; }{%
}
\end{mapleinput}

\mapleresult
\begin{maplelatex}
\[
.054
\]
\end{maplelatex}

\begin{mapleinput}
\mapleinline{active}{1d}{i :='i':deb:=time():product(`i`,`i`=1..n) :
time() -deb ;}{%
}
\end{mapleinput}

\mapleresult
\begin{maplelatex}
\[
.055
\]
\end{maplelatex}

\begin{mapleinput}
\mapleinline{active}{1d}{i
:='i':deb:=time():convert([seq(`i`,`i`=1..n)],`*`):time() -deb ;}{%
}
\end{mapleinput}

\mapleresult
\begin{maplelatex}
\[
0
\]
\end{maplelatex}

La boucle pour (for) permet \'{e}galement d'effectuer des calculs
r\'{e}p\'{e}titifs, dont des sommes
et des produits :

\begin{mapleinput}
\mapleinline{active}{1d}{i :='i':deb := time() : for j from 1 to 200
do : sum(`i`,`i`=1..n) : od : time() -deb ; i := 'i' :}{%
}
\end{mapleinput}

\mapleresult
\begin{maplelatex}
\[
3.460
\]
\end{maplelatex}

\begin{mapleinput}
\mapleinline{active}{1d}{deb := time() : for j from 1 to 200 do :
product(`i`,`i`=1..n) : od : time() -deb ; i := 'i' :}{%
}
\end{mapleinput}

\mapleresult
\begin{maplelatex}
\[
14.116
\]
\end{maplelatex}

\begin{mapleinput}
\mapleinline{active}{1d}{deb := time() : for j from 1 to 200 do : s:=
0 : for i from 1 to n do : s := s + i : od : od : time() -deb ; i :=
'i' :}{%
}
\end{mapleinput}

\mapleresult
\begin{maplelatex}
\[
3.405
\]
\end{maplelatex}

\begin{mapleinput}
\mapleinline{active}{1d}{deb := time() : for j from 1 to 200 do : s:=
1 : for i from 1 to n do : s := s * i : od : od : time() -deb ; i :=
'i' :}{%
}
\end{mapleinput}

\mapleresult
\begin{maplelatex}
\[
16.972
\]
\end{maplelatex}

\begin{mapleinput}
\mapleinline{active}{1d}{deb := time() : for j from 1 to 200 do :
convert([seq(`i`,`i`=1..n)],`+`): od : time() -deb ; i := 'i' :}{%
}
\end{mapleinput}

\mapleresult
\begin{maplelatex}
\[
1.812
\]
\end{maplelatex}

\begin{mapleinput}
\mapleinline{active}{1d}{deb := time() : for j from 1 to 200 do :
convert(\{seq(`i`,`i`=1..n)\},`+`) : od : time() -deb ; i := 'i' :}{%
}
\end{mapleinput}

\mapleresult
\begin{maplelatex}
\[
2.306
\]
\end{maplelatex}

\begin{mapleinput}
\mapleinline{active}{1d}{deb := time() : for j from 1 to 200 do :
fact(n) : od : time() -deb ; i := 'i' :}{%
}
\end{mapleinput}

\mapleresult
\begin{maplelatex}
\[
0
\]
\end{maplelatex}

On en d\'{e}duit donc les vitesses (diff\'{e}rentes) d'ex\'{e}cution et quelles
fonctions il faut utiliser.


\subsection{Les listes}

Un eliste se reconnait par les crochets en d\'{e}but
et en fin de liste. Son nombre d'\'{e}l\'{e}ments est donn\'{e}
par la fonction $nops$. Nous fournissons ici
quelques exemples de manipulation sur les listes :

\begin{mapleinput}
\mapleinline{active}{1d}{L:=[seq(i,i=1..10)] ; nops(L); L[2] ; }{%
}
\end{mapleinput}

\mapleresult
\begin{maplelatex}
\[
L := [1, \,2, \,3, \,4, \,5, \,6, \,7, \,8, \,9, \,10]
\]
\end{maplelatex}

\begin{maplelatex}
\[
10
\]
\end{maplelatex}

\begin{maplelatex}
\[
2
\]
\end{maplelatex}

\mapleresult
\begin{maplelatex}
\[
n := 10
\]
\end{maplelatex}

\begin{maplelatex}
\[
L := [1, \,2, \,3, \,4, \,5, \,6, \,7, \,8, \,9, \,10]
\]
\end{maplelatex}

\begin{maplelatex}
\[
24
\]
\end{maplelatex}

Une autre fa\c{c}on de travailler sur les listes consiste \`{a} utiliser la
fonction $map$, souvent
conjointe \`{a} l'op\'{e}rateur \$ :

\begin{mapleinput}
\mapleinline{active}{1d}{map(x->x+1,[1,2,4]) ; map(x->x-1,\{1,2,4\}) ;
3$4 ; $2..5 ;}{%
}
\end{mapleinput}

\mapleresult
\begin{maplelatex}
\[
[2, \,3, \,5]
\]
\end{maplelatex}

\begin{maplelatex}
\[
\{0, \,1, \,3\}
\]
\end{maplelatex}

\begin{maplelatex}
\[
3, \,3, \,3, \,3
\]
\end{maplelatex}

\begin{maplelatex}
\[
2, \,3, \,4, \,5
\]
\end{maplelatex}

L\`{a} encore il faut se m\'{e}fier des temps d'ex\'{e}cution :

\begin{mapleinput}
\mapleinline{active}{1d}{deb := time() : for j from 1 to 200 do :
convert(map(i->i,\{$1..n\}),`+`) : od : time() -deb ; i := 'i' :}{%
}
\end{mapleinput}

\mapleresult
\begin{maplelatex}
\[
.439
\]
\end{maplelatex}

\begin{mapleinput}
\mapleinline{active}{1d}{deb := time() : for j from 1 to 200 do :
convert(map(i->i,[$1..n]),`+`) : od : time() -deb ; i := 'i' :}{%
}
\end{mapleinput}

\mapleresult
\begin{maplelatex}
\[
.549
\]
\end{maplelatex}

%
\section{Structures d'actions}  % ##
%
Une structure d'actions permet de d\'{e}router le cheminement s\'{e}quentiel
des instructions tap\'{e}es au clavier : on peut ainsi choisir entre
diff\'{e}rentes actions, "boucler" sur une suite d'actions communes
(nomm\'{e}e \textit{corps de boucle}). Nous commen\c{c}ons donc par
rajouter la structure alternative si ($if$) pour compl\'{e}ter nos actions
algorithmiques\footnote{Attention :
on peut ici se contenter de renvoyer une valeur au lieu d'ex\'{e}cuter une action,
ce qui ne manquera pas de choquer ou g\^{e}ner un programmeur "classique"}.

\begin{Text Output}

\end{Text Output}

\begin{mapleinput}
\mapleinline{active}{1d}{f:=x->if x<3 then x+1 elif x <5 then x-1
else x*x :fi: }{%
}
\end{mapleinput}

\mapleresult
\begin{maplettyout}

\end{maplettyout}

\begin{mapleinput}
\mapleinline{active}{1d}{map(f,[$1..10]) ;}{%
}
\end{mapleinput}

\mapleresult
\begin{maplelatex}
\[
[2, \,3, \,2, \,3, \,25, \,36, \,49, \,64, \,81, \,100]
\]
\end{maplelatex}

Profitons-en pour essayer de calculer des nombres int\'{e}ressants de la
bilbioth\`{e}que  "th\'{e}orie des nombres", les nombres de $Mersenne$

\begin{mapleinput}
\mapleinline{active}{1d}{? mersenne}{%
}
\end{mapleinput}

\mapleresult
\begin{maplettyout}
   ...
\end{maplettyout}

\begin{mapleinput}
\mapleinline{active}{1d}{map(numtheory[mersenne],[$1..10]) ;}{%
}
\end{mapleinput}

\mapleresult
\begin{maplelatex}
\[
[{\it false}, \,3, \,7, \,{\it false}, \,31, \,{\it false}, \,127
, \,{\it false}, \,{\it false}, \,{\it false}]
\]
\end{maplelatex}

Sachant que la fonction $isprime$ renvoie vrai si son argument est
premier, essayons de donner une expression qui affiche les nombres de mersenne
2\symbol{94}x-1 pour x de 1 \`{a} 10.

\begin{mapleinput}
\mapleinline{active}{1d}{map( x -> if isprime(2^x-1) then 2^x-1 else
false : fi ,[$1..10]) ;}{%
}
\end{mapleinput}

\mapleresult
\begin{maplelatex}
\[
[{\it false}, \,3, \,7, \,{\it false}, \,31, \,{\it false}, \,127
, \,{\it false}, \,{\it false}, \,{\it false}]
\]
\end{maplelatex}

\begin{mapleinput}
\mapleinline{active}{1d}{map( x -> if isprime(2^x-1) then 2^x-1 : fi
,[$1..10]) ;}{%
}
\end{mapleinput}

\mapleresult
\begin{maplelatex}
\[
[3, \,7, \,31, \,127]
\]
\end{maplelatex}

Math\'{e}matiquement, si on d\'{e}montre que pour avoir 2\symbol{94}x-1
premier, il faut x premier, le calcul va beaucoup plus vite :

\begin{mapleinput}
\mapleinline{active}{1d}{map( x -> if isprime(x) and isprime(2^x-1)
then 2^x-1 : fi ,[$1..10]) ;}{%
}
\end{mapleinput}

\mapleresult
\begin{maplelatex}
\[
[3, \,7, \,31, \,127]
\]
\end{maplelatex}

\begin{mapleinput}
\mapleinline{active}{1d}{b := 100 ;}{%
}
\end{mapleinput}

\mapleresult
\begin{maplelatex}
\[
b := 100
\]
\end{maplelatex}

\begin{mapleinput}
\mapleinline{active}{1d}{deb := time() : map( x -> if isprime(2^x-1)
then 2^x-1 : fi ,[$1..b]) ;: time() -deb ; i := 'i' :}{%
}
\end{mapleinput}

\mapleresult
\begin{maplelatex}
\begin{eqnarray*}
\lefteqn{[3, \,7, \,31, \,127, \,8191, \,131071, \,524287, \,
2147483647, \,2305843009213693951, } \\
 & & 618970019642690137449562111]\mbox{\hspace{201pt}}
\end{eqnarray*}
\end{maplelatex}

\begin{maplelatex}
\[
2.417
\]
\end{maplelatex}

\begin{mapleinput}
\mapleinline{active}{1d}{deb := time() : y := map( x -> if isprime(x)
and isprime(2^x-1) then 2^x-1 : fi ,[$1..b]) : time() -deb ; i := 'i'
:}{%
}
\end{mapleinput}

\mapleresult
\begin{maplelatex}
\[
.055
\]
\end{maplelatex}

On peut alors afficher ces diff\'{e}rents nombres de mersenne :

\begin{mapleinput}
\mapleinline{active}{1d}{y ; nops(y) ; length(y) ;}{%
}
\end{mapleinput}

\mapleresult
\begin{maplelatex}
\begin{eqnarray*}
\lefteqn{[3, \,7, \,31, \,127, \,8191, \,131071, \,524287, \,
2147483647, \,2305843009213693951, } \\
 & & 618970019642690137449562111]\mbox{\hspace{201pt}}
\end{eqnarray*}
\end{maplelatex}

\begin{maplelatex}
\[
10
\]
\end{maplelatex}

\begin{maplelatex}
\[
92
\]
\end{maplelatex}

\subsection{Nombres al\'{e}atoires}

Essayons maintenant de tester la qualit\'{e} du g\'{e}n\'{e}rateur de nombres
al\'{e}atoires (nombres en
fait uniform\'{e}ment r\'{e}partis) nomm\'{e} $rand$. Nous allons compter pour cela
compter avec 1000 nombres entre 1 et 100 combien sont sup\'{e}rieurs \`{a} 50.

\begin{mapleinput}
\mapleinline{active}{1d}{y := map(1+rand(100),[$1..1000]) : z :=
map(x-> if x>50 then 1 : fi , y ) : convert(z,`+`) ;}{%
}
\end{mapleinput}

\mapleresult
\begin{maplelatex}
\[
508
\]
\end{maplelatex}

\begin{mapleinput}
\mapleinline{active}{1d}{convert(  map(x-> if x>50 then 1 : fi ,
map(1+rand(100),[$1..1000]) ),`+`) ;}{%
}
\end{mapleinput}

\mapleresult
\begin{maplelatex}
\[
475
\]
\end{maplelatex}

\subsection{Boucles}

La structure tant que (while) permet de faire des boucles dont
on sort quand une  condition est remplie :

Et maintenant, apr\`{e}s la fonction select, essayer de calculer la somme
des 1/2\symbol{94}p

pour p premier, p de 2 \`{a} 1000 (on veut une valeur approch\'{e}e).

\begin{mapleinput}
\mapleinline{active}{1d}{select(isprime,[$1..100]) ;}{%
}
\end{mapleinput}

\mapleresult
\begin{maplelatex}
\[
[2, \,3, \,5, \,7, \,11, \,13, \,17, \,19, \,23, \,29, \,31, \,37
, \,41, \,43, \,47, \,53, \,59, \,61, \,67, \,71, \,73, \,79, \,
83, \,89, \,97]
\]
\end{maplelatex}

\begin{mapleinput}
\mapleinline{active}{1d}{convert([seq(1/2^p,p=select(isprime,[$1..1000
]))],`+`)   ;}{%
}
\end{mapleinput}

\mapleresult
\begin{maplelatex}
\begin{eqnarray*}
\lefteqn{
55541984819383779078505582917861220812470941339110483632047040741
\backslash } \\
 & &
86492596269018919949037019985713276932497362044695072958574306663
\backslash  \\
 & &
48111762623802011881566894929677223427450603262976280237790450114
\backslash  \\
 & &
06729127690893115446511107359587273976292484076526148943709688066
\backslash  \\
 & & 2223121657784654685552088740185806749761 \left/ {\vrule
height0.73em width0em depth0.73em} \right. \!  \!
13393857589828341511\backslash  \\
 & &
85531311325002263201756014631917009304687985462938813906170153116
\backslash  \\
 & &
49797351961982265949334114694143353148393160711539255449807219683
\backslash  \\
 & &
73218504918209718530288731776343256327963927347442727691308093729
\backslash  \\
 & &
47742658424845944895692993259632864321399559710817770957553728956
\backslash  \\
 & & 578048354650708508672
\end{eqnarray*}
\end{maplelatex}

\begin{mapleinput}
\mapleinline{active}{1d}{deb := time() :
convert([seq(1/2^p,p=select(isprime,[$1..1000]))],`+`)  : time() -deb
;}{%
}
\end{mapleinput}

\mapleresult
\begin{maplelatex}
\[
4.559
\]
\end{maplelatex}

\begin{mapleinput}
\mapleinline{active}{1d}{convert([seq(1.0/2^p,p=select(isprime,[$1..10
00]))],`+`)  ;}{%
}
\end{mapleinput}

\mapleresult
\begin{maplelatex}
\[
.4146825099
\]
\end{maplelatex}

\begin{mapleinput}
\mapleinline{active}{1d}{deb := time() :
convert([seq(1.0/2^p,p=select(isprime,[$1..1000]))],`+`)  : time()
-deb ;}{%
}
\end{mapleinput}

\mapleresult
\begin{maplelatex}
\[
.933
\]
\end{maplelatex}

\begin{mapleinput}
\end{mapleinput}


\end{document}
