基礎理論ざっくりまとめ（応用情報技術者試験）

対応するシラバスの範囲（応用情報技術者試験シラバス Ver.7.2）：大分類「基礎理論」の中分類1「基礎理論」

記号の書き方（このメモのルール）：
- 本来は上に線を引いて表す「否定」「補集合」は、論理なら ¬A、集合なら Aᶜ と書く
- 2乗などのべき乗は 2³、σ² のように書く。log の底は log₂ のように書く

集合と論理
情報理論と符号化
オートマトン
形式言語
グラフ理論
確率と統計
回帰分析
数値計算
AI（人工知能）
ひとことでまとめると

集合と論理

一言で言うと：
- 「ものの集まり（集合）」と「正しいか正しくないか（命題）」を、記号と計算で扱う話。論理回路、SQLの条件、プログラムのif文の土台になる。

集まりを扱う（集合論理）→ 真偽を扱う（命題と論理）→ 計算のルール（論理演算）→ 式を短くする（論理式の簡略化）

覚え方の軸

集合と論理は同じものの言い換え：
- 積集合∩＝論理積AND（・、∧）、和集合∪＝論理和OR（＋、∨）、補集合＝否定NOT（¬）、対称差Δ＝排他的論理和XOR（⊕）
数えるときは「足して、重なりを引く」：
- n（A∪B）＝n（A）＋n（B）−n（A∩B）
条件文p→qは「真→偽」のときだけ偽：
- 元の文と対偶は真偽が必ず一致する。逆と裏は一致するとは限らない
式を短くする方法は2つ：
- 演算則（特にド・モルガン）で変形する、またはカルノー図で「1」のかたまりをまとめる

集合論理：ものの集まりを記号で扱う

集合：
- ある条件を満たし、他のものとはっきり区別できるものの集まり
要素：
- 集合に属するもの。元（げん）ともいう
空集合：
- 要素数が0の集合。記号は ∅
有限集合：
- 要素が有限個の集合
無限集合：
- 要素が無限個の集合
部分集合：
- 1つの集合の中に考える、いくつかの要素の集まり
- 要素数がN個の集合の部分集合は、空集合と自分自身を含めて全部で 2ᴺ個
- 例：
  - U＝{1，2，3}の部分集合は 2³＝8個
真部分集合：
- AがBの部分集合で、AとBが一致しないとき、AをBの真部分集合という
べき集合：
- 部分集合を全部集めて、それを要素にした集合
- 例：
  - U＝{1，2，3}のべき集合＝{∅，{1}，{2}，{3}，{1，2}，{1，3}，{2，3}，{1，2，3}}
差集合 A−B：
- Aの要素で、Bの要素ではないものの集合（AからBを取り除いた残り）
- A−B＝A∩Bᶜ とも書ける（★過去問で問われた）
対称差 A△B：
- 「Aにあって Bにない」か「Bにあって Aにない」ものの集合（どちらか一方にだけあるもの）
- A△B＝（A−B）∪（B−A）＝（A∩Bᶜ）∪（Aᶜ∩B）
- 論理演算の排他的論理和にあたる
補集合の書き方：
- 集合Aの補集合は、上に線を引いて表すのが一般的だが、Aᶜ と書くこともある
集合の要素数 n（A）：
- 集合Aの要素の数
和集合の要素数の公式（★）
- 2つの場合：
  - n（A∪B）＝n（A）＋n（B）−n（A∩B）
- 3つの場合：
  - n（A∪B∪C）＝n（A）＋n（B）＋n（C）−n（A∩B）−n（B∩C）−n（C∩A）＋n（A∩B∩C）
- イメージ：
  - 全部足すと重なりを二重に数えてしまうので、その分を引く
例：
- 50人のクラスで、犬を飼っている人が20人、猫を飼っている人が15人、どちらも飼っていない人が22人のとき、両方飼っている人は？
- n（A∪B）＝50−22＝28
- 28＝20＋15−n（A∩B）なので、n（A∩B）＝7人
- 「どちらも飼っていない」＝n（Aᶜ∩Bᶜ）＝n（（A∪B）ᶜ）。これはド・モルガンの法則

命題と論理：正しいか正しくないかを記号で扱う

命題：
- 1つの判断や主張を記号や文章で表したもので、真（True）か偽（False）かがはっきり決まるもの
- 例：
  - 「今日は暑い」は人によって感じ方が違うので命題ではない。「7は奇数である」は真の命題、「9は素数である」は偽の命題
- ふつう p、q などの記号で表す
条件命題（命題関数）：
- 変数xを含み、xの値によって真偽が決まる命題。p（x）、q（x）と書く（変数が2つならp（x，y））
- 例：
  - 「xは偶数である」は、x＝4なら真、x＝3なら偽
複合命題（合成命題）：
- 複数の命題を「かつ」「又は」などで結んだ命題

種類	意味	記号	真になるとき
連言命題（合接命題）	pかつq	p∧q	両方とも真のときだけ真
選言命題（隣接命題）	p又はq	p∨q	少なくとも一方が真なら真（両方偽のときだけ偽）
否定命題	pでない	¬p	pが偽なら真
条件文（含意命題）	pならばq	p→q	pが真でqが偽のときだけ偽、それ以外は真
双条件文	pならばq、かつ、qならばp	p↔q（p≡q）	pとqの真偽が同じなら真

真理値表：
- 命題の真偽の組合せと、その結果を一覧にした表。真を1（T）、偽を0（F）で書く
真理集合：
- 命題が真になる範囲を、集合の図（ベン図）で表したもの
例：
- p：雨が降る、q：風が強い、とすると、「雨が降らず、風も強くない」は ¬p∧¬q（pもqも偽のときだけ真）
含意：
- 「真→偽」のときだけ結果が偽になる演算（→のこと）
p→qの読みかえ：
- 「pであってqでない、ということはない」と考える
- p→q ＝ ¬（p∧¬q）＝ ¬p∨q（ド・モルガンで展開）
前件と後件：
- 条件文p→qのpを前件、qを後件という
原子論理式：
- 論理式を組み立てている p や q のような、いちばん小さい論理式
トートロジー：
- 原子論理式の真偽にかかわらず、常に真になる論理式（例：p∨¬p）
矛盾式：
- 常に偽になる論理式（例：p∧¬p）
逆・裏・対偶（★）

名前	形	元の文（p→q）と真偽が一致するか
元の文	p→q	−
逆	q→p	一致するとは限らない
裏	¬p→¬q	一致するとは限らない
対偶	¬q→¬p	必ず一致する

覚え方：
- 逆は入れかえ、裏は否定、対偶は入れかえて否定。逆と裏は、互いに対偶の関係なので、逆と裏どうしは真偽が一致する
例（推論問題）：
- 前提：
  - 毎日、電車かバスのどちらか一方で通勤する。電車のときは必ず本を読み、バスのときは必ず音楽を聴く
- 「電車→本を読む」の対偶は「本を読まない→電車ではない」。電車でなければバスなので、「本を読まない日はバスに乗っている」は正しい
- 「本を読む日は電車に乗っている」は逆なので、正しいとはいえない（バスで音楽を聴きながら本も読む日もありうる）

論理演算：計算のルール

基本論理演算：
- 論理積演算（AND）、論理和演算（OR）、**否定演算（NOT）**の3つ。この3つの基本論理回路を組み合わせれば、いろいろな論理回路を作れる
演算記号の対応（どちらの記号で出ても計算できるようにする）

演算	論理演算の記号	集合演算の記号
論理積	・又は ∧	∩
論理和	＋又は ∨	∪
否定	上線又は ¬	上線又は ᶜ
排他的論理和	⊕	Δ（A△B＝（A∩Bᶜ）∪（Aᶜ∩B））

排他的論理和（XOR）の真理値表：

A	B	A⊕B
0	0	0
0	1	1
1	0	1
1	1	0

XORの使いみち：
- ビットの反転。反転したいビットだけ1にしたデータとXORをとる
- 例：
  - 8ビットデータの下位4ビットを反転するには、0F（16進）＝0000 1111 とXORをとる
  - 0101 1100 ⊕ 0000 1111 ＝ 0101 0011
演算則（論理演算と集合演算で同じ形になる）
- べき等則：
  - A・A＝A、A＋A＝A（集合：A∩A＝A、A∪A＝A）
  - べき等：
    - 同じ操作を何度繰り返しても同じ結果になること（例：A・A・A＝A・A＝A）
- 交換の法則：
  - A・B＝B・A、A＋B＝B＋A
- 結合の法則：
  - （A・B）・C＝A・（B・C）、（A＋B）＋C＝A＋（B＋C）
- 分配の法則：
  - A・（B＋C）＝（A・B）＋（A・C）
  - A＋（B・C）＝（A＋B）・（A＋C）（ふつうの数の計算では成り立たない形なので注意）
- 吸収の法則：
  - A＋（A・B）＝A、A・（A＋B）＝A
- ド・モルガンの法則（★）：
  - ¬（A・B）＝¬A＋¬B、¬（A＋B）＝¬A・¬B
  - 集合：（A∩B）ᶜ＝Aᶜ∪Bᶜ、（A∪B）ᶜ＝Aᶜ∩Bᶜ
  - 覚え方：
    - 否定を中に入れると、ANDとORが入れかわる
- その他：
  - A＋0＝A、A・0＝0、A＋1＝1、A・1＝A、A＋¬A＝1、A・¬A＝0
  - 集合：A∪∅＝A、A∩∅＝∅、A∪U＝U、A∩U＝A、A∪Aᶜ＝U、A∩Aᶜ＝∅（∅：空集合、U：全体集合）

論理式の簡略化：同じ意味のまま式を短くする

簡略化：
- 与えられた論理式と等価な（同じ結果になる）、より短い論理式を求めること
演算則を使う方法（例）：
- A・B＋A・¬B＋¬A・B を簡略化する
- 手順：
  - ①べき等則で A・B をもう1つ足す（足しても値は変わらない）
  - ②A・B＋A・¬B＋¬A・B＋A・B
  - ③第1・2項をAでくくり、第3・4項をBでくくる：A・（B＋¬B）＋B・（¬A＋A）
  - ④B＋¬B＝1、¬A＋A＝1 なので：A＋B
カルノー図：
- 論理式を図（マス目）で表したもの
- 手順：
  - ①論理式の各項にあたるマスに「1」、あたらないマスに「0」を入れる
  - ②「1」が縦か横に連続しているマスをまとめる
  - ③まとめた範囲で、真偽に関係なくなった変数を消す
- 上の例：
  - A＝1の行はBに関係なく1なので A、B＝1の列はAに関係なく1なので B。合わせて A＋B
変数が4つのカルノー図：
- 変数A，Bと変数C，Dに分けて、4行×4列の図で考える。行と列の並びは 00→01→11→10（隣どうしで1ビットだけ変わる順）
- 図の端どうし（例えば左端の列と右端の列）もつながっているとみなしてまとめられる

混同しやすいペア

