111 成大資工所考古題詳解｜數學考點分析

題型與配分

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

離散數學考點（1–5）

• 第 1 題（10%）｜長度 20 的位元串中最多有 19 個 1 的有幾個，答案要表示成 A^B + C 的形式，分別填 A、B、C
• 第 2 題（10%）｜(u,v) 是 connected graph G 中權重最小的邊，證明 (u,v) 屬於某棵 minimum spanning tree
• 第 3 題（10%）｜給集合 A、B、C，計算 2^c + b + a，其中 a = |P(A)|、b = |A×B|、c = |P(C)|
• 第 4 題（10%）｜正 n 邊形的頂點：(a) 5% 能決定幾個四邊形 (b) 5% 若四邊形的邊都不能是多邊形的邊，有幾個（n ≥ 8）
• 第 5 題（10%）｜求兩張圖的 chromatic number，不需說明

線性代數考點（6–9）

四題全部是證明題：

• 第 6 題（20%）｜Hermitian matrix A 的 eigenvalue λ₁ ≥ … ≥ λ_n、orthonormal eigenvector u₁…u_n，Rayleigh quotient ρ(x) = xᴴAx / xᴴx
• 第 6(a) 題（10%）｜若 x = c₁u₁ + … + c_nu_n，證明 ρ(x) 可表示成 eigenvalue 的加權平均
• 第 6(b) 題（5%）｜證明 λ_n ≤ ρ(x) ≤ λ₁
• 第 6(c) 題（5%）｜證明 ρ(x) 的最大值與最小值各是多少
• 第 7 題（10%）｜Frobenius norm ‖A‖_F 與 trace：(a) 5% 證明 ‖A‖²_F = tr(A^TA) (b) 5% 證明 ‖A+B‖²_F = ‖A‖²_F + 2tr(A^TB) + ‖B‖²_F
• 第 8 題（10%）｜A 為 symmetric matrix 時，證明 e^A 是 symmetric 且 positive definite
• 第 9 題（10%）｜A 為 singular 方陣時，證明 A^TA 是 positive semidefinite 但不是 positive definite

作答時要注意的地方

1. 線代第 6 至 9 題全是證明題，合計 50 分。
2. 第 2 題要證明的是 minimum spanning tree 的性質。
3. 第 5 題明訂不需說明。
4. 第 6 題 20 分，是全卷配分最高的一題。

準備方向

• Rayleigh quotient 與 eigenvalue 的極值（111 第 6 題）。
• Frobenius norm 與 trace（111 第 7 題）。
• matrix exponential：109 第 3 題、111 第 8 題。
• positive semidefinite 與 positive definite 的判定（111 第 9 題）。
• minimum spanning tree 的性質證明（111 第 2 題）。
• 正多邊形頂點的 combinatorial counting（111 第 4 題）。