アルゴリズム設計マニュアル

引用

Skiena, S. S. (2020). The Algorithm Design Manual (3rd ed.). Springer.

章の要約

本書は2部22章からなり、参考文献と索引が続く。本文のページ番号は全793ページのうち約718ページまで付いている。第1部「実践的アルゴリズム設計」（第1～13章）は、アルゴリズムを設計し解析する方法を教える。第2部「アルゴリズムのヒッチハイク・ガイド」（第14～22章）について、出版社は、実際によく現れる75の問題を収めた、拾い読みするためのカタログであり、実装や文献への案内も付くと説明している。Skiena 自身のページは、本書を解析よりも設計に重きを置くものと紹介している。

第1～2章：アルゴリズム設計入門、アルゴリズム解析

冒頭の2章は、アルゴリズムの設計（第1章）と解析（第2章）を導入する。解析の章は約40ページである。出版社は本書の文体を「定理・証明を並べない」（no theorem-proof）直観的なものと説明しており、解析もその調子で述べられる。

第3～4章：データ構造、整列

データ構造と整列には第1部の中に独立した章があり、本書はこれらを単に前提としているわけではない。ただし、これらの章がどの程度の予備知識を想定しているかは、目次からは分からない。

第5～6章：分割統治法、ハッシュ法と乱択アルゴリズム

技法を扱う2章。出版社は、この版で分割統治法、ハッシュ法、乱択アルゴリズムの扱いを新設または拡充したとしており、これらの章の主題と一致する。

第7～8章：グラフの走査、重み付きグラフのアルゴリズム

2章合わせて約85ページで、走査から重み付き問題へと進む。グラフは第2部でも、多項式時間で解ける問題とNP困難な問題の別々の章で再び現れるため、本文ページの約4分の1がグラフに関わる。

第9～10章：組合せ探索、動的計画法

第9章は組合せ探索を、第10章は動的計画法を扱う。第10章は約47ページで、第1部で最も長い。

第11～13章：NP完全性、困難な問題への対処、アルゴリズムの設計法

第1部は難解性に関する一連の章で閉じる。NP完全性が何を意味するかを述べ、その意味で困難な問題への対処法を扱う。出版社は、近似アルゴリズムを新設または拡充された話題の一つに挙げているが、どの章が担当するかは述べていない。この部の最終章は「アルゴリズムの設計法」と題され、わずか6ページである。

第14章：アルゴリズム問題のカタログ

第2部への2ページの入口。第2部は435ページから「ヒッチハイク・ガイド」として始まる。出版社によれば、このカタログは、各問題について読者を解決への正しい道へ導く。

第15～19章：データ構造、数値問題、組合せ問題、グラフ問題（多項式時間）、グラフ問題（NP困難）

問題の種類ごとに整理されたカタログ項目の章。第15章はデータ構造に戻り、今度はカタログの中で扱う。第18章と第19章はグラフ問題を多項式時間で解けるものとNP困難なものに分ける。

第20～22章：計算幾何学、集合と文字列の問題、アルゴリズムの資源

カタログは、幾何学（カタログの章で最長の約56ページ）、集合と文字列、そして短い最終章「アルゴリズムの資源」で終わる。出版社は、C、C++、Java による実装へのリンクを提供しているとしている。

主要概念

第1部：実践的アルゴリズム設計（第1～13章）

• アルゴリズム解析：設計の効率を判断すること。実用の道具として扱われる。
• 分割統治法、ハッシュ法、乱択：それぞれ独立した章で扱われる技法。
• グラフの走査と重み付きグラフ：グラフ分野の中心。
• 動的計画法と組合せ探索：最適化問題と全探索型の問題に対する方法。
• NP完全性：効率的な厳密解法がおそらく存在しない問題を見分けるための用語。

第2部：アルゴリズムのヒッチハイク・ガイド（第14～22章）

• 問題カタログ：問題の種類ごとに項目を整理し、アルゴリズムからではなく問題から調べられるようにしたもの。
• 問題の分類：データ構造、数値、組合せ、グラフ（多項式時間とNP困難）、幾何、集合と文字列の各問題。カタログの章はこの分け方に従う。

批判的分析

長所

• 問題の見分け方を軸にした構成。 カタログの部では、問題の形から出発できる。これは、技法ごとに進む多くのアルゴリズム教科書とは異なる入口である。Skiena のサイトには、アルゴリズム・リポジトリとプログラムの一覧もある。
• 読みやすさへの配慮。 出版社は、「定理・証明を並べない」文体、強調された「持ち帰るべき教訓」（take-home lessons）、応用での「戦記」（war stories）を特色に挙げている。
• 練習問題が豊富。 演習には就職面接の問題が含まれ、新版では LeetCode や HackerRank 由来のものを含め100問以上が追加された。著者のサイトには、解答集のウィキ、講義ノート、講義動画へのリンクがある。
• 困難な問題に正面から取り組む。 NP完全性、困難な問題への対処、NP困難なグラフ問題の独立した章があり、効率的なアルゴリズムが期待できないときにどうするかが学べる。

短所

• 証明は意図的に最小限。 正しさや実行時間の証明を丁寧に追いたい読者は、より形式的な教科書を併用する必要がある。
• コードはC言語。 出版社によれば、多くのアルゴリズムはCのコードで示される。ほかの言語で作業する読者は、自分で翻訳するか、実装へのリンクに頼ることになる。
• 半分は参照用。 出版社は、第2部を拾い読みと参照のためのものと説明している。最初から最後まで通して読むと、それは一連の授業ではなくカタログである。

コースにおける位置づけ

このコースの中で、Skiena の本は平易な入門書と厳密な教科書の中間に位置する。Cormen の Algorithms Unlocked は数学を抑えた短い入門書で、Roughgarden の Algorithms Illuminated は無料の講義動画が付いた対話的な4部構成の解説書である。どちらを先に読んでもよい。Cormen らの Introduction to Algorithms は、厳密な説明と擬似コードで書かれた包括的な教科書で、証明が必要になったときの自然な併読書である。

第11～12章と第19章の困難な問題の部分については、専門書がさらに先へ進める。Vazirani の Approximation Algorithms と Williamson と Shmoys の The Design of Approximation Algorithms は近似を大きく掘り下げ、Mitzenmacher と Upfal の Probability and Computing は乱択アルゴリズムへの上級の道筋である。

本書の使い方

プログラムが書け、基本的なデータ構造に触れたことのある学生と、技術面接の準備をする実務者に向いている。後者は出版社が用途として挙げている。また、直面している問題がどの種類のものかを見極めたい人にも役立つ。

実践的な進め方：

• 中核（第1部）： 内容に馴染みがあれば第1～4章は手早く進める。第5～10章は技法の主要な蓄えとして順に読む。第11～12章は難解性のために、第13章はこの部を締めくくる短い設計の章として読む。
• 参照（第2部）： 入口の章を読んだら、具体的な問題が現れたときにカタログを引く。章を順に読み進めるのではなく、実装やさらなる文献への案内をたどる。
• 練習： 面接形式のものも含めて演習に取り組み、著者のサイトにある解答集ウィキと講義動画で確かめる。
• 併用： 証明のために Introduction to Algorithms のような厳密な教科書を手元に置き、いくつかのアルゴリズムは自分の言語で実装して、C のコードと比べる。