Algorithms Unlocked（アルゴリズム入門）

引用

Cormen, T. H. (2013). Algorithms Unlocked. MIT Press.

章の要約

Algorithms Unlocked は短い本で（約236ページ、図書館の書誌ではxiii + 222ページ）、10章のあとに参考文献と索引が続く。出版社は本書を、Introduction to Algorithms の共著者が書いた、専門家でない読者向けの手引きとして紹介し、アルゴリズムによってコンピュータがどのように問題を解くのかを「数学を抑えて」説明するとしている。アルゴリズムは疑似コードで示され、各章は探索とソートからグラフ、文字列、暗号、圧縮を経て、効率的な解き方を誰も知らない問題へと進む。

第1章：アルゴリズムとは何か、なぜ気にかけるべきなのか

コンピュータのアルゴリズムとは何か、そして読者がなぜそれに関心をもつべきかを扱う導入の章である。I Programmer に掲載されたMike Jamesの書評は、この章は平易な英語で始まるが、最初の数ページのうちにnの平方根のような代数が現れると指摘している。

第2章：コンピュータのアルゴリズムをどう記述し評価するか

アルゴリズムを疑似コード（配列、ループ、再帰）でどう書くか、そしてビッグO風の記法を含めてその実行時間をどう解析するかを扱う。同じ書評は、ここでループ不変条件と再帰が導入されることを指摘しており、それが本書の水準を示している。

第3章：ソートと探索のアルゴリズム

線形探索と二分探索から、標準的な比較ソートまでを扱う。Google Booksの書誌にある用語一覧には選択ソート、挿入ソート、マージソート、クイックソートが含まれ、Jamesはこの章を、探索とソートの理論についてすべてのプログラマーが知っておくべきことだと述べている。

第4章：ソートの下界とそれを破る方法

比較によるソートがなぜある下界を超えられないのか、そして計数ソートのようにキーを比較しないソートがどのようにそれを回避するのかを扱う。

第5章：有向非巡回グラフ

タスク間の依存関係やネットワークのモデルとしてのグラフを、有向非巡回グラフから扱う。出版社は、グラフがモデル化するものの例として道路網、タスクの依存関係、金融上の関係を挙げている。

第6章：最短経路

最短経路アルゴリズムを扱う。Jamesによれば、ダイクストラ法、ベルマン–フォード法、フロイド–ワーシャル法が扱われ、彼はこの章を、行列とやや長いプログラムを含む数学的な章だと述べている。Google Booksの用語一覧にある負の重みの閉路や優先度付きキューといった語も、同じ内容を示している。

第7章：文字列のアルゴリズム

DNAを動機とする文字列の問題で、最長共通部分列や、ある文字列を別の文字列に変換する問題を含む。

第8章：暗号の基礎

暗号の背後にある基本原理を扱う。書評はRSAと乱数生成に触れており、Google Booksの用語一覧には平文、暗号文、素数が含まれる。

第9章：データ圧縮

圧縮の基礎を扱う。書評によれば、ハフマン符号化から始まり、一般的な圧縮ツールの基礎であるLZWへと進む。

第10章：難しい？問題

巡回セールスマン問題、P対NP、NP完全性、NP困難性、決定不能性を扱い、3-CNF充足可能性、ハミルトン閉路、kクリークといった問題の間の多項式時間帰着も取り上げる。書評者はこれを最も理論的な章と呼んでいる。

主要概念

第1〜4章：記述、解析、ソート

• アルゴリズム：入力を受け取って正しい出力を生み出す正確な手順で、正しさと実行時間によって評価される。
• 疑似コードとループ不変条件：特定の言語によらずにアルゴリズムを述べる方法と、その正しさを論じるための道具。
• 実行時間の解析：入力の大きさに応じて操作の回数がどう増えるか。
• ソートの下界：比較によるソートの限界と、計数ソートのように比較を避けるソート。

第5〜7章：グラフと文字列

• 有向非巡回グラフ：閉路のないグラフで、タスク間の依存関係をモデル化する。
• 最短経路：重み付きグラフの経路を求めるダイクストラ法、ベルマン–フォード法、フロイド–ワーシャル法。
• 最長共通部分列：部分問題の答えを積み上げて解く文字列の問題。

