summaryrefslogtreecommitdiff
path: root/Master/texmf-dist/source/fonts/apl/problems.tex
diff options
context:
space:
mode:
Diffstat (limited to 'Master/texmf-dist/source/fonts/apl/problems.tex')
-rw-r--r--Master/texmf-dist/source/fonts/apl/problems.tex316
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