以下は私が作成した『アルゴリズムイントロダクション 第4版』の輪読資料です。一部、練習問題や章末問題を解いた結果も載せています。

対応する教科書セクションは、第1部序論、§1.1～2.1です。

導入：まえがきと序論

どういう本なのか？

『アルゴリズムイントロダクション 第4版』のまえがきを読んでみると、以下のようなことが書いてある。

「アルゴリズム」という言葉が日常的なものになったという旨の主張がなされているので軽く調べてみよう。Googleでの検索ワードトレンドがわかるサービス Google トレンド で「algorithm」について調べてみた。

以下はその関連キーワードとして挙がった上位5つである。

上位2つの「インスタグラムアルゴリズム」や「YouTube アルゴリズム」というのが目に付く。

2021年の1年間での訪問ユーザー数¹は、

• Instagram：740億人
• YouTube：4080億人 だったらしく、引用にあるような世界になりつつあるのは間違いなさそうだ。

この本は、そうした身の回りの多く存在するアルゴリズムなるものについての本である。

したがって、この本はアルゴリズムの「料理本」として使うことができる。ただ、扱う問題によっては、お決まりのアルゴリズムがないこともある。

そうした場合でも自力で対処できる力を養う本としても使えるようだ。また、アルゴリズムだけでなくそれと付随して紹介されることの多い「データ構造」についても扱う。

なんのために読むのか？

読む理由は端的に、

• 面白そう
• 役に立ちそう

という2点だ。

1つ目は感覚の話で説明のしようがないから置いておくことにして、2つ目の「役に立ちそう」についてもう少しゴニョゴニョと書く。

個人的には、機械学習や深層学習、強化学習は「あきらめの技術」という感じがしている。決まった手続きで解決するのが難しい領域（画像認識や音声認識や言語生成など）に対処するのに機械学習を使うというイメージ。

人々がちゃんと理解している領域は先人が作った手続き的な解決方法（アルゴリズム）を使って解決したい。なぜなら、

• 説明可能性が高い
• 厳密解を出せるのが多い
• 効率が良い
• 学習データがなくて良い

という利点があるからだ。馬鹿げた例かもしれないが、

というお願いをされたときに、「GPUサーバーぶん回して1週間強化学習させて、精度99%の推定器作りました！」って言ったら、ギャグだと思われると思う。

これは極端な例だとしても、すでに先人が解決してきた「普通の問題」のことを広く知っておいたほうが「車輪の再発明」が防げるのは間違いないはず。

再発明を防ぎ、真に解くべき問題に集中できるという意味で研究の役に立ち、もう少し広い意味では Computer Science の基礎（の一部）を学ぶことでエンジニアリング力を上げることの役にも立つ……はず！

余談

試しに強化学習でソーティングエージェント作ってみた。

5個の数の並べ替えくらいなら 60秒程度 (5000エピソード) DQNで学習したエージェントで割と正しい並べ替えができる感じ。

学習曲線はこんな感じ。

一方で、10個の数の並び替えエージェントを新たに学習させて推論させてみると、全然ダメだった。 500秒程度の学習だと状態空間が割と大きいので全然学習できてない。 学習曲線を見てもダメダメなのが分かる。真面目に取り組むなら巨大な状態空間に対してもっと工夫が必要だろうし、 学習時間ももっとかける必要がありそう。

補足

機械学習とアルゴリズムを対立するものとして書いてみたけど、 機械学習もアルゴリズムの一種なので、ほんとは対立関係にはない。

モチベーションの部分をほかの言葉で言い換えるなら、 基礎がおろそかなまま機械学習関係の研究をしてて「マズイ」と感じることが増えてきたので基礎を固めたい、という風になると思う。

第1部の概観

第1部は以下のような構成になっている。この記事で扱うのは太字のところ。

• 第1章：アルゴリズムとそれが現代的コンピュータシステムにおいて占める位置の概観
  • アルゴリズムの定義
  • 例示
  • 高速ハードウェア、GUI、オブジェクト指向、ネットワークと並ぶ重要性の説明
• 第2章：ソーティングアルゴリズム
  • 疑似コードの書き方
  • 挿入ソート
  • マージソート
  • 実行時間の表記法
