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

題型與配分

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

離散部分明訂「請說明如何求解過程，只寫答案不予計分」。

線性代數考點（1–3）

• 第 1 題（15%）｜給一個 4×4 循環矩陣（circulant matrix），已知兩個特徵向量 (1,1,1,1)^T 與 (1,i,i²,i³)^T，求對應的特徵值 λ₀ 與 λ₁。循環矩陣的特徵值就是 c₀ + c₁ω + c₂ω² + c₃ω³（ω 為單位根）
• 第 2 題（20%）｜給三對角矩陣 A：(a) 10% 計算 LU 分解 (b) 10% 說明為什麼 A 必為正定（用主子式、或 LU 的主元皆正）
• 第 3 題（15%）｜p(x) = −x³ + cx² + (c+3)x + 1，C 為某矩陣、A 為另一矩陣：(a) 10% 計算 A⁻¹CA (b) 5% 說明 C 是 p(x) 的 companion matrix，並用 (a) 的結果證明 p(x) 無論 c 為何值都只有實根（關鍵：A⁻¹CA 若為對稱矩陣，則其特徵值皆實）

離散數學考點（4–6）

• 第 4 題（15%）｜給集合 S 上關係 R 的邏輯矩陣 M：(a) 5% 要檢查哪些性質才能判斷是否為偏序 (b) 5% 畫出該序的 Hasse 圖 (c) 5% 找出所有不可比較（incomparable）的元素對
• 第 5 題（15%）｜解耦合的遞迴方程組：A(n) = 3A(n−1) + 2B(n−1)、B(n) = A(n−1) + B(n−1)，A(0) = 15、B(0) = 0。要寫成矩陣形式後對角化，或消去法化為單一二階遞迴
• 第 6 題（20%）｜兩張圖的最大流與最小割：(a) 10% 圖 (a) 的最大流與對應的最小割 (b) 10% 圖 (b) 的最大流與最小割 —— 圖 (b) 的標號在節點上，代表節點容量，要先做節點拆分才能用標準最大流演算法

這份考卷的難點

1. 第 3(b) 的實根證明是全卷最巧妙的一題：透過相似變換把 companion matrix 變成對稱矩陣，再用「實對稱矩陣的特徵值皆為實數」得證。
2. 第 6(b) 的節點容量要把每個節點拆成 in／out 兩點、中間連容量為節點容量的邊 —— 沒看出來就會直接用邊容量算錯。
3. 第 5 題的耦合遞迴要轉成矩陣 [[3,2],[1,1]] 的冪次問題，再對角化求封閉解。
4. 第 1 題的循環矩陣要知道它的特徵向量必為單位根向量，特徵值是係數的離散傅立葉變換。

準備建議

• 循環矩陣與單位根（108 第 1 題、110 第 6 題連兩年）是成大線代的招牌，特徵值公式要記住
• 最大流與最小割（108 第 6 題 20 分）在成大數學與軟體兩科都出現，節點容量的拆分技巧務必會
• LU 分解與正定判斷（108 第 2 題）是線代的基本功
• 耦合遞迴方程組（108 第 5 題）要能轉成矩陣冪次，與馬可夫鏈的手法相同