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

電子情報通信レクチャーシリーズ B-8

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

機械学習的,ビッグデータ的,疑似コードとC++実コードによるオブジェクト指向的考え方に配慮した学部用教科書。

ジャンル
発行年月日
2018/02/23
判型
B5
ページ数
208ページ
ISBN
978-4-339-01823-3
データ構造とアルゴリズム
在庫あり

定価

3,630(本体3,300円+税)

カートに入れる

電子版を購入

購入案内

  • 内容紹介
  • まえがき
  • 目次
  • 著者紹介
  • 書籍紹介・書評掲載情報

本書は,最近の動向に合わせて,機械学習的考え方,ビッグデータ的考え方,さらには擬似コードとC++実コードによるオブジェクト指向的考え方にも配慮しつつ,通常の学部用教科書としての側面もしっかりと押さえた教科書である。

本書で取り扱うデータ構造とアルゴリズムに関する研究は,コンピュータ科学の挑戦の歴史の中で,常に中心の位置を占めてきた.そこで開発された技法なくしては,現在の高度情報化社会の実現はあり得なかったことに疑問をはさむ余地はない.そのため専門教育における初学者用の教科書はとても大事であり,既に多くの成書が出版されている.本書を執筆するにあたって,類書の中でどのような特徴を出すかは大きく悩むところであった.本書の執筆者4人は地方国立大学において実際に関連の専門教育に長年携わってきた人間である.いろいろと議論を行った結果,以下のような執筆方針が徐々に固まっていった.

• 初学者用であるので,取り上げるトピックは奇をてらわずに,正攻法で選択する.
• 本シリーズ全体の要請にもなっているが,説明は図を多用して平易に行う.数式の使用はなるべく控えて,使用する場合でも2 行以上は連続させないことを原則とした.また解説するトピックは天下りの説明は避け,取り上げる理由や,結果を支えるアイデアから説明する.初学者には不要なレベルの厳密な説明や証明は行わない.
• 説明を平易に行うからといって,表面的なものだけに流れずに本質はきちんと説明する.また学習者が自ら興味をもってより進んだ勉学に取り組むように,裏に隠れた深い性質などについても一部,光を当てるように工夫する.
以上は初学者用教科書での一般的な方針であるが,“データ構造とアルゴリズム”の分野固有の観点からは以下の方針を考えた.
• 昨今のメモリの大容量化に代表されるハードウェアの高性能化と,高速ネットワークの普及と機械学習技術の発展に伴うデータの巨大化などの動向に留意し,その解決につながる技術を積極的に取り上げ,解説を行う.例えば,メモリ(領域)消費型のデータ構造とその上のアルゴリズム技法を,類似の成書より積極的に取り上げる.
• 昨今のシステムの大規模化と高信頼化に対応できる人材を育成するためには,ソフトウェアのカプセル化や抽象化,一般化,検証などの技術を初学者のレベルから教えることが重要である.ソフトウェア工学とは別の次元で,プログラミングレベルでの知識とスキルを身に付けさせるために,オブジェクト指向型言語であるC++による実装コードの教示を行う.
• 本書の前半ではC++言語での実装コードを示すが,これは初学者によいコードを読ませることが目的であり,Art of Programming につながるような解説を付記するように努力する.後半では疑似コードでアルゴリズムを示し,論理的かつ抽象的な思考能力の育成を図る.

オブジェクト指向型のC++言語は,初学者教育での利用には種々の議論もあるが,早いうちから,カプセル化や継承,多態性(polymorphism)などの概念に親しませることは,やはり高度な専門性の修得を目指す読者には有用であると考える.またSTL などの汎用の高性能ライブラリが利用できることも利点である.1 . 2節には,C言語などは知っているが,C++言語はよく知らない読者のための導入解説を行って,敷居を下げる工夫を行っている.

疑似コードレベルのアルゴリズム記述や問題の特性把握は,抽象的かつ論理的な思考,あるいは一般化した思考の訓練になり,とても有用である.昨今ではネット上には著名なアルゴリズムの実装コードが多数公開されている.ややもすると,それらを表面的にだけ参考にし,本質的な洞察を行わずに済ませてしまう例が数多く見受けられる.そのためか,アルゴリズムの最適化や改良のために疑似コードでの記述と整理を行わせると,ほとんどできない人が思いのほか多いことに驚かされる.そもそも疑似コードはプログラムの設計図となるものであり,上級仕様の作成などを行うためにも必要なスキルであるので,是非,多くの読者に習熟してほしいと考えている.
本書は1年間もしくは1年半程度の勉学期間を想定して編纂されている.執筆陣は本書の前半を,専門技術者教育におけるプログラミング言語教育の後半(1年後期)の教材として利用することを想定している.本書の後半は,学部2年から開始されるデータ構造とアルゴリズムの講義演習に使用することを想定している.
昨今では,ハードウェアの高性能化と高機能なソフトウェア統合開発環境の普及に伴い,アルゴリズムとデータ構造に関する専門的な勉強をしなくとも,基本的で小規模なソフトウェアならば容易に開発できる時代になっている.これは「誰でもプログラマになれる」という意味では望ましいことであるが,情報処理技術の本質に関して誤解が生じやすいという意味では望ましくないと考えられる.より先進的で高度なシステムを設計し開発するためにも,あるいは大規模かつ高信頼性を必要とするシステムを選定し運用するためにも,アルゴリズムとデータ構造に関する専門的な知識とスキルは必要不可欠なものである.より多くの読者に本分野を学んでいただき,現在および将来の高度情報化社会を支えていただければ,幸いと考える.本書がその一助になれば,執筆者らの望外の喜びである.

