summaryrefslogtreecommitdiff
path: root/fonts/apl/sample.tex
diff options
context:
space:
mode:
authorNorbert Preining <norbert@preining.info>2019-09-02 13:46:59 +0900
committerNorbert Preining <norbert@preining.info>2019-09-02 13:46:59 +0900
commite0c6872cf40896c7be36b11dcc744620f10adf1d (patch)
tree60335e10d2f4354b0674ec22d7b53f0f8abee672 /fonts/apl/sample.tex
Initial commit
Diffstat (limited to 'fonts/apl/sample.tex')
-rw-r--r--fonts/apl/sample.tex124
1 files changed, 124 insertions, 0 deletions
diff --git a/fonts/apl/sample.tex b/fonts/apl/sample.tex
new file mode 100644
index 0000000000..85481d7c94
--- /dev/null
+++ b/fonts/apl/sample.tex
@@ -0,0 +1,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