113 台大資工所數學考點分析
十題填表、每題 10 分。離散五題涵蓋計數、數論（Euler φ）與圖著色，線代五題則深入到有限體多項式、廣義逆與奇異值。
題型與配分
科目「數學（A）」（題號 313、節次 4），全卷 2 頁、10 題、100 分，每題 10 分。
作答方式：「請將答案填入試卷內所附的表格中」—— 回到填表形式（111、112 曾短暫改為選擇題）。
| 區段 | 題號 | 配分 |
|---|---|---|
| 離散數學 | 1–5 | 50% |
| 線性代數 | 6–10 | 50% |
離散數學考點（1–5，各 10%）
- 第 1 題｜從 {"A","B"}n 到 {1,2,3} 的函數個數 z，求 z mod 7。會出現指數塔，要用費馬小定理降冪
- 第 2 題｜給一個布林式，求滿足的指派個數（satisfying assignments）
- 第 3 題｜計算 Euler's phi function φ(90)（90 = 2·32·5，φ(90) = 90·(1/2)(2/3)(4/5) = 24）
- 第 4 題｜遞迴式 an = −an−1 + 12an−2（a0 = 3、a1 = 2）的解。特徵根為 3 與 −4
- 第 5 題｜給一張圖，分四小題問：(4 分) chromatic number、(4 分) 最大獨立集的大小、(1 分) 是否為 Eulerian、(1 分) 是否為 Hamiltonian
線性代數考點（6–10，各 10%）
- 第 6 題｜給增廣矩陣 [A|b]，S 為使 ‖Ax − b‖ 最小的 x 所成集合（最小平方解），求其中最小範數的平方。這是 least squares + minimum norm solution
- 第 7 題｜給有理數四元組的兩組集合 R、S 張成的子空間 U、W，求滿足 W = U ⊕ V 且 U ⊥ V 的子空間 V。這是正交補在 W 中的部分
- 第 8 題｜F 為有限體 Z3（mod-3 加法與乘法），若二次多項式 p(x) = a + bx + cx2 滿足 p(i) = i + 2 對每個 i ∈ F 成立，求 (a, b, c)。這是有限體上的插值
- 第 9 題｜已知線性算子 T 的特徵多項式 f_T(x) = x4 − 2x2 + 1，求算子 S = T5 − 2T4 − T3 + 4T3 − T2 − 2T 的 rank(S) 以 rank(T) 表示。要用 Cayley-Hamilton 把 S 化簡
- 第 10 題｜U 為 2×2 自伴複矩陣、V 為 3×3 實矩陣（皆為實數體上的向量空間），給定一組奇異值，求 T 的伴隨的偽逆的所有奇異值之乘積
這份考卷的難點
- 第 10 題（10 分）把奇異值、伴隨算子、偽逆三個概念串在一起，是全卷最難的一題。關鍵：偽逆的奇異值是原奇異值的倒數（非零者）。
- 第 8 題的有限體插值要在 Z3 上解三元一次聯立，模運算容易出錯。
- 第 1 題的指數塔 mod 7 要用費馬小定理把指數降到 mod 6。
- 第 9 題要先分解特徵多項式 x4−2x2+1 = (x2−1)2 = (x−1)2(x+1)2，再用 Cayley-Hamilton 化簡 S。
準備建議
- 最小平方解與最小範數解（113 第 6 題）在台大 113、115 連兩年出現，是近年的新重點
- 奇異值分解（SVD）與偽逆的關係（偽逆的奇異值是原奇異值的倒數）必須掌握
- Euler φ 函數與費馬小定理是離散數學的數論部分，台大 113、115 都考
- 圖論的四個基本量（chromatic number、最大獨立集、Eulerian、Hamiltonian）在 113 第 5 題一次考完，四個定義都要精確