• 第3章：実行時間の表記法・漸近表記法の厳密な定義
  • よくある漸近表記法の定義
  • 例を用いた適用
  • 5通りの漸近表記法の定義
  • 数学的表記法
• 第4章：分割統治；再帰的アルゴリズムの実行時間を記述するのに有用な漸化式を解く手法
  • 代入法
  • 再帰木
  • マスター法
  • マスター法に関する定理とその証明
• 第5章：確率的解析と乱択アルゴリズム
  • 入力する確率分布と実行時間の関係
  • 乱択アルゴリズム

第1章：計算におけるアルゴリズムの役割

アルゴリズムってそもそもなに？

アルゴリズムは明確に指定された計算問題を解くための道具ともいえる。

計算問題は典型的には以下の要素を指定する。

• 入力形式
• 望まれる出力形式

アルゴリズムは任意のサイズのすべての問題インスタンスに対して、上記の指定された入出力関係を実現する計算手続きである。

例を挙げよう。

数の列を昇順にソートする問題だ。

具体的には、

• 入力：$<31, 41, 59, 26, 41, 58>$ が与えられて、
• 出力：$<26,31,41,41,58,59>$ を返す

となれば、望まれた入出力関係を満たす。

こうした具体的な入力列のことを、ソーティング問題のインスタンスと呼ぶ。一般に問題のインスタンスは、その問題の解を計算するのに必要な（しかも問題の記述で課されたすべての制約を満たす）入力列である。

インスタンスは、ソフトウェア開発での「テストケース」に対応すると思う。

つまり、正当でないアルゴリズムは、あるインスタンスに対して

• 停止しない あるいは
• 誤った答えを出力する

アルゴリズムである。

実は、正当なアルゴリズムだけが役に立つのかというと、必ずしもそうではない。

たとえば、誤り率を制御できる場合には、正当でないアルゴリズムも役に立つ。この本の第31章（整数論的アルゴリズム）では、誤り率を制御できるアルゴリズムの例として大きな素数を求めるアルゴリズムを扱う。

多腕バンディットの最適腕識別問題における「信頼度固定設定（Fixed Confidence）」とかも誤り率を制御できるアルゴリズムの例になると思う。

アルゴリズムが解ける問題

アルゴリズムが実際に応用できる場面の例

• ヒトゲノムプロジェクト
  • 目的：人間のDNAに含まれる遺伝子のすべてを解読すること
  • やること１：人間のDNAを構成する30億個の塩基対の列を決定
  • やること２：情報をデータベースに蓄積
  • やること３：データ解析のためのツール開発
  • 第14章（動的計画法）は、DNA列の類似度を決定する問題を含むこれら生物学的問題のいくつかを解決するための方法を扱う
• インターネット
  • やること１：大量のサイトに対する検索性能の向上
  • やること２：データ転送のための経路発見
  • 第11章（ハッシュ表）と第32章（文字列照合）は特定の情報が存在するページを素早く発見する問題に対する方法を扱う
  • 第22章（単一始点最短経路問題）はデータ転送のための経路発見に役立つ方法を扱う
• EC サイト
  • やること：クレジットカードやパスワードのような個人情報を秘密裏に管理する
  • 第31章（整数論的アルゴリズム）は、公開鍵暗号とデジタル署名などの基本となるアルゴリズムや整数論を扱う
• 資源管理
  • 主体例：石油会社、議員候補、航空会社
  • 目的：
    • 利益を最大化する油井の位置を決めること
    • 限りある予算内で、選挙に勝つ可能性を最大化する宣伝の場所を知ること
    • 法令の範囲内で全てのフライトに対する経費を最小化する乗組員のスケジュールを求めること
  • これらは第29章（線形計画法）でモデル化して解ける問題である

この本では、こうした具体的な応用場面について詳細には扱わないが、これらの問題に関連した基本的な問題とその技法について扱う。

それなら、どういう問題を扱うのか？

自己交差するルートを除外しても、探すルートの数は膨大だ。すべての可能なルートの中から最短のルートをうまく見つけるにはどうすればいいのか。

この本では道路地図を、

• 第6部：グラフアルゴリズム
• 付録第B章：集合など

で紹介するグラフとしてモデル化する。このグラフで頂点から頂点への最短経路を求める問題に換言し、効率よく解く方法を考える。

