はじめに

エンジニアたるもの、数学は絶対に絶対に学んでおくべきである

この記事の目的はそのような思想を説くことではありません。

エンジニアとしてプログラムを書いたり、データを扱う上で「知ってると便利そう」というものや、「普通に知識として面白い」と思う数学・統計知識を一口サイズでまとめました。

インプットの時間として、楽しく勉強できる記事になれば幸いです！

基本中の基本から、知っているとエンジニアの人生が豊かになりそう(?)な発展編まで用意したので、ある程度基礎が分かっているという方は前半を飛ばしてもらって構いません。

弊社Nucoでは、他にも様々なお役立ち記事を公開しています。よかったら、Organizationのページも覗いてみてください。
また、Nucoでは一緒に働く仲間も募集しています！興味をお持ちいただける方は、こちらまで。

剰余演算

ある整数をある整数で割った時の余りです。

中学や高校では「合同式」と呼ばれ、登場します。

5≡3(mod2)

このような式で表され、この例は2で割った余りが5と3で等しいことを表しています。
どちらも余りは1ですね。

Pythonでは%演算子を使います。

example.py

print(5 % 2)

output

代表的なものとしては、「1000日後は何曜日か？」を求める問題などです。

自然対数e

ネイピア数とも呼びます。
最も重要な特徴は、$e^x$を微分しても$e^x$であるということです。

実際の値は

e = 2.71828182845904...

であり、"大体2.7くらい"と覚えておくのが良いでしょう。

一般的には覚える必要はありませんが、以下の式によって定義されます。

e=\lim_{t\to 0} (1+t)^{\frac{1}{t}}

対数「log」

基本の計算方法としては、

y = \log_a x

の時、

x = a^y

となります。

さらに押さえておくべきは、

a(底)とxが等しい時、yの値は1
xが0に近づく時、yの値は$-\infty$に発散する
xが大きくなるほど、xに対するyの変化量は小さくなる

ただし普段使う形としては上記のaの部分(底と呼ばれます)がネイピア数eの自然対数、または10の常用対数でしょう。

それぞれのグラフの概形を把握しておくことが重要です。

自然対数(底がe)

$\ln{x}$と表現されることも多いです。
常用対数(底が10)

$x$が100の時に2、$x$が1000の時に3とその値の桁数を把握することができます

シグマ（Σ）・パイ（Π）の計算

数式には必ずと言っていいほど出てくる総和の記号です。
今までなんとなくで見ていたなという方がいればここでマスターしてしまいましょう。
なんてことはありません、全て足すだけです。

\sum_{k=1}^{10}k = 1+2+3+...+10=55

よく出てくる形としては、変数が使われるパターンです。

\sum_{k=1}^{n}a_kb_k = a_1b_1+a_2b_2+...+a_nb_n

この数列の和の形を級数とも呼び、無限に続くものを無限級数と呼びます。

パイ（Π）は総積の記号、Σの掛け算バージョンです。

\prod_{k=1}^n k = 1\times2\times3\times...\times{n}

尤度の計算の際などに使われますが、普段お目にかかることは少ないでしょう。

有効数字

小数の桁をどこまで表記するかのルールです。

基本的な考え方は、表記する最後の桁には誤差が含まれているという共通認識です。

例) デジタルの体重計で「65.12kg」と表示された場合

65.115~65.124999...までの値を示していることになり、最後の桁である2には誤差が含まれていることになります。

なぜこの考え方が必要かというと、その後の計算の時に値をどこまで信用して良いのかを明確にするためです。

例) 先ほどの体重計で計測した3人の体重の平均を取る場合

A君の体重	B君の体重	C君の体重
65.12kg	68.35kg	72.41kg

この3人の体重の平均を取るとき、計算結果は68.62666...となります。
ただし先ほど述べた通り4桁目には誤差が含まれています。

途中の計算結果ではこれ以上誤差が拡大しないよう、5桁目以降の切り捨てを行います。
最終的な計算結果の結論を出す時は、5桁目を四捨五入して4桁目までを表示します。

つまり「3人の体重の平均」は、68.63kgと表示します。

論理演算

もれなく、ダブりなく現象を記述するために論理演算は非常に重要です。

以下の論理演算をマスターし、複雑な命題でも記述できるようにしておきましょう。

種類	記号	読み方
否定	$\neg{A}$	Aでない
論理積	$A \land B$	AかつB
論理和	$A \lor B$	AまたはB
排他的論理和	$A \oplus B$	AまたはB(ただし両方ではない)

排他的論理和は、AとBが異なる場合のみ真となります。

以下も論理演算です。

種類	記号	読み方
等値	$A＝B$	AとBは等しい
含意	$A\Rightarrow B$	AならばB

「AならばB」の定義は少し直感と反する部分があるので、真理値表を見ておきましょう。

A	B	$A\Rightarrow B$
True	True	True
True	False	False
False	True	True
False	False	True

