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

題型與配分

全卷 3 頁、12 題、100 分。

作答方式：「請在答案卷可作答部分的第一頁繪製十二列的表格並填入各題的答案」。自繪表格填答在 108、110、114、115 都有。

離散數學考點（1–7）

• 第 1 題（5%）｜給一張 undirected graph，寫出四個構成 independent set 的節點
• 第 2 題（5%）｜長度 n 的二進位迴文數有幾個
• 第 3 題（5%）｜推導 binomial coefficient 等式中的 A、B
• 第 4 題（10%）｜推導另一組 binomial coefficient 等式中的 A、B
• 第 5 題（10%）｜recurrence a_n+2 = a_n+1 + 2a_n 的解為 A(−X)ⁿ + B·Yⁿ，要以任意初始條件 a₀、a₁ 表示 A、B、X、Y
• 第 6 題（10%）｜方程式的正整數解個數，附帶 x_i > n_i 的下界條件
• 第 7 題（5%）｜判斷給定的邏輯式是否為 tautology，並說明理由

線性代數考點（8–12）

第 8 到 10 題都是「以下五個敘述有幾個正確」，只填個數。

• 第 8 題（10%）｜vector space 的基本性質：S ⊆ U 與 span(S) ⊆ U、linearly dependent 集合中的向量與其餘向量的 span、任意 vector space 是否都有 basis、inner product space 是否都有 orthonormal basis、rank-nullity theorem 在無限維時是否成立
• 第 9 題（10%）｜矩陣的 rank 與可逆性：齊次方程組的解集合、A 與 A\ 的可逆性、rank(A) 與 rank(A^T)、nullity(A) 與 nullity(A⁻¹)、det(A\) 與 det(A) 的關係
• 第 10 題（10%）｜diagonalizable 與 eigenspace：eigenspace direct sum 與 diagonalizable、normal matrix（A\A = AA\）的 eigenspace、實 symmetric matrix 的 characteristic polynomial、Hermitian matrix 的 eigenvalue、unitarily equivalent 矩陣的 tr(A\*A)
• 第 11 題（10%）｜給一個 4×4 整數矩陣，問它的 inverse 中有幾個 0
• 第 12 題（10%）｜給出從 R³ 到 R² 的所有 linear transformation 所構成 vector space 的一組 basis

作答時要注意的地方

1. 第 8 到 10 題合計 30 分，只問個數，五個敘述都要判斷正確才會對。
2. 第 8 題有一個敘述涉及無限維 vector space。
3. 第 11 題要算出 4×4 inverse 的每個元素再數 0。
4. 第 6 題的下界是 x_i > n_i，與一般的 x_i ≥ n_i 寫法不同。

準備方向

• 敘述判斷題準備成「真或假，加上反例」的表，108 年的問法只填個數。
• normal matrix、Hermitian、unitary、unitarily equivalent 這組概念在 108、110、112 都出現。
• rank-nullity theorem 在無限維 vector space 的情形，108 第 8 題有考。
• 練習時用自繪表格的格式作答。