応用情報の勉強で得た知識のメモ。
間違った認識、補足説明などあればコメントで教えてください。
- 情報量
確率Pで起きる事象の情報量Iは底が2の対数を用いて以下の式であらわされる
I = -logP
単位はビット。その事象が起こることを説明するのに何ビット必要か的な考え方。
1/全事象 の情報量は全事象を表現するのに必要なビット数に等しい。
例)8面のサイコロの出目を表すためには -log1/8 = 3 ビット必要
各事象の情報量の総和Hのこと。
H = Σ(P×I)
期待値の式っぽい。平均情報量ともいう。小さいほど事象のあいまいさが小さい。
最大平均情報量はすべての事象の発生確率が同じとき。
- ハフマン符号化
出現率が高いものは短いビット列、低いものは長いビット列であらわすことで圧縮する。
- ランレングス符号化
同じ文字の繰り返しを連続回数とその文字を用いて書くことで圧縮。
例)AAAABCC -> 3A0B1C (数字は繰り返し回数ー1になる)
- 有向グラフに関する語句
頂点に入ってくる辺の数:入次数
頂点から出ていく辺の数:出次数
次数:上記二つの和
自己ループ:端点が同じ辺(スタートとゴールが一緒)
多重辺:スタート地点が同じかつ行き先が同じ辺たち
最短経路問題の解法の一つ。多重辺が生まれたときはコスト最小の辺のみ残しながら一個ずつノードを消していって最終的にスタートとゴールのみにする。
いくつかの状態があるとき、ある状態が現れる確率が直前の状態に依存する(推移確率)。
例)明日晴れる確率は今日の天気によって変わる。
- 正規分布の重要な性質
P(μ-σ≦X≦μ+σ)≒ 0.683
P(μ-2σ≦X≦μ+2σ)≒ 0.954
P(μ-3σ≦X≦μ+3σ)≒ 0.997
母集団N(μ, σ^2)のとき標本平均はN(μ, σ^2/n)、標本合計はN(n*μ, n*σ^2)に近づく。
- ロジスティック回帰分析
yが0か1かであらわせるときに使う。
- 誤差
絶対誤差=|真値ー近似値|
相対誤差=|絶対誤差÷真値|=|1ー近似値/真値|
使っている参考書