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

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

よく知られたアルゴリズムを知識ベースに蓄え、組合せ的問題(グラフ理論、ネットワークフロー理論、回路網理論など)の新しいアルゴリズムを考案する助けとなるような手法を開発することを最終の目的として研究を進めた。本年度の成果は次の通りである。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.アルゴリズムベースの研究のため、アルゴリズムの記録方法の一般的形式について検討した。