待ち行列理論・計算量
1. 待ち行列理論
このサイトを見ましょう。
人がやってくる到着率がポアソン分布、サービス時間が指数分布に従い、窓口が一つの場合をM/M/1モデルと呼びます。M/M/1モデルでの待ち時間の求め方は、
μ = 列に並びにくる人の時間当たりの数
λ = お店が時間当たりにさばく客の数
として利用率ρ = λ/μ とします。
この時、待ち時間 = ρ / (1-ρ) × 平均サービス時間 で計算できます！
とりあえずこれだけ暗記してたら大丈夫とのこと。
時間があったら計算過程とかも勉強して見たいなーと思います。
2. 情報量
情報量 ある事象がどれぐらい起こりにくいかを表す尺度。
ある事象が起こる確率をPと置くと、
選択情報量 = -log2(P)ビット で計算できる。
そして、全ての場合の情報量の平均を**平均情報量(エントロピー)**と呼ぶ。
平均情報量がデータの圧縮の限界値となる。
3. オートマトン
オートマトンとは、
- 外から、情報が連続して入力される
- 内部に、状態を保持する
- 外へ情報を出力する
以上の特徴を持ったシステムのこと。
状態や遷移の数を有限個で表すことができるものを有限オートマトンという。
当たり前の様で何言ってるのかわからない。。。
4. 木の走査順
グラフ理論における木で、それぞれのノードを読んでいく順番を走査という。
例えば A+B という演算を行う時、コンピュータはA,+,Bの三つのノードを処理する必要がある。
この時、ノードの処理順番として三つの場合が考えられる。
前置表記法(ポーランド表記法)
+AB
中置表記法
A+B
後置表記法(逆ポーランド表記法)
AB+
人間にとって見やすいのはもちろん中置表記法やけど、コンピュータにとっては逆ポーランド表記法の方が処理しやすいらしい。表記法を置き換える問題が出ることがあるので要注意。 逆ポーランド記法では、方程式なら最後は多分イコールになるはず。
5. 計算量
計算量とはアルゴリズムを実行するのにどれくらい時間がかかるかを表すもの。
2の情報量と混同しない様に注意しないとな。
Ｏ(オーダ)記法という表記法を用い、入力データに対する増加量で表す。
n個の入力データに対してアルゴリズムを実行するときに、
計算量がnに比例して増加するものをＯ(n)
計算量がn^2に比例して増加するものをＯ(n^2)
計算量がlog(n)に比例して増加するものをＯ(log(n))
などという風に表します。
これ以上はきちんと計算も含めてアルゴリズムごとに理解したいので、探索とかソートのところで触れることにする。今回は一旦パス。