Katsuo Pages

Katsuoのサイト

View My GitHub Profile

応用情報技術の勉強ノート

応用情報の勉強ノートを書いていく。
応用情報の参考書の2周めに入って最初の方のページを見たら勉強したことをすっかり忘れているので
ノートを書く。

試験についてのことはほとんど把握しないままに試験勉強を続けてきたが、勉強を続けていると、自然とどこまでやればいいのか
把握できていないことが終わりのなさに繋がり、漫然と勉強だけを続けることになってしまう不安を感じたので、試験勉強のはじめの
段階でしっかり把握しとくべき。

試験形式と時間、出題範囲をしっかりと目次のように把握しておくことで、何をどのくらい対策すれば
いいのかが分かりやすくなるので、また、勉強を続けるうちに、目次と内容のように有機的な記憶のつながりにもなる。

ここを押さえないで勉強していたので、この知識が何の分野のどういう知識なのかが有機的に記憶の中でつながっていない、ランダムな
バラバラな知識のようになってしまっているので、最初に出題形式と試験時間、出題範囲をしっかりと把握するためにこれらを記載していく。

シラバスを読んでおき、本に載っていない知らない内容については調べていく。…2022-09-17今更だけど追記


出題形式と試験時間に対してどれだけタスクがあるかを表している。

午前問題と午後問題がある。
午前：9:30～12:00 の2時間30分、80問解答する。
午後：13:00～15:30 の2時間30分、11問から5問を選んで解答する。

午前の試験範囲

分野を大きく分けると、テクノロジ系、マネジメント系、ストラテジー系の3つの分野がある。

テクノロジー系

テクノロジー系は、大きく分けて4つの分野がある。

4つの分野：基礎理論、コンピュータシステム、技術要素、開発技術

基礎理論

勉強してきて、難しく感じるしすぐ忘れるので、しっかりと基礎を繰り返し勉強するとともに、計算は勉強するだけじゃ過去問が解けない場合が多く感じたので、
過去問を通じて勉強しきちんと解けるようにする。

コンピュータシステム

技術要素

開発技術

以上がざっくりしたテクノロジー系の4つの分野と出題範囲


マネジメント

マネジメントは分野としてプロジェクトマネジメント、サービスマネジメントがある。

プロジェクトマネジメント

サービスマネジメント

結構細かなことやちゃんと覚えていないと解けないような問題が多いので、マネジメントも過去問をしっかりとやっていくのと同時に、
繰り返しの復習で慣れていく。

散発的な知識になって頭を整理できていないので、体系的に整理して覚えていく。


ストラテジー

ストラテジーの分野としてシステム戦略、経営戦略、企業と法務の3つがある。

システム戦略

経営戦略

企業と法務

以上が午前問題のざっくりとした出題分野と範囲


午後の出題範囲

午後問題は11問から5問を選択する。5問のうち、情報セキュリティは必須項目なので、残り4つを選択することになる。
5問の配点は、各20点となっている。

11個の分野は次の通り。

午後問題の5つの分野を選択

点の取りやすさや習得の難易度などからおすすめされているものをそのまま選ぶことにした。
情報セキュリティは必須なので、残り4つを選ぶことになる。


選択についての検討項目

2023年2月に見かけた情報によると、下記がお勧めされている(上からおすすめ順)。

同位のストラテジ系、システムアーキテクチャ、サービスマネジメントの３つの問題を当日見て、
一番難しいもの1つを除く2つを選択して解くという流れ。


論理と集合

論理演算とは、0,1の2つの値で演算をすること。

論理演算は集合で考えると分かりやすい。論理演算は0をfalse,1をtrueに関係付けて、集合のベン図で考えると意味が理解できる。

論理演算には0と1を演算する種類として、論理和、論理積、排他的論理和、論理否定という演算があり、

論理和はOR, 論理積はAND, 排他的論理和はXORまたはEOR, 論理否定はNOTが演算の表現となる。また、演算子は下記となっている。

論理和はx+y, 論理積はx・y, 排他的論理和はx$\oplus$y,論理否定はx$\lnot$


論理演算の結果

x,yが0または1の値をとるとき、論理演算の結果は次のようになる。

集合の演算と論理演算は同じなので、ベン図を利用することで、論理演算の計算方法が理解できる。
0はfalseなので空という意味に関連付けてベン図を塗りつぶさず、1はtrueと関連付けて集合が存在するとし、ベン図を塗りつぶすと考える。


論理和

x,yのいずれかが1のとき1になる。
「論理和の計算方法＝和集合を求めることと同じ」と覚えておく。

ベン図で考えるとわかりやすい。集合の演算においてxとyの和集合を求めることを論理和x+yに対応させている。 和集合のベン図で考えるとx,yの少なくとも片方が1であれば1となる。


論理積

xもyも両方とも1のとき1になる。
「論理積の計算方法＝積集合(共通部分)を求めることと同じ」と覚えておく。

集合の演算においてxとyの積集合(xとyの共通部分)を求めることを論理積x・yに対応させている。

ベン図で積集合で考えると、xまたはyが0であると、xまたはyの集合が空ということになり、共通部分が存在しない。
そのため、xもyも1でどちらも集合存在する状態じゃないと積集合自体が存在しないので、論理積はxもyも1のときだけ1となる。


排他的論理和

分かりにくくて理解に時間がかかるので注意する。
xかyのどちらかだけ1のとき1になる。
論理和に”排他的”という条件を加えたものと考える。
集合のベン図で考えると、xとyの共通部分を除いたxまたはyの部分が排他的論理和に該当する。

ベン図のように集合xとyがあるとして、xもyも1だと、xとyの共通部分が存在することになるので、それだとxから見てyの要素も含まれて排他的ではなくなる。
逆の場合も同様。なので、xかyのどちらか一方だけ1のとき、排他的論理和は1となる。つまり、例えばxが1でyが0のとき排他的論理和が1になるとは、
排他的論理和はx=1そのものを表している。

また、xもyも0だと、そもそも排他的なもの自体が存在しないので、排他的論理和の出力は0となる。

排他的論理和


論理否定

論理否定は集合のベン図をイメージすると簡単にわかりやすい。
集合xの否定は$\overline{x}$と表現する。


論理演算の基本公式(法則)

一見すると普通の四則演算と同じ足し算、掛け算の記号なので四則演算の計算と勘違いしないように注意が必要。

論理演算の基本公式(法則)として、0と1の演算、同一の法則、交換法則、結合法則、分配法則、吸収法則、ド・モルガンの法則がある。

0と1の演算

0と1の演算の基本公式は、論理和、論理積を行う時の性質のこと。
これは当たり前すぎるし短い式なので別にわざわざ覚える必要はない。

$x\cdot0 = 0$

xが0でも1でも結果は0になることを表している。
論理積なので、x,yのどちらかが0のときは論理積は0になる。x,yの両方とも1のとき1になるから。


$x\cdot1 = x$

上記は、xの論理積の対象が1、つまりこれをyとすると、y=1ならば、xの値がそのまま論理積の結果になることを表している。
論理積なのでx=0のときは$0\cdot1=0$,x=1のときは$1\cdot1=1$になる。


x+0=x

論理和なので少なくともx,yのどちらかが1だったら結果は1になる。
y=0なのでx=0だったら結果は0、x=1だったら結果は1になる。


x+1=1

論理和なので少なくともx,yのどちらかが1だったら結果は1になる。
y=1なのでx=0か1にかかわらず結果は1になる。


同一の法則

同一の法則とは、同じ値同士の論理和、論理積はそのままその値が出力されることを表している。
xに対して論理和、論理積を実行するとxの値がそのまま演算結果となる性質のこと。

$x \cdot x=x$

論理積なので、x=0のときは$0\cdot0=0$,x=1のときは$1\cdot1=1$になり、xの値がそのまま結果となる。


x+x=x

論理和なので、x=0のときは0+0=0, x=1のときは1+1=1になり、xの値がそのまま結果となる。


交換法則

$x \cdot y = y \cdot x$

x+y = y+x

これはxとyの位置を交換しただけで、右辺と左辺は同一であることを表している。


結合法則

論理積の結合法則とは、x,y,zの3つの変数からなる論理積についての性質
x,y,xの3つの集合で考えると法則が成り立つ理由を理解できる。
最終的には式だけ覚えて法則を演算に利用できればいいが、性質が成り立つ理由を理解しておく。

$x \cdot (y \cdot z) = (x \cdot y) \cdot z$

左辺：xと(y,zの論理積)の論理積
x=0, y=1, z=0とすると、$x \cdot (y \cdot z) = 0$

右辺：(x,yの論理積)とzの論理積
左辺と同様にx=0, y=1, z=0とすると、$(x \cdot y) \cdot z = 0$

以上のような要領で、x,y,zすべての値の組み合わせで(左辺) = (右辺)が成立する。
これを結合法則と呼ぶ。

集合で考えてみれば、式はx,y,zの3つの集合のうち2つの集合の論理積と残り1つの集合の論理積を表しているが、結局はx,y,x3つの論理積を
求めることと同じ。結局はx,y,zの3つの集合の共通部分を求めることと同じなので、式のx,y,zのどれを入れ替えても演算結果は同じとなる。


論理和の結合法則とは、x,y,zの3つの変数からなる論理和についての性質

x+(y+z) = (x+y)+z

左辺：xと(y,zの論理和)の論理和
x=0, y=1, z=0とすると、x+(y+z)= 0+1=1

