R05ist

数学

線形代数 (Linear algebra)

$n\times n$ の実対称行列 $A=[a_{ij}{]}_{n\times n}\in {\mathbb{R}}^{n\times n}$ に対して、$A$ の各要素 $a_{ij}$ が $a_{ij}\in \{0,1\}$ ($1\le i,j\le n$) かつ $a_{ii}=0$ ($1\le i\le n$) を満たすとする。$A$ に対して、$D=[{\delta }_{ij}({\sum }_{k=1}^n{a}_{ik}){]}_{n\times n}$ と定義する。ただし、${\delta }_{ij}$ は、$1\le i,j\le n$ に対して、$i=j$ のとき ${\delta }_{ij}=1$、そうでないとき ${\delta }_{ij}=0$ によって定義される。さらに、$L=D-A$ と定義する。以下の各問いに答えよ。

(1) 以下の $A$ に対して、$L=D-A$ を求めよ。

$$A=\left(\begin{array}{cccc}0& 1& 1& 0\\ 1& 0& 1& 0\\ 1& 1& 0& 0\\ 0& 0& 0& 0\end{array}\right)$$

(2) (1) で求めた $L$ の固有値を全て求めよ。
(3) (2) で求めた $L$ の各固有値に対する固有空間を求めよ。
(4) 一般に $L$ は固有値 $0$ を持つことを示せ。

Link to original

---

解析学・微積分 (Analysis and calculus)

(1) $\mathbb{R}$ 上の関数 $f(x)=\cos x$ の $k$ 階導関数を $f^{(k)}(x)$ で表す。以下の各問いに答えよ。
(a) 全ての $k\ge 1$ について $f^{(k)}(0)$ を求めよ。
(b) $f(x)$ の原点周りでのテイラー級数を

$$\sum _{k=0}^{\infty }{a}_k{x}^k$$

とするとき、全ての $k\ge 0$ に関する $a_k$ を求めよ。
(c) 全ての $x\in \mathbb{R}$ について

$$\sum _{k=0}^{\infty }|a_k{x}^k|$$

が収束することを示せ。
(2) 次の微分方程式の一般解を求めよ。なお、$y^{\prime }$ は関数 $y(x)$ の $x$ に関する 1 階導関数を表している。

$$y^{\prime \prime \prime \prime }-2y^{\prime \prime \prime }-y^{\prime \prime }-4y^{\prime }+12y=0$$

(3) 開曲線 $C$ に沿った複素積分

$${\int }_C\frac{1}{z(z^2-1)}dz$$

を求めよ。ただし、$C$ は円 $|z|=r$, $r>0$ かつ $r\ne 1$ とする。

Link to original

---

ベクトル解析

直交座標系において、$x$、$y$、$z$ 軸方向の単位ベクトルをそれぞれ $\mathbf{i}$、$\mathbf{j}$、$\mathbf{k}$ とする。ベクトル場 $\mathbf{F}$ を $\mathbf{F}=y\mathbf{i}-x\mathbf{j}+z\mathbf{k}$ とする。次の各問に答えよ。
(1) $C$ を $x^2+y^2=4$, $z=0$ で定義される円とする。次に示す $C_1$ および $C_2$ に沿った線積分

$${\int }_{C_1}\mathbf{F}\cdot d\mathbf{r}\text{および}{\int }_{C_2}\mathbf{F}\cdot d\mathbf{r}$$

を求めよ。
(a) $C_1$: $C$ 上を点 $A(1,\sqrt{3},0)$ から点 $B(-1,\sqrt{3},0)$ まで反時計回りに向かう曲線
(b) $C_2$: $C$ 上を点 $A(1,\sqrt{3},0)$ から点 $B(-1,\sqrt{3},0)$ まで時計回りに向かう曲線
(2) $S$ を半球面 $x^2+y^2+z^2=4$ ($0\le z$) と平面 $z=0$ で囲まれた領域の境界とする。面積分

$${\int }_S(\nabla \times \mathbf{F})\cdot d\mathbf{S}$$

を求めよ。外向き法線ベクトルを用いよ。

Link to original

---

確率・統計

箱の中に5枚のコイン（コイン1～コイン5）がある。箱から一様ランダムにコインを1枚選んで何度か投げる試行を考える。ただし、それぞれのコイン $i$ の表が出る確率 $p_i$ は次の通りである。

$$p_1=0,p_2=\frac{1}{4},p_3=\frac{1}{2},p_4=\frac{3}{4},p_5=1$$

