Pythonによるアルゴリズム設計

神野健哉東京都市大教授博士（工学）著

60～70年前に生まれた有名なアルゴリズムを，Pythonで実装し，内容を解説する。

ジャンル

発行年月日: 2022/09/26

判型: B5

ページ数: 160ページ

ISBN: 978-4-339-02930-7

在庫あり

2営業日以内に出荷致します。

定価

2,860円(本体2,600円+税)

カートに入れる

購入案内

内容紹介
まえがき
目次
レビュー
著者紹介
広告掲載情報

近年プログラミング言語の中でもPythonが非常に注目を集めています。Pythonはオブジェクト指向プログラミング言語として分類できます。一般にオブジェクト指向プログラミング言語はプログラミング初心者には学習が難しいと言われますが、Pythonはインタープリタ言語であるのでどのような動作をするのかを確かめながらプログラミングができる利点があります。一方、Pythonでは様々な手続きがオブジェクトとして実装されていますが、その処理内容を理解することはプログラムの動作を正しく理解する上で非常に重要です。このような背景から本書ではPythonで有名なアルゴリズムを実装し、その実際の計算時間を測定して、各アルゴリズムの仕組みを理解した上で、処理時間が処理対象のデータ数や処理するための各アルゴリズムによってどのように変化するのかを確認できるようになることを目指しています。

本書はまずはPythonの制御構造などの基本的なことを学んだ人が、様々な目的達成のためのプログラムを作成できるようになるためにアルゴリズムを学び、自身でプログラムを作れるようになることを目指しています。そのために出来るだけ各アルゴリズムを適用させるための例題ではデータ数を設定することで自動的に様々な問題を生成できるようにし、問題を構成するデータ数とアルゴリズムに応じて、処理時間がどのように変化するのかを測定することができるようにしています。

アルゴリズムという言葉はアル・フワーリズミー（al-Khuwarizmi）が基になったとされる。アル・フワーリズミーは代数学の祖であり，彼の著書の冒頭にAlgoritmi dicti（アル・フワーリズミーに曰く）という一節があり，これがアルゴリズム（algorithm）の語源になったといわれている。

アルゴリズムは日本語では「算法」と訳され，ある問題を解くための手順や計算方法のことを指す。この手順に曖昧さがなく示されていれば，必要な時間はともかくとして誰にでも必ず問題を解くことができ，同じ答えに行き着くことができる。この性質はまさにコンピュータプログラムに必要なものであり，与えられた問題を解くための正しい手順を曖昧さがないプログラムとして記述することができれば，コンピュータは与えられた問題に対して正しく答えを出すことができる。コンピュータの命令一つひとつはコンピュータ自身に計算を指示するものであり，これをアルゴリズムに従って正しい順序で記述することでプログラムは正しく動作する。したがって正しく動くプログラムを作るためには，曖昧さのないアルゴリズムをまずは記述する必要がある。

また同じ問題を解くアルゴリズムは複数存在する場合があり，さらには同じアルゴリズムであっても，コンピュータに対する命令をどのような順で与えるかによって計算効率が変化する。プログラムは正確に，かつできるだけ高速に計算できることが重要である。コンピュータのハードウェアも日々革新が進んでおり，同じ計算の速度は非常に速くなっているが，アルゴリズムを見直すことで，ハードウェアの進展よりもはるかに速く計算結果が得られるようになることは多い。このためアルゴリズムはコンピュータプログラムで最も重要なものである。

本書では1950年代から1960年代に生まれた非常に有名なアルゴリズムを，近年非常によく用いられるようになったプログラミング言語「Python」で実装し，内容を解説する。Pythonはオブジェクト指向型インタープリタ言語である。インタープリタ言語は他のコンパイラ型言語と呼ばれるプログラミング言語よりも実行速度が劣る。しかしながらコンパイラ型言語と比較して非常に容易にプログラムを試し，修正することが可能である。このため最初にアルゴリズムを実際に動作させながら学ぶことに非常に適したコンピュータ言語であるといえる。また，アルゴリズムはその計算手順だけでなく，問題を解決するためのデータをどのような形式で扱うのかが非常に重要である。Pythonでは従来のコンピュータ言語と比較してさまざまな形式のデータ構造を使用することができ，これらのデータ構造を使用することで，従来のプログラムよりも簡潔に内容を記述することができる。