AがFalseの時、BはTrueでもFalseでも成り立つというのが$A\Rightarrow B$の定義です。

論理を読み解く際、以下のドモルガンの法則も重要です。

\neg (A \cup B) = \neg A \cap \neg B

集合・論理記号

論文でアルゴリズムを調べたり、ネットで数学を調べたりする時、難しい書き方のせいでつまづくことありませんか？
そんな時に使われていそうな記号と具体例をまとめました。

記号	意味
$\mathbb{R}$	実数全体の集合
$\mathbb{Z}$	整数全体の集合
$\mathbb{N}$	正の整数全体の集合
$A \in B$	AはBの要素である
$\forall x$	すべての$x$において
$\exists x$	ある$x$が存在して
$A := B$	AをBで定義する
$\therefore$	ゆえに
$\because$	なぜならば

具体例としてはこんな感じです。

書き方	意味
{ ${2n \mid n}$は整数 }	2の倍数の集合(右の部分が条件)
{ ${2n \mid n \in \mathbb{Z} }$ }	2の倍数の集合
$x \in N \land x \leqq 5$	xは5以下の自然数である($\land$：かつ)
$\forall x, P(x)$	すべての$x$で$P(x)$が成り立つ
$\exists x\in \mathbb{R}, x^2\geqq0$	ある実数$x$が存在して、$x^2\geqq0$が成り立つ

二項係数

$n$個のものから$r$個を（順番を考慮せず）選ぶ組合せの数です。

{}_n \mathrm{C}_r = \frac{n!}{r!(n-r)!}

で計算します。

$\binom{n}{k}$と表記することもあります。

順番を考慮した「並び替え」の数は、シンプルに

{}_n \mathrm{P}_r = \frac{n!}{(n-r)!}

です。

N進法

コンピュータは0と1の2進法で情報を扱っているという話は有名な話です。

N進法における計算方法に自信がない方はこの機にマスターしてしまいましょう！

N進数から10進数への変換

N進数で表される数abcを10進数に変換するとき、

N^2 \times a + N \times b + c

10進数からN進数への変換

ある10進数で表される数$n$をN進数に変換することを考えます。

$n$をNで割っていく方法が簡単で有名です。

<例>139を7進数で表す

7で割られる数	7で割った時の商	あまり
139	19	6
19	2	5

この時、最終的な商、あまりを逆から辿ると答えになっており、今回の答えは256です。

<例>77を2進数で表わす

2で割られる数	2で割った時の商	あまり
77	38	1
38	19	0
19	9	1
9	4	1
4	2	0
2	1	0

答えは1001101です。

「0」とは

0とはどのような存在か、考えたことはあるでしょうか。

我々の数字は、位取り記数法という考え方によって成り立っています。

これは例えば、1,2,3,...9という限られた数の数字と位(桁数)によって、文字の種類の数よりも大きな数を表現しようというものです。

位取り記数法以外の記法としてはローマ数字が代表的です。

0はそれ自体は量を持たない数ですが、その位に「量がない」ことを示しているのです。

「10000」などのように、我々は量がない部分のスペースを0で表現しています。

ベクトルと類似度

ベクトルの考え方が活躍する例をご紹介します。
ベクトルを用いることで、ある物の特徴を表現することができます。

例えば、以下のようにキャラクターの特徴が表されたとします。

特徴	キャラクターA	キャラクターB	キャラクターC
身長	11	8	13
横幅	4	4	5
色	3	6	4

この時それぞれのキャラクターの特徴は3次元のベクトルとして表されたことになり、それぞれのベクトルの類似度を計算することができます。

それぞれの特徴ベクトルを$\boldsymbol{a}$,$\boldsymbol{b}$,$\boldsymbol{c}$とすると、

\boldsymbol{a}=\begin{pmatrix}11 \\ 4 \\ 3 \end{pmatrix},
\boldsymbol{b}=\begin{pmatrix}8 \\ 4 \\ 6 \end{pmatrix},
\boldsymbol{c}=\begin{pmatrix}13 \\ 5 \\ 4 \end{pmatrix}

となります。
類似度は一般的にはそれぞれの内積を計算し、ベクトルの距離を表すノルムで割ることで算出されます。コサイン類似度と呼ばれます。

$\boldsymbol{a}$と$\boldsymbol{b}$の類似度は

\cos(\boldsymbol{a},\boldsymbol{b}) = \frac{\boldsymbol{a} \cdot \boldsymbol{b}}{\|\boldsymbol{a}\| \|\boldsymbol{b}||} = \frac{\sum_{i=1}^{n} a_i b_i}{\sqrt{\sum_{i=1}^{n} a_i^2} \cdot \sqrt{\sum_{i=1}^{n} b_i^2}}

で計算されます。$n$は次元数で、先ほどのキャラクターの例では3になります。

先ほどの例で実際に計算してみましょう。

\boldsymbol{a} \cdot \boldsymbol{b} = 122

\|\boldsymbol{a}\| = 12.083..

