Algo党紹介ページ
アルゴリズムとデータ構造の勉強に最適なBDDとは
Binary Decision Diagram (BDD)とは、論理関数をコンパクトに表現し、効率良く扱うデータ構造。ハードウェアの設計・検証や、制約充足問題を解くために利用される。再帰、ハッシュ、キャッシュ、オブジェクト指向などの基本的なアルゴリズムやデータ構造の集大成である。
さらに、応用として文字列集合や順列集合を表現する発展手法も提案、利用されている。本研究室で別途行なっている量子やハードウェアなどの分野の研究にも活用可能であり、その活用範囲は幅広い。
BDDに関する研究としては以下の様なものが考えられます。
BDDの大規模処理・高速処理を実現
BDDの並列化処理、ストリーミング処理手法を研究し、大規模なBDD処理を実現する方法や、高速処理方法を研究する。
既存手法では実現できなかったような大規模な回路設計や問題解決への活用を目指す。
新しいBDDの応用方法の提案
文字列集合を表すSeqBDDや、量子回路を表すDDMFの応用方法の発見を目指す。
Algo党ではアルゴリズムの理論を考え、それをプログラミングしていく。そのため、頭で新しい理論を考えて、それを実際にプログラムとして実装する能力が身につく。BDDは基礎的なアルゴリズム、データ構造の集大成であるため、それらの手法について勉強し、実装する力をつけることができる。
さらに、応用分野が幅広いため、その分野と組み合わせて研究を行う場合、その分野についても学び、研究することができる。
- GPUでBDDの並列処理
- SeqBDDを用いた文字列処理
- 量子回路を表現するDDMFからの量子回路合成
- BDDを用いたアルゴリズム学習システムの実現
- BDD演算の高速化手法の考案
- BDDを用いた耐故障ハードウェアの設計
-
BDDを用いた論理回路の最適化検証
-
BDDと圧縮技術との関連性の研究
卒研ではこんなことをしました
- 青木 洋士, “Sequence BDDを利用した文字列連想配列”
- 森 紘志, “ストリーム形式のTrie木を用いた文字列集合演算”
- 山本 勝也, “BDDにおける再帰アルゴリズムの学習支援システム”
- 伊藤洋平,“SeqBDD における 最長共通部分列・部分文字列アルゴリズム”
- 伊坂萌,”BDD を理解するための 学習支援システムの改善と評価”
Algorithm党についてさらに詳しく知りたい方は下のプレゼンテーションをご参照ください！