差集合 A−B（Aだけにあるもの）／対称差 A△B（どちらか一方だけにあるもの）
部分集合（自分自身も含む）／真部分集合（自分自身とは一致しない）
部分集合（集まりの一部）／べき集合（部分集合を全部集めた集合。要素数は2ᴺ）
逆（q→p）／裏（¬p→¬q）／対偶（¬q→¬p。これだけ元と必ず同じ真偽）
連言（かつ、∧）／選言（又は、∨）
条件文 p→q（真→偽のときだけ偽）／双条件文 p↔q（真偽が同じときだけ真）
トートロジー（常に真）／矛盾式（常に偽）
論理和 OR（両方1でも1）／排他的論理和 XOR（両方1なら0）

情報理論と符号化

一言で言うと：
- 情報の「量」をビットで測り、データをできるだけ短くし（圧縮）、音などのアナログをデジタルに変える話。

量を測る（情報量）→ 短くする（情報源符号化）→ デジタルにする（デジタル符号化）

覚え方の軸

情報量は「めずらしいほど大きい」：
- I＝−log₂P。確率が1/2ⁿなら、ちょうどnビット
平均情報量（エントロピー）は「あいまいさ」：
- どれも同じ確率で起こるとき最大（k個ならlog₂k）。結果がわかりきっていれば0
圧縮の考え方は2つ：
- よく出るものを短い符号にする（ハフマン符号化）、同じものが続く部分をまとめる（ランレングス符号化）
PCMは「標本化 → 量子化 → 符号化」：
- データ量＝サンプリング周波数×量子化ビット数×秒数（÷8でバイト）

情報量：情報の大きさをビットで測る

情報には、情報の質（内容が妥当か、正当か）と情報の量（多いか少ないか）の両面がある。ここでは量の話
情報：
- 処理の対象は、すべて有限長のビット列に符号化される。この符号化されたデータに、何らかの意味（判断に必要な知識）を付けたものが「情報」
情報量 I（information content）：
- ある事象Jが起こったときに伝わる情報の大きさ。単位はビット
- 情報量 I（J）＝ −log₂P（J）（P（J）は事象Jの生起確率、0≦P（J）≦1）
例：
- コインを投げて表が出る（確率1/2）：
  - −log₂（1/2）＝ −log₂2⁻¹ ＝ 1ビット
- サイコロで1が出る（確率1/6）：
  - −log₂（1/6）＝ log₂6 ≒ 2.58 → 3ビット
性質：
- 生起確率が大きい（よく起こる）ほど、情報量は小さい
- 生起確率が小さい（めずらしい）ほど、情報量は大きい
「何ビット必要か」の尺度としても使える
- 例：
  - 3桁の数字（000〜999の1,000通り）を表すには、−log₂（1/1000）＝log₂1000 ≒ 9.97 → 10ビット必要
- 簡単な見積もり方：
  - 2⁹＝512、2¹⁰＝1024 なので、9＜log₂1000＜10。つまり「9.…」とわかる
対数の重要公式（a＞0、a≠1、M＞0、N＞0）
- logₐa＝1、logₐ1＝0
- logₐMᵏ＝k×logₐM
- logₐM＝log_bM ÷ log_ba（底の変換。bは何でもよい）
- logₐ（M/N）＝logₐM−logₐN
- logₐMN＝logₐM＋logₐN
- 暗記：
  - log₁₀2＝0.301、log₂10＝3.32
情報量の加法性：
- 互いに独立な事象JaとJbが同時に起こったときの情報量は、それぞれの情報量の和
- 例：
  - 「コインで表が出る」と「サイコロで1が出る」が同時に起こる：1＋2.58＝3.58 → 4ビット
平均情報量 H（エントロピー）：
- すべての事象（J₁〜Jₙ）の、情報量の平均
- H＝Σ{P（Jₖ）×I（Jₖ）}（k＝1〜n）
- 意味：
  - あいまいさの程度。小さいほど予測しやすく、大きいほど予測しにくい
- 例：
  - 当たり50%・はずれ50%：H＝0.5×1＋0.5×1＝1ビット（2つの事象で最大。いちばん予測しにくい）
  - 当たり70%・はずれ30%：H＝0.7×（−log₂0.7）＋0.3×（−log₂0.3）≒0.7×0.515＋0.3×1.737≒0.88ビット（あいまいさが減る）
  - 当たり100%：H＝1.0×（−log₂1.0）＝0ビット（あいまいさなし）
- 最大平均情報量：
  - 事象がk個のとき、−log₂（1/k）＝log₂k。k＝2なら1

情報源符号化：データを短くする

通信路符号化：
- 情報を正しく伝えるための符号化（パリティチェック、CRC、ハミング符号など）
情報源符号化：
- 大きな情報を、できるだけ**短く（小さく）**するための符号化
情報源：
- 情報を記号の並び（一定の順序に従って並べた一連のもの）とみなしたとき、その記号を次々に発生させる源
ハフマン符号化（★試験によく出る）：
- 出現率の高い文字は短いビット列、低い文字は長いビット列で符号化し、1文字あたりの平均ビット長を最小にする圧縮方法
- 4文字（a〜d）なら1文字2ビットで区別できるが、出現率に差があれば平均2ビットより短くできる
例：

文字	符号	出現確率
a	0	40%
b	10	30%
c	110	20%
d	111	10%

1文字あたりの平均ビット数（期待値）＝
- 1×0.4＋2×0.3＋3×0.2＋3×0.1＝1.9ビット（2ビット固定より短い。100文字で約190ビット）
期待値 E（X）＝
- x₁p₁＋x₂p₂＋…＋xₙpₙ ＝ Σxᵢpᵢ（値×確率を全部足す。確率の合計は1）
Σ記号：
- 和を表す。例えば Σ2k（k＝1〜5）は「kを1から5まで1ずつ増やしながら2kを足す」
- 性質：
  - Σ（a×k）＝a×Σk、Σa＝n×a（aは定数）
ハフマン木の作り方（葉から根へ、ボトムアップに作る）
- 手順：
  - ①文字を葉にして、出現確率を重みにした「葉だけの木」を作る
  - ②重みの大きい順に並べる
  - ③重みが最小の木を2つ選び、それを子にもつ木を作る（重みは2つの和）
  - ④1つの木になるまで②③を繰り返す
- 符号の読み方：
  - 根から目的の文字（葉）へ進み、左に進むと「0」、右に進むと「1」
- 例（上の表）：
  - d（10%）とc（20%）をまとめて30% → それとb（30%）をまとめて60% → それとa（40%）をまとめて100%。a＝0、b＝10、c＝110、d＝111
ランレングス符号化：
- データの冗長さに注目し、同じ値が続く部分を「反復回数とデータ値の組」に置きかえて短くする圧縮方法
- 例（「続く個数から1を引いた数を1バイトで書き、その後に文字を置く」方式）：
  - PPPPPPPQRRRR（12バイト）→ 6P 0Q 3R（6バイト）。圧縮率50%
  - Pが7個なので「6P」、Qが1個なので「0Q」、Rが4個なので「3R」
  - 注意：
    - 1個しかない文字も「0Q」の2バイトになるので、同じ文字があまり続かないデータでは、かえって長くなる
- この方式で圧縮率が最大になるのは、256個の同じ文字を2バイトにするとき
- 2値画像の圧縮にも使う。同じ色が続いた個数だけを記録する
  - 例：
    - 白0・黒1で「0000000011111000」→「8，5，3」
  - 最初は白から始まるものとする。最初の画素が黒なら、先頭に「白が0個」あるとして符号化する

デジタル符号化：アナログをデジタルに変える

PCM（パルス符号変調、Pulse Code Modulation）：
- アナログデータをデジタル符号に変える方式
PCMの手順（★順番が大事）
- ①標本化（サンプリング）：
  - アナログ信号を一定の時間間隔で切り出す
  - サンプリング周波数：
    - 1秒間にサンプリングする回数
  - サンプリング周期：
    - サンプリングの時間間隔。サンプリング周波数の逆数
- ②量子化：
  - 切り出したアナログ値をデジタル値（整数）に変える
  - 量子化ビット数：
    - 1回のサンプリングで作られるビット数。8ビットなら0〜255の値になる
- ③符号化：
  - デジタル値を2進数のビット列にする（例：200→11001000、150→10010110）
1秒間に生成されるデータ量＝
- サンプリング回数（＝サンプリング周波数）× 量子化ビット数
例：
- サンプリング周波数8kHz、量子化ビット数8ビットで5秒間：
  - （8×10³）×8×5 ÷ 8 ＝ 40kバイト
例：
- 44.1kHz、16ビット、ステレオ（2チャネル）で1秒：
  - 44.1×10³×16×2 ÷ 8 ＝ 176.4kバイト
標本化定理：
- 元の信号に含まれる周波数成分が、サンプリング周波数の1/2未満なら、標本点の値だけで元の信号を完全に復元できる（逆にいえば、最高周波数の2倍より大きい周波数でサンプリングすればよい）
PCMの改良方式
- DPCM（差分PCM）：
  - 直前の標本との差分を量子化して、データ量を減らす
- ADPCM（適応的差分PCM）：
  - DPCMをさらに改良し、差分を表すビット数を変動幅に応じて変える。主に音声用で、PCMの約1/4に圧縮できる

混同しやすいペア

情報量（1つの事象の大きさ。−log₂P）／平均情報量（全事象の平均。あいまいさ）
通信路符号化（正しく伝える：パリティ、CRC、ハミング）／情報源符号化（短くする：ハフマン、ランレングス）
ハフマン符号化（出現率で符号の長さを変える）／ランレングス符号化（連続部分を個数でまとめる）
標本化（時間で切る）／量子化（値をデジタルにする）／符号化（2進数にする）
サンプリング周波数（1秒の回数）／サンプリング周期（間隔。周波数の逆数）
DPCM（差分を量子化）／ADPCM（差分のビット数も変える）

オートマトン

一言で言うと：
- 「今の状態」と「入力」で次の状態が決まる機械のモデル。文字列が決まった形になっているかを判定する（字句解析など）のに使う。

状態をもつ機械（順序機械・有限オートマトン）→ 正規表現との関係 → もっと強い機械（その他のオートマトン）

覚え方の軸

順序機械は「入力＋今の状態」で決まる：
- 出力と次の状態が、入力だけでなく今の状態にもよる（＝過去を覚えている）
有限オートマトンは5つ組：
- 状態の集合K、入力記号の集合Σ、状態遷移関数δ、初期状態q₀、受理状態の集合F
判定のルールは「最後にいる状態」：
- 入力を全部読み終えたとき、受理状態（◎）にいれば受理
オートマトンの強さの順番と、認識できる言語：
- 有限オートマトン（正規言語）＜プッシュダウンオートマトン（文脈自由言語）＜チューリング機械（句構造言語）

有限オートマトン：状態を移りながら文字列を読む機械

