情報系の基礎用語のまとめ

いろいろ学んできて出てくる単語の区別をつけられるようにまとめていこうと思います．
初学でまとめたものもあるので間違っているところがあれば教えていただけると幸いです．（追記します）

平均情報量と平均符号長

まず情報量の定義として，以下のように定義する．
$I_i = I(a_i) = -\log_2 p_i $
次に，エントロピーの定義をするが，これは情報源全体が持つ量として平均情報量＝エントロピーとして考えると以下のようになる．
$H(S) = \Sigma_{i=1}^M p_i I_i= \Sigma_{i=1}^n p_i \log_2 p_i$
これが平均情報量あるいはシャノン情報量，情報論のエントロピーである．単位はbitである．
エントロピーの計算のために情報量の定義を使って計算することに注意する必要がある．pについては確率を表していることに注意する．
次に，平均符号長は同様に確率を$p_i$で定義することにした時，各情報源記号$a_i$に対してそれらに割り当てられた符号語の長さを$l_i$と定義した時，平均符号長は$L_n = \Sigma_{i=0}^n a_i l_i$となる．
それらの関係性として,情報源符号化定理は以下のようになる．n次拡大した平均符号長を$L_n$としたとき，
$H(S) \leq L_n /n \leq H(S) + 1/n$
をみたす瞬時復号可能な符号が必ず存在することが言える．
https://www.mnc.toho-u.ac.jp/v-lab/yobology/entropy/entropy.htm

共通鍵暗号と公開鍵暗号

データの送信のおいては，データを暗号化して送信することが一般的であるが，これにはデータの送信者がデータの暗号化をして，受信側でデータを復号できる必要がある．この暗号化の方式が共通鍵暗号と公開鍵暗号となる．
共通鍵暗号ではデータのやり取りにおいて共通鍵というものをユーザー間で共有しておく必要があり，送信者が共通鍵でデータを暗号化してそれを受信者が同じ共通鍵を利用して復号を行う．この方式では共通鍵の交換において安全な受け渡しをできる必要があり，またユーザー間ごとに共通鍵を生成する必要があり，処理が早いという特徴がある．
公開鍵暗号では暗号化するために使用するのが公開鍵と呼ばれるもので，復号化に使われるものは秘密鍵と呼ばれるものである．公開鍵では公開鍵は一般に公開して使用してもらうものであり，公開鍵をもっているだけでは復号を行うことはできないのでユーザー別の暗号化のための鍵を作成する必要がないので公開鍵の受け渡しが容易となり，また，公開鍵方式では共通鍵とくらべて処理が遅いといった特徴がある．
これらから考えると，データの送受信においては前者を使うべきであるが，データの安全性においては後者を使うべきであるので，SSL通信では共通鍵暗号で通信をして，共通鍵暗号の受け渡しにおいては公開鍵暗号を使用するという方式が取られるようになっている．
https://cspssl.jp/guide/key.php

幅優先探索と深さ優先探索

両者は目的の木やグラフを探索するためのアルゴリズムである．
深さ優先探索では目的のノードが見つかるか，子がないノードに行き着くまで探索していき，そのあとは最も近くの探索ができていないノードまで戻って，探索していない分岐に対してさらに同様の深さ優先の探索を行なって目的対象の探索を行う，ということを繰り返して探索するアルゴリズムである．これの管理にはLIFOのスタックを使って探索を行う．
幅優先探索では始点となるノードから分岐している全てのノードを探索し，さらにそこから隣接するノードに対して探索を繰り返す，ということをすることによって目的対象を探索するアルゴリズムである．これの管理にはFIFOのキューを使って探索を行う事になる．
前者を使うべきケースは，全通りを列挙して結果をまとめる必要がある場合や，文字列などを探索するときに辞書順最小であることが求められているケースである．
後者を使うべきケースは，視点から最も近いものを求めたいものであったり，探索範囲自体は広いが深くないノードに求めたい解があることがわかっているケース，深さ優先探索をしたときにスタックが大量に使用されてしまうケースである．
http://enreco.hatenablog.com/entry/2016/09/15/090000
https://mathtrain.jp/dfsbfs

オブジェクト指向言語における継承とオーバーライド

オブジェクト指向言語において，既存のクラスを元にしてクラスを作成することを継承という．元にしたクラスをスーパークラスという．この継承において，既存の元にしたクラスの変数，コンストラクタ，メソッドなどのメンバをそのまま使うこともできる．
さらに，その継承したクラスにおいて，元になったクラス側と同じ名前のメンバも宣言することができて，このとき既存クラス側のメンバを上書きしていることになり，これをオーバーライドという．（オーバーライドされたメンバはスーパークラスで宣言されたものとしてアクセスできなくなる隠蔽が生じる．）
この意味で継承したクラスの中でスーパークラスのオーバーライドが行われているという包括関係にある言える．
http://www.artista.co.jp/article/13478440.html

