木メモ - Negative/Positive Thinking
はじめに 立派な庭師になるために、木についてちょっと調べてみたので、まとめておく。 木(構造)とは 閉路を含まない無向グラフを「森」という 連結な森を「木」という 与えられた頂点が全てつながっていて、閉路を含んでいない 閉路を含まない有向グラフは「DAG(Directed acyclic graph)」という ある頂点を根(Root)としてもつ木を「根付き木」という 2点v,wが辺を持ち、vの方が根に近い場合、vを「親」、wを「子」という 2点v,wについて、根とvとの経路にwが存在する場合、wはvの「先祖」、vはwの「子孫」という 子を持たない頂点を「葉」という 根から各点への経路の長さ(1辺を1とする)を「高さ」という 各点の子の数が常にn子の木を「n分木」という 連結グラフGについて、閉路ができなくなるまで辺を除去し続けると、残ったものは「全域木」となる 根付き木を探索などに用いるこ
焼きなまし法で遊ぶ - Negative/Positive Thinking
はじめに 焼きなまし法について、どんな挙動で、どこを気をつけないといけないのかよくわかってないので、遊んでみる。 焼きなまし法メモ : http://d.hatena.ne.jp/jetbead/20111014/1318598381 評価関数 簡単のために、4次関数を使って、初期位置は小さい山の外側(x0=2.0)に配置してみる。 【関数の形】 (google) (wolfram alpha) http://www.wolframalpha.com/input/?i=-3x%5E4%2B3x%5E3%2B10x%5E2-10x%2B15 best_x = argmax f(x)を求めたい。 コード #include <iostream> #include <cmath> //xorshift // 注意: longではなくint(32bit)にすべき unsigned long xor1
正規分布と正規乱数 - chmod 777 myknowledge
ノイズを付加する場合に確率密度関数として正規分布を用いることがある。 これを実際にやってみたくなったので実現方法を調べてみた。自分への覚え書きとして以下に示す。 正規分布の説明は以下を参照。 http://ja.wikipedia.org/wiki/%E6%AD%A3%E8%A6%8F%E5%88%86%E5%B8%83 正規分布を表す式は以下。 正規分布に従うノイズを発生させるためには、上式における x をノイズ量として x 軸上の各点におけるノイズを f(x) で表される確率で発生させればよい。 一方、多くのプログラミング言語で提供されているのは一様乱数(ある有限の区間を区切って、その区間内で全ての実数が同じ確率（濃度）で現れるような乱数 by Wikipedia)を発生させるメソッドである。C言語でいえば stdlib.h で提供される rand() が相当する。 0より大きく(0は
ALSIP2011に参加して簡潔データ構造の話を聴いて来ました - EchizenBlog-Zwei
香川県高松市にて開催されたALSIP2011(Second Workshop on Algorithms for Large-Scale Information Processing in Knowledge Discovery)に参加してきた。 簡潔データ構造で有名なRajeev Raman先生、NIIの定兼先生、PFIの岡野原さんが招待講演をして下さるということで以前から注目していた。 招待講演に加えて興味深い10本の発表がありとても楽しめた。私の勉強不足もあって初めて知ることが非常に多く勉強になった。簡単に内容をメモしておく(理解不足のため間違ったことを書いていたらすみません)。 今回の会議で最も興味深かったのがgrammer-based compressionというもので、これは例えばX=ababという文字列があったときにX1=a,X2=b,X3=X1X2,X=X3X3という感じで
竹内関数が音楽的に聴こえる理由について考えてみた - aike’s blog
前回のエントリーが予想以上に反響が大きくてびっくりしています。 プログラミング言語好きの僕にとってはヒーローみたいなすごいプログラマーたちにツイートしてもらってびびっていたところ、今日になって竹内先生ご本人からのコメントをいただいてしまって本気で腰抜かしそうになりました。せっかくなので自分なりに竹内関数が音楽的に聴こえる理由についての考えを書いてみます。 ■ちょっとした工夫 最初に少し種明かしをすると、より音楽的になるように以下のような工夫をしています。 ・ダイアトニックスケール（白鍵）だけを使用し調性の外れた音が出ないようにした ・最小値(-1)をレにわりあてることで少し寂しげなドリアンスケールにした （とはいえ-1の出現頻度が低いのでミからはじまるフリジアンスケール的かも） ・オートアルペジオ、テンポ、音色の設定でミニマルミュージック風にした 上記のことをおこなうと、ただの乱数でもわり
レーベンシュタイン距離とN-gramモデルのアルゴリズム。それは擬似Google Suggestっぽい何か。 - Bug Catharsis
きっかけは レーベンシュタイン距離 - shin5papaの日記 http://d.hatena.ne.jp/shin5papa/20090311/1236745197 レーベンシュタイン距離とN-gramモデルで、擬似的なGoogle Suggestレーベンシュタイン距離を使うことによって、擬似的にGoogle先生の「もしかして」とか、 Google Suggestっぽいことができそうかなーと思って、面白そうなのでお勉強してみた。 PHPでは標準で関数があるのかー。んー、面白いですねコレ。ということで、さっそくC#で書いてみることにしました。 ただ、このレーベンシュタイン距離のみの判定だけでは、距離が等しい結果が複数あるような場合の結果が、 イマイチ納得のゆくものにはならなかったので、更に N-gram *1による共起頻度での判定も併用することにしました。 Wikipedia - レーベ
C++: 編集距離を求めるアルゴリズム
編集距離(edit distance)とは二つの文字列がどの程度異なっているかを示す数値であり、レーベンシュタイン距離(Levenshtein distance)を指すことが多い。文字の挿入、削除、置換それぞれを一つの操作として必要な操作の最小数を求めるものだ。例えば、kittenとsittingの編集距離を求める場合、下記のように3回の操作でkittenをsittingに変更できるので編集距離は3となる。 1. sitten (k を s に置換） 2. sittin (e を i に置換） 3. sitting (g を挿入) そこで今回は編集距離を求める複数のアルゴリズムについてC++で実装してみた。 動的計画法 編集距離を求めるもっとも一般的なアルゴリズムは、動的計画法(dynamic programming)だろう。計算時間はO(mn)であり、手軽だ。C++で書いたコードを下に示
P2Pの専門知識ゼロから独自DHTを実装評価するまでの学習方法と参考資料まとめ - 情報科学屋さんを目指す人のメモ（FC2ブログ版）
何かのやり方や、問題の解決方法をどんどんメモするブログ。そんな大学院生の活動「キャッシュ」に誰かがヒットしてくれることを祈って。 P2P、特にDHTの前提知識が無い状態から、オリジナルDHTアルゴリズムを実装・評価できるようになるまでの学習方法と参考資料をまとめました。 基本的なアルゴリズムの仕組みから、実装評価に用いるツールキットの使い方までを短期間で学習することが出来ます。 「P2Pに関する卒論を書こうと思っている人」や「P2Pアプリケーションの開発前に、アルゴリズムをテストしたい人」、「なんとなくP2Pアルゴリズムに興味が出た人」などにぴったりだと思います。また、研究室での後輩教育用資料にするのも良いと思います。実際に使いましたし。 ここで紹介する資料一覧は以下の通りです。 資料１：「ChordアルゴリズムによるDHT入門」 資料１ーオプション１：「DHTアルゴリズムSymphony
頻出典型アルゴリズムの演習問題としてよさげなやつ - kyuridenamidaのチラ裏
効率的な別解とか存在する問題もあるけど演習によさそうなやつをピックアップ。そのアルゴリズムじゃないと解けないわけではないって問題も多いので注意。(ただ演習するのには都合が良いかなと)※個人的難易度をつけてみました。とても主観的な難易度付けなので気にせず解いてみてください。深さ優先探索・Balls[☆]・Sum of Integers[☆]・The Number of Island[☆]・Block[★]幅優先探索・Mysterious Worm[★]・Cheese[★]・Seven Puzzle[★☆]・Stray Twins[★★]・Deven-Eleven[★★]・Summer of Phyonkichi[★★☆]ワーシャルフロイド法(For 全点対最短路問題)・Traveling Alone: One-way Ticket of Youth[★]・A reward for a Car
アルゴリズムの勉強のしかた - きしだのHatena
この記事で、アルゴリズムの勉強はアルゴリズムカタログを覚えることじゃないよということを書きました。 プログラムの理論とはなにか アルゴリズムの勉強というのは、スポーツで言えば腕立て伏せや走り込みみたいな基礎体力を養うようなもので、「ソートなんか実際に自分で書くことないだろう」とかいうのは「サッカーは腕つかわないのに腕立ていらないだろう」とか「野球で1kmも走ることなんかないのに長距離の走り込みいらないだろう」とか言うようなものです。 Twitterでアルゴリズムの勉強とはなにかと尋ねられて、「アルゴリズムの基本的なパターンを知って、それらの性質の分析のしかたをしって、いろいろなアルゴリズムでどのように応用されているか知って、自分が組むアルゴリズムの性質を判断できるようになることだと思います。 」と答えたのですが、じゃあ実際どういう本で勉強すればいいか、ぼくの知ってる本からまとめてみました。
この機会にマスターしようぜ、正規表現、構文図、オートマトン - 檜山正幸のキマイラ飼育記 (はてなBlog)
正規表現と構文図について解説します。オートマトンについても詳しく述べます。オートマトン・スゴロクで遊びましょう！ 世間でよく知られている／使われている概念・方法にはこだわらず、僕（檜山）の感覚で一番わかりやすいと思われる筋書きと用語法／図式法を使って説明します。この記事に目を通して“感じ”が掴めたら、形式言語理論の教科書を読み始めることが出来るでしょう。 [追記]この記事の内容に対する具体例は、「正規表現とオートマトン：なんだ簡単じゃん、JavaScriptによる実装」にあります。[/追記] 内容： 正規表現 正規表現の例 構文図 基本記号 連接 選択 省略可能 繰り返し ストレートワイヤーによるレイアウト調整 有限状態オートマトン 有限状態オートマトンの実行 バックトラックと先読み スゴロクとオートマトン コマをたくさん使うスゴロクと並列処理 非決定性オートマトンと決定性オートマトン 正
第6回アルゴリズム勉強会に参加しました - nokunoの日記
というわけで、第6回アルゴリズム勉強会に初めて参加してきました。アルゴリズム勉強会 : ATND 場所は六本木黒崎ビルの株式会社Speeeさんの会議室。以前GREEが入っていた（今はアリエルネットワークになっている）フロアの下らしいです。勉強会の内容はアルゴリズムイントロダクションを順番に読んでいくもので、自分は原著の分厚いIntroduction to Algorithmsを持って行って参加しました。今回は第5章「確率的解析と乱択アルゴリズム」でした。確率が出てくるので、慣れていないと躓きやすい＆実装があまり出てこないので、飽きやすい部分です。自分も一年くらい前に12章まで読んだときは飛ばしてしまいました。なお、この本は版によって内容と構成が大きく違うので、旧版をお持ちの方はご注意ください。雰囲気としては、発表なしの輪読会なので本文を朗読したり黙々と練習問題をこなしたりホワイトボードで解
Eigen
Get it The latest stable release is Eigen 3.4.0. Get it here: tar.bz2, tar.gz, zip. Changelog. The latest 3.3 release is Eigen 3.3.9. Get it here: tar.bz2, tar.gz, zip. Changelog. The latest 3.2 release is Eigen 3.2.10. Get it here: tar.bz2, tar.gz, zip. Changelog. The unstable source code from the master is there: tar.bz2, tar.gz, zip. To check out the Eigen repository using Git, do: git clone ht
STOC 2011 論文紹介 - Preferred Networks Research & Development
吉田です。最近ACM Symposium on Theory of Computing (STOC)という学会に投稿していた論文が受理されました。論文はECCCにアップロードしています。STOCは次回が43回目の開催となる理論計算機科学(要するにアルゴリズムと計算量を扱う分野)の中では最高峰の学会です。例えばCookが初めてNP完全性という概念を提唱したのもSTOCです。 今年は4年に一度のFederated Computing Research Conference (FCRC)というイベントがあり、STOCの他にもEC (ゲーム理論、オークションなど), CCC (計算量)、PODC, SPAA (共に分散/並列アルゴリズム)など18個の学会が同時開催されます。逆に言うと18個のうちのどれかに論文が受理されれば全体に参加出来るお得なイベントで(勿論お金さえ出せば参加は可能ですが)、僕も
MinHashによる高速な類似検索 - Preferred Networks Research & Development
年が明けてもう一ヶ月経ちましたね．岡野原です． 今日はMinHashと呼ばれる手法を紹介します．これは特徴ベクトルの高速な類似検索に利用することができます(クローラーの文脈だとShingleとして知られている）． 今や世の中のあらゆる種類のデータが，高次元のバイナリベクトルからなる特徴ベクトルで表されて処理されるようになってきました．例えば文書データであれば文書中に出現する単語やキーワードの出現情報を並べた単語空間ベクトル（Bag of Words）で表し，画像データも，SIFTをはじめとした局所特徴量を並べた特徴ベクトル（とそれをSkecth化したもの）として表せます．行動情報や時系列データも特徴量をうまく抽出する．グラフデータもFast subtree kernels[1]と呼ばれる方法で非常に効率的に特徴ベクトルに変換することができ，グラフの特徴をよく捉えることができるのが最近わかっ
乱択アルゴリズム紹介(3SATのO(1.334^n)時間アルゴリズム) | Preferred Research
\(\mathcal{C} = (x \vee y \vee z) \wedge (\neg x \vee y \vee z) \wedge (y \vee \neg z \vee w)\). 上の例だと、例えば\(\alpha(x) = \mathrm{true}, \alpha(y) = \mathrm{true}, \alpha(z) = \mathrm{false}, \alpha(w) = \mathrm{false}\)とすれば全ての節を充足することが出来ます。 3SATはNP完全なので全てのNPに属す問題は3SATとして解けるのですが、そうでなくても多くの問題から”自然”に3SATが導出されます。なので3SATを解くアルゴリズムを考えましょう。一番自明なアルゴリズムは次のようになると思います。変数の数を\(n\)、節の数を\(m\)としましょう。
初ビット列がでるまでの期待時間 - tsubosakaの日記
kinabaさんのブログの 「無限ビット列を作ったときに最初に "001" が並ぶインデックスの期待値は 8。では、"000" なら？」という問題に対して、マルチンゲールを使った解説をしてみます。 いま無限に生成されるビット列に対して次に何がでるかを賭けるギャンブルを考えます。配当はフェアな賭けで賭け金の2倍返しとします。ここで000が出現したら賭けは終了するとします。 このとき毎時刻ギャンブラーが1$持ってきてつぎのように賭けます。 1. はじめに0が出ることに賭けて、勝ったら次へ、そうでなければ終了 2. 再び0が出ることに前の儲け2$を全額賭ける、勝ったら次へ、そうでなければ終了 3. 再び0が出ることに前の儲け4$を全額賭ける、勝ったら000が出てるので賭け自体が終了、そうでなければ終了この話はたとえば010がでる期待値を考えるときは2.のところで0にではなく1に賭けることになりま
Bayesian Setsの特許について - のんびり読書日記
別にブログに書いてもしょうがないかなーと思っていたのですが、同じような目に遭う方がいるかもしれないのでちょろっとだけ書いておきます。 先日Stupaという関連文書検索システムを公開したのですが、その中で使用していたBayesian Setsというアルゴリズムが既に特許を取得されているため、公開を停止してほしいってメールが来ました。以前に公開したBayesian SetsのCPANモジュールAlgorithm::BayesianSetsも同様に下ろしてほしいとのことでした。特許の内容は以下のページに書いてあります。 http://www.wipo.int/pctdb/en/wo.jsp?WO=2007063328 特許の出願者がBayesian Setsの論文の著者と大学の機関のようなので、おそらく論文発表の前に出願したのではないかと思います。請求項の内容などをすべて詳細に読んだわけではない
講演その２と今後の予定 - Yasuo Tabeiの日記
東京工業大学の杉山研究室でSketchSort法に関する講演をさせていただきました。杉山研はいろいろな国からの留学生が多くゼミでの公用語は英語だそうです。企業と同様に大学の研究室単位でもグローバル化しているようです。ツッコミも激しかった。杉山研での発表のためにスライドを少し修正したので再アップしました。またまた英語で発表したので英語のスライドになっております。 Sketch sort sugiyamalab-20101026 - publicView more presentations from tbyasu. 今後の予定 11月4日〜6日に行われるibis2010にて以下のタイトルでポスター発表します。 「大規模化合物のスケッチ表現によるクラスタリング」 http://ibis-workshop.org/2010/index.html SketchSort法を2千５百万からなる化合物デ
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
乱択アルゴリズム紹介(Bloom Filter) - Preferred Networks Research & Development