diff options
Diffstat (limited to 'Master/texmf-dist/doc/latex/apl/solutions.tex')
| -rw-r--r-- | Master/texmf-dist/doc/latex/apl/solutions.tex | 198 |
1 files changed, 198 insertions, 0 deletions
diff --git a/Master/texmf-dist/doc/latex/apl/solutions.tex b/Master/texmf-dist/doc/latex/apl/solutions.tex new file mode 100644 index 00000000000..85e37305451 --- /dev/null +++ b/Master/texmf-dist/doc/latex/apl/solutions.tex @@ -0,0 +1,198 @@ + +%========================================================================== +% Solutions to above sample exercises +%========================================================================== + +%\advance\vsize by 3truecm + +\choosett{apl} + +\noindent +\header%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +\vskip 1cm + +\noindent +As the index of the neutral element we use the index origin \BX@IO@ which +usually has the value @0@. Then $S(N)= +\{0,\dots,N-1\}$, given by the vector \IO@N@. +An example on groups are the cyclic groups $({\bf Z}_n,+)$ +the group tables of which are generated by the \APL\ function @ZNPLUS@: + +\hskip\parskip\vbox{\hsize=15truecm +\begintt + @DL Z_ZNPLUS N;@BXIO +[1] @BXIO_0 +[2] Z_N@AB(@ION)@SO.+@ION + @DL +\endtt +}\smallskip + +\item{1.} The matrices represent binary operations of $S(N)$, + since they are $N\times N$-matrices with elements from + $S(N)$. They are all associative and also commutative except for + the case (b). This can be seen by the function @TEST@: + +\hskip\parskip\vbox{\hsize=15truecm +\begintt + @DL Z_TEST B +[1] " B IS A BINARY OPERATION. THE FUNCTION RETURNS A BOOLEAN 2-VECTOR +[2] " (B ASSOCIATIVE, B COMMUTATIVE) +[3] Z_(&/&/&/B[B;]=B[;B]),&/&/B=@TRB + @DL +\endtt +}\smallskip + +\item{2.} + +\hskip\parskip\vbox{\hsize=15truecm +\begintt + @DL P_X GPOWER N;I +[1] " G GLOBAL +[2] P_@BXIO @DM I_0 +[3] TEST:@GO(N<I_I+1)/0 +[4] P_G[P;X] +[5] @GOTEST + @DL +\endtt +}\smallskip + +\item{3.} + +\hskip\parskip\vbox{\hsize=15truecm +\begintt + @DL P_X BGPOWER N;IJ +[1] " G GLOBAL +[2] P_@BXIO +[3] NEXTJ:@GO(0=N,IJ_2@ABN)/0,SQX +[4] P_G[P;X] +[5] SQX:X_G[X;X] +[6] N_(N-IJ)%2 +[7] @GONEXTJ + @DL +\endtt +} + +\item{} A comment: if $i_j=0$, then the power is not increased, + but the square $x^{2^{j+1}}=(x^{2^j})^2$ is computed. + The number of iterations is $k$; $n = i_0+i_12+\cdots+i_k2^k \ge 2^k$, + when $i_k \not= 0$, and hence $k \le \log_2(n)$. + Thus, the complexity is $O(\log_2(n))$. +\smallskip + +\vfill\eject +\item{4.} + +\hskip\parskip\vbox{\hsize=15truecm +\begintt + @DL Z_A GTSGP G +[1] " RETURNS THE SUBGROUP OF G GENERATED BY A +[2] Z_,A +[3] TEST:@GO(&/&/G[Z;Z]@EPZ)/FOUND +[4] Z_Z UNION G[Z;Z] +[5] @GOTEST +[6] FOUND:Z_Z[@GUZ] + @DL +\endtt +} + +\hskip\parskip\vbox{\hsize=15truecm +\begintt + @DL Z_A UNION B;V;@BXIO +[1] V_(,A),,B +[2] @BXIO_1 +[3] Z_,CLEAN((@ROV),1)@ROV + @DL +\endtt +} + +The auxiliary function @CLEAN@ was given earlier. +\bigskip + +\item{5.} + +\hskip\parskip\vbox{\hsize=15truecm +\begintt + @DL Z_INV G +[1] " RETURNS THE VECTOR OF INVERSE ELEMENTS OF G +[2] (@BXIO=,G)/,(@ROG)@ROG[@BXIO;] + @DL +\endtt +}\smallskip + +\item{6.} + +\hskip\parskip\vbox{\hsize=15truecm +\begintt + @DL H_A BGTSGP G;Y +[1] " RETURNS THE SUBGROUP OF G GENERATED BY A +[2] H_Y_@BXIO +[3] B:@GO(0=@ROY_(,G[Y;A])MINUS H)/0 +[4] H_H UNION Y +[5] @GOB + @DL +\endtt +} + +\hskip\parskip\vbox{\hsize=15truecm +\begintt + @DL Z_A MINUS B +[1] Z_(@NTA@EPB)/A + @DL +\endtt +}\smallskip + +\item{7.} If the elements of $G_i$ have been indexed by the interval + $[0,n_i-1]$, the elements of $G_1\times G_2$ become indexed + in a natural way by the elements of the Cartesian product + $[0,n_1-1]\times[0,n_2-1]$. With the bijection + $(i,j) \mapsto in_2+j:[0,n_1-1]\times[0,n_2-1] + \longrightarrow[0,n_1n_2-1]$ + (the inverse $k\mapsto((k-(k \bmod n_2))/n_2,k \bmod n_2)$ + selects the quotient and remainder in the division by $n_2$) + we get $[0,n_1n_2-1]$ as the index set. + +\vfill\eject +\hskip\parskip\vbox{\hsize=15truecm +\begintt + @DL G_G1 PROD G2;@BXIO;I;J;IREM;JREM;N1;N2;N +[1] N_(N1_(@ROG1)[1])#N2_(@ROG2)[1] @DM I_@BXIO_0 +[2] G_(N,N)@RO0 +[3] JLOOP:J_0 +[4] CORE:G[I;J]_(G1[(I-IREM)%N2;(J-JREM)%N2]#N2)+G2[IREM_N2@ABI;JREM_N2@ABJ] +[5] @GO(N>J_J+1)/CORE +[6] @GO(N>I_I+1)/JLOOP + @DL +\endtt +} + +Example: + +\hskip\parskip\vbox{\hsize=15truecm +\begintt + (ZNPLUS 2) PROD ZNPLUS 10 + 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 + 1 2 3 4 5 6 7 8 9 0 11 12 13 14 15 16 17 18 19 10 + 2 3 4 5 6 7 8 9 0 1 12 13 14 15 16 17 18 19 10 11 + 3 4 5 6 7 8 9 0 1 2 13 14 15 16 17 18 19 10 11 12 + 4 5 6 7 8 9 0 1 2 3 14 15 16 17 18 19 10 11 12 13 + 5 6 7 8 9 0 1 2 3 4 15 16 17 18 19 10 11 12 13 14 + 6 7 8 9 0 1 2 3 4 5 16 17 18 19 10 11 12 13 14 15 + 7 8 9 0 1 2 3 4 5 6 17 18 19 10 11 12 13 14 15 16 + 8 9 0 1 2 3 4 5 6 7 18 19 10 11 12 13 14 15 16 17 + 9 0 1 2 3 4 5 6 7 8 19 10 11 12 13 14 15 16 17 18 +10 11 12 13 14 15 16 17 18 19 0 1 2 3 4 5 6 7 8 9 +11 12 13 14 15 16 17 18 19 10 1 2 3 4 5 6 7 8 9 0 +12 13 14 15 16 17 18 19 10 11 2 3 4 5 6 7 8 9 0 1 +13 14 15 16 17 18 19 10 11 12 3 4 5 6 7 8 9 0 1 2 +14 15 16 17 18 19 10 11 12 13 4 5 6 7 8 9 0 1 2 3 +15 16 17 18 19 10 11 12 13 14 5 6 7 8 9 0 1 2 3 4 +16 17 18 19 10 11 12 13 14 15 6 7 8 9 0 1 2 3 4 5 +17 18 19 10 11 12 13 14 15 16 7 8 9 0 1 2 3 4 5 6 +18 19 10 11 12 13 14 15 16 17 8 9 0 1 2 3 4 5 6 7 +19 10 11 12 13 14 15 16 17 18 9 0 1 2 3 4 5 6 7 8 +\endtt +} + +\end + + |