106 交大資工所考古題詳解｜數學考點分析

題型與配分

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

作答規定（106、107 年皆有）：「First you need to write down your answers clearly and then explain how to compute the answers. You also need to answer the questions in order. Do not jump around.」

離散數學考點（1–6）

• 第 1 題（15%）｜(a) 10% 把兩個關於質數的敘述翻譯成邏輯式（可用 IsPrime(x) predicate）：「每個大小為 10⁸ 的區間都有質數」與「有無限多對相差不超過 10⁸ 的相鄰質數」 (b) 5% 這兩個敘述邏輯上等價嗎？哪一個必定為假？為什麼
• 第 2 題（10%）｜n = 2^k 時兩個 n×n 矩陣相乘：(a) 5% 描述一個漸進更快的乘法方法 (b) 5% 用 recurrence relation 分析複雜度
• 第 3 題（10%）｜每個人從 {1,…,n} 中任選 n_i 個相異整數：(a) 5% 兩人各選 k 個時，保證至少有一個共同整數的最大 k (b) 5% 給定具體人數與選數，求恰好共有一個共同整數的組合數
• 第 4 題（5%）｜給一個 directed graph 表示的關係 L，定義 i ~ j 若且唯若 i 與 j 之間沒有任何 L 關係，問 ~ 的 0-1 矩陣中有幾個 1
• 第 5 題（5%）｜判斷兩個圖是否 isomorphic，要給出 isomorphism 或嚴謹論證不存在
• 第 6 題（5%）｜解 recurrence a_n = 4a_n−1 − 4a_n−2（a₀ = 4、a₁ = 4）

線性代數考點（7–13）

• 第 7 題（4%）｜A 為非 symmetric 方陣時，判斷 B = A − A^T 與 C = (I+A)(I−A^T) 各屬於 symmetric、skew-symmetric 或皆非
• 第 8 題（10%）｜(a) 5% A 為 4×5、B 為 5×7 且 AB = 0，若 rank(B) = 2，求 rank(A) 的最大可能值 (b) 5% A = uv^T + vw^T + wu^T，若 x₁u + x₂v + x₃w = 0 有非零解，求 rank(A) 的最大值
• 第 9 題（6%）｜把向量 x 分解成 x_r ∈ C(A^T)（row space）與 x_n ∈ N(A)（null space）兩部分
• 第 10 題（5%）｜給三個點，用 least squares 法配一條直線 b = C + Dt，求誤差平方和 ‖e‖²
• 第 11 題（10%，10 個是非題）｜線代判斷：linear operator 是否必為 injection、orthogonal matrix 是否必有 eigenvalue 1、Markov matrix 是否必有 eigenvalue 1、projection matrix 的 eigenspace、singular matrix 是否永不 diagonalizable、實 symmetric matrix 的 eigenvalue 與 eigenvector、pivot 乘積是否等於 eigenvalue 乘積、symmetric matrix 能否與非 symmetric matrix similar、AA^T = A^TA 時 A 與 A^T 是否有相同 eigenvalue、singular value 是否皆為非負實數
• 第 12 題（5%）｜證明 det([[A,B],[C,D]]) = det(A)·det(D − CA⁻¹B)
• 第 13 題（10%）｜三個政黨的世代轉移機率，求長期 steady state

作答時要注意的地方

1. 卷面規定先寫答案再說明如何算出，且必須依序作答，不要跳題。
2. 第 1(b) 要回答兩個敘述是否等價、哪一個必定為假，並說明理由。
3. 第 11 題 10 個是非題共 10 分。
4. 第 12 題 5 分，是證明題。

準備方向

• Markov chain 的 steady state（106 第 13 題）。
• 矩陣乘法的加速與 recurrence 分析（106 第 2 題）。
• 線代是非判斷題：106 第 11 題 10 分，107 第 10–14 題 25 分。