Pythonによるアルゴリズム入門

詳細目次

アルゴリズムに取り組む方へ

第1章　アルゴリズムをはじめる前に
1.1　データ構造とアルゴリズム
1.1.1　データ構造は使いやすさが大事
1.1.2　アルゴリズムはデータを上手に扱う方法
1.2　アルゴリズムの計算量
1.2.1　ステップ数
1.2.2　漸近的計算量（オーダー記法）
1.2.3　計算量の分類
1.3　Pythonについて
1.3.1　プログラミング言語とは
1.3.2　Pythonはインタプリタ型言語

第2章　準備
2.1　macOSでPython環境の構築
2.2　Windows 10でPython環境の構築
2.3　動作確認
2.3.1　Pythonの実行方法
2.5　開発環境

第3章　データ構造
3.1　配列内データの動きの基本
3.1.1　配列に対する操作
3.1.2　Pythonの標準ライブラリのリストで配列
3.1.3　arrayモジュールの配列を利用したinsert機能、delete機能の実装
3.2　連結リスト
3.2.1　連結リストの種類
3.2.2　連結リストに対する操作（エンキューとデキュー）
3.2.3　双方向連結リストの実装
3.3　キュー（先入れ先出しの性質を持つ待ち行列）
3.3.1　キューの用途
3.3.2　キューに対する操作
3.3.3　配列を用いたキュー
3.3.4　連結リストを用いたキューの実装
3.3.5　双方向連結リストのソースコードを再利用したキューの実装
3.4　スタック
3.4.1　スタックの用途
3.4.2　スタックに対する操作
3.4.3　配列を用いたスタック
3.4.4　連結リストを用いたスタック
3.5　各データ構造の計算量

第4章　ソートアルゴリズム
4.1　ソートアルゴリズムの概要
4.2　挿入ソート
4.2.1　挿入ソートの概要
4.2.2　挿入ソートの実装
4.2.3　挿入ソートの特徴
4.3　バブルソート
4.3.1　バブルソートの概要
4.3.2　バブルソートの実装
4.3.3　バブルソートの特徴
4.4　マージソート
4.4.1　マージソートの概要
4.4.2　マージソートの実装
4.4.3　マージンソートの特徴
4.5　クイックソート
4.5.1　クイックソートの特徴
4.5.2　クイックソートの性質
4.6　ソートアルゴリズムの比較
4.6.1　大きな配列をソートしたときの実測値の比較

第5章　探索アルゴリズム
5.1　線形探索
5.1.1　配列を用いた線形探索の実装コード
5.2　二分探索
5.2.1　二分探索の概要
5.2.2　配列の二分探索の実装例
5.3　ハッシュ探索
5.3.1　ハッシュ関数
5.3.2　ハッシュ表（ハッシュ探索の準備のために）
5.3.3　チェイン法を用いたハッシュ探索の実装例

第6章　木構造
6.1　木構造の用途
6.2　木構造の基本
6.3　二分探索木
6.3.1　二分探索木を実現するプログラムの概要
6.3.2　二分探索木の実装例
6.4　ヒープ(heap)
6.4.1　ヒープが活躍する場面
6.4.2　完全二分木を用いたヒープの概要
6.4.3　ヒープの実装例

第7章　グラフアルゴリズム
7.1　グラフの用途
7.2　グラフ構造の基本
7.2.1　無向グラフと有向グラフ
7.3　隣接行列を用いたグラフの表現
7.3.1　隣接行列を用いた無向グラフ
7.3.2　隣接行列を用いた有向グラフ
7.4　クラスを用いた無向グラフの表現
7.4.1　クラスを用いた無向グラフの実装例
7.5　幅優先探索
7.5.1　幅優先探索と深さ優先探索
7.5.2　幅優先探索の概要
7.5.3　幅優先探索の実装例
7.6　深さ優先探索
7.6.1　深さ優先探索の概要
7.6.2　深さ優先探索の実装例
7.7　ダイクストラ法
7.7.1　距離の定義
7.7.2　ダイクストラ法の概要
7.7.3　ダイクストラ法の実装例
7.7.4　ダイクストラ法の計算量

第8章　その他の有用なアルゴリズム
8.1　ユークリッドの互除法
8.1.1　最大公約数
8.1.2　最大公約数を求めるアルゴリズム
8.1.3　ユークリッドの互除法の実装例
8.2　文字列探索
8.2.1　力まかせ法
8.2.2　BM法-効率的な探索
8.2.3　実測値の比較
8.3　A*アルゴリズム
8.3.1　A*アルゴリズムの用途
8.3.2　A*アルゴリズムの原理
8.3.3　A*アルゴリズムの実装例
8.3.4　A*プログラムの実行
8.4　動的計画法
8.4.1　ナップサック問題
8.4.2　動的計画法の原理
8.4.3　動的計画法を用いたナップサック問題の実装例
8.4.4　ナップサック問題プログラムの実行
8.5　計算幾何学に関するアルゴリズム
8.5.1　凸包とは
8.5.2　計算幾何学の基本プログラミング
8.5.3　ギフト包装法による凸包アルゴリズム
8.5.4　ギフト包装法の実装例
8.5.5　ギフト包装法プログラムの実行
8.5.6　凸包をGUIで表示するプログラム
8.5.7　ギフト包装法プログラムの実行
付録A　unicodeの一部
最後に

索引