ほかには、

機械が $n$ 個の部品で構成されているなら、全部で $n!$ 通りの可能な順序がある。階乗は指数よりも速く大きくなるので、全探索をするのは現実的ではない。

この問題はトポロジカルソートの例で、第20章（基本的なグラフアルゴリズム）で扱う。

ほかに、

この問題は第33章（機械学習のアルゴリズム）のクラスタリングアルゴリズムを利用すれば対応できる。

（＋画像認識の機械学習技術も必要だと思う）

ほかに、

多くの圧縮法があるが、

• 文字列の繰り返しに着目する「LZW圧縮法」
• 第15章（貪欲アルゴリズム）では「Huffmanコード法」

を扱う。

ここで列挙したものがすべてではないが、これらアルゴリズム的問題は2つの共通点がある。

効率が良いとは？

2つの観点

アルゴリズムを考えるうえで「効率の良さ」は重要な指標である。効率が良いとはなんだろうか？2つの観点がある。

コンピュータは高速だが無限の速度を持っているわけではない。またメモリも地球上の物質あるいは、宇宙中の物質に限りがある以上無尽蔵ではないし、無料でもない。

したがって、計算時間と計算空間は貴重な限りある資源といえる。ゆえに、時間と空間という資源を効率よく使うアルゴリズムを選ぶ必要がある。

もし仮に、無限の計算速度と無尽蔵のメモリを持ったコンピュータが実現したとして、それでもアルゴリズムを研究する理由が残るだろうか？

実行時間の比較

たとえば、以下の2つのソーティングアルゴリズムを比較する。

普通 $c_1 < c_2$ だが、ある程度 $n$ が大きくなるとその係数の差を相殺し、$\log_2 n$ 対 $n$ となりマージソートが勝つようになる。

アルゴリズムの威力を感じるために、以下の表のような設定で考えてみる。

命令数が違うのは、天才プログラマが書いたプログラムはコンピュータ A の上で機械語でうまく書かれていてオーバーヘッドが少ないからで、平均的プラグラマが書いたほうはコンピュータ B の上であまり効率の良くないコンパイラと高級言語を用いて書かれたものでオーバーヘッドが多いからだ。

この設定で 10,000,000 個の数値をソートするのにかかる時間は、

となる。コンピュータが遅い上にプログラムの効率が良くなくても、コンピュータ B は A よりも 17倍も速く問題を解ける！

これは問題のサイズ $n$ が大きくなればなるほどより顕著な差になっていく。

2024年時点では少なくとも17分おきに1億回以上の検索が行われ、24秒毎に1億個以上の電子メールが送られている。こうした巨大な $n$ に対処できるようなアルゴリズムを考えることは、いかにコンピュータの性能が上がったとしても重要だとわかる。

NP完全問題

時間効率の観点において、妥当な時間で実行できるアルゴリズムが知られていないような問題がある。そうした問題は「NP完全問題」として知られ、第34章で扱う。

NP完全問題に対して効率の良いアルゴリズムは今のところ見つかっていない。そして、効率の良いアルゴリズムが存在しないということが証明されている、というわけでもない。効率の良いアルゴリズムが存在するかどうか誰も知らないという現状だ。

しかし、NP完全問題には以下の面白い性質があることがわかっており、それが一部のコンピュータ科学者や数学者を虜にしている。

Q. そんな厄介な怪物のような問題を知って何になるのか？ →　A. 徒労を避けることができる。

たとえば、以下のような例を考える。

このような仕事を頼まれたとする。これに厳密な最適解を与えるシステムの構築をやるぞ！と意気込んで取り組み始めると、その労力の多くは徒労に終わる。

というのもこの問題は「巡回セールスパーソン問題」として知られるNP完全問題だからだ。この問題を解く効率の良いアルゴリズムは知られていない。

しかし、ある仮定の下では、最短の場合に近い距離を持つルートを与える効率の良いアルゴリズムが存在する。数学的な問題とは違ってこのような現実の仕事への応用の場合、厳密に最適解である必要はない。近似的な最適解で十分のはずだ。このような近似的な解を与える「近似アルゴリズム」については第35章で扱う。

並列化

コンピュータの頭脳であるプロセッサの性能が計算速度を決める。2004年頃まではプロセッサのクロック周波数を上げることで性能向上を図ってきた。

