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

コンピュータサイエンス教科書シリーズ 2

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

通常の教科書では取り上げられなかったアルゴリズムについて,初心者にもわかるように解説した,最新の内容のアルゴリズム教科書。

ジャンル
発行年月日
2017/09/28
判型
A5
ページ数
228ページ
ISBN
978-4-339-02702-0
  • 内容紹介
  • まえがき
  • 目次
  • 著者紹介

カッコウハッシュ,タンゴ木,定数時間アルゴリズムなど,非常に重要であるが内容が先進的であるために通常の教科書では取り上げられなかったアルゴリズムについて,初心者にでもわかるように解説したこれまでにない教科書。

本書はデータ構造とアルゴリズムの重要部分について基礎から最新までを記した本である。対象は主に大学の学部2~3年の講義を想定しているが,大学院でも使用できる進んだ内容も含んでいる。「データ構造とアルゴリズム」と題した書籍は数多く出版されており,それらの中には良書,好著が数多く含まれる。それらがあるにもかかわらず私が本書を記したのにはもちろん意味がある。「データ構造とアルゴリズム」の世界は日進月歩であり,つぎからつぎへと新しく重要な技術が生まれてくる。そしてそのうちのいくつかは基礎的な必須のアルゴリズムとして残っていく。そういったアルゴリズムの中で非常に重要であるにもかかわらず,なまじ先進的であるために基礎的記述が中心となる教科書にまったく出現しないものが少なからず存在する。それらを知るためには現状では原著論文か,せいぜい英語の専門書に当たるしかない。しかしわれわれ専門家は別として,学生や一般企業のエンジニアにとって,そういった文献に当たれといわれても難があるだろう。

本書はそれらを解決することを主眼として書かれている。したがって,類書にはない,最先端のアルゴリズムを解説することに多くのページを割いている。最先端のアルゴリズムはもちろん比較的難解である。しかし前述のように本書の主対象者である学部生でも理解できるよう,極力平易な解説を試みた。それらを完全に理解するには相当な努力が必要とされるかもしれないが,主たる考え方を理解することはさほど難しくないと考えている。

そして本書の最も重要な特長は,定数時間アルゴリズムの紹介に多くのページを割いていることである。定数時間アルゴリズムとは,入力のうちのほんの一部,定数個のデータだけを見て判定,計算するアルゴリズムの枠組みである。20年ほど前に現れ,今世紀になって急激に発展した。当初はほぼ理論的興味だけで研究が行われてきたが,最近ビッグデータとの絡みで実用面での研究も行われている。いまや国際会議のメイントピックの一つとなっているが,それを解説する専門書は非常に少ない。まして日本語で解説したものはほとんどなく,あるのは筆者やその共同研究者の書いた短めの解説47), 48), 65) ぐらいで,これだけきちんと解説した日本語の教科書は初めてといってよかろう。定数時間アルゴリズムは21世紀のアルゴリズムの標準技術となることは間違いなく,これからアルゴリズムを学ぶ者はこの機会に是非とも学んでおいてほしい。

本書で使用する変数や関数などの表記法(notation)について,その主なものを“記号表” という形で目次の後にまとめた。また,本書で使用する数学に関する基本的な用語および基本公式については,8章に簡単にまとめたので,適宜必要に応じて参照してほしい。さらに,各章末に演習問題を,また必要に応じてプログラム演習を掲載したので,本書の理解の助けになるだろう。

本書の使い方についての一例を記しておく。学部の基礎講義として用いる際には,前半で1章から3章「整列」までをまずしっかりと教え,その後理解度に応じて4章「集合に関する操作」と5章「平衡二分探索木」に進む。そして余裕があれば6章「古典的アルゴリズム」のうちの可能な項目を教えればよい。その際には,付録に回した部分はやるとしても紹介程度で,解説している時間はないであろう。もし通年で教える場合には,演習問題などをじっくりとやらせ,付録の部分も解説することができると思う。その上で6章のすべてを教えられると思うが,さらに7章「定数時間アルゴリズム」もざっと教えられれば理想である。ただし,正則性補題はそれを理解するだけでも(一部の優秀な学生を除き)学部生には難しいので,証明は省いてアルゴリズムのみ説明することで十分である。

大学院の講義に用いる場合には,前半で1章~6章のトピックから選んで講義し,後半は7章を中心とするのがよい。付録に回した正則性補題の証明まできちんと理解させようとすると,実は7章全部で半期の講義にできるぐらいの内容はある。
本書を執筆するにあたって多くの方に助けていただいた。電気通信大学名誉教授で先進アルゴリズム研究ステーション教授でもある富田悦次先生には,本書の執筆へお誘いいただいたのをはじめとして,さまざまな機会にご助言をいただき,大いに助けていただいた。ここに深く感謝したい。また,他の方々にもたいへんご多忙であるにもかかわらず拙著の原稿に目を通していただき,間違いのご指摘や改善案の提示などいろいろご教授いただいた。たいへんありがたく思い,深謝している。それは大阪府立大学の宇野裕之准教授,京都大学学術メディアセンターの宮崎修一准教授,国立情報学研究所の𠮷田悠一准教授,京都大学大学院情報学研究科の玉置卓助教である。それにもかかわらずまだ不完全な部分やもしかしたらまだ間違いも残っているかもしれない。しかしそれらの責任はすべて筆者である私にある。また,コロナ社には私の遅筆でたいへんご迷惑をおかけした。ここにお詫びを申し上げる。最後になったが,分野は違えどわが尊敬する学者であり,最愛の妻である,愛知県立大学日本文化学部国語国文学科教授の伸江に心から感謝の気持ちを表したい。ありがとう。本書が一人でも多くの方の助けとなることを祈りつつ筆を置くことにする。

