 |
| アルゴリズム・サイエンス シリーズ （全16巻） 編集委員（五十音順）： 杉原厚吉（東京大学教授），室田一雄（東京大学教授），山下雅史（九州大学教授），渡辺 治（東京工業大学教授） ●シリーズ趣旨：発刊にあたって インターネットやバイオインフォマティクスなど，情報科学は社会への影響力を急速に増大・拡大している．情報科学の基礎を支えるアルゴリズム・サイエンス分野も例外ではない．この四半世紀の進歩はまさに驚異的であったが，現在もその速度は増すばかりのように見える． このような情勢の下に，アルゴリズム・サイエンスに対する時代の要請は以下の４点にまとめられる： まず，並列計算機や分散計算環境が容易に手に入る時代となり，このような新しい計算環境のもとで上手に問題を解決するための新しい解法の開発が必要とされていることである． 次に，バイオインフォマティクスやナノ技術など多くの応用分野が巨大な問題を上手に扱うための新しい計算パラダイムを必要としていることである． 第３に，情報セキュリティという重要な応用分野の出現が，従来は応用に乏しい理論研究と考えられてきた整数論や計算困難性理論の実学としての再構築を迫っていることである． そして最後に，これらの要請に応える健全なアルゴリズム・サイエンスの発展を担う人材の教育・養成である． 以上の状況を踏まえ，われわれは以下の２つの主目的を掲げて，アルゴリズム・サイエンス シリーズを発刊することにした． 第１に， アルゴリズム・サイエンスを高校生あるいは大学初年度生に紹介し，若年層のこの分野に対する興味を喚起することである． 第２に，アルゴリズム・サイエンスのこの四半世紀の進歩を学問体系として整理し，この分野を志す学習者および研究者のための適切な学習指針を整備することである． これら２つの目的を達成するために，本シリーズは通常のシリーズと異なる構成をとることにした．まず，２つの「超入門編」として，『入口からの超入門』と『出口からの超入門』を置いた．これらにより，理論的な展開に興味をもつ学生も，アルゴリズムの応用に興味をもつ学生も，ともに高校生程度の基礎学力で十分にアルゴリズム・サイエンスの面白さを満喫していただけることを期待している． 次に，乱択（確率）アルゴリズムや近似アルゴリズムなどを含む，新たに建設された興味深いアルゴリズム分野を紹介し詳述するために，「数理技法編」として諸巻を設けることにした．『入口からの超入門』がこれらの巻に対する適切な入門書となるように企画されている． さらに，バイオインフォマティクスや情報セキュリティに代表されるような，重要な応用分野における各種アルゴリズムの発展という視点からいくつかのテーマを厳選し，「適用事例編」として本シリーズに加えることにした．これらの巻に対する入門書が『出口からの超入門』である． なお，各巻は大学や大学院の教科書として利用できるよう内容を工夫し，必要な初歩的知識についてもできるかぎり詳述するなど，各著者に自己完結的に構成していただいている． |
 |
| 【超入門編】 | 【数理技法編】 | 【適用事例編】 |
| １．アルゴリズム・サイエンス：入口からの超入門 （2006年10月刊行） |
３．適応的分散アルゴリズム （2010年6月刊行） |
12．バイオインフォマティクスの数理とアルゴリズム （2007年2月刊行） |
| ２．アルゴリズム・サイエンス：出口からの超入門 （2006年10月刊行） |
４．乱択アルゴリズム （2008年8月刊行） |
13．暗号プロトコルと情報セキュリティ技術 |
| ５．オンラインアルゴリズムとストリームアルゴリズム （2007年8月刊行） |
14．データマイニングのアルゴリズム | |
| ６．複雑さの階層 （2006年11月刊行） |
15．量子計算 | |
| ７．論理関数―充足可能性問題を中心に | 16．化学系・生物系の計算モデル （2009年9月刊行） |
|
| ８．現代データ構造 | ||
| ９．離散最適化 | ||
| 10．計算幾何―理論の基礎から実装まで （2007年1月刊行） |
||
| 11．近似アルゴリズム―離散最適化問題への効果的アプローチ |
|
１．アルゴリズム・サイエンス：入口からの超入門 （ISBN4-320-12167-8） 浅野哲夫 著 A5，244頁，2400円 ●内容 アルゴリズム研究の楽しさを知ってもらうために，高校生の学力程度で十分に理解できるよう心がけて記述した．各章の終わりに，本当に著者が伝えたかったことを「著者の独白」としてまとめたり，文章の途中に「質問」を挿入したりして，読者に飽きさせない工夫を随所にほどこした． ※組み見本 P74 P148 ※まえがき （PDFファイル） ●目次 （詳細目次 PDFファイル）
|
 |