しかし、プロセッサのクロック周波数は頭打ちになっている。

出典：Computer Architecture: A Quantitative Approach 6th Edition

頭打ちになっている原因は、物理的制約によるものだ。

そうしたリスクを避けるために、プロセッサを製造する企業は、1クロックで計算できる量そのものを増やす方向で性能向上を図るようになった。どのように？マルチコア化によって。

マルチコアコンピュータはシングルチップ上の複数の逐次コンピュータとみなすことができる。これはある種の「並列コンピュータ」といえる。

このコンピュータから最大の性能を引き出すためには、並列性を考慮したアルゴリズムを設計する必要があり、それは第26章（並列アルゴリズム）で説明される。

最近では、GPUを使った並列プログラミングも普通のものとなっている。GPUはマルチコアの怪物で、浮動小数点演算を高速に並列して演算することができるプロセッサだ。もともとはゲームなどのグラフィックス処理のために作られたものだが、その並列処理能力の高さからAI分野の研究でよく用いられるようになった。

出典：1. Introduction — CUDA C++ Programming Guide

並列処理が輝く計算例として挙がるのが、行列積や連立方程式の解法であるヤコビ法など。ほかにも独立な反復処理がいっぱいあるような計算の場合は並列計算に向いている。

どうやってGPUを活用するのか？Pytorchを使って torch.nn.DataParallel などで割と簡単に並列処理の性能を引き出せるようになっている。Python に慣れている人にとってはかなりお気楽。

もっとキリキリとGPUを活用したいぞ！という場合は、NVIDIA社が開発した並列コンピューティングプラットフォームであるCUDAで、C言語を拡張した「CUDA C」を使ってプログラムをすることができる。

オンライン処理

この本のほとんどの例では、アルゴリズムが実行を始めるとき、すべての入力が利用可能であることを前提にしている。

しかし実社会での応用上は、入力が絶えずやってきては、すぐに出ていく、というような状況が多い。たとえば、インターネットにおけるトラフィックは、今やってきたパケットがこの先どこに到着するかを知らずに現在の状態に基づいてルーティングしなければならない。

こうしたアルゴリズムについては第27章（オンラインアルゴリズム）で扱う。

「多腕バンディットアルゴリズム」もオンラインアルゴリズムの一種だ。

アルゴリズムとほかの技術

「実行時間の比較」で示した例は、ハードウェアと同様にアルゴリズムが技術であることを示している。

簡単な Web アプリケーションなどではアルゴリズムの中身を明示的に必要としない場合も多いが、大規模なものや凝ったものとなるとアルゴリズムが必要になってくる。

たとえば、旅行計画を手助けする Web サービスを考える。その実現のためには、

• 高速なハードウェア（サーバとクライアントPC・スマートフォン）
• GUI
• 広域ネットワーク
• オブジェクト指向システム

などがかかわってくる。そしてそれに加えて、

• ルートの発見
• 地図の表現
• 番地の補間

などの操作に対してはアルゴリズムが必要になる。

また、以下のようなほかの先端技術、

• 先端的なコンピュータアーキテクチャとチップ製造技術
• 簡単に利用できる GUI
• オブジェクト指向システム
• 統合された Web 技術
• 有線および無線の高速ネットワーク
• 機械学習
• モバイル端末

それ自体の開発にもアルゴリズムが使われている。

練習問題

練習問題 1.1-4

上で述べた最短路問題と巡回セールスパーソン問題の類似点を説明せよ. また, 相違点は何か？

類似点

1. グラフ上の問題: どちらも地点（ノード）と地点間の接続（エッジ）、および移動にかかるコスト（重み）で構成されるグラフを対象とする。
2. 経路探索: グラフ上のノードを結ぶ「経路」を見つけることが目的。
3. コスト最小化: 見つけるべき経路は、その経路に含まれるエッジのコスト（距離、時間など）の合計が最小となるもの。最適化問題の一種。
4. 応用分野: どちらも物流、交通、ネットワーク設計、ロボットの経路計画など、現実世界の様々な分野で応用されている。

相違点

