Python ではじめるアルゴリズム入門 伝統的なアルゴリズムで学ぶ定石と計算量

時代が変わっても
変わらないアルゴリズムから考え方を学ぼう

本書は、初心者にも扱いやすいプログラミング言語「Python」を使用して、
アルゴリズムの基礎・考え方を学ぶ入門書です。特に Python がはじめてという方の
ために、第 1 章では Python の基本とデータ構造について解説しています。

本書では、プログラミング入門者が最低限知っておきたいアルゴリズムの
基礎と考え方に加えて、アルゴリズムの定石とその計算量について、具体的
なサンプルコードと動作イメージを交えて丁寧に解説していきます。

【こんな方におすすめ】
・アルゴリズムをゼロから学びたい
・Python でプログラミングを学んでいるけれど何から手をつけていいのかわからない
・過去にアルゴリズムを学ぼうと思ったけれど Python の資料が少なかった
・基本情報技術者試験で Python が取り入れられるので勉強したい

【本書の特徴】
・Python の基本とアルゴリズムの基礎を一冊で学べる
・具体的なサンプルコードと動作イメージ (フローチャート) を交えて解説
・自分で書いて実行して動作を試しながら学習できる
・アルゴリズムの使い方や考え方だけでなく、アルゴリズムの計算量について
の理解も深まる

【扱うアルゴリズム】
FizzBuzz｜フィボナッチ数列｜線形探索｜二分探索｜幅優先探索｜
深さ優先探索｜番兵｜8 クイーン問題｜n-クイーン問題｜ハノイの塔｜
ミニマックス法｜選択ソート｜挿入ソート｜バブルソート｜ヒープソート｜
マージソート｜クイックソート｜最短経路問題｜ベルマン・フォード法｜
ダイクストラ法｜A*アルゴリズム｜文字列探索の力任せ法｜Boyer-Moore 法｜
逆ポーランド記法｜ユークリッドの互除法

【章構成】
■第 1 章 Python の基本とデータ構造を知る
■第 2 章 基本的なプログラムを作ってみる
■第 3 章 計算量について学ぶ
■第 4 章 いろいろな探索方法を学ぶ
■第 5 章 データの並べ替えにかかる時間を比べる
■第 6 章 実務に役立つアルゴリズムを知る
■Appendix Python のインストール

アルゴリズムを何から学べばよいか分からない人に向けて、Python の基本から始め、探索やソートといった伝統的なアルゴリズムの定石を計算量とあわせて身につけさせる入門書です。『Python ではじめるアルゴリズム入門』は増井敏克 著で、翔泳社から 2020 年 1 月 24 日に発売されました。副題は「伝統的なアルゴリズムで学ぶ定石と計算量」です。版元は、Python がはじめての方のために第 1 章で Python の基本とデータ構造を解説していると案内しており、具体的なサンプルコードとフローチャートによる動作イメージを交え、自分で書いて実行しながら学ぶ形をとります。

Python の基本から最短経路まで、全 6 章と付録の構成

目次は第 1 章「Python の基本とデータ構造を知る」から第 6 章「実務に役立つアルゴリズムを知る」までの 6 章と、Python のインストールを扱う付録です。第 2 章では FizzBuzz、お釣りの計算、基数の変換、素数の判定、フィボナッチ数列といった小さなプログラムを作り、第 3 章「計算量について学ぶ」で時間計算量の考え方を押さえます。第 4 章は線形探索、二分探索、木構造での探索、第 5 章は選択ソート、挿入ソート、バブルソート、ヒープソート、マージソート、クイックソートを順に扱い、最後に処理速度を比較します。第 6 章はベルマン・フォード法、ダイクストラ法、A* アルゴリズムによる最短経路問題と、文字列探索の力任せ法、Boyer-Moore 法、逆ポーランド記法、ユークリッドの互除法です。版元が扱うアルゴリズムとして挙げる一覧には、幅優先探索と深さ優先探索、番兵、8 クイーン問題、ハノイの塔、ミニマックス法も含まれます。

計算量で比べると見えてくる、手法を使い分ける理由

同じ結果を返すプログラムでも、データが増えたときの手間の増え方は手法によって大きく違います。入力の大きさに対して処理の回数がどの割合で増えるかを表すのが O 記法 で、たとえば先頭から順に調べる線形探索はデータ量に比例して時間が延びますが、並べ替え済みのデータを半分ずつ絞り込む二分探索は、データが倍になっても比較が 1 回増えるだけです。ソートでも、選択ソートや挿入ソートは要素数の 2 乗に比例して時間が延びるのに対し、マージソートやヒープソートはそれより緩やかに増えるため、件数が大きくなるほど差が開きます。

最短経路の手法にも、それぞれが成り立つ条件があります。道路網のように点と辺で表した グラフ の上で、ダイクストラ法は辺の重みが負でないことを前提に効率よく答えを出し、ベルマン・フォード法は負の重みがあっても扱える代わりに手間が増えます。A* アルゴリズムは目的地までの見積もりを使って探索の範囲を絞ります。第 5 章の処理速度の比較と、第 6 章で同じ問題に対する複数の手法を並べた構成は、こうした条件の違いを手元のコードで確かめる材料になります。

アルゴリズムをゼロから学びたい人に向く理由と、次に読む本

版元がおすすめの読者として挙げるのは、アルゴリズムをゼロから学びたい人、Python でプログラミングを学んでいるけれど何から手をつけてよいか分からない人、過去にアルゴリズムを学ぼうとしたものの Python の資料が少なかった人などです。第 1 章で文法から解説するため、Python に触れたばかりの段階でも読み始められます。一方で、アルゴリズムの正しさを数学的に証明する手順や、動的計画法のように目次に挙がっていない手法を学びたい場合は、より体系的な教科書が別に必要です。目的別の選び方は アルゴリズム本ガイド で整理しています。

教科書の擬似コードを読んでも手が動かなかった人や、業務で書いている処理がなぜ遅いのかを計算量の言葉で説明できるようになりたい人にとって、Python で一つずつ書いて確かめられる本書は、アルゴリズムの学習の最初の 1 冊として選びやすい本です。