右辺：(x,yの論理和)とzの論理和
左辺と同様にx=0, y=1, z=0とすると、(x+y)+z = 1+0=1

以上のような要領で、x,y,zすべての値の組み合わせで(左辺) = (右辺)が成立する。

集合で考えると、x,y,zの3つの集合の和集合を求めている。


分配法則

分配法則には2種類のパターンがある。

1) $x \cdot (y + z) = (x \cdot y) + (x \cdot z)$

x=1, y=0, z=1とする。
左辺：xと(y,zの論理和)の論理積なので、$1 \cdot 1 = 1$となる。
右辺：(x,yの論理積)と(x,zの論理積)の論理和なので、0 + 1 = 1となる。

以上のような要領で、z,y,zすべての値の組み合わせで(左辺) = (右辺)が成立する。
これは論理演算子と普通の計算の演算子が偶然同じ意味合いの分配法則なので、普通の数学と一緒と思っておく。

下記2)は数学の分配法則と違うので、別途で覚える必要がある。


2) $x + (y \cdot z) = (x + y) \cdot (x + z)$

x=1, y=0, z=1とする。
左辺：xと(y,zの論理積)の論理和なので、1 + 0 = 1となる。
右辺：(x,yの論理和)と(x,zの論理和)の論理積なので、1 + 1 = 1となる。

以上のような要領で、z,y,zすべての値の組み合わせで(左辺) = (右辺)が成立する。

論理演算における分配法則は、 1) は$x \cdot (y + z) = (x \cdot y) + (x \cdot z)$
であり数学の普通の分配法則と同じ展開方法なので、最初の方を覚えておき、

2)の方は 1)の両辺の演算子をすべて逆にしたものなので、2)は 1)の演算子をすべて逆にしたものとして覚えておく。


吸収法則

吸収法則という名前からどんな性質かイメージしづらいので注意。
吸収法則は、(式の論理演算の結果)=(xの値)であり、式の結果が結局は1つの変数であるxの値という、1つの変数に吸収されるイメージ。

1) $x \cdot (x + y) = x$

xと(x,yの論理和)の論理積はxとなることを表している。
x=0, y=0のとき、右辺は0=xとなる。
x=0, y=1のとき、右辺は0=xとなる。
x=1, y=0のとき、右辺は1=xとなる。
x=1, y=1のとき、右辺は1=xとなる。

以上から、結果がxの値と等しくなることがわかる。


2) $x + (x \cdot y) = x$

2)は1)の論理演算子をすべて逆にしたパターンで、この場合も左辺の結果がxの値と等しいことが成立する。 1)と同様にx,yに値を代入したら確認できるので説明は省略。


3) $x \cdot (\overline{x} + y) = x \cdot y$

x=1, y=0のとき、$1 \cdot (0 + 0) = 1 \cdot 0$
ここで右辺を見ると、1=x, 0=yとなっていることがわかる。

x,yのすべての取りうる値で3)が成立する。


4) $x + (\overline{x} \cdot y) = x + y$

4)は3)の論理演算子が全て逆の場合であり、この場合も4)が成立する。

3)の吸収法則を覚えておき、そこから4)は3)の論理演算子をすべて逆にしたものとして覚えておく。


ド・モルガンの法則

論理演算にもド・モルガンの法則が使える。

$\overline{(x \cdot y)} = \overline{x} + \overline{y}$

左辺の論理否定、論理積の全部逆にしたものが右辺になる。


$\overline{(x + y)} = \overline{x} \cdot \overline{y}$

左辺の論理否定と論理積を全部逆にしたものが右辺になる。


複雑な論理演算式の簡略化

xとyの否定論理積：$\overline{(x AND y)} = \overline{(x \cdot y)}$を”x NAND y”と表記する。

NANDはnot andで、論理積の否定のこと。

複雑な論理演算式を簡略化する例として、論理式 “(x NAND x) NAND (y NAND y)”を展開しわかりやすく簡略化する。

1) $x NAND x = \overline{(x \cdot x)} = \overline{x} + \overline{x} = \overline{x}$ (ド・モルガンの法則),(同一の法則)
2) $y NAND y = \overline{(y \cdot y)} = \overline{y} + \overline{y} = \overline{y}$ (ド・モルガンの法則),(同一の法則)

1),2)により、与式(x NAND x) NAND (y NAND y) = $\overline{x} NAND \overline{y}$
$=\overline{(\overline{x} \cdot \overline{y})} = \overline{\overline{x}} + \overline{\overline{y}}$ (ド・モルガンの法則)
※上記は、一番上のオーバーラインと演算子についてド・モルガンの法則を1回適用する。
$= x + y$ (論理否定の論理否定なので元にもどる)


カルノー図法

カルノー図法とは、複雑な論理和の論理式を簡略化するために利用される表のこと。
整理することで、簡単な表記ができる複雑な論理式が与えられて、それを簡単に表記するために、カルノー図法という整理方法を使う。

カルノー図についてのわかりやすい記事を参照する。
上記参考記事中に出てくるハミング距離については、ハミング距離についての記事を参照する。

AB\CD 00 01 11 10
00 1 0 0 1
01 0 1 1 0
11 0 1 1 0
10 0 0 0 0

縦はAB, 横はCDのとる値を表している。

例) AB=00, CD=00の交わるセルは1となっている。
例えばA=0はAの否定である $\overline{A}$ を表している。 この表のAB=00、CD=00と出力値1なので、
$\overline{A} \cdot \overline{B} \cdot \overline{C} \cdot \overline{D}$
がAB=00,CD=00,出力1という表の情報から読み取れる式となる。

この表から論理式を次のように導く。
出力1だけでかたまっているところを四角で囲む。囲むときは2の階乗個の個数を囲まないと正しい論理式は導き出せない。
四角で囲める部分は1箇所とは限らない。
表の両端は連続するものとみなすので、最初と最後のセルはひと続きとしてみなす。
すると、この表では真ん中あたりと最上段の2箇所を四角で囲めることになる。

次に、囲んだ1つの四角ごとに、四角で囲んだ各セルの論理式を求めて縦に並べて書く。

真ん中あたりの四角で囲んだセルの論理式

まず真ん中あたりの四角で囲んだ4つの出力1のセルの論理式を書く。

(AB=01,CD=01の論理式) $\overline{A} \cdot B \cdot \overline{C} \cdot D$
(AB=01,CD=11の論理式) $\overline{A} \cdot B \cdot C \cdot D$
(AB=11,CD=01の論理式) $A \cdot B \cdot \overline{C} \cdot D$
(AB=11,CD=11の論理式) $A \cdot B \cdot C \cdot D$

すると、4つの論理式に共通する変数があることが分かる。
この共通変数を抽出すると、B,Dなので抽出する論理式は$B \cdot D$となる。

表の最上段の四角で囲んだ2つの出力1のセルの論理式

(AB=00,CD=00の論理式) $\overline{A} \cdot \overline{B} \cdot \overline{C} \cdot \overline{D}$
(AB=00,CD=10の論理式) $\overline{A} \cdot \overline{B} \cdot C \cdot \overline{D}$

すると、2つの論理式に共通する変数があることがわかる。
この共通変数を抽出すると、$\overline{A}$, $\overline{B}$, $\overline{D}$なので
抽出する論理式は$\overline{A} \cdot \overline{B} \cdot \overline{D}$となる。

カルノー図が示す論理式は、2箇所の四角で抽出した論理式の論理和となる。

よって、カルノー図から導き出す論理式は
$\overline{A} \cdot \overline{B} \cdot \overline{D} + B \cdot D$
となる。


集合

集合Sとある要素aがあった場合に、Sにaが含まれているかを下記のように表す。

要素aが集合Sに含まれる場合： $a \in S$

要素aが集合Sに含まれない場合： $a \notin S$


部分集合の表し方

ある集合S1の要素がすべて他の集合であるS2に含まれるとき、S1をS2の部分集合と呼び、下記のように表す。

$S1 \subset S2$

上記の場合でS2がS1の要素以外を含んでいる場合はS1はS2の”真部分集合”と呼ぶ。


集合の表しかた

集合全体を全体集合または普遍集合と呼び、Ωで表す。

補集合は$\overline{S}$または$S^c$と表す。


和集合は$S1 \cup S2$と表す。

積集合は$S1 \cap S2$と表す。

差集合はS1 - S2または$S1 \setminus S2$と表す。
この場合はS1からS2と共通する要素(積集合$S1 \cap S1$)を除いた集合を表している。

差集合は積集合におきかえることができる。
$S1 - S2 = S1 \cap \overline{S2}$
差集合S1 - S2は、S1と$\overline{S2}$の共通部分に等しいので、上記の等式が成り立つ。


集合演算の公式

論理演算と同じように、集合演算子を使った集合演算にも基本的な公式がある。

和集合は論理和、積集合は論理積と同じ意味。

交換法則

集合演算子の左と右の集合を入れ替えただけのものなので当たり前に成り立つことがわかるので覚えなくてもよい。

$S1 \cap S2 = S2 \cap S1$
$S1 \cup S2 = S2 \cup S1$


結合則

論理演算の論理和、論理積の結合法則と全く同じ考え方。集合の概念で結合則を理解しようとすると大変なので、
論理演算の結合法則の方をちゃんと理解しといたら大丈夫。

論理演算の記号が集合の記号に置き換わっただけ。

$S1 \cap (S2 \cap S3) = (S1 \cap S2) \cap S3$
$S1 \cup (S2 \cup S3) = (S1 \cup S2) \cup S3$

積と和の記号が違うだけなので、どちらかだけ覚えておく。


