政大 115 年資管所（資管組） 計算機概論 參考答案

1.1 目的位址 1.1.1.1:80 全程不變，來源位址被兩層 NAT 改寫（port 為示意）：

NAT#1 轉換表：10.20.30.50:5000 ↔ 192.168.50.11:6000；NAT#2 轉換表：192.168.50.11:6000 ↔ 34.56.34.11:7000。回程依兩表反向逐層還原。

1.2 PAT/NAPT：私有 AP 為每條內部連線（來源 IP＋Port）配一個唯一的 mapped port 記入轉換表，回應封包依目的 port 查表送回對應的主機。

1.3 $2^{32-22}-2=1022$ 個。

以 A 轉帳 1000 元給 B 為例：

1. Atomicity：所有操作同時成功或同時失敗；A 扣款與 B 入帳不能只做一半。
2. Consistency：交易前後滿足完整性限制；A、B 餘額總和不變且不得為負。
3. Isolation：並行交易互不干擾；轉帳進行中查詢不會看到 A 已扣、B 未入的中間狀態。
4. Durability：commit 後結果永久有效；轉帳成功後斷電，重啟仍保留結果。

方案 (1) Scale Up：

• 優點：架構簡單，程式與資料不必修改；單執行緒工作直接受惠。
• 缺點：受單機硬體上限限制、高階硬體成本非線性上升、單點故障、升級常須停機。

方案 (2) Scale Out：

• 優點：可持續增加節點、單節點故障不影響整體、成本較線性、可線上增減節點。
• 缺點：需負載平衡與資料一致性協調，架構複雜；難以平行化的工作受 Amdahl's Law 限制，提升有限。

4.1 Page fault：行程存取的 page 不在實體記憶體（valid bit 為 0）時觸發的例外。OS 處理：trap 進核心、檢查存取是否合法、在磁碟定位該 page、無空閒 frame 時以 Page Replacement 選 victim 換出（dirty 才寫回）、載入 page 並更新 Page Table、重新執行該指令。

4.2 Thrashing：系統花在換頁的時間遠大於實際執行的時間；行程的 working set 總和超過實體記憶體所致，CPU 使用率驟降、磁碟 I/O 爆增、throughput 崩潰。

4.3 Page replacement algorithm 決定記憶體滿時換出哪個 frame（FIFO、OPT、LRU 等）。越接近 OPT 的演算法 page fault 越少；選得不好 page fault 增加，FIFO 甚至有 Belady's Anomaly。

FPR 下降、FNR 上升。$c$ 提高使判為 positive 的門檻變嚴，接受的樣本變少：分數落在新舊門檻之間的 negative 改判 negative，$FP$ 減少；同區間的 positive 也被拒絕，$FN$ 增加。

• Chatbot：被動單輪問答，自主程度低；使用者輸入一句提問觸發，例如問「台積電股價多少？」，回一句即結束。
• Copilot：嵌在工作情境中給建議或草稿，人在迴圈中主導；使用者在原生工作中操作即觸發，例如在編輯器打到一半，就地補完程式碼。
• Agent：自行規劃多步驟、呼叫工具並依回饋調整，自主程度高；使用者給一個目標觸發，例如「查台積電股價並算 100 股的台幣與美元金額」，自行呼叫兩個 API 後回覆。

best = []

def dfs(u, path, visited):
    if u == n:
        if len(path) > len(best):
            best[:] = path[:]
        return
    for v in range(1, n + 1):
        if G[u][v] and not visited[v]:
            visited[v] = True
            path.append(v)
            dfs(v, path, visited)
            path.pop()                 # 回溯：還原路徑
            visited[v] = False         # 回溯：還原 visited

visited = [False] * (n + 1)
visited[1] = True
dfs(1, [1], visited)

正確性：visited 保證路徑不重複經過同一頂點；回溯完整還原狀態，每條從 1 到 $n$ 的簡單路徑都恰被枚舉一次，故 best 必為最長者。