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

本題考查牛頓法求函數根的概念與計算。牛頓法是一種迭代方法，用於尋找函數 $f(x)$ 的根。其迭代公式為：
$x_{n+1} = x_n - \frac{f(x_n)}{f'(x_n)}$

首先，我們需要計算函數 $f(x)$ 的導數 $f'(x)$。
給定 $f(x) = x^3 - 6x + 1$，
則 $f'(x) = 3x^2 - 6$。

初始值為 $x_0 = 2$。

第一次迭代 (n=0):
計算 $f(x_0) = f(2) = 2^3 - 6(2) + 1 = 8 - 12 + 1 = -3$。
計算 $f'(x_0) = f'(2) = 3(2^2) - 6 = 3(4) - 6 = 12 - 6 = 6$。
計算 $x_1 = x_0 - \frac{f(x_0)}{f'(x_0)} = 2 - \frac{-3}{6} = 2 - (-\frac{1}{2}) = 2 + 0.5 = 2.5$。

第二次迭代 (n=1):
計算 $f(x_1) = f(2.5) = (2.5)^3 - 6(2.5) + 1 = 15.625 - 15 + 1 = 1.625$。
計算 $f'(x_1) = f'(2.5) = 3(2.5)^2 - 6 = 3(6.25) - 6 = 18.75 - 6 = 12.75$。
計算 $x_2 = x_1 - \frac{f(x_1)}{f'(x_1)} = 2.5 - \frac{1.625}{12.75}$。

核心觀念

共有 $26$ 個英文字母，密碼長度為 $4$，因此密碼總數為

$$26^4=456,976.$$

本題比較兩種回饋機制：

• 沒有即時回饋：每次必須輸入完整四字元密碼，才能知道是否正確。
• 逐字元回饋：輸入某字元錯誤時立即被告知，因此不必繼續嘗試後面的字元。

假設攻擊者不重複嘗試，且正確密碼在所有可能密碼中等機率出現。

(A) 沒有回饋，完成整組密碼後才知道結果

解題方法

所有 $456,976$ 組密碼皆可能是正確答案。攻擊者依序嘗試時，正確密碼可能在第 $1$ 組、第 $2$ 組，直到第 $456,976$ 組被猜中。

因此嘗試次數 $N$ 均勻分布於

$$1,2,\ldots,456,976.$$

均勻分布的期望值為

$$E[N]=\frac{1+456,976}{2}=228,488.5.$$

每秒嘗試一組完整密碼，所以期望時間為

$$E[T_A]=228,488.5\text{ 秒}.$$

換算為小時：

$$\frac{228,488.5}{3600}\approx 63.47\text{ 小時}.$$

換算為天：

$$\frac{228,488.5}{86,400}\approx 2.645\text{ 天}.$$

(B) 每輸入一個錯誤字元便立即得到回饋

解題方法

逐一分析四個位置。

對任一位置而言，正確字元等可能是 $26$ 個字母中的任一個。攻擊者依序嘗試且不重複猜測時，正確字元出現的位置可能是

本題考查 RSA 非對稱加密演算法的原理、金鑰生成與加密解密過程。

核心觀念：
RSA 演算法基於數論中的大數分解難題。其安全性依賴於將兩個大質數相乘得到一個合數很容易，但將這個合數分解回兩個質數非常困難。

• 金鑰生成：
  • 選擇兩個大質數 $p$ 和 $q$。
  • 計算模數 $n = pq$。
  • 計算歐拉函數 $\phi(n) = (p-1)(q-1)$，通常用 $z$ 表示。
  • 選擇公鑰指數 $e$，要求 $1 < e < \phi(n)$ 且 $\gcd(e, \phi(n)) = 1$ (即 $e$ 與 $\phi(n)$ 互質)。
  • 計算私鑰指數 $d$，要求 $ed \equiv 1 \pmod{\phi(n)}$。這表示 $d$ 是 $e$ 在模 $\phi(n)$ 下的乘法逆元。
  • 公鑰為 $(n, e)$，私鑰為 $(n, d)$。
• 加密：
  • 密文 $c$ 由明文 $m$ 計算得出：$c = m^e \pmod{n}$。
• 解密：
  • 明文 $m$ 由密文 $c$ 計算得出：$m = c^d \pmod{n}$。

題目設定：
質數 $p = 3$, $q = 11$。

(A) 計算 n 和 z

解題步驟：

1. 計算 $n = pq$。
2. 計算 $z = (p-1)(q-1)$。

計算：

1. $n = 3 \times 11 = 33$。
2. $z = (3-1)(11-1) = 2 \times 10 = 20$。

【答案】
$n = 33$, $z = 20$。

(B) 比較 e = 5 或 e = 7 的優劣

核心觀念：
選擇公鑰指數 $e$ 時，通常希望 $e$ 盡可能小，以提高加密速度。然而，$e$ 必須與 $z$ 互質。同時，$e$ 的選擇也會影響私鑰 $d$ 的大小。在某些情況下，如果 $e$ 太小，可能會存在一些安全漏洞（例如，若 $m^e < n$，則 $c=m^e$ 會直接暴露明文）。但在此題中，我們主要考慮互質條件和計算的簡便性。

解題步驟：

1. 檢查 $e=5$ 是否與 $z=20$ 互質。
2. 檢查 $e=7$ 是否與 $z=20$ 互質。
3. 比較兩者的優劣。

計算：

• 對於 $e = 5$：
  $\gcd(5, 20) = 5$。
  因為 $\gcd(5, 20) \neq 1$，所以 $e=5$ 不能選擇，因為它與 $z=20$ 不互質。

• 對於 $e = 7$：
  $\gcd(7, 20)$。20 的質因數是 2 和 5。7 不是 2 或 5 的倍數，所以 $\gcd(7, 20) = 1$。
  $e=7$ 與 $z=20$ 互質，因此 $e=7$ 可以選擇。

結論：
只有 $e=7$ 是合法的選擇。因此，它自然是「更好」的選擇，因為 $e=5$ 是無效的。
如果題目假設 $e$ 必須互質，那麼 $e=5$ 就不是一個可行的選項。
如果允許我們從 $e=5, 7$ 中選擇一個，並且 $e=5$ 確實與 $z$ 互質，那麼通常會選擇較小的 $e$ 以加快加密。但在此情況下，$e=5$ 不互質。

【答案】
$e=7$ 是唯一合法的選擇，因為 $\gcd(7, 20) = 1$，而 $\gcd(5, 20) = 5 \neq 1$。

本題考查線性迴歸中的最小平方估計，使用正規方程（Normal Equation）來求解迴歸係數。

核心觀念：
在線性迴歸模型 $y = Xw + \epsilon$ 中，我們希望找到係數向量 $w$，使得預測值 $\hat{y} = Xw$ 與實際值 $y$ 之間的誤差平方和最小。正規方程提供了一種直接求解最佳 $w$ 的方法，其公式為：
$w = (X^T X)^{-1} X^T y$
其中：

• $X$ 是特徵矩陣 (包含截距項 1)。
• $y$ 是目標向量。
• $w$ 是係數向量。
• $X^T$ 是 $X$ 的轉置。
• $(X^T X)^{-1}$ 是 $X^T X$ 的逆矩陣。

題目設定：
特徵矩陣 $X = \begin{bmatrix} 1 & 1 \\ 1 & 2 \\ 1 & 3 \end{bmatrix}$。
目標向量 $y = \begin{bmatrix} 1 \\ 1 \\ 2.5 \end{bmatrix}$。

解題步驟：

1. 計算 $X^T$ (X 的轉置)。
2. 計算 $X^T X$。
3. 計算 $(X^T X)^{-1}$ (矩陣的逆)。
4. 計算 $X^T y$。
5. 將步驟 3 和 4 的結果代入正規方程 $w = (X^T X)^{-1} X^T y$ 計算 $w$。

計算：

1. 計算 $X^T$：

$$X^T = \begin{bmatrix} 1 & 1 & 1 \\ 1 & 2 & 3 \end{bmatrix}$$

2. 計算 $X^T X$：

$$X^T X = \begin{bmatrix} 1 & 1 & 1 \\ 1 & 2 & 3 \end{bmatrix} \begin{bmatrix} 1 & 1 \\ 1 & 2 \\ 1 & 3 \end{bmatrix}$$ $$X^T X = \begin{bmatrix} (1 \cdot 1 + 1 \cdot 1 + 1 \cdot 1) & (1 \cdot 1 + 1 \cdot 2 + 1 \cdot 3) \\ (1 \cdot 1 + 2 \cdot 1 + 3 \cdot 1) & (1 \cdot 1 + 2 \cdot 2 + 3 \cdot 3) \end{bmatrix}$$ $$X^T X = \begin{bmatrix} (1 + 1 + 1) & (1 + 2 + 3) \\ (1 + 2 + 3) & (1 + 4 + 9) \end{bmatrix}$$ $$X^T X = \begin{bmatrix} 3 & 6 \\ 6 & 14 \end{bmatrix}$$

3. 計算 $(X^T X)^{-1}$：
對於一個 2x2 矩陣 $A = \begin{bmatrix} a & b \\ c & d \end{bmatrix}$，其逆矩陣為 $A^{-1} = \frac{1}{ad-bc} \begin{bmatrix} d & -b \\ -c & a \end{bmatrix}$。
在這裡，$a=3, b=6, c=6, d=14$。

本題考查幾何演算法設計，判斷一個點是否在給定三角形內部。

核心觀念：
判斷一個點是否在三角形內部有幾種常見方法：

1. 面積法 (Barycentric Coordinates)： 如果點 P 在三角形 ABC 內部，則以 P 為頂點的三个小三角形 PAB, PBC, PCA 的面積之和等於三角形 ABC 的面積。
2. 向量叉乘法 (Cross Product)： 如果點 P 在三角形 ABC 的內部，則 P 在邊 AB 的左側，在邊 BC 的左側，以及在邊 CA 的左側（或全部在右側，取決於頂點順序）。我們需要確保頂點的順序是順時針或逆時針。
3. 半平面法 (Half-Plane Test)： 每個三角形的邊都定義了一條直線，該直線將平面分成兩個半平面。點 P 在三角形內部，當且僅當它位於所有三條邊定義的「內部」半平面。

這裡我們採用向量叉乘法，因為它在計算上相對直接且效率高。

演算法設計 (向量叉乘法)：

步驟：

1. 計算三角形 ABC 的頂點順序： 確定頂點 A, B, C 的順序是順時針還是逆時針。這可以通過計算向量 AB 和 AC 的叉乘來判斷。

   • 向量 $\vec{AB} = B - A = (4-0, 0-0) = (4, 0)$。
   • 向量 $\vec{AC} = C - A = (0-0, 3-0) = (0, 3)$。
   • 2D 叉乘 (或說 z 分量) $\vec{AB} \times \vec{AC} = (4)(3) - (0)(0) = 12$。
   • 由於叉乘結果為正 (12 > 0)，頂點 A, B, C 是逆時針順序。這意味著，如果點 P 在三角形內部，它應該位於邊 AB 的左側，邊 BC 的左側，以及邊 CA 的左側。

2. 定義一個輔助函數 isLeft(P1, P2, P3)： 這個函數判斷點 P3 相對於有向線段 P1P2 的位置。

   • 它計算向量 $\vec{P1P2} = P2 - P1$ 和向量 $\vec{P1P3} = P3 - P1$ 的 2D 叉乘。
   • 設 $P1 = (x1, y1)$, $P2 = (x2, y2)$, $P3 = (x3, y3)$。
   • $\vec{P1P2} = (x2-x1, y2-y1)$
   • $\vec{P1P3} = (x3-x1, y3-y1)$
   • 叉乘值 $V = (x2-x1)(y3-y1) - (y2-y1)(x3-x1)$。
   • 如果 $V > 0$，則 P3 在 P1P2 的左側。
   • 如果 $V < 0$，則 P3 在 P1P2 的右側。
   • 如果 $V = 0$，則 P3 在直線 P1P2 上。

3. 應用 isLeft 函數：
   為了判斷點 P(x, y) 是否在三角形 ABC (A(0,0), B(4,0), C(0,3)) 內部，我們需要檢查 P 相對於有向邊 AB, BC, CA 的位置。由於 A, B, C 是逆時針順序，P 必須在所有這三條邊的左側（或在邊上）。

   • 檢查 P 相對於 AB 的位置：isLeft(A, B, P)。
   • 檢查 P 相對於 BC 的位置：isLeft(B, C, P)。
   • 檢查 P 相對於 CA 的位置：isLeft(C, A, P)。

   如果這三個條件都成立（叉乘值 >= 0），則點 P 在三角形內部或邊界上。如果需要嚴格內部，則需要叉乘值 > 0。題目通常指包含邊界。

具體演算法 Pseudocode：

本題考查條件機率的計算。

核心觀念：
條件機率 $P(A|B)$ 表示在事件 B 已經發生的條件下，事件 A 發生的機率。其公式為：
$P(A|B) = \frac{P(A \cap B)}{P(B)}$
其中 $P(A \cap B)$ 是事件 A 和事件 B 同時發生的機率，而 $P(B)$ 是事件 B 發生的機率。

題目設定：

• 紅色球 (R)：3 個
• 藍色球 (B)：4 個
• 綠色球 (G)：5 個
• 總球數：$3 + 4 + 5 = 12$ 個。
• 隨機抽取一個球。

事件定義：

• 事件 A：抽到的球是藍色 (Blue)。
• 事件 B：抽到的球不是紅色 (Not Red)。

解題步驟：

1. 計算總球數。
2. 計算事件 B (抽到的球不是紅色) 的機率 $P(B)$。
3. 計算事件 A 和事件 B 同時發生的機率 $P(A \cap B)$。
4. 使用條件機率公式計算 $P(A|B)$。

計算：

1. 總球數： 12 個。

2. 計算 $P(B)$ (抽到的球不是紅色)：
   如果球不是紅色，則它必定是藍色或綠色。
   不是紅色的球的數量 = 藍色球數量 + 綠色球數量 = $4 + 5 = 9$ 個。
   所以，抽到不是紅色的球的機率是：

本題考查貝氏定理 (Bayes' Theorem) 的應用，用於計算在觀測到某個事件 (測試結果為陽性) 後，某個假設 (患有疾病) 為真的機率。

核心觀念：
貝氏定理用於更新在獲得新證據後，某個假設的機率。
$P(A|B) = \frac{P(B|A) P(A)}{P(B)}$
其中：

• $P(A|B)$：在事件 B 發生的條件下，事件 A 發生的後驗機率 (Posterior Probability)。
• $P(B|A)$：在事件 A 發生的條件下，事件 B 發生的機率 (Likelihood)。
• $P(A)$：事件 A 的先驗機率 (Prior Probability)。
• $P(B)$：事件 B 的總機率 (Marginal Probability)。

題目設定：

• 事件 D：一個人患有該疾病。
• 事件 D'：一個人沒有患有該疾病 ($D'$ 是 $D$ 的補集)。
• 事件 Pos：醫療測試結果為陽性。
• 事件 Neg：醫療測試結果為陰性。

已知資訊：

1. 測試準確性 (Sensitivity)： 如果一個人有疾病，測試結果為陽性的機率是 95%。
   $P(\text{Pos}|D) = 0.95$。
2. 誤報率 (False Positive Rate)： 如果一個人沒有疾病，測試結果為陽性的機率是 10%。
   $P(\text{Pos}|D') = 0.10$。
3. 疾病患病率 (Prevalence)： 1% 的人口患有該疾病。
   $P(D) = 0.01$。

要求：
計算一個人實際患有疾病的機率，已知他的測試結果為陽性。即，計算 $P(D|\text{Pos})$。

解題步驟：

1. 根據 $P(D)$，計算 $P(D')$。
2. 計算測試結果為陽性的總機率 $P(\text{Pos})$。這可以通過全機率公式 (Law of Total Probability) 計算：
   $P(\text{Pos}) = P(\text{Pos}|D) P(D) + P(\text{Pos}|D') P(D')$。
3. 將已知資訊和計算出的 $P(\text{Pos})$ 代入貝氏定理公式，計算 $P(D|\text{Pos})$。

計算：

本題考查離散隨機變數的期望值 (Expected Value) 和變異數 (Variance) 的計算。

核心觀念：
對於一個離散隨機變數 $X$，其機率質量函數 (Probability Mass Function, PMF) 為 $P(X=x)$。

• 期望值 E(X)： 是隨機變數取值的加權平均，權重是對應的機率。
  $E(X) = \sum_{x} x \cdot P(X=x)$
• 變異數 Var(X)： 度量隨機變數取值的分散程度，定義為隨機變數與其期望值之差的平方的期望值。
  $Var(X) = E[(X - E(X))^2]$
  另一個常用的計算公式是：
  $Var(X) = E(X^2) - [E(X)]^2$
  其中 $E(X^2) = \sum_{x} x^2 \cdot P(X=x)$。

題目設定：
隨機變數 $X$ 的機率分佈如下：

• $P(X=1) = 0.2$
• $P(X=2) = 0.5$
• $P(X=3) = 0.3$

解題步驟：

1. 計算期望值 $E(X)$。
2. 計算 $E(X^2)$。
3. 使用公式 $Var(X) = E(X^2) - [E(X)]^2$ 計算變異數 $Var(X)$。

計算：

核心觀念

本題考查 Eulerian path 與 Eulerian circuit 的判定。

• Eulerian path（歐拉路徑）：恰好經過圖中每一條邊一次的路徑，起點與終點可以不同。
• Eulerian circuit（歐拉迴路）：恰好經過圖中每一條邊一次，且起點與終點相同的迴路。

對於具有連通性的無向圖：

1. 所有頂點的度數皆為偶數 $\Rightarrow$ 存在 Eulerian circuit。
2. 恰有兩個頂點的度數為奇數 $\Rightarrow$ 存在 Eulerian path，但不存在 Eulerian circuit。
3. 奇數度頂點超過兩個，或圖不連通 $\Rightarrow$ 不存在 Eulerian path。

其中，頂點的度數是與該頂點相連的邊數。

解題方法

題目給定：

$$V=\{A,B,C,D\}$$ $$E=\{AB,BC,CD,DA,AC\}$$

逐一計算各頂點的度數：

• $A$ 連接 $AB,DA,AC$，因此 $\deg(A)=3$。
• $B$ 連接 $AB,BC$，因此 $\deg(B)=2$。
• $C$ 連接 $BC,CD,AC$，因此 $\deg(C)=3$。
• $D$ 連接 $CD,DA$，因此 $\deg(D)=2$。

整理如下：