\|\boldsymbol{b}||= 10.770..

\cos(\boldsymbol{a},\boldsymbol{b})=0.93..

類似度はかなり高いと言えます。

特徴ベクトルは自然言語処理の特徴表現にてよく使われます。embeddingと呼ばれます。

微分

微分でやっていることをざっくり説明します。
基本的な考え方は、「変化の割合を捉える」ことです。

このグラフでは、
$y=x^2$を表す青い線の、$x = 2$における接線を表しています。
ここで言う接線の傾きは変化の割合($y=x^2$がどのくらいの割合で増えているか)を示しています。

青い線の$y=x^2$を微分すると$y'=2x$であり、任意の$x$における傾きを求めることができます。

つい初学者は計算方法から入りがちだと思うのですが、正直エンジニアにとって計算方法を学ぶことにあまり意味はないと思っています。

計算前と計算後で何をしているのか、出てきた関数が何を意味しているのかが重要です。

積分

数学的な意味は置いておいて、最も使う考え方は「面積を求めること」です。
この後に登場する確率分布を考える際に、分かっていると楽になります。

このグラフにおける面積の計算は以下のようになります。

\int_{0}^{2} x^2 \, dx = \left[ \frac{x^3}{3} \right]_{0}^{2} = \frac{2^3}{3} - \frac{0^3}{3} = \frac{8}{3}

極限

ある数値に限りなく近づいたり、無限大に発散するときの関数の挙動を考えるものです。

\lim_{{x \to +0}} \log(x) = -\infty

このように対数関数の$x$について、$x>0$と定義されているため$x=0$について考えることはできませんが、限りなく0に近い時の挙動については考えることができます。

先ほどの対数の例では、$x$が0に近づくと$y=log(x)$の値は$-\infty$に発散します。

双曲線関数

三角関数で勉強したsin,cosによく似た性質を持つ関数で、工学的にも様々な場所で使われます。

\sinh(x) = \frac{e^x - e^{-x}}{2}

\cosh(x) = \frac{e^x + e^{-x}}{2}

\tanh(x) = \frac{\sinh(x)}{\cosh(x)} = \frac{e^x - e^{-x}}{e^x + e^{-x}}

グラフの概形は以下のようになります。

$\cosh(x)$は懸垂線と呼ばれ、ひもを垂らしたときの形がこの関数に従います。

また、機械学習で用いられるシグモイド関数は$\tanh(x)$を使って表すこともできます。

三角関数の時は

\sin^2(x) + \cos^2(x) = 1

1 + \tan^2(x)=\frac{1}{\cos^2(x)}

で表された相互関係も

\cosh^2(x) - \sinh^2(x) = 1

1 - \tanh^2(x)=\frac{1}{\cosh^2(x)}

と非常によく似た形になります。

分散と標準偏差

「受験の時の覚えにくいやつ」として避けてきた方もいるのではないでしょうか？
データを扱うエンジニアにとっては覚えておきたい知識であり、慣れれば簡単の代表例でもあります。

分散も標準偏差も、「データのばらつき具合」を示す値で、主にデータ同士を比べる時に使います。

分散は$\sigma^2$、標準偏差は$\sigma$で表されます。平均値を$\mu$、データ数を$N$とするとき、

\sigma^2 = \frac{\sum_{i=1}^{N} (x_i - \mu)^2}{N}

\sigma = \sqrt{\frac{\sum_{i=1}^{N} (x_i - \mu)^2}{N}}

日本語で、「それぞれのデータから平均値を引いたものを二乗して、全部足してデータ数で割る」と覚えた方が早いかもしれません。

この標準偏差はデータの要素の数値の大きさに比例してしまうことが多いので、そこを考慮する必要があります。

変動係数

標準偏差を平均値で割った値のことです。

CV = \frac{\sigma}{\overline{x}}

先ほど述べた「この標準偏差はデータの要素の数値の大きさに比例する」際に、相対的にデータのばらつき具合を評価することができる値です。

データの標準化

異なる性質を持ったデータでも、平均値と標準偏差を使って比較できるようにすることができます。

テストの点数と1日の勉強時間の例で考えてみましょう。

特徴	A君	B君	C君
英語	82	72	78
国語	70	80	78
数学	90	78	66
1日の勉強時間(min)	186	122	164

これらから、平均値と標準偏差が求まります。

特徴	平均値	標準偏差
英語	77.33	5.03
国語	76.00	5.29
数学	78.00	12.00
勉強時間	157.3	32.52

標準化する時の式は平均値を$\mu$、標準偏差を$\sigma$とすると

\frac{X-\mu}{\sigma}

特徴	A君	B君	C君
英語	0.93	-1.06	0.13
国語	-1.13	0.76	0.38
数学	1.00	0.00	-1.00
勉強時間	0.88	-1.09	0.21

テストの点数と勉強時間は単位も異なり性質の違うデータですが、直接比較することができました。