表が出る事象を $H$ とし、コイン $i$ が選ばれる事象を $C_i$ とする。
(1) 選んだコインを1回投げるとする。表が出る確率 $p(H)$ を答えよ。
(2) 選んだコインを1回投げたところ表が出たとする。条件付き確率 $p(C_i|H)$ を $i=1,\dots ,5$ についてそれぞれ求めよ。
(3) 選んだコインを2回投げるとする。条件付き確率 $p(H_2|H_1)$ を求めよ。ただし $H_j$ は $j$ 回目に表が出る事象であり、$j=1,2$ である。
(4) 選んだコインを4回投げるとする。$p(C_i|B_4)$ を $i=1,\dots ,5$ についてそれぞれ求めよ。ただし $B_4$ は4回目に初めて表が出る事象を表す。

Link to original

---

専門科目

情報理論

問1

以下の各問いに答えよ。
(1) 区間 $[0,a]$ ($a>0$) 上の一様分布に従う確率変数の微分エントロピーを求めよ。
(2) 区間 $[0,a]$ ($a>0$) 上で定義された確率密度関数 $p(x)=\frac{2x}{a^2}$ に従う確率変数の微分エントロピーを求めよ。

Link to original

---

問2

時刻 $t$ の入力 $X_t\in \{0,1\}$ ($t=1,2,\dots$) に対し、入力と独立な誤り源 $S_E$ から発生した記号 $Z_t\in \{0,1\}$ が加わった値 $Y_t=X_t\oplus Z_t$ が出力される加法的2元通信路 $W$ を考える。ただし、$\oplus$ は排他的論理和を表し、$0\oplus 1=1$、$1\oplus 1=0$ である。誤り源 $S_E$ が、$P(Z_{t+1}=1|Z_t=0)=0.25$、$P(Z_{t+1}=1|Z_t=1)=0.5$ となる定常な単純マルコフ情報源である場合について、以下の問いに答えよ。
(1) 誤り源 $S_E$ の定常確率分布を求めよ。
(2) 誤り源 $S_E$ のエントロピーレート $H(S_E)$ を求めよ。
(3) $X^n=(X_1,\dots ,X_n)$ が $P(X_t=1)=\frac{1}{2}$ ($t=1,2,\dots ,n$) である離散無記憶情報源からの出力であり、$Z^n=(Z_1,\dots ,Z_n)$ が定数 $z^n\in \{0,1{\}}^n$ に固定されていると仮定する。$Y^n=(Y_1,\dots ,Y_n)$ が $P(Y_t=1)=\frac{1}{2}$ ($t=1,2,\dots ,n$) である離散無記憶情報源の出力であることを示せ。
(4) 通信路 $W$ の通信路容量は以下の式で定義される。

$$C=\underset{n\to \infty }{\lim }\underset{P_{X^n}\in {\mathcal{P}}_n}{\max }\frac{1}{n}I(X^n;Y^n)$$

ただし、$I(X^n;Y^n)$ は $X^n$ と $Y^n$ の間の相互情報量を、$P_{X^n}$ は入力 $X^n$ の確率分布を、${\mathcal{P}}_n$ は $\{0,1{\}}^n$ 上の確率分布全てからなる集合を表す。このとき、$C=1-H(S_E)$ となることを示せ。

Link to original

---

オートマトンと言語

問1

白玉が $k$ 個、赤玉が $l$ 個入っている袋から1つずつ玉を取り出すという操作を、袋が空になるまで繰り返す。（全部で $n=k+l$ 回の操作が行われる。）このとき、取り出された順に玉の色を並べることによって得られる長さ $n$ の文字列 $a=a_1{a}_2\dots a_n$ を次のように定義する。各 $i\in \{1,2,\dots ,n\}$ に対し、$i$ 回目の操作で白玉が取り出されたとき $a_i=w$、赤玉が取り出されたとき $a_i=r$ とする。このようにして得られるすべての文字列 $a$ からなる集合を $L_{k,l}$ とする。すなわち、$\Sigma =\{w,r\}$ としたとき $L_{k,l}\subseteq {\Sigma }^n$ である。また、$i$ 回目の操作で白玉が取り出されたとき、その時点で袋の中に残っている赤玉の個数を $p_i$、赤玉が取り出されたとき、その時点で袋の中に残っている白玉の個数を $p_i$ とし、報酬 $p_i$ が与えられるとする。このようにして得られるすべての報酬の系列 $p=p_1{p}_2\dots p_n$ からなる集合を $P_{k,l}$ とする。例えば、$k=l=3$ で、赤、白、白、赤、赤、白の順に玉を袋から取り出したとき，$a=rwwrrw$、$p=322110$ となるので、$a\in L_{3,3}$、$p\in P_{3,3}$ であるが、$rwwwrw\notin L_{3,3}$（$w$ と $r$ の出現数は等しいはず）、$322111\notin P_{3,3}$（最後に受け取る報酬は必ず0 のはず）である。

