アルゴリズムの基礎(アルゴリズム ノ キソ)

アルゴリズムを学び始めるとき、「どこまで押さえれば基礎と言えるのか」の見取り図を 191 ページで示してくれるのが『アルゴリズムの基礎』 (岩野和生 著、朝倉書店、 2010 年 10 月刊) です。大学の情報系課程を想定したシリーズ「情報科学こんせぷつ」の第 4 巻にあたる教科書で、版元は「問題のやさしさ難しさ」までを初心者向けに実質的にやさしく説き明かした一冊と紹介しています。副題の「進化する IT 時代に普遍な本質を見抜くもの」が示すとおり、特定の言語や流行の道具立てではなく、時代が変わっても通用する考え方の骨組みを扱います。

計算複雑度から近似解法まで、 191 ページの守備範囲

収録トピックは、版元の内容紹介によれば計算複雑度、ソート、グラフアルゴリズム、文字列照合、 NP 完全問題、近似解法です。注目したいのは後半の 2 つで、入門段階の教科書が ソートアルゴリズムや探索の効率比較で終わることが多いのに対し、本書は「どれだけ工夫しても速くは解けそうにない問題がある」という計算複雑度理論の核心、すなわち NP 完全問題と、それでも実用的な答えを得るための近似解法までを射程に入れています。解く手順の設計だけでなく、問題そのものの難しさを見積もる視点まで、この分量で一望できる構えです。

計算量という物差しは刊行年で古びない

アルゴリズムの優劣は「手元のマシンで速かったかどうか」ではなく、入力の大きさに対して手数がどう伸びるかで測ります。この伸び方を表す共通言語が O 記法で、たとえば入力が 100 万件になったとき、手数が入力の 2 乗で伸びる方法と「入力 × その対数」で伸びる方法の差は、ハードウェアの進歩では埋まらないほど決定的になります。こうした議論は 2010 年の刊行から古びません。機械がいくら速くなっても、指数的に手数が爆発する問題が実用にならないという事実は変わらないためで、本書の主題が刊行年に対して劣化しにくい理由もここにあります。

『アルゴリズムとデータ構造』系の本格派との使い分け

同じ分野の定番には、石畑清『アルゴリズムとデータ構造』 (岩波書店) のように、擬似コードと正当性の証明を一つひとつ厳密に積み上げていく本格派の教科書があります。証明をじっくり追う時間と体力があるならそちらが王道ですが、本書の持ち味はコンパクトさです。半期の講義と並走させる、独学の最初の一冊として通読して分野の地図を手に入れる、といった使い方に向いており、深掘りは後から大部の教科書で補う「先に地図、後で地形」の順番が現実的です。

計算量の議論を自分の言葉でできるようになりたい人へ

向いているのは、情報系の学部 1 〜 2 年生、プログラミング経験はあるが計算量や NP 完全性を体系的に学んだことがない実務エンジニア、そして設計レビューで「この処理は入力が増えたらどうなるか」を根拠を持って説明したい人です。読み終えると、目の前の問題が「速く解ける類いか、近似で妥協すべき類いか」を判断する物差しが手に入ります。一方、特定言語の実装コード集や、競技プログラミングの解法パターン網羅を期待すると外れます。それでも、コードを書く手前にある考え方を短時間で固めたい読者にとっては、通読しきれる薄さそのものが本書を選ぶ最大の理由になります。