分配則

集合演算の分配則は論理演算の分配法則と同じ考え方。集合の概念で分配則を理解しようとすると大変なので、
論理演算の分配法則の方をちゃんと理解しといたら大丈夫。

論理演算の記号が集合の記号に置き換わっただけ。

$S1 \cap (S2 \cup S3) = (S1 \cap S2) \cup (S1 \cap S3)$
$S1 \cup (S2 \cap S3) = (S1 \cup S2) \cap (S1 \cup S3)$

積と和の記号が違うだけなので、どちらかだけ覚えておく。


吸収則

集合演算の吸収則は論理演算の吸収法則と同じ考え方。集合の概念で吸収則を理解しようとすると大変なので、
論理演算の吸収則の方をちゃんと理解しといたら大丈夫。

$S1 \cap (S1 \cup S2) = S1$
$S1 \cup (S1 \cap S2) = S1$
記号が変わるだけなのでどちらか一つを覚えておくだけでいい。

$S1 \cap (\overline{S1} \cup S2) = S1 \cap S2$
$S1 \cup (\overline{S1} \cap S2) = S1 \cup S2$
記号が変わるだけなのでどちらか一つを覚えておくだけでいい。


補元則

補元則は論理演算で考えなくても集合の概念で意味をそのままイメージしやすい。

$S \cup \overline{S} = Ω$
$S \cap \overline{S} = \emptyset$


ド・モルガンの法則

集合のド・モルガンの法則も論理演算で考えると等式が成り立つ理由がわかりやすい。

$\overline{(S1 \cap S2)} = \overline{S1} \cup \overline{S2}$
$\overline{(S1 \cup S2)} = \overline{S1} \cap \overline{S2}$


複雑な集合演算の式をかんたんにする

複雑な集合演算はベン図で考えると余計にわかりにくくなるので論理演算で考えて簡単に整理する。

例：

$X = (\overline{A} \cap \overline{B}) \cup (\overline{A} \cap B) \cup (A \cap \overline{B})$を整理する。

$X = (\overline{A} \cap \overline{B}) \cup (\overline{A} \cap B) \cup (A \cap \overline{B})$

// 第1項と第2項に分配則を適用(分配則の右辺側のパターンなので分配則の左辺側に変換)。
$= \overline{A} \cap (\overline{B} \cup B) \cup (A \cap \overline{B})$

// $(\overline{B} \cup B)$は全体集合なので1となる。
$\overline{A}$と全体集合1の共通部分は、$\overline{A}$そのものなので、下記となる。
$= \overline{A} \cup (A \cap \overline{B})$

$\overline{A} \cap (\overline{B} \cup B)$は$\overline{A}$と1の積集合なので論理積と同じ。
ということは、$\overline{A} \cdot 1$なので、この出力値は$\overline{A}$がとる値そのものなので
省略できるから$\overline{A} \cup (A \cap \overline{B})$となる。

以上で$X = (\overline{A} \cap \overline{B}) \cup (\overline{A} \cap B) \cup (A \cap \overline{B})$
が$X = \overline{A} \cup (A \cap \overline{B})$と簡単に整理できた。

ここで、$\overline{A} \cup (A \cap \overline{B})$に対して吸収則が使えるように工夫をする。
吸収則を適用することでもっと簡単に整理する。

$X = \overline{A} \cup (A \cap \overline{B})$の$\overline{A} = S1$, $\overline{B} = S2$とおくと、

$X = S1 \cup (\overline{S1} \cap S2) = S1 \cup S2$ //吸収則

ここで、S1とS2をもとに戻すと、$\overline{A} \cup \overline{B}$

さらにド・モルガンの法則を適用し、$\overline{A} \cup \overline{B} = \overline{A \cap B}$

以上のように、複雑な集合演算の式を簡略化できた。


論理演算と集合演算ともに、法則をちゃんと覚えておく。問題解くときにすぐに法則を適用することができないと
問題を解く時間が足りないため。論理演算と集合演算の記号が違い、集合演算の方は演算子が認識しづらく見た目が覚えにくいので、
論理演算の方の基本公式をしっかりと覚えておき、集合演算に基本公式を適用するときは、論理演算の基本公式の演算子だけ集合演算
の演算子に変えて対応する。基本公式を見て理解するだけでは覚えにくいので、基本公式を手で何度も書くことで記憶しやすくする。

グラフ理論

木は閉じていないグラフ。完全グラフはすべての2点間が辺でつながっているグラフのこと。

無向グラフとは、辺に流れ方向など向きがないグラフのこと。有向グラフは流れ方向が決まっているグラフのこと。

木の巡回

木の巡回方法は、幅優先順と深さ優先順の2種類がある。
幅優先順は、”幅”という単語からイメージできるように、横並びの同じレベルの点を順番に巡回する巡回方法。
深さ優先順は”深さ”という単語からイメージできるように、縦方向の点を巡回する巡回方法。
深さ優先順は、さらに3つの巡回方法に分かれている。先行順、中間順、後行順。

深さ優先順は、根(親)から巡回をスタートする。根から巡回するけど点の取りだし方が先行順、中間順、後行順
で異なるので、同じ内容の木であっても取り出した点の順番が異なる結果となる。

深さ優先順の巡回方法は下記を覚えておくと覚えやすい。

先行順

点の左側を通るときに点の値を取り出す巡回方法。

中間順

点の下を通るときに点の値を取り出す巡回方法。

後行順

点の右側を通るときに点の値を取り出す巡回方法。


グラフのデータ構造

ヒープ、2分探索木、B木などがある。

ヒープ

ヒープとは、子ノードの値は親ノードの値より大きいか等しい、または小さいか等しい、という大小関係の制約を持った木構造のこと。
深さの浅い順(木構造の上から順)にノードが配置される。(親のノードの値) < (子のノードの値)または逆の大きさ順に配置される。
同じ深さのノードでは、普通は左のノードから順に、値が小さい順にノードが配置される。


2分探索木

2分探索木とは、各ノードの値に下記の制約を持った木構造のこと。
(左の子のノードの値) < (親のノードの値) < (右の子のノードの値)
例えば1，2，3という値があるとすると、
(左の子のノードの値=1) < (親のノードの値=2) < (右の子のノードの値=3) の並びで配置される。

2分探索木でAVL木という木構造もある。
AVL木はどの左右のノードについても深さの差が1以下という条件を満たす木のこと。


B木(B Tree)

B木は1つのノードに複数の値を格納した木構造。キーとなる値に対しての大小を比較して子のノードに値を振り分ける。


練習問題 | 論理演算

nビットの値L1, L2があり、次の操作によって得られる値L3はL1とL2に対するどの論理演算の結果と同じかを答える。

操作
1) L1とL2のビットごとの論理和をとって変数Xに記憶する。 2) L1とL2のビットごとの論理積をとって更に否定をとって変数Yに記憶する。 3) XとYのビットごとの論理積をとって結果をL3とする。

解答
1)$X = L1 + L2$

2)$Y = \overline{(L1 \cdot L2)}$

3)$L3 = X \cdot Y$

ここで、Yにドモルガンの法則を使う。
$Y = \overline{(L1 \cdot L2)} = \overline{L1} + \overline{L2}$

$L3 = (L1 + L2) \cdot (\overline{L1} + \overline{L2})$
分配法則を適用して右辺を展開する。　

この時、L1 + L2を一文字に置くと、分配法則が使えることがわかるので、L1 + L2 = Xと置く。
これはなかなか慣れないと気づきにくいけど、慣れていくことで使えるようにする。下記のように分配法則が使える。

$= ((L1 + L2) \cdot \overline{L1}) + ((L1 + L2) \cdot \overline{L2})$
$= (L1 \cdot \overline{L1} + L2 \cdot \overline{L1}) + (L1 \cdot \overline{L2} + L2 \cdot \overline{L2})$
ここで、$L1 \cdot \overline{L1} = 0$, $L2 \cdot \overline{L2} = 0$なので
$= L2 \cdot \overline{L1} + L1 \cdot \overline{L2}$
$= L1 \cdot \overline{L2} + L2 \cdot \overline{L1}$
これはベン図で考えると排他的論理和。

以上から、排他的論理和が正解。


オートマン

オートマンはコンピュータの動作をモデル化した図で、状態遷移表や状態遷移図を使ってコンピュータの動作を表現する。

普通は入力と出力がセットだけど、入力だけを受け取り、出力しないオートマンを有限オートマンと呼ぶ。
有限オートマンは入力をチェックするだけであり、状態遷移表や状態遷移図で動作を表せる。

有限オートマンはイテレータみたいなイメージで、一つずつ右に移動し、最後の配列の要素まで移動できていれば
途中でおかしなことがなく正常に処理が終了したことを意味しており、これを”入力は受理された”と呼ぶ。

有限オートマンはある入力に対し最終の状態として設定された箇所までたどり着いていたら受理されたことになる。

abcdeという文字列の文字それぞれに対し状態遷移が起こり、最後の文字の”e”で受理となる状態遷移であれば、受理されたことになる。
変数名の受理が有限オートマンのイメージ。

有限オートマンのほかに、プッシュダウンオートマンと呼ばれるオートマンもある。
プッシュダウンオートマンはスタックにデータを格納できるので、再度データを呼び出すことができる。

有限オートマンはコンパイラの字句解析(プログラムから字句を切り出す)に利用される。


計算量

計算量はアルゴリズムの評価尺度で、計算量を一定の尺度で表したもの。

