対象読者
- 新人プログラマ。
- 新人プログラマに数学くらいはできてくれと願う方。
- 数学をどこまで勉強すればよいのか？を知りたい方。
はじめに
何をどこまで勉強すればよいのかについて以下をこれまでに書いた。
で、私のような古参にとっては「エンジニアなんて一生勉強だ...」が正直なところだと元も子もないことを書いてしまったのだが、新人さんが配属される季節。何を勉強することが少なくとも必要なのかと考えた。で、こんな本の話です。プログラマの数学。
目次に従って、その内容と関連知識のメモです。この本に書かれているくらいの数学が分かると、どう嬉しいのか。
目次
ゼロの物語 —— 「ない」ものが「ある」ことの意味
10進法 / 2進法 / 位取り記数法 / 指数法則 / 0の果たす役割 / 人間の限界と構造の発見
位取り記数法を通して、ゼロが果たす役割を考える。ゼロは量を持たないが、桁を埋める役割を果たし、ゼロのおかげでシンプルな位取り記数法が可能になった。それが「ない」ものが「ある」ことの意味。
論理 —— trueとfalseの2分割
どうして論理が大切なのか / 網羅的で排他的な分割 / 演算子で複雑な命題を組み立てる / ド・モルガンの法則 / カルノー図 / 未定義を含む論理
2つに分けるということ。論理式、真理値表、ベン図、カルノー図などの道具を使うことができる。
剰余 —— 周期性とグループ分け
曜日クイズ / オセロで通信 / 恋人探し / 畳の敷き詰め / 一筆書き
ゼロとBoolean型の話で匂わせられたと思いきや、だんだんプログラムらしくなってきた。
- 100日後は何曜日
- 10^100 日後は何曜日
「(日-1) Mod 7」とすることで0～6の値が返り、曜日の位置を揃えることが出来ます。
カレンダーの月ごと表示(表示位置は1日の曜日により位置の調整が必要)
X = (日-1)
行 = X / 7 (7で割る、週が求まる…小数切り捨て)
列 = X Mod 7 (7で剰余、曜日が求まる）
取り扱いが難しい大きな数であっても、周期性を見つけて剰余を扱えれば、問題を簡単にできる。
数学的帰納法 —— 無数のドミノを倒すには
ガウス少年 / 数学的帰納法 / オセロクイズ / ループ・インバリアント
話は進む。数学的帰納法は、0以上のすべての整数nについて、ある主張が成り立つことを証明する方法。P(k) から P(k+1) へ「一歩を進める」仕組み。
この考え方は「ループ」に関わる。ループを構成するときには、ループの各回で成り立っている論理式を見つけることが重要。このような論理式のことを ループ不変条件 あるいは ループ・インバリアント という。
順列・組み合わせ —— 数えないための法則
数えるとは / 植木算 / 数え上げの法則 / 置換 / 順列 / 組み合わせ
数え上げの法則は、数えないで済ますための法則。小さな数で練習し、nやkを使って一般化できる。
再帰 —— 自分で自分を定義する
ハノイの塔 / 階乗 / フィボナッチ数列 / パスカルの3角形 / 再帰的な図形
再帰とは、大きい問題を、一回り小さい問題を使って表現するように考えること。
pip install k-peg-hanoi でハノイの塔を試せる。
root@0230359a1b81:~/opt# hanoi 3 3
=
===
=====
0----------------
===
===== =
1----------------
===== === =
2----------------
=
===== ===
3----------------
=
=== =====
4----------------
= === =====
5----------------
===
= =====
6----------------
=
===
=====
7----------------
他、シェルピンスキーのギャスケットなど。再帰的な構造を見つけ出し、そこから再帰的な定義や漸化式を導く。
指数的な爆発 —— 困難な問題との戦い
倍倍ゲーム / バイナリサーチ / 対数 / 計算尺 / 暗号
倍倍ゲームとは繰り返しで大きな数に膨れ上がる例。指数的な爆発を逆手にとることによって問題解決の強力な武器になる。バイナリサーチは指数的な爆発を利用して大量の情報に対して高速に検索を行うアルゴリズムである、等。
計算不可能な問題 —— 数えられない数、プログラムできないプログラム
背理法 / カウンタブル / 対角線論法 / 計算不可能な問題 / 停止判定問題
背理法 ... 「証明したいことの否定を仮定すると矛盾が起きる」ことを示す証明法
このあたりまでくればもう競技プログラミング等にも立ち向かえる。
プログラマの数学とは —— まとめにかえて
本書を振り返って / 問題を解くということ / ファンタジーの法則
つまり数学がわかれば、パターンを見抜き、一般化することができる。
もうおわかりだろうがこの本の魅力、最低限の知識を挫折しない絶妙な難易度とストーリーでプログラマ向けに説明してくれているところ。
- ゼロはシンプルなルールを作る
- 論理は2分割
- 剰余はグルーピング
- 数学的帰納法は2ステップで無限に挑む
- 順列・組み合わせで対象の性質を見抜く
- 再帰は自分の中の自分を見つける
- 指数的な爆発により大規模な問題を取り扱いやすい形に変換する
- 計算不可能な問題は原理的な限界を示す
まとめ
果たして新人さん各位は、数学と学生時代仲良くしてきたでしょうか。
冒頭の結城先生のサイトはWeb立ち読みもあるのでちょっと覗いてみてほしい。数学は大事。このレベルの理解までは端折らないことが良いプログラムを書けるようになる一本道だと思う。あるいは開発チームでなくても、この業界でプロジェクトを管理するにもヒトと対話するにも分かっておいてくれええええという話とも思う。
それほどわかりやすく読みやすい本（物足りないという人はいると思う）。**エンジニアは数学をどこまで勉強すればよいのか？ = 答え:「プログラマの数学」くらいのことは堂々と知っておけ、話はそれからだ。**どんなプログラミング言語にも、この業界のどんな部署のひとにも。
以上、各チームに配属された各位へ、なにがしか参考になればというウェルカムメッセージでした。
2022.09追記: https://manabitimes.jp/math