Design Methodology of Algorithms via Knowledge Base

假设一个n × n的点阵模式（图形、字母、符号等）在计算机内存中被表示为n个单词的序列，其中每个单词由n位组成。如果一个点存在于(i. j) -th位置。即，矩阵的第i行和第j列，则第i个字的第j位为1；否则，该位为0（图1）（单词最左边的位是第0位，最右边的位是第n-1位）。那么我们的问题是这样的：逆时针旋转这n个单词中的90位，即，将源的第i个单词的第j位移动到目标的（n-l-j）第i个单词的第i位。我们还考虑将图案旋转180度和270度，在垂直、水平和对角线方向反转的问题。图案的矩阵表示通常用于输出设备，如打印机和图形显示器。因此，这是一个非常关键的问题。在这个项目中，我们提出了一个0 （n log n）算法来解决这个问题。同时，我们还讨论了该算法与快速傅里叶变换的相似之处。研究了旋转算法改写规则群的代数结构，证明了该群与旋转算法群同构。

Suppose an n by n dot matrix pattern (figure, letter, symbol, etc.) is represented as a sequence of n words in a computer memory, where each word consists of n bits. If a dot exists in the (i. j) -th position. i. e., i-th row and the j-th column of the matrix, then the j-th bit of the i-th word is 1 ; otherwise, the bit is 0 (Figure 1) (the leftmost bit of a word is the 0-th and the rightmost bit is the n-1 st). Then our problem is as follows : rotate counterclockwise by 90 the bits in these n words, i. e., move the j-th bit of the i-th word of the source to the i-th bit of the (n-l-j)-th word of the destination. We also consider problems of rotating the pattern by 180 and 270, reversing in vertical, horizontal, and diagonal direction.Matrix representation of a pattern is often used in output devices such as printers and graphic displays. Therefore, this problem is a very priietical one. In this project we proposed an 0 (n log n) algorithm for this problem. Also, we discussed the analogy between this algorithm and the fast Fourier transform.We investigated the algebraic structure of the group of rewriting rules of rotating algorithms and showed that the group is isomorphic to the group of rotating algorithms.