計算量には領域計算量と時間計算量がある。計算量というと、どっちなのかと思うけど、時間計算量のことを指していることが多い。

領域計算量：
プログラムの実行開始から終了までに使用する記憶容量のことを指す。

時間計算量：
プログラムの実行開始から終了までにかかる所要時間のことを指す。

計算量では最悪なケースを想定して表す。
最悪なケースとは、一番時間がかかってしまうケースや一番記憶容量をいっぱい使ってしまうケース。

平均計算量という計算量もあるけど計算するのが難しいこともありあまり使われないらしい。

O記法： 計算量について下記の関係が成立する。
O(f(n)) + O(g(n)) = O(max(O(f(n)), O(g(n)))
O(f(n)) X O(g(n)) = O(f(n) X g(n))

計算量の加算は大きい方に引きずられることを意味している。
計算量が加算される例としては、2つのプログラムを一緒にしたような場合で、計算量は計算量の大きい方のプログラムと同じになる。

計算量が乗算となる例としては、2重ループになるようなアルゴリズムの場合で、1つのループの計算量がｎとすると、2重ループでは$n^2$となる。

計算量がO(1)とは、計算量が一定の定数時間ということで、プログラムの処理にかかる時間がデータ量に依存しないことを示している。


正当性

正当性とは計算機科学(コンピュータサイエンス)の概念。

正当性とは：
正当性はすべての場合においてプログラムが正しいことを証明すること。正当性はテストとは違う。テストは限られた範囲しか証明できない。

部分正当性とは：
部分正当性はプログラムの一部分においてプログラムが正しいことを証明すること。

全正当性とは：
入力条件を満たしたプログラムを実行したら必ず停止し、得られる結果が出力条件を満たすことを証明すること。
出力条件を満たすことは、部分正当性が成立していることを意味しているので、全正当性とは部分正当性を満たし、停止するということ。


データ型と演算と精度

コンピュータは有限な桁数で計算をするので、四捨五入や切り捨て、切り上げなどの操作によって誤差が生じる。

データ構造とは、コンピュータでデータ処理や計算をするときに、あらかじめデータを扱いやすいようにしておき計算速度が速くなるようにしたデータのこと。

浮動小数点数とは

浮動小数点数方式という方式で表現された数のこと。なので、数値は浮動小数点数方式で表せることになる。
コンピュータでは数値を浮動小数点数方式を使って表すことが多い。
誤差のコントロールができるので桁数の多い小数点を持つ数値を扱うときに使われる。 コンピュータは電圧の高低による1と0しか扱えないので、負の符号や小数点のドットをそのままでは扱えない
けど、浮動小数点数方式というデータ構造にすることで、負の符号や小数点のドットをコンピュータで扱えるように表現している。

数値を浮動小数点数方式で表すときのデータの構成：
浮動小数点数は、符号、仮数、指数というデータ構造に分け、10進数などの数値を0と1のビットで表すことで負の数や小数点を含む数値を表現できる。
(符号部)(指数部)(仮数部)というデータ構成でビットを並べる。

浮動小数点数の構成：
通常、浮動小数点数は32ビット。符号部は1ビットで、正の場合は0、負の場合は1が入る。
仮数部は24ビットで、仮数部には小数点以下の数値が入る。
指数部は7ビットで、2のn乗のnを2進数にした数値が入る。

仮数部は小数点以下の数値を正規化したものが入る。正規化とは、小数点の位置を調整して小数部分の最上位桁を0以外の値にすること。

正規化することで、限られた24ビットの桁数を有効桁数として最大限に使える。
$0.00012x10^3$と$0.12x10^0$は同じ数字。例えば仮数部に5桁しか入れることができないとすると、前者は00012が仮数部となり、後者は
12000となり、前者は12より小さい小数点部分は入らないので扱えないのに対し、後者は12より小さい小数点部分があと3桁入るので、前者よりも
より細かな桁の小数を扱える。これが正規化という処理をする理由。

指数部分が正の数であれば、指数をそのまま2進数で表記する。例えば指数が5の場合は、5を2進数で表すと101となる。
指数部は7ビットなので、0000101となる。指数部分が負の数であれば、2の補数を使って負の数を表現する。


補数とは

補数についての分かりやすい記事を参照する。

1の補数とはぎりぎり桁上がりしない補数の意味。2の補数とは2進数の足し算で、足したら桁上がりする補数のこと。

2の補数とは

2進数における負の数は、正の数をビット反転して1を加えたものが負の数で、それを2の補数と呼ぶ。

2進数では負の数を直接表現できないので、例えば-5という負の数を表現するために、5を利用する。
-5を表現したいので、反対の数字である5を利用し、5+(-5)=0という式を作る。絶対値が同じ数の負の数と正の数を足すと0になることを利用している。
これをそのまま2進数に当てはめる。

求めたい2進数の-5をxとすると、5は2進数で0000101なので、 5+(-5)=0 -> 0000101+(-x)=0000000

0000101に-5に該当する2進数であるｘを足したら00000000になると、その数が2進数での-5ということになる。

0000101をビット反転したものを求めると、1111010となり、0000101に1111010を加えると、0000101+1111010=1111111となる。
しかしこれでは0000000ではないので、これに0000001を加える。
よって、0000101に加えるのは1111011となり、0000101+1111011=10000000となる(1111111に0000001を加えた1111111+0000001=10000000の方が計算しやすい)。

10000000の1の部分は桁上がりした部分なので7桁からあふれたものなので無視すると、0000000となる。
よって、10進数の-5は2進数で1111011となる。


$1.2345 = 12345 * 10^{-4}$

１０進数の1.2345は、$(仮数部) * (基数)^{(指数部)}$のように表せる。


負数の表し方

1の補数、2の補数を使って負数を表現することで、引き算を足し算にする。2の補数を使って負数を表現することが普通。
1の補数で負数を表現して引き算を足し算にすると、計算結果がズレて正しく出ないので、別途の補正が必要になってくる。
そのため、1の補数を使うこともできるが、通常は2の補数を使うことが普通。


基数とは

桁上がりの基準になる数を基数という。

10進数の数値を１０進数のまま、$(仮数部) * (基数)^{(指数部)}$ で表す場合は基数は10になる。
理由は、桁上がりするには0から9の１０種類のいずれかの数値に数値を加えて合計が１０以上になると１桁桁上がりするため。
2進数で表す場合は、基数は2となる。

2進数はある桁の1に1を足す1+1=2されるとひと桁上がるので、基数は2となる。

同様に、8進数ではその桁の合計が8以上になると桁上がりするので基数は８。

16進数ではその桁の合計が16以上になると桁上がりするので基数は16。


浮動小数点数の中でもいろんな表現方式がある

IEEE754という表示形式は、32ビットのデータ構成で表す。
IEEE754の場合は、[符号部=1bit][指数部=8bit][仮数部=23bit]という構成で数値を表現する。


例) -10.25という10進数の数値を2進数のIEEE754の表示形式で表現する

10進数で$(仮数部) * (基数)^{(指数部)}$の形で表すと、$-10.25 = -1.025 * 10^{1}$のようになる。

上記の構成：
符号部：　正負
仮数部： 1.025　元の数値(10.25)から小数点を動かした値. 1の位が 指数部：　 1 小数点を動かした数


10進数の-10.25をIEEE754で表す手順：

浮動小数点数について分かりやすい記事を参照する。

符号部を表す方法：
符号がマイナスの時は1、符号がプラスの時は0のフラグを立てる。

-10.25は負の数なので、符号はマイナスなので、(符号部) = 1となる。

仮数部を表す方法：
正負の符号は符号部として別に考えるので、10進数の-10.25の仮数部は10.25。これを2進数で表す。

  1. 10進数表記の仮数部10.25を(整数部分)と(小数部分)に分けて2進数に変換する。
    まず(整数部分)の10進数表記の10を2進数で表すと1010となる。
    次に(小数部分)の10進数表記の0.25を2進数で表すと0.0100…(…の部分の0が何個続くかは表記する方式のbit数に応じて変わる).

10進数の小数点以下の数値を2進数で表現する方法：
小数点以下の10進数の数を2進数で表すには、2進数の小数は右に1桁動くたびに半分になる。
2進数の小数第一位は0.5、小数第二位は0.25、小数第3位の桁は0.125、という風に、桁が右に行くたびに前の桁の半分の数値になっていく。
10進数の小数部分を、上記の各桁の足し算で表現する例えば、10進数で0.75を2進数で表現するには、小数第一位の0.5と小数第二位の0.25
を足したもので表現できる。そのため、0.75は2進数で0.11となる。

  1. (整数部分)と(小数部分)を合わせる. (整数部分)=1010, (小数部分)=0.0100なので、合わせると1010.0100となる。

  2. 整数部分が1桁の1になるように小数点の位置を移動する(これを正規化という). 1010.0100の整数部分が”１”の１桁になるように小数点の位置を移動させると、1.0100100となる。

  3. 整数部分の1を取り除く 整数部分の１を取り除くと、0100100…となる(残りの(…)の桁の部分は全て0となる)。 この0100100…が10進数の-10.25を浮動小数点数表記にする場合の仮数部になるので、
    (仮数部) = 0100100…となる。

指数部を表す方法：
指数部は仮数部を求めるときに小数点の桁を動かした数になる。
仮数部を求めるときに、1010.0100が1.0100100となるように小数点の位置を3桁動かしたので、指数部は3となる。
IEEE754では指数部は8ビット表記なので10進数の3を8ビットの2進数で表すと、0000 0011となる。
ここで、IEEE754ではオフセットバイナリ(下記参照)形式で指数部を表すルールとなっているので、オフセットバイナリであるバイアス値(127)を足す。