第8〜10章：秘密、圧縮、困難性

• 公開鍵暗号：RSAのように数論に基づく暗号化。
• ハフマン符号化とLZW：可変長の符号による圧縮と、繰り返される文字列の辞書による圧縮。
• NP完全性と帰着：ある種の問題に効率的なアルゴリズムがないように見える理由と、ある問題が別の問題と同じくらい難しいことを示す方法。

批判的分析

長所

• 小さな本で広く見渡す。 短い10章で、アルゴリズムの講義の中核（ソート、グラフアルゴリズム、NP完全性）を扱い、さらに文字列処理、暗号、データ圧縮の章を加えているので、読者はアルゴリズムがソートをはるかに超えて広がっていることを知ることができる。
• 専門家が初心者のために書いた本。 著者は Introduction to Algorithms の共著者であり、出版社が引用する推薦文は、本書を深さを犠牲にせずに読みやすいと評している。
• 物語ではなく本物のアルゴリズム。 Jamesは、本書が実際のアルゴリズムを疑似コードで示し、実行時間の解析も行っているので、一般向けの科学読み物以上のことを教えてくれると評価し、細部についていける読者にとっては「本当によい読み物」だと述べている。

短所

• 水準の混在。 Jamesの主な批判は、文章はまったくの初心者向けに書かれている一方で、紙面には代数、疑似コード、ループ不変条件、解析が多く含まれているという点である。最もやさしい説明を必要とする読者には数学が障壁となり、数学を扱える読者には語り口が単純すぎると感じられるかもしれない。
• 演習帳ではない。 出版社の説明にも書評にも演習問題への言及はなく、目次にも見当たらない。問題を解きながら学ぶ読者には、もう一冊の本が必要である。
• 疑似コードのみ。 書評が指摘するように本書は疑似コードに徹しているので、読者はアルゴリズムを実際の言語に自分で書き換える必要がある。

コースにおける位置づけ

本書はこのコースで最もやさしい一冊であり、本格的な教科書の前の予習にあたる。Roughgardenの Algorithms Illuminated が自然な次の一歩である。著者のオンライン講座に基づく本格的な教科書で、動画、クイズ、問題、プログラミング課題を備え、同じ範囲をはるかに深く扱う。Skienaの The Algorithm Design Manual は、現実の問題に対してアルゴリズムを選ぶための実践的な手引きを求める読者に向いている。

Cormen、Leiserson、Rivest、Steinの Introduction to Algorithms は、同じ著者とその同僚による包括的な教科書である。Jamesは Algorithms Unlocked を、著者の「より大人向けの本」への入口と呼んでいる。コース内の近似アルゴリズムとランダム化アルゴリズムの本（Vazirani、WilliamsonとShmoys、MitzenmacherとUpfal）は、アルゴリズムの講義を一通り終えた、ずっと後で読むものである。

本書の使い方

本書は、コンピュータサイエンスを志す学生や1年生、標準的なアルゴリズムの背後にあるものを知りたい正規の教育を受けていないプログラマー、代数に抵抗のない他分野の読者に向いている。Jamesは、理想的な読者はコンピュータサイエンスの1年生かその志望者、あるいは分野を手軽に見渡したいプログラマーだろうと述べている。ある程度のプログラミング経験があれば、疑似コードはずっと追いやすくなる。

実際的な読み方：

• 中核： 第1〜3章と第5〜6章。語彙（疑似コード、実行時間）、ソートと探索のアルゴリズム、そして後のどの講義でも前提とされるグラフと最短経路のアルゴリズムを扱う。
• 次に優先するもの： 第4章と第10章。下界とNP完全性の章は、本格的な講義でより形式的に証明される考え方を導入する。
• 関心に応じて： 文字列、暗号、圧縮を扱う第7〜9章は、第2章の後ならどの順序で読んでもよい。

鉛筆を手に読むこと。各疑似コードの手続きを小さな入力でたどり、二つか三つのアルゴリズム（二分探索、マージソート、ダイクストラ法）を自分の知っている言語で実装してみる。その後、練習のために問題集つきの教科書に進むとよい。