最短路問題とTSPは、グラフ上でコスト最小の経路を探すという点で似ているが、「どのノードを通る必要があるか」と「経路が閉じているか開いているか」という点で根本的に異なる。この違いが、問題の計算複雑性に大きな差（多項式時間 vs NP困難）を生み出している。最短路問題は特定の2点間の効率的な移動を求めるのに対し、TSPは全ての指定地点を効率的に巡回するルートを求める、より複雑な問題と言える。

練習問題 1.2-2

同じコンピュータ上で挿入ソートとマージソートの実装を比較する. サイズ $n$ の入力に対して, 挿入ソートの実行には $8n^2$ ステップかかり, 一方, マージソートの実行には $64n\log_2 n$ ステップかかるとする. 挿入ソートがマージソートに優る $n$ の値を調べよ.

以下の不等式を満たす $n$ の範囲を求めればよい。 $$8n^2<64n\log⁡_2 n$$

解析的に求めることはできないので逐次代入して大小比較して求める。以下のコードで求めた。

import math

def insertion_sort_steps(n):
  """挿入ソートのステップ数を計算する関数"""
  if n <= 0:
      return 0
  return 8 * n**2

def merge_sort_steps(n):
  """マージソートのステップ数を計算する関数"""
  # n=1 の場合は log2(1)=0 なので 0 ステップとする
  if n <= 1:
    return 0
  # n>1 の場合のみ計算
  return 64 * n * math.log2(n)

def find_n_values_revised():
  """挿入ソートがマージソートに優るnの値を調べる関数"""
  n_values = []
  # n=1 では挿入ソートは優位ではない (8 > 0)

  # n=2 から探索を開始
  n = 2
  while True:
    insertion_steps = insertion_sort_steps(n)
    merge_steps = merge_sort_steps(n)

    if insertion_steps < merge_steps:
      n_values.append(n)
      n += 1
    else:
      # 条件を満たさなくなったらループを終了
      break
  return n_values

if __name__ == "__main__":
  n_superior_values = find_n_values_revised() 

  print("挿入ソートがマージソートに優るnの値:")
  if not n_superior_values:
    print("該当するnの値はありません")
  else:
    # 結果をリストで表示
    print(n_superior_values)
    # 結果を範囲で表示
    if len(n_superior_values) > 1 and all(n_superior_values[i] == n_superior_values[0] + i for i in range(len(n_superior_values))):
        print(f"つまり、{n_superior_values[0]} から {n_superior_values[-1]} までの整数")

これを実行すると、挿入ソートがマージソートに優る $n$ の範囲は 2 から 43 までとわかる。

練習問題 1.2-3

同じコンピュータ上で, 実行時間が $100n^2$ のアルゴリズムが, 実行時間が $2^n$ のアルゴリズムより高速に実行できる最小の $n$ の値を求めよ.

以下の不等式を満たす最小の整数 $n\geq1$ を見つければよい。 $$100n^2<2^n$$

これも大した $n$ の大きさにはならないので順番に試して調べる。

import math

def algorithm_a_cost(n):
  """アルゴリズムAの実行時間 (100n^2) を計算する関数"""
  if n < 0:
    return float('inf')
  return 100 * (n**2)

def algorithm_b_cost(n):
  """アルゴリズムBの実行時間 (2^n) を計算する関数"""
  if n < 0:
    return float('inf')
  try:
    return 2**n
  except OverflowError:
    # 念のため、非常に大きなnに対するエラー処理
    print(f"警告: n={n} で 2^n の計算中にオーバーフローの可能性")
    return float('inf')

def find_min_n_faster():
  """100n^2 < 2^n を満たす最小の正の整数nを見つける関数"""
  n = 1
  while True:
    cost_a = algorithm_a_cost(n)
    cost_b = algorithm_b_cost(n)

    print(f"n = {n}: Cost A (100*n^2) = {cost_a}, Cost B (2^n) = {cost_b}")

    # アルゴリズムAの方が高速 (コストが小さい) かどうかをチェック
    if cost_a < cost_b:
      print(f"-> n={n} で 100n^2 < 2^n が初めて成り立ちました。")
      return n

    # 次のnを試す
    n += 1

