グラフ
種類
- 密vs疎
- 密はほとんど現実にはない (=応用時に生まれにくい)
- Physical vs Non-Physical
マイナー操作
- 同じ性質を保ったままグラフをシンプルにしていく事
Search
種類
マイナー操作
普通のアルゴリズム: 入力を全て読んで問題を解く 性質検査: 入力の一部（微小な部分）だけを読んで解く という概念 ε: 閾値の定数 ある性質を持っていそうか、全く持っていない（性質からε-farである）かを、ある確率で判定するのが性質検査? なぜ性質検査をする? データーが巨大になった時はでも遅い 性質検査なら、線形時間どころか定数時間でやることもできる 問題がな場合にも、性質検査はできる可能性がある 厳密に問題を解く前の枝刈り（可能性のないものをリジェクト）に使える 他分野との関連 近似アルゴリズムは、大体「」みたいな掛け算による保証をする 性質検査は保証のしかたがちょっと違う ただ、性質検査の技法を応用できることがある 分散アルゴリズムはランダムに等の一部をみて出力を決める? 考え方が性質検査と近い? 性質検査の良いところ アルゴリズムは簡単、より大変なのは そこは専門家が頑張ればいい 大域的/な構造と局所的/な構造の関係を明らかにする いろいろな対象で性質検査は研究されている ゴール: 定数時間で解ける性質のを得る いくつかの研究では成功している（すごい） ただ当然そもそも全ての入力は読めないから、的な手法を使っている...
なぜ関数プログラミングは重要か を読んだ後に読みたい , , とか あるデーターからどのようなデーターを「生成」するかに注目するもの それ以外の/とかだと、どう「加工」するかに注目してる 理想的な構成要素 (PCF) 基本的なデーターとその演算 変数 条件分岐 関数の定義 再帰的関数の定義 関数の使用 プログラムをとして表せる 値、分岐、演算子、関数はグラフの頂点として表す 変数は点として表す いくつかのルールがある 基本は 箱にぶつかったら、一度引き返す 変数はぶつかったら、それに繋がってる全てに具体化して値を与え...
...BDD: Dont'careを省略、密な論理関数に向いてる ZDD: 負の出現を省略、疎な論理関数に向いてる 論理関数からBDD(もしくはZDD)を作りたい場合 BDTを作ってから圧縮すれば、当然作れる ただ、この圧縮を毎回やってると/が大変なことになる なので、直接から圧縮されたBDDを生成したい やりかた 方式: 各変数を小さいBDDとして、二つのBDD同士をAND,NOT,OR演算で組み合わせて最終的なBDDを作る 方式: BDTを作る過程で、（1を使った回数を数えたりして）作りながら圧縮していく 技術のフレームワーク上では、BDD,ZDD等のは「索引構造」にあたる 論理演算、数え上げ、線形関数最大化、サンプリングなどの「基本演算」のやりかた shannon decompositionで分解して、常に1/0を返すにたどり着くまで再帰的に演算していく Shannon Decomposition: 要は、二分木の一分岐を数学的に表したもの との演算を、decompositionした上で的にうことができる 応用先 初期は集積回路の設計問題のためのアルゴリズム 最近は処理能力の向上によって、めちゃでかいが扱えるように 経路探索 スーパーマーケットの売り上げデータから良く売れる商品パターンを探す データーから危険な要素の組み合わせを調べる 問題の解法もを使う n=26までの世界記録を争う話がすごい楽しそうw......
あとでかく なんか変にややこしい表現になってるきがする、もっとシンプルな言い方ありそう 何かの概念とそれらの繋がりを人が考える時、 単語とか言語で概念が分割されている それらの関係がみたいな感じで認識されている それが整理整頓されるとツリー構造になったりするけど、もっと元にある構造はグラフ Scrapboxだと、それをそのまま管理できる それぞれの概念に対してページを作る それらがつながる /shokai/脳内をそのまま出力したい