109 交大資工所數學考點分析

題型與配分

科目「線性代數與離散數學（1102）」，系所班別資訊聯招，考試日期 109 年 2 月 4 日第 2 節，全卷 3 頁、12 題、100 分，不可使用計算機。

離散數學考點（1–6）

• 第 1 題（9%）｜三個 {0,1,2,3} 上的關係中哪些是偏序（partial ordering）（需 reflexive、antisymmetric、transitive），不是的要說明違反了哪一條
• 第 2 題（8%）｜給 a_n = 1 + (−1)ⁿ 與 a_n = n(n+1)，寫出它們的遞迴定義（與 107 年第 5 題同型）
• 第 3 題（8%）｜判斷有向圖是否有從 a 出發的 Euler circuit；沒有的話再判斷是否有 Euler path，並實際構造出來
• 第 4 題（8%）｜f : P(N) → R 的函數：(a) 4% 值域的最大基數（2^|N|） (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 該取什麼值（q = p₁p₂…p_n + 1） (b) 5% 定義域為 [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%）｜三種基本矩陣（交換列／乘常數／加倍數）與 det(A) = 6 時，求 det(E₁A)、det(E₂A)、det(AE₃)、det(E₂)、det(E₃E₂E₁)
• 第 8 題（10%）｜(a) 5% 找出基本矩陣 F₁, F₂, F₃ 使 F₃F₂F₁A = U 為上三角 (b) 5% 求各 F_i 的反矩陣並令 L = F₁⁻¹F₂⁻¹F₃⁻¹，問 L 是什麼類型的矩陣並驗證 A = LU。這是 LU 分解
• 第 9 題（10%）｜給 4×4 矩陣 A 的 reduced row echelon form 與前兩個行向量：(a) 2% 求 rank(A) (b) 4% 求 N(A) 的基底 (c) 4% 求出 a₃ 與 a₄（用 rref 中的自由變數係數組合前面的行向量）
• 第 10 題（15%）｜齊次座標（homogeneous coordinates）與 3D 旋轉：兩組正交歸一右手座標系 B₁、B₂，已知部分基向量的對應：(a) 3% 求 [e_z]_B2 (b) 4% 求把 B₂ 座標轉成 B₁ 座標的 3×3 旋轉矩陣 (c) 3% 求原點位移向量 (d) 5% 寫出齊次座標下把 [u v w 1]^T 轉成 [x y z 1]^T 的 4×4 矩陣
• 第 11 題（4%）｜給五個矩陣，分別列出哪些是對稱（M^T = M）、哪些是 Hermitian（Mᴴ = M）
• 第 12 題（6%）｜給一個複數矩陣 A，求 unitary 矩陣 U 使 D = U⁻¹AU 為對角，且特徵值必須由大到小排列

這份考卷的難點

1. 第 10 題（15 分）的齊次座標是全卷最大的單題，要同時處理旋轉矩陣的構造（正交歸一右手系）與平移的齊次座標表示，四小題連動。
2. 第 4(b) 的 supermodular 不等式證明是離散最佳化的內容，要用 S₁ = C∪{i}、S₂ = T 的巧妙代換。
3. 第 5(b) 要同時滿足一個全稱句為真、一個存在句為假，需要仔細枚舉 [2,10] 中的質數與 mod 5 餘 3 的數。
4. 第 12 題要對複數矩陣做 unitary 對角化，並注意特徵值的排序要求。

準備建議

• LU 分解與基本矩陣（109 第 7、8 題共 15 分）是交大線代的固定考點
• 齊次座標與 3D 變換（109 第 10 題）是電腦圖學的基礎，在數學考科出現是交大的特色
• 擴展歐幾里得演算法（109 第 6 題）與模運算在交大、師大都考過
• Hermitian 與 unitary 對角化（109 第 11、12 題）要能處理複數矩陣，不只是實對稱