イベント企画
トップコンファレンス3-1 コンピュータシステム設計およびグラフ解析
9/13 15:30-17:30
第3イベント会場

座長:宇野 裕之(大阪公立大)

15:30-15:50 講演(1) 【タイトル邦題】 仕様の機能シナリオに基づくテストケースとテストオラクルの自動生成
劉 少英(広島大学 大学院先進理工系科学研究科 教授)
【原発表の書誌情報】 Shaoying Liu, Shin Nakajima, “Automatic Test Case and Test Oracle Generation based on Functional Scenarios in Specifications for Conformance Testing”, IEEE Transactions on Software Engineering (in press), vol. 48, no. 2, pp. 691-712, 1 Feb. 2022, doi: 10.1109/TSE.2020.2999884
【概要】 Automatic testing based on specifications can significantly alleviate the workload and cost of software testing but faces a challenge of how to ensure that both the user’s concerns in the specification and possible execution paths in the program are all covered. In this paper, we put forward a Vibration-Method”(“V-Method”), for automatic generation of test cases and test oracle from model-based formal specifications. Supporting the principle of “divide and conquer”, the method provides a specific technique for generating test cases based on functional scenarios defined in the specification, test case generation criteria, automatic test case generation algorithms, and a well-defined mechanism for deriving test oracle. We elaborate on the method by discussing how initial test cases can be automatically generated, how additional necessary test cases are produced using the “vibration” technique, and how a test oracle can be automatically derived for a group of test cases.
【略歴】 2020.4 - 現在:広島大学大学院先進理工系科学研究科 教授
2000.4 - 2020.3: 法政大学情報科学部 教授
1994.4 - 2000.3: 広島市立大学情報科学部 助教授
15:50-16:10 講演(2) 【タイトル邦題】 ビアスイッチFPGA: 65nm CMOS実装とAI向けアーキテクチャ拡張
橋本 昌宜(京都大学 大学院情報学研究科通信情報システム専攻 教授)
【原発表の書誌情報】 M. Hashimoto, X. Bai, N. Banno, M. Tada, T. Sakamoto, J. Yu, R. Doi, Y. Araki, H. Onodera, T. Imagawa, H. Ochi, K. Wakabayashi, Y. Mitsuyama, and T. Sugibayashi, "Via-Switch FPGA: 65nm CMOS Implementation and Architecture Extension for AI Applications," Technical Digest of International Solid-State Circuits Conference (ISSCC), pp. 502--503, February 2020.
【概要】 ビアスイッチFPGA(VS-FPGA)は、再構成に必要な不揮発ビアスイッチを配線層に配置することで、従来のSRAM FPGAに比べて高い実装密度を実現することが可能である。本発表では、VS-FPGAの65nm試作結果および予測性能について報告する。
【略歴】 2001年3月京都大学大学院情報学研究科博士課程修了。博士(情報学)。京都大学大学院情報学研究科助手、大阪大学大学院情報科学研究科助教授・准教授・教授を経て、2021年4月より京都大学大学院情報学研究科教授。集積システム設計に関する研究、特に高信頼化設計、低電力化設計、リコンフィギャラブルコンピューティングなどの研究に従事。
16:10-16:30 講演(3) 【タイトル邦題】 頂点が適度に増加するグラフ上におけるランダムウォークの未訪問頂点数
白髪 丈晴(中央大学 理工学部情報工学科 准教授)
【原発表の書誌情報】 Kijima, S., Shimuzu, N., Shiraga, T.: How many vertices does a random walk miss in a network with moderately increasing the number of vertices?, Proc. the 2021 ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 106-122 (2021).
【概要】 ランダムウォーク(RW)は複数のアルゴリズム設計で威力を発揮する有用な確率モデルである. 一方, 時間とともに頂点が増加するグラフ上のRWに対する理論研究は殆ど行われていなかった. 本研究ではグラフの拡大する速さとRWの未訪問頂点数に対する理論的な特徴づけを行う.
【略歴】 2017年九州大学大学院システム情報科学府情報学専攻博士後期課程終了, 博士(工学). 中央大学理工学部情報工学科, 東京工業大学情報理工学院を経て, 2022年より中央大学理工学部情報工学科准教授. 離散数学, アルゴリズム理論, 中でも確率的構造と乱択アルゴリズムに関する研究に従事.
16:30-16:50 講演(4) 【タイトル邦題】 動的計画法の平均感度
隈部 壮(東京大学 大学院情報理工学系研究科数理情報学専攻第二研究室 博士二年)
【原発表の書誌情報】 Average Sensitivity of Dynamic Programming Soh Kumabe and Yuichi Yoshida In Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA'22)
【概要】 実問題に対処するには、ノイズに対して安定なアルゴリズムの設計が重要である。本研究では、動的計画法で解かれる種々の問題に対し、入力のランダムな微小変化で出力が大きく変化しないアルゴリズムを与える一般的なフレームワークを提案した。
【略歴】 2019年東京大学工学部計数工学科卒、2021年東京大学大学院情報理工学研究科数理情報学専攻修士課程卒。2022年現在、同専攻博士課程に在籍。博士二年。離散最適化・アルゴリズム・ゲーム理論などの理論研究に従事。日本学術振興会特別研究員(DC1)。ISAAC 2021 Best Student Paper Award を受賞。
16:50-17:10 講演(5) 【タイトル邦題】 有効抵抗を近似する局所アルゴリズム
吉田 悠一(国立情報学研究所 情報学プリンシプル研究系 教授)
【原発表の書誌情報】 Pan Peng, Daniel Lopatta, Yuichi Yoshida, Gramoz Goranci. Local Algorithms for Estimating Effective Resistance. Proceedings of the 27th ACM SIGKDD Conference on Knowledge Discovery & Data Mining (KDD), pp. 1329–1338, 2021.
【概要】 有効抵抗は、グラフ内の二つの頂点の類似度を測る重要な指標であり、グラフのクラスタリング、推薦システム、ネットワークの信頼性の計算などに応用がある。その重要性にもかかわらず、巨大グラフにおいて有効抵抗を正確にまたは近似的に計算する効率的なアルゴリズムの研究は進んでいない。本研究では、有効抵抗を推定するための局所的なアルゴリズムをいくつか提案する。これらは、入力グラフのうち一部しか読み込まずに近似保証のついた推定値を出力する。提案アルゴリズムの一つは、グラフの混合時間が小さい場合、頂点ペアs, t間の有効抵抗をO(poly(log n/ε))時間で誤差εで近似する。またいくつかのベンチマークデータセットを用いて実験を行い、提案アルゴリズムの性能を検証した。
【略歴】 2012年京都大学大学院情報学研究科修了。同年より国立情報学研究所特任助教。2015年より同准教授、2022年より同教授。数理的考察に基づく巨大データに対するアルゴリズムの研究に従事。