Pythonではじめるアルゴリズム入門 伝統的なアルゴリズムで学ぶ定石と計算量
Pythonではじめるアルゴリズム入門 伝統的なアルゴリズムで学ぶ定石と計算量
翔泳社
著者：増井敏克
はじめに
実務にアルゴリズムは必要か？
アルゴリズムの学び方
本書の構成
付属データのダウンロード
第1章 Pythonの基本とデータ構造を知る
1.1 プログラミング言語の選択
目的によって言語を選ぼう
Pythonを選ぶ理由
変換方式の違いを知ろう
1.2 プログラミング言語Pythonの概要
Pythonの特徴
Pythonを実行する
対話モードでPythonを使う
スクリプトファイルへの保存
文字コードについての注意
コメント
1.3 四則演算と優先順位
Pythonにおける基本的な計算
小数の計算
データの型を調べる
1.4 変数と代入、リスト、タプル
変数
代入
リスト
タプル
1.5 文字と文字列
文字と文字列の操作
文字列の連結
1.6 条件分岐と繰り返し
条件分岐
長い行の記述方法
繰り返し
1.7 リスト内包表記
リストの生成
条件を指定したリストの生成
1.8 関数とクラス
関数の作成
値渡しと参照渡し
変数の有効範囲
オブジェクト指向とクラス
理解度Check！
第2章 基本的なプログラムを作ってみる
2.1 フローチャートを描く
処理の流れを表現する
よく使われる記号を学ぶ
簡単なフローチャートを描く
2.2 FizzBuzzを実装する
採用試験によく使われる問題
3の倍数のときに「Fizz」を出力する
5の倍数の時に「Buzz」を出力する
3と5の両方の倍数の場合に「FizzBuzz」を出力する
2.3 自動販売機でお釣りを計算する
お釣りの枚数を最小にするには？
お釣りの金額を計算する
リストトループでシンプルな実装に変える
不適切な入力に対応する
2.4 基数を変換する
10進数と2進数
10進数から2進数に変換する
2進数から10進数に変換する
2.5 素数を判定する
素数の求め方
素数か調べるプログラムを作成する
高速に素数を求める方法を考える
2.6 フィボナッチ数列を作る
フィボナッチ数列とは？
フィボナッチ数列をプログラムで求める
メモ化によって処理を高速化する
理解度Check！
第3章 計算量について学ぶ
3.1 計算コストと実行時間、時間計算量
良いアルゴリズムとは？
処理時間の増え方をどうやって調べるか？
アルゴリズムの性能を評価する計算量
FizzBuzzの計算量を調べる
掛け算の計算量を調べる
「体積を求める計算量」を調べる
計算量を比較する
最悪時間計算と平均時間計算量
3.2 データ構造による計算量の違い
連結リストの考え方
連結リストの挿入
連結リストの削除
連結リストでの読み取り
リストと連結リストの使い分け
3.3 アルゴリズムの計算量と問題の計算量
計算量のクラスとは？
指数関数時間のアルゴリズムとは？
階乗の計算が必要なアルゴリズム
難しいP≠NP予想
理解度Check！
第4章 いろいろな探索方法を学ぶ
4.1 線形探索
日常生活における探索を知る
プログラミングにおける探索とは？
線形探索を行なう関数を定義する
4.2 二分探索
探索範囲を半分に分ける
データが増えたときの比較回数を考える
4.3 木構造での探索
階層構造のデータからの探索を考える
幅優先探索
深さ優先探索
幅優先探索を実装する
深さ優先探索を実装する
行きがけ順
帰りがけ順
通りがけ順
4.4 さまざまな例を実装する
迷路の探索（番兵）
幅優先探索で探す
単純な深さ優先探索で探す
右手法による深さ優先探索で探す
8クイーン問題
n-クイーン問題
ハノイの塔
フォルダにあるファイルを探す
深さ優先探索
幅優先探索
3目並べ
ミニマックス法による評価
理解度Check！
第5章 データの並べ替えにかかる時間を比べる
5.1 身近な場面でも使われる「並べ替え」とは？
並べ替えが求められる場面
ソートのアルゴリズムを学ぶ理由
5.2 選択ソート
小さいものを選ぶ
選択ソートの実装
選択ソートの計算量
5.3 挿入ソート
ソート済みリストに追加する
後ろから移動する
挿入ソートの実装
挿入ソートの計算量
5.4 バブルソート
隣同士で交換する
バブルソートの実装
バブルソートの改良
5.5 ヒープソート
リストから効率よく使うデータ構造を知る
最後に入れたものから取り出すスタック
スタックを実装する
最初に入れたものから取り出すキュー
キューを実装する
木構造で表すヒープ
ヒープへの要素の追加
ヒープからの要素の削除
ヒープの構成にかかる時間
ヒープソートを実装する
汎用的な実装を作る
ライブラリを使う
5.6 マージソート
分割して統合する
マージソートの実装
マージソートの計算量
5.7 クイックソート
分割した内部で並び替える
クイックソートの実装
クイックソートの計算量
5.8 処理速度を比較する
計算量での比較
実データでの比較
安定ソート
理解度Check！
第6章 実務に役立つアルゴリズムを知る
6.1 最短経路問題とは？
数値化したコストで考える
経路をすべて調べる
グラフで考える
6.2 ベルマン・フォード法
辺の重みに注目する
初期値として無限大を設定する
コストを更新する
プログラムでの実装
ベルマン・フォード法での注意点
6.3 ダイクストラ法
頂点に注目して最短経路を探す
Pythonで実装する
計算量を考え、高速化する
ヒープによる優先度付きキューを実装する
ダイクストラ法の注意点
6.4 A*アルゴリズム
無駄な経路をできるだ探索しない
コストの推定値を考える
A*アルゴリズムの実装
6.5 文字列探索の力任せ法
索引のない文字列から探す
一致する位置を前から順に探す
力任せ法の実装
6.6 Boyer-Moore法
力任せ法の問題点
末尾から比較し、一気にずらす
処理時間の比較
6.7 逆ポーランド記法
演算子を前に置くポーランド記法
演算子を後ろに置く逆ポーランド記法
6.8 ユークリッドの互除法
最大公約数を効率よく求める
高度なアルゴリズムを学ぶ
理解度Check！
付録A Pythonのインストール
A.1 Pythonの処理系を知る
A.2 AnacondaでPythonをインストールする
Windowsの場合
macOSやLinuxの場合
A.3 複数のバージョンのPythonを切り替える
A.4 パッケージのインストールと削除
A.5 インストールがエラーになった場合
付録B 理解度Check！の解答
第1章
第2章
第3章
第4章
第5章
第6章
索引
著者紹介
Memo目次
複素数の計算
divmode関数
SymPyライブラリ
木構造
リストで扱う値
Column目次
テキストエディタを使おう
リスト内包表記でのif～else
モジュールとパッケージ
フローチャートは時代遅れか？
ビット演算
平均を求める
人が使うのにも役立つ二分探索
スキップリスト
現実的には重要な枝刈り
連結リストによる挿入ソート
並列処理と並行処理
図書館ソート
経路の数を求める問題