| ページトップへ |
| ２．アルゴリズム・サイエンス： 出口からの超入門
|
 |
| ページトップへ |
|
３．適応的分散アルゴリズム （ISBN978-4-320-12251-2） 増澤利光・山下雅史 著 A5，324頁，3600円 ●内容 相互結合された多数の計算機から構成される分散システム上で，ある問題を効率良く解決するための方法を記述したものが分散アルゴリズムであって，分散システムに属する各計算機上で動作する（通信命令を含む）逐次アルゴリズムの集合である。並列アルゴリズムは分散アルゴリズムとほとんど同じように定義される。しかし，並列アルゴリズム（および逐次アルゴリズム）と分散アルゴリズムはその対象に明確な相違がある。 まえがき （PDFファイル） ●目次 （詳細目次 PDFファイル）
|
 |
| ページトップへ |
|
４．乱択アルゴリズム （ISBN978-4-320-12170-6） 玉木久夫 著 A5，240頁，3000円 ●内容 アルゴリズムの振舞いを乱数に依存させる乱択アルゴリズムが流用されており，単にアルゴリズムといえば，今日では乱択アルゴリズムを含んでいると考えるのが普通である。しかし，実用アルゴリズムの世界では，乱択アルゴリズムの効果と価値が十分に認識されているとは言い難い。この状況を改善するには，アルゴリズム教育において乱択アルゴリズムに正当な地位を与える必要があろう。全体として，さまざまな分野の乱択アルゴリズムを網羅することは考えず，少数の乱択アルゴリズムを例として基本的な考え方のパターンを掘り下げる方針を採った。本書のレベルはやや高度であり，大学院あるいは学部の高学年でアルゴリズム理論とその基礎になる数学的素養を既に身につけた人，あるいはこの分野でこれから研究を始めようとする研究者を主な対象としている。 ●目次
|
 |
| ページトップへ |
|
５．オンラインアルゴリズムとストリームアルゴリズム （ISBN978-4-320-12171-3） 徳山 豪 著 A5，236頁，3000円 ●内容 未知の未来に関る決断や予測は人間生活では必須であり、最善と信じて行った行動が後で大きな後悔を生むという事は日常茶飯事である。オンラインアルゴリズムの理論は、このような未知の未来に影響する情報処理を的確に行うための計算理論であり、時事刻々変化する巨大データに対して、将来どのような状況が起きても困らないように行動をプランする最善の手法の設計と数理的解析を探求するものである。本書はオンラインアルゴリズム理論の基礎理論である競合比解析に始まり、オンライン学習、確率的最適化、ストリームアルゴリズムなど、最先端の計算理論を用いた最新成果までを網羅し、実際に即した判りやすい例題を利用してオンラインアルゴリズムを幅広い見地から紹介する、世界でもはじめての本格的な教科書である。 まえがき （PDFファイル） ●目次 （詳細目次 PDFファイル）
|
 |
