文献

J-GLOBAL ID：201402204757721305   整理番号：14A1464298

「フカシギの数え方」から広がるアルゴリズムの理工学-二分決定グラフによる離散構造処理と広がる応用分野-3.順列の圧縮列挙索引化とソーティング

著者 (2件)： 川原純 (奈良先端科学技術大学院大) ,  湊真一 (北大 大学院情報科学研究科)
資料名： 電子情報通信学会誌  (Journal of the Institute of Electronics, Information and Communication Engineers)
巻： 97  号： 12  ページ： 1086-1090  発行年： 2014年12月01日 
JST資料番号： F0019A  ISSN： 0913-5693  資料種別： 逐次刊行物 (A)
記事区分： 解説  発行国： 日本 (JPN)  言語： 日本語 (JA)

抄録/ポイント： 基礎的な離散構造の一つである順列(置換)は,ソーティングや順序付け,マッチング,レイアウト,符号化等,多くの実用的な問題で現れる。近年提案されたπDDは,多数の順列の集合を圧縮された状態で保持するデータ構造であり,二つの順列集合の和集合や共通集合を求める演算,二つの順列集合から任意に要素を取り出して積をとって得られる集合の計算等,各種集合演算をサポートする。本稿では,ルービックキューブの最小手順の計算やあみだくじの線の引き方の数え上げを題材に,πDDの基礎的な事柄について解説し,順列集合の演算の威力を見ていく。(著者抄録)

シソーラス用語： *索引 ,  *データ圧縮 ,  *ソーティング ,  *順列 ,  データ構造 ,  集合演算 ,  数え上げ理論
準シソーラス用語： 順列索引

分類 (2件)： その他の情報処理  (JE15050M) ,  グラフ理論基礎  (IA02020S)

引用文献 (11件)：

• S. Minato, “PiDD : A new decision diagram for efficient problem solving in permutation space,“ Proc. the 14th International Conference on Theory and Applications of Satisfiability Testing (SAT'11), Lect. Notes Comput. Sci., vol. 6695, pp. 90-104, 2011.
• 湊真一,“二分決定グラフによる離散構造処理の概観“信学誌,vol.97,no.12,pp.1074-1079,Dec.2014.
• B. Yao, H. Chen, C.K. Cheng, and R.L. Graham, “Floorplan representations : Complexity and connections,“ ACM Trans. Des. Autom. Electron. Syst., vol. 8, no. 1, pp. 55-80, 2003.
• Y. Inoue, T. Toda, and S. Minato, “Implicit generation of pattern-avoiding permutations by using permutation decision diagrams,“ IEICE Trans. Fundamentals, vol. E97-A, no. 6, pp. 1171-1179, June 2014.
• M. Soeken, R. Wille, S. Minato, and R. Drechsler, “Using PiDDs in the design of reversible circuits (work-in-progress) ,“ Reversible Computation, 4th International Workshop RC 2012, Revised Papers, Lect. Notes Comput. Sci., vol. 7581, pp. 197-203, 2013.

タイトルに関連する用語 (9件)： フカ ,  シギ ,  アルゴリズム ,  二分決定グラフ ,  離散構造 ,  応用 ,  順列 ,  索引 ,  ソーティング