昨年の10月11日に開催された清水市代女流王将とコンピュータ将棋「あから2010」との対局は記憶に新しい。 あから2010は、169台676coreを使った合議によるコンピュータ将棋マシンだった。 「文殊」の論文*1が発表されたときから、私は「合議は全く意味がないし、普通にクラスター並列化したほうが強い」と主張し続けてきた。 「1台のマシンと、そのマシンを3台使って合議させたものとを対局させて、3台合議のほうが有意に勝ち越したから合議は意味がある」みたいな結論を出すのはおかしい。3台のマシンで普通にクラスター並列化したものと、3台で合議したものとをなぜ真っ先に比較しないのか？ 3台のマシンで単純にクラスター並列化したものより3台のマシンで合議したもののほうが圧倒的に弱ければそれは単にマシンリソースの無駄遣いに他ならないし、その比較すらせずに169台のマシン用意しましたって馬鹿じゃないの。大

TwitterのTLで知ったのだが、少し前に海外の掲示板で"sleep sort"というソートアルゴリズムが発明され、公開されたようだ。このアルゴリズムが面白かったので紹介してみる。 Genius sorting algorithm: Sleep sort 1 Name: Anonymous : 2011-01-20 12:22 諸君！オレは天才かもしれない。このソートアルゴリズムをみてくれ。こいつをどう思う？ #!/bin/bash function f() { sleep "$1" echo "$1" } while [ -n "$1" ] do f "$1" & shift done wait example usage: ./sleepsort.bash 5 3 6 3 6 3 1 4 7 2 Name: Anonymous : 2011-01-20 12:27 >>1 なん…だと

最大流問題単語 サイダイリュウモンダイ 1.1千文字の記事 14 0pt ほめる 掲示板へ 記事編集 概要フロー増加法例最大流最小カット定理関連項目掲示板最大流問題とは、最大の流量を求める問題である。線型計画問題のひとつ。 概要 例えば、ある地点から他の地点に物資を送るとする。このとき、いくつかの地点を経由し、分岐や合流をしながら物資が送られるとする。送られる過程で、それぞれの地点からそれぞれの地点に一度に送ることのできる量の最大値が決まっている際、全体で一度に送れる量の最大値はいくらなのか。これを考えるのが最大流問題である。最大流問題では、送られる量をフロー、出発点をソース、終着点をシンクという。 フロー増加法 最大流問題を解くアルゴリズムのひとつ。 フローをすべて0にする。 残余ネットワーク(後述)を求める。 残余ネットワークにソースからシンクへつながる路がなければ、6へ飛ぶ。あれば、

最短経路問題単語 サイタンケイロモンダイ 2.8千文字の記事 7 0pt ほめる 掲示板へ 記事編集 概要ダイクストラ法例関連項目掲示板最短経路問題とは、出発点から目的地までの最短経路を求める問題である。線形計画問題のひとつ。 概要 例えば、電車を乗り継いで駅間を移動する場合、複数のルートが考えられることがある。その場合、どの線に乗るか、どの駅で乗り換えるか等で移動距離や所要時間が変化する。では、どのルートを通れば最も効率的に行けるのか。これを考えるのが最短経路問題である。最短経路問題の対象になるのは距離、時間、費用など様々あるが、ここではすべて「距離」という表現で統一する。最短経路問題で必要となる情報は、出発点、目的地、経由地、各地点のつながり(どこからどこへ直接アクセスできるか)とその距離である。 ダイクストラ法 最短経路問題を解くアルゴリズムのひとつ。 未確定リスト、確定済リスト、各

