データ構造と基本アルゴリズム

本書は情報科学関係の大学や専門学校などの学生を対象にアルゴリズム設計の基礎と応用と題して企画した。通年の教科書として 30 週で一通り終了することを念頭におき, データ構造とアルゴリズムを柱に, プログラミング言語, 計算複雑度などにまたがる内容を天下り的になることなく,”読めば理解できる形の説明をできるだけ用意しておく”という試みをし, 解説をできるだけ詳しく, 例題・演習問題を多く取り上げてできるだけ理解しやすいようにまとめた。
●1 章では, 実例に基づいてプログラムとは何かを分かりやすく説明することにより, アルゴリズム設計, プログラミングなど不案内な学生への導入とした。
●基礎的事項は例題を用いて平易な説明による導入を試み, そのため図を多く用い懇切丁寧に解説した。
●具体例からの一般化や理論的に厳密な証明などもできるだけ記述した。
●ワークステーションなどのコンピュータ上の C 言語によるプログラム作成を前提にし, これに必要な最小限の解説を本文や付録に組み込むと共に実行例もできるだけ記述した。
●必要な数学的基礎事項は付録にまとめた。
第 1 章 アルゴリズム設計の概要
1.1 プログラミングとアルゴリズム
1.2 実際のプログラミング
1.3 アルゴリズムとデータ構造
1.4 解き難い問題
1.5 アルゴリズムの設計と解析
1.6 アルゴリズムの評価基準と計算複雑度

第 2 章 コンピュータとプログラム
2.1 コンピュータ内部での文字や数値の扱い
2.2 メモリと CPU
2.3 命令コードとインストラクションポインタ
2.4 プログラムの実行
2.5 スタック領域, フレームポインタ, スタックポインタ
2.6 引数の値と戻り値の受け渡し, 変数とスコープ

第 3 章 基本データ構造
3.1 配列
3.2 リスト
3.3 スタックとキュウー
3.4 グラフ
3.5 グラフの実現度

第 4 章 ヒープ
4.1 完全 2 分木
4.2 ヒープとその基本操作
4.3 ヒープの構成法

第 5 章 整列
5.1 バケットソートと基数ソーティング
5.2 選択法
5.3 挿入法
5.4 ヒープソート
5.5 マージソート
5.6 クイックソート

第 6 章 探索
6.1 2 分探索木と対称順
6.2 2 分探索木における基本操作: 探索, 挿入, 削除
6.3 回転
6.4 赤黒木
6.5 赤黒木を実現するプログラム
6.6 ハッシュ法

第 7 章 グラフの基本アルゴリズム
7.1 概要
7.2 無向グラフに対する幅優先探索
7.3 無向グラフに対する深さ優先探索

配列で済ませるかリストにするか、整列にどの方法を選ぶかで、同じ問題でも処理時間が桁で変わります。その判断の根拠を計算複雑度の言葉で身につけさせるのが、『データ構造と基本アルゴリズム』 (渡邉敏正 著、共立出版、2000 年 1 月刊) です。版元の紹介文によれば、情報科学関係の大学や専門学校などの学生を対象に、通年の教科書として 30 週で一通り終了することを念頭に置いて企画され、データ構造とアルゴリズムを柱に、プログラミング言語や計算複雑度にまたがる内容を天下り的にならないよう、例題と演習問題を多く取り上げて解説する方針で書かれています。プログラム作成は、ワークステーションなどのコンピュータ上の C 言語 を前提にしており、必要な数学的基礎事項は付録にまとめられています。

全 7 章の構成、プログラムの実行原理からヒープ / 整列 / 探索 / グラフへ

