ASAHIネット(http://www.asahi-net.or.jp)のjouwa/salonからホットコーナー(http://www.asahi-net.or.jp/~ki4s-nkmr/ )に転載したものから。
---
http://iiyu.asablo.jp/blog/2008/09/04/3741466
Re: Jon Kleinberg, Eva Tardos著「アルゴリズムデザイン」
の続き。

　アマゾンから、
http://www.amazon.co.jp/exec/obidos/ASIN/0521872820/showshotcorne-22/
Algorithmic Game Theory (ハードカバー)
Noam Nisan (編集), Tim Roughgarden (編集), Eva Tardos (編集), Vijay V.
Vazirani (編集)
を推薦しますというメールが来た。

http://iiyu.asablo.jp/blog/2008/02/29/2672473
注目のコンピュータサイエンス本
で紹介した
http://www.amazon.co.jp/exec/obidos/ASIN/038720248X/showshotcorne-22/
Parsing Techniques (Monographs in Computer Science) (ハードカバー)
Dick Grune (著), Ceriel J. H. Jacobs (著)
を買ったからだそうだ。
　どうつながるのか、わからんけど。
　「Algorithmic Game Theory」って、直訳するとアルゴリズム的ゲーム理論。
　あれ？　ごく最近、これ、なんか、どこかで見たなあ、どこだっけなあと思
って、３日３晩うなされて、やっとわかった。

http://iiyu.asablo.jp/blog/2008/09/02/3735338
Jon Kleinberg, Eva Tardos著「アルゴリズムデザイン」
で、おっしゃ、おれも男だ。買ってやるわいと意気込んだ
http://www.amazon.co.jp/exec/obidos/ASIN/4320122178/showshotcorne-22/
アルゴリズムデザイン (単行本)
Jon Kleinberg (著), Eva Tardos (著), 浅野孝夫 (翻訳), 浅野泰仁 (翻訳),

小野孝男 (翻訳), 平田富夫 (翻訳)
の著者の一人、Eva Tardos先生が、アルゴリズム的ゲーム理論の専門家。著者
紹介にそう書いてあった。
　でね、「Algorithmic Game Theory」をみると、編者の一人に、Eva Tardos
先生の名が。
　それで、どこかでみた言葉だなと思ったのね。
　まだ、脳みその神経つながっとるのぉ。＼(^O^)／

　「Algorithmic Game Theory」は、出版元のケンブリッジのサイトに詳しい
紹介があります。
http://www.cambridge.org/us/catalogue/catalogue.asp?isbn=9780521872829
Algorithmic Game Theory
　Reviewsに書いてあることなんか、ちょっとわくわくさせますよね。

　さて、「アルゴリズムデザイン」のこと。
　出荷が遅れたけれど、来ました。ざっと見ただけ。でかい、重い、難しそう
で、枕にもなるし、お休み前に読むと、すっと睡眠に入れました。＼(^O^)／
　この本、学部の「アルゴリズムの基礎」の教科書、大学院の入門用だそうだ。
　すげえ、学生、こんな高い本(アメリカでも定価100ドル以上)、買うのか。
　さすが、アイビーリーグの名門、コーネル大学。＼(^O^)／
　この内容が、「アルゴリズムの基礎」なのか。
　さすが、アイビーリーグの名門、コーネル大学。＼(^O^)／

　第２章、第３章は、「アルゴリズムの基礎」以前の科目で取り上げているの
で、その復習的な章としているが、これが、フツー、日本の大学、たとえば、
九大とかなら、「アルゴリズムの基礎」じゃないかな。
　計算量やアルゴリズム解析の基礎知識と、グラフ理論をやっている。何度も
書くけど、グラフといっても円グラフなどのグラフじゃなくて、ネットワーク
ね。
http://iiyu.asablo.jp/blog/2008/07/08/3615983
中田育男著「コンパイラの基盤技術と実践」
で紹介した
http://www.amazon.co.jp/exec/obidos/ASIN/432001846X/showshotcorne-22/
やさしく学べる離散数学 (単行本)
石村 園子 (著)
よりは、ずっと綿密で難しい話が出てきます。
　中田先生の「コンパイラの基盤技術と実践」は、ちゃんと買ってざっと眺め
たんだけど、感想書いてませんね。とにかく、フツーのコンパイラ本とは全然
違いますよ。

　「アルゴリズムデザイン」に戻ると、全編を通じて、すごくしっかりした書
き方。ぶれないね。
　フツー、アルゴリズムの教科書って、天下り式に、こういうアルゴリズムが
あって、こんな性質があって、こういうときは、このアルゴリズムを使うんだ
よって書いてあるのが、ほとんどでしょ。
　クヌース先生の、かの有名なアルゴリズム大辞典
http://www.amazon.co.jp/exec/obidos/ASIN/475614411X/showshotcorne-22/
The Art of Computer Programming Volume1 Fundamental Algorithms Third
Edition 日本語版 (ASCII Addison Wesley Programming Series) (単行本)
ドナルド・E・クヌース (著), 有澤 誠 (編集), 和田 英一 (編集), 青木 孝
(翻訳), 筧 一彦 (翻訳), 鈴木 健一 (翻訳), 長尾 高弘 (翻訳)
から始まるシリーズだって、そうだもんね。

　この本の主張は、
「ばかー。そんなんじゃ、真のアルゴリズム力は身につかん＼(^O^)／」
です。
　なるほど。野口悠紀雄のITじゃ、真のIT力は身につかん。勝間和代本じゃ、
真の力は身につかんというのと、同じか。^^;
　いやいや、クヌース本は、わしらの世界で定番中の定番だから、そんなにひ
どくないって。
　そ、そうか。おれにとっては、本書もクヌース本も、どっちも枕か漬物石だ
もんな。＼(^O^)／
　そんなこんなで、この本では、身近な話題から、問題の本質をえぐって、そ
れをどう数理的に考えて、アルゴリズムの設計にむすびつけていくか。それを
丹念にやっています。
　計算量がどうなるかは、みっちりやってますね。NP困難、NP完全、PSPACE完
全の世界。
　書くほうは、これ、手間がかかるよ。いい題材を見つけるのも面倒だもんね。
　身近な話題といっても、コンピュータやインターネットに関係するような話
題は多い。
　たとえば、グラフ理論の演習問題だと、コンピュータの通信記録をみて、あ
るコンピュータがウイルスに感染したとすると、ある時刻には、どこまで感染
が広がっているか調べるアルゴリズムを書けなんてのがあります。
　キャッシュの追い出しはどう考えればいいか、局所的な情報しかもってない
ルータが、全体として最適な経路を作り上げるには、どんなアルゴリズムがい
いかとか、最後の第１４章は、高速パケットスイッチングの話だしね。
　といっても、第１章に選ばれている題材は、簡単にいうと、昔懐かしい「フ
ィーリングカップル５対５」＼(^O^)／
　つまり、最適で安定なマッチングをどう作るかという話。
　これ、数理経済学者のDavid GaleとLloyd Shapleyが提起した問題だそうで
す。経済学からの話題も目につきました。
　マルチキャストルーティングの話では、経済学でも出てくるゲーム理論のナ
ッシュ均衡が出てきます。
　おれ、アルゴリズム的ゲーム理論とはどういうのか、全然知らないけれど、
　この辺がそうなんですかね。
http://keisan-genkai.lab2.kuis.kyoto-u.ac.jp/reports/2007/zentai_1/C03-asano.ppt
個人的効用と社会的効用の対立問題 に対するアルゴリズム的アプローチ
には、本書で取り上げてある題材が出てきますね。ナッシュ均衡のネタは、マ
ルチキャストルーティング下でのコスト負担をどうするかという話で、本書と
同じですね。

http://keisan-genkai.lab2.kuis.kyoto-u.ac.jp/reports/2006/zentai_2/04-tokuyama.ppt
計算理論の現状と未来
は、そうか、アルゴリズム屋は、そういうことを考えているのかと思いました。
http://iiyu.asablo.jp/blog/2007/05/23/1527799
共立出版「アルゴリズム・サイエンスシリーズ」
で書いたように、
http://www.amazon.co.jp/exec/obidos/ASIN/4320121686/showshotcorne-22/
岩間一雄著「アルゴリズム・サイエンス:出口からの超入門」
を読んだとき、こいつら、普段、何を考えとるんじゃと思ったもん。
　余談だけど、おれ、PowerPointもってないけど、この２つの.pptファイルは、
OpenOfficeでばっちり読めました。

http://ja.openoffice.org/
OpenOffice

　ということで、「アルゴリズムデザイン」を枕にして毎日寝れば、頭がよく
なるかもよ。＼(^O^)／