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

[cover photo]
TOPICS
Programming
発行年月日
PRINT LENGTH
554
ISBN
978-4-87311-634-1
原書
Data Structures and Algorithms Made Easy Second Edition
FORMAT
Print PDF
Ebook
4,180円
Ebookを購入する
Print
4,180円

インド工科大学(IIT)と企業の両方で豊富な経験を持つインド人著者による、実例豊富なデータ構造とアルゴリズムの解説書。伝統的なデータ構造とアルゴリズムのトピックで、基本をしっかり押さえるだけでなく、集合のUnion/Find、動的プログラミングや計算量クラスといった話題も盛り込んでいます。圧倒的な情報量でプログラマに必要な知識を網羅。600弱の練習問題とその解を収録しており、理解度を細かく確認し、知識を着実に身に付けることができます。

正誤表

ここで紹介する正誤表には、書籍発行後に気づいた誤植や更新された情報を掲載しています。以下のリストに記載の年月は、正誤表を作成し、増刷書籍を印刷した月です。お手持ちの書籍では、すでに修正が施されている場合がありますので、書籍最終ページの奥付でお手持ちの書籍の刷版、刷り年月日をご確認の上、ご利用ください。

第1刷正誤表

1刷正誤表

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

2013年9月11日更新

位置
p.14
3行目
1. abならば、T (n)=Θ(nlogab) 1. abならばT (n)=Θ(nlogba)
p.14
5行目
a. p>-1ならば、T (n)=Θ(nlogablogp+1n) a. p>-1ならば、T (n)=Θ(nlogbalogp+1n)
p.14
6行目
b. p=-1ならば、T (n)=Θ(nlogabloglog n) b. p=-1ならば、T (n)=Θ(nlogbaloglog n)
p.14
7行目
c. p<-1ならば、T (n)=Θ(nlogab) c. p<-1ならば、T (n)=Θ(nlogba)
p.15
下から
2行目
T (n)={  c,                 n≦1のとき
 aT (n-b)+f (n), n1のとき
T (n)={  c,                 n≦1のとき
 aT (n-b)+f (n), n1のとき

目次

目次

格言(動機づけと啓発のため)
謝辞
序

1章 はじめに
    1.1 変数
    1.2 データ型
    1.3 データ構造
    1.4 抽象データ型(ADT)
    1.5 アルゴリズムとは
    1.6 なぜアルゴリズムの解析なのか
    1.7 実行時解析とは
    1.8 どのようにアルゴリズムを比較するのか
    1.9 増加率とは
    1.10 一般に用いられている増加率
    1.11 解析の種類
    1.12 漸近表記法
    1.13 O表記法
    1.14 Ω表記
    1.15 Θ表記
    1.16 なぜ漸近的解析と呼ぶのか
    1.17 漸近的解析のガイドライン
    1.18 表記の特性
    1.19 よく使われる対数と和
    1.20 分割統治マスター定理
    1.21 分割統治マスター定理の問題
    1.22 減算統治再帰(Subtract and Conquer Recurrences)マスター定理
    1.23 減算統治再帰マスター定理の変形
    1.24 ならし解析
    1.25 アルゴリズム解析の問題

2章 再帰と後戻り
    2.1 はじめに
    2.2 再帰とは
    2.3 再帰関数の形式
    2.4 再帰とメモリ(可視化)
    2.5 再帰と反復
    2.6 再帰に関する注意
    2.7 再帰アルゴリズムの例
    2.8 再帰の問題
    2.9 後戻りとは
    2.10 後戻りの問題

3章 連結リスト
    3.1 連結リストとは
    3.2 連結リストADT
    3.3 連結リストを使う理由
    3.4 配列の概観
    3.5 連結リストの配列や動的配列との比較
    3.6 単一連結リスト
    3.7 二重連結リスト
    3.8 循環連結リスト
    3.9 メモリ効率二重連結リスト
    3.10 連結リストの問題

4章 スタック
    4.1 スタックとは
    4.2 スタックはどのように使われるか?
    4.3 スタックADT
    4.4 応用
    4.5 実装
    4.6 実装の比較
    4.7 スタックの問題

5章 キュー
    5.1 キューとは
    5.2 キューはどのように使われるか
    5.3 キューADT
    5.4 例外
    5.5 応用
    5.6 実装
    5.7 キューの問題

6章 木
    6.1 木とは
    6.2 木の用語
    6.3 二分木
    6.4 二分木の型
    6.5 二分木の性質
    6.6 二分木横断
    6.7 一般木(N分木)
    6.8 スレッド二分木横断(スタック/キュー不要横断)
    6.9 式木
    6.10 XOR木
    6.11 二分探索木(BST)
    6.12 平衡二分探索木
    6.13 AVL木
    6.14 木の他の形式

7章 優先度付きキューとヒープ
    7.1 優先度付きキューとは
    7.2 優先度付きキューADT
    7.3 優先度付きキューの実装
    7.4 ヒープ
    7.5 二分ヒープ
    7.6 優先度付きキュー(ヒープ)の問題

8章 互いに素な集合ADT
    8.1 はじめに
    8.2 同値関係と同値類
    8.3 互いに素な集合ADT
    8.4 互いに素な集合ADT実装のトレードオフ
    8.5 まとめ
    8.6 互いに素な集合の問題

9章 グラフアルゴリズム
    9.1 はじめに
    9.2 グラフとは
    9.3 グラフの適用例
    9.4 グラフ表現
    9.5 グラフ横断
    9.6 トポロジカルソート
    9.7 最短経路アルゴリズム
    9.8 最小全域木
    9.9 グラフアルゴリズムの問題

10章 整列
    10.1 整列とは
    10.2 分類
    10.3 その他の分類
    10.4 バブルソート
    10.5 選択ソート
    10.6 挿入ソート
    10.7 シェルソート
    10.8 マージソート
    10.9 ヒープソート
    10.10 クイックソート
    10.11 ツリーソート
    10.12 整列アルゴリズムの比較
    10.13 線形整列アルゴリズム
    10.14 数え上げソート
    10.15 バケツソート(ビンソート)
    10.16 基数ソート
    10.17 トポロジカルソート
    10.18 外部整列
    10.19 整列の問題

11章 探索
    11.1 探索とは
    11.2 なぜ探索を行うのか?
    11.3 順不同線形探索
    11.4 整列/順序線形探索
    11.5 二分探索
    11.6 探索の問題

12章 選択アルゴリズム[中央値]
    12.1 選択アルゴリズムとは
    12.2 選択アルゴリズム
    12.3 選択アルゴリズムの問題

13章 記号表
    13.1 はじめに
    13.2 記号表とは
    13.3 記号表の実装

14章 ハッシュ
    14.1 ハッシュとは
    14.2 ハッシュ表ADT
    14.3 ハッシュを理解する
    14.4 ハッシュの構成要素
    14.5 衝突解消手法の比較
    14.6 ハッシュはどのようにして計算量O(1)を実現するのか?
    14.7 ハッシュ手法
    14.8 ハッシュの問題

15章 文字列アルゴリズム
    15.1 はじめに
    15.2 文字列照合アルゴリズム
    15.3 力任せ法
    15.4 ラビン・カープ文字列照合アルゴリズム
    15.5 有限オートマトンを使った文字列照合
    15.6 KMPアルゴリズム
    15.7 ボイヤー・ムーアアルゴリズム
    15.8 文字列を格納するためのデータ構造
    15.9 文字列のためのハッシュ表
    15.10 文字列のための二分探索木
    15.11 トライ
    15.12 三分探索木(TST)
    15.13 二分探索木、トライ、三分探索木の比較
    15.14 接尾辞木
    15.15 文字列に関する問題

16章 アルゴリズム設計技法
    16.1 はじめに
    16.2 分類
    16.3 実装方法による分類
    16.4 設計方法による分類
    16.5 その他の分類

17章 貪欲アルゴリズム
    17.1 はじめに
    17.2 ハフマン符号化アルゴリズム
    17.3 貪欲アルゴリズムの問題

18章 分割統治アルゴリズム
    18.1 はじめに
    18.2 分割統治法の可視化
    18.3 分割統治法を理解する
    18.4 分割統治法の利点
    18.5 分割統治法の欠点
    18.6 マスター定理
    18.7 分割統治法の問題

19章 動的プログラミング
    19.1 はじめに
    19.2 動的プログラミングの方法
    19.3 動的プログラミングの例
    19.4 動的プログラミングの問題

20章 計算量クラス
    20.1 はじめに
    20.2 計算量クラスの種類
    20.3 帰着/簡約
    20.4 計算量クラスの問題

21章 その他の各種概念
    21.1 はじめに
    21.2 ビット単位プログラミング
    21.3 その他のプログラミング問題

参考文献
訳者あとがき
索引