符号部で既に正負の符号をつけている。指数部は大きな値も小さな値も表せるように負の値にもなる。
これを2の補数で表すと、全体の符号を表す符号部とは別に指数部にも符号を持つことになり、
そのまま大小比較ができなくなってしまう。なので、指数部はバイアスされて常に正の値となるような形式にするためバイアス値の127を足す。

オフセットバイナリとは：
2進数で負の数を表すための2の補数と同じ考えかた。補数で負を表すのではない方法がオフセットバイナリ。
あらかじめ決めておいたオフセットバイナリの値をバイアス値と呼ぶ。

IEEE754ではバイアス値の127を足す。127は8ビットで0111 1111。
よって、(指数部) = 0111 1111 + 0000 0011 = 1000 0010 となる。

以上から、(符号部) = 1, (指数部) = 1000 0010, (仮数部) = 0100 1000 0000 0000 0000 000

なので、10進数の-10.25をIEEE754で表すと、11000001001001000000000000000000(←合計32ビット)となる。


マイナス乗とは

小数点以下の数値を２進数で表す場合、２進数の小数点以下の桁は１桁右に行くたびに2のマイナス乗になる。
右の桁に行くたびに小さな数値になるので、小数点を任意の桁の値で足して小数点の合計を表す。
例えば、１０進数の0.25は２進数で表すと$2^{-2} = 0.25$に該当する２進数の桁を1にする。意味合い的にはフラグを立てる。trueにする。と同じ。
小数点の桁を２進数の１にするとその桁を足す意味になる。

上記のように足して表現すると、小数の値によっては、合計が表したい小数ピッタリにならないことが生じる。その場合はピッタリで表現できないので近似値となる。

マイナス乗 $2^{-1}, 2^{-2}, 2^{-3},…$の意味：

$2^{-1}$ は例えば$2^{1} / 2^{2}$の計算結果だと考えてみる。$2^{2}$は掛け算にすると逆数になるので、

$2^{1} / 2^{2} = 2^{1} * 1/2^{2}$となる。これを普通に計算すると、

2 * 1/4 = 1/2となる。すなわち、$2^{-1} = 1/2 = 0.5$となる。

上記と同様に考えると、$2^{-2} = 0.25$, $2^{-3} = 0.125$,…のように、右に桁が移動するたびに値がどんどん1/2になっていく。


誤差

まず有効数字について忘れやすいし理解が難しいので分かりやすい記事を参照する。

コンピュータでは有限な桁数で計算をするので、レジスタに入りきらない数値があったりすることで、入りきらない数値は無視されたりするので
コンピュータと数学の計算結果に違いが発生する。これを誤差と呼ぶ。

いろんな種類の誤差が定義されている。


絶対誤差

絶対誤差とは、測定値や計算値などの結果から真値を引いた値のことで、(測定値) - (真値)で計算する。


相対誤差

相対誤差は、絶対誤差と真値との比のこと。真値を知ることは不可能なので測定値や計算値を真値とみなして. 求める場合が多い。

(相対誤差) = (絶対誤差) / (真値)で計算する。

相対誤差は、真値に対する絶対誤差の割合を示している。
相対誤差が小さいほど真値に対する測定値の精度が高いことになる。

例). (真値) = 1000, (測定値) = 1003のとき. (絶対誤差) = (測定値) - (真値) = 1003 - 1000 = 3. (相対誤差) = (絶対誤差) / (真値) = 3 / 1000 = 0.003

(真値) = 10000, (測定値) = 10003のとき. (絶対誤差) = (測定値) - (真値) = 10003 - 10000 = 3. (相対誤差) = (絶対誤差) / (真値) = 3 / 10000 = 0.0003

上記の２つの例のように、絶対誤差自体は同じ３でも、相対誤差は真値の大きさによって全然違ったものになるので、
絶対誤差だけでは指標として役立たない。
そのため、絶対誤差は相対誤差の計算に必要な要素くらいに考えておく。


系統誤差

特定の原因によって測定値が偏って発生する誤差のこと。分かりやすい例では測定装置の個体差や人による測定方法の癖があるなど。

誤差が発生する要因

丸め誤差：
丸め誤差とは、丸めによって発生する誤差のこと。値の近似値を計算するとき、桁の切り捨て、切り上げ、四捨五入などを
する。すなわち端数の処理をするので誤差が発生する。とくにコンピュータは無限小数を扱えないので、有限な桁数にする
ため丸めをする。これによって誤差が発生する。


桁落ち：
桁落ちとは、ほぼ同じ数値同士の引き算、あるいは絶対値がほぼ同じで符号が異なる2数の足し算をしたときに、
有効数字が少なくなってしまうこと。
例)
123.123456789 - 123.123456678 = 0.00000111

ほぼ同じ数値の引き算をしたことで、数値の有効数字が12桁→3桁に減った。
コンピュータでは浮動小数点数の計算で発生する。

コンピュータでは、上記の2数の桁数が決まっているので、例えば7桁とすると、
7桁に収まらない数値は四捨五入や切り捨てなどされるので、これにより
2数の引き算する前の時点で誤差が発生する。

さらにほぼ同じ数値を引き算するのであれば、桁落ちする。引き算の結果の数値は桁落ちした状態の数値となる。
この数値を正規化することで、余った桁に0が付加される。
その0は桁を埋めるために付加されたにすぎないので、真値と比べて
明らかに誤差が発生する。これが桁落ちによる誤差(下記参照)。

有効数字3桁の0.00000111を浮動小数点数にするために正規化したとき、
0.111000…の111以降の0は正規化によって付加された
0なのでほんとに正しい値なのかの保証がない。

例えば0.111234…がほんとうの正しい数値だとすると、付加された0は正しい値ではなく、
正規化により付加された0により(つまり桁落ちにより)誤差が発生したことになる。

※正規化とは仮数部の最上位を0以外の数字にすること。

有効数字とは：
位取りを示すだけの0を取り除いた意味のある数字のこと。
0.000123は有効数字3桁。
0.00001は有効数字1桁。

0ではない数字に囲まれた0は有効。
20.5は有効数字3桁。

小数点より右にある0は有効。23.0000は有効数字6桁。
100.0000は有効数字7桁。


情報落ちとは：
数値が無視されてしまう現象。大きな値と小さな値の組み合わせで足し算したり引き算したり
したときに小さい数値の値が無視されてしまう。

例)
123.4567 - 0.00000001234を計算する際に、小さい値の桁を大きい値の桁に揃えることによって
仮数部に入りきらなくなって、小さい値の情報が無視されてしまう。


積み残しとは：
情報落ちと似ている現象。aとbの加算結果は、a + bだけど、a»b(bよりも圧倒的にaが大きい)
のとき、bが無視されて、コンピュータでのa + bの演算結果がaとなってしまう現象のこと。

積み残しを防ぐ方法として、絶対値の小さな数値から順に加算していく。


打ち切り誤差とは：
無限に計算をする場合、無限に計算をすることはできないので、適当な誤差の
範囲で計算を打ち切ることで発生する誤差。


エンディアン(バイトオーダー)

エンディアンとは、2バイト以上の数値データを記録したり転送するときの順番のこと。

リトルエンディアンとビッグエンディアンがある。

1234ABCDという１まとまりのデータがあるとき、12, 34, AB, CDという1ワードあたり4バイトを
メモリのアドレスに格納するときの順番のこと。

例)数値データ= 12, 34, AB, CD, メモリのアドレス= A, B, C, Dのとき

1234ABCDという数値データをそのまま順番にメモリに格納する方法をビッグエンディアンとよぶ。
A = {12}, B = {34}, C = {AB}, D = {CD}
数値データの最後のバイトが最後に格納されるのでビッグエンディアン。

1234ABCDという数値データを最後のバイトから順番にメモリに格納する方法をリトルエンディアンとよぶ。
A = {CD}, B = {AB}, C = {34}, D = {12}
数値データの最初のバイトが最後に格納されるのでリトルエンディアン。

イメージとしてはアドレス空間が上から下にあるとしたら、データをアドレスの上(低位アドレス)から順に入れるか、データを アドレスの下(高位アドレス)から順にいれるかの違いとしてイメージするとイメージしやすい。


形式言語

形式言語とは、ひとの思考過程をモデル化して文字や記号で表した体系の言語のこと。
要素となる複数の記号とそれを結びつける構文規則から成っている。
プログラム言語で書かれた言語をどのように機械語に結びつけて翻訳するかに関わるのが形式言語
なのでコンピュータでは必須の概念。

形式言語の1つとしてBNF記法がある。

BNF記法

BNF記法はプログラム言語の構文と意味を文字記号で表現するもの。
BNFの基本的な表現方法として、順次、反復、選択という操作がある。

BNF記法で使われる”<>”や”::=”の意味：
“<>”は前後の文字が繋がったり範囲が不明確になるのを防ぐために使っている記号なので、省略されることもある。
“::=”は、定義するという意味で使われる。”左辺を右辺のように定義する”という意味になる。

順次：
順次とは例えば、xという構文の要素は、aとbという文字の並びであるという定義のことをいう。
aのつぎはbがないといけないという意味。

<x> ::= <a><b>

反復：
反復は、xという構文の要素はaの繰り返しであるという定義のことをいう。
つまり、xはaが1つ、または複数個連続するという意味。

<x> ::= <a>...