本書では，ある目的を解決するアルゴリズムをできるだけ複数紹介するようにした。これは冒頭で述べたように，同じ目的で同じハードウェアを使用しても，その処理速度がアルゴリズムによって大きく異なることを感じてもらうためである。特に近年，ビッグデータに注目が集まり，非常に大規模なデータを取り扱うようになった。そのような際にはアルゴリズムの良し悪しが処理時間に大きく影響を与える。各章の章末問題では処理するデータ数を極力変えられるような問題を用意し，さまざまなアルゴリズムが，問題の大きさによって処理速度がどのように変化するのかを実際に体感できるようにした。

アルゴリズムを理解するためにはまずはその概念を理解し，つぎにそれをどのように実装するのかを考えることが重要である。最初は本書に掲載しているプログラムを「写経」し，それらを改変していくことがプログラムを作成する能力のために必要である。これらの基本となるアルゴリズムを基に，機械学習などさまざまな応用につながることも意識してほしい。

本書は，東京都市大学情報工学部知能情報工学科で1年生に開講している専門科目「アルゴリズム設計」での講義を基に執筆している。全14章で構成されており14回の講義に対応する。本書が一人でも多くの人の「アルゴリズム」の理解につながることを願っている。

2022年8月
神野健哉

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　ミニマックス法の実装
章末問題

引用・参考文献
章末問題解答
索引

読者モニターレビュー【 miya 様　（ご専門：プログラミング教育）】

高校で情報Ⅰが必修となり、のち大学入試科目になること、そして2023年4月から基本情報技術者の試験から言語が消えてアルゴリズム重視に変更になることを考えると、教材探しに苦戦している人はとても多いと考えられる。
アルゴリズムは、フローチャート（今どきフローチャート？と思ったのは事実）だけで理解できないので、やはりPythonなどを使った実習で動作確認しないといけない。
取り上げられているアルゴリズムは「王道」のものが中心で、Pythonだとライブラリで実装されているためにわざわざ自分で手を動かすことはないのだが、だからこそ自分で考えて実装（と失敗）をしてみるべきものである。

読者モニターレビュー【そら様　（ご専門：ソフトウェアエンジニア）】

全体に対する印象
東京都市大学の講義を基に作成された１冊ということで、講義単位くらいのちょうど良い章立てが良かったです。学部生やエンジニア初心者の方でアルゴリズムについてあまりよく知らない読者向けに書かれていると思います。情報処理の一部問題の資格対策になる可能性もあると感じました。

理解の手助けになったポイント
各アルゴリズムの説明で、フローチャート、擬似コード、ノードとエッジ（グラフの場合）、リストの箱など複数の方法で解説されていたのが印象的でした。Pythonの実際のコードも書かれているのでわかりやすいですが、コードの前に具体的な数字を用いて初期状態からの変遷を視覚的に追えるので、独学の際にも重宝する参考書だと感じました。アルゴリズムだけでなく関連用語も丁寧に定義の説明があるので、他の本を参照することなく１冊で理解が完結する点もおすすめです。

神野健哉（ジンノケンヤ）

1996年法政大学大学院工学研究科電気工学専攻博士後期課程修了
博士（工学）（法政大学）
電子情報通信学会フェロー

現在、東京都市大学情報工学部知能情報工学科教授
法政大学兼任講師、東京理科大学非常勤講師
「アルゴリズム設計」「オブジェクト指向開発」「機械学習」「データサイエンス応用」「機械学習特論」「線形システム」などの科目を担当。

＜研究テーマ＞
・機械学習
・メタヒューリスティックス最適化
・非線形力学系解析