アルゴリズムデザイン

Ａｌｇｏｒｉｔｈｍ　ｄｅｓｉｇｎ．

共立出版
ジョン・クラインバーグ　エーバ・タルドシュ　浅野孝夫　浅野泰仁　小野孝男（情報科学）　平田富夫　

• 価格: 18,700円（本体17,000円＋税）
• 発行年月: 2008年07月
• 判型: Ｂ５
• ISBN: 9784320122178

内容情報

[BOOKデータベースより]

はじめに：いくつかの代表的問題
アルゴリズム解析の基礎事項
グラフ
グリーディアルゴリズム
分割統治法
動的計画法
ネットワークフロー
ＮＰと計算困難性
ＰＳＰＡＣＥ：クラスＮＰを超える問題のクラス
計算容易性の拡大
近似アルゴリズム
局所探索
乱択アルゴリズム

[日販商品データベースより]

本翻訳書は、Jon Kleinbergと ?va Tardosの著書“Algorithm Design”の全訳である。訳者が原書の翻訳に至ったのは、2005年5月にボルチモアで開催されたACMのSTOC（Symposiumon
Theory of Computing）の国際会議において、Addison-Wesley社のブースで原書を手に取ったときの新鮮な感銘からである。組合せ最適化の分野の著名な賞であるファルカーソン賞を受賞した ?va Tardos教授と翌2006年にチューリング賞と並ぶ情報科学のネバンリンナ賞を受賞したJon Kleinberg教授の初めての本であるということもさることながら、アルゴリズムデザインに対する著者の世界観が具現されていて、これまでに類のない画期的な本に仕上がっているという強い印象を受けたからである。そして、是非とも日本の多くの学生や研究者に、著者のアルゴリズムデザインの世界観を紹介したい、むしろ、しなければならない、という気持ちで、日本語訳の許可を著者に依頼して快諾されたのである。

　著者の序文にもあるように、著者のアルゴリズムデザインの世界観は以下のとおりである。アルゴリズム的な考え方は、情報科学分野はもちろん、実社会の様々な分野に広く浸透してきている。実際、伝統的な旧来の分野にとどまらず、インターネットのルーティングプロトコル、ゲノムインフォマティクス、組合せ的オークション、Web広告バナーの提示、等の新規分野の至るところでアルゴリズムが利用されている。しかし一方で、現実に起こる問題が、きれいに定式化された数学的な形式の問題として現れることは極めてまれである。むしろ、煩雑な細部が大量に付随しているのが普通であり、その中には本質的なものも余分なものもあったりする。したがって、アルゴリズムデザインの実際的な作業は、問題の中の、数学的な核となる部分を見出す仕事と、問題の構造に基づいた適切なアルゴリズムデザイン技法を見極める仕事という、二つの基本的な構成要素からなっている。これら二つの構成要素は相互に関連し合っている。すなわち、様々なアルゴリズムデザイン技法に習熟すればするほど、問題に潜んでいる煩雑な情報からきれいな定式化を導き出すことができるようになる。さらに、アルゴリズム的な考え方により、通常では見えなかったものまでが見えてくるようになる。潜んでいる問題を明快に表現する言語を習得でき、そしてそれを用いて、さらなる展開への扉が開けるという点に、アルゴリズム的な考え方の最大の効用がある。