順序機械：
- 1つの入力値で1つの出力値が決まるのではなく、入力値と、そのときの状態によって出力値（と次の状態）が決まる機械
- フリップフロップ回路や自動販売機のように、過去の状態を記憶できる回路や機械をモデル化したもの
- ブラックボックスで表すと：
  - 入力（t）と状態（t）から、出力（t）と次の状態（t＋1）が決まる（tは時刻）
状態遷移表：
- 状態と入力の組合せごとに、「出力」と「次の状態」を書いた表
状態遷移図：
- 状態を丸、遷移を矢印で描いた図。矢印に「入力/出力」を書く（例：1/0は入力1で出力0）
- 例：
  - 状態Pのとき1を入力すると、0を出力してQへ遷移する、という具合に読む
有限オートマトン（FA：Finite Automaton）：
- 順序機械に、言語を認識するアルゴリズムを与えた数学的なモデル
- 定義（5つ組）：
  - 有限オートマトン＝＜K，Σ，δ，q₀，F＞
  - K：
    - 状態の有限集合
  - Σ：
    - 入力記号の有限集合
  - δ：
    - 状態遷移関数（今の状態と入力記号から、次の状態を決める）
  - q₀：
    - 初期状態（Kの要素の1つ）
  - F：
    - 受理状態集合（Kの部分集合）
- 状態遷移関数の書き方：
  - 状態aで入力0を受けて状態bに移るなら、δ（a，0）＝b
  - δは「K×Σ から K への写像」。K×Σは集合KとΣの直積集合（全部の組合せ）
- 状態遷移図の書き方：
  - 初期状態を「➡」、受理状態を「◎」で表す
例：
- 「末尾が01で終わるビット列」を受理する有限オートマトン
- K＝{a，b，c}、Σ＝{0，1}、q₀＝a、F＝{c}

状態	入力0	入力1
a（初期）	b	a
b	b	c
c（受理）	b	a

状態の意味：
- a＝まだ何も読んでいないか最後が「1」（01の途中ではない）、b＝最後が「0」、c＝最後が「01」
「1101」：
- a→a→a→b→c。最後がcなので受理する
「0110」：
- a→b→c→a→b。最後がbなので受理しない
有限オートマトンのモデル：
- テープに書かれた入力ビット列を読む有限状態機械とみなせる
- 動き方：
  - 入力ヘッドをテープの左端に置き、初期状態から始める → 1マス読むと状態遷移関数に従って遷移し、ヘッドを1マス右に進める → 最後のビットを読んで遷移した先が受理状態集合Fに入っていれば受理
- 有限状態部：
  - 今の状態を持っている部分
- 入力テープ：
  - 右に延びた半無限長のテープ。入力ビット列が左から1マス1ビットずつ書かれている。空白はビット列の区切り

有限オートマトンと正規表現

正規言語：
- 正規表現で表される言語。有限オートマトンは、正規言語を認識するために使う
正規表現のメタ記号（詳しくは後の「正規表現」）
- r1|r2：
  - r1 又は r2
- (r)*：
  - r の0回以上の繰返し
例：
- 正規表現 0(10)* が表す文は、0、010、01010、0101010、…
- 特徴：
  - 「0で始まり0で終わり、0と1が交互に並ぶ」
- これを受理する有限オートマトン：
  - Q₀（初期）：0なら Q₁ へ、1なら Q₃ へ
  - Q₁（受理）：1なら Q₂ へ、0なら Q₃ へ
  - Q₂：0なら Q₁ へ戻る、1なら Q₃ へ
  - Q₃：0でも1でも Q₃ のまま（一度入ると出られない。交互にならなかったら不合格）
正規表現から有限オートマトンを作る方法は出題範囲外。試験では「この有限オートマトンが受理する正規表現はどれか」が問われる

その他のオートマトン

プッシュダウンオートマトン：
- 文脈自由文法から作られる文脈自由言語を認識する
- 有限オートマトンにプッシュダウンストアというスタックを付けたもの。入力記号、スタックの一番上の記号、今の状態で次の状態を決める
チューリング機械（チューリングマシン）：
- プッシュダウンオートマトンより能力が高い。ノイマン型コンピュータの動作原理の理論的な基本モデル
- 句構造言語を認識する

混同しやすいペア

順序機械（入力と状態で決まる。過去を覚える）／有限オートマトン（順序機械に言語を認識させるもの）
状態遷移表（表）／状態遷移図（丸と矢印）
初期状態 q₀（➡、1つ）／受理状態集合 F（◎、0個以上の集合）
有限オートマトン（正規言語）／プッシュダウンオートマトン（文脈自由言語、スタック付き）／チューリング機械（句構造言語、コンピュータのモデル）

形式言語

一言で言うと：
- プログラム言語の「文法」を記号で決め、コンパイラがその文法に沿って文を分解し、正しいかチェックし、中間のコードにする話。

文法を決める（形式文法と言語処理）→ 文法の書き方（BNF・構文図）→ 解析して中間語にする（構文木・逆ポーランド）→ 字句のパターン（正規表現）

覚え方の軸

解析は2段階で、道具がそれぞれ決まっている：
- 字句解析＝字句規則＝正規表現＝有限オートマトン
- 構文解析＝構文規則＝文脈自由文法＝BNF
文脈自由文法は G＝（N，T，P，S）：
- 非終端記号N、終端記号T、生成規則P、開始記号S。生成規則の左辺は必ず非終端記号1つ
BNFは「再帰」で繰り返しを表す：
- ＜式＞::＝＜項＞|＜式＞＜加減演算子＞＜項＞。括弧を使えるようにするなら＜因子＞::＝数|'(‘＜式＞’)’
構文木から中間語へ：
- 3つ組（演算子，左，右）、4つ組（＋結果の置き場所）、逆ポーランド（後行順＝左→右→節）
正規表現のメタ記号は5つ：
- [m−n]（範囲の1文字）、*（0回以上）、+（1回以上）、?（0か1回）、|（又は）

形式文法と言語処理：文法を記号で決める

自然言語：
- ふだん使っている言語
人工言語：
- 特定の目的のために作られた言語。そのうちコンピュータ処理のための言語がプログラム言語。ほとんどの構文は文脈自由文法で表せる
言語：
- 1つの規則に基づく文の集合
形式文法：
- 言語を作る規則を抽象化したもの。基本的なものに句構造文法、文脈依存文法、文脈自由文法、正規文法がある
- 形式文法で作られる抽象的な言語を形式言語という
文脈自由文法（形式文法）：
- **G＝（N，T，P，S）**で定義する
- N：
  - 非終端記号の集合（書きかえの対象になる記号）
- T：
  - 終端記号の集合（これ以上書きかえられない記号）
- P：
  - 書換え（生成）規則の集合
- S：
  - 開始記号（書きかえを始める最初の非終端記号）
- 特徴：
  - 書換え規則の左辺が必ず1つの非終端記号
- 文脈自由言語：
  - 文脈自由文法で作られる文の集合
例（★試験では正しい生成の過程が問われる）：
- N＝{S}、T＝{0，1}、P＝{S→ε，S→0S1}
- ①S ⇒ 0S1 ⇒ 01
- ②S ⇒ 0S1 ⇒ 00S11 ⇒ 0011
- つまり、この文法は「0をn個並べたあとに1をn個並べた列」（ε、01、0011、000111、…）を作る
- ε：
  - 空列（長さ0の記号列）
- 記号「→」は生成の実行（左辺の非終端記号を、規則に従って右辺で置きかえる）。右辺は長さ0以上の、非終端記号と終端記号の並び
言語の構成要素（小さい順）：
- 文字＜字句（トークン）＜文＜言語
字句：
- トークンともいう。文を作る最小の単位
字句規則：
- 文字から字句を作るための規則
構文規則：
- 字句の正しい並べ方の規則
プログラムを実行する前に、文法に基づいて翻訳（コンパイル）する。字句解析と構文解析を自動化するには、字句規則と構文規則をきちんと定義する必要がある
例（括弧を使わない四則演算の式。price＊3−tax など）
- 字句規則：
  - 数は、0〜9の数文字からなる長さ1以上の列
  - 変数は、a〜zの英小字から始まる長さ1以上の列
  - 演算子は、＋、−、＊、／のどれか
- 構文規則：
  - 数は式。変数は式。「式演算子式」と並べたものも式
- この式を作る文脈自由文法：
  - N＝{式，S}、T＝{数，変数，演算子}、P＝{S→式，式→数，式→変数，式→式演算子式}
字句解析：
- 字句規則に基づいて、字句の検査と切り出しを行う
- 字句規則は正規表現で表せる。正規表現には、それと等価な有限オートマトンがある。字句解析は、この有限オートマトンで行う
- 例：
  - 「数」は正規表現 [0-9]+ で表せる。Q₀から数字で Q₁（受理）へ、Q₁で数字が続けば Q₁ のまま
構文解析：
- 切り出した字句を構文規則に従って解析し、文法的に正しいかを検査する
- 構文規則は文脈自由文法で表せる。それを形式的に書く代表的な記法がBNF

構文規則の記述：BNFと構文図

BNF記法：
- Algol60の構文規則を書くのに使われた記法。今も多くのプログラム言語の構文規則に使われる
- 文脈自由文法を形式的に書く代表的な方法。構文規則だけでなく、字句規則にも使う
BNFの記号
- ::=：
  - 左辺と右辺の区切り（右辺で左辺を定義する。is defined as）
- |：
  - 又は（or）
- < >：
  - 非終端記号をくくる（＜数字＞、＜英字＞）
- a、b、c…、0、1、…9：
  - 終端記号
例：
- ＜英数字＞::＝＜英字＞|＜数字＞
- ＜数字＞::＝0|1|2|…|9
- ＜英字＞::＝a|b|c|…|z
算術式（四則演算）の構文（★よく出る）
- ＜式＞::＝＜項＞|＜式＞＜加減演算子＞＜項＞
- ＜項＞::＝＜因子＞|＜項＞＜乗除演算子＞＜因子＞
- ＜因子＞::＝数
- ＜加減演算子＞::＝＋|−
- ＜乗除演算子＞::＝＊|／
- ポイント：
  - ＊／が＜項＞の中、＋−が＜式＞の中にあるので、掛け算・割り算が先にまとまる
括弧を追加する場合（★試験で書きかえが問われる）：
- ＜因子＞::＝数|'(‘＜式＞’)’
- 括弧の中身を＜因子＞として扱えば、括弧の中が先に計算される
再帰的定義：
- 自分の定義に自分自身を使うこと（＜式＞の定義に＜式＞が出てくる）。BNFではこれで「繰り返し」を表す（★よく問われる）
構文図：
- BNFを、矢印でたどれる図にしたもの。再帰的な定義が読みやすくなる
- ＜式＞の読み方：
  - 「＜項＞1つでも＜式＞」「＜式＞に＜加減演算子＞と＜項＞が続いたら、また＜式＞」
基本構文図：
- ①Aが1回以上現れる
- ②Aが0回以上現れる
- ③Aが0回か1回現れる
- ④AかBが現れる
例：
- ＜偶数長列＞::＝＜組＞|＜偶数長列＞＜組＞、＜組＞::＝＜記号＞＜記号＞、＜記号＞::＝a|b
- ＜偶数長列＞は「2文字の組が1個以上」なので、長さが2の倍数。「abba」は合う、「aba」（3文字）は合わない

