Pythonによるアルゴリズム設計
書籍情報
発売日 : 2022年09月07日
著者／編集 : 神野 健哉
出版社 : コロナ社
発行形態 : 単行本
書籍説明
内容紹介
ある目的を解決するアルゴリズムを複数紹介し，アルゴリズムの違いで処理速度の変化を体感できる。大規模データを取り扱う際はアルゴリズムにより処理速度が変わるためその概念を理解してPythonで実装できるようにした。
目次
1. アルゴリズムとは
1.1 アルゴリズムの要件
1.1.1 停止性
1.1.2 正当性
1.1.3 汎用性
1.2 フローチャート
1.2.1 順次処理
1.2.2 選択処理
1.2.3 反復処理
1.3 最大値の探索
1.3.1 勝ち抜き方式
1.3.2 トーナメント方式
1.4 アルゴリズム
章末問題
2. Selection sortとBubble sort
2.1 Pythonのリスト構造
2.1.1 リストの生成
2.1.2 リストの結合
2.1.3 リストの比較
2.1.4 リストの要素のアクセス
2.1.5 スライスによるリストの要素のアクセス
2.1.6 リストの要素の置換
2.1.7 リストのコピー
2.1.8 リストの要素の追加（appendメソッド）
2.1.9 リストの要素の追加（extendメソッド，累算代入）
2.1.10 リストの要素の挿入（insertメソッド，スライス操作）
2.1.11 リストの要素の削除（popメソッド，del）
2.2 最大値/最小値に着目した並べ替え
2.2.1 Selection sort
2.2.2 Bubble sort
章末問題
3. Merge sortと再帰関数
3.1 関数
3.1.1 関数の定義
3.1.2 再帰呼び出し
3.2 Merge sort
3.2.1 Merge sortのアルゴリズム
3.2.2 Merge sortの実装
3.2.3 Merge sortの実装の改良
3.2.4 Merge sortのpopを使用しない実装
章末問題
4. Quick sortとリスト内包表記
4.1 Quick sort
4.1.1 データ分割法
4.1.2 実装
4.2 リスト内包表記
4.2.1 イテラブルオブジェクト
4.2.2 リスト内包表記の基本形
4.2.3 ifを利用した内包表記
4.2.4 if～elseを利用した内包表記
4.2.5 複合型
4.3 リスト内包表記を利用したQuick sort
章末問題
5. 計算量
5.1 実行時間
5.2 アルゴリズムの計算手順
5.2.1 Selection sort
5.2.2 Bubble sort
5.2.3 Merge sort
5.2.4 Quick sort
5.3 アルゴリズムの評価指標
5.3.1 時間計算量
5.3.2 O記法
章末問題
6. 検索
6.1 線形検索
6.2 二分検索
6.3 ハッシュ法
6.4 辞書
6.4.1 辞書の生成
6.4.2 辞書の情報
6.4.3 in演算子
6.4.4 辞書の要素の置換・追加
6.4.5 辞書の要素の削除
6.5 辞書を用いた検索
章末問題
7. グラフとUnion-Findアルゴリズム
7.1 グラフ
7.2 集合
7.2.1 集合の生成
7.2.2 in演算子による集合の帰属性判定
7.2.3 集合の要素の追加・削除
7.2.4 集合演算
7.3 Union-Findアルゴリズム
7.3.1 Find操作
7.3.2 Union操作
7.4 橋の検出
章末問題
8. 最小全域木
8.1 全域木
8.2 クラスカル法
8.3 プリム法
章末問題
9. 幅優先探索（BFS）と深さ優先探索（DFS）
9.1 木構造データ
9.2 幅優先探索：BFS
9.2.1 幅優先探索のアルゴリズム
9.2.2 キュー構造
9.2.3 幅優先探索の実装
9.3 深さ優先探索：DFS
9.3.1 深さ優先探索のアルゴリズム
9.3.2 スタック構造
9.3.3 深さ優先探索の実装
9.3.4 繰り返しでのbreak文
章末問題
10. 最短経路問題
10.1 最短経路
10.2 ベルマン・フォード法
10.2.1 ベルマン・フォード法のアルゴリズム
10.2.2 ベルマン・フォード法の探索の実例
10.2.3 ベルマン・フォード法の実装
10.3 ダイクストラ法
10.3.1 ダイクストラ法のアルゴリズム
10.3.2 ダイクストラ法の探索の実例
10.3.3 ダイクストラ法の実装
章末問題
11. 最大フロー問題
11.1 フローネットワーク
11.2 フォード・ファルカーソン法
11.3 最小カット問題
11.4 フォード・ファルカーソン法の実装
章末問題
12. 最大マッチング問題・割当問題
12.1 マッチング
12.1.1 二部グラフ
12.1.2 最大マッチング
12.2 最大フローによる最大マッチングの解法
12.3 割当問題
12.4 実装
章末問題
13. ナップサック問題
13.1 0-1ナップサック問題
13.2 貪欲法・動的計画法
13.2.1 貪欲法
13.2.2 動的計画法
13.2.3 動的計画法による探索の実例
13.3 動的計画法によるナップサック問題の解法の実装
章末問題
14. 敵対探索
14.1 ミニマックス法
14.2 「エイト」ゲーム
14.3 ミニマックス法の実装
章末問題
引用・参考文献
章末問題解答
索引
1.1 アルゴリズムの要件
1.1.1 停止性
1.1.2 正当性
1.1.3 汎用性
1.2 フローチャート
1.2.1 順次処理
1.2.2 選択処理
1.2.3 反復処理
1.3 最大値の探索
1.3.1 勝ち抜き方式
1.3.2 トーナメント方式
1.4 アルゴリズム
章末問題
2. Selection sortとBubble sort
2.1 Pythonのリスト構造
2.1.1 リストの生成
2.1.2 リストの結合
2.1.3 リストの比較
2.1.4 リストの要素のアクセス
2.1.5 スライスによるリストの要素のアクセス
2.1.6 リストの要素の置換
2.1.7 リストのコピー
2.1.8 リストの要素の追加（appendメソッド）
2.1.9 リストの要素の追加（extendメソッド，累算代入）
2.1.10 リストの要素の挿入（insertメソッド，スライス操作）
2.1.11 リストの要素の削除（popメソッド，del）
2.2 最大値/最小値に着目した並べ替え
2.2.1 Selection sort
2.2.2 Bubble sort
章末問題
3. Merge sortと再帰関数
3.1 関数
3.1.1 関数の定義
3.1.2 再帰呼び出し
3.2 Merge sort
3.2.1 Merge sortのアルゴリズム
3.2.2 Merge sortの実装
3.2.3 Merge sortの実装の改良
3.2.4 Merge sortのpopを使用しない実装
章末問題
4. Quick sortとリスト内包表記
4.1 Quick sort
4.1.1 データ分割法
4.1.2 実装
4.2 リスト内包表記
4.2.1 イテラブルオブジェクト
4.2.2 リスト内包表記の基本形
4.2.3 ifを利用した内包表記
4.2.4 if～elseを利用した内包表記
4.2.5 複合型
4.3 リスト内包表記を利用したQuick sort
章末問題
5. 計算量
5.1 実行時間
5.2 アルゴリズムの計算手順
5.2.1 Selection sort
5.2.2 Bubble sort
5.2.3 Merge sort
5.2.4 Quick sort
5.3 アルゴリズムの評価指標
5.3.1 時間計算量
5.3.2 O記法
章末問題
6. 検索
6.1 線形検索
6.2 二分検索
6.3 ハッシュ法
6.4 辞書
6.4.1 辞書の生成
6.4.2 辞書の情報
6.4.3 in演算子
6.4.4 辞書の要素の置換・追加
6.4.5 辞書の要素の削除
6.5 辞書を用いた検索
章末問題
7. グラフとUnion-Findアルゴリズム
7.1 グラフ
7.2 集合
7.2.1 集合の生成
7.2.2 in演算子による集合の帰属性判定
7.2.3 集合の要素の追加・削除
7.2.4 集合演算
7.3 Union-Findアルゴリズム
7.3.1 Find操作
7.3.2 Union操作
7.4 橋の検出
章末問題
8. 最小全域木
8.1 全域木
8.2 クラスカル法
8.3 プリム法
章末問題
9. 幅優先探索（BFS）と深さ優先探索（DFS）
9.1 木構造データ
9.2 幅優先探索：BFS
9.2.1 幅優先探索のアルゴリズム
9.2.2 キュー構造
9.2.3 幅優先探索の実装
9.3 深さ優先探索：DFS
9.3.1 深さ優先探索のアルゴリズム
9.3.2 スタック構造
9.3.3 深さ優先探索の実装
9.3.4 繰り返しでのbreak文
章末問題
10. 最短経路問題
10.1 最短経路
10.2 ベルマン・フォード法
10.2.1 ベルマン・フォード法のアルゴリズム
10.2.2 ベルマン・フォード法の探索の実例
10.2.3 ベルマン・フォード法の実装
10.3 ダイクストラ法
10.3.1 ダイクストラ法のアルゴリズム
10.3.2 ダイクストラ法の探索の実例
10.3.3 ダイクストラ法の実装
章末問題
11. 最大フロー問題
11.1 フローネットワーク
11.2 フォード・ファルカーソン法
11.3 最小カット問題
11.4 フォード・ファルカーソン法の実装
章末問題
12. 最大マッチング問題・割当問題
12.1 マッチング
12.1.1 二部グラフ
12.1.2 最大マッチング
12.2 最大フローによる最大マッチングの解法
12.3 割当問題
12.4 実装
章末問題
13. ナップサック問題
13.1 0-1ナップサック問題
13.2 貪欲法・動的計画法
13.2.1 貪欲法
13.2.2 動的計画法
13.2.3 動的計画法による探索の実例
13.3 動的計画法によるナップサック問題の解法の実装
章末問題
14. 敵対探索
14.1 ミニマックス法
14.2 「エイト」ゲーム
14.3 ミニマックス法の実装
章末問題
引用・参考文献
章末問題解答
索引
著者情報
神野 健哉
神野, 健哉, 1966-
