離散アルゴリズム

Last updated Unknown Edit Source

• 離散的なもの(離散構造

  離散構造

  = 的なもの 、、など を起こしがち、愚直に探すとが大変なことに は、それをアルゴリズムの工夫でなんとかす ...

  1/3/2023

  )を扱うアルゴリズムの理論と技法

• ex: 論理、集合、グラフ

  グラフ

  プロットするグラフと、のグラフの二つの意味がある このscrapboxでは、のグラフを指す 使用頻度/リンクされる価値はこっちの方が高いかなーと プロットするグラフは、とかの言葉を使う https://ja.wikipedia.org/wiki/グラフ理論 種類 密vs疎 ...

  1/3/2023

  、整数など
  • 離散構造

    離散構造

    = 的なもの 、、など を起こしがち、愚直に探すとが大変なことに は、それをアルゴリズムの工夫でなんとかす ...

    1/3/2023

    は組み合わせ爆発を起こしがち

• 計算時間

  • 速さがいかに重要か

  • ある計算に100年かかるとしたら、その人にとっては解けないことと同じ（寿命は有限）

    • 面白い考え方だなーと思った

  • 時間がかかる2つのパターン

      - これを扱うのは性質検査
    
        
    性質検査
        
    
    普通のアルゴリズム: 入力を全て読んで問題を解く
    性質検査: 入力の一部（微小な部分）だけを読んで解く
    
    という概念
        ε: 閾値の定数
        ある性質を持っていそうか、全く持っていない（性質からε-farである）かを、ある確率で判定するのが性質検査?
    
    なぜ性質検査をする?
        データーが巨大になった時はでも遅い
        ...
        
    1/3/2023
    などの分野になる
    

「離散構造処理

事例

• 影響最大化問題

  影響最大化問題

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

  1/3/2023

• 組み合わせ的相関検定

  組み合わせ的相関検定

  構造と、各ノードのデーターがある時、構造とデータにがあるかどうかの検定 「付きデータ」 ex: 都道府県の人口の変化withグラフ構造 これについて、隣接していると変化に相関があるかどうかを調べる ...

  1/3/2023