「なっとく！アルゴリズム」を読んだ
「なっとく！アルゴリズム」を読みました。
- 作者:アディティア・Y・バーガバ
- 発売日: 2017/01/31
- メディア: Kindle版
特に大事だと思われる、基本となるアルゴリズムを丁寧にわかりやすく説明してあります。
簡単な内容一覧は以下の通りです。
正直、大半は学生時代に習った（ことになっている）はずですが、ダイクストラ法以降は貪欲法を除いて、名前しか覚えてないレベルでした……。 データ構造とアルゴリズムは学生時代最も苦しかった授業の一つなので、まぁ仕方ないと言えば仕方ないと思います。
学生時代と言えば、コンピューターサイエンス系の授業はたいてい苦しみ、ソフトウェアエンジニア系は楽しめた、という記憶が薄っすらあります。 最も苦しんだ科目は英語でしたが……閑話休題。
これらのアルゴリズムを全てを即座に使いこなせる必要はないと思いますが、どういう問題のときにどういったアルゴリズムを使うと良いかというザックリとしたインデックスを頭に張っておくのは、非常に重要だと思います。特に基本となるデータ構造については、知っておいて全く損はないです。
本当にわかりやすく書かれているので、「アルゴリズムが理解できる！」という自信に、そして、最初の一歩になる本だと思います。 特に未経験からソフトウェアエンジニアしてる人は是非読んでみると良いと思います*1。
以下、読んだことをあとで思い出せるように、簡単なまとめです。
1章から6章までは、基礎の基礎という感じでした。自分でも覚えているようなことが大半でした。 また、8章の貪欲法も「各ステップで局所最適解を選ぶ」というものなので、こちらも覚えていました。
ただ、6章のトポロジカルソートについては、名前と雰囲気だけ知っている状態だったので、しっかりと把握できてよかったです。 雑に言ってしまうと DAG を並べ替えて "any of the sorted items appears after its dependencies (the ones which the item in question is dependent on)" な状態にすることです。
ダイクストラ法も名前しか知らなかったです。そしてもう詳細な内容は忘れました……。 ただ、どういうときに適応できるかを思い出せるように抜き出しておきます。
9章の動的計画法については、ぼんやりと知っている……というレベルでした。 端的に言うと、部分問題先にを解くことで難しい問題を解く手法です。
個人的に少しややこしいなと思ったのが、動的計画法と分割統治の違いでした。 どちらも同じように問題の分割をするからです。
違いとしては、
- 分割統治は、部分問題の解の組み合わせが最終解になる（例：クイックソート）
- 動的計画法は、部分問題の解を再利用して、最終的に最終解を導き出す（例えば部分問題の解を二次元配列にメモ化 memoization しておき、それを計算に再利用していく）
という違いがあります。要は動的計画法は、次の部分問題を解くためにその前の部分問題を解いておく、というように、解の再利用が必要になります。
例えばナップサック問題であれば、まずはサイズ最小、物品一つから始めます。 そして物品が一つの場合の最適解を全てのサイズで解き、次に物品を二つの場合を解きます。 この際、物品が一つの際の最適解を利用します。そしてこれを繰り返します。
大事なことの一つに、部分問題が他の部分問題に依存していてはならない、というものがあります。 部分問題の解が再利用ができなくなってしまうからです（つまり解いたと思ってた部分問題は解けていなかったということ）。
動的計画法は、制約を前提として何かを最適化する際に役立ち、問題を互いに依存関係のない部分問題に分割できるときに使えるアルゴリズムとなります。
10章は k 近傍法でした。まさか回帰の話がアルゴリズムの本に入ってるとは思わなかったです。 こういう機械学習よりのアルゴリズムは、あまりアルゴリズム本で見ない印象でした。あまりアルゴリズム本を読んでないので間違った印象な可能性も高いですが。
特徴量、分類、回帰と、基本的なことに触れていて良かったです。 機械学習への入り口として非常にわかりやすいと感じました。
最後にひとつ、大事だと思った文を抜き出しておきます。
複雑なテクノロジーてあってと、そのベースとなっているのは k 近傍法のような単純なアイデアであることを理解しておくことが重要
読みやすく良い本でした！