構文解析の技法：構文木と中間語

構文木（解析木）：
- 構文解析で、字句が構文規則に合っているかを構文解析表で調べながら、字句を木の形で表したもの
- 算術式の構文木を、特に算術木という
- 例：
  - Y＝A＋B＊C−D の構文木は、根が「＝」、その下に Y と「−」、「−」の下に「＋」と D、「＋」の下に A と「＊」、「＊」の下に B と C
下降型構文解析法：
- 文法に沿って、構文木を上から下へ作る
上昇型構文解析法：
- 構文木を下から上へ作る
構文規則に合った文と判断されたら、次は意味解析に進む。構文解析の結果から、3つ組み、4つ組み、逆ポーランド表記法などで**中間語（中間コード）**を作る
3つ組み：
- 構文木の下のほうの部分木から順に、「演算子，左の項，右の項」の形でまとめる
- 例（上の式）：
  - L1（＊，B，C）、L2（＋，A，L1）、L3（−，L2，D）、L4（＝，Y，L3）
4つ組み：
- 3つ組みに、各部分木の演算結果を何に置くかを追加したもの
- 例（上の式）：
  - L1（＊，B，C，T1）、L2（＋，A，T1，T2）、L3（−，T2，D，T3）、L4（＝，T3，∅，Y）
  - L1 は「B＊Cの結果をT1に入れる」という意味。∅は空値
逆ポーランド表記法（★）：
- 演算子を、演算の対象（演算数）の右側に書く記法。後置表記法ともいう
- 構文木からの変換：
  - 構文木を深さ優先で、後行順序木として（帰りがけのなぞり。左→右→節の順）たどる。各ノードを最後に出るときに読む
- 例：
  - Y＝A＋B＊C−D → Y A B C ＊＋ D − ＝
- 式から直接変換する方法：
  - 最後に作用する演算から始めて、内側へ順に「［演算数，演算数］演算子」の形にしていき、最後に括弧とカンマを取る
  - ［Y，（A＋B＊C−D）］＝ → ［Y，［（A＋B＊C），D］−］＝ → ［Y，［［A，（B＊C）］＋，D］−］＝ → ［Y，［［A，［B，C］＊］＋，D］−］＝ → Y A B C ＊＋ D − ＝
- 例：
  - （A＋B）×C → A B ＋ C ×（括弧の中のA＋Bを先に計算してからCを掛ける）

正規表現：字句のパターンを決める

正規表現：
- 字句記号や探索記号の定義などに広く使われるパターン定義法。正規式ともいう
記号列：
- 0個以上の記号を並べたもの。a₁a₂a₃…aₙ と書く
- 記号列の長さ：
  - 記号の個数
- 空列：
  - 長さ0の記号列。記号 ε
アルファベット V：
- 記号列の材料になる有限集合。Vから要素を（重複してよい）取り出して作った記号列を「V上の記号列」という
V＊：
- V上の記号列すべての集合。字句は V＊の部分集合
- 例：
  - V＝{x，y}なら、V＊には x、y、xy、yyx、xxyx、… が含まれる
正規表現のメタ記号（メタ文字。★意味は試験問題に示される）
- [m-n]：
  - m〜n までの連続した文字のうちの1文字
- *：
  - 直前の正規表現の0回以上の繰返し
- +：
  - 直前の正規表現の1回以上の繰返し
- ?：
  - 直前の正規表現が0個か1個
- r1|r2：
  - r1 又は r2
＊、＋、？の違い
- GOO*：
  - GO、GOO、GOOO など（2つ目のOなしもよい）
- GOO+：
  - GOO、GOOO、GOOOO など（2つ目のOが最低1つ）
- GOAL?：
  - GOA 又は GOAL
例：
- 「英小文字a〜zが1回以上、続いて数字0〜9が0個か1個」は [a-z]+[0-9]?
- abc、x7、hello3 などがこの集合の要素。hello35（数字2個）は要素ではない
正規表現の短縮：
- tanaka と tanuka：
  - tanaka|tanuka → 違いは4文字目だけなので tan(a|u)ka
- tanaka、tanuka、tanouka：
  - tan(a|o?u)ka

混同しやすいペア

字句解析（字句の切り出し：正規表現、有限オートマトン）／構文解析（並べ方のチェック：文脈自由文法、BNF）
字句規則（文字 → 字句）／構文規則（字句の並べ方）
非終端記号（書きかえられる。BNFでは＜＞）／終端記号（これ以上書きかえられない）
3つ組み（演算子，左，右）／4つ組み（＋結果の置き場所）
逆ポーランド（後置）（演算子が右。後行順＝左→右→節）
下降型（上から下へ）／上昇型（下から上へ）
正規表現の＊（0回以上）／＋（1回以上）／？（0か1回）
構文図の 1回以上／0回以上／0か1回

グラフ理論

一言で言うと：
- 点（頂点）と線（辺）のつながりを扱う話。ネットワークの経路探索、工程の順番、最短経路などの土台になる。

向きの有無（有向・無向）→ 閉路の有無（サイクリック）→ グラフの種類 → コンピュータでの表し方 → 最短経路（重みつきグラフ）

覚え方の軸

グラフは2つの切り口で分ける：
- 向きがあるか（有向／無向）、ぐるっと戻れるか（サイクリック／非サイクリック）
「1回だけ通る」のが辺か頂点か：
- オイラー＝すべての辺を1回ずつ（一筆書き）、ハミルトン＝すべての頂点を1回ずつ
表し方は3つ：
- 配列、行列（隣接行列）、リスト。行列は大きくなりやすいので、0が多い（疎な）ときはリスト
隣接行列 M の M² は「辺2本の経路の数」
ダイクストラ法は「近い頂点から1つずつ確定」

有向グラフ・無向グラフ：線に向きがあるか

グラフ：
- 頂点の集合Vと、2つの頂点を結ぶ辺の集合Eからなる図形。**G＝（V，E）**と書く
- 頂点（Vertex）：
  - 節点ともいう
- 辺（Edge）：
  - 枝ともいう
有向グラフ：
- 辺に向き（vᵢ→vⱼ）があるグラフ
無向グラフ：
- 辺に向きがないグラフ
順序対（vᵢ，vⱼ）：
- 有向グラフで、辺の向きを表したもの
- 始点：
  - vᵢ（辺が出ていく頂点）
- 終点：
  - vⱼ（辺が入ってくる頂点）
- vᵢとvⱼは「隣接している」という
- vᵢをvⱼの先行点、vⱼをvᵢの後続点ともいう
入次数：
- 頂点に入ってくる辺の数
出次数：
- 頂点から出ていく辺の数
次数：
- 入次数と出次数の和
自己ループ：
- 始点と終点が同じ頂点である辺
多重辺（並列辺）：
- 始点と終点が同じ組である、複数の辺

サイクリックグラフ：ぐるっと戻れるか

閉路（cycle）：
- ある頂点から出発して、同じ頂点に戻ってこられる道
サイクリックグラフ：
- 閉路をもつ有向グラフ
非サイクリックグラフ：
- 閉路をもたない有向グラフ
トポロジカル順序：
- 非サイクリックグラフで、すべての辺（vᵢ，vⱼ）について、iがjより前になるように頂点を一列に並べた順序
- 例：
  - 辺が A→B、A→C、B→D、C→D なら、A−B−C−D や A−C−B−D がトポロジカル順序
- 1つのグラフに、トポロジカル順序が複数あることもある

小道（trail）と経路（path）

歩道：
- 連続した頂点と辺を結んだもの。（v₁，e₁，v₂，e₂，…）のように頂点と辺を交互に書く
小道（trail）：
- すべての辺が異なる歩道（同じ頂点は2回通ってもよい）
経路（path）：
- すべての頂点が異なる歩道
回路（circuit）：
- 同じ頂点に戻る小道（辺が全部異なる）
閉路（cycle）：
- 同じ頂点に戻る経路（頂点が全部異なる）

グラフの種類

種類	中身
多重グラフ	自己ループや多重辺をもつグラフ
完全グラフ	どの2頂点の間も1本の辺で結ばれているグラフ。頂点数nの完全グラフを Kₙ と書く
2部グラフ	頂点を2つのグループV₁とV₂に分けられ、どの辺もV₁とV₂をまたいでいるグラフ（同じグループどうしを結ぶ辺がない）
オイラーグラフ	すべての辺をちょうど1回ずつ通って出発点に戻る回路（オイラー回路）をもつグラフ。一筆書きができる
ハミルトングラフ	すべての頂点をちょうど1回ずつ通って出発点に戻る閉路（ハミルトン閉路）をもつグラフ
正則グラフ	すべての頂点の価数（その頂点につながる辺の本数）が等しいグラフ

単純グラフ：
- 自己ループも多重辺もないグラフ
2部グラフの関係：
- V₁∪V₂＝V、V₁∩V₂＝∅（全部をちょうど2つに分ける）
★試験：
- 2部グラフとハミルトン閉路は午前（科目A）で、オイラーグラフは午後（科目B）で出題されている

グラフの表現：コンピュータでどう持つか

例のグラフ：
- 頂点①〜④、辺は ①−②、②−③、③−④、④−① の4本（無向。四角形の形）
配列表現：
- 辺の両端の頂点を、2つの配列に入れる
- 例：
  - vᵢ＝［①，①，②，③］、vⱼ＝［②，④，③，④］
行列表現：
- 隣接行列（頂点数×頂点数の正方行列）で表す。vᵢとvⱼを結ぶ辺があれば要素（i，j）を1、なければ0
- 例の隣接行列 M：

	①	②	③	④
①	0	1	0	1
②	1	0	1	0
③	0	1	0	1
④	1	0	1	0

1行2列の1は、①と②を結ぶ辺があるという意味
短所：
- 頂点が多いと行列が大きくなり、記憶域が膨大になる。多くのグラフアルゴリズムは行列の掛け算が必要なので、処理時間もかかる
疎（そ）：
- 行列の要素のほとんどが0であること。隣接行列が疎なら、動的なデータ構造を使えるリスト表現のほうが効率的
接続行列：
- 行が頂点、列が辺に対応する行列。頂点vᵢと辺eⱼがつながっていれば（i，j）を1、それ以外は0
リスト表現：
- 行列表現の各行を、線形リストで表したもの。隣接リストともいう
- 例：
  - ①→②→④、②→③、③→④（④からは何もない）
- 無向グラフでは「①−②」と「②−①」は同じ辺なので、行列の右上部分だけを表せばよく、記憶域を節約できる
行列表現の応用（★）：
- 隣接行列Mの要素mᵢⱼを「vᵢとvⱼを直接結ぶ辺の本数」とするとき、M²の（i，j）要素は、vᵢとvⱼが1つの頂点をはさんで結ばれる経路（辺2本の経路）の数
- 例のM²：

	①	②	③	④
