summaryrefslogtreecommitdiff
path: root/fonts/apl/sample.tex
blob: 85481d7c943f2d32c9f2fb9b242d69eea3902d08 (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

%============================================================================
%                         S A M P L E . T E X
%============================================================================

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