| ページトップへ |
|
６．複雑さの階層 （ISBN4-320-12172-4） 荻原光徳 著 A5，296頁，3400円 ●内容 計算量理論とは、計算にかかる手間（計算の複雑さ）をモデル計算機を用いて系統立てて研究する、理論計算機科学の一分野であり、Juris HartmanisとRichard Stearnsが1965年にアメリカ数学会誌に発表した論文"On the computational complexity of algorithms"によって創設された。その主眼は、計算問題のむずかしさを、それを解くアルゴリズムを実行する手間がどれくらいであるかによってクラス分けし、それらのクラスの性質および相互関係を調べることである。 計算量理論の分野は、1970年代初頭にStephen CookとLeonid Levinによって独立に提唱され、Richard Karpによって整備されたNP完全性の概念によって飛躍的進歩を遂げた。この概念は、計算量のクラスの性質を、そのクラスの代表的問題を通じて研究することを可能にした。 本書の主眼は、チューリング機械を用いて定義される基本的計算量クラスとその階層構造と包含関係について解説すること、そして、それらのクラスの完全問題を示すことである。紙面の都合上、とりあげることのできなかった発展的内容については、巻末の参考文献などを参照されたい。 なお、本書に登場する用語には、それに対応する英語を示してある。また、外国人名に対しては、少し強引なところもあるが、そのカタカナ読みを付しておいた。読者の参考になればさいわいである。 （「まえがき」より）
※まえがき （PDFファイル）●目次 （詳細目次 PDFファイル）
|
|
| ページトップへ |
|
７．論理関数−充足可能性問題を中心として− 牧野和久 著 A5 ●内容 本書は、アルゴリズムや計算量理論などの計算科学分野において中心的な話題である「充足可能性問題」を中心として、「論理関数」の主にアルゴリズム論的な側面を紹介する。これらを通して、高速なアルゴリズム設計法、計算量解析法などを学ぶ。 ●目次
|
 |
| ページトップへ |
|
８．現代データ構造 定兼邦彦 著 A5 ●内容 大量のデータを活用するにはデータをコンパクトに格納し，かつ高速な検索を行えるようにする必要がある．しかし従来のデータ構造は，それ自身の大きさが問題であった．本書では，大量データ処理のための新しいデータ構造である，圧縮されたデータ構造や，現実 的な計算モデルにおいて効率のよいデータ構造を解説する． ●目次
|
|
| ページトップへ |
|
９．離散最適化 岩田 覚 著 A5 ●内容 グラフ・ネットワークなどの離散構造に関連した最適化問題の中には，素朴な方法では膨大な計算量を要するにもかかわらず，問題の性質をうまく利用して，効率的に最適解を計算するアルゴリズムが知られているものが少なくない．離散最適化を題材に，アルゴリズム設計の基本的な技法と考え方を学ぶ． ●目次
|
|
| ページトップへ |
|
10．計算幾何−理論の基礎から実装まで− （ISBN978-4-320-12176-8） 浅野哲夫 著 A5，252頁，3200円 ●内容 計算幾何学の研究が始まって，はや30年が過ぎようとしている．今では，計算機科学の理論に関するどの国際会議の投稿案内を見ても，計算幾何学が確固とした地位を築いていることは明白であるが，残念ながら，それは計算機科学の理論研究者には当てはまっても，情報以外の研究者や情報科学の学生でさえ，計算幾何学がどんな学問であるかを正確に理解している者は多いとはいえないのが現状であろう．計算幾何学というタイトルの本が，理系の本をそろえた大型書店ですら「計算機科学」ではなく「数学」のコーナーに配架されていることが多いのは，その証拠のひとつということができる． 「計算幾何学」という日本語名は，'computational geometry'という英語名の翻訳であるが，この名前が誤解を生んでいるように思えてならない．そこで，本書のタイトルは「計算幾何学」ではなく，計算の重みをもっと増やした表現である「計算幾何」とした． アルゴリズムは難解だという巷の評価があるが，計算幾何学はアルゴリズムの中でももっとも実学に近い存在ではないだろうか．もちろん，組合せ幾何学に代表される数学的な側面も計算幾何学の重要な一面であるが，実装の面で生じるさまざまな問題に真摯に耳を傾けてきている．実装の際に生じる縮退をどのように扱うか，計算誤差による暴走をどのように防ぐか，主メモリだけではなく外部メモリへのアクセスも考慮したアルゴリズムをどう設計するかなど，いずれも実装から生じた問題点の解決策である． このような観点から，本書では通り一遍の理論だけではなく，理論の成果を実装上でどのように活用するかに焦点を当てた．もちろん，実際のプログラムでは数値誤差に対する対策や，予想しない入力に対処する方法などが必要であるが，紙数の関係上それらの問題については言及できなかった．実装を重視する立場から，もっと多くのプログラムを掲載したかったが，紙数の制限で断念せざるをえなかった．本文に盛り込むことは紙数の関係でむずかしくても，最近ではインターネットで公開するという手もあるので，なんらかの形でせっかく作成したプログラムも公開できればと考えている． 本書は「アルゴリズム・サイエンス シリーズ」と題するシリーズ本のうちの１冊である．計算幾何学の分野で国内では長く研究に従事しているために著者が担当することになったのであるが，なぜ本書の執筆を引き受けたかというと，いちど自分の不確かな知識を整理したいと思っていたからである．また，むずかしいからという理由で避けていた理論にも挑戦してみたかったからである．パラメトリック探索の技法は計算幾何学で重要であるが，今まで自分のものになっていなかったので，これをよい機会としたかった． （「まえがき」より）
まえがき （PDFファイル） ●目次 （詳細目次 PDFファイル）
|
 |