①	2	0	2	0
②	0	2	0	2
③	2	0	2	0
④	0	2	0	2

M²の1行3列は、Mの1行目と3列目の掛け算の合計（ベクトルの内積）：
- （①①の辺数×①③の辺数）＋（①②×②③）＋（①③×③③）＋（①④×④③）＝ 0×0＋1×1＋0×0＋1×1 ＝ 2
- 意味：
  - ①−②−③ と ①−④−③ の2つの経路がある
M²の1行2列が0なのは、①から②へ「辺ちょうど2本」で行く経路がないから（四角形の隣どうしは、2本では行けない）

重みつきグラフ：最短経路を探す

重みつきグラフ：
- 辺に値（距離やコスト）をもたせたグラフ。重みつきネットワークともいう
最短経路問題：
- 始点から目的点までの最短の経路を求める問題
ダイクストラ法（★）：
- 始点の隣から、いちばんコストが小さい頂点を1つずつ確定していき、範囲を広げて、すべての頂点への最小コストを求める
- 手順：
  - ①まだ確定していない頂点のうち、始点からのコストが最小の頂点を選んで確定する（＊を付ける）
  - ②確定した頂点を経由する経路のコストを計算し直す。始点から同じ頂点に入る経路が複数あれば、大きいほうを消す
  - ③全部確定するまで①②を繰り返す
例：
- 辺：A→B 4、A→C 2、C→B 1、B→D 5、C→D 8
- ①Aの隣で最小はC（2）→ Cを確定（2）
- ②Cを経由：A→C→B＝3（A→B 4より小さいので4を消す）、A→C→D＝10
- ③残りで最小はB（3）→ Bを確定（3）。Bを経由：A→C→B→D＝8（10より小さいので10を消す）
- ④Dを確定（8）
- 確定する順番は C → B → D、最小コストは 8、経路は A→C→B→D
★試験では、最小コストだけでなく、各頂点のコストが確定していく順番も問われる

混同しやすいペア

有向グラフ（向きあり）／無向グラフ（向きなし）
入次数（入ってくる）／出次数（出ていく）／次数（その和）
自己ループ（自分に戻る辺）／多重辺（同じ2頂点を結ぶ複数の辺）
サイクリック（閉路あり）／非サイクリック（閉路なし。トポロジカル順序がある）
小道（辺が全部異なる）／経路（頂点が全部異なる）
回路（戻る小道）／閉路（戻る経路）
オイラー（辺を1回ずつ。一筆書き）／ハミルトン（頂点を1回ずつ）
完全グラフ（全部の2頂点がつながる）／正則グラフ（全頂点の価数が同じ）／2部グラフ（2グループをまたぐ辺だけ）
隣接行列（頂点×頂点）／接続行列（頂点×辺）
行列表現（大きいが計算しやすい）／リスト表現（疎なとき省スペース）

確率と統計

一言で言うと：
- 「どのくらい起こりやすいか（確率）」と、「データの真ん中とばらつき（統計）」の話。待ち行列、品質管理、AIの土台になる。

数え方と確率の基本（確率）→ 原因の逆算と状態の移り変わり（確率の応用）→ データの分布（確率分布）

覚え方の軸

「または」は足す、「かつ」は掛ける：
- 和の法則・加法定理（重なりがあれば引く）、積の法則・乗法定理（従属なら条件付き確率を掛ける）
原因の確率（ベイズ）は「その原因の分 ÷ 全体」：
- 結果が起こる全確率を、原因ごとに分けて足してから割る
マルコフ過程は「直前だけで決まる」：
- 推移行列を2乗すると2段階後
データは「真ん中」と「ばらつき」で見る：
- 代表値（平均・中央値・最頻値）、散布度（レンジ・分散・標準偏差）
正規分布の数字は 68.3 → 95.4 → 99.7：
- μ±1σ、±2σ、±3σの中に入る割合。分散は和でも差でも足す

確率：数え方と基本ルール

場合の数：
- ある事柄（事象）の起こり方の総数
- 例：
  - サイコロの目の出方は6通り
積の法則：
- Aの起こり方がm通り、その各々に対してBの起こり方がn通りなら、AとBがともに起こる場合の数は m×n通り
和の法則：
- 同時には起こらないAとBで、Aがm通り、Bがn通りなら、A又はBが起こる場合の数は m＋n通り
組合せ nCr（★）：
- n個の異なるものから r個を選ぶ選び方の数（並べる順番は考えない）
- nCr ＝ n! ÷ {r!×（n−r）!}
- nC1＝n、nCn＝1、nC0＝1
- 例：
  - 5C2＝5!÷（2!×3!）＝120÷（2×6）＝10
順列：
- 取り出したものを順に並べる並べ方の数。nCr × r! で求める
- 例：
  - 5個から2個並べる：10×2!＝20通り
確率の定義：
- 全部でn通りあり、どれも同じくらい起こりやすいとき、事象Aが起こる場合がa通りなら、P（A）＝a/n
- 確率はふつう記号Pで表す
確率の基本性質

内容	式
必ず起こる事象Uの確率	P（U）＝1
事象Aの起こる確率	0≦P（A）≦1
事象Aの起こらない確率（余事象）	P（Aᶜ）＝1−P（A）
決して起こらない事象（∅）の確率	P（∅）＝0

空事象：
- 決して起こらない事象。∅で表す
排反：
- 一方が起こったら、もう一方は起こらないこと（同時に起こらない）
独立：
- ある事象の起こり方が、他の事象の起こり方に影響しないこと
確率の加法定理（A又はBの確率）
- AとBが排反のとき：
  - P（A∪B）＝P（A）＋P（B）
- AとBが排反でないとき：
  - P（A∪B）＝P（A）＋P（B）−P（A∩B）
同時確率：
- 事象AとBがともに起こる確率
条件付き確率：
- Aが起こったという条件のもとでBが起こる確率。P_A（B）又はP（B|A）と書く（BがAの従属事象のとき）
確率の乗法定理（AかつBの確率）
- AとBが独立事象のとき：
  - P（A∩B）＝P（A）×P（B）
- BがAの従属事象のとき：
  - P（A∩B）＝P（A）×P_A（B）
例：
- サイコロを2回振って、両方とも6が出る確率：
  - 独立なので 1/6×1/6＝1/36
- サイコロを1回振って、「偶数」又は「3の倍数」が出る確率：
  - 偶数3通り＋3の倍数2通り−両方（6）1通り＝4通り。4/6＝2/3

確率の応用：原因を逆算する、状態の移り変わりを追う

原因の確率：
- 互いに排反な事象E₁、E₂の結果として事象Nが起こったとき、Nの原因がE₁（又はE₂）である確率
ベイズの定理（★）：
- P＝（E₁が起こり、Nが起こる確率）÷（Nが起こる確率）
- ＝ P（E₁）×P_E₁（N） ÷ {P（E₁）×P_E₁（N）＋P（E₂）×P_E₂（N）}
- 一般化：
  - 事象E₁〜Eₙが互いに排反なら、P_N（Eₖ）＝P（Eₖ）×P_Eₖ（N） ÷ Σ{P（Eᵢ）×P_Eᵢ（N）}
例：
- 部品を工場Xから60%、工場Yから40%仕入れている。不良率は工場Xが2%、工場Yが5%。不良品が出たとき、それが工場X製である確率は？
- 工場X製で不良：
  - 0.6×0.02＝0.012
- 工場Y製で不良：
  - 0.4×0.05＝0.020
- 不良品である全確率：
  - 0.012＋0.020＝0.032
- 答え：
  - 0.012÷0.032＝0.375（37.5%）
- コツ：
  - 確率木（枝分かれの図）を描くとわかりやすい
ベイズ統計：
- ベイズの定理を基にした統計理論。古くからあるが、機械学習と相性が良いので再び注目されている
マルコフ過程：
- いくつかの状態があり、ある状態が現れる確率が直前の状態だけで決まる確率過程
推移確率：
- 直前の状態がAのとき、状態Bに移る確率。p_AB と書く
推移行列 P：
- 推移確率を行列にしたもの。i行j列の pᵢⱼ が「SᵢからSⱼへ移る確率」
2段階推移行列 P²：
- P×Pで求める。P²のi行j列は、Sᵢから、どれかの状態を1つ経て、Sⱼへ2段階で移る確率
- 例：
  - P²の1行2列＝p₁₁p₁₂＋p₁₂p₂₂（S₁→S₁→S₂ と S₁→S₂→S₂ の合計）
例（天気がマルコフ過程に従うとする）：

今日＼翌日	晴れ	曇り	雨
晴れ	0.6	0.3	0.1
曇り	0.4	0.4	0.2
雨	0.2	0.5	0.3

晴れの2日後が雨である確率（P²の1行3列）：
- 晴れ→晴れ→雨：0.6×0.1＝0.06
- 晴れ→曇り→雨：0.3×0.2＝0.06
- 晴れ→雨→雨：0.1×0.3＝0.03
- 合計＝0.15

モンテカルロ法

モンテカルロ法：
- 数値モデルとして定義された問題（確率過程を含む）の答えを、乱数を使って推定する手法の総称
- もとは、確率を伴わない問題を確率の問題に置きかえて解くために考えられた。今はAIの強化学習などにも使われる
例：
- 円周率πの近似計算
- 手順：
  - ①0.0〜1.0の乱数を2つ作り、（x，y）に点を打つ。これをN回繰り返す
  - ②半径1の四分円の中（円周上を含む）にある点を数える（p個）
  - ③円の面積 πr²＝π×1.0² ＝ 4×（p/N）から、π ≒ 4p/N

確率分布：データの真ん中とばらつき

代表値：
- データの性質や分布の特徴を数値で表したもの
- 平均値：
  - データの分布のバランスポイント。x̄＝（x₁＋x₂＋…＋xₙ）÷n
- 中央値（メジアン、Me）：
  - データを大きさ順に並べたときの真ん中の値
  - データ数nが奇数：
    - （n＋1）÷2番目
  - データ数nが偶数：
    - n÷2番目と、n÷2＋1番目の平均
- 最頻値（モード値）：
  - 最も多く出てくる値（並の値）
散布度：
- データのばらつきの大きさ
- レンジ：
  - 最大値−最小値（ばらつきの範囲）
- 分散 σ²＝
  - （1/n）×Σ（xᵢ−x̄）²
  - 平均を中心にした広がりの程度。小さいほど平均のまわりに集まり、大きいほど平均から離れたデータが多い
- 偏差：
  - xᵢ−x̄。分散は「偏差の2乗の平均」
- 標準偏差 σ＝
  - √（分散）
例：
- データ 2，4，6，8
- 平均＝20÷4＝5
- 偏差＝−3，−1，1，3。2乗の平均＝（9＋1＋1＋9）÷4＝分散5
- 標準偏差＝√5 ≒ 2.24
- レンジ＝8−2＝6
- 中央値＝（4＋6）÷2＝5（データ数が偶数なので2番目と3番目の平均）
平均値と分散・標準偏差の性質（★aは定数）

