科学技術出版　Cによるアルゴリズムとデータ構造

｜お問い合わせ｜会社概要｜サイトマップ｜

Home ＜書籍情報＜コンピュータサイエンス・シリーズ＜ Cによるアルゴリズムとデータ構造

←一覧に戻る

Cによるアルゴリズムとデータ構造

平田　富夫著

2,800円

A4 224頁

4-87653-333-4 C3055

本書は情報工学・情報科学の初学者がアルゴリズムとデータ構造について学ぶための教科書である。コンピュータの基本構成と動作についてひととおり理解していて、しかもＣ言語でのプログラミング経験がある者を対象としている。これらの予備知識と離散数学の初歩的な知識があれば本書を通読するのは容易で、アルゴリズムとデータ構造に関する基本的な概念を習得することができる。さらに、コンパイラやオートマトン・形式言語についての若干の知識があれば、本書の発展的な話題（基礎的な学習のみを目指す場合には飛ばしてもかまわない）を理解するのに困ることはない。

プログラミング経験としてはC言語の入門コースを済ませていることを仮定している。これまで、アルゴリズムの教科書は Pascal風のプログラミング言語を用いてアルゴリズムを記述することが多かった。これは、構造的プログラミングやデータ型、それに関数引数の渡し方などのプログラミングの基本概念を初めて学ぶのにはＰａｓｃａｌが適切であるという考えがあり、プログラミング入門のための言語として選ばれることが多かったためである。一方、Unix の普及とともにソフトウェア開発の現場ではＣが使われるようになり、実践的な観点からCによるプログラミング教育が要請されるようになった。理想的には、プログラミング入門はPascal で行い、その後でCのような実践的なプログラミング言語を学ぶというのが望ましい。しかし、教育現場ではそのような重複したプログラミング教育を実施できる余裕をもつことは少なく、入門からＣで始めることが多くなった。アルゴリズムの記述にC とPacal のどちらを使っても大きな差はない。一方の言語に習熟している読者ならば他方の言語で書いてあるアルゴリズムを読み解くのに困難は感じないはずである。しかし、プログラミング入門を終えたばかりの学生にとっては、なじみのある言語で記述しあるほうがずっと理解しやすいのは確かである。そのような理由で、本書ではアルゴリズムの記述にCを用いている。

アルゴリズムの深い理解のためには実際にプログラムとして実現し動かしてみることが近道である。理解したつもりでいて実は誤解しているときや、あやふやな理解で済ましてしまったときなど、プログラムとして実現してみればすぐに分かる。アルゴリズムの計算量をオーダー評価することの妥当性と重要性は、頭で理解するだけでなく、実際にプログラムとして実現し計算機上で走らせてみるとよく分かる。また、基本アイデアは比較的容易に理解できるのに、実際にプログラムを作ろうとするとどのように実現すればよいか分からず困惑するようなアルゴリズムがある。一方で、複雑そうにみえるアルゴリズムが簡潔なプログラムとして実現できることが分かったときはそのアルゴリズムに感動さえ覚えることがある。そのような意味で、計算量だけでアルゴリズムを評価するのでなく、美的感覚で眺めてみるのも楽しい。本書のアルゴリズムはCまたはC 風の言語で書かれているので、実際のプログラムに実現するのは容易である。ぜひ、計算機の上で走らせて、アルゴリズムの動きと速さとを実感してほしい。なお、プログラムを読み解く作業をしなくてもアルゴリズムの背景にあるアイデアを理解できるように明快な解説を心がけたので、プログラムに興味がない読者はプログラム部分を読み飛ばすことも可能である。

本書で学ぶアルゴリズムは実際の情報処理で現れるものを優先して選んである。しかし、単なるアルゴリズム集とは異なる。有用なアルゴリズムを集成したアルゴリズム集は、その中に使いたいアルゴリズムが見つかるときには役に立つが、少しでも違った形の問題になると対応できない。また、アルゴリズムの正当性の証明や計算量を解析する力を養うことには役立たない。応用上の問題がますます複雑化することを考えると、問題解決のために重要なことは、アルゴリズム設計の基礎を身に付け、新たに出会う問題を自力で解決する応用力を養うことである。情報処理の現場で遭遇する各種問題に対し最善の（または、要求される性能を満たす）プログラムを作るには、問題の抽象化・定式化とアルゴリズムの発見といった一連の作業に習熟することが必要であり、それが本書を通してアルゴリズム設計を学ぶ目的である。本書の内容を理解し演習問題を十分に活用することにより、そのようなモデリングのセンスと良いアルゴリズムを見つけ出す力を涵養することができると信じている。