| ページトップへ |
|
11．近似アルゴリズム：離散最適化問題への効果的アプローチ 浅野孝夫 著 A5 ●内容 現在の近似アルゴリズムの研究，すなわち，近似率の下界と上界を明らかにする研究についてわかりやすく解説する．特に，上界を下げるためには，より良い近似率をもつアルゴリズムを設計し解析しなければならないが，そのための系統的な設計解析法である数理計画法に基づくアルゴリズムに焦点を当てて説明する．また，下界を明らかにするための標準的な技法についても触れる． ●目次
|
|
| ページトップへ |
|
12．バイオインフォマティクスの数理とアルゴリズム （ISBN978-4-320-12178-2） 阿久津達也 著 A5，238頁，3000円 ●内容 バイオインフォマティクス（bioinformatics）は生命情報学などと訳されるが，その名のとおり生物学と情報学の学際領域の学問分野であり，DNA配列をはじめとするさまざまな生物学データの情報解析技術の開発，および，それらの情報解析技術を利用して実際のデータを解析し新たな生物学的知識の発見を行なうことの２つが主目的となっている．名前の起源はよくわからないが，ヒトのDNA配列を決定しようというヒトゲノム計画が本格化した1990年代初めごろから目にするようになり，現在では学問分野のひとつとして，ある程度は認知されるに至っている．計算生物学（computational biology）という用語も欧米を中心に広く利用されているが，バイオインフォマティクスとの明確なちがいはなく，同義語と考えることができる． バイオインフォマティクスにはさまざまな情報分野の理論や技術が応用されてきたが，アルゴリズムはもっとも重要なもののひとつである．その理由のひとつは，DNA配列をはじめとする大量のデータを扱わなければならず，その効率的な処理のためにアルゴリズム的考え方が必要だということである．逆に，DNA配列やアミノ酸配列などのバイオインフォマティクスにおける主要なデータを文字列として扱うことができるため，文字列アルゴリズムの応用や新たな問題の定式化が行ないやすいということがあげられる．実際，文字列アルゴリズムの研究者でバイオインフォマティクスの研究に携わっている研究者も多い． 筆者も当初は純粋にアルゴリズムの研究を志し，文字列アルゴリズムなどの研究を行なっていたが，いつのまにかバイオインフォマティクスのとりことなり，現在に至っている．バイオインフォマティクス研究の魅力は，実際に役に立つ可能性が高いということもあるが，それ以上に，生命の神秘を情報科学的立場もしくは数理的立場から解き明かせるかもしれないということにあると考えている．ヒトのDNA配列は30億文字程度からなっている．これは一見，多いように思えるが，A,C,G,Tの各文字が2ビットでコード化できることを考えると，CD-ROM １枚程度の量である．いまでは事務処理ソフトなどを購入すると何枚もCD-ROMがついてくるが，それよりも少ない量のDNA配列の中に，人間を個性のちがいまで含めて再構成できる情報が格納されているのである．そこには何かアルゴリズム的もしくは数理的な原理のようなものがはたらいているはずであり，それを解明したいということが筆者の願いである． これまで述べてきたことから，アルゴリズム的立場からのバイオインフォマティクスに関する教科書の必要性は十分にあると考えられる．しかしながら，すでに多くの教科書が出版されているのに，また新たな本を執筆する必要があるのだろうか？ 執筆の打診を受けた際に一瞬そのことが頭をよぎったが，よく考えると既存の本には少なからず満足のいかない点があることを思い出した．バイオインフォマティクスの教科書は数あれど，アルゴリズム的観点から書かれたものは少なく，必ずしもわかりやすいとはいえない．また，配列データの取り扱いを中心としたものが多く，重要性が増しつつあるタンパク質立体構造や生体内ネットワークについては詳しく説明されていない．そこで，タンパク質立体構造や生体内ネットワークについてもより詳しく説明し，かつ，電車の中でも，もしくは，横になりながらでもほとんどの部分を読むことができ，さらに，主要なアルゴリズムの本質が理解できるような本をめざして執筆することにした．その目標は完全に達成されたとはいえず，本書でカバーしきれなかった話題も少なくないが，ある程度は実現できたのではないかと考えている．もちろんむずかしい，読みづらい，誤りがあるなどの可能性はおおいに残っているので，それらの批判は喜んで拝受し，改訂の機会があればぜひ取り入れていきたい． 本書の構成は次のようになっている．１章では，本書を読むのに役に立つと思われる生物学的背景について説明している．しかしながら，全部が必要というわけではなく，DNA配列やアミノ酸配列が文字列として表現できることを最低限知っていれば，直接２章から読み始めることができる．２章では，バイオインフォマティクスで最重要と思われる配列アラインメントについて説明している．３章では，アラインメント以外の配列解析アルゴリズムについて説明している．４章では，進化系統樹の構成法を中心に説明している．５章では，RNAおよびタンパク質の立体構造の予測や比較について説明している．６章では，システム生物学の進展とともに重要になりつつある生体内ネットワークの数理モデルや特徴について説明している．最初に2.1節を読んだあとで他の箇所を読むことが多少望ましい以外は，各章は基本的に独立している．各節も独立している場合が多いため，むずかしい，もしくは，興味がないと感じた節は読み飛ばして次の節に移ることをお勧めする． 本書はアルゴリズム的観点を中心に書いてあるが，一般的なバイオインフォマティクスの教科書として利用できることも意図している．ただし，アルゴリズム論における基本的な知識，とくに情報系の学部学生が２〜３年生くらいで習う知識を仮定している部分がある．たとえば，グラフに関する基本的な定義や性質，多項式時間アルゴリズムやNP困難性の定義や意味などについての知識を仮定している部分がある．そこで，情報系以外の学生や研究者が本書を読まれる場合は，それらの部分を読み飛ばすか，もしくは，本シリーズの他の巻などを参考にしていただきたい． （「まえがき」より）
まえがき （PDFファイル）●目次 （詳細目次 PDFファイル）
|
|
| ページトップへ |
|
13．暗号プロトコルと情報セキュリティ技術 佐古和恵・寺西 勇 著 A5 ●内容 漏洩や改ざんなどの脅威から情報を守る情報セキュリティ技術では，暗号化技術や認証技術がその中核をなす．本書は，それらの基盤となる「暗号プロトコル理論」に焦点を当てて解説する．暗号プロトコルを採用することにより，運用に頼る部分を小さくしつつ，複雑なセキュリティ要件を達成するシステムを設計することが可能となる． ●目次
|
|
| ページトップへ |
|
14．データマイニングのアルゴリズム 有村博紀・宇野毅明 著 A5 ●内容 データから有用な知識を発見するデータマイニングは，近年特に注目されている分野である．本書は，データベース中に頻出するパターンを発見する問題を中心にして，巨大データに対しても効率良く動くアルゴリズムを構築するための最新技術を，理論と実践の両面から解説する． ●目次
|
|
| ページトップへ |
|
15．量子計算 松本啓史 著 A5 ●目次
|
|
| ページトップへ |
| 16．化学系・生物系の計算モデル （ISBN978-4-320-12182-1） 萩谷昌己・山本光晴 著 A5，208頁，3000円 ●内容 本書は，ペトリネットを含む状態遷移系の基礎を一通り説明した後，特に化学系・生物系をモデル化するための計算モデルとして，通常の微分方程式やマルチセット書き換え系に加えて，膜構造を持つ状態遷移系，様々な位相構造の入った状態遷移系，離散量と連続量を併せ持つ状態遷移系について解説する。 まえがき （PDFファイル） ●目次 （詳細目次 PDFファイル）
|
 |
| ページトップへ |
| Copyright (C) 2006 KYORITSU SHUPPAN CO.,LTD. |