湊　真一 (北海道大学)
  

  

    
題名: 膨大な個数の順列データを処理する新しい二分決定グラフ


  

  

    
アブストラクト: 「順列」は「組合せ」と並んで離散数学や計算機科学の基礎をなす重要な概念で
あり，ソーティング，順序付け，マッチング，符号化等，多くの局面に現れる．
本講演では，「πDD」（順列二分決定グラフ）と呼ぶ新しい二分決定グラフにつ
いて述べる．πDDは，多数の順列を要素として含む順列集合をコンパクトかつ一
意に表現し，演算処理を効率よく行える．中でも，全ての順列の合成を求める直
積演算は強力で実用的である．本講演ではπDDの基本的なデータ構造と演算アル
ゴリズムを示し，さらに簡単な応用例として，あみだくじの解析およびルービッ
クキューブの解析の実験結果を示す．πDDは数十億もの膨大な個数の順列を現実
的な計算時間と記憶量で列挙し，さらに順列集合の演算を適用して様々な制約充
足問題を解くことができる．暗号システムの設計や解析にも活用できるのではな
いかと期待している．




  
  

    

  


     
Shin-ichi Minato (Hokkaido University) 
  

  

    
Title: New Decision Diagrams for Manipulating Very Large-Scale Data of Permutations



  

  

    
Abstract: Permutations and combinations are a couple of basic concepts in
elementary combinatorics. Permutations appear in various problems such
as sorting, ordering, matching, coding, and many other real-life
situations. In this talk, we present a new decision diagram "PiDD," for
compact and canonical representation of a set of permutations. PiDD has
efficient algebraic set operations such as union, intersection, and
especially, it has a special Cartesian product operation to generate all
possible composite permutations for given two sets of permutations. This
is a beautiful and powerful property of PiDDs. We present the data
structures and the basic operation algorithms for PiDDs. We also show
two application examples of PiDDs: designing permutation networks and
analysis of Rubik's Cube. The experimental results show that
PiDD-based method can explore billions of permutations in a feasible
time and space, using simple algebraic operations for solving the
problems. We also hope that PiDDs will be useful for designing and
analyzing a kind of cryptographic systems.



  
    

[Back ]