欧米のアルゴリズムの教科書には大部なものが多く、千ページ以上というのも珍しくない。このような大部な教科書でも半年ないし通年で内容を終えることができるののは次のような理由が考えられる。学生がとる週あたりの授業科目数が３科目程度と少なく、ひとつの科目が週に数回の授業時間枠を持つため、演習の時間を含め授業時間数が多くとれる。さらに、学生は少ない科目に集中して勉強するため、かなりの分量の宿題にも対応でき、一回の授業で相当量の内容をこなすことができる。なお、このような教科書には多くのトピックが含まれているので、その中から教師が取捨選択し学生に提示することができ、教師にとってはある程度テイラーメードの授業内容を構成することも可能である。

一方、我が国の大学学部の場合、極端に密な時間割の下でひとつの科目は週にひとつの時間しかもたないのが普通である。演習の時間も短く、指導するスタッフも少ない。そのような環境下で効果的な授業を行うためには，トピックを精選し、少ない演習問題で理解を深めるような工夫が必要である。本書は海外の教科書に比してきわめてコンパクトであるが、これは取り扱うトピックを精選し、２単位（３０時間）の授業ですべてを終えることができるように配慮したためである。

そのため、独学であっても全体を通読してアルゴリズムの基礎概念を学ぶことができ、アルゴリズム設計の思考方法を身に付けることができる。大学学部または高専などの情報系の学科で教科書として使用する場合には、本書の題材すべてを半期（２単位）の授業で終了することができる。情報を専門としない学科であれば発展的な話題をいくつか省略して半期で終えることができる。

本書は、著者の前著「アルゴリズムとデータ構造」の C言語版でもある。前著は約10年前に書かれたもので、アルゴリズムはPascal 風の言語で記述されている。当時からみればパソコンやワークステーションやパソコンの性能は格段に向上しているが、アルゴリズムや計算量の基礎は普遍的なもので変わらず、本書も同じである。ただし、近似アルゴリズムや確率アルゴリズムなど、この間に実用的な意味で進展のあった事項については説明を加えた。並列アルゴリズムについては実用の観点からはまだ紹介する段階にはないと考え本書では割愛した。さらに、本書で学ぶアルゴリズムとは趣が異なるが、実用的には広く使われるようになった遺伝的アルゴリズムやシミュレーテッドアニーリングについても、ヒューリスティックアルゴリズムとしてまとめ簡単な解説を加えてある。本書で扱うアルゴリズムは正当性の証明と効率性の理論的な保証を伴うが、遺伝的アルゴリズムやシミュレーテッドアニーリングはそのような考察が非常に難しく、実験的にその正当性と性能を検証するのが普通である。そのためヒューリスティック（発見的）アルゴリズムと呼び区別している。

本書の内容

1章はア「ルゴリズムの基礎概念」を説明しており、本書全体を通して必要となる基礎知識である。まず、計算のモデルと計算量の定義を与える。オーダー評価のもとで効率の良いアルゴリズムを設計することの重要性を理解する。また、計算容易な問題と計算困難な問題があることを例を通してみることにより、問題固有の複雑さがあることを理解する。さらに、グラフと木の用語を解説している。

２章では「各種ソーティングアルゴリズム」を題材として種々のアルゴリズム概念（計算量の解析、分割統治法、再帰式の解法、計算量の下界など）を説明する。まず、素朴なアルゴリズムとしての選択法、挿入法、バブルソートを紹介する。次ぎに、工夫されたアルゴリズムとして、マージソート、クイックソート、ヒープソート、シェルソートを紹介し、それらの計算量解析を行う。クイックソートとシェルソートについては平均解析も行う。最後にバケットソートの安定性を生かした辞書式順序によるソーティングを紹介する。

３章と４章は「データ構造」の紹介である。３章は基本データ構造についての説明であり、リスト、スタック、キュー、ヒープについてその応用例を交えて解説する。４章ではデータ探索のためのデータ構造を紹介する。まず、あらゆる探索アルゴリズムの基本となる２分探索法を説明する。次に、２分探索法を基礎として、データの挿入と削除を実行できるデータ構造として２分探索木を紹介する。

