109 交大資工所考古題詳解｜數學考點分析

題型與配分

全卷 3 頁、12 題、100 分，不可使用計算機。

離散數學考點（1–6）

• 第 1 題（9%）｜三個 {0,1,2,3} 上的關係中哪些是 partial order（partial ordering），不是的要說明違反了哪一條
• 第 2 題（8%）｜給 a_n = 1 + (−1)ⁿ 與 a_n = n(n+1)，寫出它們的遞迴定義（與 107 年第 5 題同型）
• 第 3 題（8%）｜判斷 directed graph 是否有從 a 出發的 Euler circuit；沒有的話再判斷是否有 Euler path，並實際構造出來
• 第 4 題（8%）｜f : P(N) → R 的函數：(a) 4% 值域的最大基數 (b) 4% 若 f 滿足 f(S₁)+f(S₂) ≤ f(S₁∪S₂)+f(S₁∩S₂)（supermodular），證明 C ⊆ T ⊆ N 時 f(C∪{i}) − f(C) ≤ f(T∪{i}) − f(T)
• 第 5 題（10%）｜(a) 5% 質數無限多的反證法中，要讓證明成立的 q 該取什麼值 (b) 5% domain 為 [2,10] 的正整數，P(x) 為「x 是質數」、Q(x) 為「x ≡ 3 (mod 5)」，找出基數最大的集合 S 使 ∀x∈S (P(x)→Q(x)) 為真且 ∃x∈S (P(x)∧Q(x)) 為假
• 第 6 題（7%）｜a = 277、b = 91，求 s、t 使 gcd(a,b) = sa − tb

線性代數考點（7–12）

• 第 7 題（5%）｜三種 elementary matrix（交換列、乘常數、加倍數）與 det(A) = 6 時，求 det(E₁A)、det(E₂A)、det(AE₃)、det(E₂)、det(E₃E₂E₁)
• 第 8 題（10%）｜(a) 5% 找出 elementary matrix F₁, F₂, F₃ 使 F₃F₂F₁A = U 為 upper triangular (b) 5% 求各 F_i 的 inverse 並令 L = F₁⁻¹F₂⁻¹F₃⁻¹，問 L 是什麼類型的矩陣並驗證 A = LU
• 第 9 題（10%）｜給 4×4 矩陣 A 的 reduced row echelon form 與前兩個 column vector：(a) 2% 求 rank(A) (b) 4% 求 N(A) 的 basis (c) 4% 求出 a₃ 與 a₄
• 第 10 題（15%）｜homogeneous coordinates 與 3D 旋轉：兩組 orthonormal 右手座標系 B₁、B₂，已知部分 basis vector 的對應：(a) 3% 求 [e_z]_B2 (b) 4% 求把 B₂ 座標轉成 B₁ 座標的 3×3 rotation matrix (c) 3% 求原點位移向量 (d) 5% 寫出 homogeneous coordinates 下把 [u v w 1]^T 轉成 [x y z 1]^T 的 4×4 矩陣
• 第 11 題（4%）｜給五個矩陣，分別列出哪些是 symmetric（M^T = M）、哪些是 Hermitian（Mᴴ = M）
• 第 12 題（6%）｜給一個複數矩陣 A，求 unitary matrix U 使 D = U⁻¹AU 為 diagonal，且 eigenvalue 必須由大到小排列

作答時要注意的地方

1. 第 10 題 15 分，是全卷配分最高的單題，四小題連動。
2. 第 5(b) 要同時滿足一個全稱句為真、一個存在句為假。
3. 第 12 題要求 eigenvalue 由大到小排列。

準備方向

• LU 分解與 elementary matrix（109 第 7、8 題共 15 分）。
• 齊次座標與 3D 變換（109 第 10 題）。
• 擴展 Euclidean algorithm（109 第 6 題）。
• Hermitian 與 unitary diagonalization（109 第 11、12 題）。