# --- メインの実行部分 ---
if __name__ == "__main__":
  print("100n^2 < 2^n を満たす最小の整数 n を探します...")
  min_n = find_min_n_faster()

  if min_n is not None:
    print(f"\n結論: 実行時間が 100n^2 のアルゴリズムが 2^n のアルゴリズムより高速になる最小の整数 n は {min_n} です。")
  else:
    print("\n条件を満たす n は見つかりませんでした（または探索範囲を超えました）。")

実行時間が $100n^2$ のアルゴリズムが $2^n$ のアルゴリズムより高速になる最小の整数 $n$ は 15 と求まる。

章末問題

章末問題 1-1 実行時間の比較

以下の表の各関数 $f(n)$ と時間 $t$ に対して, アルゴリズムが問題を解くのに $f(n)$ マイクロ秒かかるとき, $t$ 時間で解くことができる最大の問題サイズ $n$ を求めよ.

	1秒	1分	1時間	1日	1ヶ月	1年	1世紀
$\log_2 n$
$\sqrt{n}$
$n$
$n\log_2 n$
$n^2$
$n^3$
$2^n$
$n!$

• 1ヶ月＝31日
• 1年＝365日
• 1世紀＝365 × 100 + 25 = 36525日 として計算する。

$f(n)$ マイクロ秒 = $f(n) * 10^{−6}$ 秒なので、 $$f(n) \leq t \times 10^6$$ を満たす最大の $n$ を求めればよい。

$n\log_2 n$ と $n!$ 以外は明示的に $$n \leq \cdots$$ の形で表せるので即座に求まる。ただ、$\log_2 n$ は桁が大きすぎて Python だと扱いきれないので、桁数だけ求めた。

$n\log_2 n$ と $n!$ は上記のような式にできないので、二分探索を使って数値的に求めた。

追記（2025/4/15）

桁でっけぇ～。

組み合わせ爆発のヤバさを感じられる動画としてこういう有名なのもありますね。

第2章：さあ、始めよう

挿入ソート

挿入ソートは、ソーティング問題を解く単純なアルゴリズムである。

ソートされる数値をキーとも呼ぶ。入力は $n$ 個の要素を持つ配列の形で与えられる。数値をソートしたい場合、それらの数値は付属データと呼ばれるほかのデータに付随するキーであることが多い。キーと付属データがレコードを構成する。

たとえば、年齢、GPA、履修科目数など多くの付随するデータを持つ学生のレコードからなるスプレッドシートを考えてみる。

年齢をキーにして並べ替えると、

こんなふうに付随するデータも一緒に移動する。

この本ではアルゴリズムを記述するのに、疑似コードを用いる。疑似コードと実用コードとの大きな相違点は、疑似コードは以下のソフトウェア工学的な観点に無関心で、アルゴリズムの本質を伝えるためのものになっているということだ。

さて、挿入ソートの話を始める。

挿入ソートは、トランプで手札をソートするときに多くの人が実行しているソーティングアルゴリズムである。山札から新しくとってきたカードをすでにソート済みの手札の正しい位置に挿入する。すると常に手元にはソート済みのカードがあることになる。これは、少数の要素を効率よくソートできるのが利点だ。

挿入ソートを UNO でしている動画

https://youtu.be/Dxvk2iTdzwY

アルゴリズムっぽく言うなら、

1. まず左手を空にする
2. 山札から最初のカードをとって左手に持つ
3. 次に右手で山から一枚カードを取る
4. そのカードを左手のカード群の右から順に大小比較して、挿入すべき位置を見つける
5. 挿入すべき位置にとってきたカードを置く
6. 3から5を繰り返す

みたいな感じだ。

これを疑似コードにすると以下のようになる。

INSERTION-SORT(A,n)

1.for i = 2 to n
2.    key = A[i]
3.    // A[i] をソート済みの部分配列 A[1:i-1] に挿入する
4.    j = i - 1
5.    while j > 0 かつ A[j] > key
6.        A[j+1] = A[j]
7.        j = j - 1
8.    A[j+1] = key

ソートする値を格納する配列 $A$ とソートする値の個数 $n$ を引数としてとる。$A[1:n]$ は配列 $A$ の場所 $A[1]$ から $A[n]$ の間に格納されている値の配列のことを指す。

INSERTION-SORT が終了したとき、配列 $A[1:n]$ には元の複数の値がソートされた順序で格納されている。

出典：『アルゴリズムイントロダクション 第4版』図2.2

