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

本題主要考驗對網路位址轉換 (Network Address Translation, NAT) 的理解，特別是雙重 NAT (Double NAT) 的環境下，封包如何被轉換以及路由。

核心觀念：NAT 的主要目的是將私有 IP 位址轉換成公有 IP 位址，以便在公共網路上進行通訊。在 Double NAT 環境下，封包會經過兩次 NAT 轉換。

1.1. 封包在 Double NAT 環境下的轉換過程：

首先，我們需要了解 NAT 的基本原理：

• 源 IP 位址轉換 (Source NAT)：當內部主機發送封包到外部網路時，NAT 裝置會將封包的源 IP 位址從私有 IP 轉換成 NAT 裝置自身的公有 IP 位址。同時，會記錄下這個轉換關係（私有 IP:Port -> 公有 IP:Port）在 NAT 表格中，以便回程封包能被正確路由。
• 目的 IP 位址轉換 (Destination NAT)：通常用於將外部來的封包導向內部特定主機，例如 Port Forwarding。但在本題中，我們主要關注 Source NAT。

環境設定：

• 你的私有網路：10.20.30.0/22
• 你的 AP (後端 NAT 裝置)：
  • 私有 IP (LAN)：10.20.30.x (假設是 10.20.30.1)
  • WAN IP (由 Office AP 分配)：192.168.50.11
  • NAT 轉換的公有 IP (假設用 192.168.50.11 作為轉換對象)
• Office AP (前端 NAT 裝置)：
  • WAN IP (公網)：34.56.34.11
  • LAN IP (連接到你的 AP)：192.168.50.x (假設是 192.168.50.1)
  • NAT 轉換的公有 IP (即 34.56.34.11)
• 內部筆記型電腦：10.20.30.50
• 目標伺服器：1.1.1.1 (公網 IP)

封包轉換過程：

步驟 1：從筆記型電腦到你的 AP (第一次 NAT)

• 原始封包 (在你的私有網路內)：
  • Source IP: 10.20.30.50
  • Source Port: P_laptop (例如，HTTP 請求是 80，其他應用是隨機分配的)
  • Destination IP: 1.1.1.1
  • Destination Port: 80 (假設是 HTTP 請求)
• 經過你的 AP 的 NAT 轉換後：
  • 你的 AP 會將 10.20.30.50:P_laptop 轉換成 192.168.50.11:P_your_AP。
  • 轉換後的封包：
    • Source IP: 192.168.50.11
    • Source Port: P_your_AP (你的 AP 分配的臨時埠號，用於追蹤連線)
    • Destination IP: 1.1.1.1
    • Destination Port: 80
  • 你的 AP 的 NAT 表格記錄：(10.20.30.50, P_laptop) -> (192.168.50.11, P_your_AP)

步驟 2：從你的 AP 到 Office AP (第二次 NAT)

• 原始封包 (在 Office AP 的 LAN 網段內)：
  • Source IP: 192.168.50.11
  • Source Port: P_your_AP
  • Destination IP: 1.1.1.1
  • Destination Port: 80
• 經過 Office AP 的 NAT 轉換後：
  • Office AP 會將 192.168.50.11:P_your_AP 轉換成 34.56.34.11:P_office_AP。
  • 轉換後的封包：
    • Source IP: 34.56.34.11
    • Source Port: P_office_AP (Office AP 分配的埠號)
    • Destination IP: 1.1.1.1
    • Destination Port: 80
  • Office AP 的 NAT 表格記錄：(192.168.50.11, P_your_AP) -> (34.56.34.11, P_office_AP)

回程封包 (從 1.1.1.1 到筆記型電腦)：
伺服器 1.1.1.1 回傳封包時，目的地是 34.56.34.11:P_office_AP。

1. Office AP 收到封包：查詢其 NAT 表格，找到 (34.56.34.11, P_office_AP) -> (192.168.50.11, P_your_AP) 的對應關係，將目的 IP 和 Port 改為 192.168.50.11:P_your_AP。

本題考驗對資料庫交易 (Database Transaction) 的 ACID 特性理解。ACID 是資料庫管理系統 (DBMS) 確保交易正確性和一致性的四個關鍵屬性。

核心觀念：ACID 是指 Atomicity (原子性)、Consistency (一致性)、Isolation (隔離性) 和 Durability (持久性)。

