どせいたんさき。

ナスダヨー

データ構造とアルゴリズム

ちょっと前に読み終えました.説明が極めて完結でとてもわかり易かったです.アルゴリズムの基本を学ぶには最適の本ではないかと思いました.まだ通して読んだだけで,演習問題には触れていません.これから地道に解いてみようと思います.

はじめに

書籍を購入した時のエントリでも書きましたが,幅広い内容をカヴァーしている,特定の言語に特化していない,気軽に変える値段という条件から本書を選びました.結果としてすごくよい選択をしたなと思っています.目次は以下のようになっています.

目次
  1. アルゴリズムと計算量
  2. リスト構造
  3. ヒープ
  4. ハッシュとバケット
  5. 再帰呼び出しと分割統治
  6. グラフ探索
  7. 最短路問題
  8. 動的計画法
  9. 縮小法
  10. 最大流と割り当て問題
  11. ボロノイ図とドロネー図
  12. 3次元凸包とドロネー図
  13. 平面走査法
  14. 問題の難しさの測り方
  15. 難問対策
  16. 難問を利用した情報保護

内容は広く浅く

各章の分量は「講義の一回分」が目安になっています.話がそれぞれの章で閉じているため,気軽に読むことができます.目次の部分に各章のつながりを示したフローチャートが載せられています. 1 章から 4 章までで基本的なデータ構造について学んだのち,アルゴリズムについて広く浅く学ぶという流れになっています.

アルゴリズムは擬似コード

プログラミング言語の学習はアルゴリズムの学習と密接に関わっています.ある特定の言語を使用してアルゴリズムを学ぶ本も多く出版されています.一方,本書ではアルゴリズムは擬似的なコード(あるいは簡潔な文章)で記述されています.例えば,有名なハノイの塔の問題を解くアルゴリズムは以下のように記述されています.

アルゴリズム MOVE(n,A,B,C):
if n=1 then move the disk from A to C else
    begin
        MOVE(n-1,A,C,B);
        move the largest disk from A to C;
        MOVE(n-1,B,A,C);
    end

この方式はすぐにアルゴリズムを試すことができないという点が短所になります.一方で,アルゴリズムを簡潔に理解できる,アルゴリズムをコードに落としこむ練習ができる,という長所があると思います.

カーペンターズ・アルゴリズム

本書にはコラムとして「カーペンターズ・アルゴリズム」が紹介されています.

コンピュータ内で計算・処理をする代わりに,身の回りの物理現象を利用して問題を解くこともできる.そのような方法は,カーペンターズ・アルゴリズム (carpentar's algorithm) と呼ばれている.carpenter とは「大工さん」のことである.

必ずしも実用的とは言えませんが,ここで紹介されているアルゴリズムの多くは視覚的に明確でわかり易いです.

以下の図はカーペンターズ・アルゴリズムの 1 つ「陰線処理によるボロノイ図の作成」を gnuplot で試してみたものです.詳しくはこのエントリを参照してください.

f:id:xr0038:20130207153115p:plain


本書ではアルゴリズムが大変明快に説明されていますが,アルゴリズムを身につけるためにはやはり手を動かすことが必要だと思います.本書の演習問題と対峙しつつ,アルゴリズムを使いこなせるよう精進したいと思います.