なっとく！アルゴリズム

2019年1月28日

翔泳社

著者：Aditya Bhargava
監訳：株式会社クイープ

まえがき
謝辞
本書について
著書紹介
目次

第1章あれもこれもアルゴリズム
1.1 はじめに
1.1.1 パフォーマンスについて学ぶこと
1.1.2 問題の解決について学ぶこと
1.2 二分探索
1.2.1 より効果的な探索法
1.2.2 時間計算量
1.3 ビッグオー記法
1.3.1 時間計算量が増えるペースはアルゴリズムによって異なる
1.3.2 さまざまな時間計算量をビッグオー記法で可視化する
1.3.3 ビッグオーは最悪の場合の時間計算量を定める
1.3.4 ビッグオー記法の一般的な時間計算量
1.3.5 巡回セールスマン
1.4 まとめ

第2章並べたり差し込んだり選んだり：ソート
2.1 メモリの仕組み
2.2 配列とリンクリスト
2.2.1 リンクリスト
2.2.2 配列
2.2.3 用語
2.2.4 リストの途中に挿入する
2.2.5 削除
2.3 選択ソート
2.3.1 サンプルコード
2.4 まとめ

第3章同じ手順で何度でも：再帰
3.1 再帰
3.2 基本ケースと再帰ケース
3.3 スタック
3.3.1 コールスタック
3.3.2 再帰でのコールスタック
3.4 まとめ

第4章ちっちゃくしてから考えよう：クイックソート
4.1 分割統治
4.2 クイックソート
4.3 ビッグオー記法の再考
4.3.1 マージソートとクイックソート
4.3.2 平均的なケースと最悪のケース
4.4 まとめ

第5章関連付ければ話も早い：ハッシュテーブル
5.1 ハッシュ関数
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 キュー
6.4 グラフの実装
6.5 アルゴリズムの実装
6.5.1 時間計算量
6.6 まとめ

第7章本からピアノへ物々交換大作戦：ダイクストラ法
7.1 ダイクストラ法
7.2 用語
7.3 ピアノの物々交換
7.4 負の重みをもつ辺
7.5 実装
7.6 まとめ

第8章問題は続くよどこまでも：貪欲法
8.1 教室の時間割問題
8.2 ナップザック問題
8.3 集合カバー問題
8.3.1 近似アルゴリズム
8.4 NP完全問題
8.4.1 巡回セールスマン：ステップバイステップ
8.4.2 NP完全問題かどうかを見分ける方法
8.5 まとめ

第9章ドロボーは計画的に：動的計画法
9.1 ナップザック問題
9.1.1 単純解
9.1.2 動的計画法
9.2 ナップザック問題のFAQ
9.2.1 品物を追加するとどうなるか
9.2.2 行の順序を変更するとどうなるか
9.2.3 グリッドを行ごとではなく列ごとに埋めることはできるか
9.2.4 もっと小さい品物を追加するとどうなるか
9.2.5 品物の一部を盗むことはできるか
9.2.6 旅行日程の最適化
9.2.7 相互に依存する項目に対処する
9.2.8 部分ナップザックを3つ以上要求する解はあり得るか
9.2.9 ナップザックが完全に埋まらない最適解はあり得るか
9.3 最長共通部分文字列
9.3.1 グリッドの作成
9.3.2 グリッドの設定
9.3.3 解
9.3.4 最長共通部分列
9.3.5 最長共通部分列の解
9.4 まとめ

第10章分類したら予測して：ｋ近傍法
10.1 オレンジとグループフルーツの分類
10.2 レコメンデーションシステムの構築
10.2.1 特徴抽出
10.2.2 回帰
10.2.3 よい特徴量の選択
10.3 速習：機械学習
10.3.1 OCR
10.3.2 スパムフィルタの構築
10.3.3 株価の予測
10.4 まとめ

第11章この先にはなにがあるの？
11.1 木(ツリー)
11.2 転置インデックス
11.3 フーリエ変換
11.4 並列アルゴリズム
11.5 MapReduce
11.5.1 分散アルゴリズムはなぜ便利か
11.5.2 map関数
11.5.3 reduce関数
11.6 ブルームフィルタとHyperLogLog
11.6.1 ブルームフィルタ
11.6.2 HyperLogLog
11.7 SHAアルゴリズム
11.7.1 ファイルの比較
11.7.2 パスワードの確認
11.8 LSハッシュ
11.9 ディフィー・ヘルマン鍵交換
11.10 線形計画法
11.11 エピローグ