0が平均、平均より高ければ正、平均より低ければ負の値を取ることがわかります。

データの分析をしたり、機械学習モデルを扱う際には必須の知識です。

偏差値

標準化を利用した考え方に偏差値があります。
計算方法は先ほどの標準化の式に10をかけ、50を足すだけです。

特徴	A君	B君	C君
英語	59.3	39.4	51.3
国語	38.7	57.5	53.8
数学	60.0	50.0	50.0
勉強時間	58.8	39.1	52.1

「偏差値は100を超えることがある」という話はトピックとして有名ですね。

相関係数

データとデータの相関を-1から1で表す値です。
それぞれの標準偏差と、共分散から算出します。

r_{xy} = \frac{\frac{1}{N}\sum_{i=1}^{n} (x_i - \bar{x})(y_i - \bar{y})}{\sqrt{\frac{1}{N}\sum_{i=1}^{n} (x_i - \bar{x})^2} \sqrt{\frac{1}{N}\sum_{i=1}^{n} (y_i - \bar{y})^2}}

この時分母は先ほど紹介したxとyの標準偏差をかけたもの。
分子の共分散は「xとyそれぞれ、データから平均値を引いたものをかけて、全て足し合わせたもの」です。

この時標準偏差は必ず正の値になりますが、共分散は負の値を取ることがあります。
そのため負の相関がある際には相関係数の値は負になります。

以下のデータで計算してみましょう。

生徒	A君	B君	C君	D君	E君	F君	G君	H君
勉強時間 (時間)	5.5	3.0	6.0	2.5	4.5	7.0	3.5	5.0
英語の点数	72.0	50.3	80.1	55.5	67.4	75.6	59.7	71.2

平均と標準偏差を求めます。

	平均	標準偏差
勉強時間	4.62	1.45
英語の点数	66.47	9.68

r_{xy} = \frac{13.01}{1.45\times9.68}=0.93

強い相関があることが分かりました。このデータの散布図は以下になります。

確率変数と確率分布

様々な値を取るような現象がある時、取りうる値全体を確率変数として表現します。

例えばサイコロの出目について考える時、確率変数は

X = 1,2,3,4,5,6

となり、それぞれについて発生する確率は等しく、

P(X) = \frac{1}{6}

です。

これらを分布として表現したものを確率分布と言います。

離散型と連続型

先ほどの確率変数$X$のように、はっきりと値が分かれていることを離散的であると言います。
対照的な考え方として、境目がない続いている性質のことを連続的であると言います。

エンジニア業界でよく用いられる言葉として、質的・量的と同じような意味だと考えてよいでしょう。

以下の上のグラフが離散型、下のグラフが連続型とイメージしてもらえるとよいです。

期待値

1回の試行において得られる値の平均値のことです。
例えばサイコロは1から6までそれぞれ同じ確率で出るので、出目の期待値は

\frac{1+2+3+4+5+6}{6} = 3.5

と求められます。ちなみにこの例は離散型確率変数の期待値の例であり、求め方は

確率変数$X$が$x_i$の時の確率を$p_i$とすると、

E(X)=\sum_{i=1}^{n}p_ix_i

です。連続型確率変数における期待値は以下のとおりです。

E(X) = \int_{-\infty}^{\infty} x f(x) \, dx

正規分布(ガウス分布)

ある測定を限りなく多く行った際の、誤差を含んだ計測結果が従う分布のことです。
天文学に用いるデータを測定していたガウスが発見しました。

データの平均$\mu$、標準偏差$\sigma$を用いて

f(x) = \frac{1}{\sqrt{2 \pi \sigma^2}} \exp \left( -\frac{(x - \mu)^2}{2 \sigma^2} \right)

と表せます。

平均値0、標準偏差1の正規分布のグラフは以下のグラフのように分布します。

大数の法則

「試行回数を増やすほど、試行の結果計測された確率は、理想的な確率の値に近づく」
という法則のことです。

サイコロの出目の例が有名です。
サイコロを1回投げた時の出目を記録する時、期待値は3.5になります。

サイコロを2回投げた時の平均値
サイコロを10回投げた時の平均値
サイコロを1000回投げた時の平均値

それぞれランダムにサイコロを投げた時の結果をヒストグラムにしてみましょう。

試行回数が多いほど、真の平均値である3.5に近づいていることが分かります。

ちなみにこのグラフはどんどん正規分布の形に近付いていることがわかりますが、この性質を説明したものを中心極限定理と言います。

モンテカルロ法

大数の法則を利用して、事象が起こる確率や未知の値を求める手法です。
最も有名である円周率を求める方法を紹介します。

この方法は、

正方形の面積S = 直径R \times 直径R

円の面積S = \frac{直径R}{2} \times \frac{直径R}{2} \times \pi

ゆえに

円の面積 = \frac{\pi}{4}\times正方形の面積

が成り立つことを利用しています。

以下に簡単な手順を示します。

