115 年 國立成功大學工程科學系碩士班己組《計算機數學》

此題考查邏輯敘述的逆否命題。
原敘述為「若 P 則 Q」，即 $P \rightarrow Q$。
其逆否命題為「若非 Q 則非 P」，即 $\neg Q \rightarrow \neg P$。

原敘述：「若 $n^2$ 是偶數（P），則 $n$ 是偶數（Q）。」
這裡的 P 是「$n^2$ 是偶數」，Q 是「$n$ 是偶數」。

我們需要找 $\neg Q \rightarrow \neg P$。
$\neg Q$ 是「$n$ 不是偶數」，也就是「$n$ 是奇數」。
$\neg P$ 是「$n^2$ 不是偶數」，也就是「$n^2$ 是奇數」。

所以，逆否命題是：「若 $n$ 是奇數，則 $n^2$ 是奇數。」

核心觀念

函數 $h:A\to B$ 為單射（injection），是指：

$$h(x_1)=h(x_2)\Longrightarrow x_1=x_2$$

本題已知合成函數 $g\circ f:A\to C$ 為單射，也就是：

$$(g\circ f)(x_1)=(g\circ f)(x_2)\Longrightarrow x_1=x_2$$

其中

$$(g\circ f)(x)=g(f(x))$$

要判斷由 $g\circ f$ 為單射，能否推出 $f$ 或 $g$ 必為單射。

---

解題方法

假設 $f(x_1)=f(x_2)$。兩邊同時套用函數 $g$，可得：

$$g(f(x_1))=g(f(x_2))$$

也就是：

$$(g\circ f)(x_1)=(g\circ f)(x_2)$$

因為 $g\circ f$ 是單射，所以必有：

$$x_1=x_2$$

因此符合單射定義，得到：

$$f\text{ 必為單射}$$

但是，$g$ 不必為單射。原因是 $g$ 在整個集合 $B$ 上即使有不同元素映射到相同值，只要這些元素不是由 $f$ 的值域取得，就不會影響合成函數 $g\circ f$ 的單射性。

---

選項分析

(A) $g$ must be an injection.

錯誤。

令

$$A=\{1\},\qquad B=\{a,b\},\qquad C=\{0\}$$

定義

$$f(1)=a,\qquad g(a)=0,\qquad g(b)=0$$

由於 $A$ 只有一個元素，$g\circ f:A\to C$ 必為單射；但 $g(a)=g(b)$ 且 $a\ne b$，所以 $g$ 不是單射。

因此 $g\circ f$ 為單射，不能保證 $g$ 為單射。

---

此題考查費馬小定理（Fermat's Little Theorem）的應用。

費馬小定理指出，如果 $p$ 是一個質數，那麼對於任意整數 $a$ 不被 $p$ 整除，都有 $a^{p-1} \equiv 1 \pmod{p}$。

題目中給定 $p=101$，它是一個質數。
我們要計算 $2^{100} \pmod{101}$。
根據費馬小定理，取 $a=2$。

此題考查二項分布（Binomial Distribution）的方差計算。

一個伯努利試驗（Bernoulli trial）是指一個只有兩種結果（成功或失敗）的隨機試驗。
成功機率為 $p$，失敗機率為 $q = 1-p$。

當一個伯努利試驗獨立重複 $n$ 次時，總成功次數 $X$ 服從二項分布，記為 $X \sim \text{Binomial}(n, p)$。
二項分布的期望值為 $E[X] = np$。
二項分布的方差為 $\text{Var}(X) = npq = np(1-p)$。

此題考查矩陣的特徵值與多項式函數的關係，以及行列式的性質。

已知矩陣 $A$ 是一個 3x3 的可對角化矩陣，其特徵值為 $\lambda_1 = 1$, $\lambda_2 = 2$, $\lambda_3 = 3$。
我們需要計算矩陣 $B = A^2 - 3A + 2I$ 的行列式 $\det(B)$。
其中 $I$ 是 3x3 的單位矩陣。

