111 成大資工所數學考點分析

題型與配分

編號 202，系所「電機資訊學院－資訊聯招」，科目：計算機數學，考試日期 111 年 2 月 19 日第 3 節，全卷 2 頁、9 題、100 分，不可使用計算機。

離散數學考點（1–5）

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

線性代數考點（6–9）

四題全部是證明題：

• 第 6 題（20%）｜Hermitian 矩陣 A 的特徵值 λ₁ ≥ … ≥ λ_n、正交歸一特徵向量 u₁…u_n，Rayleigh quotient ρ(x) = xᴴAx / xᴴx：
• (a) 10%｜若 x = c₁u₁ + … + c_nu_n，證明 ρ(x) = (|c₁|²λ₁ + … + |c_n|²λ_n) / (|c₁|² + … + |c_n|²)
• (b) 5%｜證明 λ_n ≤ ρ(x) ≤ λ₁
• (c) 5%｜證明 max ρ(x) = λ₁、min ρ(x) = λ_n
• 第 7 題（10%）｜Frobenius 範數‖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 為對稱矩陣時，證明 e^A 是對稱且正定（用對角化：e^A 的特徵值 e^λ > 0）
• 第 9 題（10%）｜A 為奇異方陣時，證明 A^TA 是半正定但不是正定

這份考卷的難點

1. 線代 50 分全是證明題，這在成大十年間是唯一一次。第 6 題的 Rayleigh quotient（20 分）需要完整寫出展開與不等式論證。
2. 第 4(b) 的環狀不相鄰選取：從 n 個頂點中選 4 個且兩兩不相鄰（含首尾相鄰），公式是 n/(n−4) · C(n−4,4)，不是一般的組合。
3. 第 2 題要證明 cut property，而不是直接引用 —— 標準做法是反證＋交換論證。
4. 第 9 題的「半正定但不正定」要同時證明 x^TA^TAx = ‖Ax‖² ≥ 0（半正定）與存在非零 x 使 Ax = 0（不正定）。

準備建議

• 111 年的線代全是證明，顯示成大要求的不只是計算能力 —— 常見定理的證明要能完整寫出
• Rayleigh quotient 與特徵值的極值性質（111 第 6 題 20 分）是線代的重要定理，也是 PCA 的理論基礎
• Frobenius 範數與 trace 的關係（111 第 7 題）在機器學習中常用，值得熟悉
• MST 的 cut property 證明（111 第 2 題）與軟體考科的 MST 題目相通