(1) $k=l=3$ のとき、集合 $L_{k,l}$ を受理する状態数最小の決定性有限オートマトンの状態遷移図を示せ。ただし、受理状態に到達することのない状態、および、そのような状態への遷移は省略してもよい。

(2) $k=l=3$ のとき、集合 $P_{k,l}(\subseteq \{0,1,2,3{\}}^6)$ を受理する状態数最小の決定性有限オートマトンの状態遷移図を示せ。ただし、受理状態に到達することのない状態、および、そのような状態への遷移は省略してもよい。

(3) 任意の白玉数 $k$、赤玉数 $l$ に対し、玉の取り出し方によらず、報酬の総和が ${\sum }_{i=1}^n{p}_i=kl$ となることを示せ。（ヒント：$n$ に関する帰納法を用いよ。）

Link to original

---

問2

文脈自由文法を４つ組 $(N,\Sigma ,P,S)$ で表す。ただし、$N$、$\Sigma$、$P$、$S$ をそれぞれ非終端記号の集合、終端記号の集合、生成規則の集合、開始記号とする。$\Sigma =\{a,b\}$ とする。
(1) $L_1=\{a^i{b}^j|0\le i<j\}$ とする。言語 $L_1$ を生成する文脈自由文法 $G_1=(N_1,\Sigma ,P_1,S)$ の生成規則の集合 $P_1$ を与えよ。ただし $|N_1|=1$ とする。
(2) $L_2$ を以下の条件を満たす言語とする。

• $L_2\cup \{a^i{b}^j|0\le i<j\}\cup \{a^i{b}^j|i>j\ge 0\}={\Sigma }^{\ast }\setminus \{a^i{b}^i|i\ge 0\}$
• $L_2\cap \{a^i{b}^j|0\le i<j\}=L_2\cap \{a^i{b}^j|i>j\ge 0\}=\varnothing$
  言語 $L_2$ を生成する文脈自由文法 $G_2=(N_2,\Sigma ,P_2,S)$ の生成規則の集合 $P_2$ を与えよ。ただし $|N_2|\le 2$ とする。
  (3) $L_3={\Sigma }^{\ast }\setminus \{a^i{b}^i|i\ge 0\}$ とする。以下のような生成規則の集合を持ち、かつ言語 $L_3$ を生成する文脈自由文法 $G_3=(N_3,\Sigma ,P_3,S)$ を考える。ただし $N_3=\{S,X\}$ であり、$ϵ$ は空文字列を表す。(i), (ii), (iii) を与えよ。
  $S\to \boxed{(i)}|\boxed{(ii)}|\boxed{(iii)}$
  $X\to bX|aX|ϵ$
  (4) 以下の状態遷移図を持つ決定性有限オートマトン $M=(K,\Sigma ,\delta ,q_0,F)$ で受理される言語を $L(M)$ とする。ただし、$K=\{q_0,q_1,q_2\}$、$\Sigma$、$\delta$、$q_0$、$F=\{q_0\}$ は、それぞれ $M$ の状態の集合、アルファベット、遷移関数、初期状態、受理状態の集合を表す。$L_4={\Sigma }^{\ast }\setminus L(M)$ とする。言語 $L_4$ を生成する文脈自由文法 $G_4=(N_4,\Sigma ,P_4,S)$ の生成規則の集合 $P_4$ を与えよ。ただし $|N_4|\le 2$ とする。

\usepackage{tikz}
\begin{document}
\begin{tikzpicture}[->, shorten >=1pt, auto, semithick]
  % Define states with absolute positions
  \node[double,circle, draw] (q0) at (0, 0) {$q_0$};
  \node[circle, draw] (q1) at (2, 0) {$q_1$}; % sqrt(3)*2 = 3.46 for equilateral triangle
  \node[circle, draw] (q2) at (1, -1.732) {$q_2$};
  % Transitions
  \path (q0) edge[bend left] node[midway] {a} (q1)
        (q0) edge node[below] {b} (q2)
        (q1) edge node[below] {b} (q0)
        (q1) edge node[midway] {a} (q2)
        (q2) edge[loop right] node {a, b} ();
\end{tikzpicture}
\end{document}

Link to original