由於矩陣 $A$ 是可對角化的，存在一個可逆矩陣 $P$ 使得 $A = P D P^{-1}$，其中 $D$ 是一個對角矩陣，其對角線元素是 $A$ 的特徵值。
$D = \begin{pmatrix} 1 & 0 & 0 \\ 0 & 2 & 0 \\ 0 & 0 & 3 \end{pmatrix}$。

對於多項式函數 $p(x) = x^2 - 3x + 2$，如果 $A$ 的特徵值是 $\lambda_i$，那麼矩陣 $p(A)$ 的特徵值就是 $p(\lambda_i)$。
所以，矩陣 $B = A^2 - 3A + 2I$ 的特徵值是：
$p(\lambda_1) = \lambda_1^2 - 3\lambda_1 + 2 = 1^2 - 3(1) + 2 = 1 - 3 + 2 = 0$
$p(\lambda_2) = \lambda_2^2 - 3\lambda_2 + 2 = 2^2 - 3(2) + 2 = 4 - 6 + 2 = 0$
$p(\lambda_3) = \lambda_3^2 - 3\lambda_3 + 2 = 3^2 - 3(3) + 2 = 9 - 9 + 2 = 2$

因此，矩陣 $B$ 的特徵值為 $0, 0, 2$。

此題考查圖論中關於無環圖（acyclic graph）的性質，特別是樹（tree）的定義。

一個簡單無向圖（simple undirected graph）是指圖中任意兩點之間最多只有一條邊，且沒有自環（loop）。
無環圖（graph with no cycles）是指圖中不存在任何閉合的路徑。

一個連通的無向圖，如果它沒有環，那麼它一定是樹。
一棵有 $n$ 個頂點的樹，恰好有 $n-1$ 條邊。

題目要求的是「最大」邊數，這暗示我們需要考慮圖的連通性。
如果一個圖有 $n$ 個頂點且沒有環，那麼它最多可以有 $n-1$ 條邊。
這是因為每增加一條邊，如果這條邊連接了兩個已經在同一個連通分支中的頂點，就會形成一個環。如果連接了兩個不同連通分支的頂點，則會將兩個分支合併成一個更大的連通分支，但不會形成環。

此題考查遞迴關係式（Recurrence Relation）的求解，以確定演算法的時間複雜度，通常使用主定理（Master Theorem）。

給定的遞迴關係式為 $T(n) = 2T(n/2) + n^2$。
這個遞迴關係式的形式是 $T(n) = aT(n/b) + f(n)$，其中：
$a = 2$ (遞迴調用的次數)
$b = 2$ (每次遞迴調用時問題規模的縮小因子)
$f(n) = n^2$ (合併或處理步驟的時間複雜度)

我們需要將 $f(n)$ 與 $n^{\log_b a}$ 進行比較。
首先計算 $n^{\log_b a}$：
$\log_b a = \log_2 2 = 1$。
所以，$n^{\log_b a} = n^1 = n$。

現在我們將 $f(n) = n^2$ 與 $n^{\log_b a} = n$ 進行比較。
我們看到 $f(n) = n^2$ 相對於 $n^{\log_b a} = n$ 是「漸進地更大」的。
具體來說，對於足夠大的 $n$， $n^2$ 比 $n$ 要大得多。

我們檢查主定理的第三種情況：
若 $f(n) = \Omega(n^{\log_b a + \epsilon})$ 對於某個常數 $\epsilon > 0$，且 $af(n/b) \le c f(n)$ 對於某個常數 $c < 1$ 和足夠大的 $n$。

在這裡，$f(n) = n^2$。
$n^{\log_b a} = n^1$。
我們有 $n^2 = \Omega(n^{1+\epsilon})$。

此題考查布林代數（Boolean Algebra）中的異或（XOR）運算性質。

布林代數中的異或運算符號通常用 $\oplus$ 或 XOR 表示。
其運算規則為：
$0 \oplus 0 = 0$
$0 \oplus 1 = 1$
$1 \oplus 0 = 1$
$1 \oplus 1 = 0$

