問題解決力を鍛える！アルゴリズムとデータ構造
2020
著 大槻兼資・著　秋葉拓哉・監修
PDFなし
https://youtu.be/RXvDkLdLHOw
構成が独特
問題をどう解くのか（設計技法）をまず説明する（3-7章）
以降設計技法がどうつかわれているのかを意識しながらの説明
言語はC++
計算量とオーダー記法
ランダウの記号 O(f(n)) は n が無限大でどのような関数で押さえられるか、についての表現だ。
なので実行時間を論じているときには、n が 10^6 みたいな小さい値の周辺でフィットする行為は実行時間のオーダーを推測する補助手段でしかない。
2010 haskell の fib は遅くない - 白のカピバラの逆極限 S.144-3
設計技法
全探索
再帰と分割統治法
動的計画法
二分探索法
貪欲法
データ構造
配列、連結リスト、ハッシュテーブル
スタックとqueue
グラフとTree
Union-Find
ソート
グラフ
グラフ探索
最短経路問題
最小全域木問題
ネットワークフロー
PとNP
目次
問題解決力を鍛える！アルゴリズムとデータ構造 | 書籍情報 | 株式会社 講談社サイエンティフィク
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)：配列、連結リスト、ハッシュテーブル （ Linked List）
8.1 データ構造を学ぶ意義
8.2 配列
8.3 連結リスト
8.4 連結リストの挿入操作と削除操作
8.5 配列と連結リストの比較
8.6 ハッシュテーブル
8.7 まとめ
9章 データ構造(2)：スタックとキュー (stack and queue）
9.1 スタックとキューの概念
9.2 スタックとキューの動作と実装
9.3 まとめ
10章 データ構造(3)：グラフと木 （Graph and tree）
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 まとめ