アルゴリズムのデータベース化とそれを用いたソフトウェア設計手法の研究

算法数据库创建及使用其的软件设计方法研究

• 批准号: 04219201
• 负责人: 中森 眞理雄
• 金额: $ 0.77万
• 依托单位: Tokyo University of Agriculture and Technology
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for Scientific Research on Priority Areas
• 财政年份: 1992
• 资助国家: 日本
• 起止时间: 1992 至 无数据
• 项目状态: 已结题
• 来源: https://kaken.nii.ac.jp/en/grant/KAKENHI-PROJECT-04219201/
• 关键词: アルゴリズム; 組合せ的問題; 線形計画問題; 双線形計画問題; 整列; 論理式充足可能性; グラフの同型性; データベース

よく知られたアルゴリズムを知識ベースに蓄え、組合せ的問題(グラフ理論、ネットワークフロー理論、回路網理論など)の新しいアルゴリズムを考案する助けとなるような手法を開発することを最終の目的として研究を進めた。本年度の成果は次の通りである。1.複数のデータを大小関係にしたがって1列に並べかえる問題(ソートあるいは整列)が線形計画問題として記述できることを証明した。データ数がnのとき、この線形計画問題の変数の個数はn^2、制約条件式の数は2n(別に、変数が非負であるという式がn^2)である。2.典型的なNP完全問題である理論式充足可能性判定問題が双線形計画問題として記述できることを証明した。論理式中の変数の個数がn、論理式の長さ(論理記号や括弧も含めて)がmのとき、この双線形計画問題の変数と制約条件式の数はnとmの1次式で表わされる。3.グラフの同型性を判定する問題が双線形計画問題として記述できることを証明した。グラフの点の個数がnのとき、この双葉形計画問題の変数の個数はn^2、制約条件式の数は2n(別に、変数が非負であるという式がn^2)である。4.線形計画問題の可能解の存在領域や最適解を可視化して研究に役立てるソフトウェアツールを作った。5.アルゴリズムの実行過程を可視化して研究に役立てるソフトウェアツールを作った。6.アルゴリズムベースの研究のため、アルゴリズムの記録方法の一般的形式について検討した。

The problem of knowledge accumulation and combination (theory, theory of loop network) and the problem of knowledge accumulation and combination (theory of loop network) The results of this year are reversed. 1. The problem of linear planning is described in detail. The number of variables in the linear planning problem is n^2. The number of constraints is 2n(n^2). 2. A typical NP complete problem is described in terms of sufficient possibility of theoretical formula. The number of variables in a logical expression is n, the length of the logical expression is n (logical notation brackets), the number of variables in a two-linear program problem is n, and the number of constraints in a conditional expression is n m. 3. The problem of determining the homology of a two-line project is described and proved. The number of points in a bi-lobed plan problem is n, the number of variables in a bi-lobed plan problem is n^2, the number of constraint equations is 2n(the number of variables in a bi-lobed plan problem is not negative). 4. We are working on a software tool for visualizing the existing fields and optimal solutions of possible solutions to linear planning problems. 5. Visualize the implementation process of the system and study the software. 6. The general form of the recording method of the research on the collection of files

项目成果

石嶺 寿子: "線形計画法の教育と支援する環境に関する研究" 情報処理学会アルゴリズム研究会報告. 32. 81-88 (1993)

石峰久子：《线性规划教育及支持环境的研究》日本信息处理学会算法研究组报告32. 81-88 (1993)。

曽田 忠之: "アルゴリズム研究のための環境におけるアルゴリズムアニメーション" 情報処理学会アルゴリズム研究会報告. 32. 73-80 (1993)

Tadayuki Soda：“算法研究环境中的算法动画”日本信息处理学会算法研究小组报告 32. 73-80 (1993)。