113 交大資工所考古題詳解｜數學考點分析

題型與配分

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

離散數學考點（1–6）

• 第 1 題（5%）｜中文的邏輯推理題：醫院共 16 名醫生與護士，滿足四個條件（護士多於醫生、男醫生多於男護士、男護士多於女護士、至少一位女醫生），且把說話者排除後四條仍成立，問說話者的性別與職務
• 第 2 題（10%）｜(a) 5% 非遞減數列中 k 恰出現 k² 次，f(n) 定義為使 a_m = n 的最大 m，求 f(f(n)) (b) 5% 求所有滿足 √a + √b = √2009 的非負整數 a、b
• 第 3 題（10%）｜(a) 5% 把 Goldbach 猜想（每個大於 2 的偶數都是兩個質數之和）翻譯成邏輯式，只能用 ∀、∃、∧、∨、¬、→、↔ 與四則運算（除法是整數除法） (b) 5% 長度 10 的位元串中，含有五個連續 1 或五個連續 0 的有幾個
• 第 4 題（11%）｜格子圖上只能往右或往上走：(a) 3% 從 m 到 n 的路徑數 (b) 4% 不經過頂點 x 的路徑數 (c) 4% 定義關係 R 為「一步可達」，問 (P,R) 是否為 poset 並說明理由
• 第 5 題（6%）｜對兩個 Hasse 圖做 topological sort，各能得到幾種不同結果
• 第 6 題（8%）｜已知「連通平面簡單圖滿足 e ≤ 3v − 6」，用這個定理證明 connected planar simple graph（v ≥ 3）必有一個 degree 不超過 5 的頂點

線性代數考點（7–12）

• 第 7 題（12%）｜(a) 6% 求 4×4 矩陣的 A⁻¹ (b) 6% 求 PA = LU 分解（P 為 permutation matrix、L 為單位下三角、U 為 upper triangular）
• 第 8 題（8%）｜給四個點 (0,20)、(1,0)、(2,0)、(3,0)，用 least squares 法配二次多項式 b = C + Dt + Et²，求誤差平方和 ‖e‖²
• 第 9 題（5%）｜證明：A 可逆時 (A⁻¹)^T = (A^T)⁻¹。卷面寫著「不會寫請留白，答錯最多倒扣 5 分，扣至 7、8、9 題 0 分為止」
• 第 10 題（15%）｜(a) 5% 求 A 的 eigenvalue (b) 5% 求對應的 eigenvector (c) 5% 求 block matrix B = [[2A, 2A], [A, 3A]] 的 eigenvalue
• 第 11 題（5%）｜給矩陣 C = LL^T，求 lower triangular matrix L（Cholesky 分解）
• 第 12 題（5%）｜給 D = FᴴF，求 Hermitian matrix F

作答時要注意的地方

1. 第 6 題指定要用題目給的定理來證明。
2. 第 9 題答錯倒扣最多 5 分，且會扣到第 7、8、9 題整組 0 分為止。
3. 第 1 題的條件包含「排除說話者後四條仍成立」。

準備方向

• Cholesky 分解（C = LL^T）與 LU、PA = LU 分解：109、113 都有。
• 邏輯式的翻譯（Goldbach 猜想、質數敘述、自然數無限）：106、107、112、113 都出現。
• planar graph 的邊數上界與其推論（113 第 6 題、111 第 4 題）。
• 倒扣題型：110、111、113、115 年都出現「不會寫請留白」的證明題。