最後に,遅々として進まぬ執筆作業を忍耐強く待ち,励ましをいただいたコロナ社の皆様に感謝を申し上げる次第です.

2017年12月 岩沼宏治(著者代表)

1. はじめに
1.1 天文学的数字とコンピュータ科学的数字はどちらが大きいか?
1.2 データ構造のプログラム表現:オブジェクトとクラス
 1.2.1 クラスとオブジェクト
 1.2.2 値渡しと参照渡し
本章のまとめ
理解度の確認

2. データ構造の基礎
2.1 計算とメモリ
2.2 配列
 2.2.1 固定長配列
 2.2.2 可変長配列
 談話室 C++標準テンプレートライブラリのvectorクラス
2.3 連結リスト
 談話室 C++標準テンプレートライブラリのlistクラス
2.4 スタックとキュー
2.5 木構造
本章のまとめ
理解度の確認

3. 基本的な探索整列の手法
3.1 アルゴリズムと計算量
3.2 素朴な探索
 談話室 任意のキーによる探索
3.3 再帰的探索
3.4 素朴な整列
 3.4.1 選択ソート
 3.4.2 挿入ソート
3.5 再帰的整列
 3.5.1 マージソート
 3.5.2 クイックソート
3.6 空間を利用する整列
 3.6.1 バケットソート
 3.6.2 計数ソート
 3.6.3 基数ソート
本章のまとめ
理解度の確認

4. 二分木とその応用
4.1 二分探索木
 4.1.1 素朴な二分探索木
 談話室 多態性
 4.1.2 平衡二分探索木
 談話室 さまざまな平衡木
4.2 優先度付きキューとヒープソート
 4.2.1 優先度付きキュー
 4.2.2 ヒープによる高速な優先度付きキュー
 4.2.3 ヒープソート
4.3 最近傍探索とkd-木
 4.3.1 最近傍探索
 4.3.2 kd-木の構築
本章のまとめ
理解度の確認

5. ハッシュ表
5.1 ハッシュ表の原理
 5.1.1 分離チェイン法
 5.1.2 ハッシュ関数の設計
 5.1.3 文字列キーに対するハッシュ関数
5.2 開番地法
 5.2.1 開番地法の原理
 5.2.2 開番地法における削除
 5.2.3 代替アドレス
 5.2.4 ハッシュ表の拡大
 談話室 ハッシュ関数と認証
本章のまとめ
理解度の確認

6. グラフ
6.1 グラフの表現と探索
6.2 最小全域木問題
6.3 最短経路問題
 6.3.1 単一始点問題:ダイクストラ法とベルマン・フォード法
 6.3.2 単一点対問題:A*アルゴリズム
6.4 最長経路問題:トポロジカルソート
本章のまとめ
理解度の確認

7. 文字列照合
7.1 文字列照合問題と素朴な解法
 7.1.1 力まかせ法
7.2 高速な文字列照合法
 7.2.1 力まかせ法の欠点とBM法の原理
 7.2.2 BM法の実際
 談話室 BM法の補足
7.3 ハッシュ法を用いた文字列検索
7.4 索引に基づく高速文字列照合
 7.4.1 トライに基づく文字列照合
 7.4.2 パトリシアトライによる文字列照合
 7.4.3 サフィックス木に基づく文字列照合
本章のまとめ
理解度の確認

8. アルゴリズム技法
8.1 分割統治法
 8.1.1 分割統治法の適用例
 8.1.2 分割統治法の性質
 談話室 シュトラッセン(Strassen)のアルゴリズム
8.2 動的計画法
 8.2.1 0-1ナップサック問題と動的計画法
8.3 分枝限定法
 8.3.1 緩和法と上界見積り
8.4 オンライン近似計算:ストリームマイニング
 8.4.1 ストリームマイニング
 8.4.2 オンライン近似計算とSpace Saving法
 談話室 オンライン計算と近似計算の枠組みについて
本章のまとめ
理解度の確認

引用・参考文献
索引

岩沼 宏治(イワヌマ コウジ)

美濃 英俊(ミノ ヒデトシ)

鍋島 英知(ナベシマ ヒデトモ)

山本 泰生(ヤマモト ヨシタカ)

「電子情報通信学会誌」平成30年9月1日発行 掲載日:2018/09/10