Booklog - プログラマの数学

はじめに ~ 第 1 章。位取り記数法。基数・指数・基数変換。 0 がないことを明示することでパターン化を容易にする。 昔買って読んでなさそうな本があったので読む。サラッと見た感じ純粋に数学という感じの本でないけど内容は読んできた本に重なるのでちょうど良さそう。数式に疲れたし。 内容は難しくなさそうなので今あえて読むか一瞬迷ったが、内容は丁寧だし学び直しと共に、積読消化のために読む。

2026-06-18, read count: 1, page: i ~ xiv, 1 ~ 22, pages read: 36

第 2 章。論理。真偽による 2 分割。 undefined も加えた 3 値論理。 論理式、真理値表、ベン図、カルノー図での表現。ド・モルガンの法則。 内容は基礎的なもので簡単なのと丁寧なことでサクサク読める。過去に学んだ内容の復習であるとか普段何気なくやってることの再確認という感じ。

2026-06-19, read count: 1, page: 23 ~ 64, pages read: 42

第 3 章。剰余と周期性・パターン。剰余を使うことで大きな数の問題を小さな数の問題に置き換える。 偶奇(パリティ)。ケーニヒスベルクの橋。オイラーによるグラフ理論の始まり。 この章は実際に普段から接することのあるアルゴリズムの話で興味深かった。改めて見ると整理して取り組んでるなあという印象。

2026-06-20, read count: 1, page: 65 ~ 88, pages read: 24

第 4 章。数学的帰納法。基底(base)と帰納(induction)の証明で成り立つことを示す。 プログラムにおけるループと数学的帰納法の関係。ループ不変条件(loop invariant)。 帰納との関係は再帰の方がわかりやすいと思うけど時代や C 言語で書かれてる関係でループなんかな。 中々普段の仕事で数学的帰納法と意識的に結びつけて考えることがないので、ちょっと新鮮だったかも。

2026-06-21, read count: 1, page: 89 ~ 112, pages read: 24

第 5 章。順列・組み合わせ。植木算。和の法則、包含と排除の原理(The Principle of Inclusion and Exclusion)、積の法則。 置換(substitution)、階乗(factorial)。順列(permutation)、樹形図で性質を見抜く。組み合わせ(combination)。 置換・順列・組み合わせの関係はそれぞれ、置換は並べ替え、順列は選ぶ、選んで並べ替えるのが順列。 この章は数学図鑑でも読んだし復習がてら理解が深まったのでは？今思えば植木算は zero-based numbering やな。関連付けできた。

2026-06-22, read count: 1, page: 113 ~ 144, pages read: 32

第 6 章。再帰。ハノイの塔と漸化式。 n だけで表現できる閉じた式。大きな問題を一回り小さい問題を使って表現するのが再帰。 再帰と 0! の値が 1 な理由。再帰と帰納は本質的に同じ。フィボナッチ数列。パスカルの 3 角形の再帰的定義と組合せ論的解釈。 再帰的な図形。木、シェルピンスキーのギャスケット(Sierpinski gasketcx)。フラクタル図形。 わかりやすい章だった。まだ再帰の話は後の指数の章でも出てくるみたい。

2026-06-23, read count: 1, page: 145 ~ 174, pages read: 30

第 7 章。指数的な爆発。 n^2 じゃなくて 2^n の話。例えばテストの組み合わせパターンが爆発する。 指数的な爆発を逆に利用するのことが便利なケース。二分探索(binary search)。暗号。 暗号は、ブルートフォースアタック(brute-force attack)に対し、指数的な爆発で安全性を担保している。 対数。底、基数。指数的な爆発を小さな数に置き換える。計算尺は対数を用いる。 ちらっと調べたところ「現実的に時間で解けない」というような話は古典的な数学ではないから、計算機科学で発展した考えのようだな。そこから計算量理論につながるのか。

2026-06-24, read count: 1, page: 175 ~ 202, pages read: 28

第 8 章。計算不可能な問題。 背理法。帰謬法ともいう。カウンタブル、日本語では可算・可付番。 カウンタブルな集合の例、有限集合・ 0 以上の偶数全体の集合・整数全体の集合・有理数全体の集合、等。 カウンタブルでない集合。整数列全体の集合は対角線論法でカウンタブルでないことが示せる。実数全体の集合・関数の集合。 計算不可能な問題とは「プログラムで解くことが_原理的に_不可能な問題」。例として停止判定問題。

2026-06-25, read count: 1, page: 203 ~ 232, pages read: 30