Bluemo's Brain

Search

離散構造処理

Last updated Unknown Edit Source

フレームワーク
- 離散構造処理技術 = 索引構造 + 基本演算
- 索引構造とは
  - 例: 決定グラフ (ZDD, BDD
    
    BDD
    
    二分決定 = 0/1の組み合わせに対して0/1を返す物論理関数をBDDで表せる https://ja.wikipedia.org/wiki/二分決定図より BDDで、AND, OR, XORなどが表現できる ...
    
    1/3/2023
    
    とか)
  - ただの「論理関数を表す二分木」だったものを、圧縮して扱いやすくした「索引」がBDD
    
    BDD
    
    二分決定 = 0/1の組み合わせに対して0/1を返す物論理関数をBDDで表せる https://ja.wikipedia.org/wiki/二分決定図より BDDで、AND, OR, XORなどが表現できる ...
    
    1/3/2023
    
    、ZDDなど
- 基本演算とは
  - 索引構造を扱う演算
  - ex: 決定グラフの基本演算: 論理演算、数え上げ、線形関数最大化、サンプリング、etc
- 応用する方法: 問題を既知の索引構造に落とし込んで、それに対していろいろな基本演算を組み合わせる

#離散アルゴリズム

Backlinks

影響最大化問題

影響最大化問題

 と情報伝達が与えられて、「影響拡散」 $σ(S)$ を最大化させる $σ(S)$ は複雑なのでBDDでは解けない([NP困難]])が、 $1-1/e$ [[近似]は可能 #近似アルゴリズムあるノードSから別のノードへのパスの集合は起こすなので、これをに落とし込むことによって回避技術のパターン(フレームワーク)に沿う決定グラフ（BDD含む）のを用いれば、σ(S)の最大化ができる #離散アルゴリズム...

1/3/2023
組み合わせ的相関検定

組み合わせ的相関検定

 構造と、各ノードのデーターがある時、構造とデータにがあるかどうかの検定「付きデータ」 ex: 都道府県の人口の変化withグラフ構造これについて、隣接していると変化に相関があるかどうかを調べる ex: 地域別のの感染者数withグラフ構造の地理データ $K(x)$ : ある値以下の観測値の最大? K(x)=kのP値: の元でK(x)>=kとなる確率 P値の高さによって、帰無仮説(相関なし説)を否定する(相関があるなら) 技術のパターンに沿って、計算大変なところをBDDに落とし込む...

1/3/2023
離散アルゴリズム

離散アルゴリズム

 的なもの()を扱うの理論と技法 ex: 、、、などはを起こしがち速さがいかに重要かある計算に100年かかるとしたら、その人にとっては解けないことと同じ（寿命は有限）面白い考え方だなーと思った時間がかかる2つのパターンこれを扱うのはなどの分野になる「技術」と「離散アルゴリズム」の言葉の関係がよくわからない事例 ...

1/3/2023
BDD

BDD

...BDD: Dont'careを省略、密な論理関数に向いてる ZDD: 負の出現を省略、疎な論理関数に向いてる論理関数からBDD(もしくはZDD)を作りたい場合 BDTを作ってから圧縮すれば、当然作れるただ、この圧縮を毎回やってると /が大変なことになるなので、直接から圧縮されたBDDを生成したいやりかた方式: 各変数を小さいBDDとして、二つのBDD同士をAND,NOT,OR演算で組み合わせて最終的なBDDを作る方式: BDTを作る過程で、（1を使った回数を数えたりして）作りながら圧縮していく技術のフレームワーク上では、BDD,ZDD等のは「索引構造」にあたる論理演算、数え上げ、線形関数最大化、サンプリングなどの「基本演算」のやりかた shannon decompositionで分解して、常に1/0を返す $f$ にたどり着くまで再帰的に演算していく Shannon Decomposition: $fa = (\lnot xi \land f{a0}) \lor (xi \land f_{a1})$ 要は、二分木の一分岐を数学的に表したもの $fa$ と $f{a\prime}$ の演算を、decompositionした上で的にうことができる応用先初期は集積回路の設計問題のためのアルゴリズム最近は処理能力の向上によって、めちゃでかいが扱えるように経路探索スーパーマーケットの売り上げデータから良く売れる商品パターンを探すデーターから危険な要素の組み合わせを調べる問題の解法もを使う n=26までの世界記録を争う話がすごい楽しそうw......

1/3/2023