113 中興資工所數學考點分析

題型與配分

系所「資訊工程學系 甲組」（113 年起系名由「資訊科學與工程學系」改為「資訊工程學系」），科目：離散數學與線性代數，本科目試題共 2 頁、15 大題、100 分，「不可以」使用計算機。

全部申論、寫在答案卷、沒有倒扣（與 112 年一致）。

前 10 題「每題 5 分」的快問快答格式是 113 年獨有，涵蓋面極廣但每題深度不大——時間分配上前半應該快速通過，把時間留給後面的線代。

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

• 第 1 題｜說明「Eratosthenes 篩法」的概念——純觀念題，要寫出「從 2 開始逐一劃掉倍數、只需篩到 √n」
• 第 2 題｜說明「Kleene 定理」的概念——正規語言 ⟺ 有限狀態自動機可辨識 ⟺ 正規表達式可描述。這是形式語言的內容，其他七校的數學科都不考
• 第 3 題｜遞迴定義集合的基數運算：A₁ = {∅, {∅}}、A_n = {∅, A_n−1, {A_n−1}}，求一長串 |A_i|、|P(A_i)|、A_i − A_i−1 的組合值。關鍵：n ≥ 1 時 |A_n| 恆為 3（n ≥ 2）
• 第 4 題｜著色計數：用紅白兩色塗 2×4 棋盤的八格，有幾種塗法 → 2⁸ = 256
• 第 5 題｜非負整數解：x₁+x₂+x₃+x₄ = 10 的非負整數解個數 → C(13,3) = 286
• 第 6 題｜布林積（Boolean product）：給圖的關聯矩陣 A 與 B = [1 0 0 0 0]，求 A ⊙ B^T
• 第 7 題｜Huffman 編碼：權重取自 f(x) = (x²+x³+x⁴+…)⁴ 在指定次方的係數——要先算出生成函數的係數，再建 Huffman 樹
• 第 8 題｜反證法＋解消原理（resolution）：三個前提（至少一人錄取、若 A 錄取但 B 未錄取則 C 必錄取、若 B 錄取則 C 必錄取），推出「C 一定錄取」。要用 resolution 的形式寫證明
• 第 9 題｜凱撒密碼：y = (x+12) mod 26
• (a) 2%：明文 "discrete" → 密文
• (b) 3%：密文 "ymftqymfulq" → 明文
• 注意題目註明「One word wrong and all wrong」（錯一個字母整題零分）
• 第 10 題｜巢狀迴圈的 Big-O：三層迴圈且內層起點依賴外層變數，判斷總時間複雜度

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

• 第 11 題（10%）｜線性獨立判斷：四個行向量構成的集合 S 是否線性獨立。題目直接給提示「求由 S 組成的矩陣 A 的 rank」
• 第 12 題（10%）｜5×5 行列式：矩陣有大量 0，要沿零最多的列／行展開，禁用計算器下不能硬算
• 第 13 題（10%）｜對角化與高次冪
• (a) 證明 A 可對角化（求出三個相異特徵值即可）
• (b) 求 A¹⁰⁰ = PD¹⁰⁰P⁻¹
• 第 14 題（10%）｜正交矩陣的封閉性證明：A、B 為正交矩陣、C = AB，證明 C⁻¹ 也是正交矩陣。題目明寫「Proof is necessary, otherwise no credits will be given」——要寫出 (AB)^T(AB) = B^TA^TAB = I 的完整推導
• 第 15 題（10%）｜正交投影與正交分解：u = (3,1,−1)^T，W 是 x₁ + 2x₂ − x₃ = 0 的解集合
• (a) 求 W 的正交投影矩陣 P_W
• (b) 求唯一的 w ∈ W 與 z ∈ W⊥ 使 u = w + z

這份考卷的難點

1. 第 3 題的遞迴集合極易算錯：A₁ = {∅, {∅}} 有 2 個元素，但 A₂ = {∅, A₁, {A₁}} 有 3 個元素，之後每個 A_n 都是 3 個元素。題目把 |A_i|、|P(A_i)|、差集三種運算串成一長串算式，任何一項算錯整題就錯。
2. 第 7 題要先展開生成函數再做 Huffman：(x²+x³+x⁴+…)⁴ = x⁸/(1−x)⁴，要取出 x⁸、x¹⁰、x¹²、x¹⁴ 等指定次方的係數當作權重，然後才能建樹。兩個步驟都要對。
3. 第 9 題的「錯一個字母整題零分」：凱撒密碼本身不難，但 11 個字母的解密要全部正確，禁用計算器下要逐字母手算 (x−12) mod 26。
4. 第 2 題的 Kleene 定理在多數離散課本屬於「計算理論」章節，很多人根本沒讀過。5 分看似不多，但這類「說明概念」的題目寫不出來就是完全空白。

準備建議

• 113 的線代五題（11–15）全部是標準題型：線性獨立、行列式、對角化求高次冪、正交矩陣性質證明、正交投影——把這五題練熟等於穩拿 50 分
• 正交投影矩陣 P_W 與正交分解 u = w + z（113 第 15 題、114 第 12 題與計算題、115 甲組）三年連續出現，是中興線代近年的核心
• 形式語言與計算理論（113 第 2 題 Kleene 定理、112 第 11 題文法）是中興獨有，其他七校不考
• 凱撒密碼（第 9 題）的公式 y = (x + k) mod 26 要熟，解密時是 (y − k) mod 26
• Huffman 編碼（第 7 題）在中興數學與軟體考科都出現過（110 資訊概論第 8 題也考 Huffman 位元數）