ACID 屬性解釋與範例：

1. 原子性 (Atomicity)

   • 定義：一個交易是不可分割的工作單元，其所有操作必須全部成功執行，或者全部失敗回滾。不存在部分成功的交易。
   • 目的：確保交易的完整性，避免資料處於中間或不一致的狀態。
   • 範例：假設一個銀行轉帳交易，從帳戶 A 扣款 1000 元並存入帳戶 B 1000 元。
     • 成功執行：如果扣款成功，則存款也必須成功。
     • 部分失敗：如果扣款成功，但存款時系統崩潰，則整個交易必須回滾，帳戶 A 的扣款操作會被撤銷，恢復到交易前的狀態。不會出現 A 扣款了，但 B 沒收到的情況。

2. 一致性 (Consistency)

   • 定義：一個交易必須使其資料庫從一個有效狀態轉換到另一個有效狀態。交易執行前後，資料庫必須遵守所有預定義的規則，包括約束（如主鍵、外鍵、唯一性約束）、觸發器和任何其他資料庫層級的完整性規則。
   • 目的：確保資料庫的完整性和有效性。
   • 範例：延續銀行轉帳的例子。
     • 有效狀態：假設帳戶餘額不能為負數。
     • 一致性檢查：如果帳戶 A 的餘額只有 500 元，而交易要求扣款 1000 元，那麼這個交易將違反「餘額不能為負」的規則。資料庫系統會阻止這個交易的執行，因為它會導致資料庫進入一個不一致的狀態。

本題考驗對系統效能提升策略的理解，特別是單機效能提升與分散式擴展的比較。

核心觀念：比較單一伺服器效能提升 (Vertical Scaling) 與增加多個伺服器 (Horizontal Scaling) 的優缺點。

情境設定：

• 目標：提升公司伺服器的整體處理能力。
• 選項 1：垂直擴展 (Vertical Scaling) - 升級現有伺服器，使其處理速度變為原來的 k 倍。
• 選項 2：水平擴展 (Horizontal Scaling) - 複製現有伺服器，建立 k 個節點，每個節點速度與原伺服器相同。

比較分析：

選項 1：將伺服器處理速度提升 k 倍 (垂直擴展)

• 優點 (Pros)：

  1. 架構簡單：不需要改變現有的軟體架構或應用程式設計。只需更換硬體（CPU、RAM、SSD 等），或透過軟體優化。
  2. 管理容易：只需管理一台伺服器，維護、監控和更新都相對簡單。
  3. 低延遲 (可能)：如果應用程式本身有較強的單線程處理需求，單機效能提升可能帶來更低的延遲，因為不需要網路通訊來協調多個節點。
  4. 軟體兼容性：大多數現有軟體不需要修改即可受益於更快的硬體。

• 缺點 (Cons)：

  1. 成本高昂：通常，購買更高性能的單一伺服器或升級組件的成本非常高，尤其是當 k 很大時。
  2. 擴展上限低：單一伺服器的性能提升總有物理上的極限。當 k 非常大時，可能無法透過垂直擴展達到目標。
  3. 單點故障 (Single Point of Failure, SPOF)：如果這台高性能伺服器發生故障，整個系統將完全停止服務，可用性較差。
  4. 升級時間長/複雜：大規模的硬體升級可能需要較長的停機時間，且過程可能較為複雜。

選項 2：複製伺服器為 k 個節點 (水平擴展)

• 優點 (Pros)：

  1. 高可用性 (High Availability)：即使其中一個或多個節點發生故障，其他節點仍可繼續提供服務，系統整體可用性大大提高。
  2. 成本效益 (可能)：使用 k 個較便宜、標準化的伺服器組成的集群，總體成本可能比購買一台頂級伺服器低，尤其當 k 較大時。
  3. 線性擴展性 (Potential for Linear Scalability)：理論上，增加節點可以近似線性地提升總體處理能力。
  4. 彈性：可以根據需求動態增減節點，靈活應對負載變化。
  5. 故障隔離：單個節點的故障不會影響其他節點。

