頻出典型アルゴリズムの演習問題としてよさげなやつ - 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
diffのアルゴリズム - Plan9日記
ふと見つけた「あなたが一番好きなアルゴリズムを教えてください。また、その理由やどんな点が好きなのかも教えてください」を読んで、diffのアルゴリズムを調べてみた。2つのファイルの違いを見つけるには、共通する部分が最長になるペアを見つければよい。これはLCS (Longest Common Subsequence)問題と呼ばれる。LCS問題の最適解は動的計画法を用いて求めることができるが、計算時間、メモリ使用量ともにO(MN)になる*1。これより早く、また小メモリで実行できるようにいろいろなアルゴリズムが提案されている。 テキストを比較するdiffというUnix系のコマンドがありますが、これは実は高度に数学的なエディットグラフというアルゴリズムが使われています。 [1] E.W.Myers, "An O(ND) difference algorithm and its variations"
「最強最速アルゴリズマー養成講座」関連の最新 ニュース・レビュー・解説 記事 まとめ - ITmedia Keywords
最強最速アルゴリズマー養成講座： そのアルゴリズム、貪欲につき――貪欲法のススメ アルゴリズムの世界において、欲張りであることはときに有利に働くことがあります。今回は、貪欲法と呼ばれるアルゴリズムを紹介しながら、ハードな問題に挑戦してみましょう。このアルゴリズムが使えるかどうかの見極めができるようになれば、あなたの論理的思考力はかなりのレベルなのです。（2010/9/4） 最強最速アルゴリズマー養成講座： 病みつきになる「動的計画法」、その深淵に迫る 数回にわたって動的計画法・メモ化再帰について解説してきましたが、今回は実践編として、ナップサック問題への挑戦を足がかりに、その長所と短所の紹介、理解度チェックシートなどを用意しました。特に、動的計画法について深く掘り下げ、皆さんを動的計画法マスターの道にご案内します。（2010/5/15） 最強最速アルゴリズマー養成講座： アルゴリズマーの登
天気予報から機械学習、金融工学まで - DO++
もう随分経ちますが，先日CompView秋の学校というのに行き，2泊3日みっちり機会学習を勉強してきました．講師陣は豪華でどの話も面白かったのですが特にElad Hazanによる"Prediction in the dark: the multi-armed bandit problem"が非常に面白かったです． その話を説明するために，まず簡単ながら驚くべき性能を達成するアルゴリズムを紹介しましょう． 解きたい問題は，毎日，次の日の天気が晴れか雨かを予想する問題です．t日目が晴れの場合 y(t)=1, 雨の場合 y(t)=0と表すことにしましょう．t日目にy(t+1)を予想するわけです． さて、自分は天気の専門家ではないので，自分で予報せずに，専門家に頼ることにしてみます．M人の天気予報士がいて，それぞれが独自に次の日の天気を予想しています．i人目の天気予報士のt日目の予報をp(i,t)
ジャンル別ゲームの作り方とアルゴリズムまとめ - ネットサービス研究室
ゲームの作り方とアルゴリズムをジャンル別にまとめてみました。ゲーム制作や、プログラミングの勉強用にご活用ください。言語別ゲームプログラミング制作講座一覧もあわせてお読みください。 リンク切れがおきていたものは、URLを表示しておくので、Internet Archiveなどでキャッシュを表示させてみてください。 RPG ゲームの乱数解析 乱数を利用した敵出現アルゴリズムの解説 各種ゲームプログラム解析 FF、ドラクエ、ロマサガのプログラムの解析。乱数の計算など ダメージ計算あれこれ（http://ysfactory.nobody.jp/ys/prg/calculation_public.html） ダメージの計算式 エンカウントについて考えてみる エンカウント（マップでの敵との遭遇）の処理方法いろいろ RPGの作り方 - ゲームヘル2000 RPGのアルゴリズム ドルアーガの塔 乱数の工夫の
アルゴリズムと計算量
金庫破りと計算量膨張 n 桁の番号をもつ暗証ロックがあるとします。 2 桁であれば 00 〜 99 の 100 個の正解があるわけで、 0 番から順に入力していく解き方では、 最悪の場合は 100 手目に開きます。 99 が正解とは限らないので、平均的にはこれより早く解き終わります。 0 であるときの確率は 1/100 で、このときの手数は 1 手です。 1 であるときの確率は 1/100 で、このときの手数は 2 手です。 2 であるときの確率は 1/100 で、このときの手数は 3 手です。 3 であるときの確率は 1/100 で、このときの手数は 4 手です。 : 99 であるときの確率は 1/100 で、このときの手数は 100 手です。 つまり、平均手数は により、100 手目の約半分です。 ここでいう解き方をアルゴリズムといい、 問題を解くための手数 (てかず) のことを計
北海道を落とすとどう跳ねるのか？の裏側 - てっく煮ブログ
asおかげさまで大好評の 北海道を落とすとどう跳ねるのか？ ですが、どのように作ったか、製作過程を紹介することにします。1. 地図の素材を取ってくるまずは地図の素材が必要です。以下のサイトから拝借しました。白地図、世界地図、日本地図が無料pdf や eps 形式の地図データを無料で配布してくれているありがたいサイトです。2. 都道府県ごとに分割する上記の素材は県境もベクター形式で提供されていて大変ありがたかったのですが、島がどの都道府県に属しているかの情報がありませんでした。そこで、Google Maps と見比べながら、島を都道府県ごとに分類していきました。無事、全ての島を分類し終わって、こんな感じになりました。とても地味な作業でした…。3. 都道府県ごとに SVG で出力する次に、Illustrator 内で分類したデータをプログラムで扱える形式にしなければなりません。ここでは XML
線分
凸包の計算 2005・計算幾何学 本谷 凸包 与えられた図形を含む最小の凸図 （輪ゴムで囲む） 凸包の計算 • 応用１：ロボット・衝突判定 凸包の計算 • 応用２：「最も離れた２点」の探索 • 答えは凸包に寄与する点のどれか 凸包の計算 • 応用３：分類 凸包の計算法 • • • • • 包装法 Grahamの走査法 逐次構成法 分割統治法 その他 包装法 1. • y座標最小の点を見つけて p0 と呼ぶ． 複数あったらx座標が最小のもの 2. ① ② ③ ④ ⑤ i=0としたあと，①から⑤を実行 点piを原点として他点を見込む角を計算 角度最小の点pjを求める． pi – pjを凸包の辺に登録 j=0なら終了 i=jとして①に戻る 包装法 １： ｙ座標最小の点を原点に，ｘ軸となす角 が最小の点を探す．見付かった点を凸包の 一点に追加． 包装法 ２：見付かった点
おとうさん、ぼくにもYコンビネータがわかりましたよ！ - 2009-04-09 - きしだのはてな
やっと、Yコンビネータが何を意味するものなのか、どういう意義があるのかがわかりました。 名前を使わず再帰ができますよ！というだけのものじゃなかったのですね。 まずλありき 関数の話をしたいのです。 そのとき、いちいち hoge(x) = x * 2 としてhogeを・・・、とか名前をつけて話を進めるのがめんどうなので、関数を値としてあらわすと便利ということで、λという値を定義するのです。 そうすると、上のhoge関数なんかはλ(x)(x*2)などとあらわせますが、引数をあらわすのに()を使うといろいろまぎらわしいので、 λx.x*2 のように表記します。 というのがλ。 このとき、λになにかわたされたら、引数としてあらわされる部分を単純におきかえます。 (λx.x*2)y とあったら、xの部分をyでおきかえて (λx.x*2)y → y * 2 となります。λの引数部分を与えられた引数で置
アルゴリズムコンテストの挑み方 (3) - d.y.d.
17:19 08/11/27 TopCoder Code Jam の練習に……と思ってしばらく前から TopCoder のSRMに参加してたのですが、 せっかくなので cafelier@SRM に記録をつけることにしました。 どういう試行錯誤をしながら提出した時のコードにいたったのかを、 できるだけ詳細にメモろうと思っています。 426以前のは記憶から掘り起こして書いたのでちょい大ざっぱですが。 これまで何回かここで書いたような整然とした考え方を本当に自分がしているかいうと、 してないよなー、と薄々思ってしまっているので、じゃあどういう風にやっているんだろうかと。 自分のふり見て我がふり直す。 20:26 08/11/24 論文 PLAN-X 2009 通ったみたいです。ばんざい。 ただでさえD論まったく間に合う気がしないのに、camera ready版なんて作ってる時間が… オートマトン
アルゴリズムコンテストの挑み方 (2) - d.y.d.
21:25 08/10/27 論文 の締め切り終わったら頑張った自分へのご褒美（笑）であれとこれとそれをやる時間をとるぞー！ ……みたいなことを思っていたはずなのに、いざ提出し終わると気が抜けて何一つやる気がでない問題。 困った困った。 ナイチル たくさん人がいらしてる今のうちに 「ナイトメア☆チルドレン」新装版 面白いよみんな買おうぜ！ などと書いてみる。 自分のマンガの趣味はわりと平凡だと思ってて、 流行ってるマンガは大抵好きだし自分の好きなのはだいたい流行ってるし。 なのになぜだか藤野もやむ作品だけは唯一の例外で、とっても不思議でならない。 100回くらいアニメ化されてて然るべきだと思う。 何回か書いてますがとにかく最終話が好きで、 そこまでのシナリオが一気に集まって一つ一つのセリフが３倍の重みを持つように収斂していく幕引き。 あれは良い。 17:12 08/10/24 アルゴリズム
待ち行列に入門した - steps to phantasien(2008-08-12)
先週, 会社をさぼって システム性能評価と待ち行列理論 という講義を受けてきた. 待ち行列理論の入門講義で, 大学の学部でやるレベルの話らしい. 私は学部でも学部以外でも勉強したことがない話題だったので, とても興味深く聞いた. 受講後はすっかり盛り上り, 待ち行列で性能評価するぜ! という気分になったのだが, 実際は難しい. 性能評価一般の難しさはさておくとして, 待ち行列理論そのものがけっこう複雑. 数学が苦手な身には辛い. 理論の常として, 待ち行列の理論もまず解析対象の特性に様々な制限や前提を設けた上でモデルをたてる. そのモデルがうまく解析できたら, 少しずつ制限をとりはずしていく. 現実を扱えるモデルに至る道程は険しそうだ. 高価なツールを使えばそんな洗練されたモデルも扱えるのかもしれないけれど, もうちょっと庶民に優しい路線であってほしい. 解析に挫ける一方, 理論の成果が明
MapReduce - naoyaのはてなダイアリー
"MapReduce" は Google のバックエンドで利用されている並列計算システムです。検索エンジンのインデックス作成をはじめとする、大規模な入力データに対するバッチ処理を想定して作られたシステムです。 MapReduce の面白いところは、map() と reduce() という二つの関数の組み合わせを定義するだけで、大規模データに対する様々な計算問題を解決することができる点です。 MapReduce の計算モデル map() にはその計算問題のデータとしての key-value ペアが次々に渡ってきます。map() では key-value 値のペアを異なる複数の key-value ペアに変換します。reduce() には、map() で作った key-value ペアを同一の key で束ねたものが順番に渡ってきます。その key-values ペアを任意の形式に変換すること
mixi Engineers’ Blog » スマートな分散で快適キャッシュライフ
今日は以前のエントリーで書くと述べたConsistent Hashingに関して語らせて頂こうかと思います。ただしConsistent Hashingはセミナーやカンファレンスなどでかなり語られていると思いますので、コンセプトに関しては深入りせず、実用性に着目したいと思います。 問題定義 分散されたキャッシュ環境において、典型的なレコードを適切なノードに格納するソリューションはkeyのハッシュ値に対しmodulo演算を行い、その結果を基にノードを選出する事です。ただし、このソリューションはいうまでもなく、ノード数が変わるとキャッシュミスの嵐が生じます。つまり実世界のソリューションとしては力不足です。 ウェブサイトのキャッシュシステムの基本はキャッシュがヒットしなかったらデータベースにリクエストを発行し、レコードが存在したらキャッシュしてクライエントに返すという流れです。ここで問題なのが一瞬
void element blog: ドキッ！変態だらけのActionScript的超絶技巧発表会
超絶技巧＋発表必須というシビアな参加条件の「ActionScript的超絶技巧発表会」に参加してきました。 どんな感じだったのかはてっく煮ブログのエントリにまとめられているので、そちらをご覧ください。 まーみんな変態というか「こんなのにまじになっちゃってどーすんの」と言わんばかりのハックぶりでポカーンとしたりさせたり発表してる自分まで危うくポカーンとしかねない勉強会でしたが、何よりも刺激受けまくりでこれだからやめられないぜ！と再確認。 で、何を発表したかというと以前公開したフィールドマップジェネレータでさりげなく使っているアルゴリズムの説明。 ピクセル走査を一切行わず、画像処理だけで全部やっちゃうという無茶っぷりを晒してみましたが、あの説明と資料でその場で理解できた人がどれくらいいたのか正直気になるところ。 発表資料をそのまま公開しても全く理解できないこと請け合いなので、口頭で説明した部分
ベイジアンフィルタ: 日誌
いまさらにベイジアンフィルタについて。 P(A|B) = P(A∩B)×P(B) P(B|A) = P(A∩B)×P(A) = ( P(A|B) / P(B) ) × P(A) ∴P(B|A) = P(A|B)×P(A) / P(B) これを P(spam|word) = P(word|spam)×P(word) / P(spam) という感じに応用してみた、ってことでいいのかな。
アルゴリズム百選 - ベキ乗はO(1)でOK? : 404 Blog Not Found
2007年12月04日23:00 カテゴリアルゴリズム百選Math アルゴリズム百選 - ベキ乗はO(1)でOK? これ、Hyukiさんをはじめ多くの方が疑問に思っていらっしゃるようなので、いまのうちに答えておきましょう。blogで書く以上、書く順番は順不同で構わないのですし。 アルゴリズム百選 - フィボナッチ数列にO()を学ぶ - www.textfile.org フィボナッチ数列の一般項を求める式を使ったときってO(1)って言えるのだろうか？まずは、論より証拠、というわけで実測値をご覧下さい。Cでフィボナッチ数をO(n)アルゴリズムと公式を使ってそれぞれ100万回計算した時にかかった時間をプロットしたものです。最適化をかけていないものと-O3で最適化をかけたものと双方を計測しています。fib(73)まで計算したのは、doubleで整数で保っておける限界がそこまでだったので。ソースは本
404 Blog Not Found:プログラマーでなくても名前ぐらい覚えておきたいアルゴリズムx10
2007年11月26日18:15 カテゴリMathLightweight Languages プログラマーでなくても名前ぐらい覚えておきたいアルゴリズムx10 ぎくっ あなたが一番好きなアルゴリズムを教えてください。 また、その理由やどんな点が好きなのかも教えてください。 - 人力検索はてな なぜぎくってしているかというと、実はすでにアルゴリズム本の発注を受けているからなのだ。いつまでも伏せておくのもなんなので、ここにえいやっとdiscloseしてしまうことにする。 アルゴリズム大募集! C&R研究所 - トップページ その下書きもかねて、そこでも紹介しないわけに行かないメジャーなアルゴリズムをとりあえず10個紹介しておくことにする。 ユークリッドの互除法(Euclidean algorithm) その昔(数百年ほど前)は「アルゴリズム」といえば、「手順一般」を指すのではなく、この「互除法
あなたが一番好きなアルゴリズムを教えてください。 また、その理由やどんな点が好きなのかも教えてください。 - 人力検索はてな
あなたが一番好きなアルゴリズムを教えてください。 また、その理由やどんな点が好きなのかも教えてください。
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
新しいエントロピー符号化 - www.textfile.org
