試験日
通常通りならば2020年4月第三日曜日.
基本情報の際と同じく, 一度範囲を軽く通してから間違いが多いところを中心に深掘りしていきたい. 以前同様, 初めはざっと流しながら曖昧なところを調べつつ進めたいです.
使用する参考書
過去問＋以下の本です.
情報処理教科書 応用情報技術者 テキスト＆問題集 2019年版
メモ
基礎理論
論理演算
参考文献：
基本と範囲が重複しているので省略. カルノー図だけ確認.
グラフ理論
参考文献：学部専門教育 グラフ理論（2005） – 北海道大学オープンコースウェア
上記の第4回まで. グラフ理論の基本とデータ構造に関係するグラフのみ覚える. (久々なので)用語の定義のみ簡単に復習.
- グラフの種類
- 同型：二つのグラフの辺と点に１対１で対応づけできる時（同型写像がある時）
- 単純グラフ：ループや多重の辺を含まないグラフ
- 歩道：連結した辺の列
- 道：歩道のうち、どの点も一回しか訪れない歩道
- 閉路：閉じた歩道
- 連結グラフ：どの２点間にも歩道があるグラフ
- オイラーグラフ：全ての辺を一回ずつ通って出発点に戻る（一筆書き）ことができるグラフ
- ハミルトングラフ：全ての点を一回ずつ通って出発点に戻ることができるグラフ
- 木：どの二点間も道が一つしかないグラフ
- 完全グラフ：nC2の辺がある、全ての点間に辺がある
- 正則グラフ：全ての点の次数が同じグラフ
- 二部グラフ：集合間にのみ辺があるように二つの集合にGを分割できる時
- 完全二部グラフ：二部グラフのうち、集合間の対応が全て一本のような点
定義
- V(G)：点集合
- E(G)：辺集合
- グラフの時数列：グラフの次数を昇順に並べたもの
- 端点：次数１の点
- 孤立点：次数０の点
- 隣接行列：点i, 点jに辺があるなら１の行列
- 接続行列：点i, 辺jに辺があるなら１の行列
データ構造に関するグラフ
AVL木：平衡２分探索木の一種、部分木の深さが最大でも１しか違わない
AVL Tree by Java -- これで分かったAVL木
B木：B-Tree by Java -- B木のすごく簡単な実例
”全ての葉から根までのパス上のノード数が等しい”
オートマトン
参考文献：形式言語とオートマトン講義資料
上記のサイト内容で十分そうなので省略.
情報理論関係
参考文献：西田豊明のサイト - 情報符号理論
上記の京都大学の講義資料の中で, おそらく第一・二・六回のみが範囲.
- 情報量
- 定義：情報量I＝-log_2_p(x), p(x) = 事象xが生起する確率
- 1ビット＝1/2の確率の事象が起きるか・起きないかを表した時の情報量
- logなので独立な複数の事象の情報量は足し算になる（加法性）
- 平均情報量 ：その情報源がどれだけ情報を出しているかを測る指標
- 平均情報量 エントロピー
- 全事象が等確率の時に最大になる
- 情報源
- マルコフ情報源：過去のmステップの状態に依存する情報源, m=1は特に単純マルコフ情報源と呼ぶ
- エルゴード情報源：集合平均と時間平均が等しい, 一つの値に収束する
- 定常情報源：時間がずれても”統計的”性質が変化しない情報源
その他
ビックエンディアン・リトルエンディアン
数値誤差
以下のサイトで十分.