各箱の上にある数が対応する配列のインデックスであり、箱の中の数がその場所に格納されている値である。また図の(a)~(f)は以下に対応する。

• (a)~(e)：疑似コードの第1行～8行の for ループ
• (f)：最終的に得られるソート済み配列

各繰り返しでは、青い箱に $A[i]$ から取り出したキーを保持し、そのキーをその左側に置かれたオレンジの網掛けの箱に保持されている値のそれぞれと第5行の判定文で比較する。右側に向かっている矢印は値が第6行で一つ右に移されることを示し、左側に向かっている矢印は第8行でキーが移動する場所を示す。

ループ不変式

Note | ループ不変式とは

ループの各反復の開始時（または終了時）において、常に真（成り立つ）と期待される条件や性質のこと

これを踏まえて、挿入ソートの部分列が持つ性質を定式化すると以下のようになる。

アルゴリズムの正当性を理解するためにループ不変式を利用する。ループ不変式を使うには、ループ不変式に対する次の3つの性質を示す必要がある。

ループ不変式の証明は、数学的帰納法の形をしている。ある性質が成り立つことを示すために、基底段階と帰納段階を証明する。

なぜループ不変式で定式化するのか？

• 正当性の証明: 上記の3つの性質を示すことで、ループが何回繰り返されようとも、最終的に正しい結果を導くことを数学的に（あるいは論理的に）証明できる。
• アルゴリズムの理解: ループ不変式を考えることで、ループが何をしているのか、どのようにして最終的な目標に向かっているのかを深く理解する助けになる。
• アルゴリズムの設計: 正しいループ不変式を念頭に置いてアルゴリズムを設計することで、バグの少ない、目的を達成するコードを書きやすくなる。
• デバッグ: ループが期待通りに動かない場合、ループ不変式がどの段階（初期、維持、終了）で破綻しているかを調べることで、バグの原因特定に役立つ。

疑似コードのお約束

この本で用いる疑似コードについての約束事がいくつかあるので列挙する。

• 字下げはブロック構造を示す。begin, end 文や中括弧のようなブロック構造を示す指示子の代わりに字下げを用いる。
• ループ構造 while, for, repeat-until と条件分岐 if-else の解釈は C, C++, Java, Python, JavaScript とほとんど同じである。C++, Java と違う点は、本書のループインデックスはループを出た後も値を持ち続ける点である。
• for ループで用いるキーワード to はループインデックスの値を繰り返しのたびに 1 ずつ増加させるときに用いる。キーワード downto は 1 ずつ減少させるときに用いる。ループインデックスの値を 1 以外の値で変化させるときは by の後に記述することによってその変化量を示す。
• 記号 “//” は注釈
• グローバル変数は明示することなしには用いない。
• 配列要素は角括弧でくくったものを指定することでアクセスする。この本ではインデックスは 1 始まりである。記号 “:” は部分配列を表す。また、この記法は配列の限界を表すのにも用いる。
• 複合データを属性から構成されるオブジェクトとして組織する。そして、多くのオブジェクト指向言語に取り入れられている構文を用いて特定の属性にアクセスする。たとえば、オブジェクト $x$ が属性 $f$ を持つなら、この属性は $x.f$ とあらわす。
• 配列やオブジェクトを表す変数は、その配列やオブジェクトを表すデータへのポインタである。$y=x$ を実行すると、オブジェクト $x$ のすべての属性 $f$ について $y.f$ は $x.f$ と等しくなる。さらに、$x.f=3$ を実行すると、そのあとは $x.f=3$ が成立するばかりでなく $y.f=3$ も成立する。つまり、代入 $y=x$ の結果、$y$ と $x$ は同じオブジェクトを指すようになる。
• 属性を表現する表記法を「直列につなぐ」ことができる。たとえば、属性 $f$ が、属性 $g$ を持つあるタイプのオブジェクトへのポインタであるとする。このとき、$x.f.g$ は暗に $(x.f).g$ という意味である。つまり、代入 $y=x.f$ が実行されたとすると、$x.f.g$ は $y.g$ と等しいということである。
• ポインタがどのオブジェクトも指さないことがある。この時、ポインタは特別な値 NIL をとる。
• 引数（パラメータ）は手続きに値で引き渡される。呼び出された手続はその引数の自分用のコピーを受け取り、呼び出された手続が、ある値をその引数に代入してもその変化は呼び出した手続きからは見えない。オブジェクトを引数として渡すと、そのオブジェクトが表すデータへのポインタだけがコピーされ、そのオブジェクトの属性はコピーされない。たとえば、呼び出された手続の引数を $x$ とするとき、呼び出された手続き内の代入文 $x=y$ は呼び出した手続きから見えないが、代入文 $x.f=3$ は見える。同様に、配列もポインタで渡す。したがって、配列全体ではなくその配列を指すポインタだけが渡され、配列の個々の要素の変化は、呼び出した手続きから見える。
• return 命令は呼び出した手続きが呼び出しを実行した場所に制御を直ちに戻す。大半の return 命令には呼び出した手続きに戻す値が定められている。疑似コードでは 1つの return 命令で複数の値を戻すことができる。
• ブール演算子 “かつ（and）” と “または（or）” はショートサーキット演算子である。つまり、式 “$x$ かつ $y$” の評価では $x$ の評価をまず行う。仮に $x$ が FALSE ならばこの式全体が TRUE になることはないので $y$ を評価する必要がない。一方で、$x$ が TRUE なら式全体の値を確定させるために $y$ の値も評価しなければならない。「or」も同様である。ショートサーキット演算子を使うことで、「$x\neq NIL$ かつ $x.f=y$ 」といった式を $x$ が NIL のときの $x.f$ の評価の仕方を気にすることなく書くことができる。
• キーワード error は、正しくない条件の下で手続きが呼び出されたためにエラーが発生したことを示し、この手続きは直ちに停止する。呼び出した手続きがこのエラーを取り扱う責任があるので、取られる処置を記述することはない。

