R04ist

数学

線形代数

n次元ユークリッド空間上の $n+1$ 個の点 $p_1,p_2,\dots ,p_{n+1}\in {\mathbb{R}}^n$ に対し, 2点 $p_i,p_j$ 間のユークリッド距離を $d_{i,j}=\Vert p_i-p_j\Vert$ で表す．ただし, 各 $p_i$ は列ベクトルである．また, $g_{i,j}=d_{i,n+1}^2+d_{j,n+1}^2-d_{i,j}^2(1\le i,j\le n)$ を添字順に並べて得られる行列を $G=(g_{i,j})\in {\mathbb{R}}^{n\times n}$ とする．このとき以下の各問いに答えよ.

1. $n=2$ とする．以下の2つの場合に対して, 等式条件を満たす3個の点 $p_1,p_2,p_3\in {\mathbb{R}}^2$ の組をそれぞれ1つ求めよ.

   • (a) $(d_{1,2},d_{1,3},d_{2,3})=(1,1,1)$
   • (b) $(d_{1,2},d_{1,3},d_{2,3})=(1,2,3)$

2. $x_j=p_j-p_{n+1}(1\le j\le n)$ とし, $x_j$ を添字順に並べて得られる行列を $X=(x_j)\in {\mathbb{R}}^{n\times n}$ とする．(1) で求めた答えに対し, $X^{\top }X$ をそれぞれ計算せよ.

3. 一般に $G$ が半正定値であることを示せ．ただし, $n\times n$ 実対称行列 $A\in {\mathbb{R}}^{n\times n}$ が半正定値であるとは, 任意のベクトル $v\in {\mathbb{R}}^n$ に対して $v^{\top }Av\ge 0$ が成り立つことをいう.

Link to original

---

解析学・微積分

1. $R^m$ 上で微分可能な実数値関数 $f(x)(x=(x_1,x_2,\dots ,x_m))$ について, $x_i=v_i(t)(i=1,2,\dots ,m)$ とおく．ただし, 各 $v_i$ は $R$ 上で微分可能な関数とする．次の各問いに答えよ.
   • (a) $\frac{df}{dt}$ を $\frac{\partial f}{\partial x_i}$ と $\frac{d{v}_i}{dt}(i=1,2,\dots ,m)$ で表せ.
   • (b) $m=2,f(x)=x_1^2+x_1{x}_2+2x_2^2,v_1(t)=\sin t,v_2(t)=e^t$ のとき, $\frac{df}{dt}$ を求めよ.
2. 次の微分方程式の一般解を求めよ. $\frac{dy}{dx}-2xy=e^{x^2}$
3. 閉曲線 $C$ に沿った複素積分 ${\oint }_C\frac{\cos z}{(2z-\pi {)}^3}dz$
   を求めよ．ただし, $C$ は円 $|z|=2$ とする.

---

Link to original

---

ベクトル解析

直交座標系において, $x$, $y$, $z$ 軸方向の単位ベクトルをそれぞれ $\mathbf{i}$, $\mathbf{j}$, $\mathbf{k}$ とする．ベクトル場 $\mathbf{F}$ を

$$\mathbf{F}=x\mathbf{i}+2y\mathbf{j}+10z\mathbf{k}$$

とする．次の面 $S_1,S_2$ および $S_3$ に対する面積分を計算せよ.

1. $S_1$ を円筒面 $x^2+z^2=1(0\le y\le 4)$ とする (上面と底面の無い円筒の表面) ．円筒外向き法線ベクトルを用いよ.
2. $S_2$ を円筒面の一部 $x^2+z^2=1(0\le y\le 4,0\le z)$ と長方形面 $z=0(-1\le x\le 1,0\le y\le 4)$ からなる半円筒面とする (上面と底面の無い半円筒の表面) ．半円筒外向き法線ベクトルを用いよ.
3. $S_3$ を円筒面 $x^2+z^2=1$ と, 平面 $z=0,y=0,x+y=4$ で囲まれた領域の境界とする．外向き法線ベクトルを用いよ.

Link to original

---

確率・統計

2以上の自然数 $n$ に対して, $P=(P_1,\dots ,P_n)$ は一様ランダムに選ばれた $\{1,\dots ,n\}$ の順列とする．任意の自然数 $i,j(1\le i<j\le n)$ に対して,

