- 平澤巧望,
篠埜 功,
プログラミングの写経型学習の欠点を補う翻訳学習法の提案,
日本ソフトウェア科学会第41回大会(2024年度) 講演論文集,
2b-3-R, 立命館大学大阪いばらきキャンパス（OIC）,
2024年9月9日〜12日（2024年9月10日 平澤巧望が現地で発表）.
- 宮島健太,
篠埜 功,
デバッグ演習への意欲向上を目的とした順位付けをしない得点提示式演習の提案,
日本ソフトウェア科学会第41回大会(2024年度) 講演論文集,
2b-4-R, 立命館大学大阪いばらきキャンパス（OIC）,
2024年9月9日〜12日（2024年9月10日 宮島健太が現地で発表）.
-
Md Monir Ahammod Bin Atique,
Kwanghoon Choi,
Isao Sasano,
Hyeonah Moon,
Improving LLM-based Code Completion Using LR Parsing-Based Candidates,
10th International Symposium on Symbolic Computation in Software Science
— Work in Progress Workshop
(SCSS 2024),
Tokyo, Japan, Aug 28-30, 2024.
(presented by Atique on Aug 28, 2024)
- 岡本祐希,
篠埜 功,
Rustにおける複数の関数定義をトレイト境界を用いて1つにまとめるアルゴリズムの提案,
情報処理学会 第150回プログラミング研究発表会
(PRO150),
徳島県郷土文化会館およびzoom,
2024年8月8日〜9日（2024年8月8日 岡本祐希がzoomで発表）.
- 平澤巧望,
篠埜 功,
ブロック型言語のブロック内に用いられる文字の種類の違いがプログラミング学習に与える影響の調査 — 日本語と英語を事例として,
情報処理学会 第150回プログラミング研究発表会
(PRO150),
徳島県郷土文化会館およびzoom,
2024年8月8日〜9日（2024年8月8日 平澤巧望が現地で発表）.
ツールのサービスおよびソースコード
- 岡本祐希,
篠埜 功,
Rustにおけるトレイトの実装の衝突を避けるための新たなトレイト境界の構文の提案,
情報処理学会 第149回プログラミング研究発表会
(PRO149),
zoom,
2024年6月13日（2024年6月13日 岡本祐希発表）.
ツールのソースコード
-
Kwanghoon Choi,
Sooyeon Hwang, Hyeonah Moon,
Isao Sasano,
Ranked syntax completion with LR parsing,
The 39th ACM SIGAPP Symposium on Applied Computing
(SAC 2024),
pp. 1242-1251, Avila, Spain, April 8-12, 2024.
(presented by Kwanghoon Choi on April 11, 2024)
-
Isao Sasano,
Kwanghoon Choi,
A text-based syntax completion method using LR parsing and its evaluation,
Science of Computer Programming, Volume 228, 102957, June 2023.
-
劉源,
篠埜 功,
凝集型階層クラスタリングによる偶然の成功テストケースの検出,
電子情報通信学会総合大会, D-3-6,
芝浦工業大学 大宮キャンパス,
2023年3月7日〜10日.（2023年3月8日劉源発表）
検出ツールのソースコード
-
飯田尚之,
篠埜 功,
構文単位のギャップを考慮した関数型言語に対するtype3コードクローン検出手法の提案および実装,
電子情報通信学会総合大会, D-3-7,
芝浦工業大学 大宮キャンパス,
2023年3月7日〜10日.（2023年3月8日飯田尚之発表）
コードクローン検出ツールのソースコード
-
美馬隆志,
篠埜 功,
敵対的サンプルに対しても堅牢な制御フローグラフを用いた機械学習によるAndroidマルウェア検出システム,
情報処理学会第85回全国大会,
7D-03,
電気通信大学,
2023年3月2日〜4日.（2023年3月4日美馬隆志発表）
マルウェア検出システムのソースコード
- 平澤巧望, 篠埜 功,
光るキーボードを用いた写経型プログラミング学習の支援,
情報処理学会第142回プログラミング研究発表会, 2022-4-(5),
広島市立大学サテライトキャンパス,
2023年1月12日〜13日（2023年1月13日平澤巧望発表）.
情報処理学会論文誌プログラミング（PRO）Vol. 16, No. 2, pp. 1-27. 2023年6月.
ツールのソースコード
-
菊池敬裕,
篠埜 功,
遺伝的アルゴリズムによる消費エネルギーを考慮した移動ロボットの複数回通過を指定可能なオフライン経路生成方式の提案および実装,
電子情報通信学会総合大会, D-8-8,
オンライン開催,
2022年3月15日〜18日.（2022年3月15日菊池敬裕発表）
経路生成およびロボット動作プログラムのソースコード
-
吉祥,
篠埜 功,
リファクタリング可視化ツールの提案および実装,
電子情報通信学会総合大会, D-3-4,
オンライン開催,
2022年3月15日〜18日（2022年3月15日吉祥発表）
可視化ツールのソースコード
-
Nobuhiro Kasai,
Isao Sasano,
Server-Side Computation of Package
Dependencies in Package-Management Systems,
The 19th Asian Symposium on Programming Languages and Systems
(APLAS 2021),
Physical in Chicago, Illinois, United States
and virtual via zoom, October 17-18, 2021.
Lecture Notes in Computer Science, Vol. 13008,
pp. 62-79, Springer.
video
(presented on zoom by Kasai on Oct 17, 2021)
- 今泉良紀,
篠埜 功,
Messer: マクロ展開過程を表示できる C++17 に準拠したCプリプロセッサの対話型環境,
コンピュータソフトウェア, 38巻2号, pp. 27-45, 2021年5月. 岩波書店.
-
亀井亮汰,
篠埜 功,
摂動を用いたランダムなコード生成手法の提案及び有効性評価,
電子情報通信学会総合大会, D-15-8,
オンライン開催,
2021年3月9日〜12日（2021年3月12日亀井発表）
web applicationのソースコード
-
上條典嗣,
篠埜 功,
関数型言語における深層学習を用いたtype4コードクローン検出,
電子情報通信学会総合大会, D-3-6,
オンライン開催,
2021年3月9日〜12日（2021年3月12日上條発表）.
-
笠井信宏,
篠埜 功,
ユースケースに合ったパッケージマネージャ開発の支援を目指したパッケージマネージャの依存関係解決方式に関する考察,
第23回プログラミングおよびプログラミング言語ワークショップ
(PPL2021)
論文集(インフォーマルな論文集),
オンライン開催,
2021年3月9日〜11日（2021年3月11日笠井発表）.
- 亀井亮汰, 吉塚大浩,
篠埜 功,
古宮誠一,
写経型学習の欠点を補う摂動を用いた理解度確認問題生成手法 --- 二項演算子の事例に基づく有効性評価,
コンピュータソフトウェア, 38巻1号, pp. 111-139, 2021年2月. 岩波書店.
web applicationのソースコード
第27回研究論文賞
-
Isao Sasano,
Kwanghoon Choi,
A text-based syntax completion method using LR parsing,
ACM SIGPLAN 2021 Workshop on Partial Evaluation and Program Manipulation
(PEPM 2021),
pp. 32-43, Virtual meeting, Denmark, January 18-19, 2021.
(video,
presented on zoom by Sasano on Jan 18, 2021)
Source code of the tool
A language example (An arithmetic language)
Another language example (A small subset of Standard ML)
-
吉塚大浩,
篠埜 功,
マルチスレッドを学習するためのメモリアクセス可視化ツールの提案および実装,
情報処理学会
第132回プログラミング研究発表会,
zoom,
2021年1月13日〜14日.（2021年1月14日 吉塚発表）
web applicationのソースコード
-
Isao Sasano, Kei Morisawa,
Yutaka Hirakawa,
Personalized spoiler detection in tweets by using
support vector machine,
Journal of Advances in Technology and Engineering Research
Vol. 5, Issue 5, pp. 219-226, October 2019. TAF Publishing.
2nd International Conference on Artificial Intelligence,
Software Engineering, Information Technology and Applied Sciences
(ASIA 2020),
Sydney, Australia, March 14-15, 2020.
(presented by Sasano on March 14, 2020)
Abstract proceedings
-
上野裕太郎,
篠埜 功,
マーケットバスケット分析における注意機構を用いた商品推薦手法の提案および実装,
情報処理学会第82回全国大会,
4N-03,
金沢工業大学 扇が丘キャンパス,
2020年3月5日〜7日（2020年3月6日上野発表、オンライン会議）.
-
Isao Sasano,
An approach to generate text-based IDEs for syntax
completion based on syntax specification,
ACM SIGPLAN 2020 Workshop on Partial Evaluation and Program Manipulation
(PEPM 2020),
pp. 38-44, New Orleans, Louisiana, United States, January 20, 2020.
(video,
presented by Sasano on January 20, 2020)
An Emacs-mode based on the approach presented in the paper
-
笠井信宏,
篠埜 功,
パッケージマネージャにおける依存パッケージの衝突の解消方法
提案システムの考案及び実装,
情報処理学会
第126回プログラミング研究発表会,
国立情報学研究所（学術総合センター）,
2019年10月30日〜10月31日（2019年10月31日笠井発表）.
-
Kentaro Kikuchi,
Takahito Aoto,
Isao Sasano,
Inductive theorem proving in non-terminating rewriting systems and its application to program transformation,
21st International Symposium on Principles and Practice of Declarative Programming
(PPDP 2019),
pp. 1-14, Porto, Portugal, October 7-9, 2019.
(presented by Kikuchi on October 7, 2019)
- 亀井亮汰, 吉塚大浩,
篠埜 功,
古宮誠一,
写経型学習の欠点を補う摂動を用いた理解度確認問題生成手法 --- 二項演算子の事例に基づく有効性評価,
日本ソフトウェア科学会第36回大会講演論文集,
46-L, 芝浦工業大学芝浦キャンパス, 2019年8月27日〜29日.（2019年8月29日吉塚発表）
web applicationのソースコード
-
Yutaka Hirakawa,
Fumiya Hirose,
Isao Sasano,
PVRotate: An improved vibration-based user authentication method,
International Journal of Future Computer and Communication,
Volume 8, Number 2, pp. 50-54, June 2019.
4th International Conference on Systems, Control and Communications
(ICSCC 2018),
Nanyang Technological University, Singapore,
December 28-30, 2018.
-
菊池 健太郎,
篠埜 功,
無限のデータを含む等式に対する帰納的定理証明
,
日本ソフトウェア科学会第35回大会(2018年度)講演論文集,
PPL3-1-L, 大阪大学コンベンションセンター, 2018年8月29日〜31日.（8月30日菊池発表）
-
Shigeki Suwa,
Hiroaki Fukuda,
Isao Sasano,
Liquid: A concurrent calculus with declaring first-order asynchronous functions,
Trends in Functional Programming 2018
(TFP 2018),
Gothenburg, Sweden, June 11-13, 2018. (presented by Fukuda on June 11, 2018)
-
諏訪重貴,
福田浩章,
篠埜 功,
Liquid - 非同期一階関数による並行計算体系,
情報処理学会第80回全国大会,
6J-05,
早稲田大学 西早稲田キャンパス,
2018年3月13日〜15日（2018年3月15日発表）.
-
矢ノ口裕貴,
篠埜 功,
ニューラルネットワークを用いた麻雀の捨て牌危険度推定における過学習の影響,
情報処理学会第80回全国大会,
2M-04,
早稲田大学 西早稲田キャンパス,
2018年3月13日〜15日（2018年3月13日矢ノ口発表）.
-
今泉良紀,
篠埜 功,
解析表現文法に基づくC++のパーサーコンビネーター実装の実行速度の比較,
情報処理学会
第118回プログラミング研究発表会,
東京工業大学 大岡山キャンパス,
2018年2月28日〜3月1日（2018年2月28日今泉発表）.
-
Yutaka Hirakawa,
Ayaka Shimoda,
Isao Sasano, Kazuo Ohzeki,
Improvements in a puzzle authentication method
,
The 10th International Conference on Computational Intelligence
and Software Engineering
(CiSE 2018),
Bangkok, January 5-7, 2018. (presented on January 6, 2018)
Journal of Computer Science and Communications,
Vol. 6, No. 1, pp. 12-20, 2018. Scientific Research Publishing.
-
今泉良紀,
篠埜 功,
マクロ処理の実装に適したパックラットパーサーコンビネーターの設計と実装,
情報処理学会
第114回プログラミング研究発表会,
静岡県総合社会福祉会館シズウエル,
2017年6月8日〜9日（2017年6月8日今泉発表）.
-
東 拓磨,
篠埜 功,
C言語プログラムを対象とした効率の良い盗用検知手法の提案および実装,
情報処理学会第79回全国大会,
7H-05,
名古屋大学 東山キャンパス,
2017年3月16日〜18日（2017年3月18日東発表）.
-
矢ノ口裕貴,
篠埜 功,
ニューラルネットワークを用いた麻雀の捨て牌危険度推定,
情報処理学会第79回全国大会,
6P-06,
名古屋大学 東山キャンパス,
2017年3月16日〜18日（2017年3月18日矢ノ口発表）.
-
座間 翔,
篠埜 功,
初期配置が指定された場合における高難易度数独問題の自動生成手法の提案および実装,
情報処理学会 第37回ゲーム情報学研究会,
早稲田大学,
2017年3月7日〜8日（2017年3月7日座間発表）.
この論文の手法に基づいた問題生成プログラム
-
Tsubasa Matsushita,
Isao Sasano,
Detecting code clones with gaps by function applications,
ACM SIGPLAN 2017 Workshop on Partial Evaluation and Program Manipulation
(PEPM 2017),
pp. 12-22, Paris, France, January 16-17, 2017. (presented by Sasano on January 16, 2017)
Code clone detection tool based on the algorithms presented in the paper
-
白楊,
篠埜 功,
LR構文解析のエラー回復機能を用いたキーワード補完機能の系統的導出,
情報処理学会
第109回プログラミング研究発表会,
浜松市福祉交流センター,
2016年6月9日〜10日（2016年6月10日白楊発表）.
この論文の方式に基づいたキーワード補完システム
-
松下 翼,
篠埜 功,
関数適用によるギャップを考慮したコードクローンの検出および除去に関する研究,
第18回プログラミングおよびプログラミング言語ワークショップ
(PPL2016)
論文集(インフォーマルな論文集),
岡山県玉野市たまの温泉 ダイヤモンド瀬戸内マリンホテル,
2016年3月7日〜9日（2016年3月9日松下発表）.
この論文の方式に基づいたコードクローン検出ツール
-
座間 翔,
篠埜 功,
初期配置が指定された場合に適した数独問題生成手法の提案および実装,
情報処理学会 第35回ゲーム情報学研究会,
電気通信大学,
2016年3月8日〜9日（2016年3月8日座間発表）.
この論文の手法に基づいた問題生成プログラム
-
東 拓磨,
篠埜 功,
C言語プログラムを対象とした盗用検知手法の提案および実装,
情報処理学会第78回全国大会,
7H-02,
慶應義塾大学 矢上キャンパス,
2016年3月10日〜12日（2016年3月12日東発表）.
-
Isao Sasano,
A tool for visualizing buffer overflow with
detecting return address overwriting,
BICT 2015 Special Track on Modularization for Practical Software Engineering
(MPSE2015),
pp. 438-441, New York City, New York, United States, December 3-5, 2015.
ACM Digital Library.
(presented by Sasano on December 5, 2015)
This paper is also available here.
-
Isao Sasano,
Toward modular implementation of
practical identifier completion on incomplete program text,
BICT 2014 Special Track on Modularization for Practical Software Engineering
(MPSE2014),
pp. 231-234, Boston, Massachusetts, United States, December 1-3, 2014.
ACM Digital Library.
(presented by Sasano on December 2, 2014)
An Emacs-mode based on the approach presented in the paper
Author's version:
Copyright ©ICST, 2014. This is the author's version of the work.
It is posted here by permission of ICST for your personal use.
Not for redistribution. The definitive version was published
in the ACM digital library.
-
青木史勇,
篠埜 功,
C言語における記憶域期間と有効範囲を考慮したメモリの可視化,
情報処理学会第76回全国大会,
1L-1,
東京電機大学 東京千住キャンパス,
2014年3月11日〜13日（2014年3月11日青木発表）.
-
Isao Sasano,
Takumi Goto,
An approach to completing variable names for implicitly typed functional languages,
Higher-Order and Symbolic Computation,
Volume 25, Issue 1, pp. 127-163, August 2013.
Springer.
(This is a journal version of the paper in PEPM 2012 below.)
-
天野秀亮,
篠埜 功,
杉本 徹,
ニューラルネットワークによる数独の難易度判定手法の提案,
人工知能と知識処理研究会(AI),
九州大学 伊都キャンパス, 2012年11月26日.
電子情報通信学会技術研究報告, Vol. 112, No. 319, AI2012-17, pp. 13-18, 2012年11月.
-
篠埜 功,
大堀 淳,
SML#へのC言語の埋め込み,
コンピュータソフトウェア,
Vol. 29, No. 2, pp. 193-203, 2012年4月. 岩波書店.
-
Harukazu Igarashi,
Masato Handa,
Seiji Ishihara,
Isao Sasano,
Agent Control in Multiagent Systems: Reinforcement Learning of Weight Parameters in Particle Swarm Optimization,
芝浦工業大学研究報告理工系編,
56巻1号1頁〜8頁, 2012年3月31日. 芝浦工業大学.
-
Takumi Goto,
Isao Sasano,
An approach to completing variable names for implicitly typed functional languages,
ACM SIGPLAN 2012 Workshop on Partial Evaluation and Program Manipulation
(PEPM 2012),
pp. 131-140, Philadelphia, Pennsylvania, USA, January 23-24, 2012.
An Emacs-mode based on the algorithm presented in the paper
Author's version:
Copyright ©ACM, 2012. This is the author's version of the work.
It is posted here by permission of ACM for your personal use. Not for redistribution.
The definitive version was published in
ACM SIGPLAN 2012 Workshop on Partial Evaluation and Program Manipulation (PEPM'12),
January 23-24, 2012, Philadelphia, Pennsylvania, USA,
http://doi.acm.org/10.1145/2103746.2103771.
-
五十嵐 治一,
半田 雅人,
石原 聖司,
篠埜 功,
マルチエージェントシステムにおける行動制御 --- PSOにおける重み係数の強化学習,
電子情報通信学会論文誌,
Vol. J94-D, No. 10, pp. 1612-1621, 2011年10月.
-
Yota Kogure,
Isao Sasano,
Masaomi Kimura,
A Topic Maps Query Language supporting Composite and Recursive Queries,
12th International Symposium on Advanced Intelligent Systems
(ISIS 2011),
SA1-3,
LA VIE D'OR Resort, Suwon, Korea,
September 28-October 1, 2011.
-
篠埜 功,
胡 振江,
日高 宗一郎,
稲葉 一浩,
加藤 弘之,
中野 圭介,
GRoundTramによるATLの双方向化の実現,
日本ソフトウェア科学会第28回大会(2011年度)講演論文集,
7C-2, 沖縄県那覇市 沖縄産業支援センター・沖縄県市町村自治会館, 2011年9月27日〜29日.
-
Soichiro Hidaka,
Zhenjiang Hu,
Kazuhiro Inaba,
Hiroyuki Kato,
Kazutaka Matsuda,
Keisuke Nakano,
Isao Sasano,
Marker-directed optimization of UnCAL graph transformations,
21st International Symposium on Logic-Based Program Synthesis and Transformation
(LOPSTR 2011),
Odense, Denmark, July 18-20, 2011.
Lecture Notes in Computer Science, Vol. 7225,
pp. 123-138, Springer Verlag.
-
Isao Sasano,
Zhenjiang Hu,
Soichiro Hidaka,
Kazuhiro Inaba,
Hiroyuki Kato,
Keisuke Nakano,
Toward bidirectionalization of ATL with GRoundTram,
International Conference on Model Transformation
(ICMT 2011),
Zurich, Switzerland, June 27-28, 2011.
Lecture Notes in Computer Science, Vol. 6707,
pp. 138-151, Springer Verlag.
-
小暮 陽太,
篠埜 功,
木村 昌臣,
合成に関して閉じているトピックマップ問い合わせ言語の提案と実装,
2011年度人工知能学会全国大会(第25回)
(JSAI2011),
3G3-4, 岩手県盛岡市 いわて県民情報交流センター,
2011年6月1日〜3日.
-
後藤 拓実,
篠埜 功,
暗に型付けられた関数型言語に対する変数名補完方式の提案,
第13回プログラミングおよびプログラミング言語ワークショップ
(PPL2011)論文集(インフォーマルな論文集),
pp. 216-230, 北海道札幌市 定山渓ビューホテル, 2011年3月9日〜11日.
この論文の手法に基づいたEmacsモード (lambda-mode version 0.10)
-
後藤 拓実,
篠埜 功,
多相型言語の変数名補完を行うEmacsモードの開発,
第12回プログラミングおよびプログラミング言語ワークショップ
(PPL2010)論文集
(インフォーマルな論文集),
pp. 177-190, 香川県 琴平温泉, 2010年3月3日〜5日.
この論文の手法に基づいたEmacsモード (lambda-mode version 0.06)
-
Atsushi Ohori,
Isao Sasano,
Lightweight Fusion by Fixed Point Promotion,
The 34th ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages
(POPL 2007),
pp. 143-154, Nice, France, January 17-19, 2007. ACM Press.
Author's version
-
Isao Sasano,
Mizuhito Ogawa,
Zhenjiang Hu,
Maximum Marking Problems with Accumulative Weight Functions,
International Colloquium on Theoretical Aspects of Computing
(ICTAC2005),
Hanoi, Vietnam, October 17-21, 2005.
Lecture Notes in Computer Science, Vol. 3722,
pp. 562-578, Springer Verlag.
Author's version
-
Mizuhito Ogawa,
Zhenjiang Hu,
Isao Sasano,
Iterative-Free Program Analysis,
Proceedings of the 8th ACM SIGPLAN International Conference on
Functional Programming
(
ICFP2003 ),
pp. 111-123, Uppsala, Sweden, August 25-29, 2003. ACM Press.
Author's version
Abstract
Program analysis is the heart of modern compilers. Most control flow
analyses are reduced to the problem of finding a fixed point in a
certain transition system, and such fixed point is commonly computed
through an iterative procedure that repeats tracing until
convergence. This paper proposes a new method to analyze programs
through recursive graph traversals instead of iterative procedures,
based on the fact that most programs (without spaghetti goto) have
well-structured control flow graphs, graphs with bounded tree width.
Our main techniques are; an algebraic construction of a control flow
graph, called SP Term, which enables control flow analysis to be
defined in a natural recursive form, and the Optimization Theorem,
which enables us to compute optimal solution by dynamic programming.
We illustrate our method with two examples; dead code detection and
register allocation. Different from the traditional standard
iterative solution, our dead code detection is described as a simple
combination of bottom-up and top-down traversals on SP
Term. Register allocation is more interesting, as it further
requires optimality of the result. We show how the Optimization
Theorem on SP Terms works to find an optimal register allocation as
a certain dynamic programming.
-
Isao Sasano,
Generation of Efficient Algorithms for Maximum Marking Problems,
Ph. D. thesis, University of Tokyo, 2002.
Abstract
In existing work on graph algorithms, it is known that a linear time
algorithm can be derived mechanically from a logical formula for a
class of optimization problems. But this has a serious problem that the
derived algorithm has huge constant factor. In this work, we redefine
this problem on recursive data structures as a maximum marking problem
and propose method for deriving a linear time algorithm for that. In
this method, specification is given using recursive functions instead
of logical formula, which results in a practical linear time
algorithm. This method is mechanical and in fact, based on this
deriving method, we make a system which automatically generates a
practical linear time algorithm from specification for a maximum
marking problem.
-
横山 哲郎,
篠埜 功,
胡 振江,
武市 正人,
変換戦略の記述に基づくプログラムの自動生成システムの実装,
情報処理学会論文誌, Vol. 43, No. SIG 3(PRO 14), pp. 62-77,
2002年3月.
-
Isao Sasano,
Zhenjiang Hu,
Masato Takeichi,
Mizuhito Ogawa,
Derivation of Linear Algorithm for Mining Optimized Gain Association Rules,
コンピュータソフトウェア, Vol. 19, No. 4, pp. 39-44, 2002年7月. 岩波書店. (in English)
Abstract
Data mining, which is a technology for obtaining useful knowledge from
large database, has been gradually recognized as an important subject.
Algorithms for data mining have to be efficient since target database
is often huge, and various kinds of efficient algorithms for data
mining are individually investigated. This paper shows that an
efficient linear time algorithm for mining optimized gain association
rules can be systematically derived from a simple specification by
reducing it to an instance of the {\it maximum marking problem}. Our
approach not only automatically guarantees the correctness of the
derived algorithm, but also is easy to derive new algorithms for
modification of the problem.
-
Isao Sasano,
Zhenjiang Hu,
Masato Takeichi,
Generation of Efficient Programs for Solving Maximum Multi-Marking
Problems,
Workshop on the Semantics, Applications, and Implementation of
Program Generation
(SAIG 2001),
Firenze, Italy, September 6, 2001. Lecture Notes in
Computer Science, Vol. 2196, pp. 72-91, Springer Verlag.
Author's version
Abstract
Program generation has seen an important role in a wide range of
software development processes, where effective calculation rules
are critical.
In this paper, we propose a more general calculation rule for
generation of efficient programs for solving maximum marking
problems. Easy to use and implement, our new rule gives a
significant extension of the rule proposed by Sasano {\em et al.},
allowing multiple kinds of marks as well as more general description
of the property of acceptable markings. We illustrate its
effectiveness using several interesting problems.
-
篠埜 功,
胡 振江,
武市 正人,
小川 瑞史,
ナップサック問題およびその発展問題の統一的解法,
コンピュータソフトウェア,
Vol. 18, No. 2, pp. 59-63, 2001年3月. 岩波書店.
概要
組合せ最適化問題の代表的問題の１つであるナップサック問題は, NP困難であ
るが, 重みが整数のみの場合には動的計画法による多項式時間アルゴリズムが
知られている. しかし, 入力データにリスト, 木等の構造を導入して構造に関
する制約条件（たとえば互いに隣合わない等）を加えると, 効率のよいアルゴ
リズムを考えるのは容易ではない. 本論文では, 入力データが再帰構造を持つ
ナップサック問題を統一的に扱い, 仕様からの効率のよいアルゴリズム導出法
を提案する.
-
篠埜 功,
胡 振江,
武市 正人,
小川 瑞史,
最大重み和問題の線形時間アルゴリズムの導出,
コンピュータソフトウェア,
Vol. 18, No. 5, pp. 1-16, 2001年9月. 岩波書店.
概要
入力として与えられる再帰データ中の, ある性質を満たす要素集合の中で, 重
み和が最大のものを求める, 最大重み和問題の線形時間アルゴリズムの導出法
に関する研究が行われているが, 計算量の定数係数が実用にならないほど大き
くなるという問題点があった. 本論文においては, 係数の小さい実用的線形時
間アルゴリズムの導出法を提案し, その有効性を示すため, 木の最大連結部分
和問題, 制限付きナップサック問題の線形時間アルゴリズムの導出を行う.
- 国際会議版:
Isao Sasano,
Zhenjiang Hu,
Masato Takeichi,
Mizuhito Ogawa,
Make it Practical: A Generic Linear-Time Algorithm for Solving
Maximum-Weightsum Problems,
Proceedings of the Fifth ACM SIGPLAN International
Conference on Functional Programming
(ICFP 2000),
pp.137-149, Montreal, Canada, September 18-20, 2000. ACM Press.
Author's version
Abstract
In this paper we propose a new method for deriving a practical
linear-time algorithm from the specification of a
maximum-weightsum problem: From the elements of a data structure $x$,
find a subset which
satisfies a certain property $p$ and whose weightsum is maximum.
Previously proposed methods for automatically generating
linear-time algorithms are theoretically appealing,
but the algorithms generated are hardly useful in practice
due to a huge constant factor for space and time.
The key points of our approach are to express the property $p$ by a
{\em recursive\/} boolean function over the structure $x$ rather than
a usual logical predicate and to apply program transformation
techniques to reduce the constant factor.
We present an {\em optimization theorem}, give a calculational
strategy for applying the theorem, and demonstrate the
effectiveness of our approach through several nontrivial examples
which would be difficult to deal with when using the methods
previously available.
-
国内ワークショップ版(インフォーマルな論文集):
第2回プログラミングおよびプログラミング言語ワークショップ論文集
(PPL'00),
pp. 14-25, 静岡県 浜名湖舘山寺温泉, 2000年3月20日〜22日.
- インフォーマルなワークショップで発表:
The Third Program Transformation Workshop
(PTW'00), Hakone, Japan, March 15-17, 2000.
-
篠埜 功,
胡 振江,
武市 正人,
グラフの探索関数の再帰的定義と変換,
コンピュータソフトウェア, Vol. 17, No.3, pp.2-19, 2000年5月.
概要
グラフアルゴリズムを再帰的に記述し, プログラム変換を行おうとする試みが
これまでにいくつかなされているが, それらは深さ優先探索を対象としており,
提案されている変換規則も複雑である. 本論文では, 深さ優先探索をその特別
の場合として含むグラフの一般的探索を行う関数を再帰的に定義する. この関
数をhylomorphismと呼ばれる形に変換することにより, 融合変換やその他の各
種の変換を行うことができ, 効率的なアルゴリズムを導出することができる.
本稿ではさらに, グラフの一般的探索関数を関数型言語Haskellによって実現
する方法を示す.
-
篠埜 功,
胡 振江,
武市 正人,
構成的手法によるグラフアルゴリズムの導出,
日本ソフトウェア科学会第15回大会論文集, pp.269-272, 電気通信
大学, 1998年9月8日〜11日.
概要
効率のよいアルゴリズムの設計を人間の思考で行うことは大変な労力を要し、
その正しさの証明は別途行う必要がある。それに対し、単純なプログラムに正
しさを保ったプログラム変換を施すことにより、効率が良くかつ正しいプログ
ラムを得るという手法がある。リスト、木を扱うアルゴリズムの設計にプログ
ラム変換を用いるという研究は数多くなされてきているが、グラフアルゴリズ
ムの設計に関してはあまり行われていない。本論文では、構成的に表現された
グラフ上でのプログラムの変換規則を提示し、それを用いて最短経路問題を解
く効率的なアルゴリズムの関数プログラミングによる表現を単純な仕様から導
出する。
