R06ist

数学

線形代数 (Linear Algebra)

1. 実数行列 $A\in {\mathbb{R}}^{m\times n}$ および実数ベクトル $b\in {\mathbb{R}}^m$ に対して、集合を以下のように定義する： $$S=\{x\in {\mathbb{R}}^n\mid Ax=b\},f(x)=Ax$$ 次の事実を証明なく用いてよい。
   • ベクトル空間 $V$ の部分空間 $W\subseteq V$ である条件は次の通りである：
     • $C1:0\in W$
     • $C2:u,v\in W⟹u+v\in W$
     • $C3:u\in W,c\in \mathbb{R}⟹cu\in W$
       以下に答えよ：
   1. $A=\left[\begin{array}{cccc}2& 0& 2& 0\\ 0& 8& 24& 24\\ 0& 2& 6& 6\end{array}\right]$ の場合、写像 $f$ のカーネル $\mathrm{Ker}(f)$ の次元と基底を求めよ。
   2. 一般的に $\mathrm{Ker}(f)$ が ${\mathbb{R}}^n$ の部分空間であることを示せ。
   3. $S\subseteq {\mathbb{R}}^n$ が部分空間の場合、$b=0$ を示せ。
   4. $S\subseteq {\mathbb{R}}^n$ が部分空0不8間かつ $A$ が正方行列の場合、$A$ が可逆なら $S=\{0\}$ を示せ。

---

Link to original

---

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

1. 次の積分を計算せよ：

   $$I={\int }_0^{\infty }{x}^5\exp (-x^4)dx$$

   ただし、以下を証明なく用いてよい：

   $${\int }_{-\infty }^{\infty }\exp (-x^2)dx=\sqrt{\pi }$$

2. 次の微分方程式の一般解を求めよ：

   $$\frac{dy}{dx}+y=x\sinh (x)$$

3. 複素関数 $f(z)=\frac{1}{z^4+1}$ を考える。以下に答えよ：

   1. $f(z)$ の極を全て求めよ。
   2. $C$ を図示した半円とし、$R>1$ の場合、複素積分 ${\int }_{C}f(z)dz$ を計算せよ。

4. 积分の計算
   次の積分を計算する：

   $$I={\int }_0^{\infty }{x}^5\exp (-x^4)dx$$

---

Link to original

---

ベクトル解析

直交座標系において，$x$，$y$軸方向の単位ベクトルをそれぞれ $\mathbf{i}$，$\mathbf{j}$ とする．次の (1)，(2) で示すベクトル場 $\mathbf{F}$ と経路 $C$ について，線積分

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

をそれぞれ求めよ．

1. ベクトル場

$$\mathbf{F}=(2x{y}^3-y)\mathbf{i}+(3x^2{y}^2-x)\mathbf{j}$$

とし，経路 $C$ を曲線

$$y^3+x^2-2xy=1$$

上で，始点 $(-13,-4)$ から終点 $(5,-4)$ までの部分とする．

2. ベクトル場

$$\mathbf{F}=(3e^{2x}+4y)\mathbf{i}+(x+7y{e}^y)\mathbf{j}$$

とする．経路 $C$ は，点 $P(0,0)$，$Q(2,2)$，$R(4,6)$，$S(1,3)$ を頂点とする四辺形であり，$P\to Q\to R\to S\to P$ の向きに一周するものとする．

---

Link to original

---

確率・統計

1. 箱の中に $N_1$ 個の白球と $N_2$ 個の黒球があり、総数は $N=N_1+N_2$ である。箱からランダムに 2 個の球を取り出すとき、両方が白球である確率が $1/2$ であることが分かっている。
   1. $N_2$ が奇数の場合、$N_1$ の最小値を求めよ。
   2. $N_2$ が偶数の場合、$N_1$ の最小値を求めよ。
   3. $N$ の最小値を 3 通り求めよ。

Link to original

---

情報理論 (Information Theory)

【問1】

