Design Methodology of Algorithms via Knowledge Base

点击翻译按钮获取中文摘要

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.