練習問題

練習問題 2.1-1

図2.2を手本にして、数列 $<31,41,59,26,41,58>$ を含む配列上での INSERTION-SORT の動作を説明せよ。

練習問題 2.1-3

INSERTION-SORT 手続きは単調増加順でソートする。これを書き換えて単調減少順でソートするようにせよ。

INSERTION-SORT-DECREASING(A, n)

1. for i = 2 to n
2.     key = A[i]
3.     // A[i] を単調減少順でソート済みの部分配列 A[1:i-1] に挿入する
4.     j = i - 1
5.     while j > 0 かつ A[j] < key   // 変更点: key より小さい要素を右に動かす
6.         A[j+1] = A[j]
7.         j = j - 1
8.     A[j+1] = key

練習問題 2.1-4

以下の探索問題を考えよう。

• 入力：配列 $A[1:n]$ に格納された $n$ 個の数列 $<a_1,a_2,\ldots,a_n>$ と、ある値 $x$
• 出力：$x=A[i]$ となるインデックス $i$、または $x$ が $A$ の中に存在しないときは特別な値 NIL 線形探索の疑似コードを書け。線形探索は $x$ を探しながら配列を最初から最後まで順に走査するアルゴリズムである。

LINEAR-SEARCH(A, x)

1. for i = 1 to n
2.     if A[i] == x
3.         return i
4. return NIL

練習問題 2.1-5

$n$ 要素配列 $A[0:n-1]$ と $B[0:n-1]$ に蓄えられた2つの $n$ ビットの2進数の和を求める問題を考える。ここで、配列の各要素は 0 または 1 であり、$a=\sum_{i=0}^{n-1}A[i]\cdot 2^i$, $\sum_{i=0}^{n-1}B[i]\cdot 2^i$ である。この2つの整数の和 $c=a+b$ を2進数として $(n+1)$ 要素配列 $C[0:n]$ に蓄える。ここで、$c=\sum_{i=0}^{n}C[i]\cdot 2^i$ である。入力として大きさ $n$ の配列 $A$ と $B$ をとり、その和を格納する配列 $C$ を返す手続き ADD-BINARY-INTEGERS を記せ。

ADD-BINARY-INTEGERS(A, B)

1. C[0:n] を作成
2. carry = 0
3. for i = 1 to n-1
4.     sum = A[i] + B[i] + carry
5.     C[i] = sum % 2
6.     carry = floor(sum / 2)
7. C[n] = carry
8. return C