著者

酒井 政裕 今井 健男

出版者

日本ソフトウェア科学会

雑誌

コンピュータ ソフトウェア (ISSN:02896540)

巻号頁・発行日

vol.32, no.1, pp.1_103-1_119, 2015-01-26 (Released:2015-02-11)

---

SAT問題は,命題論理式の充足可能性問題,すなわち命題変数を含む論理式に対し,その論理式を真にするような命題変数への値の割り当てが存在するかを決定する問題である.SATは古典的なNP完全問題であり,計算量的には難しい問題であるものの,近年のアルゴリズムの改良とハードウェアの進化によって著しい高性能化が実現された結果として,様々な分野への応用が行われている.本稿ではSATにまつわる研究で現在活発な領域として,関連する問題クラスへの応用やそれにまつわる研究分野との間の交流について,調査し,紹介する.

著者

酒井 政裕

出版者

日本ソフトウェア科学会

雑誌

コンピュータ ソフトウェア (ISSN:02896540)

巻号頁・発行日

vol.34, no.1, pp.1_62-1_66, 2017-01-25 (Released:2017-03-25)

著者

今井 健男 酒井 政裕 萩谷 昌己

出版者

日本ソフトウェア科学会

雑誌

コンピュータ ソフトウェア (ISSN:02896540)

巻号頁・発行日

vol.30, no.2, pp.2_207-2_226, 2013-04-25 (Released:2013-08-25)

---

本稿では,プログラムの事前条件推定を行う新たな手法を提案する.本手法では,プログラムのテキストから生成した述語の集合とプログラムに相当する論理式,および事後条件の否定の連言を作り,そのMinimal Unsatisfiable Core(MUC)から事前条件を求める.MUCは一般的に複数存在するが,本手法ではまずMUCを列挙し,その中から事前条件として適格で,かつ最も弱い条件を選択する.こうして得られる事前条件は理想的な最弱条件ではないが,与えられた述語群の組み合わせの中で最も弱いという点で,我々はこれを「準最弱」な事前条件と呼ぶ.我々は,C言語向け有界検査ツールCForgeを援用し,上記手法を実現するツールSMUCEを試作した.その上で,教科書的なアルゴリズムを実装するC言語関数9個に,2種類の事後条件と共に適用し,人手で求めた事前条件との比較による評価を行った.結果,延べ18個中10個において,人手で求めた事前条件と同等か,より弱い条件が推定され,提案手法が原理上,実用的な事前条件を推定できることが確認できた.

著者

丸地 康平 酒井 政裕 進 博正

雑誌

研究報告ソフトウェア工学(SE)

巻号頁・発行日

vol.2013-SE-179, no.17, pp.1-8, 2013-03-04

---

本論文では,シーケンス制御プラグラミング言語に適した新しいカバレッジ基準 MTC を提案する.MTC は,必要となるテストケース数を抑えつつ,効果的なテストを実現するためのカバレッジ基準であり,論理回路におけるトグル網羅とソフトウェアにおける MC/DC 網羅の両性質を併せ持つことを特徴とする.ミューテーションテストによる評価実験により,MTC の有効性を確認した.