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

題型與配分

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

作答方式：先在試卷第一頁自行繪製答案表格再填入。題目明訂「答案需化至最簡（分數請有理化或化為最簡分數），未以最簡分數表示不予給分」。答案填進表格，卷面沒有要求寫推導過程。

離散數學考點（1–5）

• 第 1 題｜2D random walk，從 (0,0) 出發，每步可走四個斜向或原地不動，問 n 步後可能狀態數
• 第 2 題｜函數計數加模運算：A 為 {1..5}→{1..6} 的所有函數所成集合，N 為 A→{1..9} 的函數個數，求 N mod 11，題目中會出現指數塔
• 第 3 題｜三階線性遞迴 a_n = 6a_n−1 − 11a_n−2 + 6a_n−3 的通解
• 第 4 題｜承上題，寫出 generating function 的 partial fraction 分解
• 第 5 題｜x₁+⋯+x₁₂ ≤ 6 的非負整數解個數再取 mod 11

線性代數與最佳化考點（6–10）

• 第 6 題｜三元齊次線性系統有非零解的 λ 條件
• 第 7 題｜A = [[4,3],[1,2]]，求 A²⁰⁰⁴ 四個元素和除以 5²⁰⁰⁴
• 第 8 題｜minimum-norm least-squares solution
• 第 9 題｜給定 positive semidefinite 矩陣 A，在 nuclear norm 受限（‖X‖\* ≤ c）下最小化 trace(AX)，問最佳解 X
• 第 10 題｜relative smoothness：f 相對於 g 為 L-smooth 的定義（∇²(Lg − f) positive semidefinite），求在給定單純形上最小的 L

作答時要注意的地方

1. 答案填進表格，卷面沒有要求寫過程。
2. 答案要化到最簡，未化簡不給分。
3. 第 9、10 題的主題是 nuclear norm 與 relative smoothness，屬於凸優化與機器學習理論。
4. 第 3 題的初始條件印成「a₀ = 1, a₁ = 2, and a₁ = 2」，a₁ 出現兩次，依上下文第二個應為 a₂。

準備方向

• 前八題是離散與線代的基本題，先全部做完，再處理第 9、10 題。
• 模運算搭配大指數，115 第 2、5 題都用到，113、114 也考過。
• least squares 解與最小 norm 解，113、115 連兩年出現。
• 矩陣冪次、pseudo-inverse、positive semidefinite 矩陣。
• 若有餘力，可以看一下 nuclear norm 與 relative smoothness。