summaryrefslogtreecommitdiff
path: root/fonts/apl/problems.tex
blob: 3f47553ea3750046b7584abbfe4f4a87558b1034 (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316

%===================================================================
% 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