新刊ピックアップ

「アルゴリズムって?」と聞かれたらどう答えますか

この記事を読むのに必要な時間:およそ 1 分

突然ですがクイズを1つ。

1~100の中から数を1つ思い浮かべます。あなたは,その数を当ててください。あなたが言った数が当たりでないなら,もっと大きい,または,もっと小さい,というヒントを与えます。できるだけ少ない回数で当てるように工夫してください。

これはIT企業の入社面接で使われたことのある問いです。ある「解法」を知っていれば簡単に解ける問いで,面接官はその「解法」を知っているかどうかを尋ねています。

「解法」は,正確にいえば「アルゴリズム」となります。この面接官が聞いているのは,ごく基本的なアルゴリズムを知っているかどうか,ということです。

アルゴリズム。たまに目にしたりすることがある言葉と思いますが,その意味をご存じでしょうか?

アルゴリズムは,一言で表すのは難しい言葉です。新刊アルゴリズム はじめの一歩 完全攻略の冒頭では,次のように説明されています。

筆者の手元にある『新英和中辞典』⁠研究社)では,algorithmという英語を,以下の日本語に訳しています。これらは,どれも「与えられた問題の解を得る方法」という意味です。

英和辞典の和訳
⁠演算法」⁠演算方式」⁠算法」

インターネットのgoo辞書によると,algorithmの語源は,9世紀の数学者の名前が著作を通して学術用語となった,⁠数」を連想させるもの,となっています。

語源
→数学者の名前,数を連想させるもの

日本工業規格のJIS X 0001:1994「情報処理用語−基本用語」では,アルゴリズムという用語を,以下のように定義しています。

JISの定義
⁠問題を解くためのものであって,明確に定義され,順序付けられた有限個の規則からなる集合」

これらをまとめると,アルゴリズムは,⁠数」に関する「問題を解く方法」だということになります。そして,コンピュータの分野では,⁠明確であること(あやふやな部分がないこと)⁠「有限であること(いつ終わるかわからない手順でないこと)⁠という条件が付きます。

冒頭のクイズは,このアルゴリズムにのっとって正解を導けます。たとえば面接官の頭の中にある数字が「3」だったとします。

  • 受験者:1~100の真ん中の値である「50(もしくは51)⁠と答える
  • 面接官:「もっと小さい」と答える
  • 受験者:1~49の真ん中の値である「25」と答える
  • 面接官:「もっと小さい」と答える
  • 受験者:1~24の真ん中の値である「12(もしくは13)⁠と答える
  • 面接官:「もっと小さい」と答える
  • 受験者:1~11の真ん中の値である「6」と答える
  • 面接官:「もっと小さい」と答える
  • 受験者:1~5の真ん中の値である「3」と答える

数が偶数個の場合はぴったり真ん中になる値(中央値)はないので,⁠50(もしくは51)⁠などとしていますが,奇数個ならぴったり真ん中の数が見つかります。このように,全体から範囲を徐々に絞りつつ探索していくことを「二分探索」といいます。基本的なアルゴリズムの1つです。

1~100→1~49→1~24→1~11→1~5と,正解に向かって網を狭めていきます。もっと具体的にいえば,中央値50より小さいということは,1~49の中に正解がある(51~100に正解はない)⁠中央値25より小さいということは,1~24の中に正解がある(26~49に正解はない)⁠中央値12より小さいということは,1~11の中に正解がある(13~24に正解はない)……となり,正解の可能性があるグループと不正解のグループの2つに分けていくことを繰り返して確実に正解までたどり着きます。

「アルゴリズム」にぴったりはまる訳語はないため,⁠問題を解くためのものであって,明確に定義され,順序付けられた有限個の規則からなる集合」といったお堅い説明になってしまうのですが,簡単な具体例を通して見てみると「そういうことか」と納得いただけるのではないでしょうか。