Basic Research on Interactive Algorithms

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

Interactive algorithm is an algorithm that allows human solver (user) to interrupt execution and input information, In the present research we investigated methods of algorithm description, relations with bilinear programming, relations with parallel algorithms, from the above point of view. We also obtained a new algorithm of sorting (ordering) data, which is called internal merge sort. Sorting, in general, is an operation of arranging data such that records are in a sequence of ascending or descending order. Our internal merge sort does not require a large working area. We made a theoretical analysis and obtained a theoretical estimation of average computing time of (internal) merge sort, This is a new result, which has not been known before. The computational time of our internal merge sort is twice as much as that of quick sort and merge sort. This result is the same as our theoretical analysis.