操作	平均	分散	標準偏差
全データに a を足す	もとの平均＋a	変わらない	変わらない
全データを a 倍する	もとの平均×a	もとの分散×a²	もとの標準偏差×｜a｜

例（上のデータ 2，4，6，8）：
- ＋10 すると、平均15、分散は5のまま
- ×2 すると、平均10、分散は5×4＝20、標準偏差は2.24×2≒4.47
x̄管理図（品質管理で使う）：
- 管理限界線 UCL、LCL は中心線CLから±3σ。標本数が少ないときは、σの代わりに標本から求めたレンジの平均 R̄ を使い、CL±係数×R̄ とする
標本調査：
- 集団の一部だけを調べて、全体を推測すること
- 母集団：
  - 本来調べたい集団全体
- 標本（サンプル）：
  - 調査のために無作為に抜き出した集団
- 母平均／標本平均：
  - 母集団の平均／標本の平均
確率分布：
- 標本の分布に確率を取り入れたもの。確率変数の種類で2つに分かれる

種類	データ	主な分布
連続型確率分布	身長や体重のように連続的に変わる	正規分布、指数分布、一様分布など
離散型確率分布	1，2，3…のように飛び飛び	二項分布、ポアソン分布など

待ち行列理論では、指数分布とポアソン分布が重要
ポアソン分布：
- 二項分布B（n，p）で、平均npを一定にしたままnを無限大にした分布。とても大きなサンプルで、起こる確率pがとても小さいときの分布
正規分布（ガウス分布）：
- 統計で最も重要な分布。平均を中心に左右対称の釣鐘型
- ドイツの数学者ガウスが、測量の誤差を整理する中で研究した
- 形は平均μと標準偏差σで決まる。**N（μ，σ²）**と書く
- μ±σ のところが変曲点（曲線の曲がり方が変わる点）
- 標準正規分布：
  - 平均0、標準偏差1の正規分布 N（0，1²）
- 確率密度関数：
  - f（x）＝ 1/（√（2π）σ）× e^（−（x−μ）²/（2σ²））（π：円周率3.14159…、e：自然対数の底2.71828…）
正規分布の性質（★必ず覚える）

範囲	入る割合
μ−σ 〜 μ＋σ	約 68.3%
μ−2σ 〜 μ＋2σ	約 95.4%
μ−3σ 〜 μ＋3σ	約 99.7%

例：
- 平均と標準偏差がA（50，20）、B（65，10）、C（70，12）、D（75，6）の4つのテストで、85点以上の人の割合が最も多いのは？
- 85点が平均から標準偏差の何倍離れているか：A＝35÷20＝1.75、B＝20÷10＝2.0、C＝15÷12＝1.25、D＝10÷6≒1.67
- 離れ方がいちばん小さいCが、85点以上の人の割合が最も多い
例：
- 平均60点、標準偏差10点の正規分布なら、70点以上の人は約（100−68.3）÷2 ≒ 16%
標本平均と標本合計の分布
- 母集団が平均μ、分散σ²の正規分布に従うとき、大きさnの標本について
- 標本平均 x̄ の分布：
  - nが大きくなると、平均 μ、分散 σ²/n の正規分布に近づく（たくさん集めて平均するとばらつきが小さくなる）
- 標本合計 Σx の分布：
  - 平均 n×μ、分散 n×σ² の正規分布に近づく
- 母集団が正規分布でなくても、n＝50以上なら x̄ の分布はほぼ正規分布になる
正規分布の加法性（再生性）：
- 独立なXとYが N（μx，σx²）、N（μy，σy²）に従うとき
- 和 X＋Y：
  - N（μx＋μy，σx²＋σy²）
- 差 X−Y：
  - N（μx−μy，σx²＋σy²）
- 注意：
  - 平均は足したり引いたりするが、分散は差のときも足す（ばらつきは打ち消し合わず、増える）

混同しやすいペア

積の法則（ともに起こる。掛ける）／和の法則（どちらか。足す）
組合せ nCr（選ぶだけ）／順列（選んで並べる。nCr×r!）
排反（同時に起こらない。加法定理で関係）／独立（影響しない。乗法定理で関係）
同時確率（AとBがともに）／条件付き確率（Aが起きたうえでB）
ベイズの定理（結果から原因の確率を求める）／マルコフ過程（直前の状態で次が決まる）
平均値（バランス点）／中央値（真ん中の順位）／最頻値（最も多い値）
分散（偏差の2乗の平均）／標準偏差（分散の平方根）
データに足す（分散は変わらない）／データを掛ける（分散はa²倍）
連続型（正規・指数・一様）／離散型（二項・ポアソン）
母集団（本当に調べたい全体）／標本（抜き出した一部）
標本平均の分散 σ²/n（小さくなる）／標本合計の分散 nσ²（大きくなる）

回帰分析

一言で言うと：
- データどうしの関係を y＝f（x）のような式にして、予測したり、どの要因がどのくらい効いているかを調べたりする話。

要因が1つ（単回帰分析）→ 要因が複数（重回帰分析）→ 結果が「する／しない」の2値（ロジスティック回帰分析）

覚え方の軸

説明変数の数と、目的変数の形で3つに分ける：
- 説明変数1つ＝単回帰、複数＝重回帰、目的変数が0か1＝ロジスティック回帰
回帰直線は最小二乗法で引く：
- 点と直線の残差の2乗の合計が最小になるように a、b を決める
相関係数 r は −1〜1：
- 符号は回帰直線の傾きと同じ。｜r｜が1に近いほど強い相関、0なら相関なし
「見かけの相関（擬似相関）」を疑う：
- 他の変数の影響を取り除いた偏相関係数で確かめる

単回帰分析：要因1つで予測する

回帰分析：
- ある変量と、その要因となる変量の関係を統計的に分析し、**y＝f（x）**という数式モデルに当てはめること
- 使いみち：
  - 要因から目的の値を推測・予測する。目的の値に影響する要因を探し、影響の大きさを測る
目的変数（従属変数）：
- 予測したい値 y
説明変数（独立変数）：
- 要因となる値 x
単回帰分析：
- 目的変数に影響する要因（説明変数）が1つの場合の分析
線形回帰：
- xとyの関係が y＝ax＋b のような直線の式で表されるもの
例：
- 店舗ごとの広告費xと売上yを散布図にすると、ほぼ直線上に並ぶ → 線形回帰モデル y＝ax＋b を当てはめる
回帰係数（回帰パラメータ）：
- 係数a、bのこと
最小二乗法（★）：
- 点と直線の残差の2乗和が最小になるように a、b を決める方法
- 残差：
  - 点Pᵢ（xᵢ，yᵢ）と、そのxでの直線上の点Qᵢ（xᵢ，axᵢ＋b）との差。eᵢ＝yᵢ−（axᵢ＋b）
- 求める式：
  - a＝Σ（xᵢ−x̄）（yᵢ−ȳ） ÷ Σ（xᵢ−x̄）²
  - b＝ȳ−a x̄（回帰直線は必ず平均の点（x̄，ȳ）を通る）
- 正規方程式：
  - 残差の2乗和Sを a と b でそれぞれ偏微分して0とおいた式（∂S/∂a＝0、∂S/∂b＝0）。ここから a、b が出る
回帰直線：
- 最小二乗法で求めた y＝ax＋b。「yのxへの回帰直線」という
- 分布の中心的な傾向を示すので、相関が強ければ、xからyの中心的な値を予測できる
- 注意：
  - yのxへの回帰直線で、yからxを予測してはいけない。それには「xのyへの回帰直線」を別に求める
相関係数 r：
- 回帰直線が「中心的な傾向」を示すのに対し、相関係数は「分布の広がり」、つまりxとyの関係の強さを示す
- r＝（xyの共分散）÷（xの標準偏差×yの標準偏差）
- ＝ Σ（xᵢ−x̄）（yᵢ−ȳ） ÷ {√Σ（xᵢ−x̄）² × √Σ（yᵢ−ȳ）²}
- 共分散 Cxy＝
  - （1/n）Σ（xᵢ−x̄）（yᵢ−ȳ）
- 範囲は −1≦r≦1。符号は回帰直線の傾きの符号と同じ

r の値	意味
｜r｜＝1	完全相関（全部の点が回帰直線上。傾きが正なら r＝＋1）
｜r｜が1に近い	強い相関（点が直線の近くに集まる。回帰直線が有効）
｜r｜が0に近い	弱い相関（点が広がっている。回帰直線は有効といえない）
r＝0	相関なし（直線的な傾向がない）

例：
- 3点（1，2）、（2，2）、（3，5）
- 平均：
  - x̄＝2、ȳ＝3
- 偏差：
  - x：−1，0，1、y：−1，−1，2
- Σ（x偏差×y偏差）＝1＋0＋2＝3、Σ（x偏差）²＝2、Σ（y偏差）²＝1＋1＋4＝6
- a＝3÷2＝1.5、b＝3−1.5×2＝0 → 回帰直線 y＝1.5x
- r＝3÷√（2×6）＝3÷√12 ≒ 0.87（正の強い相関）

重回帰分析：要因が複数あるとき

重回帰分析（多元回帰分析）：
- 1つの目的変数を、複数の説明変数で推測・予測する分析
- 例：
  - 売上yを、広告費x₁と店舗面積x₂で予測する：y＝a₀＋a₁x₁＋a₂x₂
- 説明変数がn個なら y＝a₀＋a₁x₁＋a₂x₂＋…＋aₙxₙ
- 係数は最小二乗法で求める
偏相関係数：
- 2つの変数の関係の強さを、他の変数の影響を取り除いて測る尺度
擬似相関：
- 他の変数の影響で生まれた、見かけ上の相関（例：アイスクリームの売上と水の事故の件数に相関があっても、実は両方とも気温の影響かもしれない）
単相関係数 r_yx₁：
- x₂をまったく考えないときの、yとx₁の相関係数
偏相関係数 r_yx₁・x₂：
- x₂の影響を取り除いたうえでの、yとx₁の相関係数（「・x₂」は「x₂の影響を除いた」という意味）
- 式：
  - （r_yx₁ − r_yx₂ × r_x₁x₂）÷ {√（1−r_yx₂²）× √（1−r_x₁x₂²）}
- 注意：
  - 単相関係数と偏相関係数は、一般には等しくならない

ロジスティック回帰分析：「する／しない」を予測する

ロジスティック回帰分析：
- 目的変数が「1か0」の2値のときに使う分析
- ある事象が起こるかどうかを判別するため、説明変数群X（x₁，x₂，…，xₙ）から、その事象が起こる確率を出すモデルを使う
- 出した確率が閾値以上（ふつう0.5以上）なら「1（起こる）」、そうでなければ「0（起こらない）」と判断する
ロジスティック回帰モデル：
- p（X）＝ 1 ÷（1＋e⁻ˣ）、X＝a₀＋a₁x₁＋…＋aₙxₙ
- p（X）は0〜1の間をとるS字の曲線（ロジスティック曲線）になる
- 係数 a₀〜aₙ は最小二乗法などで求める
- e：
  - 自然対数の底。ネピア数ともいう。2.71828…と続く超越数
