共同研究・競争的資金等の研究課題

2018年4月 - 2022年3月

効率性と拡張性をもつ可逆アルゴリズム族の系統的な設計と解析

日本学術振興会  科学研究費助成事業 基盤研究(C)
  • 横山 哲郎

課題番号
18K11250
配分額
(総額)
3,510,000円
(直接経費)
2,700,000円
(間接経費)
810,000円

近年、消費エネルギー最適化やプログラムのモジュラリティの向上を目的として、計算の全ステップにおいて直前の状態が一意に決まる可逆計算の研究が実施されてきた。本研究は、効率的な可逆アルゴリズム族の設計、その系統的な設計のための可逆アルゴリズム戦略の発展、および可逆プログラミング言語による実装を目指している。本年度は、二分木に関する基本アルゴリズムについて既知の様々な一般解法よりも効率的な可逆化を実現することができた。これによって問題固有の知識に基づく効率化手法がこれらのアルゴリズムにおいても有効であることを確認できた。この可逆化手法は類似するアルゴリズムにも同様にして一定程度適用することができそうである。
可逆アルゴリズムの記述とテストには申請者が形式化した言語とその可逆言語処理系を拡張して用いた。拡張された可逆プログラミング言語のオンラインインタプリタを公開しておりインターネットを経由して誰でもアイデアを試せるようにしている。研究成果は、可逆回路の設計、双方向変換、投機的実行の逆計算、および量子計算などの隣接分野における応用や異なる視点からの解釈が期待できる。
また,本年度は、命令型言語WHILEに対応する可逆プログラミング言語R-WHILEについては任意の可逆プログラミング言語と同等の計算能力があること、すなわちその可逆チューリング完全性を示した論文を発表した。本可逆言語の構造化データをもちいて可逆プログラムを記述することで研究が加速されることが期待される。

ID情報
  • 課題番号 : 18K11250