数学

数学

対数の特徴 †

log(M*N) = log(M) + log(N)
log(M/N) = log(M) - log(N)
log(M^p) = p * log(M)

底の変換公式
log(a)b = log(c)b/ log(c)a
(a,b,c が正の数で、a != 1, c != 1)

ド・モルガンの法則 †

!(A | B | C) = !A & !B & !C
!(A & B & C) = !A | !B | !C
(| : 論理和, & : 論理積, ! : 否定 とする。)

等差数列 †

どの隣り合う2つの項も“共通して一定な”差（common difference; 公差）になっている数列のこと。

例 (1, 2, 3, 4, 5) (2, 5, 8, 11, 14)

初項 a，項数 n，末項 e の等差数列の初項から第 n 項までの和 Sn は
Sn = n(a + e) / 2

この式に、初項 1。末項 n。項数 n をあてはめると、1 から n までの和である
和の公式 n(n + 1) /2
を得ることができる。

等比数列 †

数列で、隣り合う二項の比が項番号によらず一定であるようなものである。
その比のことを公比（こうひ、英:common ratio）といい、記号 r で表す。

例 (4, 12, 36, 108)

初項 a, 項数 n, 項比 r の等比数列の初項から第 n 項までの和 Sn は
r != 1 ならば、
 Sn = a(1-r^n) / (1-r)
r == 1 ならば、
 Sn = na

[証明]
Sn = a + ar + ar^2 + ar^3 + ar^4 + … + ar^(n-1)
両辺に r をかけると
rSn =    ar + ar^2 + ar^3 + ar^4 + … + ar^(n-1) + ar^n
最初の式から2番目の式を引くと
Sn -rSn = a - ar^n
式を変形
Sn(1-r) = a(1 - r^n)
Sn =  a(1 - r^n) / (1 -r)
となる。

数字根 †

数字根(すうじこん)とは、数値を各桁に分解して足し、足した数値へ同様の操作を繰り返し、最終的に得られる1桁の数値のこと。

例えば 56 ならば、
5 + 6 = 11
10以上の場合さらに各桁を足し、1桁の数値を求める。
1 + 1 = 2
つまり、56の数字根は2になる。

数字根を効率的に求めるには、各桁の数値を足すさいに、9と足して9になる数値は除外する。

例:
95421 の数字根を求める。
9 + 5 + 4 + 2 + 1
この式から、
9と、足して 9 になる部分を除外する。
先頭の9 と、5 + 4 のペアは9になるので除外し、2 + 1 だけが残る。
よって、数字根は3。

九去法 †

数字根を使って、加算や乗算結果を簡単に検算する方法。
九去法という名称は、数字根を求める計算過程で 9 を無視することを意味している。

加算 †

以下の計算結果が正しいかチェックする。
12 + 34 + 56 = 102
各項の数字根を求める。
12 => 3
34 => 7
56 => 2
これらの数値の和から、さらに数字根を求める。
3 + 7 + 2 = 12 => 3
計算結果の 102の数字根を求める。
102 => 3
計算が正しければ、2つの数値は一致する。

乗算 †

以下の計算結果が正しいかチェックする。
12 * 34 * 56 = 22848
各項の数字根を求める。
12 => 3
34 => 7
56 => 2
これらの数値の積から、さらに数字根を求める。
3 * 7 * 2 = 42 => 6
計算結果の 22848の数字根を求める。
22848 => 6
計算が正しければ、2つの数値は一致する。

素数 †

エラトステネスの篩（ふるい） †

1からn までの範囲の素数を求める。
1は素数ではないので除き、2から n まで順番に数を並べた数値の順列を作る。

2,3,4,5,6,7,8,9,10,11....n （これを探索リストとする。）

まず、探索リスト最初の数値を素数のリストに加える。
そして、その素数の倍数を探索リストから取り除いていく。

素数リスト：2
探索リスト：3,5,7,9,11....n

探索リストから、素数の倍数を取り除いたら、残っている最初の数を素数リストに加えて同様に繰り返す。

素数リスト：2,3
探索リスト：5,7,11....n