2017年8月 伊藤 大雄

1. はじめに
1.1 アルゴリズムとデータ構造の重要性
1.2 計算モデルと計算量
 1.2.1 問題と問題例
 1.2.2 計算機モデル
 1.2.3 アルゴリズムのオーダー表記
 1.2.4 指数関数と多項式関数の比較
 1.2.5 計算量とアルゴリズムの種類
1.3 NP完全性
 1.3.1 PとNP
 1.3.2 NPの定義
 1.3.3 多項式時間帰着とNP完全
演習問題

2. 基本的データ構造
2.1 配列
2.2 線形データ構造
 2.2.1 配列を使う方法
 2.2.2 リスト
 2.2.3 スタック
 2.2.4 キュー(待ち行列)
2.3 木
 2.3.1 一般的木構造
 2.3.2 完全二分木
2.4 グラフ
 2.4.1 グラフの基本
 2.4.2 次数とカット
 2.4.3 部分グラフと路と連結性
 2.4.4 木と森とDAGと二部グラフと完全グラフ
 2.4.5 グラフのデータ構造
 2.4.6 グラフの探索-幅優先探索と深さ優先探索
演習問題
プログラム演習

3. 整列
3.1 整列とはなにか
3.2 バブルソート
 3.2.1 バブルソートのアルゴリズム
 3.2.2 バブルソートの計算時間
3.3 マージソート
 3.3.1 マージソートのアルゴリズム
 3.3.2 マージソートの計算時間
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.7 ヒープソート
 3.7.1 ヒープとはなにか
 3.7.2 ヒープの構造
 3.7.3 Insertの方法
 3.7.4 DeleteMinの方法
 3.7.5 Deleteの方法
 3.7.6 ヒープソートのアルゴリズム
 3.7.7 ヒープの線形時間作成法
3.8 整列計算時間の下界値
演習問題
プログラム演習

4. 集合に関する操作
4.1 主な操作とデータ構造
4.2 辞書
 4.2.1 ハッシュ表
 4.2.2 外部ハッシュ法
 4.2.3 内部ハッシュ法
4.3 カッコウハッシュ
 4.3.1 カッコウハッシュとはなにか
 4.3.2 カッコウハッシュの詳細
 4.3.3 格納列の閉路と単純格納列
 4.3.4 カッコウハッシュの解析*
4.4 ユニオン・ファインド
 4.4.1 問題設定
 4.4.2 配列による実現
 4.4.3 ポインタでの実現
 4.4.4 木による実現-ほぼ線形時間のユニオン・ファインド
 4.4.5 木構造上に限定された場合の線形時間ユニオン・ファインド
演習問題
プログラム演習

5. 平衡二分探索木
5.1 平衡二分探索木の基本
 5.1.1 二分探索
 5.1.2 二分探索木の構造とMember
 5.1.3 最大値・最小値の発見と整列
 5.1.4 データの挿入と削除
 5.1.5 回転操作
5.2 二色木
 5.2.1 二色木の基本
 5.2.2 二色木における挿入
 5.2.3 二色木における削除
 5.2.4 二色木の合併と分割
 5.2.5 別のデータの管理
5.3 スプレー木
 5.3.1 オンラインアルゴリズムと動的最適性予想
 5.3.2 スプレー木のアルゴリズム
 5.3.3 スプレー木のO(logn)競合化*
5.4 タンゴ木
 5.4.1 タンゴ木の基本思想とインターリーブ限界
 5.4.2 タンゴ木の構造
 5.4.3 補助木のつくり替え
 5.4.4 タンゴ木の計算時間の解析*
演習問題
プログラム演習

6. 古典的アルゴリズム
6.1 最小木問題
 6.1.1 問題の定義
 6.1.2 貪欲算法とクラスカルのアルゴリズム
 6.1.3 クラスカルのアルゴリズムの正当性
6.2 最短路問題
 6.2.1 最短路問題とはなにか
 6.2.2 最短路の存在条件
 6.2.3 最短路木
 6.2.4 ダイクストラ法
 6.2.5 フロイド・ワーシャル法
6.3 彩色問題
 6.3.1 平面グラフとその性質
 6.3.2 グラフ彩色問題
 6.3.3 1,2彩色問題
 6.3.4 染色数とその上限
 6.3.5 四色定理*
演習問題

7. 定数時間アルゴリズム
7.1 定数時間アルゴリズムとはなにか
 7.1.1 定数時間アルゴリズムの一般的枠組み
 7.1.2 性質検査
 7.1.3 グラフの「性質」
 7.1.4 グラフGと性質Pの距離
 7.1.5 インスタンスの表現法
 7.1.6 検査アルゴリズムと検査可能性
7.2 隣接行列モデル
 7.2.1 無三角性検査
 7.2.2 手続きTriangleFreeの正当性の証明
 7.2.3 一般化-無H性とモノトーン性
7.3 次数制限モデル
 7.3.1 次数制限モデルの基本
 7.3.2 無三角性検査と無H性検査
 7.3.3 無閉路性検査
 7.3.4 マイナー閉鎖な性質と超有限性と分割定理
 7.3.5 分割神託
 7.3.6 無Hマイナーなグラフの検査アルゴリズム
演習問題
プログラム演習

8. 数学用語の解説
8.1 基本用語
8.2 対応・関係・関数・順序
8.3 基本公式
8.4 グラフマイナー
 8.4.1 クラトウスキーの定理
 8.4.2 グラフマイナー定理
8.5 正則性補題
 8.5.1 正則性補題とはなにか
 8.5.2 正則性補題の証明*
演習問題

引用・参考文献
索引

伊藤 大雄(イトウ ヒロオ)