選択：
選択は、xという構文の要素は、aまたはbであるという定義のことをいう。
選択は”|”を使って表現する。”|”は、いずれか一方を選択することを意味する記号。

<x> ::= < a | b >

選択の一方がない場合は、”[]”を使って下記のように表現する。

<x> ::= [<a>]

これは、xという構文の要素は、aであるかまたは空であるという意味。
“[]”は省略可能を意味する記号。aか空かを選択できるので、空を選んだ場合はその部分については
要素は何もないので省略できることを意味している。

非終端記号と終端記号

非終端記号：
BNF記法ですでに定義した構文の要素を別の定義に利用すること、また、その定義自身に使用できる。
このように、すでに定義されておりその定義を利用(使い回し)をできる記号を非終端記号とよぶ。
非終端記号はすでに定義されたものなので、”<左辺> ::= <右辺>"の左辺のことを指すので変数と同じ。

終端記号： 終端記号は右辺にのみ存在する。アルファベットの1文字からなる記号のこと。
それ以上分解できないものなので終端記号という。

例) 終端記号と非終端記号の例

<y> ::= <a><x>  
<x> ::= <b><c>

上記ではxは非終端記号、a,b,cは終端記号。


BNF記法の再帰的定義

<文字> ::= ね|こ
<文字列> ::= <文字> | <文字列><文字>

右辺の”|”記号の”または”の部分の意味に注意しないといけない。
またはなので、条件分岐を表していて、1文字または２文字以上であると読み解く必要がある。

左辺の文字列定義が右辺の中でも使われている。これを再帰的定義とよぶ。

右辺の文字列の部分にそのまま(左辺) ::= (右辺)の右辺の文字列定義を入れるだけ。

なので右辺は実際は次のようになっている。
右辺で(文字列)(文字)の部分が選択されたということは、２文字以上なので、

<文字> | <文字列><文字>

の”|”記号の左側の１文字の部分は無いものとして考えないといけない。
この考えが意外と抜けてしまい、抜けたままだと分からなくなる。
つまり、再帰的定義の部分を考えるということは、この場合では２文字以上の場合となる。
2文字以上の選択なので、整理すると、

<文字列> ::= <文字列><文字>・・・①

となる。この右辺の”文字列”の部分に、

<文字列> ::= <文字> | <文字列><文字>

を再度当てはめることになる。

文字列の部分を再帰的に処理すると、

<文字列> ::= <文字列><文字>・・・①

の右辺の文字列の部分は、

<文字> | <文字列><文字>・・・②
となる。２文字の場合は、” “記号の前の１文字を選ぶことになる。すると、①の右辺は 
<文字><文字>

となる。

3文字以上の場合は、

<文字列><文字>

を選ぶことになる。これと①より

<文字列><文字><文字>

となる。以降、何文字でもこの再帰的な処理で表現が可能になる。


確率と確率分布

確率は、(求めたい事象の確率) = (事象の数)　/ (全ての事象の数) で求める。

事象の数(場合の数)を求めるときに使うのが、順列や組み合わせ。

順列

“異なるn個のものから異なるr個を選んで１列に並べる並べ方のパターン数を求める” ために順列の計算方法を使う。

順列の公式：
${}nPr = n(n-1)(n-2)… (n-r+1)= \frac{n!}{(n-r)!}$

例えば、異なる5個から3個選んで並べる場合：

(n-r+1)の部分は、5-3+1=2+1=3となる。つまり、(n-r+1)と表現することで、残りの個数が5、4、と選んでいき、残り3個になるまで
選ぶことができる。

なので、(n-r+1)が、階乗はここまでだよ。という末尾の数字を表している。
よって、5x4x3のように3個選んで並べることができる。

異なる5個から4個選んで並べる場合：

(n-r+1)の部分は、5-4+1=2となる。つまり、残りの個数が5,4,3と選んでいき、残りの個数が2個になるまで
並べるということを意味している。

1番目のものの取り方は n通り
2番目のものは、残りn-1個の中から1つ取るから、取り方は n-1通り
3番目のものは、残りn-2個の中から1つとるから、取り方は n-2通り
最後のr番目のものは、すでに取ったr-1個を除いた残りn-(r-1)個中から1つ取るから、
取り方はn-(r-1)通り、すなわちn-r+1通り。

最後のr番目について、具体的には、5個の中から3個取る場合はn=5, r=3
最後の3番目のものは、すでに取った3-1=2個を除いた残り5-(3-1)=5-3+1=3個の
中から1つ取るから、取り方は3通り。

以上のように、r-1は、最後のr番目までにすでに取って除かれた個数を示しているので、
最後のr番目のものの取り方は、n-(r-1) = n-r+1 通りとなる。

以上から、求める順列の総数は、${}nPr = n(n-1)(n-2)… (n-r+1)$
(順列は、nから始まって1ずつ小さくなるr個の数の積である)

また、$\frac{n!}{(n-r)!}$は下記のように理解する。
まず5!で全ての並べ方を求めておく。次に、３個選んで並べるので、n-r=5-3=2個選んで並べる場合の数は. 除外しないといけないので、5!個ある全ての並べ方から2!個除くことになる。なので、上記のような式に一般化される。


組み合わせ

“異なるn個の中から異なるr個とる組み合わせの数”という場合の数を計算するときに組み合わせの計算方法を使う。

a,b,c,d,eの中から２つを選ぶ組み合わせを求める場合でイメージする。

abとbaは同じ組み合わせであることに注意。
{ab}, {ac}, {ad}, {ae}, {bc}, {bd}, {be}, {cd}, {ce}, {de}の10通りの組み合わせの選び方がある。
順列だと5個から2個選んで順番に並べる方法は5x4=20通りある。順列だと順番に並べるので、{ab}と{ba}は
異なるけど、組み合わせで考えると同じものなので、2個の並べ方で1個の組み合わせとなる。

なので、順列から並べ方のパターンを除外した20÷2=10個が組み合わせの数となる。
順列は並べるので並べ方を考えるけど、組み合わせは並べ方は考えない。というように定義が区別されている。

組み合わせの公式：

${}nCr$
$= \frac{nPr}{r!}$
$= \frac{n(n-1)…(n-r+1)}{r(r-1)…3 \cdot 2 \cdot 1}$
$= \frac{n!}{r!(n-r)!}$

例) 異なる５人をa,b,c,d,eとする。異なる５人から３人選ぶ組み合わせの数を求める。

まずは５人から３人選んで並べる順列を考える。

順列の数は、${}{5}P{3} = 5 \cdot 4 \cdot 3 = 60$通り

上記60通りのうち、例えばaとbとcを選んだ場合について、{abc},{acb},{bac},{bca},{cab},{cba}の６この順列がある。
この6通こある順列は、組み合わせとして見ると同じものなので、1つの組み合わせである。

つまりaとbとcを選んだ場合の順列は${}3P3　= 3 \cdot 2 \cdot 1 = 6$通り。
この順列の6通りは1つの組み合わせということになる。

a,b,c,d,eの５人からa,b,cの３人を選んで並べる場合で考えると、順列の総数は６０個。この中の６個は１つの組み合わせなので、
組み合わせの単位に変換すると、組み合わせの数は、60÷6=10個の組み合わせとなる。

組み合わせの数を手作業で抽出すると{abc}, {abd}, {abe}, {acd}, {ace}, {bcd}, {bce}, {cde}, {dea}, {deb}. の１０個確かにある。

以上で${}nCr = {}{5}C{3} = 10$となる。

上記を順列で考えると、例えば{abc}という1つの組み合わせに対し${}3P3 = 3! = 3 \cdot 2 \cdot 1 = 6$個の並べ方がある。

よって、${}{5}C{3} \cdot 3! = 10 \cdot 6 = 60$個の順列となり、これは順列の総数。

また、この順列の総数は順列の式で表すと${}{5}P{3}$

したがって、${}{5}C{3} \cdot 3! = {}{5}P{3}$

上記の式より${}{5}C{3}　= \frac{5P3}{3!} = \frac{5 \cdot 4 \cdot 3}{3 \cdot 2 \cdot 1} = 10$

同様にして考えると、n個からr個とる組み合わせの数は、

順列に関して ${}nCr \cdot r! = {}nPr$ となる関係を利用すると、

${}nCr = \frac{nPr}{r!} = \frac{n(n-1)…(n-r+1)}{r(r-1)…3 \cdot 2 \cdot 1}$が成り立つ。

また、${}nPr = \frac{n!}{(n-r)!}$より、

${}nCr = \frac{nPr}{r!} = \frac{n!}{(n-r)!} \cdot \frac{1}{r!} = \frac{n!}{r!(n-r)!}$

だから${}nCr = \frac{n!}{r!(n-r)!}$

となり、組み合わせの公式が証明される。


確率

確率は1つの事象の起こりえる可能性を表した数。
全部の事象の数をn、事象Aの数をn(A)とすると確率P(A)は、
$P(A) = \frac{n(A)}{n}$となる。

余事象

事象Aに対して、Aでない事象をAの余事象とよぶ。Aの余事象は$\overline{A}$と表す。

ある事象と、その余事象の発生する確率の関係は、$P(A) + P(\overline{A}) = 1$
となる。

排反事象

2つの事象のうち一方が発生したらもう一方は発生しない事象がある場合、発生しない事象のことを排反事象とよぶ。

確率の加法定理