今、素数リストに p を加え、探索リストから 素数 p の倍数を取り除くとすると、
探索リストの先頭の p を除けば、2p, 3p, 4p と取り除くことになるが、
m < p とした場合、m * p は mの倍数だから、すでに取り除かれている。
よって、この時点で探索リストに残る数値 p * p 未満までは、すべて素数である。
とりのぞく必要がるのは、p*p 以上の数値となる。(探索リストの先頭の pは除く必要があるけど。）

よって 「探索リストの最大値が素数リストの最大値の平方よりも小さい場合、素数リストおよび探索リストに残っている数が素数となる。」
n以下の素数表を作る場合、nの平方根以下の素数についてのみふるえば良い。

例えば、nを24として、5を素数リストに加えて、5の倍数を探索リストから取り除いた。

素数リスト：2 3 5
探索リスト：7 11 13 17 19 21 23

この時点で、5^2 = 25 が、探索リストに残る最大値 23 より大きくなったので、
探索リストに残るのは全て素数である。

素数は無限にある。 †

ユークリッドによる証明
背理法による。
素数は有限個しかないと仮定して、
2, 3, 5, 7 ...... P(最大の素数) とする。

全ての素数を掛け合わせて、1を足した数を Q とする。
Q = 2 × 3 × 5 × 7 × .... × P + 1

Q は合成数であるか素数であるかのいずれかである。
(合成数とは、2つ以上の素数の積で表すことのできる自然数)

Q が合成数だとすると Q は 素数のいずれかを用いて積の形に表されるはずである。
その一方で Q は 素数 のいずれで割っても 1 があまり、矛盾する。

素数だとすると、これは 素数 のいずれとも異なるから素数が有限個しかないことに反する。

基数変換 †

k進数から、10進数への変換 †

それぞれの、n桁目に、k^(n-1) をかける。

 4桁目 * k^3
 3桁目 * k^2
 2桁目 * k       (k^1 = k)
 1桁目 * 1       (k^0 = 1)
-1桁目 * k^-1    (k^-1 = 1/k)
-2桁目 * k^-2

2進数から、10進数への変換 †

例:10110
2^5 + 2^3 + 2^2

16進数から、10進数への変換 †

例:AB.B2
(A * 16^1) + (B * 1) + (B * 1/16) + (2 * 1/(16^2)) =(11 * 16^1) + (12 * 1) + (12 * 1/16) + (2 * 1/(16^2))

※ヒント
16 の累乗を計算するのは時間がかかるため、2の乗数に変換したほうが計算が楽。
(16  = 2^4 であるため。）
16^3 = (2^4)^3 = 2^12 = 4096

10進数から、k進数への変換 †

整数 †

A  / k = x1 --- y1
x1 / k = x2 --- y2
x2 / k = x3 --- y3
x3 / k =  0 --- y4 ↑下から並べる。
        (↑ 0になるまで繰り返す。)
(y4) (y3) (y2) (y1) と並べた値が答え。
10進数から 16進数への変換 などでは、y の値は 0～15 になるので、0～ Fの文字に変更して並べる。

小数(方法1) †

例:0.8125 を2進数に変換する。
0.8125 * 2 = 1.625
 (↓小数部のみを 持ち越す)
0.625  * 2 = 1.25
0.25   * 2 = 0.5
0.50   * 2 = 1.0    ↓整数部を上から並べる。
              (↑小数部が0になるまで繰り返す。）
答え： 0.1101

小数(方法2, ただし 2,8,16 進数の場合のみ） †

整数部は、上の方法で変換。
小数部は、分数に変更する。
例:0.8125 を 2進数へ変換する。
分数にする。8125/10000
通分して  13/16
8/16  + 4/16 +1/16 に展開。
これを2進数に変換して
0.1101
(8進数、16進数の場合は、以下の方法でさらに変更。)

2進数と、8進数, 16進数 の相互変換 †

これらは、相性がよく効率よく変換できる。 (ただし、16進数と8進数の相互変換は、特に効率的な方法はなく、1度2進数に変換して行う。)

2進数から、8進数への変換 †

例:10101.00101
3桁ずつに区切る。
10 101.001 010 (←最後の足りない0は補う！
 2   5.  1   2
 = 25.12 

2進数から、16進数への変換 †

例:10101. 001011
4桁ずつに区切る。
1 0101. 0010 1100 (←最後の足りない0は補う！
1    5.    2    C
15.2C

16進数から、2進数への変換 †

例:AB.CD
各桁を4桁に変換
AB.CD
1010 1011. 1100 1101

8進数から、2進数への変換 †

例:27.24
各桁を3桁に変換
27.24
010 111.010 100

待ち行列理論(M/M/1モデル) †

待ち行列理論のモデルはケンドール記号によって以下のように表現される。

到着分布 / サービス時間分布 / 窓口の数(行列の長さ制限)

ここでは、M/M/1(∞)について表記する。

到着分布 M

ランダムに到着(ポアソン分布)

サービス時間分布 M

1人の客がサービスを受ける時間はバラバラ(指数分布)

窓口の数 1

サービスを行う窓口は1つ

行列長 ∞

待ち行列長は十分長くあふれることはない。

平均到着率 †

単位時間当たりに到着するトランザクション数。記号λ(ラムダ)で表す。

平均到着間隔 †

前のトランザクションから、次のトランザクションまでの平均時間。

平均到着間隔 = (1 / 平均到着率) = (1/λ)

平均サービス率 †

単位時間当たりにサービス可能なトランザクション数。記号μ(ミュー)で表す。

平均サービス時間 †

1トランザクションがサービスを受ける平均時間。

平均サービス時間 = (1/平均サービス率) = (1/μ)

利用率(トラフィック密度) †

単位時間に窓口を利用している割合。記号ρ(ロー)で表す。

利用率(ρ) = (平均サービス時間 / 平均到着間隔) = (平均到着率 / 平均サービス率)

平均待ち時間 †

サービスを受けるまでの待ち時間

平均待ち時間(Wq) = ρ/(1-ρ) * 平均サービス時間

平均応答時間 †

サービスを受ける時間を含めた全処理時間

平均応答時間(Ww) = 平均待ち時間 + 平均サービス時間
                 = ρ/(1-ρ) * 平均サービス時間 + 平均サービス時間
                 = 1/(1-ρ) * 平均サービス時間