アルファベット $\{s_1,s_2,s_3,s_4,s_5,s_6\}$ 上の無記憶情報源 $S$ の符号化に関して，以下の問いに答えよ。ただし，符号語アルファベットを $\{0,1\}$ とする。

1. 無記憶情報源 $S$ に関して，各符号語長を $3,3,3,2,2,2$ とする符号が瞬時に復号可能になり得るかどうかを述べよ。なり得る場合，瞬時に復号可能な符号の一例を示せ。
2. 無記憶情報源 $S$ に関して，各符号語長を $3,3,3,3,2,2$ とする符号が瞬時に復号可能になり得るかどうかを述べよ。なり得る場合，瞬時に復号可能な符号の一例を示せ。
   以後の問いにおいて， 無記憶情報源 S に関して，その確率分布が

$$P(s_1)=0.18,P(s_2)=0.2,P(s_3)=0.3,P(s_4)=0.13,P(s_5)=0.11,P(s_6)=0.08$$

であるとする．次の問いに 答えよ
3. 無記憶情報源 $S$ に関して，その確率分布が以下のように与えられるとする：
ハフマン符号化により符号化せよ。
4. ハフマン符号化により得られた符号の平均符号長を求めよ。

Link to original

---

【問2】

アルファベット $X=\{1,2,3\}$ 上の確率分布 $p_1$ と $p_2$ を以下のように定める：

$$p_1(1)=1,p_1(2)=0,p_1(3)=0,p_2(1)=0,p_2(2)=b,p_2(3)=1-b$$

ただし，$b\in (0,1)$ を定数とする。$p_1$ と $p_2$ の重み付き平均で表される確率分布 $q$ のうち，$X$ 上の一様分布 $u$ とのKullback-Leiblerダイバージェンス

$$D(u||q)=\sum _{x\in X}u(x)\log \frac{u(x)}{q(x)}$$

が最小となるものを求めよ。

---

Link to original

---

オートマトンと言語

問1

アルファベット $\Sigma =\{a,d\}$ 上の言語 $L$ を以下のように定義する：
$L=\{w\in {\Sigma }^{\ast }\mid w\in \{xad,xadd,xdad\}\text{ for some }x\in {\Sigma }^{\ast }\}$以下の図は $L$ を受理する非決定性有限オートマトン $M=(K,\Sigma ,\delta ,q_0,F)$ の状態遷移図である。ただし

• $K=\{q_0,q_1,\dots ,q_8\}$
• $\Sigma =\{a,d\}$
• $\delta$
• $q_0$
• $F=\{q_2,q_5,q_8\}$
  は、それぞれ $M$ の状態の集合、アルファベット、遷移関数、初期状態、受理状態の集合を表す。次の各問いに答えよ：

\usepackage{tikz}
\usetikzlibrary{positioning}
 
\begin{document}
\begin{tikzpicture}[node distance=1cm and 1cm]
 
% Nodes
  \node (q0) [circle, draw] {$q_0$};
  \node (q1) [circle, draw, above right=of q0] {$q_1$}; % q1在右上角
  \node (q3) [circle, draw, right=of q0] {$q_3$};       % q3在正右方
  \node (q6) [circle, draw, below right=of q0] {$q_6$}; % q6在右下角
 
  \node (q2) [circle, draw, double, right=of q1] {$q_2$};
  \node (q4) [circle, draw, right=of q3] {$q_4$};
  \node (q5) [circle, draw, double, right=of q4] {$q_5$};
  \node (q7) [circle, draw, right=of q6] {$q_7$};
  \node (q8) [circle, draw, double, right=of q7] {$q_8$};
 
  % Edges
  \draw[->] (-0.5, 0) -- (q0);% Start state arrow
  \draw[->] (q0) to[loop above] node {a, d} ();
  \draw[->] (q0) to node[midway, above left] {a} (q1);
  \draw[->] (q0) to node[midway, above] {a} (q3);
  \draw[->] (q0) to node[midway, below left] {d} (q6);
  \draw[->] (q1) to node[midway, above] {d} (q2);
  \draw[->] (q3) to node[midway, above] {d} (q4);
  \draw[->] (q4) to node[midway, above] {d} (q5);
  \draw[->] (q6) to node[midway, above] {a} (q7);
  \draw[->] (q7) to node[midway, above] {d} (q8);
 
