プログラマの数学 第2版
SBクリエイティブ
著者：結城浩
はじめに
数学的な考え方の例
人間とコンピュータの共同戦線
本書の対象読者
本書の構成
初版謝辞
第2版の刊行にあたって
第1章 ゼロの物語ー「ない」ものが「ある」ことの意味
この章で学ぶこと
小学一年生の思い出
10進法
10進法とは何か
2503を分解すると
2進法
2進法とは何か
1100を分解すると
基数変換
コンピュータで2進法が使われている理由
位取り記数法
位取り記数法とは何か
位取り記数法を使わないローマ数字
指数法則
10の0乗は何か
10^-1って何だろう
ルールの拡張
2^0を考える
2^-1って何だろう
0の果たす役割
0の役割：場所を確保する
0の役割：パターンを作り出し、ルールをシンプルにする
日常生活の中のゼロ
人間の限界と構造の発見
歴史の流れを振り返って
人間の限界を越えるために
この章で学んだこと
第2章 論理ーtrueとfalseの2分割
この章で学ぶこと
どうして論理が大切なのか
論理はあいまいさをなく道具
論理に対して否定的に感じている方へ
乗車料金の問題ー網羅的で排他的な分割について
バス料金のルール
命題と真偽
「もれ」はないか
「だぶり」はないか
数直線を書いて考えよう
境界に注意しよう
網羅的で排他的な分割をしよう
if文は問題を分割する
論理の基本は2分割
複雑な命題を組み立てる
否定ーAではない
論理積ーAかつB
論理和ーAまたはB
排他的論理和ーAまたはB(でも両方ではない)
等値ーAとBは等しい
含意ーAならばB
すべてを尽くしているか
ド・モルガンの法則
ド・モルガンの法則とは
双対性
カルノー図
2ランプゲーム
まずは論理式で考えてみよう
カルノー図を使ってみよう
3ランプゲーム
未定義を含む論理
条件付論理積(&&)
条件付論理和(||)
3値論理での否定(!)
3値論理でのド・モルガンの法則
すべてを尽くしたか？
この章で学んだこと
第3章 剰余ー周期性とグループに分け
この章で学ぶこと
曜日クイズ(1)
クイズ(100日後は何曜日)
クイズの答え
剰余を使って考える
剰余の力ー大きな数を割り算1回でグループで分け
曜日クイズ(2)
クイズ(10^100日後は何曜日)
ヒント：直接計算できる？
クイズの答え
周期性を見ぬこう
周期を視覚的にとらえる
累乗クイズ
クイズ(1234567^987654321)
ヒント：実験して周期性を見つけよう
クイズの答え
振り返って：周期性の発見と剰余の関係
オセロで通信
クイズ
ヒント
クイズの答え
パリティのチェック
パリティ・ビットで2つの集合に分割
恋人探しクイズ
クイズ(恋人探し)
ヒント：小さな数で実験しよう
クイズの答え
振り返って
畳の敷き詰めクイズ
クイズ(部屋に畳を敷き詰める)
ヒント：畳の数を数えてみると
クイズの答え
振り返って
一筆書きクイズ
クイズ(ケーニヒスベルクの橋)
ヒント：試しにやってみよう
ヒント：単純化して考えよう
ヒント：入口と出口を考えよう
クイズの答え
パリティのチェック
この章で学んだこと
第4章 数学的帰納法ー無数のドミノを倒すには
この章で学ぶこと
ガウス少年、和を求める
クイズ(貯金箱の金額)
考えてみよう
ガウス少年の解答
ガウス少年の解答を検討する
一般化する
数学的帰納法ー無数のドミノを倒すには
0以上の整数についての主張
ガウス少年の主張
数学的帰納法とは
ドミノ倒しにたとえてみよう
ガウス少年の主張を数学的帰納法で証明する
奇数の和を求めるー数学的帰納法の例
奇数の和
数学的帰納法による証明
図形的な説明
オセロクイズー誤った数学的帰納法
クイズ(オセロの石の色)
ヒント：図に惑わされないように
クイズの答え
プログラムと数学的帰納法
数学的帰納法をループで表現する
ループ不変条件
この章で学んだこと
第5章 順列・組み合わせー数えないための法則
この章で学ぶこと
数えるとはー整数との対応付け
数えるとは
「もれ」と「だぶり」に注意
植木算ー0のことを忘れるな
植木算クイズ
和の法則
和の法則
積の法則
積の法則
置換
置換
一般化してみよう
クイズ(トランプの並べ方)
順列
順列
一般化してみよう
樹形図ー性質を見ぬけるか
組み合わせ
組み合わせ
一般化してみよう
置換・順列・組み合わせの関係
クイズで練習
重複組み合わせ
論理も使おう
この章で学んだこと
第6章 再帰ー自分で自分を定義する
この章で学ぶこと
ハノイの塔
クイズ(ハノイの塔)
ヒント：小さいハノイを解きながら考えよう
クイズの答え
閉じた式を求める
ハノイの塔を解くプログラム
再帰的な構造を見つけ出そう
階乗、ふたたび
階乗の再帰的定義
クイズ(和の定義)
再帰と帰納
フィボナッチ数列
クイズ(増えていく生物)
フィボナッチ数列
パスカルの3角形
パスカルの3角形とは
組み合わせの数の再帰的定義
組み合わせ論的解釈
再帰的な図形
再帰的に木を描く
実際に描いてみよう
シェルピンスキーのギャスケット
この章で学んだこと
第7章 指数的な爆発ー困難な問題との戦い
この章で学ぶこと
指数的な爆発とは何か
クイズ(月へ届く祈り紙)
指数的な爆発
倍倍ゲームー指数的な爆発が生み出す困難
プログラムの設定オプション
「有限だから」は通じない
バイナリサーチー指数的な爆発を利用する検索
犯人探しクイズ
ヒント：少ない人数で考えてみよう
クイズの答え
再帰的な構造の発見と漸化式
バイナリサーチと指数的な爆発
対数ー指数的な爆発を把握する道具
対数とは
対数と累乗の関係
2を底とする対数
2を底とする対数の練習
対数グラフ
指数法則と対数
対数と計算尺
暗号ー指数的な爆発で秘密を守る
ブルート・フォース・アタック
ビット長と安全性の関係
指数的な爆発に対処するには
問題空間の広さを理解する
4つの対処法
この章で学んだこと
第8章 計算不可能な問題ー数えられない数、プログラムできないプログラム
この章で学ぶこと
背理法
背理法とは
素数クイズ
背理法の注意点
カウンタブル
カウンタブルとは
カウンタブルな集合の例
カウンタブルではない集合は存在するのか
対角線論法
整数列全体はカウンタブルではない
実数全体の集合はカウンタブルではない
関数の集合もカウンタブルではない
計算不可能な問題
計算不可能な問題とは
計算不可能な問題が存在することを示す
クイズ
停止判定問題
プログラムの停止判定
プログラムを調べるプログラム
停止判定問題とは
停止判定問題の証明
納得しない人のために
計算不可能な問題はたくさんある
この章で学んだこと
第9章 プログラマの数学とはーまとめにかえて
本書を振り返って
問題を解くということ
パターンを見ぬき、一般化する
苦手から生まれる知恵
ファンタジーの法則
プログラマにとっての数学
付録1 機械学習への第一歩
この付録で学ぶこと
機械学習とは
注目される機械学習
機械学習は時代の技術
予測問題と分類問題
予測問題
分類問題
パーセプトロン
パーセプトロンとは
重み付け和
活性化関数
パーセプトロンのまとめ
機械学習における「学習」
学習の流れ
訓練データとテストデータ
損失関数
勾配降下法
プログラマの関与
ニューラルネットワーク
ニューラルネットワークとは
誤差逆伝搬法
ディープラーニングと強化学習
人間は不要になるのか
この付録で学んだこと
付録2 読書案内
読み物
コンピュータ科学
索引