頻出典型アルゴリズムの演習問題としてよさげなやつ - 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
DHTアルゴリズムSymphonyの解説 - 情報科学屋さんを目指す人のメモ
SymphonyはDistributed Hash Table(DHT)を実現するアルゴリズムの一つで、有名な物にChord, Kademlia, CAN, Pastry, Tapestryなどなどが有ります。もう大量にあるわけで、私自身でもLFRTとかそういうものを作っていたりします。 Symphonyの立ち位置はと言うと、大御所たちに比べたら知名度は低めだと思います。つまるところ、わざわざ日本語で説明文を書いてHPに載せようと思う人自体少ないと思います。じゃぁ書こうとなるわけです。 Symphonyのスライド 発表する訳じゃないですが、スライドで作りました。喋りが無くても分かるように吹き出しだらけです。 それと、短時間で作ったので、あまり重要でない部分は絵を描いてません。 今回は、Symphonyを読む人がChordを知らないはずがないという前提の元、Chordを多少は(雑誌記事程度で
livedoor Techブログ : decision tree (決定木) でユーザエージェント判定器を作ってみる
アクセスログのユーザエージェント(UA)からブラウザを判別するのって，みんな何使ってますか？ 自分が作ったアクセス解析システムでは HTTP::BrowserDetect と HTTP::MobileAgent にそれぞれ独自パッチをあてたものを使っています。これらはルールベースの判定器なので，新しいブラウザや新種の bot が登場するたびに手作業でルールを追加し，パッチを作って配布するという作業が必要になります。 この更新作業が大変面倒くさくて対応が遅れがちになるので，「このUA文字列はこのブラウザですよ、という例を大量に与えたら、自分で勝手に判定ルールを学習してくれるようになったら便利なのになぁ」と思い，decision tree (決定木)を使ってみることを思い立ちました。 目標は， "Mozilla/5.0 (Windows; U; Windows NT 6.1; ja; rv:1
決定木 - Wikipedia
決定木（けっていぎ、英: decision tree）は、（リスクマネジメントなどの）決定理論の分野において 決定を行うためのグラフであり、計画を立案して目標に到達するのに用いられる。 決定木は、意志決定を助けることを目的として作られる。 決定木は木構造の特別な形である。 機械学習の分野において決定木は予測モデルであり、ある事項に対する観察結果から、その事項の目標値に関する結論を導く。内部の節点は変数に対応し、子である節点への枝はその変数の取り得る値を示す。 葉（端点）は、根(root)からの経路によって表される変数値に対して、目的変数の予測値を表す。 データから決定木を作る機械学習の手法のことを決定木学習 (英: decision tree learning)、または略して単に決定木と呼ぶ。 決定木による分類モデルはその分類にいたる過程が容易に解釈できるので、決定木はデータマイニングでよ
行列分解ライブラリredsvdを公開しました - DO++
大規模疎行列向けの行列分解ライブラリredsvdを公開しました． redsvd 大規模疎行列向けの特異値分解や主成分分析，固有値分解を行うライブラリredsvdを公開しました． 修正BSDライセンスで公開しており，コマンドラインから使える他，C++ライブラリが用意されています． 例えば，行と列数がそれぞれ10万，非零の要素が1000万からなる疎行列に対する上位20位までの特異値分解を約2秒で処理します． 特異値分解とか，使っている技術の詳細とか応用事例を以下に簡単に紹介しましたので，興味のある方は参考にしてください． 特異値分解とは まず行列を適当に復習します．行列Xの転置をX^tと表すことにします．またIを単位行列とし，Oを全ての成分が0である零行列とします．また，行列XX^t=IであるようなXを直交行列と呼びます．Xが直交行列の時，Xvはベクトルvを長さを変えずに回転させます．ここでは
経路探索アルゴリズムの「ダイクストラ法」と「A*」をビジュアライズしてみた - てっく煮ブログ
as詳解 ActionScript 3.0アニメーション ―衝突判定・AI・3DからピクセルシェーダまでFlash上級テクニック を読んでいて、経路探索のアルゴリズムで A* が取り上げられていました。A* については、いろいろ検索して調べたりもしたのですが、やっぱり本に書いてあると理解しやすいですね。せっかくなので自分流に実装してビジュアライズしてみました。ダイクストラ法まずは A* の特別なケースでもあるダイクストラ法から見ていきます。クリックすると探索のシミュレーションが開始します。スタート地点(S)からゴール(G)への探索が始まります。色がついたところが「最短経路が決定した場所」です。スタート地点から少しずつ探索が完了していきます。半分ぐらい完了しました。まだまだ進みます。最後まで終わりました。最短経路を黒色矢印で表示しています。ダイクストラ法は、スタート地点から近いノード(=マス
d.y.d. 2倍だけじゃない
10:01 10/07/20 それでも２倍だ 先日のvectorの伸長度合いの記事に関して 本当に1.5倍のほうがメモリ効率がよいのか という反応をいただきました。とても興味深い。みんな読みましょう。 自分の理解メモ： 「再利用ができるから嬉しい」等の議論をするなら、 今までに確保したメモリ (1 + r^1 + ... + r^k) のうち、 有効に使えてるメモリ r^{k-1} (バッファ拡大直後) や r^k (次のバッファ拡大直前) の割合で評価してみようじゃないかという。 まず簡単のために再利用をしない場合を考えると、この割合はそれぞれ (r-1)/r^2、 (r-1)/r になります（途中計算略）。 この利用率が最悪になる瞬間 (r-1)/r^2 を最善にしよう、 という一つの指標で考えてみると、式を微分なりなんなりしてみると r = 2 で最大(25%)となることがわかります
チームラボ / teamLab
森ビル デジタルアート ミュージアム：エプソン チームラボボーダレス Feb 09, 2024 - 麻布台ヒルズ、東京 NOW OPEN
LSH(SimHash) で recall(適合率) を見積もりたい - 木曜不足
英単語タイピングゲーム iVoca で「おすすめブック」機能をリリースしました。 ブック(単語帳)の画面に、そのブックと似ていて、同じユーザが学習しているブックを自動的に表示します。 英検の単語を集めたブックには英検の、しかもだいたい同じレベルのものを、TOEIC には TOEIC、イタリア語にはイタリア語、ドイツ語にはドイツ語、と ちゃんとおすすめできています。 外国語以外にも 古文の単語を集めたブックには古文、アメリカ合衆国の５０州を覚えるブックには世界の首都や都道府県を覚えるブックをおすすめしてくれます。 学びたいブックを見つけやすくなった iVoca をこれからもよろしくお願いします。 以上、よそいきモード終わり。 今回の類似ブック探索には、ソーシャルブックマーク界隈で噂の LSH(Locality Sensitive Hashing)、特に余弦類似度を用いた SimHash を採
「最強最速アルゴリズマー養成講座」関連の最新 ニュース・レビュー・解説 記事 まとめ - ITmedia Keywords
最強最速アルゴリズマー養成講座： そのアルゴリズム、貪欲につき――貪欲法のススメ アルゴリズムの世界において、欲張りであることはときに有利に働くことがあります。今回は、貪欲法と呼ばれるアルゴリズムを紹介しながら、ハードな問題に挑戦してみましょう。このアルゴリズムが使えるかどうかの見極めができるようになれば、あなたの論理的思考力はかなりのレベルなのです。（2010/9/4） 最強最速アルゴリズマー養成講座： 病みつきになる「動的計画法」、その深淵に迫る 数回にわたって動的計画法・メモ化再帰について解説してきましたが、今回は実践編として、ナップサック問題への挑戦を足がかりに、その長所と短所の紹介、理解度チェックシートなどを用意しました。特に、動的計画法について深く掘り下げ、皆さんを動的計画法マスターの道にご案内します。（2010/5/15） 最強最速アルゴリズマー養成講座： アルゴリズマーの登
３次元手ぶれ補正（知覚補正付き） - potasiumchの日記
（ちょっと遅ればせながら）今年のSIGGRAPHで発表された手ぶれ補正アルゴリズムは面白いと思った。素人が撮ったぶれぶれのビデオを後からソフトウェア的に修正してくれるというもの。ウィスコンシン大学とアドビ社の共同研究。 Content-Preserving Warps for 3D Video Stabilization Feng Liu, Michael Gleicher, Hailin Jin and Aseem Agarwala SIGGRAPH 2009 枠組みとしては、まずビデオ動画から特徴点抽出を行い、３次元的なカメラの動きの情報を得る。そこからカメラが理想的な（ぶれぶれでない）軌跡をたどったとしたら見えたであろう景色を再構成するべく、画像を局所毎にリマッピングしよう、というもの。ただし単純に再構成だけを考えてリマッピングすると情景自体が変わる部分（被写体が動いて隠蔽箇所が変化
PTAMの解析 - 2 処理プロセスの概要 - Pipe Render
2回目は、PTAMの処理プロセスの概要です。 また概要になります、すいません。各プロセスの詳細は、後々解説していこうと思います。 --------- < 処理プロセスについて > --------- PTAMでの処理は、大きく分けて次のようなものがあります。 １．マップの初期化 ２．トラッキング３．マップの更新 ○１のマップの初期化は、一番最初に行われる作業です。PTAMの動画を見ていると分かりますが、最初にバッチ処理っぽいことを行っています。この時の画像を元にマップが構築されて、これが基本のマップになります。 ○2のトラッキングでは、このマップを元にカメラの位置・姿勢（方向）の推定が行われます。この処理はスレッドで行われ、coarse-to-fineという手法が用いられます。 coarse-to-fine：最初に大まかなマッチングを行い、大体の位置を確定できたら、次に細かいマイッチングを
PTAMの解析 - 1 概要 - Pipe Render
PTAM（Parallel Tracking and Mapping for Small AR Workspaces）の解析を行っております。 正直言って非常に難しいです。 なので、とりあえず概要について説明したいと思います。 また資料として、以下のサイトを参考にさせていただきました。 masayashi：PTAMを15分でなんとなく理解する Cagylogic：PTAMのアルゴリズムを理解するのに必要な用語 ※非常に大雑把に翻訳しているので、誤りや不足があるはずです、ご注意ください。 ※また、この内容は未完成で、修正される可能性があります。 ○PTAMとは？ マーカーなしのARの手法です。 以下のような特徴があります。 初めて映す場所でも実行できる（マーカーなどの目印いらず）最初の場所から少し移動しても、トラッキングし続けることができる。（常にマップを更新）マップの更新とトラッキングを別
ジャンル別ゲームの作り方とアルゴリズムまとめ - ネットサービス研究室
ゲームの作り方とアルゴリズムをジャンル別にまとめてみました。ゲーム制作や、プログラミングの勉強用にご活用ください。言語別ゲームプログラミング制作講座一覧もあわせてお読みください。 リンク切れがおきていたものは、URLを表示しておくので、Internet Archiveなどでキャッシュを表示させてみてください。 RPG ゲームの乱数解析 乱数を利用した敵出現アルゴリズムの解説 各種ゲームプログラム解析 FF、ドラクエ、ロマサガのプログラムの解析。乱数の計算など ダメージ計算あれこれ（http://ysfactory.nobody.jp/ys/prg/calculation_public.html） ダメージの計算式 エンカウントについて考えてみる エンカウント（マップでの敵との遭遇）の処理方法いろいろ RPGの作り方 - ゲームヘル2000 RPGのアルゴリズム ドルアーガの塔 乱数の工夫の
適切なクラスタ数を推定するX-means法 - kaisehのブログ
K-means法によるクラスタリングでは、あらかじめクラスタ数Kを固定する必要があります。HatenarMapsでもK-means法を使っているのですが、クラスタ数は（特に根拠もなく）200個に決め打ちになっていました。 これに対して、X-means法というK-means法の拡張が提案されていることを知りました。X-means法を使うと、データに応じて最適なクラスタ数を推定できます。 K-means and X-means implementations http://www-2.cs.cmu.edu/~dpelleg/download/xmeans.pdf X-means法の考え方は、K=2で再帰的にK-means法を実行していくというもので、クラスタの分割前と分割後でBIC（ベイズ情報量規準）を比較し、値が改善しなくなるまで分割を続けます。 調べたところ、Javaのデータマイニングツー
Web上の膨大な画像に基づく自動画像補完技術の威力 - A Successful Failure
画像内に映り込んだ所望のオブジェクトを排除し、違和感の無い画像を生成するシーン補完技術に関しては近年複数の研究成果が発表されている。しかし中でも2007年のSIGGRAPHにて米カーネギメロン大のJames HaysとAlexei A. Efrosが発表した手法*1はブレークスルーとなりうる画期的なものだ。 論より証拠、早速適用例を見てみよう。本エントリで利用する画像はPresentationからの引用である。元画像の中から邪魔なオブジェクト等の隠蔽すべき領域を指定すると、その領域が補完された画像が自動的に生成される。 アルゴリズム 効果は抜群だがアイデア自体は単純なものだ。Web上には莫大な数量の画像がアップされており、今や対象となる画像の類似画像を一瞬にして大量に検索することができる。そこで、検索された類似画像で隠蔽領域を完全に置き換えてしまうことで違和感の無い補完画像を生成するのだ。
Google Research Publication: Bigtable: A Distributed Storage System for Structured Data
Bigtable: A Distributed Storage System for Structured Data Fay Chang, Jeffrey Dean, Sanjay Ghemawat, Wilson C. Hsieh, Deborah A. Wallach, Mike Burrows, Tushar Chandra, Andrew Fikes, and Robert E. Gruber Abstract Bigtable is a distributed storage system for managing structured data that is designed to scale to a very large size: petabytes of data across thousands of commodity servers. Many projec
クラスタリングの定番アルゴリズム「K-means法」をビジュアライズしてみた - てっく煮ブログ
集合知プログラミング を読んでいたら、K-means 法（K平均法）の説明が出てきました。K-means 法はクラスタリングを行うための定番のアルゴリズムらしいです。存在は知っていたんだけどいまいちピンときていなかったので、動作を理解するためにサンプルを作ってみました。クリックすると１ステップずつ動かすことができます。クラスタの数や点の数を変更して、RESET を押すと好きなパラメータで試すことができます。こうやって１ステップずつ確認しながら動かしてみると、意外に単純な仕組みなのが実感できました。K-means 法とはK平均法 - Wikipedia に詳しく書いてあるけど、もうすこしザックリと書くとこんなイメージになります。各点にランダムにクラスタを割り当てるクラスタの重心を計算する。点のクラスタを、一番近い重心のクラスタに変更する変化がなければ終了。変化がある限りは 2. に戻る。これ
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
Client Challenge
IBM Developer