異或運算有以下性質：

1. 交換律：$A \oplus B = B \oplus A$
2. 結合律：$(A \oplus B) \oplus C = A \oplus (B \oplus C)$
3. 單位元素（恆等元素）：存在一個元素 $0$ 使得 $A \oplus 0 = A$ 對於所有 $A$。

此題考查條件機率與全機率定理（Law of Total Probability）的應用。

我們定義以下事件：
$T_0$: 發送者發送 '0'。
$T_1$: 發送者發送 '1'。
$R_0$: 接收到 '0'。
$R_1$: 接收到 '1'。

根據題目給定的資訊：
發送 '0' 的機率：$P(T_0) = 0.6$
發送 '1' 的機率：$P(T_1) = 0.4$
（注意：$P(T_0) + P(T_1) = 0.6 + 0.4 = 1$，這表示發送者只會發送 '0' 或 '1'。）

通信通道的雜訊特性：
傳送 '0' 但接收到 '1' 的機率（錯誤接收）：$P(R_1 | T_0) = 0.1$
傳送 '1' 但接收到 '0' 的機率（錯誤接收）：$P(R_0 | T_1) = 0.2$

此題考查貝氏定理（Bayes' Theorem）的應用。

我們沿用上一小題定義的事件：
$T_0$: 發送者發送 '0'。
$T_1$: 發送者發送 '1'。
$R_0$: 接收到 '0'。
$R_1$: 接收到 '1'。

已知資訊：
$P(T_0) = 0.6$
$P(T_1) = 0.4$
$P(R_1 | T_0) = 0.1$ (傳送 0 收到 1 的機率)
$P(R_0 | T_1) = 0.2$ (傳送 1 收到 0 的機率)
$P(R_0 | T_0) = 0.9$
$P(R_1 | T_1) = 0.8$

題目要求計算：如果 '1' 被接收到，那麼 '1' 被傳送的機率。這表示我們要求後驗機率 $P(T_1 | R_1)$。

此題考查連續隨機變數機率密度函數（PDF）的性質。

一個函數 $f(x)$ 是有效的機率密度函數（PDF）必須滿足兩個條件：

1. $f(x) \ge 0$ 對於所有 $x$。
2. $\int_{-\infty}^{\infty} f(x) dx = 1$。

給定的 PDF 是 $f(x) = kx^2$ 對於 $0 \le x \le 3$，其他地方為 0。
首先，為了滿足條件 1 ($f(x) \ge 0$)，對於 $0 \le x \le 3$，$x^2 \ge 0$。因此，常數 $k$ 必須大於或等於 0。如果 $k < 0$，則 $f(x)$ 在此區間內將為負，不符合 PDF 的定義。所以，$k \ge 0$。

此題考查連續隨機變數累積分布函數（CDF）的計算。

累積分布函數 $F(x)$ 定義為 $F(x) = P(X \le x)$，對於連續隨機變數，這可以通過對機率密度函數（PDF） $f(t)$ 從負無窮大積分到 $x$ 來計算：
$F(x) = \int_{-\infty}^{x} f(t) dt$

我們已經在上小題中求出，使 $f(x)$ 成為有效 PDF 的常數 $k = 1/9$。
所以，PDF 為 $f(x) = \frac{1}{9}x^2$ 對於 $0 \le x \le 3$，其他地方為 0。

我們需要分段計算 $F(x)$，考慮 $x$ 的不同取值範圍：

情況 1：$x < 0$
此時，$f(t) = 0$ 對於所有 $t \le x$。
$F(x) = \int_{-\infty}^{x} 0 dt = 0$。

情況 2：$0 \le x \le 3$
此時，積分範圍從 $-\infty$ 到 $x$ 包含 $f(t)=0$ 的部分和 $f(t) = \frac{1}{9}t^2$ 的部分。
$F(x) = \int_{-\infty}^{x} f(t) dt = \int_{-\infty}^{0} 0 dt + \int_{0}^{x} \frac{1}{9}t^2 dt$
$F(x) = 0 + \frac{1}{9} \int_{0}^{x} t^2 dt$
$F(x) = \frac{1}{9} \left[ \frac{t^3}{3} \right]_{0}^{x}$

