R03ist

数学

線形代数

$n\times m$ 実行列 $A\in {\mathbb{R}}^{n\times m}$ の第 $j$ 列 ($j=1,2,\dots ,m$) を $a_j\in {\mathbb{R}}^n$ とする。
各部分集合 $J\subseteq \{1,2,\dots ,m\}$ について、その要素数を $|J|$ で表し、$a_j(j\in J)$ を $j$ に関する昇順で左から並べて得られる $A$ の部分行列を $A[J]\in {\mathbb{R}}^{n\times |J|}$ で表す。
このとき、以下の問いに答えよ。

1. 以下の行列 $A$ に対し、$\{a_j|j\in J\}$ が線形独立であるような部分集合 $J\subseteq \{1,2,3,4,5,6\}$ をすべて求めよ。 $$A=\left(\begin{array}{cccccc}1& 0& 0& -2& 0& 0\\ 0& 1& 0& -2& -3& -5\\ -2& -2& 0& 4& 6& 0\end{array}\right)$$
2. (1) の行列 $A$ に対し、$rank(A[J])<|J|$ を満たす部分集合 $J\subseteq \{1,2,3,4,5,6\}$ であって、$J$ の任意の真部分集合 $I\subset J$ について $rank(A[I])=|I|$ が成り立つものをすべて求めよ。ただし、空集合 $\varnothing$ に対しては $rank(A[\varnothing ])=0$ と定義する。
3. 一般の $A\in {\mathbb{R}}^{n\times m}$ について、$I\subseteq J\subseteq \{1,2,\dots ,m\}$ かつ $rank(A[J])=|J|$ のとき、$rank(A[I])=|I|$ が成り立つことを示せ。

---

微分積分

${\mathbb{R}}^2$ 上の関数

$$f(x,y)=(x+y)\exp \left(-\frac{x^2+y^2}{2}\right)$$

について次の各問いに答えよ。

1. $f$ の停留点を全て求めよ。
2. $f$ の極大点と極小点を全て求めよ。
3. $f$ の最大値または最小値が存在する場合、それらを求めよ。

微分方程式

次の微分方程式の一般解を求めよ。

$$\frac{dy}{dx}=\frac{x^2+6y^2}{4xy}$$ $$\frac{dy}{dx}=e^{2x+y+1}-1$$

---

ベクトル解析

直交座標系において、$x$，$y$，$z$ 軸方向の単位ベクトルをそれぞれ $\mathbf{i}$，$\mathbf{j}$，$\mathbf{k}$ とする。次の各問に答えよ。

1. 3点 $(2,-6,2)$, $(1,-10,-1)$ および $(-1,2,3)$ が決定する平面と点 $(2,-2,-2)$ との距離を求めよ。
2. ベクトル場 $\mathbf{F}$ を

$$\mathbf{F}=\left(-\frac{xy}{4}\right)\mathbf{i}+(z-x)\mathbf{j}+(x+y)\mathbf{k}$$

とする。曲線 $C:x=\frac{y^2}{8},y=-z$ に沿って、$(0,0,0)$ から $\left(\frac{9}{2},6,-6\right)$ までの線積分

$${\int }_C\mathbf{F}\cdot d\mathbf{r}$$

を計算せよ。

---

Link to original

---

複素関数論

次の各問に答えよ。

1. 複素関数

$$f(z)=\frac{1}{z(z-2{)}^2}$$

を $z=0$ でローラン展開せよ。
2. 複素関数

$$g(z)=z\sin \left(\frac{1}{z+2}\right)$$

を $z=-2$ でローラン展開し、級数が収束する領域を示せ。次に、$z=-2$ における留数を求めよ。

Link to original

---

確率・統計

実数 $p$ は $0<p<1$ を満たすものとする。確率変数 $X$ と $Y$ は独立に同一の確率関数