x座標、y座標がそれぞれ-1~1の範囲に、ランダムに点をプロットします。
それぞれの点について、中心$(0,0)$からの距離を計算し、半径1の円の中にあるか否かを判定します。
(円内の点の数$\times$4)$\div$(全ての点の数)が円周率となります。

大数の法則より、プロットする点の数が多ければ多いほど算出される円周率の値は真の値に近づきます。

ちなみに10000個の点をプロットした上の図では、3.1576...と推定されました。

ランダムな点プロットするだけで円周率が推定できるのは面白いですね。

ベイズの定理

事象が発生した時に、その事象がある条件に依存している確率を求めることができます。

P(A|B) = \frac{P(B|A) \cdot P(A)}{P(B)}

$P(A|B)$は事象$B$が起きた時のAが起きる条件付き確率です。

例えばABテストにおいて、新しいパターンが従来のバージョンよりも優れている確率を算出できます。

時系列分析

株価や気温など、横軸を時間とするデータの分析です。
一定の期間の平均を取って表示する移動平均法がよく用いられます。

ばらつきのあるオリジナルデータを、期間を指定した移動平均を表示させることで、データの特徴を把握することができます。

マルコフ連鎖（マルコフ過程）

確率によって状態が遷移していくモデルのことです。

天気の例で考えてみましょう。
「晴れ」「曇り」「雨」の3つの状態があり、それぞれ次の日の天気に遷移する確率を次のように確率します。

現在の天気	晴れ	曇り	雨
次の日が晴れ	0.6	0.3	0.3
次の日が曇り	0.4	0.4	0.1
次の日が雨	0.2	0.3	0.4

このような遷移確率を仮定し、次の日の天気、またその次の日の天気...という風に計算していきます。

このように「次の状態は現在の状態にのみ依存する」という性質をマルコフ性と呼びます。
モンテカルロ法と組み合わせて使われる場合が多いです。

エンジニアにとっては、webページの訪問者のページ遷移など状態遷移のあるシステムをモデル化する際に使えます。

確率分布一覧

正規分布が最も重要な確率分布であり、それ以外は一般的にあまり目にかかることがないと思います。
こんな確率分布が世の中には存在するよという代表的なものをいくつか紹介します。

連続一様分布：全て同じ値の分布
二項分布：ベルヌーイ試行を$n$回行った時のある事象が起こる回数の分布
ベルヌーイ分布：二項分布の$n=1$における分布
多項分布：二項分布を一般化し、結果が$k$通りある時の事象が起こる回数の分布
指数分布：ある事象が起こるまでの時間の分布
ポアソン分布：単位時間あたりに事象が起こる確率の分布
幾何分布：ベルヌーイ試行を繰り返し、初めて成功するまでの回数の分布
超幾何分布：有限個の母集団から特定の数サンプリングし、特定の要素が出る確率の分布

詳しくは

統計学、データ解析でよくでてくる確率分布のまとめ -Qiita

統計学の時間

などで勉強するのがおすすめです。

データ分析手法のまとめ

統計的なデータ分析手法には様々な種類があります。

全て紹介しているとあっという間に記事の内容がパンパンになってしまうため、今回は一覧で紹介します。

分類

階層クラスター分析
k近傍法
k平均法
判別分析
ロジスティック回帰分析
サポートベクターマシン

回帰

線形回帰分析・非線形回帰分析
- 単回帰分析・重回帰分析
主成分分析
因子分析

どちらも

ニューラルネットワーク
決定木分析
相関分析

その他

数量化理論
コンジョイント分析
ABC分析
アソシエーション分析
コレスポンデンス分析
感度分析
メタ分析

最小二乗法

グラフのプロットから、最適な直線を引く時に使われる手法です。
プロットからの距離の合計が最も小さくなる直線の傾きと切片を求めます。

a = \frac{n \sum_{i=1}^{n} x_i y_i - \sum_{i=1}^{n} x_i \sum_{i=1}^{n} y_i}{n \sum_{i=1}^{n} x_i^2 - \left(\sum_{i=1}^{n} x_i\right)^2}

b = \frac{\sum_{i=1}^{n} y_i - a \sum_{i=1}^{n} x_i}{n}

これらの式は共分散や分散で考えることもできます。

線形回帰分析の理想的な直線を引く時にも使われます。

この考え方を拡張して、多次元や非線形の近似方法もありますので興味のある方は調べてみてください。

交差検証

交差検証（Cross-Validation）は、機械学習モデルやデータ分析モデルの性能を評価する手法の一つです。

データセットを$k$個に分割し、分割したうちの1つをテストデータ、それ以外を学習データとする検証を$k$回行います。

それぞれにおけるスコアを平均し、最終的なモデルのスコアとして評価します。

浮動小数点数

2進数を扱うコンピュータが「小数」をどのように扱っているのか、理解できていますか？

浮動小数点数では、符号・仮数・基数・指数に分けて値を格納しています。

