113 中興資工所考古題詳解｜數學考點分析

題型與配分

全卷 2 頁、15 大題、100 分，簡章規定不可使用計算機。全部是申論題，卷面沒有計分規則的標示。

離散數學考點（1–10，各 5%）

• 第 1 題｜說明 Sieve of Eratosthenes 的概念
• 第 2 題｜說明 Kleene's Theorem 的概念
• 第 3 題｜A₁ = {∅, {∅}}，A_n = {∅, A_n−1, {A_n−1}}，計算 |A₁|² + … + |A_n|² + |P(A₁)| + … + |P(A_n)| + |A₂ − A₁| + … + |A_n − A_n−1|
• 第 4 題｜用紅、白兩色塗 2×4 棋盤的八個方格，有幾種塗法
• 第 5 題｜x₁ + x₂ + x₃ + x₄ = 10 的非負整數解個數
• 第 6 題｜給一張圖的 incidence matrix A 與 B = [1 0 0 0 0]，求 A 與 B^T 的 Boolean product
• 第 7 題｜六個權重 a–f 分別是 f(x) = (x² + x³ + x⁴ + …)⁴ 在指定次方的係數，建構 optimal binary prefix code
• 第 8 題｜用反證法搭配 resolution 完成證明：三個前提是至少一人被錄取、A 錄取且 B 未錄取則 C 必錄取、B 錄取則 C 必錄取，結論是 C 一定被錄取
• 第 9 題｜凱撒密碼 y = (x + 12) mod 26：(a) 2% 明文 discrete 轉密文；(b) 3% 密文 ymftqymfulq 轉明文
• 第 10 題｜給一段三層巢狀迴圈的 pseudo code，求 Big-O 時間複雜度

線性代數考點（11–15，各 10%）

• 第 11 題（10%）｜給 R⁴ 中四個 column vector 組成的集合 S，判斷是否 linearly independent
• 第 12 題（10%）｜求一個 5×5 矩陣的 determinant，矩陣中有大量的 0
• 第 13 題（10%）｜給 3×3 矩陣 A：(a) 證明 A diagonalizable；(b) 求 A¹⁰⁰
• 第 14 題（10%）｜A、B 為 n×n orthogonal matrix、C = AB，問 C 的 inverse 是否也是 orthogonal matrix
• 第 15 題（10%）｜u = (3, 1, −1)^T，W 是 x₁ + 2x₂ − x₃ = 0 的解集合：(a) 求 W 的 orthogonal projection 矩陣 P_W；(b) 求唯一的 w ∈ W 與 z ∈ W⊥ 使 u = w + z

作答時要注意的地方

1. 簡章規定不可使用計算機，卷首另標示全卷 2 頁。
2. 前 10 題每題只有 5 分，第 1、2 題要求說明概念。
3. 第 9 題註明 One word wrong and all wrong，(a)(b) 都是整題全對才給分。
4. 第 11 題題目附有提示，要求先找出由 S 的向量組成之矩陣的 rank。
5. 第 14 題註明 Proof is necessary, otherwise no credits will be given，要寫出證明。
6. 第 13 題 (a) 要求證明，(b) 要求 A¹⁰⁰。

準備方向

• 非負整數解的個數：113 第 5 題，108 填空 ③、115 第 1 題也有。
• Huffman 編碼：113 第 7 題，110 資訊概論第 8-D 題、113 軟體第 3 題也有。
• 巢狀迴圈的複雜度：113 第 10 題，112 第 8 題考 Master Theorem。
• formal language：113 第 2 題考 Kleene's theorem，112 第 11 題考 grammar。
• 模運算與密碼：113 第 9 題，109 第 7 題、111 第 4、9 題、115 第 5 題也有。
• linearly independent 判斷：113 第 11 題，108 第 1 題、115 第 12 題也有。
• diagonalization 與矩陣高次冪：113 第 13 題，108 第 2(c) 題也有 diagonalization。
• orthogonal matrix 的性質：113 第 14 題，111 選擇第 1 題、114 第 14 題也有。
• orthogonal projection 矩陣與 orthogonal decomposition：113 第 15 題，112 第 6 題、114 第 12 題與計算題也有。