事象A,Bのうち少なくとも一方が起こる確率は、$P(A \cup B)$と表し、
$P(A \cup B) = P(A) + P(B) - P(A \cap B)$となる。
事象Aが起こる確率と事象Bが起こる確率を足して、事象Aと事象Bが同時に起こる確率を引いたものとなる。
事象Aと事象Bに共通する要素がある場合は、単純に足し合わせて終わると、AとBの共通する要素を２重に足し合わせてしまうので引く。
なので、一度２重に足し合わせた共通部分の確率を引くことで、AだけまたはBだけが起こるときもAもBも起こるときもちゃんと共通部分の
確率が処理できる。

kahouteiri

もし事象A,Bが排反事象だったら$P(A \cap B) = 0$となる。その場合は$P(A \cap B)$は存在しないので確率はP(A) + P(B)となる。


確率の乗法定理

事象A,Bが互いに独立して起こる確率は$P(A \cap B)$と表す。←めっちゃわかりにくい。
事象Aと事象Bがともに起こるので、事象Aと事象Bは共通部分として表される。

確率の乗法定理とは、事象Aが起こった後に続いてBが起こる確率を計算する方法を表している。

事象Aの起こる確率と、Aが起こったという条件のもとでBが起こる確率を掛け算する。

$P(A \cap B) = P(A) \cdot P(B)$

例)
5枚のカードがあって当たりが2枚あるとする。
最初にnekoくんが5枚のカードから1枚引いて当たったら、残りのカードは4枚で、当たりは1枚となる。
nekoくんが当たる確率をP(A)とする。

nekoくんの次にnukoくんが当たりを引く確率をP(B)とすると、P(B)は残りのカード4枚から当たり1枚を引く確率となるので、
nekoくんが当たりを引くという事象の影響を受けていることになる。

なぜ掛け算になるのかについては下記のリンクが分かりやすかったので参照。
確率が掛け算となるケースの証明は、直感的に掛け算と分かる感じではなく、結果的に分かる感じ。
確率の掛け算になる理由を証明している記事


プロジェクト管理での日程管理

プロジェクトを管理する技法がある。PERTとPDMなど。

PERT

PERTとは、Program Evaluation and Review Techniqueの略で、プロジェクトの日程計画に使うプロジェクト管理技法のこと。

アローダイヤグラムで所要日数を表し、最も日数のかかる経路をクリティカルパスとよぶ。
クリティカルパスはこれ以上遅れたら予定よりも遅れてしまう経路なのでクリティカルパスとよぶ。
アローダイヤグラムのスタートからゴールまでの最短の経路やクリティカルパスをスタートからの前進で
計算していく方法を前進計算とよぶ。

arrowdiagram

前進計算で作業にかかるクリティカルパスの所要日数が分かったら、後進計算で作業の日程調整をする。
例えばクリティカルパスが20日とする。経路の合流などを考慮すると、クリティカルパスの合流までの
分岐作業で余裕がある場合は少なくとも何日前までにこの作業を開始すればよいや、これまでには終わらせ とかないといけないなどのスケジュール管理ができる。このような計算を後進計算とよぶ。逆算と同じ感じ。

日程短縮をしたい場合にはクリティカルパス上の経路を短縮することで日程が短縮できる。

PDM

PDMとは、Precedence Diagramming Methodの略で、優先順位ダイアグラム法の意味。
ダイアグラムとは、幾何学的な図示のこと。
プロジェクトなどの作業工程を表すネットワーク図の一つ。
依存関係にある2つの工程間の順序をFS,SS,SF,FFという4つの関係で定義している。

FS: Finish-to-Start 先行作業が終了したら後続作業が開始。

SS: Start-to-Start 先行作業が開始すると後続作業も開始。

SF: Start-to-Finish 先行作業が開始すると後続作業が終了。

FF: Finish-to-Finish 先行作業が終了すると後続作業も終了。

PERTとPDMの違い：
PERTでは先行作業の終了したら後続作業が開始するFSしか表現できないが、PDMだと
SS,SF,FFも表現できるので、より細かく日程計画を表現できる。

pdm

ES: 最早開始日、EF: 最早終了日、LS: 最遅開始日、LF: 最遅終了日

上記のように個々の作業を設定し、下記のような感じでダイアグラムを書く。

pdmimage


待ち行列

応用情報で出題される待ち行列はM/M/1型というもので、この表記方法をケンドールの記号と呼ぶ。

ケンドールの記号とは、待ち行列の特徴を表した記号のこと。

待ち行列の状態・特徴を表現するために”A/B/C”という形式で、3つの特徴で表現する。

M/M/1の最初のMは処理窓口に到着するタスクの回数(頻度)に着目した分布を表していて、ランダムな分布を意味している。

2番目のMは、処理窓口に到着したタスクを処理する時間に着目しており、タスクが処理される時間が指数分布であることを表している。

3番目の1は、処理できる窓口が1つであることを表している。

以上から、M/M/1モデルは、1つの窓口にタスクがランダムに到着し、窓口が処理するタスクの処理時間は指数分布の待ち行列を表している。

最初のMも2番目のMも平均値を意味していることが重要。例えば平均の待ち人数が10人とすると、平均値が10人なので、
1人しか待っていない時もあれば、20人待っていることも考えられ、この平均値がランダムな特徴を表していることに注意する。

最初のMは、ポアソン分布で、２番目のMは指数分布。


M/M/1の最初のMは窓口に到着するタスクの様子を表している

タスクが窓口に到着する様子(10人集まる確率が80%、1000人集まる確率が0.001%など)を表している。

Mの部分に入る記号として、Mの他に、性質によって9種類ほどある。
応用情報の勉強ではM/M/1モデルしか出題されないので、下記の”M”という記号の定義だけ覚えておけば大丈夫。

Mの定義：
待ち行列がマルコフ過程という性質を持つ。待ち行列への到着はランダムに発生する。
確率と回数の関係をグラフにすると、ポアソン分布となる。