追記：ハッキリ言ってこの正規表現はネタなので，実際に素数判定を行いたい場合は，もっと別な賢いアルゴリズムを使ったほうが良いです 正規表現で素数が判定できるという記事を見たので試してみた． http://www.noulakaz.net/weblog/2007/03/18/a-regular-expression-to-check-for-prime-numbers/ この記事によると /^1?$|^(11+?)\1+$/ という正規表現を使うと，素数判定が出来るらしい．ある整数 n が素数かどうか判定したい場合は，"1" * nという文字列がこの正規表現にマッチするかどうかを調べればよく，マッチすれば非素数，マッチしなければ素数となる．ただし，"1" * n は，例えば，n が 4 ならば "1111" と 1 が 4 回連続して続く文字列となる． Rubyで書いた素数判定プログラムはこん

かつてのMac OS9までの描画エンジンの主役はQuickDrawが担っていた。GUIなOSでは、文字も含めてすべてをグラフィックとして扱うので、画面に見えているすべてのもの*1はQuickDrawによって描かれていたことになる。描画エンジンは、GUIなOS開発の要となる技術である。その出来が、GUIなOS開発の成否を分けるとも言える。 そして、最初期のQuickDrawは、ビル・アトキンソンがたった一人で開発したそうである。 当時（25年以上前）のCPUは、動作クロックが8MHzという性能だった。（現在は2GHz=2000MHzかつ、複数コアが当たり前） そのような性能であっても、違和感なくマウスで操作できるOS環境にするために、斬新な発想や試行錯誤を重ね、相当な努力の末に開発されたのがLisaやMacintoshであった。 Amazon.co.jp： レボリューション・イン・ザ・バレー

AI将棋 Version 17 for Windows DVD版がWindows 7のマルチタッチ対応になり、そのインタビュー記事がMicrosoft公式サイトに掲載された。 【Windows 7 マルチタッチ対応】AI将棋Version 17 - タッチは思考を阻害しません http://www.microsoft.com/japan/powerpro/TF/interview/38_1.mspx ところでこのインタビュー記事の内容がひどすぎる。 ・ やはり将棋ソフトは強さが人気の秘訣なのですか? もちろん、箔が付くという面はあります。 例えば「AI将棋」はアマ 4 段の認定を将棋連盟から頂いています。 しかしながら、強さで言うと、実は現在、世界中の将棋ソフト全体が課題を抱えているといえるのです。 ・ どういうことですか? 思考エンジンの現在のトレンドが、データベース参照型になっていると