• 缺點 (Cons)：

  1. 架構複雜：需要額外的軟體和硬體來管理和協調 k 個節點，例如負載均衡器 (Load Balancer)、叢集管理軟體、分佈式資料庫等。
  2. 軟體修改：應用程式可能需要修改以適應分佈式架構，例如處理分佈式狀態、併發控制、數據分片等。

本題考驗對作業系統虛擬記憶體管理機制，特別是分頁 (Paging) 和頁面錯誤 (Page Fault) 的理解。

核心觀念：作業系統利用虛擬記憶體將程式的記憶體空間劃分為固定大小的頁 (Page)，並將這些頁儲存在硬碟上 (作為交換空間 Swap Space)。當 CPU 需要存取某個頁時，如果該頁不在主記憶體 (RAM) 中，就會發生頁面錯誤。

4.1. 頁面錯誤 (Page Fault) 的定義與處理：

• 定義：當 CPU 嘗試存取一個虛擬記憶體位址，而該位址對應的頁面 (Page) 並不在主記憶體 (RAM) 中，而是儲存在硬碟上的交換空間 (Swap Space) 或尚未載入時，就會發生頁面錯誤 (Page Fault)。
• 處理流程：
  1. 發生頁面錯誤：CPU 觸發一個硬體中斷 (Page Fault Interrupt)。
  2. 作業系統介入：控制權從應用程式轉移到作業系統的頁面錯誤處理程序 (Page Fault Handler)。
  3. 檢查頁面有效性：作業系統檢查該虛擬位址對應的頁面是否有效。
     • 如果頁面無效 (例如，存取未分配的記憶體區域)，則終止該程式 (Segmentation Fault / Access Violation)。
     • 如果頁面有效，但不在記憶體中 (即頁面錯誤)，則繼續處理。
  4. 查找頁面：作業系統在硬碟的交換空間 (Swap Space) 或可執行檔中找到所需的頁面。
  5. 分配記憶體：在主記憶體中找到一個空閒的頁框 (Page Frame)。
     • 若無空閒頁框：作業系統必須選擇一個目前在記憶體中的頁面，將其寫回硬碟（如果被修改過），然後將該頁框標記為空閒。這個過程涉及 頁面替換 (Page Replacement)。
  6. 載入頁面：將從硬碟找到的所需頁面讀取到分配的頁框中。
  7. 更新頁表 (Page Table)：更新虛擬位址與實體位址的對應關係，標記該頁面現在位於主記憶體中。
  8. 恢復執行：將控制權交還給發生頁面錯誤的程式，並重新執行導致頁面錯誤的指令。這次指令應該能夠成功存取到記憶體中的頁面。

4.2. 系統抖動 (Thrashing) 的概念與影響：

• 概念：當系統花費了絕大部分時間在頁面交換 (Page Swapping) 上，而不是執行實際的程式指令時，就發生了系統抖動 (Thrashing)。這通常發生在系統的主記憶體不足以容納所有活躍的程式頁面時。
• 原因：當系統負載過高，記憶體不足，作業系統頻繁地將頁面從記憶體換出到硬碟，又從硬碟換入到記憶體，導致 CPU 大部分時間都在等待 I/O 操作完成，而不是做有用的工作。

本題考驗對分類器 (Classifier) 評估指標，特別是誤判率 (False Positive Rate, FPR) 與假陰性率 (False Negative Rate, FNR) 與決策閾值 (Threshold) 之間關係的理解。

核心觀念：一個基於分數的二元分類器，其決策是基於一個評分函數 $f(x)$ 和一個閾值 $c$。當 $f(x) > c$ 時，分類器預測為正類 (Positive Class)；當 $f(x) \le c$ 時，預測為負類 (Negative Class)。

• 真實情況 (True Label)：

  • Positive Class (P)
  • Negative Class (N)

• 預測結果 (Predicted Label)：

  • Predicted Positive (PP)
  • Predicted Negative (PN)

• 四種結果：

  • True Positive (TP)：真實為 P，預測為 P。
  2. False Positive (FP)：真實為 N，預測為 P。 (第一類錯誤，Type I Error)
  3. True Negative (TN)：真實為 N，預測為 N。
  4. False Negative (FN)：真實為 P，預測為 N。 (第二類錯誤，Type II Error)

