数学的な考え方の例

【条件分岐と論理】プログラミングをする際に、私たちは条件に応じて処理を「分岐」させます。CやJavaなど、多くのプログラミング言語ではif文を使いますね。条件を満たすならこっちの処理を行い、満たさないならあっちの処理を行う、というように処理の流れを制御します。このとき私たちは、数学の一分野である「論理」を使ってプログラムをコントロールしていることになります。ですから、プログラミングでは「かつ」「または」「…ではない」「…ならば…」という論理を構成している要素をきちんと使いこなす必要があります。【繰り返しと数学的帰納法】私たちは大量の情報を処理するために、プログラムを使って「繰り返し」を行います。たとえばfor文を使えば、たくさんのデータを繰り返し処理できますね。繰り返しを支えているのは「数学的帰納法」です。【場合分けと数え上げの法則】たくさんの条件やデータを「場合分け」するとき、プログラマは見落としが絶対に起きないように気をつけなければなりません。そんなときには、和の法則、積の法則、順列、組み合わせといった「数え上げの法則」が役立ちます。これは、プログラマがいつも磨き上げておくべき数学の道具です。この他にも本書では、再帰、指数、対数、剰余などの基本的で大切な考え方を学ぶことができるようにしています。

第2版の刊行にあたって

近年、機械学習、ディープラーニング（深層学習）、人工知能（AI）といったキーワードをニュースなどで頻繁に見聞きするようになりました。機械学習に関心を持つ人もたくさんいます。しかし、機械学習はプログラミングと数学の両方に深く関わっており、変化が激しく話題も広範囲に及ぶので、近寄りがたいと感じる人もいるでしょう。そこで今回の『プログラマの数学第2版』では「機械学習への第一歩」と題した付録を新たに書き下ろしました。この付録では、機械学習に登場する基本的な概念を順序立てて紹介します。本書は「数式をできるだけ使わない」方針で書いていますが、この付録に関しては簡単な数式を解説しつつ使います。数式を見慣れていないと「易しい」内容を表しているものでも「難しい」と感じてしまうでしょう。数式を見ただけで思考停止してしまうのはもったいないことです。数式も、そんなに恐くないんですよ。この付録が、機械学習への第一歩を踏み出すきっかけになることを願っています。

15人の中から犯人を探す

15人の容疑者が一列に並んでおり、この中に1人だけ「犯人」がいます。あなたは、この人たちに「犯人はどこですか？」と質問して、犯人探しをしなければなりません。

質問した時の答えは3通り

ある人を一人選んで「犯人はどこですか？」と質問したとき、以下の3通りの答えのうち、どれか1つが正しく返ってくるとします。

（1）「犯人はわたしです」（質問した相手が犯人だった場合）

（2）「犯人はわたしよりも左にいます」

（3）「犯人はわたしよりも右にいます」

このとき、3回の質問を行うだけで15人の中から確実に犯人を探すことができます。どのように質問すればよいでしょうか。

少ない人数で考えてみよう

3人の場合には、真ん中の1人に質問すれば、犯人が誰であるかを確定できます。このとき、真ん中の人が犯人である必要はありません。犯人に直接質問しなくても、真ん中の人の答えによって犯人が確定できるからです。

（1）「犯人はわたしです」→当人が犯人確定

（2）「犯人はわたしよりも左にいます」→左の人が犯人確定

（3）「犯人はわたしよりも右にいます」→右の人が犯人確定

これをヒントにして、人数が15人の場合には、どのような質問の手順が適切かを考えましょう。

クイズの答え

次のように「犯人が含まれている範囲で、真ん中の人を質問する」を繰り返せば、3回の質問で犯人を確実に見つけることができます。

【1回目の質問】まず、15人のうち真ん中の人に質問します。このとき、左の7人・本人・右の7人の3グループのどこに犯人がいるかがわかります。本人が犯人なら質問は終わりです。

【2回目の質問】次に、絞り込んだ7人のうち真ん中の人に質問します。このとき、左の3人・本人・右の3人の3グループのどこに犯人がいるかがわかります。本人が犯人なら質問は終わりです。

【3回目の質問】最後に、絞り込んだ3人のうち真ん中の人に質問します。

このとき、左の人・本人・右の人の3人の誰が犯人なのかがわかります。これで犯人が確定します。

バイナリサーチと指数的な爆発

上の「犯人探し」のクイズで使用した方法は、コンピュータでデータを検索するときによく使われる「バイナリサーチ」と同じ方法です。バイナリサーチ（binary search）は、順序よく並んでいるデータから目的のデータを探し出す際に「目的のデータが含まれている範囲の真ん中を常に調べる」という方法です。「二分法」や「二分探索」と呼ばれることもあります。バイナリサーチは、大量の数の中から目的の数を探し出すときに、ものすごい威力を発揮するのです。たとえば、たった10回調べるだけで2047個の中から目的の数を探すことができますし、20回調べたら209万7151個、30回調べたら21億4748万3647個の中から目的の数を探すことができるのです。バイナリサーチで大切なのは、1回調べるたびに検索対象を約半分に絞り込んでいる点です。そのためには、検索対象の数は「順序よく」並んでいる必要があります。そうでないと、1回調べたときに目的の数が「左右のどちらにあるのか」を判断することができないからです。前節で解説した「犯人探し」でも、一列に並んでいる人たちはみな、ほんとうの犯人が自分の左右いずれにいるかを知っていたわけですね。バイナリサーチでは、1回調べるごとに対象を約半分に絞り込みます。言い換えれば、1回多く調べれば約2倍の検索対象から探し出せるということです。バイナリサーチが、指数的な爆発をうまく利用していることがわかるでしょう。