113 師大資工所考古題詳解｜數學考點分析

題型與配分

全卷 3 頁、7 大題、100 分，申論題，卷面沒寫倒扣。卷面注意事項是「請依序在答案卷上作答，並標明題號，不必抄題」與「答案必須寫在指定作答區內，否則依規定扣分」。卷首有 Some notations，定義 column vector 與 linear operator。

110–112 年離散數學是五大題，這一年只有三大題。

線性代數考點（1–4，50%）

• 第 1 題（14%）｜A = [a₁ a₂ a₃ a₄ a₅]（4×5），題目給 reduced row echelon form R = [[1,2,0,0,−2],[0,0,1,0,3],[0,0,0,1,1],[0,0,0,0,0]]，以及 a₂ = (6,10,4,2)^T、a₃ = (2,0,−1,−1)^T、a₄ = (2,−1,3,2)^T
• 第 1(a) 題（6%）｜求矩陣 A
• 第 1(b) 題（2%）｜求 Col A 的 dimension
• 第 1(c) 題（2%）｜求 Null A 的 dimension
• 第 1(d) 題（4%）｜求 Ax = 0 通解的向量形式，x = (x₁, …, x₅)^T
• 第 2(a) 題（5%）｜3×3 矩陣 A，det A = −9，求矩陣 [a₁₁−3a₂₁, a₁₂−3a₂₂, a₁₃−3a₂₃ ; 4a₂₁, 4a₂₂, 4a₂₃ ; 2a₃₁−5a₂₁, 2a₃₂−5a₂₂, 2a₃₃−5a₂₃] 的 determinant
• 第 2(b) 題（5%）｜R³ 上的 linear operator T(x₁, x₂, x₃) = (−4x₁ − 2x₂, c·x₂, 4x₁ + 4x₂ − 2x₃)，c 為某純量，求所有使 T 不 diagonalizable 的 c
• 第 3(a) 題（7%）｜R³ 對平面 W = {x : x₁ − x₂ + x₃ = 0} 的 reflection operator T_W，要求寫出明確公式
• 第 3(b) 題（6%）｜u = (3, −2, 1)^T，求 W 中離 u 最近的唯一向量 w
• 第 4(a) 題（7%）｜symmetric matrix A = [[6, 2, 0], [2, 9, 0], [0, 0, −9]]，求由 eigenvector 組成的 orthonormal basis 與對應的 eigenvalue
• 第 4(b) 題（6%）｜利用 (a) 的結果，寫出 A⁴ 的 spectral decomposition

離散數學考點（5–7，50%）

• 第 5 題（15%）｜無向 simple graph G，頂點集為 V。頂點子集 U 稱為「good」，若 U 中每個頂點在 V−U 中恰有一個鄰居；稱為「not bad」，若 V−U 中每個頂點在 U 中恰有一個鄰居
• 第 5(a) 題（5%）｜證明或反證：good 蘊含 not bad
• 第 5(b) 題（10%）｜證明或反證：not bad 蘊含 good
• 第 6 題（25%）｜m×n 矩陣 M，每個元素獨立地以 1/2 機率設為 0 或 1，樣本空間 Ω 是 M 所有可能的結果。題目給了 5×4 矩陣的一個例子
• 第 6(a) 題（5%）｜若 M_ij 的上、下、左、右四個鄰居（M_i−1,j、M_i,j+1、M_i+1,j、M_i,j−1）都是 1，稱 M_ij 為 feasible，X(i,j) 是「M_ij 為 feasible」這個事件，例子中只有 (3,3) 與 (4,2) 是 feasible。證明或反證：(a,b) ≠ (c,d) 時，事件 X(a,b) 與 X(c,d) 獨立
• 第 6(b) 題（5%）｜W : Ω → R 是 M 中 feasible 元素個數的隨機變數，求 E[W]
• 第 6(c) 題（5%）｜Alice 觀察到 m ≥ 3 且 n ≥ 2^m+1 時，總有四個相異元素 M_ij、M_ij′、M_i′_j、M_i′_j′ 全為 0 或全為 1（例子中 (i,j,i′,j′) = (1,1,5,3) 的四個位置全為 0）。證明 Alice 的觀察必成立，或給反例
• 第 6(d) 題（10%）｜Bob 觀察到 m ≥ 3 且 n ≥ 7 時，同樣總有這樣的四個元素。證明 Bob 的觀察必成立，或給反例
• 第 7 題（10%）｜求下列 congruence equation 組的第二小正整數解：x ≡ 20 (mod 26)、x ≡ 8 (mod 11)、x ≡ 18 (mod 57)

作答時要注意的地方

1. 全卷申論題，卷面沒寫倒扣。
2. 第 1 題給的是 R 與 a₂、a₃、a₄ 三個 column vector，要回推出完整的 A。
3. 第 4(b) 問的是 A⁴ 的 spectral decomposition。
4. 第 5、6 題的小題都是「證明或反證」，不是單純的證明。
5. 第 7 題問的是第二小的正整數解。
6. 第 1 題 R 的前三列與 108 年第 1 題的 R 相同，兩年給的行不同。

準備方向

• RREF、rank 與四大 subspace：113 第 1 題；106 第 1、2 題、107 第 1 題、108 第 1 題、109 第 2 題、110 第 2 題、111 第 6 題、112 第 1 題、114 第 1 題、115 第 1(a) 題也有。
• determinant 與 row operation：113 第 2(a) 題；110 第 1 題、111 第 7 題也有。
• eigenvalue、diagonalization 與 eigenspace：113 第 2(b)、4 題；106 第 4 題、107 第 3、5 題、108 第 3 題、109 第 3、5 題、111 第 9 題、112 第 4 題、114 第 2、5 題、115 第 1(b) 題也有。
• orthogonal projection、reflection 與最近向量：113 第 3 題；108 第 4 題、109 第 4 題、110 第 3、4 題、111 第 10 題、112 第 5 題、114 第 4 題、115 第 3 題也有。
• 圖論：113 第 5 題；106 第 7(4) 題、107 第 6(d) 題、108 第 6(4)、8(4) 題、109 第 9(1) 題、110 第 8(2) 題、111 第 5 題、112 第 9 題、114 第 6、7 題、115 第 5、6 題也有。
• 隨機 0/1 矩陣的機率與期望值：113 第 6 題。
• congruence 與數論：113 第 7 題；106 第 7(2)(3)、10 題、107 第 10 題、108 第 8(1)、12(1) 題、109 第 10 題、111 第 4(2) 題、112 第 7 題、114 第 8 題、115 第 7 題也有。