詳しく知りたい方は、こちらの記事が非常に分かりやすいので読んでみてください。
「0.1+0.2≠0.3」を説明できないエンジニアがいるらしい -Qiita

文字コード

我々が扱っている文字は、コンピュータ内部ではバイナリデータとして扱われ、相互に変換する必要があります。例えばAは01000001などです。

文字コードは、相互に変換する文字の対応や規則を定めたものです。
代表的なものとしては以下のようなものがあります。

ASCII
最も基本的な文字コードです。7ビットのバイナリ値を使ってアルファベットや数字、記号など128個の文字を表します。

UTF-8
多くの言語を一つの文字コードで扱えるようにしたUnicodeの一つです。Unicodeの規則を8ビット(1バイト)単位で表します。

Shift_JIS
日本語を扱うための文字コードの一つです。システム実装においては互換性の問題が生じやすい文字コードの一つです。

詳しくは以下の記事が詳しく解説されています。
新人さんに知ってほしい「文字コードのお話」-Qiita

探索アルゴリズム

対数計算が登場する、エンジニアにとって最も聞き馴染みのあるであろうアルゴリズムです。
詳しい仕組みは割愛しますが、計算量を定量的に推定することができます。

有名なものとしては、

全探索
bit全探索
順列前探索
二分探索
三分探索
枝刈り全探索
ハッシュ探索

などがあります。

全てのパターンを試すシンプルな全探索においては、計算量は$O(N)$（データ数$N$に比例する）
整列させたデータ群を二つに分ける二分探索においては、$O(log_2N)$となります。

詳しくはこちらのQiita記事が非常に分かりやすいので読んでみてください。

アニメーションで理解する探索アルゴリズム
 たのしい探索アルゴリズムの世界【前編：全探索、bit全探索から半分全列挙まで】

Antsの問題

競技プログラミング界で最も有名な問題と呼ばれている問題です。

99cmの棒の上に100匹の蟻が、1cm感覚で向かい合っており、この状態からすべての蟻が秒速1cmで移動を始めます。

左端の蟻は右側を向いており、隣は左、その隣は右、...右端の蟻は左側を向いています。
蟻同士がぶつかった時、即座に反対方向へ折り返します。
蟻が棒の端へ到達すると、棒から落ちます。

この時、蟻が移動を始めてから最後の蟻が棒から落ちるまでには何秒かかるでしょうか？という問題です。

この問題、単純なプログラムを書こうとすると計算量が膨大になります。
しかし、工夫をすることによって単純な問題へと置き換えることができるんです。

それは、

全ての蟻を区別せず、「蟻同士がぶつかる」→「蟻同士がすり抜ける」と捉えることです。

蟻同士を区別しないことで、直線上ではこれが同じ現象として捉えることができるようになります。

考え方を工夫することで、圧倒的に計算を単純にすることができる例として非常に有名です。

黄金比・白銀比

ご存知、人間が美しいと感じる比率のことです。
黄金比は1:1618, 白銀比は1.414です。
正確にはそれぞれ

黄金比率=1+\frac{\sqrt{5}}{2},白銀比率=\sqrt{2}

です。

使われている有名なものとしてはピラミッドやミロのヴィーナス、アップルのロゴなどが挙げられます。

現代でよく使われるアスペクト比の16:9も黄金比に近い比率です。

実はこの記事に使われている全てのグラフの縦横比も黄金比に近い8:5で作られています...

グラフ理論

頂点とそれらを結ぶ辺の集合を扱う数学的な理論です。
この記事でも登場するヒストグラムや折れ線グラフなどとは別物です。

以下の図はグラフと言うことができます。

経路問題、ネットワーク、化学構造など様々な問題について考えることができるようになります。

コンピュータ上でも隣接行列を用いて計算することができます。

全てを紹介することはできないので、グラフ理論に含まれる重要な要素を紹介します。

無向グラフと有向グラフ
連結グラフと非連結グラフ
完全グラフと2部グラフ
オイラーグラフとハミルトングラフ

最短経路問題

先ほど紹介したグラフ理論において、最短の経路を求める問題です。

代表的な手法であるダイクストラ法について簡単に紹介します。

始点である駅に直接繋がっている駅への所要時間を更新する
始点から所要時間が小さい駅から順に、その駅から直接繋がっている駅への所要時間を更新する。この時、他に最短の経路がない場合は最短所要時間を確定する
全ての頂点について最短所要時間が確定するまで繰り返す。

最短経路を求めることができました。

ここでは簡単な紹介しかできませんが、以下の記事が参考になります。

初心者のためのダイクストラアルゴリズム -Qiita

1%ガチャ問題

「排出率1%のガチャにおいて、100回引いた時に当たる確率はいくらか？」
こちらの実際の値が直感に反して低いことで有名な問題です。

確率における余事象の考え方で計算することができます。
100回連続で外れる確率を、1から引けばよいだけです。

1-(0.99)^{100} =  0.6339...

正解は約63.4%です。

