確認問題

以下にすらすら答えられる人は読まなくても大丈夫。
・マルコフ過程とは何かを説明せよ。
・平均値μ(ミュー)、標準偏差σ(シグマ)において、μ±1σ、μ±2σ、μ±3σはそれぞれ何％ぐらいかを答えよ。
・ハミルトン閉路、オイラー閉路とはそれぞれ何かを説明せよ。
・隣接行列、隣接リストとは何か、具体的にイメージできるか。

確率＞マルコフ過程

マルコフ過程とは、「現在の状態によって未来の状態が決まる」と仮定した状態。本来の事象はもっと複雑だが、過去の状態は関係なく、今の状態で未来の状態の確率が定まる、と仮定している。
例えば今日の天気が晴れ、曇り、雨のいずれかによって、明日の天気が晴れ、曇り、雨のどれになるかの確率分布が定まるとする。

統計＞正規分布と標準偏差

平均値μ(ミュー)、標準偏差σ(シグマ)において、
μ±1σ：およそ68％
μ±2σ：およそ95%
μ±3σ：およそ99%
これだけ覚えておけばよい。
オマケ：μ±2σ以上のゾーンは有意差があると見なせる。

グラフ理論

ここでいうグラフとは一般的な表形式のもの、棒線グラフや折れ線グラフとは異なる。ツリー構造やハミルトングラフなどを指す。

閉路

始点と終点が同じとなる経路が存在する場合に、そのグラフを「閉路」と呼ぶ。
三角形を描いて、進行方向が特に定義されていない場合、どの点においても始点は終点たりえるので、閉路と呼べる。ただし、閉路の条件は「いずれかのノードにおいて始点と終点が両立する」ことである。
もし三角形ＡＢＣにおいて「辺ＡＢにおいてＡ→Ｂのみ可能」「辺ＢＣにおいてＣ→Ｂのみ可能」（つまりＢからＡにもＣにも行けない）という制限があるなら、ＡＢＣのどこを始点としても帰ってこれないので、閉路ではなくなる。

ハミルトン閉路

「すべての点を１度ずつ通る」閉路があること。
例えば直方体の頂点をノード、辺をエッジと見なせば、そのグラフ（立方体）はハミルトン閉路となる。

オイラー閉路

「すべての辺を１度ずつ通る」閉路があること。

グラフのデータ構造

上記のようなグラフをどうやってデータ構造として表現するか？
「隣接行列」「隣接リスト」がある。
隣接行列とは、ノードの数ＮがあるときＮ行Ｎ列のグラフを作り、隣接するノード同士には１を、それ以外には０を記入する方式。データがでかくなりやすいため非推奨。
隣接リストとは、各ノードごとにリストを作り、そのノードと隣接しているノードをリスト形式で追加していくもの。「あるノードからたどる経路を記載する」ものではない点に注意。