Design Methodology of Algorithms via Knowledge Base

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

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.