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

題型與配分

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

離散部分明訂：「You should show how to get the answers in detail or obtain no credit.」—— 成大十年不變的鐵律。

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

• 第 1 題｜5 個標號頂點的簡單無向圖，且沒有孤立點：(a) 恰有一個連通元件（連通圖）的有幾個 (b) 恰有兩個連通元件的有幾個。要用排容原理或已知的連通標號圖計數
• 第 2 題｜資料中心的 4×5 圓柱格網路（4 層水平環、每層 5 個路由器；5 個直行也各成 4 元素環，每個路由器度數為 4），判斷它能否嵌入平面 PCB 而不交叉。題目明訂只能用 Euler 公式與 girth-based 邊數上界論證（girth = 4，所以 e ≤ 2v − 4 = 36，而實際 e = 40 > 36，故非平面）
• 第 3 題｜衛星放在 Z³ 的整數座標，兩衛星可建立安全連線若中點也是整數格點：(a) 求最小的 N 使得任意 N 顆衛星必存在一組安全連線（2³ + 1 = 9，用奇偶性的鴿籠原理） (b) 改成「兩點座標總和為偶數」時的最小數量（3）
• 第 4 題｜遞迴式 E_n = 4E_n−1 − 4E_n−2 + 2ⁿ + 3ⁿ（E₀ = 2、E₁ = 10），估計使 E_n > 10⁶ 的最小 n。特徵根 2 為重根，且 2ⁿ 與特徵根重疊，特解要取 n²·2ⁿ
• 第 5 題｜電子鎖的 Moore machine 狀態圖設計（要畫圖、起始狀態用箭頭、Unlock 狀態用雙圓）：
• (a)｜「Header-Trailer」協定：開頭必須是 11（否則永久鎖定）、中間忽略、結尾為 00 才解鎖、解鎖後若破壞 00 結尾要重新監控
• (b)｜「Strict Rhythm」協定：header 後必須嚴格交替 0,1,0,1…、破壞節奏立刻永久鎖定、解鎖後任何輸入都觸發鎖定（一次性）

線性代數考點（6–7，各 25%）

• 第 6 題（30%）｜LU 分解的複雜度與分塊加速：
• (a) 10%｜給典型的無主元 LU 分解演算法，求其時間複雜度（O(n³)）
• (b) 10%｜給基於分塊矩陣乘法的加速版（內含 Strassen 式的 SIMULTIPLY 與遞迴的 SISOLVE），求其複雜度（O(n^log₂7)）
• (c) 10%｜用 (b) 的方法對給定矩陣實際做一次 LU 分解，要列出關鍵中間結果才給滿分
• 第 7 題（20%）｜A ∈ R^m×n（m > n）且秩虧損，A^TA 為半正定：
• (a) 10%｜證明 λ > 0 時 A^TA + λI 是正定
• (b) 10%｜推導某個最佳化問題的封閉解。這就是 ridge regression（Tikhonov 正則化），解為 (A^TA + λI)⁻¹A^Tb

這份考卷的難點

1. 第 6 題（30 分）是全卷最大的一題，而且 (b) 要從給定的 pseudo-code 看出它用了 Strassen 的七次乘法，才能得出 O(n^log₂7)。
2. 第 5 題要實際畫出兩個狀態機，(b) 的「嚴格交替 + 一次性解鎖」狀態數會比 (a) 多不少，容易漏掉某個轉移。
3. 第 2 題明訂只能用 Euler 公式與 girth 邊界，不能說「看起來像 K₅ 的細分」—— 要算出 girth = 4 對應的 e ≤ 2v−4。
4. 第 4 題的特解形式：4E_n−1 − 4E_n−2 的特徵根是重根 2，而右式含 2ⁿ —— 特解必須取 cn²·2ⁿ。

準備建議

• 115 年全面情境化（資料中心、衛星網路、電子鎖），但底層都是標準題：平面圖判定、鴿籠原理、遞迴式、有限狀態機
• Ridge regression 的封閉解（115 第 7 題）是機器學習的基礎，近年在各校數學考科都開始出現
• 有限狀態機的設計在成大 113、114、115 連三年出現，是明顯的趨勢，Moore 與 Mealy 機的差別要清楚
• Euler 公式的 girth 推廣（girth = g 時 e ≤ g(v−2)/(g−2)）比 e ≤ 3v−6 更一般，115 年直接考