ITエンジニアと（自称）作家を両立させたい僕が目指したい最終形である、結城浩先生の「プログラマの数学 第2版」を読みました。
2日かけて一気に読み上げました。数学が苦手で、でももっとプログラミング能力を上げたい人は手にとってほしいです。
かつて数学がちんぷんかんぷんでも、俺たちには結城浩先生がいる
仕事でプログラミングをしているものの、小手先の話ではなくもっと原理的な部分を理解したいと思うようになりました。 勉強は好きではないので、AtCoderやAIZU ONLINE JUDGEを使ってゲーム感覚でやってたんですが、どうしても解けない問題が出てきます。
それが数学（の授業で出てきた単語の出現）です。
特に、順列という単語が出てきたときは「それっていつかの数学の授業でやった気がする（全く覚えてない）」となって、プログラムで実装どころではなくなりました。とりあえず順列の意味を知らないとどうしようもないです。
例えば、FizBuzzのような条件分岐や、特定回数ループしようといった問題文ならある程度プログラミングに慣れていれば解けてしまいます。 しかし、「条件分岐やループをさせればXXを表現できる」という構造を見抜いた上で実装するのとは全く意識に差があるでしょう（そこに数学的発想があることを理解できたのはプログラマの数学 第2版のおかげです）。
このまま練習をしても、計算量オーダーやアルゴリズムをすぐに理解できないことは明白でした。
「あーあもっと学生時代勉強しておけばよかった」とは思っていません。当時の僕にとって数学は意味不明な宇宙語のように感じていました。今更そんなことを言っても僕がかわいそうです。
やはり、数学が苦手だった自分をどうにかするしかありません。どんなに数学アレルギーでも、ここから先に進むには何百歩も戻って、わかるところから進み直すしかないわけです。
そんなときに寄り添ってくれるのが、結城浩先生です。 「数学ガール」を代表とする著書は僕のような数学音痴にもわかるように執筆されています。
今回読んだ「プログラマの数学 第2版」のコンセプトもプログラミング初心者や数学が苦手な人に向けて書かれています。
学生時代に苦手だったからなんだというのでしょう。今から学び直せばいいだけです。
プログラマの数学 第2版
目次ごとに感じたことを書いていきます。
- 読了時間: 約16時間
- IT業界: 7年目
- アプリケーション開発歴: 1年半（コードを書かないエンジニアだった期間が長い）
条件分岐やループといった基本的な処理を理解していて、FizBuzzが回答できるレベル以上ならまず読み切れると思います。さらに業務でプログラミングしているなら安心して取り組めるはずです。
数学っぽい表現（p, k, nみたいな代数）が当時とても苦手でしたが、プログラミング経験によって「ただの変数でしかない」という感覚になり、アレルギー反応が消えていました。
むしろ章が終わるたびに「あれはこういうことだったのか」と点がつながって、気持ちよくなります。
第1章 ゼロの物語 —— 「ない」ものが「ある」ことの意味
10進法や2進法など、数字に関する話です。なぜコンピュータは2進法なのか。N進法を採用する理由はなにか。など、意外と知らなかったことを知れます。というか気にしたこともなかった話もあって面白いです。
徐々に「10の0乗は何か」「10の-1乗って何だろう」という問いかけが始まり、そこからルールを見出します。公式を覚えていなくても、もっとシンプルに値を出したいと意識することのほうが重要だと書かれています。
人間は人間の処理限界を超えるために様々な工夫をしてきたとあります。
大きな問題は、小さな『まとまり』に分けて解け
ゼロやN進法、指数法則がなぜあるのかを理解するだけでも数学の入り口に立てたような気がしてきます。
第2章 論理 —— trueとfalseの2分割
おなじみのTrue, Falseです。あいまいさをなくすために、この論理が必要だといいます。
論理積や論理和といった懐かしい単語が出てきますが、プログラミングをしていれば言いたいことはわかるはずです。AかつB、AまたはBとか。
学生時代、ベン図という謎の図にずいぶん苦しめられました。でも本当は図にすることでシンプルにしているんだ、という意図に気づいてやれなかった僕の落ち度です。
一見複雑そうにみえる問題文であっても、条件を論理に当てはめて考えると一瞬で解けたりする例も記載されています。これが実に面白かったので、ぜひ読んでみてほしいです。
第3章 剰余 —— 周期性とグループ分け
割り算して出た余りっていうのはグループ分けなんだぜ、という章です。
「日曜日の今日から、100日後は何曜日？」という問題が記載されています。
一日ずつ考える方法もあるわけですが、これがもし1億日後になったら数えられんよな？とバッサリ言われます。 構造を見抜くのだと、何度も耳元で教えてくれるようです。
1週間は7日あって、7日ごとに同じ曜日が回ってくる。ならば、7日後・14日後と「7の倍数」日後は必ず日曜日である。
と見抜けるかがポイントになっています。 そこまでわかれば、98日後も日曜日であることが計算できます。
答えは日曜日+2日後=火曜日と算出できるというわけです。
このように他の例題でも割り算と余り値によって算出される一定のルールを見つけることで、巨大な数値の計算も可能にしています。
わかってしまえばとてもスッキリする章です。
第4章 数学的帰納法 —— 無数のドミノを倒すには
数学的帰納法……知らない子ですね。
数学的帰納法とは、
数学的帰納法（すうがくてききのうほう、英: mathematical induction）は証明の手法の一つ。自然数に関する命題 P(n) が全ての自然数 n に対して成り立つ事を証明するために、次のような手続きを行う。
- P(1) が成り立つ事を示す。
- 任意の自然数 k に対して、「P(k) ⇒ P(k + 1)」が成り立つ事を示す。
- 1と2の議論から任意の自然数 n について P(n) が成り立つ事を結論づける。
とあります。
数学やっていると、毎回「だからそれなんかの役に立つんですか？」と言いそうになりますがぐっとこらえます。 掲載されている例題を見ることで、僕らは日頃プログラミングでよくやっている処理を思い出すことになるでしょう。
P(0)が成り立つ→P(0)が成り立つなら、P(0+1)も成り立つ
という意味はわかります。そしてこれを利用して、こんなコードを書くことはありませんか。
# 配列要素の和を求める処理 array = [1,2,3,4,5] def sum(array, size) k = 0 s = 0 while (k < size) do s = s + array[k] k += 1 end puts s end sum(array, array.size)
- s = 0にすることで、P(0)の部分が成立します
- それが成り立つなら s = s + array[k]も成り立つ
ループ文が条件が合致している間ずっと成り立っています。あとはsizeが上限に達したとき、このループは役目を終えて終了します。無事命題 P(n) が全ての自然数 n に対して成り立つ事を証明したと言えるでしょう。
ほとんど初めて（学校でやっただろ！）この概念を聞くと、一回ではなかなか理解に至れないなあと情けなくなります。 ただ、数学的帰納法はループ文をつくるときに重要な考え方とわかれば、かなりとっつきやすくなるなと思いました。
第5章 順列・組み合わせ —— 数えないための法則
この本で一番理解する難易度が高いと思った章です。何回読んでもうまく掴めてないです。
すくなくとも順列、組み合わせという数学の名前で丸暗記する章ではありません。プログラミングに重要な「もれ」「重複」に関する知見がつまっています。
トランプやサイコロで例えられている間はわかるのですが、一般化された途端にわからなくなってきました。一回読んだくらいでは、うまく構造を見抜けなかったです。慣れの問題でしょうが、このブログで紹介できるほど理解度が追いついてません。
ぜひ気になる方は購入してみてください。
第6章 再帰 —— 自分で自分を定義する
再帰はプログラミングをしていれば聞いたことがあるでしょう。
自分で自分を定義する
というもので、ハノイの塔、フィボナッチ数列、パスカルの3角形、シェルピンスキーのギャスケットの例があげられています。
自分で自分を定義するには、やはり構造を見抜くことが重要と書かれています。
階乗（3! = 3 * 2 * 1）を再帰的に定義するとき、
n! → n * (n - 1)! という構造が現れます。
3! = 3 * 2! ↓ 2! = 2 * 1! ↓ 1! = 1 * 0! ↓ 0! = 1
この再帰が重要なのは、
大きな問題を、同じ形をした小さな問題に帰着させる
という点だそうです。ソフトウェア開発に限らず、人間に手に負えない大きくて複雑な問題は小分けにすべきです。無論プログラミングにおいても小さく切り分けることは鉄則とも言えるでしょう。
この考え、構造を見抜く練習に使えるのでとても重要な章でした。
第7章 指数的な爆発 —— 困難な問題との戦い
厚さ1mmの紙があります。この紙は何度でも2つ折りにできる柔軟性を持ち、2つ折りをするたびに厚さ2倍になるとします。月までの距離を39万kmとして、2つ折りを何回繰り返したら月までの距離を越す厚みになりますか
たった1mmの厚みでも、倍倍にしていけばとんでもない数になる。という例を実感できる問いです。
答えはなんと39回で55万km程度になって超えることになります。
指数的な爆発は、あっという間に大きな数になってしまうという点でなんだか怖いですが、それを利用した考え方があるといいます。
それは、実際にアプリケーションを書いてても起こるので身近な方法です。
たとえば、100万レコードあるデータを0から順番に探索して99万番目にあるデータが対象だった場合、とんでもない処理時間になってしまうでしょう。これを指数的な爆発を利用して効率化する方法がバイナリサーチです。二分探索とも言います。
これを使えば、どんなに数が大きくとも対象は毎回半分ずつになっていくわけです。0から探索せず、50万番目から半分ずつにしていく。
バイナリサーチは基本のアルゴリズムですが、このように0から説明してもらうとわかりやすくしっくりきました。
また、ここでは計算量オーダーでよく見るlog nも登場します。毎度logって言われても全然ピンとこねえな（ちゃんと勉強してなかっただけだけど）と思ってました。
ここを読むだけで、log n についてもわかるようになるのでNiceな章でした。
第8章 計算不可能な問題 —— 数えられない数、プログラムできないプログラム
計算不可能の意味は「処理が長すぎる」などではなく、プログラム不可能を指しています。
プログラムそのものの処理結果に矛盾をはらんでいる場合、そのプログラムは実行できません。
たとえでは、停止判定問題が紹介されています。
「プログラムにデータを与えて動かしたとき、有限時間内に動作が停止するかどうか」を判定する問題
仮にこれを試しても、
- Aというデータではプログラムが停止できた
- Bというデータではプログラムは無限ループし、停止しない
となります。すると、Bの場合は永遠に停止しないので、判定することは不可能ということです。これが計算不可能な問題です。
プログラムを使えば人間には解ききれない問題を処理できますが、本質的にプログラムでは解くことができないことがある。ということを知れる章です。
付録1：機械学習への第一歩
機械学習に関する章が追加されていました。個人的にはそこまで興味がないので、今回はまだ読んでません。
付録2：読書案内
本に興味を持った人のために、関連する書籍がズラッと掲載されています。このあたりの優しさはさすがです。
読書感想
2日で読んだので、まだ完全に理解したとは言えないのが本音です。が、すごくためになったのは確かです。ああここが使えるんだ。面白いなと思ったり、計算量オーダーを考える際の基礎部分だったりします。
このあとはアルゴリズムの勉強もする予定なので、また難しくなったらこの本に立ち戻ってくるような使い方をしたいと思います。
それにしても数学を学生時代から楽しく取り組めた人は羨ましいです。とはいえ、昔はできなかったことができるようになっていく実感はとても楽しいと思います。
やっていき
