並列アルゴリズムについて

タイトルの割に不穏なタグが・・・

何のためかは後述しますが学校の図書館へ。
前回書いたこともあってアルゴリズムイントロダクションの並列アルゴリズムの章を。３巻の内容だった。まあさすがにExtraな内容かも。
で、抽象機械PRAM(Parallel Random Access Machine)の説明のあと、長さnのリンクリストの長さをn個のプロセッサでO(lg n)で求めたり、それをちょっと応用してy(k)=x(k) op x(k-1) op x(k-2) op ... op x(1)を(opは任意のオペレーション、y(k)はx(1)からx(k)までの和とか積とか)求めたり。で終了。限界が来た。ポインタ飛び越しとか何なのほんと・・・。なんでそんな発想が出てくるの・・・。まあ非並列の頭で考えるリストの線形操作をlogにしてる時点で怪しげな雰囲気が漂ってたのは確かだが・・・。

どうもlogに「桁数」という直感が抜けている。log10で十進数の桁というのは高校数学でやったんだが。どうしても指数関数の逆関数のイメージばかり。いやまあどちらもまさにその通りなんだけれども。アルゴリズムにありがちなlog2も結局二進数の桁数(ビット数)なんだけど。logを知らない人にlogを教えるときに

• 簡単に言うと
  • 指数関数の逆ですね(y=2^xのグラフをxとyでひっくり返したものですね)
  • 桁数のことですね(1000のlogは0が3個で3ですね)

(底は気にするなよ)
あなたはどちらにしますか？どちらの方がわかりやすいと思いますか？(下の説明をしているのを見て違和感を感じただけ)
もしかしてオレって学校の数学で常用対数と桁をやる前に二分探索に目覚めてた・・・？(対数時間のアルゴリズムの初見時って「悟り」があるよね)

で、本題のなんで図書館へ行ったかというと10時にならないと店が開かなかったから。DS修理中だけど買おうと思って。これですよこれ。2:00AMに起きてPCであんなことしたりこんなことしたりした後松屋で食事して行ったら開いてなくて。9:30PMだったか。で、0:00PMくらいに行ったら売り切れ。空箱カウンターに持って行ったら「売り切れのシールがはがれてたみたいです」。遊戯王はごく一部のマニアックな人だけのものだといつの間にか思い込んでいたようです。そりゃ私の歳に限ればそうだけれども。かなり大衆向けだったよね・・・。DS返ってくるまでに買えるか？

遊戯王ファイブディーズ スターダスト アクセラレーター ワールドチャンピオンシップ2009

アルゴリズムイントロダクションを張らずに遊戯王を張る。まさに外道。
しかしアルゴリズムイントロダクションは数学理論がしっかり丁寧に書いてはあるけどそれが身上の人以外には少々読みにくいのではと思うこともある。信頼はできるんだけれども。もう少し直感重視だけどイントロダクションで扱われている項目くらいのレベルのことが書かれている本ありませんかね。概要の予備知識があればイントロダクションが読みやすくなってしっかりした理論説明もできるようになって万々歳なんですが。
といいつつ読んじゃう。くやｓ（ｒｙ
実はタイトルがかっこいいから読んでるとかいえなi
表紙もかっこいi(日本語版の方がかっこいい、でも図書館の本は全部カバー外されててダメ)
Introduction to Algorithms(原題)。「アルゴリズム入門」。「入門」、ですよ・・・。