問題解決力を鍛える!アルゴリズムとデータ構造

大槻兼資・著 秋葉拓哉・監修

問題解決力を鍛える!アルゴリズムとデータ構造

発行
2020/09/30
サイズ
A5
ページ数
368
ISBN
978-4-06-512844-2
本体
3000円(税別)
在庫
在庫あり

書籍を購入する

本体
3000円(税別)

内容紹介

競技プログラミング経験が豊富な著者が、「アルゴリズムを自分の道具としたい」という読者に向けて執筆。入門書を標榜しながら、AtCoderの例題、C++のコードが充実。入門書であり実践書でもある、生涯役立つテキストを目指した。

目次

1章 アルゴリズムとは
1.1 アルゴリズムとは何か
1.2 アルゴリズムの例(1):深さ優先探索と幅優先探索
1.3 アルゴリズムの例(2):マッチング
1.4 アルゴリズムの記述方法
1.5 アルゴリズムを学ぶ意義

2章 計算量とオーダー記法
2.1 計算量とは
2.2 計算量のオーダー記法
2.3 計算量を求める例(1):偶数の列挙
2.4 計算量を求める例(2):最近点対問題
2.5 計算量の使い方
2.6 計算量に関する注釈
2.7 ランダウのO記法の詳細
2.8 まとめ

3章 設計技法(1):全探索
3.1 全探索を学ぶ意義
3.2 全探索(1):線形探索法
3.3 線形探索法の応用
3.4 全探索(2):ペアの全探索
3.5 全探索(3):組合せの全探索
3.6 まとめ

4章 設計技法(2):再帰と分割統治法
4.1 再帰とは
4.2 再帰の例(1):ユークリッドの互除法
4.3 再帰の例(2):フィボナッチ数列
4.4 メモ化して動的計画法へ
4.5 再帰の例(3):再帰関数を用いた全探索
4.6 分割統治法
4.7 まとめ

5章 設計技法(3):動的計画法
5.1 動的計画法とは
5.2 最初の例題
5.3 動的計画法に関連する諸概念
5.4 動的計画法の例(1):ナップサック問題
5.5 動的計画法の例(2):編集距離
5.6 動的計画法の例(3):区間分割の仕方を最適化
5.7 まとめ

6章 設計技法(4):二分探索法
6.1 配列の二分探索
6.2 C++のstd::lower bound()
6.3 一般化した二分探索法
6.4 さらに一般化した二分探索法
6.5 応用例(1):年齢当てゲーム
6.6 応用例(2):std::lower bound() の活用例
6.7 応用例(3):最適化問題を判定問題に
6.8 応用例(4):メディアンを求める
6.9 まとめ

7章 設計技法(5):貪欲法
7.1 貪欲法とは
7.2 貪欲法が最適解を導くとは限らないこと
7.3 貪欲法パターン(1):交換しても悪化しない
7.4 貪欲法パターン(2):現在がよいほど未来もよい
7.5 まとめ

8章 データ構造(1):配列、連結リスト、ハッシュテーブル
8.1 データ構造を学ぶ意義
8.2 配列
8.3 連結リスト
8.4 連結リストの挿入操作と削除操作
8.5 配列と連結リストの比較
8.6 ハッシュテーブル
8.7 まとめ

9章 データ構造(2):スタックとキュー
9.1 スタックとキューの概念
9.2 スタックとキューの動作と実装
9.3 まとめ

10章 データ構造(3):グラフと木
10.1 グラフ
10.2 グラフの例
10.3 グラフの実装
10.4 重み付きグラフの実装
10.5 木
10.6 順序木と二分木
10.7 二分木を用いるデータ構造の例(1):ヒープ
10.8 二分木を用いるデータ構造の例(2):二分探索木
10.9 まとめ

11章 データ構造(4):Union-Find
11.1 Union-Findとは
11.2 Union-Findの仕組み
11.3 Union-Findの計算量を削減する工夫
11.4 Union-Findの工夫その1:union by size
11.5 Union-Findの工夫その2:経路圧縮
11.6 Union-Findの実装
11.7 Union-Findの応用:グラフの連結成分の個数
11.8 まとめ

12章 ソート
12.1 ソートとは
12.2 ソートアルゴリズムの良し悪し
12.3 ソート(1):挿入ソート
12.4 ソート(2):マージソート
12.5 ソート(3):クイックソート
12.6 ソート(4):ヒープソート
12.7 ソートの計算量の下界
12.8 ソート(5):バケットソート
12.9 まとめ

13章 グラフ(1):グラフ探索
13.1 グラフ探索を学ぶ意義
13.2 深さ優先探索と幅優先探索
13.3 再帰関数を用いる深さ優先探索
13.4 「行きがけ順」と「帰りがけ順」
13.5 最短路アルゴリズムとしての幅優先探索
13.6 深さ優先探索と幅優先探索の計算量
13.7 グラフ探索例(1):s-tパスを求める
13.8 グラフ探索例(2):二部グラフ判定
13.9 グラフ探索例(3):トポロジカルソート
13.10 グラフ探索例(4):木上の動的計画法
13.11 まとめ

14章 グラフ(2):最短路問題
14.1 最短路問題とは
14.2 最短路問題の整理
14.3 緩和
14.4 DAG上の最短路問題:動的計画法
14.5 単一始点最短路問題:ベルマン・フォード法
14.6 単一始点最短路問題:ダイクストラ法
14.7 全点対間最短路問題:フロイド・ワーシャル法
14.8 参考:ポテンシャルと差分制約系
14.9 まとめ

15章 グラフ(3):最小全域木問題
15.1 最小全域木問題とは
15.2 クラスカル法
15.3 クラスカル法の実装
15.4 全域木の構造
15.5 クラスカル法の正当性
15.6 まとめ

16章 グラフ(4):ネットワークフロー
16.1 ネットワークフローを学ぶ意義
16.2 グラフの連結度
16.3 最大流問題と最小カット問題
16.4 フォード・ファルカーソン法の実装
16.5 応用例(1):二部マッチング
16.6 応用例(2):点連結度
16.7 応用例(3):プロジェクト選択問題
16.8 まとめ

17章 PとNP
17.1 問題の難しさの測り方
17.2 PとNP
17.3 P ≠ NP予想
17.4 NP完全
17.5 多項式時間帰着の例
17.6 NP困難
17.7 停止性問題
17.8 まとめ

18章 難問対策
18.1 NP困難問題との対峙
18.2 特殊ケースで解ける場合
18.3 貪欲法
18.4 局所探索と焼きなまし法
18.5 分枝限定法
18.6 整数計画問題への定式化
18.7 近似アルゴリズム
18.8 まとめ