構成は全 7 章です。第 1 章「アルゴリズム設計の概要」はプログラミングとアルゴリズム、実際のプログラミング、解き難い問題、アルゴリズムの設計と解析、アルゴリズムの評価基準と計算複雑度と進み、版元の紹介文にあるとおり、実例に基づいてプログラムとは何かを説明することで、アルゴリズム設計やプログラミングに不案内な学生の導入部を担います。第 2 章「コンピュータとプログラム」はアルゴリズムの教科書としては珍しい章で、コンピュータ内部での文字や数値の扱い、メモリと CPU、命令コードとインストラクションポインタ、スタック領域とフレームポインタとスタックポインタ、引数の値と戻り値の受け渡し、変数とスコープを扱います。第 3 章「基本データ構造」で配列、リスト、スタックとキュー、グラフとその実現を押さえ、第 4 章「ヒープ」は完全 2 分木からヒープの基本操作と構成法へ進みます。第 5 章「整列」はバケットソートと基数ソーティング、選択法、挿入法、ヒープソート、マージソート、クイックソートを並べ、第 6 章「探索」は 2 分探索木と対称順、探索 / 挿入 / 削除の基本操作、回転、赤黒木、赤黒木を実現するプログラム、ハッシュ法を扱います。終章の第 7 章「グラフの基本アルゴリズム」は概要と、無向グラフに対する幅優先探索と深さ優先探索です。

C 言語で動かしながら学ぶ、データ構造と計算複雑度の技術背景

アルゴリズムの教科書には、言語を特定せず擬似コードで手順だけを示す流儀と、特定の言語で実際に動くプログラムを載せる流儀があります。本書は後者で、しかも第 2 章でメモリと CPU、スタック領域とフレームポインタまで説明したうえでデータ構造に入るため、リストのポインタ操作や再帰呼び出しのコストが、機械の上で何をしているかと結び付いて理解できる構成です。入力サイズ n に対して処理時間がどう増えるかを表す 計算複雑度 の考え方は、ヒープが優先度付きの取り出しを対数時間で行える理由、赤黒木が回転によって木の高さを抑えて探索 / 挿入 / 削除の最悪時間を保証する仕組み、ハッシュ法が平均的に定数時間で探索できる代わりに衝突の扱いを要する事情を、同じ尺度で比べさせてくれます。整列の章で単純な選択法や挿入法から、ヒープソート、マージソート、クイックソートへ進む順序も、同じ問題に対する複数の解法を計算複雑度で比較するという本書の軸に沿ったものです。第 7 章の幅優先探索と深さ優先探索は、最短経路や連結性の判定など多くの グラフアルゴリズム の土台になる 2 つの走査で、ここまでを一通り実装しておくと、後で応用アルゴリズムを学ぶときの足場になります。

情報系学部の通年講義を想定した前提知識と、2000 年刊という時点の読み方

前提知識は、C 言語の基本文法に触れたことがあるか、これから並行して学ぶ意思があることです。版元の紹介文のとおり第 1 章がプログラミングに不案内な学生への導入として書かれ、C 言語に必要な最小限の解説が本文や付録に組み込まれているので、言語の入門書を 1 冊終えた程度の段階から読み始められます。数学は具体例からの一般化や理論的に厳密な証明もできるだけ記述するとされており、証明を追う体力は求められますが、必要な数学的基礎事項が付録にまとめられている点は独習者にとって助けになります。注意したいのは刊行が 2000 年 1 月であることで、ワークステーションを想定した実行環境の記述は当時のものです。ただし配列やリスト、ヒープ、2 分探索木、赤黒木、ハッシュ法、幅優先探索と深さ優先探索といった本書の中身は、その後の言語や環境の変化に左右されない基礎に絞られており、C コンパイラさえあれば手元で試せる内容です。

Python や Java など C 以外の言語で手を動かしたい人、競技プログラミングで使う実装テクニックを短期間で集めたい人、最短経路や動的計画法のような発展的な題材まで 1 冊で進みたい人には、本書は遠回りに感じられるはずで、その目的なら アルゴリズム本の選び方 で紹介している本のほうが合います。逆に、情報系の学部で講義の教科書として指定された学生はもちろん、C 言語を学んだ直後にメモリの動きとアルゴリズムの効率を切り離さずに理解したい人、あるいは業務で使っているデータ構造の選択がなぜ速いのかを一度根元から確かめたいエンジニアにとって、例題と演習問題を通年分そろえた本書は、時間をかけた分だけ確実に基礎が残る教科書です。