115 成大資工所考古題詳解｜數學考點分析

題型與配分

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

離散部分明訂「You should show how to get the answers in detail or obtain no credit.」

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

• 第 1 題｜5 個標號頂點的簡單 undirected graph，且沒有 isolated vertex：(a) 恰有一個 connected component（connected graph）的有幾個 (b) 恰有兩個 connected component 的有幾個
• 第 2 題｜資料中心的 4×5 圓柱格網路（4 層水平環、每層 5 個路由器；5 個直行也各成 4 元素環，每個路由器 degree 為 4），判斷它能否嵌入平面 PCB 而不交叉，題目明訂只能用 Euler's formula 與 girth-based 邊數上界論證
• 第 3 題｜衛星放在 Z³ 的整數座標，兩衛星可建立安全連線若中點也是整數格點：(a) 求最小的 N 使得任意 N 顆衛星必存在一組安全連線 (b) 改成「兩點座標總和為偶數」時的最小數量
• 第 4 題｜recurrence E_n = 4E_n−1 − 4E_n−2 + 2ⁿ + 3ⁿ（E₀ = 2、E₁ = 10），估計使 E_n > 10⁹ 的最小 n
• 第 5 題｜電子鎖的 Moore machine state diagram 設計，要畫圖、起始狀態用箭頭、Unlock 狀態用雙圓
• 第 5(a) 題｜「Header-Trailer」協定：開頭必須是 11（否則永久鎖定）、中間忽略、結尾為 00 才解鎖、解鎖後若破壞 00 結尾要重新監控
• 第 5(b) 題｜「Strict Rhythm」協定：header 後必須嚴格交替 0,1,0,1…、破壞節奏立刻永久鎖定、解鎖後任何輸入都觸發鎖定（一次性）

線性代數考點（6–7）

• 第 6 題（30%）｜LU 分解的複雜度與分塊加速
• 第 6(a) 題（10%）｜給典型的無 pivot LU 分解演算法，求其時間複雜度
• 第 6(b) 題（10%）｜給基於 block matrix 乘法的加速版（內含 SIMULTIPLY 與遞迴的 SISOLVE），求其複雜度
• 第 6(c) 題（10%）｜用 (b) 的方法對給定矩陣實際做一次 LU 分解，要列出關鍵中間結果才給滿分
• 第 7 題（20%）｜A ∈ R^m×n（m > n）且 rank deficient，A^TA 為 positive semidefinite
• 第 7(a) 題（10%）｜證明 λ > 0 時 A^TA + λI 是 positive definite
• 第 7(b) 題（10%）｜推導某個最佳化問題的 closed-form solution

作答時要注意的地方

1. 離散部分要寫出詳細過程，否則不給分。
2. 第 2 題明訂只能用 Euler's formula 與 girth 邊數上界論證。
3. 第 5 題要實際畫出兩個 state diagram。
4. 第 6 題 30 分，是全卷配分最高的一題。

準備方向

• finite state machine 的設計：113 第 4 題、114 第 1 題、115 第 5 題，Moore 與 Mealy machine。
• planar graph 的 Euler's formula 與邊數上界：109 第 6 題、115 第 2 題。
• pigeonhole principle：109 第 4 題、110 第 2(b) 題、115 第 3 題。
• 非齊次 recurrence：112、113、114、115 年各一題。
• 最佳化問題的 closed-form solution 與正則化（115 第 7 題）。
• LU 分解與 block matrix：108 第 2 題、115 第 6 題。