紙媒体で知識や経験を管理すると無くなりがちなのでブログで管理することにしました.
      殆どの記事は自分自身のためだけに書いているため,他人に見せる前提の内容, 文章ではありません.
      また, ブログのコメント欄を解放していたらbotからの迷惑行為を受けたため現在コメント欄は解放しておりません.

【環境設定】Ubuntu 18.04LTSでCtrl + Spaceで変換する

mozcを起動してデフォルトでHankaku/Zenkakuの項目をメモして
f:id:umashika5555:20180917024215p:plain
全く同じものをCtrl+Spaceに置き換えてエントリーを追加すればよい.
f:id:umashika5555:20180917024220p:plain
f:id:umashika5555:20180917024217p:plain
mozcを閉じるときに「設定は新しいアプリケーションから適応されます」的なことを言われたので, 新しいアプリを起動して試してみたができなかった.
しかし, 再起動したらできた.

【環境設定】ubuntuにGPUドライバを入れる

自分のノートPCにubuntu 18.04 LTSを入れて, GPUドライバがデフォルトでIntelの内蔵のグラフィックドライバになっていたため, NVIDIAのに変えた.
ここを参考にしたらスンナリできた.
taktak.jp

【統計学】 t分布

t分布はz分布と同じく, 平均 \mu = 0 であるが, その形状は自由度f が小さいとz分布に比べて広がりが大きく, 自由度fが多クック成るに従ってz分布に近づき, 自由どうが[\infty]のときにz分布に一致する.
このため, t分布は主にサンプルサイズが小さく,  \sigma が不明(未知) のときの検定や推定に用いられる.

標本平均のz分布である

\begin{eqnarray*}
z = \frac{\bar{x}-\mu}{\frac{\sigma}{\sqrt{n}}}
\end{eqnarray*}
の分母の母標準偏差 \sigmaを標本標準偏差sに置き換えたものが自由度f(=n-1)のt分布となる.
 
\begin{eqnarray*}
z = \frac{\bar{x}-\mu}{\frac{s}{\sqrt{n}}}
\end{eqnarray*}
t分布は自由度の小さい標本に対して行うものであるため, t分布表には例えば50を超えるような自由度は細かく記載されていない.
このとき自由度78のようなものを扱いたいときは記載されている自由度60と自由度80における値を用いて 逆数線形補間法により, 導出する.

【統計学】 z分布(標準正規分布)

N(0, 1) の正規分布を標準正規分布という.
これは正規分布の密度関数の変数xを z = \frac{x-\mu}{\sigma}で変換(標準化, 基準化)した形.

 N(\mu, \sigma^2) N(0, 1^2)のz分布に変換することによって, どのような確率自称に対しても, 複雑な計算結果を一覧表にした付録の数表(確率分布表) を使って,
簡単に正規分布の確率が求められるようになっている.
f:id:umashika5555:20180905173749p:plain
図:z分布表の見方
表のz=1.96は信頼度95%における上側確率についてのz値を表している.

z分布の使いみち

  • 標準偏差 \sigmaが既知のときの検定, 推定
  • 標準偏差 \sigmaが未知だが, 大標本のときの検定, 推定

2番目の根拠は中心極限値定理である.
すなわち母集団分布が正規分布であろうが, 正規分布じゃない分布であろうが, 和 X_1 + X_2 + ... + X_nの確率分布の形は, nが大きいときにはほぼ正規分布とみなして良いという定理から来ている.
サンプル数nが大きいとき
 S_n = X_1 + .... + X_n  N(n\mu, n\sigma^2)
 \bar{x} = \frac{X_1 + .. + X_n}{n} N(\mu, \frac{\sigma^2}{n})に従う.

【グラフ理論】 中国人郵便配達問題

中国人郵便配達問題
https://ja.wikipedia.org/wiki/%E4%B8%AD%E5%9B%BD%E4%BA%BA%E9%83%B5%E4%BE%BF%E9%85%8D%E9%81%94%E5%95%8F%E9%A1%8C

中国人郵便配達問題(ちゅうごくじんゆうびんはいたつもんだい、英: Chinese postman problem)とは、グラフ理論における問題の一つであり、以下のように定義される。
Gを連結な無向グラフとし、Gの各辺には距離が割り当てられている。このとき、Gの辺をすべて通るような閉路のうち、距離の合計が最小になるものを求めよ。

まずオイラーグラフGが与えられたときに, オイラー回路Wを求めるアルゴリズムは次の3つあるらしい(詳しくは勉強していない)

f:id:umashika5555:20180904000743p:plain
図: オイラー回路を求めるアルゴリズム

Gの辺をすべて通らなければならないので, (距離の合計を最小化するためには)同じ辺なんて2回通らない方がよいのは自明.
Gがオイラー回路(各点の次数が偶数)であれば, 各辺1回しか通らないため, 辺の重みの総和が答え.