insertion sortは「挿入ソート」と訳される。(Wikipedia→ http://ja.wikipedia.org/wiki/%E6%8C%BF%E5%85%A5%E3%82%BD%E3%83%BC%E3%83%88 ) ■　日本語版 Wikipediaの日本語のページのコードを引用すると次のようになっている。 for (i = 1; i < n; i++) { tmp = data[i]; for (j = i; j > 0 && data[j-1] > tmp; j--) { data[j] = data[j-1]; } data[j] = tmp; }上のコードでは、内側のループでinsertの必要がなかった場合でも最後にdata[j] = tmpでtmp変数をwrite backしており、しかも、insertの必要のなかった場合でもj=iが1回実行される。それらの意味に

昨日の記事で、世間で広く知られているinsertion sortのコードがいかにひどいかについて書いた。 私の提案したコードをWikipediaにも掲載(注記としてだろう)したほうがいいのではという意見をいくつか頂戴した。 Yuichirou 2009/11/26 02:03 私はyaneuraoさんのコードの方が可読性にも優れていると思います。むしろ日本語版Wikipediaのコードは脱出条件が複雑な内側のループを無理にfor文で書いているため、可読性が落ちています。 yaneuraoさん、ぜひその最後のコードをWikipediaに掲載すべきだと思いますがいかがでしょうか。 上のYuichirouさんの意見は好意からだろうが、はてブでは、次のような否定的な意見も見られる。 shuji_w6e 「馬鹿すぎる」とか「駄目すぎる」とか何様なんだろ？調べて回ったついでに全部書き換えてくればいいの

こんにちは、電設部の塚田です！ 月日の流れは早いもので、もう11月も半ばを過ぎ、7月の暑い日に産声をあげたこの連載も4回目となりました。来年3月に筆者は学校を卒業いたします。それまでに、まだまだたくさんの学生スターエンジニアに会いたい、話を聞きたい所存です。皆さま、どうかお付き合いくださいませ。 「学生スターエンジニア」4人目は、アルゴリズマー 高橋直大！ 第4回のターゲットは高橋直大さんです。慶應義塾大学 環境情報学部の2年生で、ITmedia エンタープライズにて「最強最速アルゴリズマー養成講座」という連載を行っています。 彼のことを知ったのは、Imagine Cup 2008（筆者注：マイクロソフトが主催する、全世界の学生向け技術コンテスト）が開催された2008年の7月です。彼は、この大会のアルゴリズム部門で世界第3位という快挙を成し遂げました。この偉業を報じる各メディアの記事を見て

超気合を入れた日記を書いたところ投稿寸前でマウスのもどるボタンを押してしまい、消滅したため箇条書きでテキトウに書きます。 前々回でいう6の部分の話。 作戦 先に進むには視点(正面とか、右斜め上とか）の違いに強い髪型類似検索が必要 人が似ていると感じる基準→視点の変更に影響を受けない、画素の並びとしての画像→視点の変更に非常に影響を受ける イラストは意識的に視点が変えられていることが多いので「正面のみ」と言って逃れる事ができないのでやるしかない この条件はImager::AnimeFace(アニメ顔検出器)のときにもあった 一般画像認識でも様々な視点の違う画像も分類できている←教師ありだからできる SimHash(参照 lsh p-stable) 同じ髪型なら視点が異なっても似たHash値かつ髪形が違うと似てないHash値になるような変換を求めたい（存在する全ての髪型において！） 教師データ

ふと、ビット並列アルゴリズムを使った編集距離を計算するアルゴリズムを書きたくなったので書いてみた。 まず、通常の編集距離であるLevenshtein Distanceを求めるアルゴリズムは以下のように書ける int levenshteinDistance(String A, String B) { int m = A.length(); int n = B.length(); int dp[] = new int[n + 1]; int next[] = new int[n + 1]; for (int i = 0; i <= n; i++) dp[i] = i; for (int i = 1; i <= m; i++) { next[0] = i; for (int j = 1; j <= n; j++) { if (A.charAt(i - 1) == B.charAt(j - 1))

情報処理学会の学会誌『情報処理』の2008年9月号（Vol.49, No.9）に「3日で作る高速特定物体認識システム」という特集記事があります。OpenCVを用いた面白そうなプロジェクトなのでレポートにまとめてみようと思います。3日でできるかはわからないけど。 残念ながらこの記事はPDFを無料でダウンロードすることができません（CiNiiでオープンアクセス可能になったみたいです）。なので会員以外で元記事が読みたい人は図書館でコピーする必要があるかも・・・また、2009年9月号の人工知能学会誌にも物体認識の解説「セマンティックギャップを超えて―画像・映像の内容理解に向けてー」があります。こちらも非常に参考になりますが同様にPDFが手に入りません・・・。他にもいくつかわかりやすい総説論文へのリンクを参考文献にあげておきます。 物体認識とは 物体認識（object recognition）は、画

id:smoking186 さんの指摘を受け, First Authorの名前などを付加しました. どうもです. 記事内のcodeは最適化などを施しておらず, 冗長に, 定義どおりに書いています. ifがまとめられたりとかしますが, そのあたりはご容赦を... Rubyでlevenshtein距離を見て以来, 個人的にdiffブームが来ていた. 計算量O(ND) / O(NP)のalgorithmなどがあるのは知っていたが, 論文(英語)および, 解説のみ, またはソースコードのみなど分かれているものが多く, algorithmに疎い自分には理解するのに大変時間がかかってしまった. しかしやっとわかったので, 解説+JS実装してみる. 解説とソースコードがセットだと, 多少はわかりやすくなるかと... 自分は正直これくらい細かく言われないとすぐにはわかんない人なので(the O(ND)だけ