フォワードキネマティクスとインバースキネマティクス

両者はボーンが設定されているオブジェクトのアニメーションをしようとしたときのそのボーンの動かし方の手法である．
フォワードキネマィテクスではそれらのボーンの親子関係に注意して，ボーンの接続関係を表す関節の角度を何らかの方法で調節することによってアニメーションを行う方法であって，階層が深い子のボーンを目的の位置に持ってこようとしたときの調整方法が難しいという欠点がある．
それに対して，インバースキネマティクスでは階層が深い子のボーンを目的の位置に持ってきたときに，逆運動学によってそのボーンの親子関係から関節の曲がる角度を計算させて制御してあげることで，設定されるべきボーンの接続関係の角度の調節を人為的に調節する必要がなくなってフォワードキネマィテクスのときの面倒がなくなるとともに，ボーンが設定されたキャラクターの関節が動物として自然な角度で設定させることができるという利点がある．
目的の位置に持ってこようとするボーンの階層が浅ければフォワードキネマィテクスを用い，深ければインバースキネマティクスを使ってアニメーションを行うという使い分けをすると良いと考えることもできる．
http://my-job-is-cg-designer.com/category67/entry400.html

大域照明とフォトンマップ法

大域照明はレンダリングにおける対象領域の光の輝度の計算における手法のことである．
大域照明によるレンダリングでは，注目している物体に対して，視点に向かって対象の物体から反射した光が対象の輝度を決定していると考えたときに，直接照明という，光源が直接対象物にむかった光線のみを物体からの反射光とするものだけでなく，間接照明という，周辺の物体の反射による光が対象物に向かった光線も物体からの反射光として考慮することによって，よりリアルなレンダリングを行う手法となる．
ここで，大域照明の種類として，フォトンマッピングというものがある．光源からの光を物理的なフォトンとは異なるがフォトンと呼ばれる光の粒子として大量に飛ばされているものとして考え，このフォトンは拡散反射面に衝突したときはその領域の光の情報として保持し，そのほかに一定の透過率がある領域に衝突したときは一定数のフォトンをその領域に保持してそれ以外をさらにそのまま透過させ，鏡面反射がある場合は反射させるなどの挙動をするようにしたのち，視点からレイを飛ばして衝突した領域に対して，その領域がどれほどの光の情報としてのフォトンを保持しているかをみることによって光の輝度を計算することができる．

仮想現実感と拡張現実感

人間が知覚している情報に対するコンピュータの情報の作用のさせ方が両者は異なっている．
仮想現実は現実の世界かのように，人間にコンピュータが見せる世界を知覚させる方法をとる．仮想現実感を実現する方法としては，HMDによってCGを人間が視覚で認識するような３次元空間の視覚情報のようにみせることだけでなく，聴覚，触覚，嗅覚などの観点からも実際の現実世界であるかのように錯覚させる技術的な方法によって仮想現実感を実現する．
それに対し，拡張現実感は現実世界の情報はそのまま人間に知覚させた上で，それに対してコンピュータによる情報を付加することによって生じる感覚である．拡張現実では現実の物体に，新たに情報が付加されることになるために，知覚できる情報を現実のそれまでのものよりも増すことができる，という点が特徴的である．

オブジェクト指向プログラミングにおけるインスタンスとメソッド

オブジェクト指向において，クラスはオブジェクトに対する設計図となるものである．そのクラスはデータ部分（メンバ変数）と手続き部分（メソッド）を構成することができるということを前提とする．
インスタンスとは，あるクラスを設計図として，別のクラスあるいはそのクラス自身で使用される実際のオブジェクトのことである．これによってそのインスタンスにおけるクラスのなかに定義されているメンバ変数またはメソッドを自分で定義する必要なしに使用することができる．
メソッドはクラスの手続き部分として一連の処理を定義することができる．プログラムのなかで繰り返し現れる処理や，特定の処理を実現するために実行する一連の処理をメソッドとしてまとめておくことができ，これによって重複する一連の処理を別のクラスの中で記述する必要がなくなる．他のクラスで使用したいメソッドが記述されたクラスのインスタンスを作成して，そのインスタンスからメソッドを実行することによって，別のクラスでは同じ処理を記述する必要がなくなる．メソッドはそれを使用する際の自身のインスタンス内部へのアクセスがあることで，実質そのメソッドを使用している際には外部にはそのメソッドを使用する上で必要になる情報以外のメンバやメソッドが秘匿されるというカプセル化が生じる．
（この意味で，あるクラスでは特定のクラスのインスタンスをそのクラスのメンバ変数にすることもできることに注意する必要がある．注意というほどでもないが．）