• 評估指標：

  • 誤判率 (False Positive Rate, FPR)：
    $FPR = \frac{FP}{FP + TN} = \frac{\text{預測為正類但實際為負類的樣本數}}{\text{所有實際為負類的樣本數}}$
  • 假陰性率 (False Negative Rate, FNR)：
    $FNR = \frac{FN}{FN + TP} = \frac{\text{預測為負類但實際為正類的樣本數}}{\text{所有實際為正類的樣本數}}$

分析增加閾值 $c$ 的影響：

當我們 增加閾值 $c$ 時，分類器要求 $f(x)$ 必須比原來更高的值才能被判斷為正類。這意味著：

1. 對 False Positive (FP) 的影響：
   • 原本可能因為 $f(x)$ 略大於舊的 $c$ 而被預測為正類（但實際上是負類）的樣本，現在由於新的、更高的 $c$，其 $f(x)$ 可能不再大於新的 $c$。

本題考驗對不同類型人工智能 (AI) 應用及其互動方式的理解。

核心觀念：釐清 chatbot, agent, 和 Copilot 這三者在功能、交互模式和應用場景上的差異。

1. Chatbot (聊天機器人)

• 定義：一種能夠模擬人類對話的 AI 程式。它主要設計用於理解和回應使用者的文本或語音輸入，進行自然語言的交流。
• 功能：
  • 回答問題 (FAQ)。
  • 提供資訊。
  • 執行簡單的指令 (如設定提醒、查詢天氣)。
  • 進行閒聊。
• 觸發方式：
  • 使用者主動發起對話，通常透過輸入文字訊息或語音指令。
  • 例如：在網站的客服聊天視窗輸入「你好，我想查詢訂單進度。」；在手機語音助理說「設定明天早上七點的鬧鐘」。
• 範例：客服機器人、Siri/Google Assistant (在對話模式下)、ChatGPT (在對話模式下)。

2. Agent (代理人/智慧代理)

• 定義：一個能夠感知其環境，並自主採取行動以達成特定目標的軟體或硬體實體。Agent 的重點在於「自主性」和「目標導向」。
• 功能：
  • 自主監控環境並做出決策。
  • 執行複雜的任務，可能涉及多個步驟和與外部系統的互動。
  • 學習和適應環境。
• 觸發方式：
  • 通常是 被動觸發 或 預設觸發。Agent 可能在特定條件滿足時自動啟動，或在其被設計的系統中持續運作。
  • 使用者可以設定 Agent 的目標或規則，然後 Agent 會自主地去執行。
  • 例如：
    • 一個交易 Agent：當股票價格低於某個設定值時，自動買入。
    • 一個網路爬蟲 Agent：按照預設的規則，自動抓取網頁資訊。
    • 一個機器人吸塵器 (Roomba)：感知環境中的障礙物和髒污，自主規劃路徑進行清潔。
    • 現代 AI Agent (如 Auto-GPT, BabyAGI) 則可以接收一個高層次的目標，然後自主生成並執行一系列子任務來達成該目標。
• 範例：自動交易系統、網路爬蟲、推薦系統 (在後台自主推薦)、自動駕駛汽車的決策系統、AI Agent 框架。

3. Copilot (副駕駛/協作者)

• 定義：一種 AI 工具，旨在作為人類工作者的「副駕駛」或「協作者」，在特定任務中提供輔助和建議，幫助使用者更高效、更優質地完成工作。它通常嵌入在現有的應用程式或工作流程中。
• 功能：
  • 生成程式碼、文本、圖片等內容。
  • 提供建議、自動完成。
  • 解釋複雜概念。
  • 總結資訊。
• 觸發方式：

本題考驗對圖論 (Graph Theory) 的理解，特別是尋找特定路徑的演算法設計。題目要求找出從頂點 1 到頂點 n 的最長「無環路徑」(acyclic path)。

核心觀念：

• 無環路徑 (Acyclic Path)：一條路徑，其中不包含任何重複的頂點（除了起點和終點可能相同，但在此題中起點是 1，終點是 n，且 n>1，所以路徑上的所有頂點都必須是唯一的）。
• 最長路徑 (Longest Path)：在所有符合條件的路徑中，邊數最多的那條路徑。
• 圖的表示：使用鄰接矩陣 (Adjacency Matrix) G，其中 G[x][y] = true 表示頂點 x 和 y 之間有邊。

問題分析：