\end{tikzpicture}
\end{document}

1. $L$ を受理する状態数4の非決定性有限オートマトンの状態遷移図を示せ。
2. $L$ を表す正規表現を示せ。
3. $L$ を受理する状態数4の決定性有限オートマトンの状態遷移図を示せ。
4. $L$ を受理する決定性有限オートマトンの状態数は必ず4以上であることを証明せよ。

Link to original

---

R06-C-問2

問2

アルファベット $\Sigma =\{\to ,\leftarrow ,\uparrow ,\downarrow \}$ 上の文字列 $a=a[1]a[2]\cdots a[n]$（各 $i$ に対し $a[i]\in \Sigma$）に対し、2次元ベクトルの系列 $f(a)=(p[0],p[1],\dots ,p[n])$（各 $i$ に対し $p[i]=(x[i],y[i])$, $x[i],y[i]$ は整数）を次のように定義する：

$$p[i]=\{\begin{array}{ll}p[i-1]+(1,0)& \text{if }a[i]=\to \\ p[i-1]-(1,0)& \text{if }a[i]=\leftarrow \\ p[i-1]+(0,1)& \text{if }a[i]=\uparrow \\ p[i-1]-(0,1)& \text{if }a[i]=\downarrow \end{array}$$

すなわち、$f(a)$ は、原点からスタートして $a$ の矢印の向きに従って2次元格子点上を遷移したときの軌跡を表す。
また、各 $i=1,2,\dots ,n$ に対し、$|x[i]|+|y[i]|>|x[i-1]|+|y[i-1]|$ のとき（$a[i]$ によって原点から遠ざかる方向に遷移したとき） $i$ を前進ステップ、そうでないとき（$a[i]$ によって原点に近づく方向に遷移したとき） $i$ を後進ステップと呼ぶ。

文字列 $a$ が往復的であることを、任意の後進ステップ $i$ に対し、

$$i_0=\max \{j\mid j\le i-1,p[j]=p[i-1],j\text{ は前進ステップ}\}$$

が存在し、$p[i]=p[i_0-1]$ が成り立つことと定義する。すなわち，往復的な文字列 $a$ に おいては，後進ステップ i による $p[i-1]$ から $p[i]$ への遷移は，i に対応する前進ステッ プ $i_0$ による $p[i_0-1]$ から $p[i_0]$ への遷移を逆にたどるものとなっている．往復的で $f(a)$ の最後の要素が原点であるような文字列 a からなる言語

言語 $L$ を以下のように定義する：

$$L=\bigcup _{n\ge 0}\{a\in {\Sigma }^n\mid a\text{ は往復的},p=f(a),p[n]=(0,0)\}.$$

について，次の各問いに答えよ.

1. 以下の文字列 $a_1,a_2,a_3,a_4$ が $L$ の要素であるか否かをそれぞれ判定せよ。
   • $a_1=\uparrow \uparrow \downarrow \to \downarrow \uparrow \leftarrow \downarrow$
   • $a_2=\to \to \leftarrow \leftarrow \leftarrow \uparrow \downarrow \to$
   • $a_3=\downarrow \leftarrow \uparrow \to$
   • $a_4=\leftarrow \uparrow \uparrow \downarrow \leftarrow \to \downarrow \leftarrow \downarrow \uparrow$
2. 次の図は、アルファベットを $\{\to ,\leftarrow \}$ に限定した言語 $L\cap \{\to ,\leftarrow {\}}^{\ast }$ を最終状態によって受理するプッシュダウンオートマトン（PDA）の状態遷移図の一部である。空欄 ①, ②, ③ を埋めよ。（2か所の ③ には同じものが入る。）

\usepackage{tikz}
\begin{document}
\begin{tikzpicture}[->, shorten >=1pt, auto, semithick]
  % 定义状态节点
  \node[circle, draw] (s_) at (-2, 0) {$S_-$};
  \node[double,circle, draw] (s0) at (0, 0) {$S_0$};
  \node[circle, draw] (s+) at (2, 0) {$S_+$};
 
  % 定义状态转移
\path 
(s_) 
edge[loop left] node[left] {
	$\leftarrow, \leftarrow /\leftarrow\leftarrow$,\\
	$\rightarrow,\leftarrow /\epsilon$} ()
edge[bend right] node[below] {3} (s0)
(s0) 
edge[bend right] node[above] {${1}$} (s_)
edge[bend left] node[above] {$\rightarrow, Z / \rightarrow Z$} (s+)
(s+) 
edge[loop right] node[above] {${2}$} ()
edge[bend left] node[below] {${3}$} (s0);
 
\draw[->] (-0.5, -0.5) -- (s0);
 
\end{tikzpicture}
\end{document}

遷移規則 $a,b/s$ は，遷移元の状態で読んだ入力文字が $a$，スタックの先頭文字が $b$ のとき，遷移先の状態に遷移し，スタックの先頭を文字 $b$ から文字列 $s$ に置き換える動作を表す．ただし，$ϵ$ は空文字列を表す．初期状態では，スタックは，空であることを表す特殊文字 $Z$ のみを保持しているとする．$S_0$ は初期状態であり唯一の最終状態でもある．
ヒント：状態 $S_0$，$S_{+}$，$S_{-}$ は，それぞれ，$x[i]=0$，$x[i]>0$，$x[i]<0$ であることを表す

3. 次の図は、言語 $L$ を最終状態で受理するPDAの状態遷移図の一部である。ただし、②と③は、(2)で求めたものと同じである。④と⑤を埋めよ。

\usepackage{tikz}
\begin{document}
\begin{tikzpicture}[->, shorten >=1pt, auto, semithick]
  % 定义状态节点
  \node[double, circle, draw] (s0) at (-2, -2) {$S_0$};
  \node[circle, draw] (s0plus) at (-2, 2) {$S_{0+}$};
  \node[circle, draw] (splusplus) at (2, 2) {$S_{++}$};
  \node[circle, draw] (splus0) at (2, -2) {$S_{+0}$};
 
  % 定义状态转移
  \path 
  % S0+ 到其他节点
  (s0plus) edge[bend left] node[above] {$\to, \uparrow / \to Y \uparrow$} (splusplus)
           edge[bend left] node[right] {3} (s0)
           edge[loop above] node {4} (s0plus)
  % S++ 到其他节点
  (splusplus) edge[bend left] node {$\epsilon, Y / \epsilon$} (s0plus)
              edge[bend left] node[right] {$\epsilon, X / \epsilon$} (splus0)
              edge[loop right] node[right] {5} (splusplus)
  % S+0 到其他节点
  (splus0) edge[bend left] node {3} (s0)
           edge[bend left] node {$\uparrow, \to / \uparrow X \to$} (splusplus)
           edge[loop right] node[right] {2} (splus0)
  % S0 到其他节点
  (s0) edge[bend left] node {$\uparrow, Z / \uparrow Z$} (s0plus)
       edge[bend left] node {$\epsilon, Z / \to Z$} (splus0);
 
\draw[->] (-3, -3) -- (s0);
\end{tikzpicture}
\end{document}

ヒント：このPDAは、$x[i]$ と $y[i]$ の全ての符号の組に対応する9個の状態を持つ。このうち、$x[i]=y[i]=0$ を表す状態 $S_0$（初期状態であり唯一の最終状態でもある）、$x[i]=0,y[i]>0$ を表す状態 $S_{0+}$、$x[i]>0,y[i]=0$ を表す状態 $S_{+0}$、$x[i]>0,y[i]>0$ を表す状態 $S_{++}$ の4つの状態間の状態遷移図のみ示してある。

Link to original