３次元モデルの凸包とバウンディングスフィア

両者は3次元モデルの衝突判定をするときの手法である．
バウンディングスフィアでは，ある複雑な形状をした3次元モデルがあったとき，それを内包するバウンディングスフィアと呼ばれる球を用意する．ほかの物体に対してもそのバウンディングスフィアによって内包している状況を考えたとき，これらの3次元モデル同士が衝突したかどうかをそれらの球の中心同士の距離がそれらの球の半径の和よりも小さくなったときに衝突した，として判定してあげることによって衝突判定を行う方法を取ることができる．
また凸包では，凸包と呼ばれる任意の多面体で対象の複雑な形状の3次元モデルたちをそれぞれ被覆してあげて，２つの3次元モデルの衝突判定を考えるためにその多面体の3軸それぞれへの射影によってできる線分において3軸すべてで重複している領域があれば，それら２つの多面体は衝突していると判定することで衝突判定を考えることができる．

強化学習と教師あり学習

機械学習における訓練データがあるのが教師あり学習（，あるいは教師なし学習）であり，訓練データ自体はないのが強化学習である．
（教師なし学習ではその訓練データ自体のデータ構造を学習させるものである．）
教師あり学習では，入力に対する出力の関係を学習させるものであり，これのために用いる訓練データは入力として使用するデータと，それに対する正解としての出力として使用するデータを用意してあげて，これを学習させるものである．（理想的にはこのような入力と出力の関係が正確であるデータを使うべきであるが，データの欠損値であったり，入力に対する出力のデータが正解とは言えないものであったりすることもあるので注意する必要がある．）
それに対し強化学習は，報酬を最大化するような行動をできるように学習させるものである．エージェントと呼ばれる仮想的な存在を，特定の報酬を最大化させたい状態に存在できるように問題設定を行い，そこにおけるエージェントの行動の結果によってどれだけ報酬を得られるのか，といったことを設定し，エージェントに学習を繰り返させることで機械学習を行わせる方法である．（アルゴリズムとしてはQ学習，Sarsa,モンテカルロ法などがある．）
http://blog.brainpad.co.jp/entry/2017/02/24/121500

RGB表色系とCMY表色系

両者は色の表現においてどのようなものをパラメータとして表現するかという違いがある．
RGBではRed,Green，Blueによって全ての色を表現する．RGBにおいてはこれらの3つのパラメータが混色した場合は白色になる．このRGB標識系によって，赤，緑，青を表現することができる部品をモニターに配置することによって液晶モニターはすべての色を表現することができるようになっている．加法混色と呼ばれる色の変化をするために，2色を混合した際には鮮やかな色の表現をすることができる．
CMY表色系はCyan,Magenta,Yellowの3つのパラメータによって色を表現するという方法を取っている．この3つのパラメータが混色した場合は黒色になる．この表色系では，インクプリンタにおける色の表現に使うことができる．減法混色の色の変化をするために，2色を混ぜ合わせた場合には暗くなってしまうのが特徴的である．
変換方法としては

\begin{pmatrix}
a \\ b \\ c
\end{pmatrix}
+
\begin{pmatrix}
c \\ m\\ y
\end{pmatrix}
= 
\begin{pmatrix} 1 \\ 1 \\ 1 \end{pmatrix}

という関係性がある．

桁落ちと情報落ち

両者ともにコンピュータで計算したときに有効桁数が限られているときに生じる問題である．
情報落ちとは，絶対値が大きく異なる数の加減を行うことによって絶対値が小さい方の情報が無視されてしまうことである．
桁落ちとは，両者の数が近い数を減算したときに有効数字が小さくなってしまうことである．

連長符号化とハフマン符号化

両者ともにデータ圧縮の方法である．
https://michisugara.jp/archives/2013/huffman.html

キューとスタック

両者はデータの保存の取り出し方の方法であり，データを一列に並べるという点では同じである．
キューではデータを追加するときはデータ列の末尾に入れることになり，データを取り出すときはデータ列の先頭から取り出されることになるデータの扱い方である．この考え方を最初にデータ列に入ったものから出ていくということでFirst In First Outと呼ぶ．
それに対してスタックではデータを追加するときは列の先頭に追加され，データを取り出すときはデータ列の先頭から取り出されることになるデータの取り扱い方である．この考え方を最後にデータ列に入ったものから出ていくということでLast In First Outと呼ぶ．