5%だとどうでしょうか？

1-(0.95)^{100} =  0.9940...

約99.4%と一気に高くなりました。これで欲しいアイテムが出なかったら流石に悲しいですね。

誕生日のパラドックス

似たような話題として、「クラスに同じ誕生日同士の人がいる確率は？」という問題があります。

時間がある方は一度考えてみてください。

「25人のクラスにおいて、同じ誕生日同士の2人が少なくとも1組いる確率は？」

計算してみましょう。

先ほど同様、余事象である「全員の誕生日が一致しない確率」を計算します。

2人目の誕生日が1人目と異なる確率は、

1 \times \frac{364}{365}

これを繰り返すと、

1 \times \frac{364}{365} \times \frac{363}{365} \times ... \times \frac{365 - (25-1)}{365} = 0.5686...

正解は約56.9%でした！こちらも直感と反して高いですね...

最適停止問題

最適停止問題のうち最もスタンダードな形の「お見合い問題」についてご紹介します。
題材によって、秘書問題などとも呼ばれます。

「複数人のお相手と連続でお見合いしていった時、何人目で交際を申し込むと最良のお相手と交際することができるか？」という問題です。

ルール

お見合いできる全体数は決まっており、$n$人とします。
お見合いが終わったら、その場で交際するか否かを決めなければなりません。
一度断った相手との交際はできません。
交際を決めたらそれ以降のお見合いはできません。

戦略

そしてここで取る戦略ですが、はじめの$k$人を無条件で見送り、以降でそれまでの中で最も良いと思った人と交際するというものです。

この時$k$をどのくらいに設定すると最良の相手と交際できる確率が最大となるでしょうか？

結論です。

$\frac{n}{e}$人（$e$:ネイピア数,$\frac{n}{e}$:全体の約37%）を無条件で見送り、それ以降で最も良いと思った人と交際、です。

この方法を取ると、全体で最良の候補者を採用できる確率が最大となり、その確率は1/e(37%)になります。

37%の確率で最良の人と交際できるなら高い！と取る方もいれば、ここまでしても40%にも満たないのかととる方もいそうです。

証明は割愛しますが、こちらに分かりやすく記載されています。

秘書問題（お見合い問題）とその解法

72の法則

72の法則とは、投資などの話題で登場する法則です。

年の利率$r$%で資産を運用した時、元本が2倍になるまでの年数$n$は

n = 72 \div r

で計算できるという法則です。

ただし、実際に計算してみると少し違う値が出てくることがわかります。

元本$A$が、年利$r$%で$n$年後に2倍になる時、

2A = A ({1 + \frac{r}{100}})^n

これを両辺対数をとると、

\ln{2} = n \ln ({1 + \frac{r}{100}})

$\ln ({1 + \frac{r}{100}}) \risingdotseq \frac{r}{100}$と近似して、$n$について解くと

n=\frac{100 \ln{2}}{r} = \frac{69.314..}{r}

と求められました。72とは少しずれてますね。

ただ69よりも72の方が素因数が多く割りやすいため、実用的に72が使われているようです。

ピケティの不等式

経済学者のトマ・ピケティが有名な「21世紀の資本」の中で説いた、資本主義の性質についての不等式です。

現代では資産運用が一般的な概念となり、この法則を目にする機会も増えてきました。

結論から言うと、資本収益率を$r$,経済成長率を$g$とした時に

r>g

が成り立っているという不等式です。

これは「資本が増えるスピードは、経済が成長するスピードよりも速い」ことを表しており、ピケティはこの不等式を基に経済格差が広がっていることを主張しています。

歴史を振り返ってみると、局所的に見れば例外の時期はあるものの全体的に見れば$r$は大体5%、$g$は大体2%であるというのが一般的な解釈です。

そして経済成長率$g$は労働者の給与の増加率として解釈されます。

留意しておきたいのが、不等式とはいっても論理的に証明されているものではなく、過去の統計データによって「明らかである」と判断されているということです。

そのためこの記事で紹介している他のトピックとは性質が異なります。

比率の値についても多くの議論がなされているところであり、「現代において本当に成り立っていると言えるのか？」については専門家の中ではいろんな意見があります。

ナッシュ均衡

ナッシュ均衡は、「プレーヤー全員が最適な戦略を取っている状態」を指すゲーム理論における有名な考え方です。

最も有名な囚人のジレンマの例で考えます。

各場合における囚人AとBの懲役を以下のマトリクスに示します。

	囚人B: 自白	囚人B: 黙秘
囚人A: 自白	A:5年, B:5年	A:0年, B:10年
囚人A: 黙秘	A:10年, B:0年	A:3年, B:3年

自分が囚人Aの立場に立った時、囚人Bが自白を選んでも黙秘を選んでも自分は自白をした方が得をします。

それは囚人Bの立場でも同じのため、この時のナッシュ均衡は2人とも自白になります。

