Basic Research on Interactive Algorithms

交互算法基础研究

• 批准号: 07680339
• 负责人: NAKAMORI Mario
• 金额: $ 1.47万
• 依托单位: Tokyo University of Agriculture and Technology
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for Scientific Research (C)
• 财政年份: 1995
• 资助国家: 日本
• 起止时间: 1995 至 1997
• 项目状态: 已结题
• 来源: https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-07680339/
• 关键词: interactive algorithm; algorithm; bilinear programming; parallel algorithm; sorting; internal merge sort; average computational complesity; worst case computational complexity; スケジューリング; 問題解決; 計算複雑度; ヒューマンインタフェース

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.

交互式算法是一种允许人类求解者(用户)中断执行和输入信息的算法，本文从上述角度研究了算法的描述方法、与双线性规划的关系、与并行算法的关系。我们还得到了一种新的数据排序算法，称为内部归并排序。一般而言，排序是对数据进行排列以使记录按升序或降序排列的操作。我们的内部合并排序不需要很大的工作区。进行了理论分析，得到了(内部)归并排序的平均计算时间的理论估计，这是一个以前未知的新结果。我们的内部合并排序的计算时间是快速排序和合并排序的两倍。这一结果与我们的理论分析是一致的。

项目成果

岸恵一: "分岐限定アルゴリズムの並列化における一手法" 情報処理学会第52回全国大会講演論文集. 1. 41-42 (1996)

Keiichi Kishi：“并行化分支定界算法的方法”第 52 届日本信息处理学会全国会议论文集（1996 年）。

飯田卓郎: "WWWによるアルゴリズムベースシステム" 情報処理学会第52回全国大会講演論文集. 4. 191-192 (1996)

Takuro Iida：“使用 WWW 的基于算法的系统”第 52 届日本信息处理学会全国会议论文集。4. 191-192 (1996)。

萩原 斉: "困難な問題の双線形計画問題を用いたモデル化技法" 情報処理学会 技術研究報告. MPS19. 19-24 (1998)

Hitoshi Hagiwara：“使用双线性规划问题解决难题的建模技术”日本信息处理协会技术研究报告 19-24 (1998)。

Kyoko Iwasawa: "Optimizing Method of Array Decomposition in Fortran 90" Trans.IEICE (DI). J78bI-5. 504-506 (1995)

Kyoko Iwasawa：“Fortran 90 中数组分解的优化方法”Trans.IEICE (DI)。

Kyoko Iwasawa: "Automatic Parallelization Method of Loops by conditional Region Analysis" Proc.ISTED. 1-3 (1998)

Kyoko Iwasawa：“通过条件区域分析实现循环的自动并行化方法”Proc.ISTED。