ハッシュ関数と電子署名

データの送受信における暗号化を考えるときに両者ともに必要となる．
ハッシュ関数とは，入力した値に対してハッシュ値と呼ばれる全く異なる値が出力される関数であり，同じ入力であれば同じハッシュ値になる，という特徴がある．このハッシュ関数ではハッシュ値から入力された値の特定が非常に困難であるという不可逆性があることによって暗号化が可能になっている．また，どんな入力値に対しても出力される長さは固定されているという特徴がある．
電子署名では，データの送信者と受信者において，まずは送信者は公開鍵と秘密鍵を用意しておいて，公開鍵を受信者側は用意しておく．ここで秘密鍵は送信者固有のものとなっていることに注意する．まず送信者は送信するデータそのものを特定のハッシュ関数によってハッシュ値を算出する．次にこのハッシュ値を秘密鍵によって暗号化して，データとこの暗号化されたハッシュ値を送信する．受信者はこのデータを同じハッシュ関数にかけてハッシュ値を算出して，かつ，暗号化されたハッシュ値を公開鍵で復号化してハッシュ値を算出して，両者が一致しているかを確認し，両者が一致していれば送信者のデータであることが確認できる．この送信者によって秘密鍵でハッシュ値を暗号化したものを電子署名という．

確率変数の結合分布と周辺分布

両者ともに多変数の確率分布の表現に使われる用語である．
多変数の確率変数があったとき，多変数のペアに対してのそれぞれの確率分布を表したものが結合分布である．
それに対して，周辺分布では多変数のうちの特定の確率変数を，例えばYを消去する場合は$\Sigma_{y=0}^n P_{X,Y}(x,y)$（あるいは連続な確率分布であれば積分）によって消去して，得たい確率変数に関する分布の情報だけを取り出したときの確率分布を周辺分布と呼ぶ．
https://mathwords.net/doujibunpu

エイリアシングと量子化誤差

両者ともにディジタル信号処理を行ったときに生じる問題点である．
エイリアシングは，信号をディジタル化する際の標本化処理の時に生じる．標本化定理よりアナログ信号の周期の1/2よりも小さな間隔でサンプリング間隔を取れば，元の画像を再現することができるが，それよりも間隔を大きくしていった場合に，もとの入力の信号では高周波数のものであったものが低い周波数のものに見えてしまう現象がおきてしまい，これをエイリアシングという．これを防ぐには標本化の前に高周波成分を取り除く平滑化を行う必要がある．
それに対して量子化誤差は，信号をディジタル化する際の量子化処理するときに生じる．信号の振幅を特定の階調数で量子化していったときのアナログ信号とディジタル信号の丸め誤差のことを量子化誤差という．画像においては量子化レベル数が極端に少なくなっていったとき，量子化レベルが1かわるごとに等高線のような本来存在しないはずである疑似輪郭が表れる．

フレームバッファとzバッファ

ディジタル画像の画素のRGBを格納するメモリをフレームバッファという．
zバッファはフレームバッファと同様の画像の解像度（ピクセル数）をもって，画素ごとにその画像における奥行きを格納するメモリのことである．このzバッファがあることによって画像のポリゴンに対する陰面消去を行うことができるようになる．

NP完全な問題とNP困難な問題

まず，P問題とは判定問題のうち決定性チューリング機械によって多項式（Polynominal)時間で解かれる問題のことである．判定問題とは二値分類問題のことである．決定性チューリングマシンとは入力xに対して出力yが一意的に出力される単純化・理想化された機械のことである．
次にNP問題とは，非決定性チューリングマシンによって多項式時間で解くことができる問題のことである．非決定性チューリングマシンとは，入力xに対して出力yが一意的に定められず，入力に対する状態の遷移について非決定的に選択できるマシンのことである．（量子コンピュータは厳密にはNTMではない．）
この上で，NP困難な問題とは，NP問題に属しているかはわからないが，少なくともNP以上の時間で解くことが要請される問題のことである．定義としてはすべてのNP問題が問題Aへ多項式時間還元可能であるとき，AはNP困難であるという．これよりNP困難な問題を多項式時間で解くことができるマシンはNP問題を多項式時間で解くことができる．多項式時間還元可能であるとは，多項式時間で解ける問題Aに対してある問題BがAを解くためのアルゴリズムをサブルーチンとして多項式時間で解くことができるときに，問題Bは問題Aへ多項式時間還元可能であるという．
次に，NP完全な問題とは，問題AがNP問題で，かつすべてのNP問題がAへ多項式時間還元可能であるとき，AはNP完全な問題であるという．NP問題の中で最も解くのが難しいとされる．
具体的な問題としては，NP完全な問題は部分和，組み合わせ最適化問題，充足性問題，頂点被覆などである．NP困難な問題は巡回セールスマン問題，ナップサック問題などである．（これらの関係性については関係図を見るとわかりやすい）
http://motojapan.hateblo.jp/entry/2017/11/15/082738
http://www.akita-pu.ac.jp/system/elect/ins/kusakari/japanese/teaching/InfoMath/2007/note/5.pdf