$$X_{ij}=\{\begin{array}{ll}1& (P_i>P_j\text{の場合})\\ 0& (\text{それ以外})\end{array}$$

また, $Y_i={\sum }_{j=i+1}^n{X}_{ij}(1\le i\le n-1)$ とし, $Z={\sum }_{i=1}^{n-1}{Y}_i$ とする．以下の各問いに答えよ.

1. $Z$ の期待値 $E[Z]$ を求めよ.
2. $i(1\le i\le n-2)$ と $k(0\le k\le n-i)$ に対して, $Y_{n-1}=l(l\in \{0,1\})$ の条件の下で $Y_i=k$ となる条件付確率 $P[Y_i=k|Y_{n-1}=l]$ を求めよ.
3. $Z$ の分散 $\mathrm{Var}[Z]$ を求めよ. ただし,

$$\sum _{k=1}^n{k}^2=\frac{1}{6}n(n+1)(2n+1)$$

を用いて良い.

---

Link to original

---

选修

情報理論

問1

$k$ を正の整数とする．入力アルファベットが $X=\{0,1{\}}^k$, 出力アルファベットが $Y=\{0,1{\}}^k$ の無記憶な通信路 $W(Y|X)$ を

$$W(Y|X)=\{\begin{array}{ll}0& (d(X,Y)=0)\\ \frac{1}{k}& (d(X,Y)=1)\\ 0& (d(X,Y)\ge 2)\end{array}$$

で定める．ただし, $d(X,Y)$ は, $X=(X_1,X_2,\dots ,X_k)$ と $Y=(Y_1,Y_2,\dots ,Y_k)$ の間のハミング距離

$$d(X,Y)=\sum _{i=1}^k|X_i-Y_i|$$

を表す．この通信路の通信路容量を求めよ．

Link to original

---

問2

アルファベットが $\{1,2,3,4\}$ である単純マルコフ情報源の遷移確率行列が

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

で与えられたとする．ここで, $(i,j)$ 成分は遷移確率 $P(j|i)$ を表し, $0<\gamma <1$ とする．以下の問いに答えよ:

1. このマルコフ情報源の状態遷移図を図示せよ．
2. このマルコフ情報源の定常確率分布が $(1/8,1/4,1/8,1/2)$ であるとき, $\gamma$ の値を求めよ．
3. (2) が前問で求めた値となるとき、このマルコフ情報源のエントロピー率を求めよ．
4. このマルコフ情報源に従う確率変数の列 $X_1,X_2,\dots$ を考える．$X_i$ が上述の定常確率分布 $(1/8,1/4,1/8,1/2)$ に従う場合, $(X_1,X_2)$ に対するハフマン符号化を行い, 符号的表示图を示せ．ただし符号語のアルファベットは $\{0,1\}$ とする．

Link to original

---

オートマトンと言語

問1

以下の状態遷移図を持つ決定性有限オートマトンを $M=(K,\Sigma ,\delta ,q_0,F)$ とする.

• $K=\{q_0,q_1,\dots ,q_6\}$, 状態集合
• $\Sigma =\{0\}$,
• $\delta :K\times \Sigma \to K$は遷移関数
• $q_0$ は初期状態,
• $F=\{q_2\}$ は最終状態集合.

\usepackage{tikz}
 
\begin{document}
\begin{tikzpicture}[->, shorten >=1pt, auto, node distance=1.5cm, thick]
 
  % Define the states
  \node (q2) at (180:1.5cm) [circle, draw, double] {$q_2$}; % q2 at 180° (leftmost point)
 
  % Define the pentagon nodes using polar coordinates around q2
  \foreach \i in {1, 2, 3, 4} {
    \node (q\the\numexpr\i+2\relax) at ({180 - 72*\i}:1.5cm) [circle, draw] {$q_{\the\numexpr\i+2\relax}$};
  }
  \node (q1) [circle, draw, left of=q2] {$q_1$};
  \node (q0) [circle, draw, left of=q1] {$q_0$};
 
  % Draw the transitions
  \path (q0) edge node {0} (q1)
        (q1) edge node {0} (q2)
        (q2) edge node {0} (q3)
        (q3) edge node {0} (q4)
        (q4) edge node {0} (q5)
        (q5) edge node {0} (q6)
        (q6) edge node {0} (q2);
 
  % Start state arrow
  \draw[->] (-5.5, -1) -- (q0);
 
\end{tikzpicture}
\end{document}

このオートマトン $M$ に基づいて、決定性有限オートマトン $\tilde{M}=(\tilde{K},\tilde{\Sigma },\tilde{\delta },\widetilde{q_0},\tilde{F})$ を、
$\tilde{K}=K\times K,\tilde{\Sigma }=\{0,1\},\widetilde{q_0}=(q_0,q_0),\tilde{F}=\{(q_2,q_2)\},$

\begin{cases} (\delta(q, 0), \delta(q', 0)) & a = 0 のとき, \\ (\delta(q, 0), \delta(q', 0)) & a = 1 のとき \end{cases}$$ と定義する。入力文字列 $10$ に対するオートマトン $\tilde{M}$ の状態系列は $$(q_0, q_0) \to (q_1, q_2) \to (q_2, q_3),$$ 遷移先状態はその最後の状態 $(q_2, q_3)$ であることに注意せよ。以下の各問いに答えよ。 1. 入力文字列 $01101$ に対するオートマトン $\tilde{M}$ の状態系列を記せ。 2. $n (≥ 1)$ が $5$ の倍数のとき、入力文字列 $1^n$ に対するオートマトン $\tilde{M}$ の遷移先状態が $(q_5, q_5)$ となることを示せ。 3. 長さ $2$ 以上の入力文字列 $w ∈ \{0, 1\}^*$ に対するオートマトン $\tilde{M}$ の遷移先状態を $(q_{iw}, q_{jw})$ とする。$iw, jw ∈ \{2, 3, 4, 5, 6\}$ を、$\#_0(w), \#_1(w)$ を用いた式で表せ。ただし、$\#_a(w)$ は文字列 $w$ に現れる文字 $a$ の個数を表す。 4. オートマトン $\tilde{M}$ が受理する言語は以下であることを示せ。ただし、$x \mod y$ は $x$ を $y$ で割ったときの余りを表す。

{w \in {0, 1}^* | #_0(w) \mod 5 = 2, #_1(w) \mod 5 = 0}

### 中文翻译 定义以下状态转移图的确定性有限自动机 $M = (K, \Sigma, \delta, q_0, F)$： - $K = \{q_0, q_1, \dots, q_6\}$，状态集合 - $\Sigma = \{0\}$，输入字母表 - $\delta: K \times \Sigma \to K$ 为状态转移函数 - $q_0$ 是初始状态 - $F = \{q_2\}$ 是终态集合 ```tikz \usepackage{tikz} \begin{document} \begin{tikzpicture}[->, shorten >=1pt, auto, node distance=1.5cm, thick] % Define the states \node (q2) at (180:1.5cm) [circle, draw, double] {$q_2$}; % q2 at 180° (leftmost point) % Define the pentagon nodes using polar coordinates around q2 \foreach \i in {1, 2, 3, 4} { \node (q\the\numexpr\i+2\relax) at ({180 - 72*\i}:1.5cm) [circle, draw] {$q_{\the\numexpr\i+2\relax}$}; } \node (q1) [circle, draw, left of=q2] {$q_1$}; \node (q0) [circle, draw, left of=q1] {$q_0$}; % Draw the transitions \path (q0) edge node {0} (q1) (q1) edge node {0} (q2) (q2) edge node {0} (q3) (q3) edge node {0} (q4) (q4) edge node {0} (q5) (q5) edge node {0} (q6) (q6) edge node {0} (q2); % Start state arrow \draw[->] (-5.5, -1) -- (q0); \end{tikzpicture} \end{document} ``` 基于此自动机 $M$，定义确定性有限自动机 $\tilde{M} = (\tilde{K}, \tilde{\Sigma}, \tilde{\delta}, \tilde{q_0}, \tilde{F})$，如下： $$\tilde{K} = K \times K, \ \tilde{\Sigma} = \{0, 1\}, \ \tilde{q_0} = (q_0, q_0), \ \tilde{F} = \{(q_2, q_2)\},$$ $$\tilde{\delta}((q, q'), a) = \begin{cases} (\delta(q, 0), \delta(q', 0)) & a = 0 \text{ 时}, \\ (\delta(q, 0), \delta(q', 0)) & a = 1 \text{ 时} \end{cases}$$ 对于输入字符串 $10$，自动机 $\tilde{M}$ 的状态序列为： $$(q_0, q_0) \to (q_1, q_2) \to (q_2, q_3),$$ 最终状态为 $(q_2, q_3)$。回答以下问题： 1. 给出输入字符串 $01101$ 在自动机 $\tilde{M}$ 上的状态序列。 2. 证明当 $n (≥ 1)$ 是 $5$ 的倍数时，输入字符串 $1^n$ 在自动机 $\tilde{M}$ 上的最终状态为 $(q_5, q_5)$。 3. 对于长度 $≥ 2$ 的字符串 $w ∈ \{0, 1\}^*$，自动机 $\tilde{M}$ 的最终状态记为 $(q_{iw}, q_{jw})$，其中 $iw, jw ∈ \{2, 3, 4, 5, 6\}$。请用字符串 $w$ 中 $0$ 和 $1$ 的个数（即 $\#_0(w)$ 和 $\#_1(w)$）表示 $iw$ 和 $jw$。 4. 证明自动机 $\tilde{M}$ 接受的语言是：

{w \in {0, 1}^* | #_0(w) \mod 5 = 2, #_1(w) \mod 5 = 0}

其中 $x \mod y$ 表示 $x$ 除以 $y$ 的余数。 --- # o1 **先にことわり** 題意をよく読むと，「入力が $\texttt{0}$ のときは元のオートマトン $M$ の“1ステップ”遷移を両座標ともに踏む」「入力が $\texttt{1}$ のときは，第一座標は“1ステップ”，第二座標は“2ステップ”進む」という形になっていることが分かります。実際，問題文にある > 入力文字列 $\texttt{10}$ に対する状態遷移が > $$ > (q_0,q_0)\;\xrightarrow{\;\texttt{1}\;}\;(q_1,q_2)\;\xrightarrow{\;\texttt{0}\;}\;(q_2,q_3) > $$ という例がその証拠です。もし「$\texttt{1}$ を読むと両座標ともに “同じステップ” 進む」という定義であれば，第一座標・第二座標が異なる状態に分かれるはずがありません。ところが実際は - 第一座標は「1 ステップ進む」($q_0 \to q_1$) - 第二座標は「2 ステップ進む」($q_0 \to q_1 \to q_2$) という動きをしているからこそ，$(q_0,q_0) \xrightarrow{\texttt{1}} (q_1,q_2)$ になっています。 同様に，$\texttt{0}$ を読むと「両座標とも 1 ステップ進む」動きになります。元のオートマトン $M$ では

q_0 \xrightarrow{0} q_1 \xrightarrow{0} q_2 \xrightarrow{0} q_3 \xrightarrow{0} q_4 \xrightarrow{0} q_5 \xrightarrow{0} q_6 \xrightarrow{0} q_2 \xrightarrow{0}\dots

という 1 ステップ遷移のサイクルがあり，$q_2 \to q_3 \to q_4 \to q_5 \to q_6 \to q_2$ の部分は「長さ 5 のループ」を形成しています。 --- ## 1. 入力文字列 $\texttt{01101}$ に対する状態系列 与えられた規則 - $\texttt{0}$ を読む $\;\to\;) $\bigl(\delta(q,0),\,\delta(q',0)\bigr)$ - すなわち「両座標とも1ステップ進む」 - $\texttt{1}$ を読む $\;\to\;) $\bigl(\delta(q,0),\,\delta(\delta(q',0),0)\bigr)$ - すなわち「第一座標は1ステップ，第二座標は2ステップ進む」 という解釈で，$\tilde{M}$ 上の状態遷移を追うと次のようになります。入力 $\texttt{01101}$ は左から順に $\texttt{0}$, $\texttt{1}$, $\texttt{1}$, $\texttt{0}$, $\texttt{1}$ の 5 文字です。 1. 初期状態は $(q_0,q_0)$。 2. **$\texttt{0}$ を読む** - 第一座標: $q_0 \xrightarrow{0} q_1$ - 第二座標: $q_0 \xrightarrow{0} q_1$ - よって $(q_0,q_0)\xrightarrow{\texttt{0}}(q_1,q_1)$ 3. **$\texttt{1}$ を読む** - 第一座標: 1ステップ $q_1 \xrightarrow{0} q_2$ - 第二座標: 2ステップ $q_1 \xrightarrow{0} q_2 \xrightarrow{0} q_3$ - よって $(q_1,q_1)\xrightarrow{\texttt{1}}(q_2,q_3)$ 4. **$\texttt{1}$ を読む** - 第一座標: 1ステップ $q_2 \xrightarrow{0} q_3$ - 第二座標: 2ステップ $q_3 \xrightarrow{0} q_4 \xrightarrow{0} q_5$ - ただし元のオートマトンで $q_3 \xrightarrow{0} q_4$, $q_4 \xrightarrow{0} q_5$ - よって $(q_2,q_3)\xrightarrow{\texttt{1}}(q_3,q_5)$ 5. **$\texttt{0}$ を読む** - 第一座標: $q_3 \xrightarrow{0} q_4$ - 第二座標: $q_5 \xrightarrow{0} q_6$ - よって $(q_3,q_5)\xrightarrow{\texttt{0}}(q_4,q_6)$ 6. **$\texttt{1}$ を読む** - 第一座標: 1ステップ $q_4 \xrightarrow{0} q_5$ - 第二座標: 2ステップ $q_6 \xrightarrow{0} q_2 \xrightarrow{0} q_3$ - ループ部 $q_6 \to q_2 \to q_3$ - よって $(q_4,q_6)\xrightarrow{\texttt{1}}(q_5,q_3)$ 以上から，$\texttt{01101}$ に対する状態系列は

(q_0,q_0)
;\xrightarrow{\texttt{0}};
(q_1,q_1)
;\xrightarrow{\texttt{1}};
(q_2,q_3)
;\xrightarrow{\texttt{1}};
(q_3,q_5)
;\xrightarrow{\texttt{0}};
(q_4,q_6)
;\xrightarrow{\texttt{1}};
(q_5,q_3)

となります。最終状態は $(q_5,q_3)$ です。 --- 以下，ほかの設問にも関連してざっくりポイントを述べておくと： - **問2:** 「$n$ が 5 の倍数のとき，$1^n$ を読むと $(q_5,q_5)$ に行き着く」 は，上述のように「$\texttt{1}$ を読むたびに，第一座標は“1ステップ前進”，第二座標は“2ステップ前進”」だからこそ，それぞれ

\text{第一座標は }n\text{ ステップ前進},\quad
\text{第二座標は }2n\text{ ステップ前進}

となります。元のオートマトン $M$ の状態遷移が

q_0 \xrightarrow{0} q_1 \xrightarrow{0} q_2 
   \;\xrightarrow{0} q_3 \xrightarrow{0} q_4 
   \xrightarrow{0} q_5 \xrightarrow{0} q_6 
   \xrightarrow{0} q_2 \xrightarrow{0}\dots

という「$q_2$ を基点に長さ 5 のループ」をもつことと，$n$ が 5 の倍数という条件を組み合わせると，初期状態 $q_0$ から丁度 $q_5$ に到達する形でうまく説明できます。 - **問3, 4:** 結局，$\tilde{M}$ が最終的に $(q_2,q_2)$ へ到達するための条件は 1. 第一座標 $\to q_2$: これは「$(\#_0(w)+\#_1(w)) \mod 5 = 2$」 2. 第二座標 $\to q_2$: これは「$(\#_0(w)+2\,\#_1(w)) \mod 5 = 2$」 となります。両方合わせると

 \#_0(w) \equiv 2 \pmod{5},
 \quad
 \#_1(w) \equiv 0 \pmod{5}

が成立することが分かり，$\tilde{M}$ の受理言語が

\{\,w \in \{0,1\}^* \mid \#_0(w) \bmod 5 = 2,\;\#_1(w)\bmod 5 = 0\}

であることが示されます。 以上が，まずは問1（入力 $\texttt{01101}$ に対する状態系列）の要点です。 --- # DeepSeek **1. 给出输入字符串 $01101$ 在自动机 $\tilde{M}$ 上的状态序列。** 根据自动机 $\tilde{M}$ 的转移函数定义，无论输入是 0 还是 1，状态转移都按照输入 0 来进行。因此，输入字符串 $01101$ 的状态序列为：

(q_0, q_0) \to (q_1, q_1) \to (q_2, q_2) \to (q_3, q_3) \to (q_4, q_4) \to (q_5, q_5)

**2. 证明当 $n (≥ 1)$ 是 $5$ 的倍数时，输入字符串 $1^n$ 在自动机 $\tilde{M}$ 上的最终状态为 $(q_5, q_5)$。** 由于输入字符串仅由 1 组成，且转移函数定义为 $\tilde{\delta}((q, q'), a) = (\delta(q, 0), \delta(q', 0))$，对于每一个输入 1，状态转移都按照输入 0 来进行。 因此，输入 $1^n$ 时，状态序列为：

(q_0, q_0) \xrightarrow{1} (q_1, q_1) \xrightarrow{1} (q_2, q_2) \xrightarrow{1} (q_3, q_3) \xrightarrow{1} (q_4, q_4) \xrightarrow{1} (q_5, q_5)

当 $n$ 是 5 的倍数时，最终状态为 $(q_5, q_5)$。 **3. 对于长度 $≥ 2$ 的字符串 $w ∈ \{0, 1\}^*$，自动机 $\tilde{M}$ 的最终状态记为 $(q_{iw}, q_{jw})$，其中 $iw, jw ∈ \{2, 3, 4, 5, 6\}$。请用字符串 $w$ 中 $0$ 和 $1$ 的个数（即 $\#_0(w)$ 和 $\#_1(w)$）表示 $iw$ 和 $jw$。** 根据转移函数定义，状态转移始终按照输入 0 来进行。因此，最终状态 $(q_{iw}, q_{jw})$ 可以表示为：

iw = (#_0(w) + #_1(w)) \mod 5 + 2

jw = (#_0(w) + #_1(w)) \mod 5 + 2

**4. 证明自动机 $\tilde{M}$ 接受的语言是：**

{w \in {0, 1}^* \mid #_0(w) \mod 5 = 2, #_1(w) \mod 5 = 0}

自动机 $\tilde{M}$ 的接受状态为 $(q_2, q_2)$。根据转移函数定义，状态转移始终按照输入 0 来进行。因此，要使最终状态为 $(q_2, q_2)$，需要满足：

(#_0(w) + #_1(w)) \mod 5 = 2

并且，由于 $\#_1(w) \mod 5 = 0$，所以：

#_0(w) \mod 5 = 2

因此，自动机 $\tilde{M}$ 接受的语言是：

{w \in {0, 1}^* \mid #_0(w) \mod 5 = 2, #_1(w) \mod 5 = 0}

Link to original

---

問2

文字列 $x$ と文字列 $y$ に対して, ${\#}_y(x)$ を $x$ における $y$ の部分文字列としての出現回数とする．例えば、文字列$x=abbbabb$と文字列$y=bb$について、${\#}_y(x)=3$である. また、文字列$x$の反転文字列を$x^R$と表す. 以下の言語を考える:

$$\begin{array}{rl}& L_1=\{x\in \{a,b{\}}^{\ast }|{\#}_a(x)={\#}_b(x)\},\\ & L_2=\{x\in \{a,b{\}}^{\ast }|{\#}_{ab}(x)={\#}_{ba}(x)\},\\ & L_3=\{x\in \{a,b{\}}^{\ast }|{\#}_{aa}(x)={\#}_{bb}(x)=0\},\\ & L_4=\{x{x}^R|x\in \{a,b{\}}^{\ast }\},\\ & L_5=\{a^i{b}^j{c}^k|i,j,k\ge 0,j=i+k\}.\end{array}$$

言語 $L_1,L_2,L_3,L_4,L_5$ のそれぞれについて:

• 正則であれば正規表現を与えよ.
• 正則でなければ文脈自由文法を与えよ.

Link to original