プログラマの数学

プログラミングに役立つ「数学的な考え方」を身につけよう。
プログラムや数学の知識は必要ありません。難しい数式はいっさい使わず、明快な文章、たくさんの図、パズルを通して、やさしく解説しています。プログラミング初心者、数学の苦手な人にも最適。

--

はじめに

　こんにちは、結城浩です。『プログラマの数学』へようこそ。
　本書は、プログラマのための数学の本です。
　プログラミングの土台はコンピュータ科学（サイエンス）であり、コンピュータ科学の土台は数学です。ですから、数学を学ぶことは、プログラミングの土台を固めることにつながり、しっかりしたプログラムを書く助けとなります。
　「でも、数学はどうも苦手なんです」という読者もいるでしょう。特に「数式が出てくると、つい読み飛ばしちゃうんです」という読者は多いと思います。正直なところ、私自身も本の中の数式が出てくると、そこを読み飛ばしたくなります。
　本書は、こうした「読み飛ばしたくなる数式」をできるだけ取り除きました。また、定義や定理や証明がびっしり書かれることもありません。
　本書はあくまでも、プログラマが日々のプログラミングをよりよく理解するための本です。本書を通して、プログラミングに役立つ「数学的な考え方」を学んでください。


数学的な考え方の例

　「数学的な考え方」を学ぶといっても抽象的すぎるので、例を少しお話ししましょう。

【条件分岐と論理】
　プログラミングをする際は、私たちは条件に応じて処理を「分岐」させます。CやJavaあらif文を使いますね。条件を満たすならこっちの処理を行い、満たさないならあっちの処理を行う、というように処理の流れを制御します。このとき私たちは、数学の一分野である「論理」を使ってプログラムをコントロールしていることになります。ですから、プログラミングでは「かつ」「または」「…ではない」「…ならば…」という論理を構成している要素をきちんと使いこなす必要があります。

【繰り返しと数学的帰納法】
　私たちは大量の情報を処理するために、プログラムを使って「繰り返し」を行います。たとえばfor文を使えば、たくさんのデータを繰り返し処理できますね。繰り返しを支えているのは「数学的帰納法」です。

【場合分けと数え上げの法則】
　たくさんの条件やデータを「場合分け」するとき、プログラムは見落としが絶対に起きないように気をつけなければなりません。そんなときは、和の法則、積の法則、順列、組み合わせといった「数え上げの法則」が役立ちます。これは、プログラマがいつも磨き上げておくべき数学の道具です。
　この他にも本書では、再帰、指数、対数、剰余などの基本的で大切な考え方を学ぶことができるようにしています。


人間とコンピュータの共同戦線

　私たちがプログラムを書くのは、人間だけでは解けない問題を解くためです。プログラマは、問題を理解し、プログラムを書きます。コンピュータは、そのプログラムを実行し、問題を解きます。
　人間は繰り返しが苦手です。すぐに飽きてしまい、ミスをおかします。でも、問題を解きほぐすのは得意です。これに対して、コンピュータは繰り返しが得意ですが、自分で問題を解きほぐすことはできません。
　つまり人間とコンピュータは力を合わせて問題を解いているのです。
　難しい問題にぶつかる。人間だけでは解けない。コンピュータだけでも解けない。でも、人間とコンピュータが力を合わせれば解ける。その姿を描くのも本書の目的のひとつです。
　しかし、プログラムを作るのは難しいものです。いくら人間とコンピュータが力を合わせて挑戦しても、うまく解けない問題もあります。本書では、人間とコンピュータの限界についても考察します。
　本書を読み終えたとき、プログラムを使って人間とコンピュータが共同でやろうとしていることを、より深く理解してもらえればと思います。


本書の対象読者

　本書の主な読者対象はプログラマです。でも、プログラミングや数学に関心のある方なら、どなたでも楽しめると思います。
　数学に精通している必要はありません。本書にはΣや∫を使った難しい数式は登場しませんので、数学に苦手意識を持っている方でも大丈夫です。本書を読み進めるのに必要とする知識は、四則演算（＋−×÷）と累乗（2^3=2×2×2）くらいです。それ以外は、本書の中ですべて説明しています。
　数や論理に対して興味を持っている方なら、本書の内容をいっそう楽しむことができるでしょう。
　プログラミングに精通している必要はありません。でも、ちょっとでもプログラムを書いた経験があるなら、本書を理解するうえで大きな助けになるでしょう。説明の一部として、C言語によるプログラムをいくつか使っていますが、C言語を知らなくとも、本書を読むのには不都合はありません。

ISBN4-7973-2973-4.zip

--

目次

　はじめに
　数学的な考え方の例
　人間とコンピュータの共同戦線
　本書の対象読者
　本書の構成
　謝辞

　第１章 ゼロの物語──「ない」ものが「ある」ことの意味
　　小学一年生の思い出
　　２進法
　　位取りの記数法
　　指数法則
　　０の果たす役割
　　人間の限界と構造の発見

　第２章 論理──trueとfalseの２分割
　　どうして論理が大切なのか
　　乗車料金の問題──網羅的で排他的な分割について
　　複雑な命題を組み立てる
　　ド・モルガンの法則
　　カルノー図
　　未定義を含む論理

　第３章 剰余──周期性とグループ分け
　　日曜クイズ（１）
　　日曜クイズ（２）
　　累乗クイズ
　　オセロで通信
　　恋人探しクイズ
　　畳の敷き詰めクイズ
　　一筆書きクイズ

　第４章 数学的帰納法──無数のドミノを倒すには
　　ガウス少年、和を求める
　　数学的帰納法──無数のドミノを倒すには
　　奇数の和を求める──数学的帰納法の例
　　オセロクイズ──誤った数学的帰納法
　　プログラムと数学的帰納法

　第５章 順列・組み合わせ──数えないための法則
　　数えるとは──整数との対応付け
　　積木算──０のことを忘れるな
　　和の法則
　　積の法則
　　置換
　　順列
　　組み合わせ
　　クイズで練習

　第６章 再帰──自分で自分を定義する
　　ハノイの塔
　　階乗、ふたたび
　　フィボナッチ数列
　　パスカルの３角形
　　再帰的な図形

　第７章 指数的な爆発──困難な問題との戦い
　　指数的な爆発とは何か
　　倍倍ゲーム──指数的な爆発が生み出す困難
　　バイナリサーチ──指数的な爆発を利用する検索
　　対数──指数的な爆発を把握する道具
　　暗号──指数的な爆発で秘密を守る
　　指数的な爆発に対処するには

　第８章 計算不可能な問題──数えられない数、プログラムできないプログラム
　　背理法
　　カウンタブル
　　対角線論法
　　計算不可能な問題
　　停止判定問題

　第９章 プログラマの数学とは──まとめにかえて
　　本書を振り返って
　　問題を解くということ

　付録
　　読み物
　　コンピュータ科学

　索引