113 年 國立成功大學人工智慧科技碩士學位學程《計算機數學(含線性代數、離散數學)》
第 1 題7 分
Solve the recurrence relation for and and .
登入後即可作答並保存紀錄。
核心觀念
本題考查**二階常係數非齊次遞迴關係式(Second-order Linear Non-homogeneous Recurrence Relation with Constant Coefficients)**的求解。
遞迴關係式的一般形式為:
其通解(General Solution)結構由兩部分組成:
- 齊次解(Homogeneous Solution, ):對應齊次方程式 的通解,由特徵方程式(Characteristic Equation) 的根決定。
- 特設解 / 特解(Particular Solution, ):滿足非齊次關係式的任意一特解。當非齊次項 (本題 ),若 為特徵方程式的單根(重複度 ),則特設解的形式需乘以 ,假設為 。
最後代入初始條件(Initial Conditions) 即可求得齊次解中的未定係數。
解題方法
步驟一:求齊次解
考慮對應的齊次遞迴關係式:
寫出特徵方程式(Characteristic Equation):
因式分解:
解得特徵根為 與 。
因此,齊次解為:
其中 為實數常數。
步驟二:求特設解
非齊次項為常數 。
因為特徵根包含 (單根),一般的常數試驗特解 會與齊次解中的 項產生線性相依(衝突)。
因此,特設解必須調整為:
將 代入原非齊次遞迴關係式 :
第 2 題10 分
Please list the first 5 coefficients of the generating function . (請化簡為最簡分數形式)
登入後即可作答並保存紀錄。
核心觀念
本題考查離散數學中**生成函數(Generating Function)的冪級數展開,以及廣義二項式定理(Generalized Binomial Theorem)**的應用。
-
生成函數與係數定義:
生成函數 的「前 5 個係數」即指序列中對應 的係數值 。 -
廣義二項式定理:
對任意實數 與非負整數 ,當 時,有:
其中廣義二項式係數(Generalized Binomial Coefficient)定義為:
解題方法
將生成函數表示為指數形式 ,即 。利用廣義二項式定理依序推導前 5 個係數 :
-
計算 ( 的係數):
-
計算 ( 的係數):
-
計算 ( 的係數):
-
計算 ( 的係數):
-
計算 ( 的係數):
第 3 題15 分
If is the generating function for the sequence , what is the generating function for each of these sequences?
(A) (5 points)
(B) (5 points)
(C) (5 points)
登入後即可作答並保存紀錄。
核心觀念
**普通生成函數(Ordinary Generating Function, OGF)**的定義為:設數列為 ,其對應的生成函數 表示為無窮級數:
本題考核生成函數的三大基本代數運算性質:
- 線性純量乘法性質:若將數列的每一項皆乘以常數 ,其生成函數等於原生成函數乘以常數 ,即 。
- 位移與截斷性質:
- 數列前補零(向右位移 位):生成函數乘以 。
- 數列截斷前幾項:需先自 中減去已被截斷的低次方項,再配合相應的位移次方。
- 逐項微分性質:
對生成函數 關於變數 求微分,可將次方降一次並將原次方指數轉化為新係數:
解題方法
(A) 推導數列 的生成函數
設目標生成函數為 ,根據生成函數定義寫出無窮級數:
將常數 提出:
由於括號內即為 的定義式,代入得:
(B) 推導數列 的生成函數
設目標生成函數為 ,依據數列項次寫出展式:
簡化後可得:
提出公因式 :
回顧原生成函數 ,可知:
將此代回 的推導式中,得到:
(C) 推導數列 的生成函數
設目標生成函數為 ,依據數列項次寫出展式:
將已知生成函數 對變數 進行逐項求導:
第 4 題13 分
Design a finite state machine , where , , . The machine outputs 1 if the input string contains at least three 1s, otherwise it outputs 0. (請填問號應有的內容)
🖼️【此處有附圖,請對照原卷】
登入後即可作答並保存紀錄。
核心觀念
本題考查 Mealy 型有限狀態機:每條轉移弧標示為「輸入,輸出」。狀態用來記錄目前已讀取的輸入字串中,符號 出現的次數。
令各狀態代表:
- :目前尚未讀到 。
- :目前恰好讀到一個 。
- :目前恰好讀到兩個 。
- :目前至少讀到三個 。
輸入符號為 ,其中只有輸入 會使計數增加;輸入 或 不會改變狀態。
解題方法
在 時,若輸入 或 ,已讀到的 的數量不變,因此留在原狀態,且尚未達到三個 ,輸出為 。
輸入 時,狀態依序前進:
第三個 被讀入時,字串首次滿足「至少包含三個 」,因此該轉移的輸出為 。進入 後,無論再讀到 中的哪個符號,條件都持續成立,因此全部留在 且輸出 。
完整轉移表如下,表中內容為「下一狀態,輸出」:
第 5 題5 分
Consider the trees with vertices that have corresponding degrees . How many different spanning trees are there in total?
登入後即可作答並保存紀錄。
核心觀念
本題主要考驗圖論(Graph Theory)中樹的度數性質、**握手定理(Handshaking Lemma)以及標記樹(Labeled Tree)與 Prüfer 序列(Prüfer Sequence)**的對應關係。
-
握手定理(Handshaking Lemma):
對任意無向圖 ,所有頂點的度數和(Sum of Degrees)等於邊數的兩倍:
由此定理可知,任何圖的頂點度數總和必然為偶數。 -
樹的度數和性質:
若 為包含 個頂點的樹(Tree),則 的邊數恰為 。
根據握手定理,包含 個頂點的樹,其頂點度數和恆滿足:
-
指定度數序列的標記樹計數公式(Prüfer 序列):
若給定 個頂點的度數序列 且滿足合法條件 ,則每一個標記樹唯一對應到長度為 的 Prüfer 序列,且頂點 在序列中恰好出現 次。
此時,異構標記樹(生成樹)的總數可由多項式係數(Multinomial Coefficient)給出:
解題方法
步驟一:檢查頂點度數總和與握手定理
題目給定頂點集合為 ,頂點個數 。
第 6 題10 分
Let a vector . It has 24 rearrangements like and . Those 24 vectors span a subspace . Find specific vectors so that the dimension of is three.
登入後即可作答並保存紀錄。
核心觀念
- 向量空間的生成(Span)與維度(Dimension):
由向量集 生成的子空間 ,其維度 即為該向量集中最大線性獨立向量組的向量個數。 - 分量總和守恆(Sum Invariance under Permutation):
對於任意置換矩陣 ,向量 的元素僅為 的分量重新排列,故其分量總和恆等於原向量 的分量總和:
- 正交分解與超平面(Orthogonal Decomposition & Hyperplane):
全空間 可正交分解為一維常數空間 與三維零和超平面 的直和:
解題方法
步驟一:向量的正交分解
將任意向量 唯一分解為:
其中:
- ,平均值 。
- ,滿足分量總和 。
步驟二:分析置換向量的表示式
設 為任意 置換矩陣(全體共 24 個,記作集 )。由於 的四個分量完全相同,對任意置換矩陣 皆有 。
因此, 的任意置換向量可表示為:
由此可知,24 個置換向量生成的子空間 可寫為:
步驟三:分析子空間的差向量生成集
對於任意兩個置換矩陣 ,置換向量之差為:
令 。顯然 ,且 中所有向量的分量總和皆為 ,故 。
當 (即 的四個分量不全相等)時, 的生成空間精確等於整個三維超平面 ,因此:
步驟四:討論子空間 的維度條件
因為 ,子空間 的維度視 與 的值分為以下情況:
-
若 且 (即 且 的分量不全相等):
此時 ,故所有置換向量 。
因此 。再結合 ,得到:
-
若 且 (即 且 的分量不全相等):
此時 ,且 。
第 7 題10 分
Let and be the determinants of the matrices in the following form:
Calculate the value of .
登入後即可作答並保存紀錄。
核心觀念
本題考查線性代數中高階行列式(Determinant)的計算技巧與特殊矩陣之特徵值(Eigenvalues)性質。主要涵蓋以下核心知識點:
- 行列式的列運算性質:
- 將某一列的倍數加到另一列,行列式的值保持不變。
- 某一列具有公因數 時,可將 提至行列式前方。
- 三角矩陣的行列式:
- 上三角矩陣(Upper Triangular Matrix)或下三角矩陣(Lower Triangular Matrix)的行列式值等於其主對角線(Main Diagonal)所有元素的乘積。
- 全 矩陣與特徵值法:
- 令 為 之全 矩陣(All-ones Matrix), 為 之單位矩陣(Identity Matrix)。原矩陣可表示為 。
- 矩陣的行列式等於其所有特徵值的乘積,即 。
解題方法
本題給定 行列式:
法一:高斯消去與列運算(標準解法)
步驟一:進行列加總
觀察發現,矩陣每一列的元素和均為 。將第 列全部加至第 列(列運算 ),行列式的值不變:
步驟二:提出第一列的公因數
將第 列的公因數 提取至行列式前方:
步驟三:消去下方元素,化為上三角矩陣
對第 列()分別減去第 列(列運算 ):
步驟四:計算上三角矩陣行列式
此時行列式已化為上三角矩陣,主對角線元素首項為 ,其餘 個元素皆為 。其值為對角線上所有元素的乘積:
第 8 題10 分
Let and as two matrices. If is invertible, prove that has the same eigenvalues as .
登入後即可作答並保存紀錄。
核心觀念
- 相似矩陣(Similar Matrices)定義:
若 矩陣 與 滿足存在一可逆矩陣 ,使得 (或等價地 ),則稱 與 相似。 - 相似矩陣的特徵多項式不變性:
相似矩陣擁有完全相同的特徵多項式(Characteristic Polynomial),因此具備完全相同的特徵值(Eigenvalues)及其代數重數(Algebraic Multiplicities)。 - 行列式的乘法性質(Determinant Multiplicative Property):
對於同階方陣 ,行列式滿足 。當 為可逆矩陣時,。
解題方法
本題欲證明「當 為可逆矩陣時, 與 具有相同的特徵值」。以下提供兩種標準且嚴謹的證明切入點。
方法一:矩陣相似與特徵多項式推導法(推薦)
-
建立相似關係:
因為 為可逆矩陣,其逆矩陣 存在。將矩陣乘積 進行變形:
此式說明矩陣 與 為相似矩陣(Similarity Transformation)。 -
推導特徵多項式:
設 為與 同階的單位矩陣。矩陣 的特徵多項式 定義為:
將 代入上式,並將 寫為 :
利用矩陣分配律提出左側的 與右側的 :
-
利用行列式乘法性質簡化:
根據行列式性質 :
由於 ,代入化簡可得:
-
結論:
矩陣 與 的特徵多項式完全相同(),故 與 擁有完全相同的特徵值。
方法二:特徵向量與定義推導法
第 9 題10 分
Consider the points and , and . Find the point in whose first component is -1 and such that is parallel to .
登入後即可作答並保存紀錄。
核心觀念
- 空間向量表示法:設空間中兩點為 與 ,由 指向 的向量定義為 。
- 向量平行的定義與性質:非零向量 與 平行(記做 ),當且僅當存在一非零實數 ,使得 。亦即兩向量的對應分量成相同比例。
解題方法
本題為空間向量的基本運算題。切入點為先求出基準向量 ,再運用「向量平行等同於純量倍數關係」建立方程組以求解點 的未知分量。
推導步驟如下:
-
計算向量 :
由點 與 可得:
-
設定點 的坐標:
題目指定點 的第一個分量( 坐標)為 ,故設點 為 。 -
計算向量 :
由點 與 可得:
-
利用平行關係求解未知數:
因為 ,故存在一實數 使得 :
第 10 題10 分
True or False
(a) (2%) Every positive definite matrix is invertible.
(b) (2%) The determinant of equals .
(c) (2%) If is orthogonal to every vector of a subspace , then .
(d) (2%) If is square and is inconsistent for some vector , then the nullity of is zero.
(e) (2%) If there is a basis for consisting of eigenvectors of an matrix , then is diagonalizable.
登入後即可作答並保存紀錄。
核心觀念
本題為線性代數(Linear Algebra)基礎觀念題,綜合測驗矩陣與向量空間的核心性質,包含:
- 正定矩陣(Positive Definite Matrix) 之特徵值性質與可逆性。
- 行列式(Determinant) 的非線性運算性質。
- 正交補空間(Orthogonal Complement) 之定義與性質。
- 秩-零度定理(Rank-Nullity Theorem) 與線性方程組解的結構。
- 矩陣可對角化定理(Matrix Diagonalization Theorem) 的充要條件。
解題方法
針對每個是非題敘述,採用以下分析切入點:
- 正確性驗證:引用線性代數權威定理(如秩-零度定理、可對角化充要條件)或嚴謹的代數定義進行證明。
- 錯誤性反駁:指出邏輯或概念上的盲點,並構造明確的**反例(Counterexample)**證明該敘述不恆成立。
選項分析
(a) 正確(True)
-
詳細解析:
若 實對稱矩陣(或複埃爾米特矩陣) 為正定矩陣(Positive Definite Matrix),根據正定之定義,對所有非零向量 (),皆滿足:
若 為不可逆矩陣(矩陣化零空間不為零),則齊次方程組 必存在非零解 。將其代入可得:
此結果與正定矩陣的定義 矛盾。因此 僅有唯一零解,矩陣 必然可逆(Invertible)。另解(特徵值觀點):正定矩陣的所有特徵值(Eigenvalues) 皆為嚴格正實數()。由於矩陣行列式等於其所有特徵值之連乘積:
因為 ,故 必為可逆矩陣。
(b) 錯誤(False)
-
詳細解析:
行列式(Determinant)映射具有多重線性(Multilinear)與交錯性(Alternating),但對於矩陣加法與減法不具備線性可加性。一般而言:
-
反例驗證:
設二階單位矩陣 與矩陣 :- ,其行列式
計算等式兩端:
兩端不相等(),故該敘述錯誤。
(c) 錯誤(False)
- 詳細解析:
若向量 與子空間 中的每一個向量都正交,表示 屬於子空間 的正交補空間(Orthogonal Complement),即 。
若 為全空間 的真子空間(Proper Subspace,即維度 ),則其正交補空間的維度為:
因此 中必存在非零向量(Non-zero Vectors)。唯有當 時,其正交補空間才僅包含零向量(即 )。