トーンマッピングとヒストグラム平坦化

両者は画像の輝度の変換または濃淡の変換において使われる方法である．
ヒストグラム平坦化では，入力された画像の画素値のヒストグラムに対して，出力の画像の画素値のヒストグラムが画素値の全域にわたって均等に分布するような変換をするものである．特定の画素値の区間に高頻度なヒストグラムになってしまっているときにヒストグラム平坦化を行うことによって，その画像の濃淡を視認しやすくできるようになる．
トーンマッピングでは，画素値を浮動小数点まで記録することによって可能にしたハイダイナミックレンジで撮影された画像はたいていのディスプレイなどへの表示のために（8bit程度へのディジタル化するためには）ローダイナミックレンジ画像に変換する必要があり，このときにトーンマッピングが必要となる．人間の目が明るさに順応することと同様に，特定の領域のダイナミックレンジのみを取り出して8ビットの値に割り当てるということをトーンマッピングでは行う．
輝度もヒストグラムとなるので両者は同様のことをやっているように一見見えるが，後者はHDR画像からLDR画像への変換のために特定領域の輝度のみを取り出して画素値へ割り当てているのに対して，前者はすでにLDR画像の画素値に割り当てられている輝度だけでなくRGBの画素値のヒストグラムに対してそれらが視認しやすくなるように特定の領域の画素値だけ取り出して新たに8ビットの画素値に割り当てるということをするという違いがある．

バイラテラルフィルタとメディアンフィルタ

両者は画像のエッジを保ちながら画像のノイズを平滑化する方法である．
メディアンフィルタでは，ある一つの画素値の周辺の領域の画素値の平均値ではなく中央値をその画素の画素値として出力するように入力画像に対して出力するように変換する方法である．画像の中でスパイク状の点のようなノイズがある場合にメディアンフィルタではもとの画像のエッジを残したままノイズを除去できるという特徴がある．
バイラテラルフィルタでは，注目画素との距離に応じたガウシアン分布による重みづけによって平均化フィルタをかけるのではなく，注目画素とそのほかの位置の画素値の差によるガウシアン分布による重みづけをした画素の平均値をもとめることによって，その位置の画素の出力が決まるようにしたフィルタである．これによって通常の平均化フィルタでは入力画像のエッジが保存されないのに対して，バイラテラルフィルタではエッジを保存することができる．（バイラテラルフィルタを複数回使用することによってエッジを残しながら細かい部分をつぶしたようなノンフォトリアリスティックレンダリングにも使われる．）

二分法とニュートン法

両者は方程式の解を求めるためのアルゴリズムである．
https://qiita.com/sugarcoder18/items/57aca2d38964b634fc4d

計算量におけるクラスPとクラスNP

クラスPは多項式時間で解くことができる問題のクラスであり，決定性チューリングマシンによって解くことができる問題のことである．
クラスNPは多項式時間で正解が正しいか判定できる問題のクラスであり，非決定性チューリングマシンによって解くことができる問題のことである．正解を多項式時間で見つけることができるかはわからなくても，正解であるかどうかを多項式時間で判定することはできる，という問題のことである．
Pに属している問題は多項式時間で正解を導くことができるのでそれが正解かを多項式時間で判定できるのは当然であるのでNPに属していることは明らかですが，現段階ではNPに属している実際の問題の問題は見つかっているが，その問題がPに属していないことは証明することができていないために，$P \neq NP$は証明することができていない．

丸め誤差と桁落ち

両者はコンピュータで計算をさせた時に生じる誤差の種類である．
丸め誤差は，桁数が多い数に対して，特定の桁以降を無視することによって生じる誤差のことである．特定の桁以降の無視による誤差は切り捨て，切り上げ，四捨五入などその丸め方の方法に依存する．
桁落ちとは，近い数を引き算することによって有効数字が少なくなる現象のことである．

打切り誤差は無限級数の計算で特定の項以降を無視することである．
情報落ちとはすでに述べた．
https://mathwords.net/marumegosa