さらに、それを平衡化させたデータ構造として２色木を紹介する。２色木のようなデータ構造に対しデータの更新（データの挿入または削除）を実行すると、そのたびに２色木はその構造を変化させる。一般のデータ構造では現在のデータ構造に対してのみデータ探索とデータの更新が実行できるが、データの探索に関しては過去のデータ構造に対しても実行できるようにしたものをパシステント構造という。データ更新を行う毎にそのときのデータ構造のコピーを残しておくことも可能であるが、それでは記憶容量が増えてしまう。ここでは、２色木の持つうまい性質を利用して、記憶領域を増やさずにパシステント構造を構成する。また、その記憶容量の解析では「ならし計算量解析」という解析法を用いる。ならし計算量というのは、更新操作の時間を、一回の操作に要する時間で評価するのではなく、多数回をまとめて評価し一回あたりにならしてみるという解析法である。最後に、データ探索のための実用的なデータ構造としてハッシュ法を紹介する。

５章～７章は対象とする問題別にそれらのアルゴリズムを紹介している。

５章は「ストリングマッチングとパターンマッチング」である。

これらのアルゴリズムはヒトゲノムプロジェクトでのＤＮＡ解析のような重要な応用分野をもつ。ストリングマッチングの歴史を概観した後、クヌース・モーリス・プラットのアルゴリズムを紹介する。次に、マッチングオートマトンを使った複数パターンのマッチングアルゴリズムと正規表現のパターンマッチングアルゴリズムを与える。最後に、動的計画法を用いて二つの文字列の最長共通部分列を見つけるアルゴリズムを与える。

６章は「高速フーリエ変換アルゴリズム」である。まず離散フーリエ変換を定義し、たたみ込み演算との関係を述べる。次に、高速フーリエ逆変換（ＦＦＴ）のアルゴリズムを紹介する。高速フーリエ変換は信号処理などでおなじみであるが、アルゴリズム設計の立場から眺めてみると実に簡明なアルゴリズムであることが納得できる。

７章は「グラフとネットワークのアルゴリズム」を集めてある。まず、深さ優先探索と幅優先探索を紹介し、次に、深さ優先探索を応用した２連結成分アルゴリズムについて解説する。最短路アルゴリズムとしてはダイクストラによるものとワーシャル・フロイドによるものを紹介する。最大スパニング木ではunion-find問題を効率良く解くデータ構造が用いられる。最後に、ネットワークフローアルゴリズムについて簡単に紹介する。

８章と９章は「アルゴリズム設計の基本技法」について解説している。これらは設計法というよりむしろ設計パラダイムである。したがって、これによりアルゴリズム設計が自動的に行なえるものではないが、このような眺めかたをすることでアルゴリズム概念が整理され、実際にアルゴリズム設計を行なうときの力強い指導原理となる。

８章では「分割統治法、動的計画法、グリーディ法、分枝限定法」について、それぞれ例を用いて説明している。

９章では代表的な「ヒューリスティックアルゴリズム」を解説してる。局所探索法、タブー探索、シュミレーテッドアニーリング、遺伝的アルゴリズムについてそれぞれ例を用いて解説。

１．アルゴリズムの基礎概念
計算のモデル
計算量
計算困難な問題
グラフと木

２．ソーティング
素朴なアルゴリズム
工夫されたアルゴリズム
再帰式の解法
バケットソートと辞書式順序

３．基本データ構造
リスト
スタック
キュー
ヒープ

４．探索アルゴリズム・データ構造
２分木
２色木
パシステント構造
ハッシュ法

５．ストリングマッチング
KMPアルゴリズム
複数パターンのマッチング、
正規表現によるパターンマッチング
最大共通部分列

６．高速フーリエ変換アルゴリズム
離散フーリエ変換とたたみ込み
フーリエ逆変換

７．グラフとネットワークのアルゴリズム
深さ優先探索と幅優先探索
２連結成分アルゴリズム
最短路アルゴリズム
最大スパニング木
ネットワークフロー

８．アルゴリズム設計の基本技法
分割統治法
動的計画法
グリーディ法
分枝限定法

９．ヒューリスティックアルゴリズム
局所探索法
タブー探索
シュミレーテッドアニーリング
遺伝的アルゴリズム

｜書籍情報｜ご注文方法｜人材募集｜お問い合わせ｜会社概要｜サイトマップ｜