此題考查連續隨機變數期望值（Expected Value）的計算。

對於一個連續隨機變數 $X$ 具有機率密度函數（PDF）$f(x)$，其期望值 $E[X]$ 的計算公式為：
$E[X] = \int_{-\infty}^{\infty} x f(x) dx$

我們已經在上小題中確定了 PDF 為 $f(x) = \frac{1}{9}x^2$ 對於 $0 \le x \le 3$，其他地方為 0。
將此 PDF 代入期望值公式：
$E[X] = \int_{-\infty}^{\infty} x f(x) dx = \int_{0}^{3} x \left( \frac{1}{9}x^2 \right) dx$
$E[X] = \int_{0}^{3} \frac{1}{9}x^3 dx$

此題考查馬可夫鏈（Markov Chain）的轉移矩陣（Transition Matrix）的建構。

我們有兩個狀態（平台）：A 和 B。
一個月內，用戶在 A 和 B 之間移動。
30% 的用戶從 A 轉移到 B。
20% 的用戶從 B 轉移到 A。

這意味著：
從 A 轉移到 A 的機率：$P(A \rightarrow A) = 1 - P(A \rightarrow B) = 1 - 0.30 = 0.70$。
從 A 轉移到 B 的機率：$P(A \rightarrow B) = 0.30$。

從 B 轉移到 B 的機率：$P(B \rightarrow B) = 1 - P(B \rightarrow A) = 1 - 0.20 = 0.80$。
從 B 轉移到 A 的機率：$P(B \rightarrow A) = 0.20$。

轉移矩陣 $P$ 的維度是 $2 \times 2$，其中列代表起始狀態，行代表結束狀態（或者反之，這裡我們按照常見的約定：行代表起始狀態，列代表結束狀態，使得狀態向量是行向量；或者列代表起始狀態，行代表結束狀態，使得狀態向量是列向量。

此題考查馬可夫鏈的狀態分佈計算。

我們已經建構了轉移矩陣 $P = \begin{pmatrix} 0.7 & 0.3 \\ 0.2 & 0.8 \end{pmatrix}$。
其中 A 是狀態 1，B 是狀態 2。

初始分佈是 100% 的用戶在平台 A。
我們可以用一個列向量來表示初始狀態分佈，假設用戶總數為 1。
初始狀態向量 $v_0 = \begin{pmatrix} 1 \\ 0 \end{pmatrix}$ (100% 在 A，0% 在 B)。

經過一個月的狀態分佈 $v_1$ 可以通過 $v_1 = P v_0$ 計算。
$v_1 = \begin{pmatrix} 0.7 & 0.3 \\ 0.2 & 0.8 \end{pmatrix} \begin{pmatrix} 1 \\ 0 \end{pmatrix} = \begin{pmatrix} 0.7 \times 1 + 0.3 \times 0 \\ 0.2 \times 1 + 0.8 \times 0 \end{pmatrix} = \begin{pmatrix} 0.7 \\ 0.2 \end{pmatrix}$
所以，一個月後，70% 的用戶在 A，20% 的用戶在 B。
（注意：這裡的計算結果 $0.7+0.2=0.9$ 似乎少了一部分用戶。這是因為我們假設的初始分佈是一個嚴格的列向量。如果我們考慮的是用戶的總數，那麼 $P(A \rightarrow A) = 0.7$ 和 $P(A \rightarrow B) = 0.3$。如果初始是 100% 在 A，那麼 70% 留在 A，30% 轉到 B。所以一個月後，A 的用戶比例是 $1 \times 0.7 = 0.7$，B 的用戶比例是 $1 \times 0.3 = 0.3$。所以初始狀態向量的表示方法需要更精確。