ちなみに、全体の利益が最大になる選択は2人とも黙秘であり、このような状態をパレート最適と言います。

ちなみにちなみに、このような選択が1回だけでなく繰り返される時、ナッシュ均衡が2人とも黙秘になることがあります。そのような状態はフォーク定理で表されます。

降水確率

降水確率がどのように算出されているか知っていますか？

まず降水確率の定義とは、「1mm以上の雨や雪が降る確率」です。

そして算出方法は、実は「過去の同じような気圧配置やその他の気象条件において1mm以上の雨や雪が降った割合」によって算出されています。

そして天気予報等では10%刻みで表示されていますが、四捨五入して表示されています。

つまり降水確率0%の時は、降水確率 $< 4 $%の時ということですね。

有限オートマトン

文字列などの特定のパターンや規則を効率的に認識し、処理するための理論です。

ここでは情報系の資格に登場するような形で紹介します。

状態遷移図

ここでは初期値は$a$、入力は {0,1} とします。

入力である {0,1} で構成される文字列(1101001など)が渡されます。
この時、状態遷移図の1,0にしたがって状態が変わります。

通常は各状態が受理状態と非受理状態が設定されており、最終的な状態がどちらかによって、入力内容が条件に当てはまっているかどうかを判定します。

以下のような状態遷移表として表される場合もあります。

状態遷移表

	0	1
a	a	b
b	a	c
c	b	c

今回の例のように次の状態が1つに定まるものを決定性オートマトンと呼び、他にも状態が複数個存在する非決定性オートマトンなどが存在します。

逆ポーランド記法（後置換記法）

数式における記法の一つであり、プログラミングの基本である「スタック」の考え方と親和性の高い記法です。

ちなみに普段我々が使っているものを中置記法と呼びます。

考え方としては、「演算子が出現した場合、スタックのトップにある値を2つ取り出して演算を行い、結果をスタックにプッシュする。」です。

さっそく例を見てみましょう。

A B C × +

これはポーランド記法で書かれた数式であり、中置記法では

A + B × C

となります。

もう少し難しい例も見てみましょう。

Y A B + C D E ÷ - × =

この数式を中置記法に直すとどうなるでしょうか。

Y = ( A + B ) × ( C - D ÷ E )

BNF記法

BNF（Backus-Naur Form）記法は、文法や構文を定義するために使用される表記法です。
情報系の資格では以下の形で登場します。

\langle R_0 \rangle~::=~0~|~4~|~8

\langle R_1 \rangle~::=~1~|~5~|~9

\langle R_2 \rangle~::=~2~|~3~|~6~|~7

\langle A \rangle~::=~\langle R_0 \rangle~|~\langle A \rangle \langle R_0 \rangle~|~\langle B \rangle \langle R_1 \rangle~|~\langle C \rangle \langle R_2 \rangle~

\langle B \rangle~::=~\langle R_1 \rangle~|~\langle A \rangle \langle R_1 \rangle~|~\langle B \rangle \langle R_2 \rangle~|~\langle C \rangle \langle R_0 \rangle~

\langle C \rangle~::=~\langle R_2 \rangle~|~\langle A \rangle \langle R_2 \rangle~|~\langle B \rangle \langle R_0 \rangle~|~\langle C \rangle \langle R_1 \rangle~

$::=$は定義記号で、左の記号を右の式で定義することを表しています。
$~|~$は論理記号の「または」です。

この時、$\langle R_1 \rangle,\langle R_2 \rangle,\langle R_3 \rangle$はこれ以上分解できない記号であり、終端記号と呼ばれます。

対して$\langle A \rangle,\langle B \rangle,\langle C \rangle$は分解できる記号であり、非終端記号と呼ばれます。

問題例

例として、"123"という文字列が非終端記号$\langle A \rangle$から生成されることがあるかどうかを見ていきます。

まず一番右側の文字列は$\langle R_2 \rangle$で定義される"3"であるため、$\langle A \rangle$の定義から右側が$\langle C \rangle$$\langle R_2 \rangle$で確定します。
次の"2"も$\langle R_2 \rangle$で定義されるため、$\langle C \rangle$の定義から$\langle A \rangle$$\langle R_2 \rangle$$\langle R_2 \rangle$に確定します。
ここで$\langle A \rangle$の定義から文字列は$\langle R_0 \rangle$$\langle R_2 \rangle$$\langle R_2 \rangle$に確定しますが、これは"123"を満たしません。

よって"123"という文字列が$\langle A \rangle$によって生成されることはありません。

まとめ

お疲れ様でした。ここまで読んでみていかがだったでしょうか。

ざっくり

数学の基礎
統計の基礎
エンジニア知識の基礎
知っていると人生が豊かになりそうな数学知識

の順に紹介しました。

特に後半のトピックについては、「面白いな」と感じられるようなものが多かったと思います。

スペースの都合上厳密性に欠ける部分もあり恐縮ですが、皆さんが楽しく勉強できる時間になっていれば幸いです！