例：
- 会員がサービスを解約するかどうか。既存会員の情報（利用年数、月の利用回数、年齢）と解約の有無の関係からモデル式を作り、今の会員の情報を入れて判別する
ロジスティック回帰分析は2値分類のための分類モデルでもあるので、機械学習では判別認識の手法として使われる

その他の分析手法

重回帰分析：
- 従属変数を、2つ以上の独立変数の一次結合式で推定する。係数は最小二乗法で求める
因子分析：
- 観測された変数の相関関係から、共通して存在する潜在的な因子を導く手法（目的は「共通因子を見つけること」）
主成分分析：
- 多くの変数を、情報をできるだけ失わないようにまとめて、より少ない変数（主成分）に要約する手法（目的は「情報を縮約して見通しをよくすること」）。因子分析とよく混同される
クラスタ分析（クラスタリング）：
- データを、互いに似たものを集めた集団（クラスタ）に分ける手法
判別分析：
- 分類がわかっている既知のデータをもとに、未知のデータがどの分類に入るかを判別する手法

混同しやすいペア

目的変数（従属変数。予測したいy）／説明変数（独立変数。要因x）
単回帰（説明変数1つ）／重回帰（説明変数が複数）／ロジスティック回帰（目的変数が0か1）
回帰直線（中心的な傾向。予測に使う）／相関係数（広がり。関係の強さ）
yのxへの回帰直線（xからyを予測）／xのyへの回帰直線（yからxを予測）
単相関係数（他の変数を考えない）／偏相関係数（他の変数の影響を除く）
因子分析（共通の因子を見つける）／主成分分析（少ない変数に要約する）
クラスタ分析（似たものをグループ化。正解なし）／判別分析（既知の分類をもとに振り分ける）

数値計算

一言で言うと：
- 式を変形しても答えが出せない問題を、コンピュータの繰り返し計算で「だいたいの答え（近似値）」にする方法と、そのときに出る誤差の話。

方程式の根を求める（二分法・ニュートン法）→ 面積を求める（数値積分・台形公式）→ 誤差（丸め・情報落ち・桁落ち・打切り）→ 連立方程式を解く（逆行列・掃き出し法）

覚え方の軸

根の求め方は「半分に切る」か「接線で近づく」：
- 二分法（確実だが遅い）、ニュートン法（速い）。どちらも差がε未満になったら止める
ニュートン法の式は1本：
- x₁＝x₀−f（x₀）÷f’（x₀）
誤差は「どこで起きるか」で4つ：
- 端数（丸め）、大＋小（情報落ち）、近い数の引き算（桁落ち）、途中でやめる（打切り）
連立方程式は「Aα＝b → α＝A⁻¹b」：
- 掃き出し法は（A｜b）を（E｜c）に変形する。cが答え

数値的解法：近似値を繰り返し計算で求める

二分法：
- f（x）＝0 の近似根を求める方法。f（a）とf（b）の符号が逆なら、aとbの間に根がある。その範囲を半分に切る操作を繰り返して、範囲を狭めていく
- 前提：
  - f（x）が区間［a，b］で単調に増加する連続関数で、f（a）＜0 かつ f（b）＞0
- 手順：
  - ①c←（a＋b）÷2
  - ②｜a−b｜＜ε なら、cを近似根として終わる
  - ③f（c）＜0 なら a←c、そうでなければ b←c
  - ④①に戻る
- 閉区間［a，b］：
  - aとbの両端を含む区間
- ε（イプシロン）：
  - 収束判定に使う、十分に小さい正の値
例（f（x）＝x²−2、根は√2≒1.414）：
- ［1，2］：c＝1.5、f（1.5）＝0.25＞0 → b＝1.5
- ［1，1.5］：c＝1.25、f（1.25）＝−0.4375＜0 → a＝1.25
- ［1.25，1.5］：c＝1.375、f＜0 → a＝1.375
- ［1.375，1.5］：c＝1.4375 …と、1.414に近づいていく
ニュートン法（★）：
- y＝f（x）の接線を使って近似根を求める方法。「x₀での接線とx軸の交点x₁は、x₀より真の根に近い」という考えで繰り返す。二分法より速く収束する
- 手順：
  - 予想できる近似値を初期値x₀にする → 点（x₀，f（x₀））の接線とx軸の交点x₁を求める → x₁を新しいx₀にして繰り返す → ｜x₁−x₀｜＜ε になったら止め、x₁を近似根にする
- 接線の式：
  - y−f（x₀）＝f’（x₀）（x−x₀）
- y＝0、x＝x₁ を入れて変形すると（★試験で問われる）：
  - x₁＝x₀−f（x₀）÷f’（x₀）
- f’（x）：
  - f（x）を微分した導関数（接線の傾き）
例（f（x）＝x²−2、f’（x）＝2x、x₀＝2）：
- x₁＝2−（4−2）÷4＝1.5
- x₂＝1.5−（2.25−2）÷3＝1.5−0.0833…＝1.4167
- x₃ ≒ 1.4142（3回でほぼ√2。二分法よりずっと速い）
はさみうち法（線形逆補間法）：
- 根を含む区間［a，b］で、点（a，f（a））と点（b，f（b））を結ぶ直線とx軸の交点を求め、それを新しい区間の端にして繰り返す
数値積分：
- 積分公式を使わずに、曲線で囲まれた面積の近似値を求める方法
台形公式（台形則）：
- 区間［a，b］でf（x）を一次関数（直線）で近似し、できた台形の面積で定積分を近似する
- 1つの台形：
  - ∫f（x）dx ≒（b−a）÷2 ×（f（a）＋f（b））
- 台形の面積：
  - （上底＋下底）×高さ÷2
- 区間をn等分（幅 h＝（b−a）/n、端点 x₀，x₁，…，xₙ）すると、よりよい近似になる：
  - ∫f（x）dx ≒ h/2 ×（f（x₀）＋2f（x₁）＋2f（x₂）＋…＋2f（xₙ₋₁）＋f（xₙ））
  - 両端は1回、間の点は2回（隣どうしの台形で共有するため）
- 区間を n＝2ᵏ（k＝1，2，…）等分していき、｜Sₖ−Sₖ₋₁｜＜ε になったら止めて、Sₖ を積分値とする
シンプソン法：
- 誤差をさらに小さくするため、微小区間を一次関数ではなく二次関数で近似する方法
例（∫₀² x² dx、真の値は8/3≒2.667）：
- 2等分（h＝1、x＝0，1，2、f＝0，1，4）：
  - 1/2 ×（0＋2×1＋4）＝3
誤差の種類（★）

誤差	どこで起きるか
丸め誤差	数値を有限のビット数で表すため、最下位桁より小さい部分を四捨五入・切上げ・切捨てしたときに出る
情報落ち	絶対値がとても大きな数ととても小さな数を足し引きしたとき、小さいほうの数の仮数部の下位が結果に反映されない
桁落ち	絶対値がほぼ等しい2つの数の差を求めたとき、有効桁数が大きく減る
打切り誤差	計算を途中で打ち切ったために出る（εが大きいと真の値に近づく前に止まる）

情報落ちの仕組み：
- 指数部が違う2つの数を足し引きするときは、指数部を大きいほうにそろえる。そのため小さいほうの仮数部が右にずれて、下位の桁がはみ出す
絶対誤差＝
- ｜近似値−真値｜
相対誤差＝
- ｜絶対誤差÷真値｜＝｜（近似値−真値）÷真値｜
誤差限界：
- 誤差がこれを超えない、という範囲（｜近似値−真値｜≦ε なら、εが誤差限界）
相対誤差の限界＝
- 誤差限界÷真値
積の相対誤差の限界：
- A、Bの近似値をa、b、それぞれの絶対誤差（誤差限界）をda、dbとすると、積の相対誤差の限界は｜da/A｜＋｜db/B｜（掛け算では相対誤差が足し算になる）
例（上の台形公式の例）：
- 絶対誤差＝｜3−2.667｜≒0.333、相対誤差＝0.333÷2.667≒0.125（12.5%）

連立一次方程式の解法：行列で解く

多元連立一次方程式：
- 未知数がいくつもある連立一次方程式。最小二乗法などで、データから情報を得るときに解く必要がある
行列による表現：
- x＋2y＝5、3x＋4y＝11 は、係数の行列 A＝（1 2 / 3 4）、解の列ベクトル α＝（x / y）、定数項の列ベクトル b＝（5 / 11）を使って Aα＝b と書ける
単位行列 E：
- 対角要素が1で、他がすべて0の行列。2×2なら（1 0 / 0 1）。E 又は I と書く
逆行列 A⁻¹：
- AB＝BA＝E を満たす行列B
正則行列：
- 逆行列をもつ行列
Aα＝b の解き方：
- 両辺に A⁻¹ を掛けると、A⁻¹Aα＝A⁻¹b → Eα＝A⁻¹b → α＝A⁻¹b（Eα＝α）
- Aに逆行列があれば、解は一意に決まる
2×2の逆行列の求め方：
- A＝（a b / c d）なら、A⁻¹＝1/（ad−bc）×（d −b / −c a）
- 行列式：
  - ad−bc のこと。｜A｜又は detA と書く
例：
- A＝（1 2 / 3 4）の行列式＝1×4−2×3＝−2
- A⁻¹＝−1/2 ×（4 −2 / −3 1）
- α＝A⁻¹b＝−1/2 ×（4×5−2×11 / −3×5＋1×11）＝−1/2 ×（−2 / −4）＝（1 / 2）→ x＝1、y＝2
- 検算：
  - 1＋2×2＝5、3×1＋4×2＝11 で合う
行列式を使う解き方（クラメルの公式）：
- ax＋by＝p、cx＋dy＝q で D＝ad−bc≠0 なら
- x＝（pd−bq）÷D、y＝（aq−pc）÷D
- 例：
  - x＝（5×4−2×11）÷（−2）＝1、y＝（1×11−5×3）÷（−2）＝2
掃き出し法（★）：
- Aα＝b の左辺の A を単位行列に変える、という考え方の解き方
- 手順：
  - ①係数の行列Aと定数項のベクトルbをまとめて、（A｜b）という行列を作る
  - ②基本変形をくり返して、（E｜c）の形にする。このとき c が解
- 拡大係数行列（拡大行列）：
  - 行列と列ベクトルを「｜」で区切ってまとめた行列
- 基本変形（この3つだけ使ってよい）：
  - （1）ある行を k倍する（k≠0）
  - （2）ある行の k倍を、他の行に足す
  - （3）ある行と他の行を入れかえる
例（（1 2 ｜ 5 / 3 4 ｜ 11）から始める）：
- ①1行目を−3倍して2行目に足す → 2行目が（0 −2 ｜ −4）
- ②2行目を−1/2倍する → 2行目が（0 1 ｜ 2）
- ③2行目を−2倍して1行目に足す → 1行目が（1 0 ｜ 1）
- 結果は（1 0 ｜ 1 / 0 1 ｜ 2）。答えは x＝1、y＝2
変形しても（E｜c）の形にならないときは、解がない（不能）か、解が無数にある（不定）
ガウス・ジョルダン法：
- 上の掃き出し法の別名
ガウスの消去法：
- 拡大係数行列のAの部分を、対角より左下が全部0の三角行列にしてから（前進消去）、下から順に代入して（後退代入）解を求める方法