我們採用行向量表示狀態分佈，使得 $v_{n+1} = v_n P$。
初始狀態向量 $v_0 = \begin{pmatrix} 1 & 0 \end{pmatrix}$ (100% 在 A，0% 在 B)。

經過一個月的狀態分佈 $v_1$：

此題考查馬可夫鏈的穩態分佈（Steady-State Distribution）。

穩態分佈 $\pi = \begin{pmatrix} \pi_A & \pi_B \end{pmatrix}$ 是一個行向量，滿足以下兩個條件：

1. $\pi P = \pi$ (其中 P 是轉移矩陣)。
2. $\pi_A + \pi_B = 1$ (所有狀態的機率和為 1)。

我們已經建構了轉移矩陣 $P = \begin{pmatrix} 0.7 & 0.3 \\ 0.2 & 0.8 \end{pmatrix}$。
令穩態分佈為 $\pi = \begin{pmatrix} \pi_A & \pi_B \end{pmatrix}$。

根據條件 1：$\pi P = \pi$
$\begin{pmatrix} \pi_A & \pi_B \end{pmatrix} \begin{pmatrix} 0.7 & 0.3 \\ 0.2 & 0.8 \end{pmatrix} = \begin{pmatrix} \pi_A & \pi_B \end{pmatrix}$

展開矩陣乘法：
第一列：$\pi_A \times 0.7 + \pi_B \times 0.2 = \pi_A$

此題考查非齊次線性遞迴關係式（Non-homogeneous Linear Recurrence Relation）的求解，包含求齊次解和特解。

給定的遞迴關係式為：$a_n - 3a_{n-1} + 2a_{n-2} = 3^n$
初始條件為：$a_0 = 1$, $a_1 = 3$。

遞迴關係式的通解 $a_n$ 由齊次解 $a_n^{(h)}$ 和特解 $a_n^{(p)}$ 相加得到：$a_n = a_n^{(h)} + a_n^{(p)}$。

第一步：求解齊次遞迴關係式的解 $a_n^{(h)}$。
齊次遞迴關係式為：$a_n - 3a_{n-1} + 2a_{n-2} = 0$
其特徵方程式（Characteristic Equation）為：
$r^2 - 3r + 2 = 0$

因式分解特徵方程式：
$(r-1)(r-2) = 0$
所以，特徵根為 $r_1 = 1$ 和 $r_2 = 2$。

由於特徵根是兩個不同的實根，齊次解的形式為：
$a_n^{(h)} = c_1 (1)^n + c_2 (2)^n = c_1 + c_2 2^n$
其中 $c_1$ 和 $c_2$ 是待定常數。

第二步：求解非齊次遞迴關係式的特解 $a_n^{(p)}$。
非齊次項是 $3^n$。
由於 $r=1$ 是特徵根之一，且非齊次項是 $3^n$ (其中 3 不是特徵根)，我們假設特解的形式為：
$a_n^{(p)} = A \cdot 3^n$
其中 $A$ 是待定常數。

將此特解形式代入原遞迴關係式：
$A \cdot 3^n - 3(A \cdot 3^{n-1}) + 2(A \cdot 3^{n-2}) = 3^n$
$A \cdot 3^n - 3A \cdot \frac{3^n}{3} + 2A \cdot \frac{3^n}{9} = 3^n$
$A \cdot 3^n - A \cdot 3^n + \frac{2A}{9} \cdot 3^n = 3^n$
$0 + \frac{2A}{9} \cdot 3^n = 3^n$

為了使等式成立，我們需要：
$\frac{2A}{9} = 1$
$2A = 9$
$A = \frac{9}{2}$

所以，特解為 $a_n^{(p)} = \frac{9}{2} \cdot 3^n$。

第三步：組合齊次解和特解得到通解。
$a_n = a_n^{(h)} + a_n^{(p)} = c_1 + c_2 2^n + \frac{9}{2} 3^n$

第四步：利用初始條件確定常數 $c_1$ 和 $c_2$。
初始條件是 $a_0 = 1$ 和 $a_1 = 3$。