111 師大資工所數學考點分析

題型與配分

科目「數學基礎」，適用系所：資訊工程學系，全卷 2 頁、10 大題、100 分。

申論卷、寫在答案卷上、標明題號、不必抄題、沒有倒扣。

111 年把離散排在線代之前（110 年是線代在前）。師大的順序每年可能不同，進場先掃過整份卷子再決定作答順序。

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

• 第 1 題（10%）｜分治遞迴（Master Theorem）：f(n) = 5f(n/3) + 8、f(1) = 2，求 n = 3^k 時的 f(n)。用反覆展開得 f(3^k) = 2·5^k + 8(5^k−1)/4，也就是 Θ(n^log₃5)
• 第 2 題（10%）｜排列與多項式定理
• (1) WANNANNASSA 的相異排列數（11 個字母：A×5、N×4、W×1、S×2 → 要先數對每個字母的重複次數，再算 11!/(5!4!1!... )）
• (2) (2x − 3y)²⁰⁰ 中指定項的係數 → C(200,k)·2^200−k·(−3)^k
• 第 3 題（10%）｜關係的複合與部分函數
• (1) 給 S 與 R 的 0-1 矩陣，求 R∘S 的矩陣（布林矩陣乘法，注意複合的左右順序）
• (2) 對 f : Z×Z → Z、f(m,n) = m/n，寫出 domain、codomain、domain of definition、undefined 的集合，並判斷是否為全函數（total function）（不是，n = 0 時無定義）
• 第 4 題（10%）｜邏輯與數論
• (1) 論域為所有命題時，把「兩個恆真式的合取仍是恆真式」寫成帶量詞的邏輯式
• (2) 求 7¹²³ mod 11 → 用費馬小定理：7¹⁰ ≡ 1 (mod 11)，123 = 12×10 + 3，所以答案是 7³ mod 11 = 343 mod 11 = 2
• 第 5 題（10%）｜Hamilton 迴路與路徑：對給定的圖
• (1) 判斷是否有 Hamilton circuit，有就找出來、沒有就證明為什麼不存在
• (2) 判斷是否有 Hamilton path，同樣要給出或論證
• 關鍵：「沒有」的情形必須論證（常用度數 1 的頂點、割點、二分圖兩側不等大等理由）

線性代數考點（6–10，50%）

• 第 6 題（8%）｜由線性相依關係反推 RREF：u、v 線性獨立，a₁ = u、a₂ = u+2v、a₃ = 2u+2v、a₄ = u
• (1) 4%：求 A = [a₁ a₂ a₃ a₄] 的 RREF（a₁ 與 a₂ 是 pivot，a₃ = a₁ + ... 、a₄ = a₁）
• (2) 4%：求 rank 與 nullity（rank = 2、nullity = 2）
• 第 7 題（8%）｜行列式的列運算：已知 det A = −7，求兩個由 A 的列做線性組合得到的矩陣的行列式
• (a) 列 1 加上 2×列 3、列 2 乘 3、列 3 乘 2 再減 5×列 2 → 只有「乘常數」會改變行列式
• (b) 交換與變號的組合
• 第 8 題（10%）｜求 B-矩陣表示：給 R³ 上的線性算子 T 與基底 B，求 [T]_B = [[T(b₁)]_B [T(b₂)]_B [T(b₃)]_B]
• 第 9 題（12%）｜正交對角化：給對稱的線性算子 T，找單位正交基底 B 使 [T]_B 為對角矩陣，並寫出 [T]_B。做法是求 T 的標準矩陣 → 求特徵值與特徵向量 → 正交化
• 第 10 題（12%）｜正交投影矩陣：W 是兩個方程式的解集（即 R⁴ 的一個二維子空間）
• (1) 8%：求 W 的正交投影矩陣 P_W（先找 W 的基底，再用 P = A(A^TA)⁻¹A^T）
• (2) 4%：求 W 中離 v 最近的向量 w（就是 P_W v）

這份考卷的難點

1. 第 9 題把「正交對角化」包裝成「找基底使 [T]_B 為對角」：要先看出 T 的標準矩陣是對稱的（否則不保證存在單位正交的對角化基底），再做完整的特徵分解與正交化。12 分裡包含三個步驟，任一步錯就全錯。
2. 第 3(1) 的複合順序：R∘S 表示「先做 S 再做 R」，矩陣要寫成 M_S ⊙ M_R（布林積，注意課本慣例），左右順序寫反是最常見的錯誤。
3. 第 5 題「證明不存在」比「找出來」難——要能提出結構性的理由（例如某個頂點度數為 1、或移除 k 個頂點後產生超過 k 個連通分量）。
4. 第 2(1) 的 WANNANNASSA 要正確數出每個字母的重複次數，數錯一個字母整題就錯。

準備建議

• 正交投影矩陣 P_W = A(A^TA)⁻¹A^T 與「W 中離 v 最近的向量」是師大六年全中的題型（110、111、112、113、114、115），這 10–12 分等於每年送分
• 費馬小定理求大冪次模餘（111 第 4(2) 題）與中國剩餘定理（113、114、115）構成師大的數論主線
• Master Theorem／分治遞迴（111 第 1 題）在師大數學基礎只出現這一次，但在師大軟體基礎是常客
• 行列式對三種列運算的反應（110 第 1 題、111 第 7 題、113 第 2(a) 題）要背成一張表
• 「證明某圖沒有 Hamilton circuit」的標準論證方式要準備三種：度數論證、割點論證、二分圖論證