$$f(k)=\{\begin{array}{ll}p& (k=1)\\ 1-p& (k=-1)\end{array}$$

に従うものとする。$Z=XY$ として、以下の各問に答えよ。

1. 期待値 $E[Z]$ を求めよ。
2. $X$ と $Z$ の共分散 $E[(X-E[X])(Z-E[Z])]$ を求めよ。
3. $X$ と $Z$ が独立となる $p$ を求めよ。求めた $p$ に対し、$Y$ と $Z$ も独立であることを示せ。
4. (3) で求めた $p$ に対し、確率 $Pr[X+Y+Z\le 2]$ を求めよ。

---

Link to original

---

选修

情報理論

問1

入力アルファベットと出力アルファベットがともに $\{1,2,3,4\}$ である無記憶な通信路 $W(y|x)$ の通信路行列が

$$\left(\begin{array}{cccc}0.5& 0.5& 0& 0\\ 0& 0.5& 0.5& 0\\ 0& 0& 0.5& 0.5\\ 0.5& 0& 0& 0.5\end{array}\right)$$

で与えられているとする。ただし、$(i,j)$ 成分は $W(j|i)$ を表す。この通信路の通信路容量を求めよ。また、それを達成する入力分布をすべて求めよ。

Link to original

問2

定常無記憶情報源 $X_1{X}_2\dots$ を考える。この情報源のアルファベットを有限集合 $\chi$ とし、各 $X_i$ は確率分布 $p(x)$ に従うものとする。任意に固定された $\epsilon >0$ に対し、系列 $(x_1,x_2,\dots ,x_n)\in {\chi }^n$ が

$$2^{-n(H(X_1)+\epsilon )}\le p(x_1,x_2,\dots ,x_n)\le 2^{-n(H(X_1)-\epsilon )}$$

を満たすとき、この系列を $p(x)$ に関する典型系列であると言う。ここで、$H(X_1)$ は $X_1$ のエントロピーを表し、$p(x_1,x_2,\dots ,x_n)$ は同時確率分布を表す。全ての典型系列からなる集合を $A_{\epsilon }^{(n)}$ と表記する。次の各問いに答えよ。ただし、$X=\{0,1\},p(0)=1-\alpha ,p(1)=\alpha$ とする。ここで $\alpha \in (0,1)$ は定数である。

1. $(x_1,x_2,\dots ,x_{10})=(0,1,1,0,0,0,0,1,0,0)$ に対し、$p(x_1,x_2,\dots ,x_{10})$ を求めよ。
2. $H(X_i)$ ($i=1,2,\dots ,n$) および $H(X_1,X_2,\dots ,X_n)$ を求めよ。
3. $x=(x_1,x_2,\dots ,x_n)$ に対し、$S(x)={\sum }_{i=1}^n{x}_i$ とおく。$\alpha =0.2,n=200,\epsilon =0.01$ とする。$A_{\epsilon }^{(n)}$ に属する系列 $x$ に対する $S(x)$ の範囲を求めよ。

Link to original

---

オートマトンと言語

問1

状態数2の決定性有限オートマトンを考える。決定性有限オートマトン $M=(K,\Sigma ,\delta ,q_0,F)$ において、$K=\{q_0,q_1\},\Sigma =\{a,b\},F=\{q_0\}$ とする。ただし、$K,\Sigma ,\delta ,q_0,F$ はそれぞれ $M$ の状態集合、アルファベット、遷移関数、初期状態、最終状態の集合を表し、$a$ と $b$ は文字である。なお $\delta (p,x)=r(p,r\in K,x\in \Sigma )$ は、$M$ が文字 $x$ を読むことで状態 $p$ から状態 $r$ に移ることを表す。$M$ によって受理される言語を $L(M)$ で表す。
$\Sigma$ 上の正規表現 $e(a,b)$ が表す言語を $\Vert e(a,b)\Vert$ で表す。次の各問いに答えよ。

\usepackage{tikz}
\usetikzlibrary{positioning}
 
\begin{document}
\begin{tikzpicture}[node distance=1cm and 1cm]
 
  % 子图1
  \node (A1)[double, circle, draw] {$q_0$};
  \node (B1)[circle, draw] [right=of A1] {$q_1$};
 
  \draw[->] (A1) to[loop above] node {a} ();
  \draw[->] (A1) to node[midway, above] {b} (B1);
  \draw[->] (B1) to[loop above] node {a/b} ();
 
  % 子图2
  \node (A2)[double, circle, draw] [right=of B1] {$q_0$};
  \node (B2)[circle, draw] [right=of A2] {$q_1$};
 
  \draw[->] (A2) to[loop above] node {a} ();
  \draw[->] (A2) to[bend left] node[above] {b} (B2);
  \draw[->] (B2) to[bend left] node[below] {b} (A2);
  \draw[->] (B2) to[loop above] node {a} ();
 
  % 子图3
  \node (A3)[double, circle, draw] [right=of B2] {$q_0$};
  \node (B3)[circle, draw] [right=of A3] {$q_1$};
 
  \draw[->] (A3) to[loop above] node {a} ();
  \draw[->] (A3) to[bend left] node[midway, above] {b} (B3);
  \draw[->] (B3) to[bend left] node[midway, below] {a} (A3);
  \draw[->] (B3) to[loop above] node {b} ();
 
  % 子图4
  \node (A4)[double, circle, draw] [right=of B3] {$q_0$};
  \node (B4)[circle, draw] [right=of A4] {$q_1$};
 
  \draw[->] (A4) to[loop above] node {a} ();
  \draw[->] (A4) to[bend left] node[midway, above] {b} (B4);
  \draw[->] (B4) to[bend left] node[midway, below] {a/b} (A4);
 
\end{tikzpicture}
\end{document}

図1: $\delta (q_0,a)=q_0,\delta (q_0,b)=q_1$ である4種類のオートマトン $M$

1. 図1は、$\delta (q_0,a)=q_0,\delta (q_0,b)=q_1$ である4種類の $\delta$ に対応する $M$ の状態遷移図である。図1の各 $M$ について $L(M)$ に含まれる文字列を説明せよ。
2. $\delta (q_0,a)=\delta (q_0,b)=q_1$ のとき、可能な $M$ の状態遷移図を図1にならってすべて与えよ。さらに、各 $M$ について $L(M)$ に含まれる文字列を説明せよ。
3. 言語 $L=\Vert e(a,b)\Vert$ について、$\Vert e(b,a)\Vert$ を $L$ の交換言語と呼ぶ。たとえば、$L_0$ が文字 $a$ を偶数個含む文字列から構成される言語であるとき、$L_0$ の交換言語は文字 $b$ を偶数個含む文字列から構成される言語である。(1) と (2) とは異なる $\delta$ に対応する各 $M$ に対し、(1) あるいは (2) の言語の交換言語とならない $L(M)$ に含まれる文字列を説明せよ。

Link to original

問2

文脈自由文法を4つ組 $(N,\Sigma ,P,S)$ で表す。ただし、$N,\Sigma ,P,S$ をそれぞれ非終端記号の集合、終端記号の集合、生成規則の集合、開始記号とする。$\Sigma$ 上の文字列 $w$ と終端記号 $x\in \Sigma$ に対して、$|w{|}_x$ を $w$ 中の $x$ の出現回数とする。以下の各問いに答えよ。

(A) 以下に示す言語 $L_i(i=1,2,3)$ を導出する文脈自由文法 $(N_i,{\Sigma }_i,P_i,S)$ の生成規則の集合 $P_i$ を与えよ。

1. $L_1=\{w\in \{a,b{\}}^{\ast }||w{|}_a\ge 3\}$。ただし ${\Sigma }_1=\{a,b\}$ である。答えには $N_1=\{S,X\}$ を用いよ。
2. $L_2=\{w\in \{a,b{\}}^{\ast }||w{|}_a\ge 2|w{|}_b\}$。ただし ${\Sigma }_2=\{a,b\}$ である。答えには $N_2=\{S\}$ を用いよ。
3. $L_3=\{a^i{b}^j{c}^k|i,j,k\ge 0かつ(2i=jまたは3j=k)\}$。ただし ${\Sigma }_3=\{a,b,c\}$ である。答えには $N_3=\{S,V,X,Y,Z\}$ を用いよ。

(B) 以下に示す言語 $L_4,L_5$ は文脈自由言語であるか否か。証明せよ。

4. $L_4=\varnothing$。
5. 有限個の有限長文字列から構成される空でない任意の言語 $L_5$。

Link to original