実践・最強最速のアルゴリズム勉強会 第二回講義資料(ワークスアプリケーションズ & AtCoder)
1. This document provides explanations for the AtCoder Regular Contest 038 programming problems in Japanese. 2. It describes the logic and pseudocode for solving a problem about determining if a knight piece on a chessboard will win or lose from its current position. Dynamic programming is used to store and lookup previously computed results. 3. It then provides sample test cases and outputs for t
大規模ネットワークの性質と先端グラフアルゴリズム - iwiwiの日記
本日，PFI セミナーにて「大規模ネットワークの性質と先端グラフアルゴリズム」というタイトルで発表をさせてもらいました．スライドは以下になります． 大規模ネットワークの性質と先端グラフアルゴリズム View more presentations from iwiwi Ustream の録画もあります． http://www.ustream.tv/recorded/27531606 内容としては，以下のようになっています． 現実世界のネットワークの特徴量と性質 次数分布 平均距離 クラスター係数 その他の特徴量 木っぽさ それらの性質を活用したグラフアルゴリズム セオリー方面 近接中心性の近似 コンパクトルーティング 支配集合問題の近似 プラクティカル方面 最短路 密部分グラフ列挙 可視化 タイトルは 1 年前にやった PFI セミナーと似ていますが，内容はあまりかぶっていません．今回は，グ
クラスタリングの定番アルゴリズム「K-means法」をビジュアライズしてみた
集合知プログラミング を読んでいたら、K-means 法（K平均法）の説明が出てきました。 K-means 法はクラスタリングを行うための定番のアルゴリズムらしいです。存在は知っていたんだけどいまいちピンときていなかったので、動作を理解するためにサンプルを作ってみました。 クリックすると１ステップずつ動かすことができます。クラスタの数や点の数を変更して、Restart を押すと好きなパラメータで試すことができます。 こうやって１ステップずつ確認しながら動かしてみると、意外に単純な仕組みなのが実感できました。 (追記) HTML5 版の K-means 法を D3.js でビジュアライズしてみた も作成しました。Flash を表示できない環境ではそちらをご覧ください。 K-means 法とは K平均法 - Wikipedia に詳しく書いてあるけど、もうすこしザックリと書くとこんなイメージに
ウェーブレット木の効率的で簡単な実装 "The Wavelet Matrix" - EchizenBlog-Zwei
久しぶりに論文を読んだ。 http://www.dcc.uchile.cl/~gnavarro/publ.html The Wavelet Matrix Claude & Navarro; SPIRE2012 "The Wavelet Matrix"はSPIRE2012のNavarro無双のうちの一本。タイトルからするとウェーブレット木の拡張のように思える。 機能としてはウェーブレット木と同一でデータ列に対するaccess,rank,selectを提供する。しかし実装は既存手法と比べて効率的でしかも簡単になっている。 これまでにウェーブレット木の実装としてはノードをポインタでつないだ普通の木として実装する方法(Standard Wavelet Tree. 論文のAlgorithm 1)と、木の階層ごとにノードをつなげた配列で表現する方法(Levelwise Wavelet Tree. 論文
MapReduceできる10個のアルゴリズム - データサイエンティスト上がりのDX参謀・起業家
HadoopとMahoutにより、ビッグデータでも機械学習を行うことができます。Mahoutで実装されている手法は、全て分散処理できるアルゴリズムということになります。Mahoutで実装されているアルゴリズムは、ここに列挙されています。論文としても、2006年に「Map-Reduce for Machine Learning on Multicore」としていくつかのアルゴリズムが紹介されています。 そこで今回は、（何番煎じか分かりませんが自分の理解のためにも）この論文で紹介されているアルゴリズムと、どうやって分散処理するのかを簡単にメモしておきたいと思います。計算するべき統計量が、summation form（足し算で表現できる形）になっているかどうかが、重要なポイントです。なってない場合は、”うまく”MapReduceの形にバラす必要があります。 ※例によって、間違いがあった場合は随時
大規模グラフアルゴリズムの最先端
2. 挨拶 • 自己紹介 – 秋葉拓哉 / @iwiwi – 東京大学 コンピュータ科学専攻 M1 – アルゴリズム系の研究室 – プログラミングコンテストが好き – 2009 年にインターンさせてもらって以来アルバイト アリ本 （グラフの話もあるよ） 1 3. いろんなグラフ 道路・交通ネットワーク • 頂点：交差点，駅など • 辺：道，路線など やりたいことの例 • 案内，交通管制 • 輸送や災害のための解析 • 地理情報と絡めたサービス • … 2 4. いろんなグラフ ソーシャルネットワーク • 頂点：人 • 辺：人間関係 やりたいことの例 • 「知り合いかも？」とか • 重要度・影響度の解析 • コミュニティ解析 • 情報の伝播力の解析 • … (MentionMap で作成) 映画 3
SimString - 高速かつシンプルな類似文字列検索ライブラリ
SimStringは，類似文字列検索のための高速かつシンプルなライブラリです． 類似文字列検索とは，文字列集合（データベース）の中から，クエリ文字列との類似度が閾値以上のものを，見つけ出す操作です． クエリ文字列と完全に一致しなくても，データベース中の似ている文字列を検索することができるので，スペル訂正，あいまい計算，柔軟な辞書マッチング，重複レコード検出，データベース統合など，様々なアプリケーションを構築できます． SimStringは，類似度関数として，コサイン係数，ジャッカード係数，ダイス係数，オーバーラップ係数に対応しています． 文字列の類似度を計算するための特徴量としては，文字nグラムをサポートしています． SimStringには，次のような特徴があります． 高速な類似文字列検索アルゴリズム．Google Web1T の英語単語（13,588,391文字列）から，コサイン類似度が
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
あなたの知らないハッシュテーブルの世界
プログラミングコンテストでの乱択アルゴリズム