プログラマの数学

数学

2019-04-12 12:56:17

プログラマの数学

  • 第1章 ゼロの物語 ―― 「ない」ものが「ある」ことの意味
  • 第2章 論理 ―― trueとfalseの2分割
  • 第3章 剰余 ―― 周期性とグループ分け
  • 第4章 数学的帰納法 ―― 無数のドミノを倒すには
  • 第5章 順列・組み合わせ ―― 数えないための法則
  • 第6章 再帰 ―― 自分で自分を定義する
  • 第7章 指数的な爆発 ―― 困難な問題との戦い
  • 第8章 計算不可能な問題 ―― 数えられない数、プログラムできないプログラム
  • 第9章 プログラマの数学とは ―― まとめにかえて
  • 付録1:機械学習への第一歩
  • 付録2:読書案内

第1章 ゼロの物語 ―― 「ない」ものが「ある」ことの意味

10進法

2503を分解すると

p.4

  • 基数(底)
    • 桁の重みの基本になる数
      • 10進数なら10、2進数なら2

コンピュータで2進数が使われている理由

p.8

  • スイッチのオン・オフ
  • 数字の種類が少なく済む、桁数は多い

位取り記数法

位取り記数法とは何か

p.10

  • 10進数や2進数といった表記法
  • 8進数、16進数、N進数...

位取り記数法を使わないローマ数字

p.12

  • 位は意味を持たず、数字そのものが数を示す
  • ゼロがない
  • I(1)、V(5)、X(10)、L(50)、C(100)、D(500)、M(1000)

指数法則

10の0乗は何か

p.13

  • 指数が1減ると全体は10分の1になる
    • 10^2 = 100
    • 10^1 = 10
    • 10^0 = 1

10^-1って何だろう

p.13

  • 10^-1 → 10 * 1/10

0の果たす役割

0の役割:場所を確保する

p.16

  • 位の数がないとしても、”場所”を確保する

人間の限界と構造の発見

人間の限界を超えるために

p.20

  • 数が大きくなってくると扱いが難しくなる
  • 大きな問題は小さな「まとまり」に分けて解け

第2章 論理 ―― trueとfalseの2分割

乗車料金の問題ー網羅的で排他的な分割について

命題と真偽

p.26

  • 命題
    • 正しいか正しくないか
    • true or false

網羅的で排他的な分割をしよう

p.30

  • 網羅的
    • 「もれ」がないこと
  • 排他的
    • 「だぶり」がないこと

複雑な命題を組み立てる

論理積ーAかつB

p.35

  • 論理積
    • AかつB
    • A∧ B

論理和ーAまたはB

p.37

  • 論理和
    • AまたはB
    • A∨B

排他的論理和ーAまたはB(でも両方ではない)

p.40

  • 排他的論理和
    • AまたはBのどちらか一方
    • A⊕B

等値

p.42

  • 等値
    • A=B

含意ーAならばB

p.43

  • 含意
    • AならばB
    • A→B

ド・モルガンの法則

ド・モルガンの法則とは

p.50

第4章 数学的帰納法 ―― 無数のドミノを倒すには

数学的帰納法ー無数のドミノを倒すには

数学的帰納法とは

p.95

  • 整数についての主張を、0以上のすべての整数について証明するときに用いる方法
    • 基底
    • 前提

第5章 順列・組み合わせ ―― 数えないための法則

和の法則

和の法則

p.119

  • ダブリのない集合同士をあわせてできる集合を得るための法則
    • 集合の要素にダブリがない時に成り立つ

積の法則

積の法則

p.123

  • 集合AとBの積
    • AとBのすべての要素の組み合わせ

置換

置換

p.125

  • n個のものを順序を考えて並べること

一般化してみよう

p.126

  • 階乗(factorial)
    • 5!
      • 54321

順列

順列

p.128

  • n個のものから一部だけを選び出して並べる
    • 順列と同様に順序を考えて並べる
    • 重複して数えた分で割り算する
      -nPk
    • nPk = n! / (n-k)!

組み合わせ

組み合わせ

p.134

  • n個のものから順序考えずに一部を選び出す
  • nCk
    • nPk / kPk

第6章 再帰 ―― 自分で自分を定義する

ハノイの塔

p.152

  • 漸化式
    • 各項の値をそれよりの前の値の項によって求める規則の式

階乗、再び

再帰と帰納

  • 「大きな問題を、同じ形をした小さな問題に帰着させる」という点で共通 
  • 再起
    • 「大きなおのからだんだん小さいものへ」
  • 帰納
    • 「小さなものからだんだん大きなものへ」

第7章 指数的な爆発

指数的な爆発に対処するには

4つの対処法

p.201

  • 力ずくで解く
    • コンピューターリソースの力
  • 変換して解く
    • 簡単な問題に変換する
  • 近似的に解く
    • 概算やシュミレーション
  • 確率的に解く
    • 乱択アルゴリズム

第8章 計算不可能な問題

背理法

背理法とは

p.204

  • 「証明したい命題の否定」が成り立つと仮定
  • その仮定を元にして論証を勧め、矛盾を導く
  • →証明したいことの否定を仮定すると矛盾が起きることを示す証明法
  • 帰謬法ともいう

カウンタブル

カウンタブルとは

p.208

  • 集合の要素が有限個であるか、または集合のすべての要素を1以上の整数と1対1に対応付けられるとき、その集合をカウンタブルであると定義する
  • 要素を「もれ」なく「ダブリ」なく数えるルールを定められる

計算不可能な問題

計算不可能な問題とは

p.218

  • 原理的にプログラムで解くことが不可能な問題
  • 解を求めるのに沢山の時間がかかる問題のことではない

第9章 プログラマの数学とは

本書を振り返って

p.234

  • 「ゼロ」はシンプルなルールを作る
  • 「論理」は2分割
  • 「剰余」はグルーピング
  • 「数学的帰納法」は2ステップで無限に挑む
  • 「順列・組み合わせ」では対象の性質を見抜くことが大切
  • 「再帰」は自分の中の自分を見つける
  • 「指数的な爆発」 は大規模な問題を取り扱いやすい形に変換するアイデアを見つける
  • 「計算不可能な問題」は原理的な限界を示す

問題を解くということ

パターンを見ぬき、一般化する

p.237

  • 問題のパターンを見抜いて一般化して考える

About the author

Image

bmf san @bmf_san
A web developer in Japan.