Programming Topics
This page will contain links to a series of essays on computer chess topics, as I have time to write them. The topics are oriented toward those who want to write their own chess program, or understand how chess programs work. I do not mean to describe ever conceivable way of writing a chess program. It is my intent to talk about common techniques, in some cases with a personal perspective since I
アルゴリズムコンテストの挑み方 (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版なんて作ってる時間が… オートマトン
アルゴリズムコンテストの挑み方 - d.y.d.
17:29 08/09/30 クロスワード 暇つぶしに "Clueless Crossword" という冊子を買ってみて意外とハマっています。 クロスワードパズルなんだけど、単語のヒントの代わりに、 各マスに1～26の数字が振ってあって同じ数字のマスには同じA～Zが入るように埋めるというもの。 「母音っぽくて二連続して語尾にも出てくるのは多分 E だろう、もしかしたら O の可能性はなくもないけど」 みたいに埋めていく。 ちょっと違うけど フラッシュであった。 20:15 08/09/28 だいちのよろい そろそろ日本に戻る前に観光するぞ月間、ということにして、ウルル（エアーズロック）に行ってきました。 もっとワイルドな感じかと思ったら、完全にリゾートのリゾートによるリゾートのための地帯になってました。 まあそんなもんか。 本日は強風のため登るの禁止とのことだったので、周りから見るだけ。
Spaghetti Source - 各種アルゴリズムの C++ による実装
ACM/ICPC（プログラミングコンテスト）系列の問題を解くことを目標にして，各種アルゴリズムを C++ で実装してみた．極めて意地が悪い類の問題には対応していないし，特定の入力に対して高速に動くということもない．計算量も最良とは限らない． これらを参考にする方への注意とお願い： これらの記述は正確とは限りません．参考文献を参照することを強く推奨します．間違っている場合は是非教えてください． これらのプログラムは間違っているかもしれません．各人で検証することを強く推奨します．バグがあれば是非教えてください． 分類が怪しいので，これはこっちだろう，ということがあればコメントを下さると助かります． 注意！ 現在書き換え中 TODO 分類を正しく行う． 全体的に説明と使い方を詳しく． Verify していないものを Verify． ボロノイ図（いつになることやら……） 基本 テンプレート グラフ
ユメのチカラ: セキュリティ＆プログラミングキャンプ2008
ユメのチカラ インターネットの時代になって、地球規模の知恵の集積が 可能になった。ソフトウェア開発においてもオープンソースソフトウェアのバザール的開発が注目されている。いまおきているその現実を現場の視点から記していきたい。 吉岡 弘隆 - よしおか ひろたか 日本OSS推進フォーラム ステアリングコミッティ委員 OSDL Board of Directorsを歴任 カーネル読書会主宰 2000年6月、ミラクル・リナックスの創業に参加。 95年～98年、米国OracleにてOracle RDBMSの開発をおこなっていた。 98年にNetscapeのソースコード公開(Mozilla)に衝撃をうけ、オープンソースの世界に飛びこみ、ついには会社も立ち上げてしまう。 2008年6月取締役CTOを退任し一プログラマとなった。
クラスタリングによる迷路作成アルゴリズム
はじめに クラスタリングアルゴリズムにより、解くと絵が浮かび上がる 迷路を作成する方法を紹介する。 クラスタリングとは ウェブのリンク情報や、mixiの友人関係など、ネットワークの性質を 知りたいことがよくある。このとき、ネットワークの性質として このネットワークにおいて任意に選んだ要素Aと要素Bはつながっているか？ このネットワークは全体がつながっているか？ つながっていないとしたらいくつのグループに分かれるか？ 要素数最大のグループはどれか？ などの情報が欲しくなる。このような解析をするときに 必要となるのがクラスタリングである。 クラスタリングとは、同値関係のリストが与えられたときにグループ分けを することである。たとえば、 友達の友達は友達である と定義すると、友人関係は同値関係を作る。 その上で、 A君とB君は友達 C君とE君は友達 B君とD
Cuckoo Hashing - Radium Software
ハッシュテーブルからエントリーを検索する処理は，一般に定数時間で済むとされている。つまり，どんなにエントリーが増えても検索の速さは変わらない，ということ。データ構造の教科書には必ず載っていることだね。 でも実際には，ハッシュの衝突が起こった場合に，速度の低下が発生する可能性がある。例えば，一般的なチェイン法（オープンハッシュ）だと，衝突したエントリーに関して線形検索を行うことになるから，衝突が多ければ多いほど，定数時間からは遠のいてしまう。 この速度低下を防ぐ方法はいろいろある。なかでも cuckoo hashing （カッコウ・ハッシング）は仕組みが面白い。こいつは，エントリーの検索を必ず定数時間で済ませてくれるという優れものなんだ。 Cuckoo hashing では，２つのハッシュ関数と，２つのテーブルを用いる。ここでは，２つのハッシュ関数をそれぞれ h1, h2 として，２つのテー
集合知と多量情報の可視化アルゴリズム本 Programming Collective Intelligence | fladdict
先日購入したBen FryのVisualizing Dataとあわせて買ってみた、Programming Collective Intelligence: Building Smart Web 2.0 Applications という本もかなりよさげ。 端的にいうとWEB2.0コンテンツ用に特化した、統計解析の理論とアルゴリズムの解説本。 いわゆる「これを買った人はこれを買ってます」を筆頭に、市場予測やスパム抽出、特徴データのグルーピングなど、集合知を抽出するアルゴリズムが大集合してる感じです。各アルゴリズムの原理の説明から、シンプルな自力実装までが書いてある感じっぽい。こういう系は数式だけあって理解不能か、動作がライブラリに隠蔽されてて理解不能で手が出せなかったけど、この本あれば大分理解できそう。以下、乗ってる内容メモ。 ・Amazon的なリコメンドのしくみ ・データのグループ化(クラス
404 Blog Not Found:プログラマーでなくても名前ぐらい覚えておきたいアルゴリズムx10
2007年11月26日18:15 カテゴリMathLightweight Languages プログラマーでなくても名前ぐらい覚えておきたいアルゴリズムx10 ぎくっ あなたが一番好きなアルゴリズムを教えてください。 また、その理由やどんな点が好きなのかも教えてください。 - 人力検索はてな なぜぎくってしているかというと、実はすでにアルゴリズム本の発注を受けているからなのだ。いつまでも伏せておくのもなんなので、ここにえいやっとdiscloseしてしまうことにする。 アルゴリズム大募集! C&R研究所 - トップページ その下書きもかねて、そこでも紹介しないわけに行かないメジャーなアルゴリズムをとりあえず10個紹介しておくことにする。 ユークリッドの互除法(Euclidean algorithm) その昔(数百年ほど前)は「アルゴリズム」といえば、「手順一般」を指すのではなく、この「互除法
アルゴリズム百選 - フィボナッチ数列にO()を学ぶ : 404 Blog Not Found
2007年11月28日18:00 カテゴリアルゴリズム百選Math アルゴリズム百選 - フィボナッチ数列にO()を学ぶ 404 Blog Not Found:プログラマーでなくても名前ぐらい覚えておきたいアルゴリズムx10、これほどの反響になるとは。200ブクマぐらいは予想していたが、もいくとは。 とりあえず、本の仮題を「アルゴリズム百選」として、「アマグラマーのすすめ」と同じように本blogに草稿を書いていくことにする。「メインページ」の「アルゴリズム大募集! C&R研究所 - トップページ」の方も適宜更新していくが、「その場で動かせるコードサンプル」はここでないと書けないので。 ただし、「アマグラマーのすすめ」よりは書き方は順不同になるはず。それでも序文相当のことは「チラ見」ならぬ「チラ書き」しておいた方がいいだろう。というわけで、序文に変えて紹介するのが、本Entry。 ヒントとな
第6回 上手なアルゴリズムの見つけ方
図1に示すHTML形式のテキスト・データ（以下，HTMLデータ）があります。このHTMLデータをブラウザに表示させたときに「表示される文字列」と「その文字列に対して有効なタグ名」を対応付けるアルゴリズムを考えてください。結果は配列に格納して，画面に表示させるものとします（図2）。 見わたせば，世の中はアルゴリズムだらけです。私のようなプログラマは，日常生活でも「締め切り順に仕事をソートしてごらん」「仕事のスタックがたまっているからてんてこまい」など，いま置かれている状態をアルゴリズムやデータ構造になぞらえて会話することがよくあります。前回紹介した再帰処理と言えば，落語の演目の一つ，「頭山」です。自分の頭に生えた桜の木を引っこ抜いて，その跡にできた池に自分自身が身を投げる，という不思議な話ですが，これこそ再帰処理をよく言い表していると思います。 このように世の中には，ハッシュだってスタックだ
きまぐれ日記: 動的配列への追加コストはなぜ 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」の確率もある、という風に計算を行なう。
きまぐれ日記: ソートの平均要素移動距離
配列をソートする際に各要素の平均移動距離はどれくらいになるか問題が同僚の間で話題になった. 結論から言ってしまえば，サイズ n の配列の場合平均移動距離は n/3 になるらしい． サイズ n の場合, 最右の要素は [0 .. n-1] に等確率で移動するので，直感的に考えると n/2 のような気がする．しかし，真ん中の要素は両側に移動するので，その距離は小さくなる．平均移動距離は n/2 より小さい値になるはずだ. 頭で考えるより手を動かしたほうが楽なので，モンテカルロサンプリングしてみた. 配列をランダムにシャッフルし，ソート済みの配列と比較して各要素の平均移動距離を求める．これを 1000 回繰り返し平均値を計算する. #include <iostream> #include <vector> #include <cmath> #include <algorithm> static
第2回 パズルみたいに楽しいデータ圧縮
適当な圧縮ルールを作り，ASCII文字で描いた絵（図1）をなるべく少ない文字数で表現してください。 ある日のこと，ぼーっとした頭で仕事をしていると，同僚がそれはもう満面の笑みを浮かべて「プログラムで使っている画像データを圧縮するためにLZSS＊1を実装してみたんですよ。ふふん，どうよ」と話しかけてきました。「ぬあ?」とそれがどうした的に返事をしつつも，ふと気づいたのは，何らかの圧縮プログラムやアルゴリズムを作った経験を持つプログラマは意外に多いということです。すでにzlibなどの著名な圧縮ライブラリが公開されていますが，「ブロックソート」や「PPM」などの新しい圧縮方法が日夜開発されています。 どうも圧縮というのは，プログラマ心をそそる何かがあるようです。今回はそんな圧縮アルゴリズムの不思議で魅力的なところを紹介します。パズルのような圧縮アルゴリズムの楽しさを感じていただければと思います。
JavaScript でソートアルゴリズムを可視化 - bkブログ
JavaScript でソートアルゴリズムを可視化 JavaScript でソートアルゴリズムを可視化するプログラムを書いてみました。元ネタは Jon Bentley による ソートアルゴリズムを可視化する Java アプレットです。 アルゴリズム 要素数 動作確認は Firefox 2, IE 7, Opera 9 で行いました。要素数は最大で200まで選べますが、かなり重くなるので遅いマシンで実行すると危険です。 English version is also available. ソースコード: sort-animation.js 解説 X軸が配列の添え字、Y軸が配列の要素の値を示しています。最初に要素がランダムに並んでいる配列 (値に重複なし) を作って、それを各種のソートアルゴリズムでソートする様子をアニメーションで表示します。 ただし、要素のあらゆる変更に対して毎回表示を更新し
地球にやさしいアルゴリズム---目次 - 地球にやさしいアルゴリズム：ITpro
アルゴリズムを構成している楽しい仕組みを紹介しながら，あなたに「おおっ」と言わせることが，本連載の最初の目的です。興味を持てたなら，アルゴリズムに関する文献や情報を抵抗なく読めるようになるはずです。アルゴリズムを使いこなしたり，作ることも無理なくできるようになるでしょう。 まずはいろいろなアルゴリズムの面白いところを見て，楽しんでみましょう 第1回 ナンプレを解いてみよう 第2回 パズルみたいに楽しいデータ圧縮 第3回 「場面」の移り変わりに注目する 第4回 できるだけ短いルートでゴールに到達する 第5回 隣の区画と異なる色で地図を四色に塗り分ける 第6回 上手なアルゴリズムの見つけ方 第7回 多対多の関係を賢く扱う 第8回 倉庫番を解くアルゴリズム 第9回 プロトコルを実現するアルゴリズム 第10回 麻雀の役を判定する 第11回 プログラム同士の対戦ゲーム 第12回 対戦ゲームの戦略を考
アルゴリズムの紹介
ここでは、プログラムなどでよく使用されるアルゴリズムについて紹介したいと思います。 こんなことやって意味あるのかどうか正直言って迷いました。プログラマはたいてい知っているような内容だし見る人もいないんじゃないかと思いましたが、これからプログラミングを始めてみようという方にとっては参考になるかもしれないし、何よりも自分にとって頭の中を整理できたりするので、これから定期的にやっていこうかと考えてます。 ところで、紹介する内容はほとんど過去に出版された書物関係から抜粋しています。一応下の方に参考文献として挙げておきますので興味を持たれた方は書店などで探してみてはいかがでしょうか？ ということで、まずはライン・ルーチン(画面に直線を描画する)についての紹介です。
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
http://yimado.s-lines.net/algo_and_ds/
UNIXの楽しみ