diff options
Diffstat (limited to 'Master/texmf-dist/source/fonts/apl/problems.tex')
-rw-r--r-- | Master/texmf-dist/source/fonts/apl/problems.tex | 316 |
1 files changed, 0 insertions, 316 deletions
diff --git a/Master/texmf-dist/source/fonts/apl/problems.tex b/Master/texmf-dist/source/fonts/apl/problems.tex deleted file mode 100644 index 3f47553ea37..00000000000 --- a/Master/texmf-dist/source/fonts/apl/problems.tex +++ /dev/null @@ -1,316 +0,0 @@ - -%=================================================================== -% Sample problems; solutions give examples on using APL style in TeX -% Taken from the course ``Mathematics on the Computer'', Fall 87 -%=================================================================== - -\magnification = \magstep1 - -\advance\vsize by 3truecm - -\input mssymb % for some math symbols only! This is the new - % symbol font for some standard and non-standard - % mathematical symbols. It is only used here for - % blackboard bold letters. If you dont have it, - % just define \def\Bbb{} etc. - -\input aplstyle - -\choosett{apl} - -\font\sans = amss10 -\font\sltt = amsltt10 - -\def\header{{\sans Sample problems 9.\ 10.\ 1987}} -% some of them come from Sims' ``Abstract Algebra, A Computational Approach'' -\def\APL{{\sltt APL}} - -\nopagenumbers -\tolerance = 300 -\noindent -\header - -\vskip 2cm - -\item{1.} Let $N>1$ be an integer. Show that each of the following - matrices represents a binary operation on - $S(N)$ (we set locally \BX@IO_0@.) Which of them are - associative, which commutative? - \medskip - - \itemitem{a)} @(@\IO@N)@\SO@.@\CE\IO@N@ - - \itemitem{b)} \AB@(@\IO@N)@\SO@.-@\IO@N@ - - \itemitem{c)} @N@\AB@(@\IO@N)@\SO@.+@\IO@N@ - - \itemitem{d)} @N@\AB@(@\IO@N)@\SO@.#@\IO@N@ - - \medskip -\item{} Here @x@\CE@y@ is $\max(x,y)$, @x@\AB@y@ is - $y\bmod x$ and \AB@x@ is the absolute value of $x$. - -\bigskip - -\item{2.} Write an \APL\ function @GPOWER@ that computes for a group - @G@ (global variable) the $n$-th power of a given element $x$. - (If $S(M)$ is a representation vector of @G@, then - @GPOWER@ is a map $S(M)\times \Bbb Z\to S(M)$. Simply - use iteration.) - -\bigskip - -\item{3.} (Continuing problem 2.) A faster algorithm is obtained by - decomposing $x^n$ into its 2--base form - $x^n = x^{i_0}\times x^{2i_1}\times - x^{4i_2}\times ... \times x^{{2^k}i_k}$, where $i_j\in\{0,1\}$. Show - that the complexity of this algorithm is $O(\log_2(n))$. - (Show that the number of necessary multiplications does - not exceed $2\log_2(n)$). How would you write the corresponding - function in \APL? (Note that the binary representation of $n$ - can be obtained by applying iteratively the procedure $n\bmod 2$.) - -\bigskip - -\item{4.} Write an \APL\ function @GTSGP@ that computes for a given group @G@ - (global variable) the subgroup generated by a given subset $A$. The - function @GTSGP@ has one argument (the vector @A@) and returns - a subset of the set $S(N)$ (as a vector). (Extend the set @A@ - by the group operation until @A@ becomes closed with respect - to the operation.) - -\bigskip - -\item{5.} Write an \APL\ function @INV@ that returns for a group @G@ - the vector of inverse elements as a vector $S(N)\to S(N)$ so - that the index of the inverse of $x_i$ is @(INV G)[I]@. - -\bigskip - -\item{6.} Let $(G,\theta)$ be a group and let $A$ be a subset of $G$. Program - the following algorithm in \APL\ to find the subgroup @H@ - generated by @A@. Compare the perfomance of this algorithm - with the algorithm in Problem 4. - \medskip - - \itemitem{a)} put $H$ and $Y$ equal to $\{e\}$. - - \itemitem{b)} let $Y$ be $YA\smallsetminus H$. - - \itemitem{c)} if $Y=\emptyset$, stop. - - \itemitem{d)} put $H$ equal to $H\cup Y$ and - go to (b). - - \medskip -\item{} ($e$ is the neutral element and $YA\smallsetminus H$ - is the set--theoretical difference of $YA$ and $H$. - The product $YA$ is the set $\{y\theta a: y\in Y, a\in A\}$.) - -\bigskip - -\item{7.} Write an \APL\ function @PROD@ that returns for given groups - $(G_1,\theta_1)$ ja $(G_2,\theta_2)$ the {\sl direct product} - $(G_1\times G_2,\theta_1\times\theta_2)$ as a group table. - (The binary operation in the product is $(x,y)\theta_1\times\theta_2 - (z,w) = (x\theta_1 z,y\theta_2 w)$). - -\bigskip - -\vfill\eject - -%========================================================================== -% 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 |