１．基礎理論

ｎ進数、基数変換

• （ある程度理解しているので省略。試験でも後回しにして時間かければ計算できる）

浮動小数点形式（ＩＥＥＥ形式）

• 符号部Ｓ（１ビット）＋指数部Ｅ（８ビット）＋仮数部（２３ビット）
• 
• 仮数部は最上位の桁を整数第一位にする（正規化）。例外は指数部が０の場合。
• 符号部Ｓ＝０：正、１：負
• 指数部Ｅは、指数に１２７を足したものを設定。
• 指数部は２の補数表現方式と、定数を足す（０乗を中間の値とする）方式がある

誤差の種類

• 丸め誤差
  • 切り捨て・切り上げ・四捨五入の誤差。
• 桁落ち
  • ほぼ同じ大きさの数値の減算によって有効桁が減ること。
• 情報落ち
  • 大きな数字と非常に小さな数字の加算で小さな数字が加味されないこと。
• オーバーフロー、アンダーフロー
  • 表現できる範囲を超えてしまうこと。

論理演算

• ド・モルガンの法則
  • 　　※は命題Aの否定
• が成り立つ場合も成り立つ（対偶論理）

カルノー図

複数の命題をマトリックス化した表。
すみません、図示できない。参考書等を参照。

• 真偽値表に対する論理式を確認したい場合
  • カルノー図を作成する
  • 隣あった１（真）の場所を長方形の枠でくくる。長方形はなるべく大きくなるようにする。長方形をいくつか使用してすべての１をくくる。
  • 長方形を論理式に変換して表現する（マトリックス中のどの命題が真／偽であるか）

回路図

論理回路と半加算機・全加算機、フリップフロップといった内容。
（なぜか回路図は自分が拒否反応を起こすのであきらめる）

データ圧縮

• ハフマン符号
  • 各記号の生起確率に応じて符号をふる。頻度が高いものは短い符号（１とか）、頻度の小さいものは長い符号（００１１０１とか）をとる。生起確率がもっとも低い２記号を組み合わせ、それを繰り返して二分木を構成すればＯＫ。

• ランレングス法
  • 同じ記号が連続した回数をつけて表現。同じ記号が連続して続くことが多い場合に有効。
  • 「ＡＡＡＡＡＢＣＣＣＣ」→「Ａ５Ｂ１Ｃ４」

誤り検出・訂正

• パリティ検査符号
  • 末尾に１ビット余分に情報をつけておき、誤りを検出する。１の個数が奇数になるように決める奇数パリティと偶数になるように決める偶数パリティがある。
  • 誤り検出しかできない。

• パリティ検査符号（水平・垂直）
  • 水平・垂直パリティを組み合わせれば１ビットの誤りが訂正できる。
  • （１ビット誤りが発生した場合、行と列でつじつまがあわない場所がでるので特定できる）

• ハミング符号
  • ビット列の１部を組み合わせたものをいくつか符号ビットとして定義して付与する。
  • よくあるのが４ビットの情報〜に３ビットの冗長ビット〜を埋め込む形式。
    • 
  • １ビット誤りを訂正、２ビット誤りを検出できる。

• ＣＲＣ符号
  • （まだ勉強してない。難しそうだったのでやる気なくした）

状態遷移図（有限オートマトン図）

• （理解しているので省略）

ＢＮＦ表記法

• なんかPrologぽい記法。再起とか使いまくりで理解しがたい。

正規表現

[A-Z]、[0-9]、+、* とか。エディタとかの正規表現と同じ。

ポーランド記法

• 数式で演算子をどこに置くかをルール決めしたもの

• 中置記法　「Ａ＋Ｂ」
• 前置記法／ポーランド記法　「＋ＡＢ」
• 後置記法／逆ポーランド記法　「ＡＢ＋」

確率

• 事象Ａと事象Ｂが共に起こる確率
  • 
• 事象Ａと事象Ｂのいずれかが起こる確率
  • 
• 条件付き確率（Ａが起こったときにＢが起こる確率）　Ａが起こる場合と起こらない場合でＢの確率が異なる場合とか。
  • 

※自分はばかなので∪と∩がごっちゃになる。Unionが∪で覚える。

• （確率分布（二項分布、ポアソン分布）、マルコフ過程といった内容は理解できなかった。あきらめる）

統計、相関、回帰直線

• 回帰直線はデータと直線の誤差が最小となるような直線。最小二乗法で求める。
• （ほか、たいした内容はなさそうなので省略）

待ち行列理論

• よくいわれるのがＭ／Ｍ／１モデル。１項目（客の到着）がポアソン分布に従い、２項目（サービス時間）が指数分布に従い、３項目（窓口）が１個。
• （理論がやたらと難しいのであきらめ＞＜）

以上。