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

題型與配分

全卷 2 頁、10 題、100 分，每題 10 分。

作答方式：「請將答案填入試卷內所附的表格中」。111、112 兩年是選擇題，113 年回到填表。

離散數學考點（1–5，各 10%）

• 第 1 題｜從 {"A","B"}ⁿ 到 {1,2,3} 的函數個數 z，求 z mod 7，題目中會出現指數塔
• 第 2 題｜給一個布林式，求滿足的指派個數（satisfying assignments）
• 第 3 題｜計算 Euler's phi function φ(90)
• 第 4 題｜recurrence a_n = −a_n−1 + 12a_n−2（a₀ = 3、a₁ = 2）的解
• 第 5 題｜給一張圖，分四小題問：(4 分) chromatic number、(4 分) 最大 independent set 的大小、(1 分) 是否為 Eulerian、(1 分) 是否為 Hamiltonian

線性代數考點（6–10，各 10%）

• 第 6 題｜給 augmented matrix [A|b]，S 為使 ‖Ax − b‖ 最小的 x 所成集合（least squares 解），求其中最小 norm 的平方
• 第 7 題｜給有理數四元組的兩組集合 R、S span 的 subspace U、W，求滿足 W = U ⊕ V 且 U ⊥ V 的 subspace V
• 第 8 題｜F 為 finite field Z₃（mod-3 加法與乘法），若二次多項式 p(x) = a + bx + cx² 滿足 p(i) = i + 2 對每個 i ∈ F 成立，求 (a, b, c)
• 第 9 題｜已知 linear operator T 的 characteristic polynomial f_T(x) = x⁴ − 2x² + 1，求 operator S = T⁵ − 2T⁴ − T³ + 4T³ − T² − 2T 的 rank(S) 以 rank(T) 表示
• 第 10 題｜U 為 2×2 self-adjoint 複矩陣、V 為 3×3 實矩陣（皆為實數 field 上的 vector space），給定一組 singular value，求 T 的 adjoint 的 pseudo-inverse 的所有 singular value 之乘積

作答時要注意的地方

1. 第 10 題同時用到 singular value、adjoint operator、pseudo-inverse 三個概念。
2. 第 5 題四個小題的配分是 4、4、1、1 分。

準備方向

• least squares 解與最小 norm 解在 113、115 連兩年出現。
• SVD 與 pseudo-inverse 的關係，113 第 10 題考。
• Euler φ 函數在 113 第 3 題。
• 模運算搭配大指數在 113、114、115 連三年出現。
• 圖論的 chromatic number、最大 independent set、Eulerian、Hamiltonian 在 113 第 5 題一次問完，四個定義都要記清楚。