AIとGPU

GPU（Graphics Processing Unit）：
- 3Dグラフィックスなどの画像描画計算を高速に行うプロセッサ。「単純な演算を、多数のデータに、並列に、繰り返し」行うのが得意
GPGPU（General-Purpose computing on Graphics Processing Units）：
- GPUの高い演算性能を、画像処理以外の用途に使うこと。「GPUコンピューティング」「GPUによる汎用計算」ともいう
- 代表例がディープラーニング。大量のデータで膨大な計算をし、その大部分が行列計算なので、CPUの代わりにGPUを積んだGPUサーバが使われる

混同しやすいペア

二分法（区間を半分に。確実だが遅い）／ニュートン法（接線を使う。速い）／はさみうち法（2点を結ぶ直線を使う）
台形公式（一次関数で近似）／シンプソン法（二次関数で近似。より正確）
情報落ち（大きい数＋小さい数）／桁落ち（ほぼ同じ数どうしの引き算）
丸め誤差（端数処理）／打切り誤差（計算を途中で止める）
絶対誤差（差そのもの）／相対誤差（差÷真値）
単位行列（対角が1）／逆行列（掛けると単位行列になる）
ガウス・ジョルダン法（掃き出し法。Aを単位行列にする）／ガウスの消去法（三角行列にして後退代入）
前進消去（左下を0にする）／後退代入（下から代入する）

AI（人工知能）

一言で言うと：
- コンピュータにデータから学ばせる方法（機械学習）と、それを深くしたディープラーニングの話。

3つの学び方（教師あり・教師なし・強化学習）→ 脳をまねた仕組み（ニューラルネットワーク）→ 層を深くする（ディープラーニング）

覚え方の軸

学び方は「正解をどう与えるか」で3つ：
- 正解つき（教師あり：回帰・分類）、正解なし（教師なし：クラスタリング・次元削減）、報酬（強化学習：試行錯誤）
ニューロンは「入力×重みの合計が閾値を超えたら1」
重みの調整は誤差逆伝播法：
- 出力と正解の誤差が小さくなるよう、出力層 → 入力層の向きに調整する
ニューラルネットワークを多層にしたのが DNN＝ディープラーニング：
- 計算の大部分は行列計算なので GPU を使う

機械学習とディープラーニング

AI（Artificial Intelligence：人工知能）：
- 人間の「知能」を実現するための技術
機械学習：
- AIを実現するアプローチの1つ。コンピュータを教育する方法の総称
- 特定のタスク（判別、分類、予測など）のために、「大量のデータ」と「データを解析して、タスクの実行方法を学習できるアルゴリズム」でコンピュータをトレーニングする
機械学習の学び方

学び方	やり方	用途
教師あり学習	入力と正解がセットになったトレーニングデータを与え、未知のデータでも正解を出せるようにする	回帰（過去の実績から未来を予測）、分類・判別
教師なし学習	大量の入力データだけを与え、コンピュータ自身にデータの特徴や規則を見つけさせる	クラスタリング（似たものでグループ化）、次元削減（意味をなるべく残して、少ない次元の情報にする。データの圧縮や可視化）
強化学習	試行錯誤を通じて、「価値（報酬）を最大にする行動」を学ぶ	将棋や碁のソフト、株の売買など

代表的なアルゴリズム
- 回帰：
  - 線形回帰、ベイズ線形回帰
- 分類・判別：
  - ロジスティック回帰、決定木
- 次元削減：
  - 主成分分析
強化学習の3つの構成要素：
- 環境、エージェント（学習者）、行動。ある環境の中のエージェントに、どの行動をとれば価値が最大になるかを学ばせる
マルコフ決定過程：
- マルコフ過程をもとに、各状態で報酬が与えられるようにした確率モデル。強化学習の「環境」の最も基本的なモデル。最終的に最も高い報酬が得られる状態遷移の並び（シーケンス）を見つける
過学習（過適合）：
- 学習データにだけ最適化されてしまい、未知のデータに対する精度が下がる現象
ニューラルネットワーク：
- 脳の神経回路網をまねた数理モデル。入力層と出力層の間に、中間層（隠れ層）をもつ
- ニューロン（脳の神経細胞）を数理モデルにした形式ニューロンを並べて組み合わせる
- 大量の学習用データを与え、出力と正解（目標値）の誤差が最小になるように信号線の重みを自動で調整する
形式ニューロン：
- 入力x₁〜xₙにそれぞれ重みw₁〜wₙを掛けて合計し、閾値θを超えたら1、超えなければ0を出力する
- 式：
  - Σxᵢwᵢ＞θ なら y＝1、Σxᵢwᵢ≦θ なら y＝0
例：
- 入力（1，0，1）、重み（0.5，0.3，0.4）、閾値0.8
- 合計＝1×0.5＋0×0.3＋1×0.4＝0.9 → 0.8を超えるので出力 1
誤差逆伝播法（バックプロパゲーション）：
- 最適な重みに調整するためのアルゴリズム。出力層から入力層に向かって順に、各重みの誤差が小さくなるよう調整していく
学習を重ねて重みが最適化されると、ニューラルネットワークは正解にたどり着くためのルール（例：犬と猫を区別する目の付けどころ）を自分で学べるようになる。学習用データが多いほど精度が高くなる
パーセプトロン：
- 入力層と出力層の2層だけのもの。単純パーセプトロンともいう
- 一般に「ニューラルネットワーク」というと、3層の多層パーセプトロンを指す
出力層のニューロンの数：
- 解く問題に合わせて決める。クラス分類なら、分けたいクラスの数にするのが一般的
ディープラーニング（深層学習）：
- 機械学習をさらに発展させたもの。ニューラルネットワークを多層化し、中間層とニューロンを増やした DNN（Deep Neural Network：ディープニューラルネットワーク）で、膨大なデータを処理して、より複雑な判断ができるようにする
基盤モデル：
- 学習済みのモデル
ファインチューニング：
- 基盤モデルに独自のデータを追加で学習させ、重みを微調整して、新しい目的に特化したモデルにすること。自社業務向けのモデルを、ゼロから作るより簡単・安く作れる

その他のAI関連の用語

エキスパートシステム：
- 特定分野の専門知識をもとにルールベースの推論を行い、専門家と同じレベルの問題解決をする
バックトラック法（後戻り法）：
- 場合分けをして深さ優先で探索し、解が見つからなければ1つ前の場合分けに後戻りする。しらみつぶしの探索を、組織的に効率よく行う技法
遺伝的アルゴリズム（GA：Genetic Algorithm）：
- 生物の進化をまねた方法。解の候補を遺伝子に見立て、突然変異・交配・とう汰を繰り返して、より良い解に近づける

混同しやすいペア

教師あり学習（正解つき。回帰・分類）／教師なし学習（正解なし。クラスタリング・次元削減）／強化学習（報酬で試行錯誤）
分類（教師あり。決まった正解のグループに振り分ける）／クラスタリング（教師なし。似たものどうしでグループを作る）
マルコフ過程（直前の状態で次が決まる）／マルコフ決定過程（それに報酬を加えたもの。強化学習の環境）
入力層／中間層（隠れ層）／出力層
単純パーセプトロン（2層）／多層パーセプトロン（3層。一般的なニューラルネットワーク）／DNN（さらに多層。ディープラーニング）
誤差逆伝播法（出力層 → 入力層の向きに重みを調整）
過学習（学習データにだけ合いすぎる）
基盤モデル（学習済みのモデル）／ファインチューニング（追加学習で特化させる）
エキスパートシステム（ルールで推論）／ディープラーニング（データから学ぶ）／遺伝的アルゴリズム（進化をまねる）

ひとことでまとめると

テーマ	何の話か
集合と論理	集合と命題を記号で扱う。ド・モルガン、対偶、カルノー図
情報理論と符号化	情報量をビットで測り、ハフマン・ランレングスで圧縮し、PCMでデジタル化する（計算あり）
オートマトン	入力と状態で次の状態が決まる機械。最後に受理状態にいれば受理
形式言語	文法（BNF）と正規表現で字句解析・構文解析し、逆ポーランドなどの中間語にする
グラフ理論	頂点と辺のつながり。オイラー／ハミルトン、隣接行列、ダイクストラ法
確率と統計	組合せ、ベイズ、マルコフ、平均・分散、正規分布（計算あり）
回帰分析	最小二乗法で回帰直線を引き、相関係数で関係の強さを見る
数値計算	二分法・ニュートン法・台形公式で近似値を出し、誤差を知り、連立方程式を行列で解く（計算あり）
AI（人工知能）	教師あり・教師なし・強化学習と、ニューラルネットワーク、ディープラーニング

基礎理論 ざっくりまとめ（応用情報技術者試験）

集合と論理

覚え方の軸

集合論理：ものの集まりを記号で扱う

命題と論理：正しいか正しくないかを記号で扱う

論理演算：計算のルール

論理式の簡略化：同じ意味のまま式を短くする

混同しやすいペア

情報理論と符号化

覚え方の軸

情報量：情報の大きさをビットで測る

情報源符号化：データを短くする

デジタル符号化：アナログをデジタルに変える

混同しやすいペア

オートマトン

覚え方の軸

有限オートマトン：状態を移りながら文字列を読む機械

有限オートマトンと正規表現

その他のオートマトン

混同しやすいペア

形式言語

覚え方の軸

形式文法と言語処理：文法を記号で決める

構文規則の記述：BNFと構文図

構文解析の技法：構文木と中間語

正規表現：字句のパターンを決める

混同しやすいペア

グラフ理論

覚え方の軸

有向グラフ・無向グラフ：線に向きがあるか

サイクリックグラフ：ぐるっと戻れるか

小道（trail）と経路（path）

グラフの種類

グラフの表現：コンピュータでどう持つか

重みつきグラフ：最短経路を探す

混同しやすいペア

確率と統計

覚え方の軸

確率：数え方と基本ルール

確率の応用：原因を逆算する、状態の移り変わりを追う

モンテカルロ法

確率分布：データの真ん中とばらつき

混同しやすいペア

回帰分析

覚え方の軸

単回帰分析：要因1つで予測する

重回帰分析：要因が複数あるとき

ロジスティック回帰分析：「する／しない」を予測する

その他の分析手法

混同しやすいペア

数値計算

覚え方の軸

数値的解法：近似値を繰り返し計算で求める

連立一次方程式の解法：行列で解く

AIとGPU

混同しやすいペア

AI（人工知能）

覚え方の軸

機械学習とディープラーニング

その他のAI関連の用語

混同しやすいペア

ひとことでまとめると

コメント

基礎理論ざっくりまとめ（応用情報技術者試験）