尋找圖中的最長路徑是一個 NP-hard 問題。然而，題目特別指定了「無環路徑」且起點固定為 1，終點固定為 n。這意味著我們尋找的是一個簡單路徑 (Simple Path)。

在一個 有向無環圖 (DAG) 中，最長路徑問題是可以在多項式時間內解決的。但是，這裡的圖是 無向圖，並且可能包含環。

如果圖中存在 負權邊，尋找最長路徑會變得非常困難。但這裡的路徑長度是計算邊的數量，相當於所有邊的權重都為 1。

在無向圖中尋找最長簡單路徑，其複雜度仍然很高。然而，題目限制了起點和終點，這可能意味著存在某種特定演算法。

一個可能的演算法方向：動態規劃 (Dynamic Programming) 或深度優先搜索 (Depth First Search, DFS) 結合剪枝。

由於我們尋找的是「無環路徑」，這意味著路徑上的每個頂點都只能訪問一次。這提示了 DFS 是一種自然的方法。

演算法設計：DFS 結合狀態記錄

我們可以設計一個 DFS 函數，它從當前頂點出發，遍歷所有未訪問過的鄰居，並記錄當前路徑的長度。

dfs(current_vertex, visited_mask, current_length)

• current_vertex: 當前所在的頂點。
• visited_mask: 一個位元遮罩 (bitmask)，用來記錄哪些頂點已經在當前路徑上被訪問過。如果第 i 位是 1，表示頂點 i 被訪問過。
• current_length: 從起點 1 到 current_vertex 的路徑長度（邊數）。

演算法步驟：

1. 初始化：

   • maxLength = -1 (記錄找到的最長無環路徑的長度)
   • visited_mask = (1 << 0) (標記起點頂點 1 為已訪問，假設頂點編號從 0 開始，如果從 1 開始，則是 (1 << 1))。為了方便，我們將頂點 1...n 映射到位元 0...n-1。所以，頂點 v 對應位元 v-1。
   • visited_mask = (1 << (1 - 1)) = (1 << 0)
   • 呼叫 DFS：dfs(1, visited_mask, 0)

2. DFS 函數 dfs(u, mask, len)：

   • 參數：
     • u: 當前頂點 (1-indexed)。
     • mask: 位元遮罩，記錄已訪問頂點 (0-indexed)。
     • len: 當前路徑長度 (邊數)。
   • 終止條件：
     • 如果 u == n (到達終點)：
       • 更新 maxLength = max(maxLength, len)。
       • 返回。
   • 遞迴步驟：
     • 遍歷所有頂點 v 從 1 到 n：
       • 檢查 G[u][v] 是否為 true (即 u 和 v 之間有邊)。
       • 檢查頂點 v 是否已經在當前路徑上訪問過：檢查 (mask & (1 << (v - 1))) == 0。
       • 如果以上兩個條件都滿足 (有邊且 v 未訪問過)：
         • 遞迴呼叫：dfs(v, mask | (1 << (v - 1)), len + 1)。

效率分析：

• 頂點數量：n
• 邊的數量：m (最多 $n^2$)
• 每個頂點最多被訪問一次（因為是無環路徑）。
• 在 DFS 中，對於每個頂點 u，我們遍歷所有其他頂點 v (O(n)) 來檢查邊 G[u][v] 和訪問狀態。
• 因為每個頂點只會進入 dfs 函數一次（最多），所以總的時間複雜度是 O(n * n) = O(n^2) 的 DFS 遍歷。
• 位元遮罩操作 (位元與、位元或、位移) 是 O(1) 的。
• 空間複雜度：DFS 遞迴深度最多為 n，所以空間複雜度是 O(n)。

這個演算法的效率分析是基於「無環路徑」的限制。 如果圖很大，但從 1 到 n 的無環路徑長度相對較短，這個演算法效率較高。但如果存在很長的無環路徑，DFS 仍可能探索大量路徑。

演算法正確性解釋：

1. 遍歷所有可能路徑：DFS 演算法的本質是系統性地探索所有從起點 1 出發、到達終點 n 的可能路徑。
2. 無環路徑保證：透過使用 visited_mask，我們確保在遞迴過程中，不會重複訪問任何一個頂點。這就保證了我們找到的每一條路徑都是無環路徑（即簡單路徑）。