【技術書典応援祭】アルゴリズム本紹介
はじめまして。ねず宮ちんじろう(@land_chinchilla)と申します。
先日から開催されている「技術書典」というイベントに初参加しています。本記事はオンラインマーケット「技術書典 応援祭」で頒布している新刊「0から分かる！ソート・選択アルゴリズムと資源配分問題」の紹介です。
一言で言えば、アルゴリズムの流れや考え方を誰でも分かるように解説した本となっています。
■想定する読者
・数学・パズル・ゲームなどが好き
・ソートって何？アルゴリズムに触れたことがない
・基本的なアルゴリズムは分かるけど、
難しくなると手に負えない
・競プロにおけるアルゴリズムの構築方法を学びたい
■内容
・アルゴリズムの中でも超有名！「ソートアルゴリズム」の流れ
・ソートの応用「選択アルゴリズム」の流れ
・経済学にソート・選択アルゴリズムの知識を応用！
「資源配分問題」を解くアルゴリズム
アルゴリズムとは？
アルゴリズムというのは何らかの問題を解くための手続きのことです。
例えば 1+2+3+4+5+6+7+8+9+10 を頭からやっていくと大変です。
これを1+10=11, 2+9=11, 3+8=11, 4+7=11, 5+6=11と考えることで、答えは 11×5=55 と簡単に求めることができます。
このように解き方を工夫すると問題を解く手間が変わることがあります。定義によりますが、ざっくり良いアルゴリズムというのは
・計算の回数が少ない
・使う道具（マシン・メモリ）が少ない
といった点で評価されることが多いです。
ソートアルゴリズム
ソートとは何らかの規則に従って、データを並び替えることです。
例えば、次の8つのデータからなる数列を考えて、
これを小さい順に並べ替えます。
この本ではいくつかのソートアルゴリズムの流れを、
具体的な例を挙げて説明します。
選択アルゴリズム
ソートの一種であるクイックソートを利用したのが選択アルゴリズムです。こちらも例を挙げて説明します。次のような27個の数字があります。
この中で1番大きい数字を見つけるのは比較的簡単だと思います(答えは98)。しかし，この中で14番目に大きい数を見つけるのはかなり大変です。
複数のデータの集まりから〇番目のものを探索するアルゴリズムを、選択アルゴリズムといいます。
この本では選択アルゴリズムの動作を、具体例を使って説明します。
資源配分問題
この本ではソートや選択アルゴリズムを使ってどんな問題が解けるのかを、経済学のモデルを使って説明します。
6個のりんごをAさん、Bさん、Cさん、Dさんに分配することを考えます。
このとき、誰に何個りんごをあげるとどれくらいうれしいか、という値が数値として分かっているとします。例えば次のような状況です。
このとき、全員のうれしさの合計が最大になるように
りんごを配分することを考えます。
この問題はソート・選択アルゴリズムの知識を使って効率的に解けます。
アルゴリズムの基礎知識を使ってどのように新たなアルゴリズムを組み立てるのか、ということを具体例を用いて説明します。
まとめ
このように「アルゴリズム？全然わからない・・・」
という人でも出来る限り分かるように解説しました。
この記事で紹介した問題以外にも、
最短路問題という問題を扱った本を無料公開中です。
今回の新刊はハードルが高そう・・・と言う方は
試し読みしてみて下さい。11pしかないので気軽に読めます。
■新刊「0から分かる！ソート・選択アルゴリズムと資源配分問題」
■無料公開中「最短路問題のおはなし」
■BOOTH
この記事が気に入ったらサポートをしてみませんか？