ゲーマーでなくても仕組みぐらいは知っておきたいアルゴリズムx40
高校生の時、数学の先生がこう言いました。 ゲームなんて、開発者が作ったルールの上で遊ばれるだけだ。 と。 その時、ゲーマーな自分はこう思いました。 ゲーマーは、開発者が作ったルールの上で遊ばれたい。 と。 というわけで、普段何気なくプレイしているゲームには、どのようなルール（アルゴリズム）があるのか。それを知るために、いろいろなゲームのアルゴリズムなどを解析しているページへのリンク集を作りました。 ほとんどのゲームのアルゴリズムは正式に発表されていないので、ユーザーの手による逆解析だったり、大学の研究による真面目な考察だったりします。（リンク先には、一部アルゴリズムと呼べないものも含まれています） 各種ゲームのプログラム解析 ドラクエ、FF、ロマサガのプログラム解析 DQ調査報告書（リンク切れ） ドラクエの物理ダメージ計算式は本質的にどれも同じだが、細かい部分で微妙に違う RPG INST
404 Blog Not Found:プログラマーでなくても名前ぐらい覚えておきたいアルゴリズムx10
2007年11月26日18:15 カテゴリMathLightweight Languages プログラマーでなくても名前ぐらい覚えておきたいアルゴリズムx10 ぎくっ あなたが一番好きなアルゴリズムを教えてください。 また、その理由やどんな点が好きなのかも教えてください。 - 人力検索はてな なぜぎくってしているかというと、実はすでにアルゴリズム本の発注を受けているからなのだ。いつまでも伏せておくのもなんなので、ここにえいやっとdiscloseしてしまうことにする。 アルゴリズム大募集! C&R研究所 - トップページ その下書きもかねて、そこでも紹介しないわけに行かないメジャーなアルゴリズムをとりあえず10個紹介しておくことにする。 ユークリッドの互除法(Euclidean algorithm) その昔(数百年ほど前)は「アルゴリズム」といえば、「手順一般」を指すのではなく、この「互除法
タイムインターメディア、ナンプレ自動生成アルゴリズムをGPLで公開 | OSDN Magazine
タイムインターメディア（本社：東京都新宿区）は2007年8月27日、数字パズル「ナンプレ（数独）」の問題を自動生成するプログラム「ナンプレ自動生成 Version1.0」をオープンソースで公開した。通常の問題（ヒント数24程度）の場合、0.05秒程度で1問作成できるという。 利用しているアルゴリズムは、多種類のパズルに適用できる基本アルゴリズムで、特許出願中。高速、高性能で、プログラムサイズもJavaで1000行程度と小さく、携帯ゲーム機や携帯電話などリソースが限られる端末上でも動作可能という。 同社によると、これまでパズル問題の自動生成は低品質という誤解があり、高品質な自動生成をソースコードレベルで正しく知ってもらうためにGPLライセンスでの公開を決めたという。 アルゴリズムはゲームメーカーに提供しており、関連ソースの公開が不要な商用ライセンスも用意した。すでにニンテンドーDS用ソフトに
野村監督とバカボンのパパの論理 - 檜山正幸のキマイラ飼育記 (はてなBlog)
今朝のニュースにて： プロ野球チーム楽天の勝率が5割をこえたことに関して、野村監督が「あしたは雪かな」と自嘲ぎみのジョークを言ってました。いまの季節に「あしたは雪」ってのは、ありえそうにないこと。つまり、楽天が勝率5割なんてありえそうにないことが起きたな、ってな意味合い -- と説明するのも野暮ですがね。 さて実は、野村監督のこの論法(?)、古典論理の法則を使っています（本人がそう思っているかどうかは別）。「Aではない」（Aの否定）と「Aならば矛盾」が同じ意味だという法則ね -- これは論理のなかでも分かりにくいと不評な部分ですが、日常会話でけっこう使ったりしてるんですよ。 古典論理の否定と矛盾 まず、問題の古典論理の法則とは； 「Aではない」と「Aならば矛盾」は論理的に同値だという法則です。「Aではない」と「Aならば矛盾」が主張している内容に変わりはないのです。「ではない」を記号¬で、「
データ構造とアルゴリズムの解説ブログ | 秋元@サイボウズラボ・プログラマー・ブログ
via del.icio.us/popular datastructures は、データ構造とアルゴリズムに関するトピックを、図解(動くものや動画のものもある)とC++/Cのコードで解説するブログだ。 ハッシュ表、二分木探索、ハフマン法、各種ソートアルゴリズムなどをわかりやすく解説している。Wikipediaとかでもカバーされているとは思うけど。 この記事は移転前の古いURLで公開された時のものですブックマークが新旧で分散している場合があります。移転前は現在とは文体が違い「である」調です。(参考)記事の内容が古くて役に立たなくなっている、という場合にはコメントやツイッターでご指摘いただければ幸いです。最新の状況を調べて新しい記事を書くかもしれません
きまぐれ日記: 動的配列への追加コストはなぜ O(1)?
動的配列への追加コストは O(1) ってのは覚えていればそれだけの話ですが，どうしてかと言われると意外と難しいものです． というのも, このO(1)ってのは動的配列の実装方法に強く依存しているからです．実装を知っていないと答えられません． 一般論として，1つ要素を追加するとき，配列に空きがなかったら新しく配列を作り直して全要素をコピーする必要があります．コピーのコストは O(n) だから，追加コストも O(n) になるという議論が混乱の元になっています． こういうときは，要素追加を n 回繰り返したときの計算量を n で割った平均をとるという解析方法が使われるそうです．一般に, ある operation C の計算量を C を n 回行ったときの計算量 O(n) を n で割った値 O(n)/n で評価する手法をならし解析 (amortized analysis)と言うそうです． さて，s
ユビキタスの街角 データ圧縮手法の応用
PPM (Prediction by Partial Matching)というデータ圧縮アルゴリズムがある。 一般に、あるデータ列が与えられているとき、次に来るデータを予測することができればデータ圧縮を行なうことができる。 データ列から判断して次に来るデータが「a」だと確実に判断できるときは「a」を記述する必要が無いからである。 PPM法では、既存のデータ列中の文字列出現頻度を計算することによってこのような予測を行なう。 たとえば「abracadab」というデータの次にどの文字が来るか予測する場合、 「a」は4回、「b」は2回出現している 「b」の後に「r」が続いたことがある 「ab」の後に「r」が続いたことがある ... といった情報を累積して確率を推定する。 この場合、 (3)から考えて次の文字は「r」である確率が高いが、 (1)も考慮すると「a」の確率もある、という風に計算を行なう。
[結] 結城浩の最新刊『Java言語で学ぶリファクタリング入門』 - 2006年11月 - 結城浩の日記
目次 2006年11月30日 - 日経ソフトウエアに「Comet」の記事を書きました / 2006年11月28日 - あらためて「固有IDのシンプル・シナリオ」を読み返す / 2006年11月27日 - 仕事 / 2006年11月25日 - 仕事 / 風邪 / 2006年11月24日 - 結城浩の最新刊『Java言語で学ぶリファクタリング入門』 / 仕事 / よかった探しリース…はちょっと待ってね / 2006年11月23日 - 仕事 / 情報系の大学院に通う読者さんからのメッセージ / また来たトドちゃん / 2006年11月21日 - 仕事 / 2006年11月20日 - gnuplot + pLaTeXメモ / 『Java並行処理プログラミング』無料プレゼント / 2006年11月18日 - 仕事 / 2006年11月17日 - 仕事 / 2006年11月16日 - 夜 / 来た来た
定番アルゴリズムを徹底理解！ - 今からでも遅くない！アルゴリズム入門：selfup
このパートでは，プログラミングを勉強するうえで欠かせないアルゴリズムの中でも定番中の定番を紹介します。ソート（並べ替え）やサーチ（検索）などの機能は今では標準のライブラリとして提供されています。実用的なプログラムを作るときにそのものずばりをいちいち書く機会は少ないかもしれません。しかし定番のアルゴリズムは，様々に形を変えて普段のプログラミングに登場します。 解説を読んで仕組みがわかったら，ぜひそれをプログラムにしてみてください。読んだだけではプログラムを書けるようにはなりませんし，プログラムを書いてみて初めて，実は十分に理解できていなかったと気付くことがよくあります。しかもアルゴリズムは特定のプログラミング言語に依存しないので，一度身に付ければ，後でどんな言語を学ぶ場合でも役に立ちます。 1番目から6番目まではソートのアルゴリズム，7番目から9番目まではサーチのアルゴリズムです。一つひとつ
再帰再考 : 404 Blog Not Found
2006年07月23日13:00 カテゴリLightweight Languages 再帰再考 今やこれは逆ではないか。 再帰的アルゴリズム まずは，非再帰プログラムで問題を考えてみる。 難しいと判断した場合，再帰プログラムで考えてみる。 むしろ私はこうしてきた。 まずは再帰で実装する。 速度と資源の制約があるとき、非再帰で実装しなおす 一番の理由は、今やプログラミングそのもののコストの方がプログラムを実行するコストよりも大きいからだ。早くプログラムを書く要請の方が速いプログラムを書く要請より強いからだ。 次の理由は、再帰は遅いとは限らないからだ。特にLisp系では、末尾再帰(tail recursion)は重くない。これはもうshiroさんが力説しているのでそちらを参照して欲しい。フィボナッチ数列を解くプログラムはとにかく、階乗を解くプログラムぐらいだとわざわざ再帰しないようにするご利益
再帰的アルゴリズム
このようにして３！が計算されます。 このような定義の仕方を再帰的定義と言います。 この階乗関数を Basic プログラムとして実現してみると，（Tiny Basic には階乗関数 Factorial が内蔵されていますから，実際にこのようなプログラムを書く必要はありませんが。） Function Kaijyou(n) If n = 0 then Kaijyou = 1 Else Kaijyou = Kaijyou(n-1)*n End if End Function となります。しかし，実は階乗関数は，再帰を使わなくても，次のように実現することが出来ます。 Function Kaijyou(n) F = 1 For i = 1 to n F = F * i Next i Kaijyou = F End Function このように再帰的プログ
An Algorithm for Compressing Space and Time | 3 1, 2006
An Algorithm for Compressing Space and Time By Tomas G. Rokicki, April 01, 2006 Making a slow program fast can lead to both joy and frustration. But sometimes a new approach yields amazing improvements. Making a slow program fast can lead to both joy and frustration. Frequently, the best you can do is a low-level trick to double or maybe quadruple the speed of a program; for instance, many readers
これだけは知っておきたいアルゴリズム〜ハッシュ関数・公開鍵暗号・デジタル署名編 ― ＠IT
これだけは知っておきたいアルゴリズム ～ハッシュ関数・公開鍵暗号・デジタル署名編：デファクトスタンダード暗号技術の大移行（4）（1/3 ページ） 前回の共通鍵暗号の紹介に引き続き、安全性・処理性能ともに優れていると国際的に認められ、米国政府標準暗号、欧州のNESSIEや日本のCRYPTREC（Cryptography Research ＆ Evaluation Committees）での推奨暗号、ISO/IEC国際標準暗号、インターネット標準暗号などで共通して選定されているハッシュ関数・公開鍵暗号・デジタル署名について紹介する。 共通鍵暗号ではアルゴリズムそのものを代替わりさせることによって、より安全でより高速なものへと移行することが可能である。これに対して、ハッシュ関数、公開鍵暗号、デジタル署名ともに、アルゴリズムそのものを代替わりさせるというよりも、基本的にはほぼ同じ構成のままハッシュ
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
動画でわかるソートアルゴリズムの違い:Geekなぺーじ
kaz::hatena - 特別公演 - プロ棋士はどう考えているか