マルコフ過程とは:
マルコフ性を持つ確率過程のこと。未来の挙動が現在の値だけで決定する。
マルコフ性(Markov property）とは、確率論における確率過程が持つ特性のひとつで、確率の分布が現在の状態のみに依存し、
過去のいかなる状態にも依存しない特性を持つこと。マルコフ性を持つ確率過程をマルコフ過程とよぶ。

マルコフ性などについて分かりやすい記事を参照。

確率過程とは、時間などの条件によって変化する確率変数の数理モデル。
株価や為替の変動、ブラウン運動など粒子のランダムな運動を数学的に記述するモデルとして利用されている。

確率過程とは、時刻0,1,2,…tの確率変数をそれぞれの時刻について集めたもの。
また、確率変数の集まりに対して、確率だけではなく、回数(n回目)または時間(時刻ｔ)も紐づけしたもの。

確率変数とは、ある確率を持ったもののこと。例えば、さいころを投げて出る目は確率変数である。

ポアソン過程とは、ランダムに発生する事象を確率変数で表現したもの。
故障、災害の発生やお店への来客など、時間軸と発生確率で表せる事象がポアソン過程で表せる。

ポアソン過程は、例えばAという名前の地震は、次に同じ地震が発生するまでの平均時間は分かっているけど、
発生する間隔については2年連続で発生し、その後ずっと発生せず10年後に1回発生する。みたいに、平均は分かっているけど。
等間隔ではなくランダムに発生するイベントを表す。

ポアソン分布は、確率変数の値をある関数で表し、それをグラフにしたもの。縦軸が確率、横軸が回数を表している。
回数と確率の分布が見た目で分かるようになっている。
コールセンターへの電話が5回かかってくる確率が80%、1000回かかってくる確率は0.001%などグラフから読み取れるようになっている。

指数分布は、次に何かが起こるまでの時間間隔を表す分布によく使われる。指数分布と似ているのがポアソン分布。
指数分布とポアソン分布は縦軸はどちらも確率を表している。指数分布とポアソン分布は横軸に着目するものが異なる。
指数分布は横軸が時間であり、ポアソン分布は横軸が回数。

指数分布は無記憶性という性質があり、今までのことは関係なくこれからのことが起こることを意味する。
お店への来客が次くるまでにかかる時間、コールセンターに次に電話がかかってくるまでの時間などは、
これまでのこととは無関係に起こることなので、指数分布となる。
このように、ランダムなイベントの発生間隔を表すのが指数分布。

離散的とは、連続的ではないこと。 数学で値や数量がとびとびになっていること。
サイコロの目も整数値なので離散的なものに分類される。

サイコロの目という確率変数が1,2,3,4,5,6の6個の目のときは、さいころの目それぞれが出る確率は1/6。
確率変数は6個あるので、どれか一つの目が出る確率は1/6 * 6 = 1となり、100%となる。
これは、サイコロをふったらサイコロの目が出る確率は100%であることを意味している。

一方、確率変数が1〜6でも、その間が小数も取りうるとすると、1.000123などが確率変数となり、確率変数は実質無限な値をとりうる。
これを連続確率変数とよぶ。もし、サイコロの時のように1から6までの値が生じる可能性が1/6だったとすると、連続確率変数の個数は無限
なので、

どれかの目が出る確率は、”目の出る確率” * “無限個の確率変数” = “無限”
となり、どれかの目が出る可能性が1を超え、無限となりおかしなことになる。
これは、連続確率変数を扱うときは、通常の確率の考え方が使い物にならないことを意味している。

そこで登場するのが確率密度という考え方。

確率密度では、確率の合計が１になるように定義する。縦ｘ横の面積が1である面積に確率を対応させる。
横軸が確率変数、縦軸が確率。連続確率変数では、x軸の2点間の範囲のグラフ下側の範囲の面積が確率に対応しているため
x軸のある1点の確率を求めようとしても、面積は0となり確率が0になる。
そのため、連続確率変数はx軸のある1点での確率は求めることができないことに注意する。

サイコロの1,2,3,4,5,6のようにとびとびの値である離散確率変数の頻度をヒストグラムにすると、カクカクした図になるが、
この離散値を連続にすると、ヒストグラムが曲線になる。
この曲線を表す関数を、確率密度関数という。


M/M/1の2番目のMはタスクの処理にかかる時間の分布を表す

M/M/1の2番目のMに入る記号として、5種類ほどの記号が定義されている。
応用情報の勉強ではM/M/1モデルしか出題されないので、下記の”M”という記号と意味だけ覚えておく。

M: マルコフ過程で指数分布。タスクの処理時間は指数分布に従ったものとなる。


M/M/1の1は窓口の数を表す

M/M/1の1はタスクを処理する窓口の数やサーバーの台数といった処理できる機器の数を表している。

M/M/1モデルにおいて1はタスクを処理する窓口の数が1つであることを表している。


M/M/1モデルで使う待ち行列の公式

待ち行列の公式では平均到着率、平均処理率、利用率という概念を使う。
タスクの到着率、処理率ともにランダムなので、平均を使って表していることを意識しておく。

平均到着率

平均到着率は、1時間あたり50件到着するというような感じに、単位時間当たりに窓口に到着するタスクの件数を表す。

このように、窓口へのタスクの到着件数について扱うのが平均到着率。

平均到着率をラムダλと表現する。
λ= 単位時間当たりの平均到着数(件/時間)

2時間の間に100件のタスクが到着する場合は、λ=100件÷2時間=50件/1時間となる。


平均処理率

平均処理率はサービスの処理能力を表している。
平均処理率は、一定時間に処理できるタスクの数を表している。例えば2時間に200件など。
窓口に到着したタスクの処理件数について扱うのが平均処理率。

平均処理率をミューμと表現する。
μ= 単位時間当たりの平均処理数(件/時間)

2時間にタスクを200件処理できる場合は、μ=200÷2=100件/1時間となる。


利用率

利用率は、窓口の処理能力に対して、タスク処理にどれだけ能力を使っているか、占有しているかを表している。
利用率は平均到着率と平均処理率を使って求める。

処理能力である平均処理率に対しサービス窓口に存在するタスクはどのくらいなのかの比率なので、処理能力である平均処理率が分母にくる。

利用率はローρと表現する。

利用率は、窓口に存在するタスクの数をタスクの処理能力(数)で割ったものになる。
処理能力に対してどれだけタスクがあるかを表している。 (単位時間あたりに到着してくるタスクの数)÷(単位時間あたりに窓口がタスクを処理するタスクの数)により、
単位時間あたりに到着してくるタスクの数と窓口が処理するタスクの比率がわかる。つまり、単位時間当たりに
どれくらい窓口の能力が利用されているかがわかる。

(利用率)=(平均到着率)/(平均処理率)となる。つまり、ρ=λ/μ

単位は、(件/時間)/(件/時間)なので打ち消しあって無くなるので数値だけとなる。


M/M/1モデルでは利用率ρは視点を変えて表現するとトラフィック密度とも呼ばれ、0 < ρ < 1という特性がある。
もしρが1以上だと、到着するタスクの数よりも処理するタスクの数が少ないことになり、到着するタスクの数に対して窓口の処理が追いつかないことを意味する。

例えば、利用率2のように1以上だと、ρ=λ/μ=200/100などとなり、これは同じ時間内で処理できるタスクの数100に対し処理待ちが200なので処理
待ちのタスクが時間の経過とともにどんどん増えていくことを意味している。
例えば、上記が1時間当たりの利用率だとすると、1時間経過する毎に処理待ちのタスクが100件増していくことを意味している。
なので、ρが1以上だと処理待ちのタスクの数である待ち行列がどんどん大きくなってしまうので、待ち行列理論が成立しないのでρが1以上のケースは
待ち行列理論では扱えない。

逆に利用率が0未満となる場合を考えてみる。そもそもρ=λ/μ=2/10000など極端な場合でも0以下にはならない。ρ=λ/μ=0/10000などとすれば0となるが、
そもそも到着してくるタスクが0だと待ち行列の考えが成り立たないので、待ち行列ではρは0より大きいことも条件となる。

ρ=1の場合は、ρ=λ/μ=200/200などが考えられるが、これだと到着してくるタスクと処理できるタスクの数が同じなので
常に処理待ちのタスクが存在しないことになり、ρ=0の場合と同様に、待ち行列が存在しない。
なのでρは1未満となる。

以上から、待ち行列を考えるときは、トラフィック密度(利用率ρ)は0 < ρ < 1を前提の条件としている。


タスク1件当たりの処理時間

窓口でタスクを処理するので、窓口がタスク1件を処理するのにどのくらい時間がかかるかについても考慮する必要がある。

タスク1件当たりの処理時間は、処理能力である平均処理率を利用して求めることができる。問題によってはタスク1件当たりの処理時間がはじめから示されて
いることもあると考えられるが、平均処理率から計算できることを知っておく。

タスク1件を窓口の処理能力である平均処理率μで割ったものになる。
(タスク1件当たりの処理時間) = (タスク1件) / (平均処理率μ) = 1 / μ = 件 / (件/時間) = (時間)

例えば1時間という単位時間あたりに、100件のタスクを処理できる場合、平均処理率μ = 100件/1時間 = 100(件/時間)。

上記の平均処理率μのとき、タスク1件当たりの処理時間は、1(件)/100(件/時間) = 0.01時間 となる。ここでは単位時間は1時間なので0.01時間=0.01x3600=36秒となる。
以上からタスク1件当たりの処理時間は36秒かかることがわかる。

以上の、タスク1件当たりの処理時間のことを、”平均サービス時間(平均処理時間)”とよぶ。


平均サービス時間から利用率ρを求めることもできる。

平均サービス時間をtとする。

利用率ρ = λ/μ より$ρ = λ \cdot \frac{1}{μ}$ここで、$\frac{1}{μ}$は平均サービス時間なので、tに置き換えることができる。

よって、ρ=λt となる。これは、上記のように単純に式変形したものと理解しておくだけでよさそうだけど、意味合いのイメージとしては
タスクの数に1件のタスク処理にかかる時間をかけることで、処理能力のうちどれだけの処理能力を使っているかを表す利用率が計算できる。


処理待ちのタスクの長さ(処理中のタスクも含めて滞留しているタスク数の平均値(件))

処理中のタスクも含めて滞留しているタスク数の平均値(件)とは、処理の最中のタスク＋処理待ちのタスクの数なので、
処理待ちのタスク数を表していて、タスクの長さと呼ぶ。

処理待ちのタスクの長さをEとすると、E=ρ / (1-ρ)で求めることができる。1が処理能力を表していて、ρは利用率なので、
1-ρは処理能力の余力を表している。

例えば、処理能力が1時間に100件の場合で、利用率が1時間に30件の場合は、30件のタスクに対して、余力が100-30=70件。
この場合、タスクの長さ E=30/70となる。これをイメージすると、余力に対して処理待ちのタスクはどんな割合なのかについて程度を
表している。

待ち行列での利用率ρ、つまりタスクのたまり具合であるトラフィック密度は0 < ρ < 1 が前提で、
ρが0に近づくほど処理能力に対しての余裕がいっぱいで、1に近づくほど処理能力に対し余裕がないのを意味しているので、
1が窓口の処理能力の最大値を表している。

利用率ρに対して1-ρは、(窓口の最大能力)-(窓口の利用率)なので、窓口の能力の余裕分を表している。
を表している。

例えば処理能力が限りなく余っている場合を考える。ρが0に近いほど処理能力に余裕があるのでρ=0.01としてみる。
この場合、タスク処理の余裕分は1-ρ=1-0.01=0.99となる。このとき、

E=0.01/0.99=0.01…となり、処理待ちのタスクの長さは、0.01…で1個以下なので、限りなく少なくなることが分かる。

処理能力の余裕分がほとんど残されていない場合を考える。ρ=0.99とすると、1-ρ=1-0.99=0.01となるので、E=0.99/0.01=99となり、処理待ちのタスク数が99である。

以上から、E=ρ/(1-ρ)によって、滞留しているタスク数がどれだけになるのかを計算できる。

Eの値が小さいほど滞留しているタスク数が少なく、値が大きいほど滞留しているタスク数が多いことを意味している。


以上から、(タスクが到着してから処理開始までの時間)=(平均待ち時間)を計算する。

平均待ち時間は、上記で求めた滞留しているタスク数に、タスク1件を処理するのにかかる時間を掛けたものになるので、

求めたい平均待ち時間をTq、滞留しているタスク数をE、タスク1件を処理するのにかかる時間をtとすると、Tq= E x t = $\frac{ρ}{1-ρ} \cdot t$となる。

タスクが到着して処理が終了するまでの時間、すなわち平均応答時間は、Twとすると、上記で求めた平均待ち時間Tqと平均処理時間tの和になるので、

Tw = Tq + t となる。ここで、$Tq = \frac{ρ}{1-ρ} \cdot t$なので、

$Tw = Tq + t = \frac{ρ}{1-ρ} \cdot t + t$を整理して、

$=\frac{ρt}{1-ρ} + \frac{t(1-ρ)}{1-ρ} = \frac{t}{1-p} = \frac{1}{1-ρ} \cdot t$と整理できる。