オイラーグラフでないとき, 少なくとも1つの辺は2度通る必要がある.
重複する辺の重みの和は最小化した方が良い. (なぜならグラフGの辺の総和に重複分の重みを足すので重複文はできるだけ小さくしたいから)
各辺を一回しか通らないという考えのもと, 辺を重複して通るとは, 辺二重化を行ったグラフで考えれば良い.
f:id:umashika5555:20180904003011p:plain
図: 辺の二重化
上図は奇点に対して, 辺二重化をするということで, 単一の辺には一回しか通らないという原則を生み出している.

中国人郵便配達問題のアルゴリズム
(1)次の条件を満たすようにGの対象の辺を辺二重化してオイラーグラフ G^*をつくる
 [条件] G^*は辺二重化して付け足した辺の重みの総和 \sum_{e\in E(G^*)-E(G)}w(e)が最小になる
(2)  G^*オイラー回路を見つける(上記アルゴリズム)
に従っている.

中国人郵便配達問題の解き安さは下の関係になっている.
f:id:umashika5555:20180904010022p:plain
図: 中国人郵便配達問題の解きやすさの関係(大きいほど一般化された問題)
オイラーグラフであるときは, 始点と終点が一致し, 全ての辺をそれぞれ一回しか通らないので辺の重みの総和が答え.
次にオイラー小道を持つグラフのときは, 始点から終点までの最短経路を考え(ダイクストラ法), その最短経路を辺二重化することによって閉路とすることでオイラーグラフに帰着する.
f:id:umashika5555:20180904011053p:plain
図: オイラー小道を持つグラフでの中国人郵便配達問題の解き方
最後に一般の連結グラフでは, 奇点が偶数個のグラフは, 奇点全体の集合Sの任意の2点から完全グラフを作り, そこから完全マッチングな辺集合Mをつくる.(完全マッチングについてはまた今度). Mの任意の辺について対応するGの辺を二重化する. これを G^*とする.  G^*についてオイラー回路を求めて, オイラーグラフの問題に帰着させる.

【グラフ理論】 オイラーグラフについて

オイラーグラフ」という考え方は,「中国人郵便配達問題」を考える際に重要になってくる.
中国人郵便配達問題とは, 正の重み付き無向グラフについて, 重みの和が最小となる閉路(閉じた道)を求める問題である.

まずはオイラーグラフについて考える.
オイラーグラフの定義は, "オイラー回路を持つグラフ"である.
では, オイラー回路とは, "すべての辺を含む回路" である.
また, オイラー小道とは, "すべての辺を含む閉じていない(始点 \neq終点)の小道"である.

定理2.1
Gを連結で位数が2以上のグラフとする.
Gがオイラーグラフである  \Leftrightarrow Gの全ての点の次数が偶数

証明:
「Gがオイラーグラフ→Gの全ての点の次数が偶数」の証明
Gはオイラーグラフであるので定義より, Gはオイラー回路を持つ. すなわち全ての辺を含む回路を持つ.
各点は, 出る辺と入る辺(日本語おかしい)の2本ずつカウントされるので, 次数は偶数.

「Gがオイラーグラフ←Gの全ての点の次数が偶数」の証明
Gは連結で位数が2以上であるので定理1.9より, Gには閉路Cが存在する.
(i)閉路Cが, Gの全ての辺を含んでいるとき. E(C) = E(G)
これはGにおけるオイラー回路である.
(ii) 閉路Cが, Gの全ての辺を含んでいないとき, すなわちE(C)  \in E(G)
GからCを除いたHを考える. このCの各点の次数は偶数なので, Hの各点も偶数になる.
これを再帰的に, 言えれば良い. (省略)
f:id:umashika5555:20180903212959p:plain

これを言い換えると
系2.2
Gを連結, 位数2以上のグラフ
Gがオイラーグラフ \LeftrightarrowE(G)が互いに素な閉路に分割できる


系2.3
Gを連結, 位数2以上のグラフ
Gがオイラー小道をもつ \LeftrightarrowGの奇点の個数が2

説明:
奇点となるのは始点と終点の2点.
始点は偶数個+出, 終点は偶数個+入の奇数個となる.

証明:
「Gがオイラー小道をもつ→Gの奇点の個数が2」の証明
オイラー小道Pの始点と終点以外は入と出で辺を2本カウントするので偶点.
始点は偶数+出, 終点は偶数+入のみ
「Gがオイラー小道をもつ←Gの奇点の個数が2」の証明
始点uと終点vを結ぶ辺eをGに加えてグラフG+eを考える.
G+eは全ての点が偶点 \LeftrightarrowグラフG+eはオイラーグラフ \Leftrightarrowオイラー回路Wが存在する
uを始点としてeをまずたどりオイラー閉路Wを作る.
f:id:umashika5555:20180903231554p:plain
赤はオイラー回路
これを W: u, v, w_1, w_2, ..., w_k, u と表せる.
ここで v, w_1, w_2, ..., w_k, uはGのオイラー小道である.


参考: