109 年 國立政治大學資訊管理學系碩士班科技組《計算機概論》

此題考驗基本的邏輯閘運算。

第一組邏輯閘：
由圖示可知，第一組邏輯閘為 XOR 閘後接 NOT 閘（即 XNOR 閘）。
XOR 閘的特性是當輸入不同時輸出為 1，輸入相同時輸出為 0。
當輸入皆為 1 時，XOR 閘的輸出為 $1 \oplus 1 = 0$。
再經過 NOT 閘後，輸出為 $\neg 0 = 1$。

此題考驗對無線網路傳輸速率與影音串流需求的理解。

IEEE 802.11b 標準是較早期的 Wi-Fi 標準，其最高理論傳輸速率為 11 Mbps。
Full HD (1920x1080) 的 24-bit 未壓縮影片，其資料傳輸速率計算如下：
解析度：1920 像素 (寬) $\times$ 1080 像素 (高) = 2,073,600 像素
色彩深度：24 bits/pixel
影格率：30 frames/second

每秒資料量 = 像素 $\times$ 色彩深度 $\times$ 影格率
= 2,073,600 像素/影格 $\times$ 24 bits/像素 $\times$ 30 影格/秒

此題考驗對網路層協定與傳輸層協定的理解，特別是 IP Header 中的 Protocol 欄位。

IP (Internet Protocol) 是一種網路層 (Network Layer) 協定，負責在不同網路之間路由封包。
IP Header 中有一個欄位稱為 Protocol (或 Next Header)，用來識別 IP 封包所攜帶的上層協定類型。
這個 Protocol 欄位的值是預先定義好的，常見的協定值如下：

• ICMP (Internet Control Message Protocol): 協定編號為 1 (0x01)。ICMP 協定用於傳送錯誤訊息和操作資訊，例如 ping。

此題考驗對作業系統虛擬記憶體管理機制，特別是 MMU 和 Page Table 的作用。

MMU (Memory Management Unit) 是硬體元件，通常位於 CPU 內部或與 CPU 緊密整合，負責處理記憶體位址轉換。
作業系統透過 MMU 來實現虛擬記憶體 (Virtual Memory) 的機制。
虛擬記憶體允許程式使用比實際實體記憶體 (Physical Memory) 更大的位址空間。
MMU 利用 Page Table 來將程式使用的虛擬位址 (Virtual Address) 轉換為實體位址 (Physical Address)。

Page Table 是一個資料結構，由作業系統維護，儲存了虛擬頁面 (Virtual Page) 到實體頁框 (Physical Page Frame) 的對應關係。

此題考驗邏輯推導能力，特別是使用真值表或邏輯規則來驗證命題。

我們要驗證的命題是：從 $(P \lor Q)$ 和 $(\neg P)$ 是否能邏輯推導出 $(\neg Q)$。
這相當於驗證 $( (P \lor Q) \land (\neg P) ) \implies (\neg Q)$ 是否為一個重言式 (tautology)。

方法一：使用真值表

P	Q	$P \lor Q$	$\neg P$	$(P \lor Q) \land (\neg P)$	$\neg Q$	$( (P \lor Q) \land (\neg P) ) \implies (\neg Q)$
T	T	T	F	F	F	T
T	F	T	F	F	T	T

核心觀念

• Tower of Hanoi：將 $n$ 個直徑遞減的圓盤從一根柱子搬到另一根柱子，只允許一次搬移一個圓盤，且較大的圓盤不能放在較小的圓盤上面。
• 最少移動次數 $H(n)$：可用遞迴關係 $H(n)=2H(n-1)+1$ 推導出閉式公式 $H(n)=2^{\,n}-1$。
• Fibonacci 數列：遞迴定義 $F(n)=F(n-1)+F(n-2)$（基礎情況 $F(0)=0,\;F(1)=1$）。
• 時間複雜度：純遞迴實作會重複計算許多相同子問題，遞迴樹的節點數呈指數級增長，最終可表示為 $\Theta(\varphi^{\,n})$，其中 $\varphi=\frac{1+\sqrt5}{2}\approx1.618$，而 $\varphi^{\,n}=O(2^{\,n})$。

---

解題方法

1. 證明 $H(n)=2^{\,n}-1$

   • 基礎情況：$H(1)=1=2^{1}-1$，成立。
   • 假設對 $k$ ( $1\le k<n$ ) 成立，即 $H(k)=2^{k}-1$。
   • 考慮 $n$ 個圓盤的搬移：
     1. 先把上面的 $n-1$ 個圓盤從起始柱子搬到輔助柱子，需要 $H(n-1)$ 步。
     2. 把第 $n$ 個（最大）圓盤直接搬到目標柱子，需 1 步。
     3. 再把 $n-1$ 個圓盤從輔助柱子搬到目標柱子，仍需 $H(n-1)$ 步。
   • 因此 $H(n)=H(n-1)+1+H(n-1)=2H(n-1)+1$。代入歸納假設：
     $H(n)=2(2^{\,n-1}-1)+1=2^{\,n}-2+1=2^{\,n}-1.$
   • 完成歸納證明，得 $H(n)=2^{\,n}-1$。

2. 分析 Fibonacci 純遞迴的時間複雜度

   • 遞迴樹根節點為 $F(n)$，其左子樹為 $F(n-1)$，右子樹為 $F(n-2)$。
   • 每層的節點數約為前一層的 2 倍（除最底層外），樹高為 $n$，故總節點數 $T(n)$ 滿足

此題考驗對軟體測試中白箱測試 (White-box Testing) 和黑箱測試 (Black-box Testing) 的區別與特點的理解。

白箱測試 (White-box Testing)：

• 測試者需要了解軟體的內部結構、設計和程式碼。
• 目標是驗證軟體程式碼的邏輯是否正確，找出程式中的錯誤。
• 測試案例的設計基於程式碼路徑、條件、迴圈等。
• Code coverage 是一種白箱測試的度量標準，用於衡量測試案例涵蓋了多少程式碼。
• Statement coverage (語句覆蓋)：要求測試案例至少執行到程式中的每一條語句一次。
• Branch coverage (分支覆蓋)：要求測試案例至少執行到程式中的每一個分支（如 if-else 的 true 和 false 路徑）一次。
• Path coverage (路徑覆蓋)：要求測試案例執行到程式中的所有可能的執行路徑一次（通常很難實現）。
• 進行白箱測試通常需要具備程式設計知識。

此題考驗對 SQL 的 COUNT 聚合函數、GROUP BY 子句以及 HAVING 子句的理解。

首先，我們分析 Customers 資料表：

ID	CustomerName	City	Postal Code	Country
1	Alfreds Futterkiste	Berlin	12209	Germany
2	Ana Trujillo Emparedados	México D.F.	05021	Mexico
3	Antonio Moreno Taquería	México D.F.	05023	Mexico
4	Around the Horn	London	WA1 1DP	UK
5	Berglunds snabbköp	Luleå	S-958 22	Sweden

總共有 5 筆資料。
各國家的數量：

• Germany: 1
• Mexico: 2
• UK: 1
• Sweden: 1

第一個 SQL 語句：SELECT COUNT(ID), Country FROM Customers GROUP BY Country;

• GROUP BY Country 會將資料按照 Country 欄位進行分組。
• COUNT(ID) 會計算每個分組中的 ID 數量。
• 預期的結果會是每個國家的一行，顯示國家名稱和該國家對應的客戶數。
• 分組結果：

此題考驗對機器學習中 Loss Function 和 Regularization 的理解，特別是 L2-norm 和 L2 regularization。

1. L2-norm Loss Function (Least Squares Error, LSE):

   • LSE 的數學形式通常是 $\frac{1}{2} \sum_{i=1}^n (y_i - \hat{y}_i)^2$，其中 $y_i$ 是真實值，$\hat{y}_i$ 是模型預測值。
   • 目的：LSE 的主要目的是最小化預測值與真實值之間的平方差。
   • 可微分性：LSE 確實是可微分的。這是因為平方函數和求和運算是可微分的，這使得我們可以利用梯度下降等優化方法來求解模型參數（例如，通過計算損失函數對參數的梯度）。
   • 求其解較容易：由於其可微分性，我們可以通過解析方法（如正則方程 Normal Equation）或迭代優化方法（如梯度下降）來找到使損失最小化的參數。因此，說「求其解較容易」是合理的。

2. L2 Regularization:

   • L2 Regularization (也稱為 Ridge Regression) 的目的是在損失函數中添加一個懲罰項，該懲罰項是模型參數（權重）的平方和。

此題考驗對機器學習中監督式學習 (Supervised Learning) 和非監督式學習 (Unsupervised Learning) 的區別，以及 K-Nearest Neighbor (KNN) 和 K-Means 演算法的特點。

1. K-Nearest Neighbor (KNN):
   • KNN 是一種分類 (Classification) 和迴歸 (Regression) 演算法。
   • 它屬於 監督式學習 (Supervised Learning)，因為在訓練階段需要有標籤的數據（即輸入特徵和對應的類別或目標值）。
   • KNN 的工作原理是：對於一個新的數據點，它會找出訓練集中距離它最近的 K 個鄰居，然後根據這 K 個鄰居的類別（對於分類問題）或平均值（對於迴歸問題）來預測新數據點的類別或值。
   • KNN 中的 'K' 指的是鄰居的數量，這個值是需要事先設定的，通常可以透過交叉驗證等方法來選擇最佳的 K 值。這是一個 超參數 (hyperparameter)，可以由使用者（人工）設定。

此題考驗對非對稱式加密（公鑰加密）原理、數位簽章以及 PKI 的理解。

非對稱式加密（公鑰密碼學）涉及一對金鑰：公鑰 (Public Key) 和私鑰 (Private Key)。
公鑰可以公開，私鑰必須保密。
加密和解密的操作是相對的：

• 使用公鑰加密的訊息，只能用對應的私鑰解密。
• 使用私鑰加密（或簽章）的訊息，可以用對應的公鑰解密（或驗證）。

我們逐一分析選項：

(A) 甲方使用非對稱式加密演算法傳送資料至乙方,若要確保資料只能由乙方解讀,應使用甲方
之公鑰加密資訊。

• 分析：如果甲方想確保只有乙方能解讀訊息，那麼甲方應該使用乙方的公鑰來加密訊息。因為只有乙方擁有與其公鑰配對的私鑰，所以只有乙方能夠解密。使用甲方自己的公鑰加密，則表示任何擁有甲方公鑰的人（包括乙方）都可以解密，這無法確保只有乙方能解讀。
• 結論：此選項錯誤。

(B) 甲方使用非對稱式加密演算法傳送資料至乙方,若要確保資料確實來自甲方,應使用甲方
之密鑰加密資訊。

• 分析：要確保資料確實來自甲方，這涉及到身份驗證，通常是通過數位簽章實現的。數位簽章是使用發送者的私鑰對訊息的雜湊值進行加密（簽章）。接收者（乙方）可以使用發送者（甲方）的公鑰來驗證簽章。如果驗證成功，則證明該訊息確實來自持有該私鑰的甲方，並且未被篡改。
• 結論：此選項正確。

(C) 甲方使用非對稱式加密演算法傳送資料至乙方,若要確保資料內容正確未被竄改,應使用甲
方之密鑰加密資訊。

• 分析：確保資料未被竄改（完整性）也是通過數位簽章實現的。

此題考驗對資料庫正規化 (Normalization) 的基本概念、目的和優缺點的理解。

正規化是關係型資料庫設計中的一個過程，旨在減少資料冗餘 (redundancy) 和提高資料的獨立性，以避免資料異常 (anomalies)。

我們逐一分析選項：

(A) 正規化的程度越高,資料的重複性會降低

• 分析：正規化的主要目標之一就是消除或減少資料的冗餘。例如，從非正規化 (0NF) 或第一正規化 (1NF) 到更高層次的正規化（如 2NF, 3NF, BCNF），都是通過將大表拆分成小表，並利用表之間的關係來儲存數據，從而減少重複儲存的資訊。
• 結論：此選項正確。

(B) 正規化的程度越高,資料存取效能亦會越高

• 分析：正規化通常會將一個大表拆分成多個小表。當需要查詢跨越多個表（即需要進行 JOIN 操作）才能獲取完整資訊時，JOIN 操作本身會增加查詢的複雜度和時間開銷。因此，過度正規化 (over-normalization) 可能會導致查詢效能下降，因為需要更多的 JOIN 操作。

此題考驗對作業系統虛擬化技術（虛擬機器與容器）、檔案權限、分頁機制 (Paging) 與寫時複製 (Copy-on-Write, CoW) 的理解。

我們逐一分析選項：

(A) 虛擬機器(virtual machine)和容器(container)的不同在於目前容器內外的作業系統必須是
相同的,而虛擬機器內外的作業系統架構(architecture)可以不同。

• 分析：
  • 虛擬機器 (VM)：VM 模擬了一整台硬體，包括 CPU、記憶體、儲存裝置、網路介面等。在 VM 上運行的作業系統（Guest OS）與宿主作業系統（Host OS）是完全獨立的。Guest OS 可以是與 Host OS 完全不同的作業系統，甚至架構也可以不同（例如在 x86 架構的 Host 上運行 ARM 架構的 Guest OS，儘管這需要模擬器）。
  • 容器 (Container)：容器（如 Docker）共享宿主作業系統的 Linux 核心。它提供的不是硬體模擬，而是作業系統層級的虛擬化，隔離的是進程、檔案系統、網路等。因此，容器內的應用程式運行在與宿主 OS 相同的核心之上。雖然容器內的應用程式可能會認為自己運行在一個獨立的 OS 環境，但底層 OS 必須是相容的（通常是 Linux 核心）。
• 結論：此選項正確。容器要求宿主 OS 和容器內的 OS 核心是相容的（通常是 Linux），而 VM 則可以運行完全不同的 Guest OS，其架構也可以不同。

(B) 若一個 Linux 檔案的存取權限為 655,則此檔案擁有者之外的使用者可以執行此檔案。

• 分析：Linux 檔案權限由三組數字表示：擁有者 (Owner)、群組 (Group)、其他人 (Others)。每組數字由三位組成，分別代表讀取 (r=4)、寫入 (w=2)、執行 (x=1)。
  • 權限 655 表示：
    • 擁有者 (Owner): 6 = 4 (讀) + 2 (寫) = rw-
    • 群組 (Group): 5 = 4 (讀) + 1 (執行) = r-x
    • 其他人 (Others): 5 = 4 (讀) + 1 (執行) = r-x
  • 題目問「擁有者之外的使用者可以執行此檔案」。擁有者之外的使用者包括群組使用者和其他使用者。
  • 群組使用者的權限是 r-x (讀取和執行)。
  • 其他使用者的權限是 r-x (讀取和執行)。
  • 因此，擁有者之外的使用者（包括群組和其他人）都可以執行此檔案。
• 結論：此選項正確。

核心觀念

• DNS 解析：在使用 URL（如 http://www.example.com）時，必須先將 domain name 轉成 IP 位址，以便建立 TCP 連線。
• P2P 檔案傳輸瓶頸：傳輸速率受上傳頻寬（特別是持有檔案者）與下載端頻寬的最小值限制，總和概念不構成瓶頸。
• Web Proxy 與 DNS 快取：Proxy 透過快取減少外部流量；本機 DNS 快取減少向上層（root/TLD）伺服器的查詢。
• TCP 連線唯一辨識：TCP 連線以 4‑tuple（src IP、src port、dst IP、dst port）唯一標示，但「socket」在 OS API 中只指本端 IP+port。

---

解題方法
逐一檢視選項的敘述是否符合上述概念。若敘述在技術上正確且描述完整，即判為「正確」；若包含概念性錯誤或表述過於絕對（與實務不符），則為「錯誤」。

---

選項分析

選項	判斷	理由
A	✅ 正確	在建立 HTTP（TCP/80）或 SMTP（TCP/25）連線前，通常會先向 DNS server 詢問目標 domain name 的 IP 位址。此過程是「可能需要」的，符合實務。
B	❌ 錯誤	敘述混合了三個不同的因素：① 檔案持有者的上傳頻寬、② 下載者的最小頻寬、③ 上傳頻寬的總和。

此題考驗對無線網路協定（Wi-Fi/802.11）中 CSMA/CD, CSMA/CA, Hidden Terminal Problem, 以及網路層與資料鏈結層封包特性的理解。

我們逐一分析選項：

(A) CSMA/CD機制可以偵測 collision,CSMA/CA 機制可以避免 collision。

• 分析：
  • CSMA/CD (Carrier Sense Multiple Access with Collision Detection)：這是早期有線乙太網路 (Ethernet) 使用的 MAC 協議。它允許節點在傳輸前先偵聽載波 (Carrier Sense)，如果信道空閒則開始傳輸。如果在傳輸過程中偵測到碰撞 (Collision Detection)，則停止傳輸，隨機等待一段時間後重試。
  • CSMA/CA (Carrier Sense Multiple Access with Collision Avoidance)：這是無線網路 (Wi-Fi, 802.11) 使用的 MAC 協議。由於無線環境中偵測碰撞非常困難（例如，一個節點可能聽不到另一個節點的傳輸，但它們可能同時發送而發生碰撞），因此 CSMA/CA 採用避免碰撞的策略。它在傳輸前會等待一個隨機的回退時間 (backoff time)，並且通常使用 RTS/CTS (Request to Send/Clear to Send) 握手機制來預約信道，以減少碰撞的發生。
• 結論：此選項正確。CSMA/CD 用於有線網路並偵測碰撞，CSMA/CA 用於無線網路並避免碰撞。

(B) Hidden Terminal Problem 只會出現在無線網路的環境,且RTS/CTS 可以完全避免此問題。

• 分析：
  • Hidden Terminal Problem (隱藏節點問題)：這個問題確實主要出現在無線網路中。當節點 A 和節點 C 都想與節點 B 通信，但 A 無法聽到 C 的傳輸（因為距離、障礙物等），C 也無法聽到 A 的傳輸，但 A 和 C 卻可能同時發送給 B，從而導致 B 收到衝突的信號。
  • RTS/CTS 的作用：RTS/CTS 握手機制可以有效地緩解 Hidden Terminal Problem。當節點 A 想發送數據給 B 時，它先發送一個 RTS 訊框給 B。如果 B 能夠收到 RTS，並且準備好接收，它會回覆一個 CTS 訊框。收到 CTS 的節點（包括 A 和其他可能聽到的節點）就知道 B 正在與 A 通信，因此會暫時停止向 B 發送數據。
  • 「完全避免」：雖然 RTS/CTS 大大降低了 Hidden Terminal Problem 的機率，但並不能「完全」避免。例如，如果 RTS 或 CTS 訊框本身發生碰撞，或者有其他未被 RTS/CTS 覆蓋到的情況，問題仍可能發生。此外，如果節點沒有正確實現 RTS/CTS 或其範圍有限，也可能無法完全解決。
• 結論：此選項錯誤。「完全避免」的說法太絕對。

(C) 802.11 frame 的MAC address 在每一個 Layer 2的hop之後,都會更換。

• 分析：802.11 協議工作在 OSI 的 Layer 2 (資料鏈結層)。在有線網路中，當一個乙太網路幀從一個交換機轉發到另一個交換機時，乙太網路幀的 MAC 地址（源 MAC 和目標 MAC）通常不會改變。只有當幀通過路由器（Layer 3）時，IP 位址才會改變（NAT 等情況下）。

NAT (Network Address Translation) 是一種將私有 IP 位址轉換為公共 IP 位址的技術，常見於家庭和企業網路邊界路由器上，用於讓多台設備共享一個公共 IP 位址上網。

NAT 的運作原理：

NAT 的核心在於修改 IP 封包的 IP 位址和埠號資訊。它通常部署在網路邊界（例如路由器）。
當內部網路的設備（使用私有 IP 位址，如 192.168.x.x, 10.x.x.x）要與外部網路（公共 IP 位址）通信時，封包會經過 NAT 設備。

1. 從內部到外部 (Outbound Translation):

   • 內部設備發送一個 IP 封包，源 IP 位址是私有 IP，源埠號是該設備的應用程式埠號。
   • NAT 設備（通常是路由器）接收到這個封包。
   • NAT 設備會修改封包的源 IP 位址，將其替換為 NAT 設備的公共 IP 位址（或一個預分配的公共 IP 位址）。
   • 同時，NAT 設備還會修改源埠號，將其替換為一個新的、在 NAT 設備上唯一的埠號。這個新的埠號通常是從一個預定義的埠號範圍中選擇的。
   • NAT 設備會將原始的私有 IP 和埠號、以及轉換後的公共 IP 和埠號記錄在一個 NAT Table (或稱 PAT Table, Connection Tracking Table) 中。
   • 修改後的封包被發送到外部網路。
   • 外部伺服器收到封包時，看到的源 IP 和埠號是 NAT 設備的公共 IP 和新分配的埠號。

2. 從外部到內部 (Inbound Translation):

   • 外部伺服器響應封包，其目標 IP 位址是 NAT 設備的公共 IP，目標埠號是 NAT 設備之前分配的那個新埠號。
   • NAT 設備接收到這個響應封包。
   • NAT 設備查詢其 NAT Table，根據目標 IP 和目標埠號，找到對應的原始內部 IP 和原始埠號。
   • NAT 設備將封包的目標 IP 位址改回原始的內部私有 IP，目標埠號改回原始的埠號。
   • 修改後的封包被轉發到內部網路中對應的設備。

NAT Table 的建立與使用步驟：

NAT Table 是 NAT 運作的核心，它記錄了內部 IP/埠號與外部 IP/埠號之間的映射關係。

1. 建立 (Creation):
   • 當內部設備首次發起一個與外部網路的連接（例如，瀏覽網頁）時，NAT 設備會接收到這個出站封包。
   • NAT 設備為這個連接分配一個唯一的外部埠號（如果使用 PAT/NAPT，即 Port Address Translation，也稱為 IP Masquerading）。

此題考驗如何使用標準 SQL 語法來計算排名 (Rank)，特別是處理同分情況下的排名規則（即同分同名次，下一個名次不跳過）。這通常需要利用 COUNT 和 DISTINCT 結合 ORDER BY 或 GROUP BY。

目標：根據 scores 表中的 Score 列，產生一個新表，包含唯一的 Score 值以及對應的 Rank。
排名規則：

1. 分數越高，排名越靠前（Rank 值越小）。
2. 同分者，排名相同。
3. 下一個排名應緊接前一個排名，不跳過。

例如：

• 4.00 是最高分，排名為 1。
• 3.85 是次高分，排名為 2。
• 3.65 是再次高分，有兩筆，它們都排名為 3。
• 3.50 是最低分，排名為 4。

我們需要寫一個 SQL 查詢，從 scores 表中獲取 Score 和 Rank。

方法一：使用子查詢和 COUNT (標準 SQL 語法)

這個方法的核心思想是：對於每一個分數 s，計算有多少個分數比它「大」。這個計數值就是它的排名。
由於我們需要處理同分同名次，並且下一個名次不跳過，這個方法需要調整。

一個更符合題意的方法是：對於每一個分數 s，計算有多少個「不同」的分數比它「大」。這個計數值加上 1，就是它的排名。

SQL 語句結構：

SELECT
    DISTINCT s1.Score,
    (SELECT COUNT(DISTINCT s2.Score) + 1
     FROM scores s2
     WHERE s2.Score > s1.Score) AS Rank
FROM
    scores s1
ORDER BY
    s1.Score DESC;

讓我們逐步驗證這個查詢：

假設 scores 表的內容如下：

Id	Score
1	3.50
2	3.65
3	4.00
4	3.85
5	4.00
6	3.65

當 s1.Score 為 4.00 時：
子查詢 SELECT COUNT(DISTINCT s2.Score) + 1 FROM scores s2 WHERE s2.Score > 4.00

• WHERE s2.Score > 4.00 的條件為假，沒有分數大於 4.00。
• COUNT(DISTINCT s2.Score) 得到 0。
• 排名 = 0 + 1 = 1。
• 結果：(4.00, 1)

當 s1.Score 為 3.85 時：
子查詢 SELECT COUNT(DISTINCT s2.Score) + 1 FROM scores s2 WHERE s2.Score > 3.85

• WHERE s2.Score > 3.85 的條件滿足的分數是 4.00。
• DISTINCT s2.Score 得到 {4.00}。
• COUNT(DISTINCT s2.Score) 得到 1。
• 排名 = 1 + 1 = 2。
• 結果：(3.85, 2)

當 s1.Score 為 3.65 時：
子查詢 SELECT COUNT(DISTINCT s2.Score) + 1 FROM scores s2 WHERE s2.Score > 3.65

• WHERE s2.Score > 3.65 的條件滿足的分數是 4.00 和 3.85。
• DISTINCT s2.Score 得到 {4.00, 3.85}。
• COUNT(DISTINCT s2.Score) 得到 2。
• 排名 = 2 + 1 = 3。
• 結果：(3.65, 3)

當 s1.Score 為 3.50 時：
子查詢 `SELECT COUNT(DISTINCT s2.Score) + 1 FROM scores s2 WHERE s2

在機器學習領域，「模型」和「模型有效性評估」是兩個核心的概念。

一、什麼是「模型」(Model)？

在機器學習中，「模型」是指一個從數據中學習到的數學表示或結構，它能夠根據輸入的數據進行預測、分類、決策或其他任務。模型是機器學習演算法在訓練過程中學習到的結果。

更具體地說，模型可以被看作是一個函數 $f$，它將輸入數據 $X$ 映射到輸出 $Y$：$Y = f(X)$。
這個函數 $f$ 的具體形式取決於所使用的機器學習演算法，並且它包含了一組通過訓練數據學習到的參數 (parameters) 或權重 (weights)。

模型的種類繁多，常見的包括：

1. 線性模型 (Linear Models)：如線性迴歸 (Linear Regression)、邏輯迴歸 (Logistic Regression)。它們假設輸入與輸出之間存在線性關係，模型的結構是輸入特徵的線性組合。
2. 決策樹 (Decision Trees)：模型結構是一個樹狀圖，通過一系列基於特徵的規則來進行決策。
3. 支持向量機 (Support Vector Machines, SVM)：尋找一個最佳的超平面來分隔不同類別的數據。
4. 神經網路 (Neural Networks)：由多層相互連接的節點（神經元）組成，能夠學習複雜的非線性關係。
5. k-近鄰 (k-Nearest Neighbors, KNN)：根據最近鄰居的類別進行預測。
6. 貝葉斯分類器 (Bayesian Classifiers)：基於貝葉斯定理進行概率預測。

模型的核心是通過學習數據中的模式和關係，來泛化到未見過的數據上，並做出有意義的預測或決策。

二、如何評估模型的有效性？

評估模型的有效性，就是判斷一個模型在多大程度上能夠準確地完成其預期的任務，特別是對於新數據的泛化能力。這通常是通過將模型在獨立的測試數據集上進行評測來實現的。評估指標的選擇取決於具體的任務類型（分類、迴歸、聚類等）。

1. 對於分類任務 (Classification Tasks)：

• 準確率 (Accuracy)：最直觀的指標，表示模型正確預測的樣本數佔總樣本數的比例。
  $\text{Accuracy} = \frac{\text{Number of Correct Predictions}}{\text{Total Number of Predictions}}$
  缺點：在類別不平衡的數據集上可能產生誤導。
• 混淆矩陣 (Confusion Matrix)：一個表格，總結了模型的預測結果，包含真陽性 (True Positive, TP)、假陽性 (False Positive, FP)、真陰性 (True Negative, TN) 和假陰性 (False Negative, FN)。
• 精確率 (Precision)：表示模型預測為正例的樣本中，真正是正例的比例。
  $\text{Precision} = \frac{TP}{TP + FP}$
  衡量「查得準」。
• 召回率 (Recall) / 靈敏度 (Sensitivity)：表示所有真實為正例的樣本中，被模型正確預測為正例的比例。
  $\text{Recall} = \frac{TP}{TP + FN}$
  衡量「查得全」。
• F1 分數 (F1-Score)：精確率和召回率的調和平均數，用於綜合評價兩個指標。

生成對抗網路 (Generative Adversarial Network, GAN)

GAN 是一種深度學習模型架構，由兩個神經網路組成，它們之間進行「對抗」訓練。這兩個網路分別是：

1. 生成器 (Generator, G)：

   • 任務：學習從一個隨機的潛在空間 (latent space) 向量 $z$ 生成與真實數據 (real data) 分佈相似的偽造數據 (fake data)。
   • 輸入：一個隨機向量 $z$，通常從一個簡單的分佈（如標準常態分佈）採樣。
   • 輸出：一個偽造的數據樣本，例如一張圖像。
   • 訓練目標：希望生成的數據足夠逼真，能夠欺騙判別器。

2. 判別器 (Discriminator, D)：

   • 任務：學習區分輸入的數據是真實數據集中的樣本，還是由生成器生成的偽造樣本。
   • 輸入：一個數據樣本（可能是真實的，也可能是生成的）。
   • 輸出：一個機率值，表示該樣本是真實數據的機率（通常在 0 到 1 之間）。
   • 訓練目標：希望能夠準確地識別出真實樣本和偽造樣本。

訓練過程 (Adversarial Training)：
GAN 的訓練是一個「零和遊戲」(zero-sum game) 或「對抗性博弈」(minimax game)。

• 生成器 $G$ 嘗試最大化判別器 $D$ 將其生成的偽造數據誤判為真實數據的機率。
• 判別器 $D$ 則嘗試最小化將真實數據誤判為偽造數據，以及將偽造數據誤判為真實數據的機率。

這個過程可以表示為一個價值函數 $V(D, G)$：
$\min_G \max_D V(D, G) = \mathbb{E}_{x \sim p_{data}(x)}[\log D(x)] + \mathbb{E}_{z \sim p_z(z)}[\log(1 - D(G(z)))]$
其中：

• $p_{data}(x)$ 是真實數據的分佈。
• $p_z(z)$ 是潛在空間 $z$ 的分佈。
• $D(x)$ 是判別器判斷樣本 $x$ 為真實的機率。
• $G(z)$ 是生成器生成的偽造樣本。
• $\mathbb{E}[\cdot]$ 表示期望值。

通過這種對抗訓練，生成器 $G$ 逐漸學會生成越來越逼真的數據，直到其生成的數據分佈 $p_g$ 趨近於真實數據的分佈 $p_{data}$，此時判別器 $D$ 難以區分真偽，其輸出機率接近 0.5。

「潛在空間」(Latent Space) 在 GAN 中的用途

雲端運算 (Cloud Computing) 的服務模型是指雲端供應商提供的不同層級的服務，讓使用者能夠在雲端環境中部署和運行應用程式。最常見的三種服務模型是 IaaS, PaaS, 和 SaaS。它們之間的分層關係可以類比為「硬體-平台-軟體」。

1. IaaS (Infrastructure as a Service) - 基礎設施即服務

• 定義：IaaS 提供最底層的雲端運算資源，包括伺服器（虛擬機）、儲存空間、網路設備和作業系統。使用者可以像擁有自己的數據中心一樣，完全掌控這些基礎設施。
• 使用者負責：
  • 作業系統的安裝、配置和管理。
  • 中間件（如資料庫、Web 伺服器）。
  • 運行時環境 (Runtime)。
  • 應用程式 (Applications)。
  • 數據 (Data)。
• 雲端供應商負責：
  • 虛擬化層（Hypervisor）。
  • 伺服器硬體、儲存硬體、網路硬體。
  • 資料中心的物理基礎設施（電力、冷卻、安全）。
• 優點：
  • 靈活性最高，使用者可以完全控制其 IT 環境。
  • 適合需要高度客製化、運行特定作業系統或應用程式的場景。
  • 按需付費，可以根據實際資源使用量擴展或縮減。
• 例子：Amazon Web Services (AWS) EC2, Microsoft Azure Virtual Machines, Google Compute Engine。

2. PaaS (Platform as a Service) - 平台即服務

• 定義：PaaS 在 IaaS 的基礎上，額外提供了運行應用程式所需的運行時環境、中間件、資料庫、作業系統等預配置好的平台。使用者無需擔心底層基礎設施和作業系統的維護。
• 使用者負責：
  • 應用程式 (Applications)。
  • 數據 (Data)。
• 雲端供應商負責：
  • IaaS 層的所有內容（硬體、網路、虛擬化）。
  • 作業系統。
  • 中間件（如資料庫、Web 伺服器）。
  • 運行時環境 (Runtime)。
• 優點：
  • 簡化了應用程式的開發、部署和管理流程。
  • 開發者可以專注於編寫應用程式代碼，而無需管理伺服器和作業系統。
  • 通常提供自動擴展、負載平衡等功能。

核心觀念

本題要求實作子字串搜尋：

• s：要搜尋的子字串。
• t：被搜尋的完整字串。
• 回傳 s 在 t 中第一次完整出現的起始索引，索引從 $0$ 開始。
• 若 s 為空字串，依題意回傳 $0$。
• 若 s 不是 t 的子字串，回傳 $-1$。

不能使用 strstr()、strlen() 等內建字串函式，因此必須自行逐字元比較。

解題方法

採用「逐一嘗試起始位置」的方法：

1. 令 t 的每個位置 $i$ 都作為可能的匹配起點。
2. 從該位置開始，逐字元比較 s[j] 與 t[i+j]。
3. 只要發現字元不同，表示從位置 $i$ 開始不可能匹配，改測下一個位置。
4. 若 s 的結束字元先被遇到，代表整個 s 已經匹配成功，回傳 $i$。
5. 若 t 掃描完仍未成功，回傳 $-1$。

C 語言字串以空字元 '\0' 表示結尾，因此不需要使用 strlen() 即可判斷字串長度與結束位置。

C 語言實作

核心觀念

• 2 的次方（Power of Two）定義：若正整數 $n$ 能寫成 $2^{k}$（$k\ge 0$ 為整數），則稱 $n$ 為 2 的次方。
• 位元運算性質：對於任意正整數 $n$，若 $n$ 為 2 的次方，則其二進位表示僅有唯一一個 1，形如 100…0。此時 $n-1$ 的二進位會把這個 1 變成 0，而右側全部變成 1，兩者 按位與 (AND) 的結果必為 0。
• 判斷條件：
  $n>0 \,\land\, (n \,\&\, (n-1)) = 0$

---

(a) Pseudocode（使用一般迴圈或遞迴）

方法說明

1. 先檢查 $n$ 是否大於 0。
2. 透過不斷除以 2（或右移一位）檢查是否仍為整數；若在過程中出現餘數則不是 2 的次方。
3. 最終若除到 1，則代表原數為 2 的次方。

Pseudocode（使用迴圈）

FUNCTION IsPowerOfTwo_Loop(n: integer) RETURNS boolean
    IF n <= 0 THEN
        RETURN FALSE                // 正整數才可能是 2 的次方
    END IF
    WHILE n MOD 2 = 0               // 只要能被 2 整除就持續除
        n ← n / 2
    END WHILE
    RETURN (n = 1)                  // 最後必須剩 1
END FUNCTION

• 時間複雜度：$O(\log_2 n)$（每次除以 2，最多除 $\log_2 n$ 次）。
• 空間複雜度：$O(1)$（只使用常數額外變數）。

Pseudocode（使用遞迴）