チューリングマシンは無限に長いテープとそのテープを読み書きするヘッド、及び内部状態を保持するためのメモリからなる。チューリングマシンはその内部状態に従ってヘッドを動かし、テープから情報を読んで状態を変更したり、テープに情報を書き込んだりする。
チューリングマシンの動作は非常に単純だが、チューリングマシンで解くことのできる問題のクラスは実際の計算機の解くことのできる問題のクラスと同一であり、計算機のモデルとしてよく利用される。
関係データベースの正規化とは、関連するデータをグループ化したり、同一データを重複して持つことが無いようにテーブルを分割・整理したりすることにより、データベースを正規形と呼ばれる形式に統一することを言う。
正規化を行うことで、データの更新による矛盾の発生を防ぐことができ、データの一貫性が保たれる。
正規化されていないデータベースはしばしば非効率であり、データベースの活用の妨げとなる。
正規化のうち特によく知られているのが第1〜第5正規形とボイス・コッド正規形であり、特に第3正規形までのものは実務でもよく用いられている。
スペクトル拡散通信とは、デジタル信号を送信する際に冗長性を付加して本来必要とされる帯域より広い帯域に拡散させて通信を行う通信方式。受信側では送信側と同じ拡散符号を利用して元のデジタル信号を復元する。
冗長性が非常に高いためノイズの影響を受けにくく、妨害や干渉に非常に強い。また、デジタル信号の復元には送信側と同じ拡散符号が必要なため、情報の秘匿性にも優れる。
決定木の学習では訓練データを何らかの指標に基づいて幾つかの集合に分割し、分割したそれぞれのデータを部分木とする木を作成する。それぞれの部分木に対しても再帰的に分割を行い、最終的な木構造を得る。
良い決定木を得るためには訓練データの分割の指標の定め方が問題となる。この指標の定め方には様々な種類があり、例えばID3やC4.5と呼ばれる手法では情報量(エントロピー)を基に指標を定める。
事象Aの確率(事前確率)をP(A)とし、条件Aの下で事象Bが成立する確率(事後確率・条件付き確率)をP(B|A)とする。
このとき、P(B|A)はP(A), P(B), P(A|B)を用いて次のように記述できる。
P(B|A) = P(A|B) * P(B) / P(A)
ベイズの定理はベイズ統計学の基礎であり、迷惑メールのフィルタリングなど、様々な応用がなされている。
