114 年 國立臺灣大學生醫電子與資訊學研究所丙組《計算機概論與演算法》

核心觀念

本題為研究所入學考試中高分佔比（40%）的經典名詞解釋題，全方位涵蓋計算機科學五大核心領域：

1. 演算法與計算理論：NP-Complete、Palindrome、MST、Hash Function。
2. 資料結構：Red-Black Tree、Heap Data Structure。
3. 作業系統與硬體架構：NTFS File System、Thread、GPU。
4. 計算機網路與資訊安全：HTTPS、HTTP Cookie、DNS、VPN、TCP/IP、DHCP。
5. 軟體工程、人工智慧與新興技術：SVM、AI、OOP、Turing Test、SQL。

答題標準要求具備「參考書等級」的嚴謹度，每一子題皆須明確交代：英文全名（若為縮寫）、精確定義（含數學式化表示）、核心機制與內容、設計目的及實際應用與實例。

---

解題方法與作答架構

針對此類開放式名詞解釋，評分標準側重於架構的條理性與定義的精確度。針對每一名詞，均採用以下標準模組進行推導與論述：

• 英文全名（Full Name）：展開縮寫。
• 數學定義 / 嚴謹定義（Definition）：使用集合論、邏輯式或形式語言給出數學形式。
• 核心內容與機制（Content & Mechanism）：解析底層原理與關鍵特徵。
• 目的（Purpose）：說明該技術被發明所欲解決的痛點。
• 應用與實例（Application & Example）：列舉產業界或演算法中的具體使用情境。

---

名詞詳解（第 (1) 至 (20) 題逐題解析）

(1) NP complete

• 英文全名：Non-deterministic Polynomial-time Complete（NP 完全）
• 數學定義：
  在計算複雜度理論中，一個判定問題（Decision Problem）或語言 $L$ 屬於 $\text{NP-Complete}$（簡記為 $L \in \text{NPC}$），若且唯若滿足以下兩項條件：
  1. $L \in \text{NP}$（可在多項式時間內由非確定型圖靈機驗證其解）。
  2. $\forall L' \in \text{NP}, L' \le_p L$（所有屬於 NP 的問題皆可在多項式時間內歸約至 $L$，即 $L$ 具備 NP-hard 性質）。
• 核心內容：NPC 是 NP 集合中「最難」的問題群。若能在確定型圖靈機（Deterministic Turing Machine）上找到任一 NPC 問題的多項式時間演算法（即存在 $O(n^k)$ 解法），則可推導出 $\text{P} = \text{NP}$。
• 目的：界定計算問題的內在複雜度極限，指引演算法設計者放棄尋找多項式時間的精確解，轉向近似演算法（Approximation Algorithms）或啟發式演算法（Heuristics）。
• 應用與實例：
  • 實例：布林可滿足性問題（3-SAT，由 Cook-Levin 定理證明為首個 NPC 問題）、旅行推銷員問題（TSP 判定版）、0/1 背包問題（0/1 Knapsack Decision）、最大團問題（Max Clique）。

---

(2) palindrome

• 定義與數學表示：
  給定一有限字母集 $\Sigma$ 上的字串 $S = s_1 s_2 \dots s_n$（其中 $s_i \in \Sigma$）。若對所有 $1 \le i \le n$，皆滿足： $$s_i = s_{n-i+1}$$ 即字串與其反轉字串（Reversal）完全相同（$S = S^R$），則稱 $S$ 為迴文。空字串 $\epsilon$ 亦定義為迴文。
• 核心內容：在形式語言與自動機理論中，迴文語言 $L = \{w w^R \mid w \in \Sigma^*\}$ 屬於非確定性無歧義上下文無關語言（Deterministic Context-Free Language 若有中央分隔符號，否則為 Non-deterministic CFL），無法由有限狀態機（FSM）識別，需借助堆疊（Pushdown Automaton）處理。
• 目的：在字串處理與演算法設計中，作為動態規劃、雙指標搜尋及對稱性結構分析的基準模型。
• 應用與實例：
  • 實例：英文單字 "level"、"racecar"；迴文數 12321。
  • 應用：生物資訊學中限制酶識別的雙鏈 DNA 迴文序列（如 EcoRI 切割位點 5'-GAATTC-3' 及其互補鏈 3'-CTTAAG-5'）。

---

(3) SVM: Support Vector Machine

• 英文全名：Support Vector Machine（支援向量機）
• 數學定義：
  給定線性可分的訓練樣本集 $\mathcal{D} = \{(x_i, y_i)\}_{i=1}^n$，其中 $x_i \in \mathbb{R}^d, y_i \in \{-1, +1\}$。SVM 旨在尋找最佳超平面 $w^T x + b = 0$，滿足最大化幾何邊界（Margin）的二次規劃問題： $$\min_{w, b} \frac{1}{2} \|w\|^2$$ $$\text{subject to } y_i (w^T x + b) \ge 1, \quad \forall i = 1, \dots, n$$ 其中落於邊界 $y_i (w^T x + b) = 1$ 上的樣本點即稱為「支援向量」（Support Vectors）。
• 核心內容：基於結構風險最小化（Structural Risk Minimization）原理。面對非線性問題時，可透過核技巧（Kernel Trick，如 RBF Kernel $K(x, z) = \exp(-\gamma \|x-z\|^2)$）將低維特徵映射至高維希爾伯特空間以達成線性可分。
• 目的：建構強健的二元或多元分類器與迴歸模型，在具備高維特徵與小樣本數據時仍具備極佳泛化能力。
• 應用與實例：生物資訊基因表現譜分類、醫療影像癌症偵測、文字分類與手寫辨識（如 MNIST 數字辨識）。

---

(4) NTFS file system

• 英文全名：New Technology File System（新科技檔案系統）
• 定義：微軟公司（Microsoft）為 Windows NT 核心作業系統所設計的高效能、高安全性日誌型檔案系統（Journaling File System）。
• 核心內容：
  1. 核心資料結構為「主檔案表」（Master File Table, MFT），記錄所有檔案與目錄的元資料（Metadata）。
  2. 具備 USN 日誌（Update Sequence Number Journal），於系統崩潰時能快速進行資料一致性修復。
  3. 支援 ACL（存取控制清單）檔案級安全權限、EFS（加密檔案系統）、透明壓縮、稀疏檔案（Sparse Files）與磁碟配額。
• 目的：取代舊式 FAT32 檔案系統，突破單一檔案 4 GB 及磁碟分區容量限制，提供企業級的資料容錯與權限控管能力。
• 應用與實例：現今 Windows 10/11 系統碟（如 C:\）與外接硬碟的預設格式。

---

(5) thread in operating system

• 定義：作業系統進行 CPU 排程與分派執行的最小單位，亦被稱為輕量級行程（Lightweight Process, LWP）。
• 核心內容：
  1. 同一處理程序（Process）內的所有執行緒共享該行程的虛擬位址空間、程式碼段（Text Segment）、資料段（Data Segment）以及開啟的作業系統資源（如檔案描述符）。
  2. 每個執行緒各自擁有獨立的執行狀態：程式計數器（Program Counter, PC）、暫存器集合（Register Set）及獨立的堆疊（Stack）。
• 目的：降低行程間 Context Switch（內文切換）與資源配置的巨大負擔，實現多核心硬體上的真平行計算與高並行（Concurrency）。
• 應用與實例：
  • 網頁伺服器（如 Apache Worker 模型）：主行程監聽連線，為每一 HTTP 請求分配獨立執行緒並行處理。
  • 文字處理軟體：一個執行緒負責前景使用者打字互動，另一個背景執行緒自動執行拼字檢查與定時存檔。

---

(6) GPU

• 英文全名：Graphics Processing Unit（圖形處理器）
• 定義：一種高度平行化、具備多核心架構的專用微處理器，專門設計用於加速影像渲染、幾何變換與大規模數值矩陣計算。
• 核心內容：與 CPU 專注於降低單執行緒延遲（Low Latency）與複雜分支預測不同，GPU 採用大量算術邏輯單元（ALU）構建 SIMD（單指令多資料流）或 SIMT（單指令多執行緒）架構，強調超高資料吞吐量（High Throughput）。
• 目的：卸載 CPU 於圖形渲染與巨量重複性數值運算上的瓶頸，提供數十倍至數百倍的平行運算吞吐率。
• 應用與實例：3D 電腦繪圖與光線追蹤、深度學習大型語言模型訓練（如利用 NVIDIA CUDA 架構加速 Tensor 矩陣乘法）、分子動力學模擬。

---

(7) AI

• 英文全名：Artificial Intelligence（人工智慧）
• 定義：計算機科學的一門核心領域，致力於研發能模擬、延伸與擴展人類感知、推理、學習、決策及問題解決等智慧行為的計算系統與演算法。
• 核心內容：技術範疇包含符號邏輯推論、專家系統、機器學習（Machine Learning，含監督式、非監督式與增強式學習）以及深度類神經網路（Deep Neural Networks）。
• 目的：使機器具備自主環境感知與資料抽象能力，自動化處理傳統確定性演算法難以解決的複雜、非結構化問題。
• 應用與實例：自動駕駛汽車之環境辨識與路徑規劃、醫療病理切片判讀、語音助理（如 Siri）、大語言模型系統（如 Gemini）。

---

(8) HTTPS

• 英文全名：Hypertext Transfer Protocol Secure（超文本傳輸安全協定）
• 定義：以安全為導向的 HTTP 協定，透過在應用層（HTTP）與傳輸層（TCP）之間引入傳輸層安全協定（TLS/SSL）建立加密與驗證機制。預設使用 TCP 連接埠 443。
• 核心內容：
  1. 身分驗證：利用數位憑證機構（CA）核發之 X.509 憑證，透過非對稱加密驗證伺服器身分。
  2. 資料加密：透過 TLS 握手協商建立對稱金鑰（如 AES-GCM），對傳輸內容進行全端對端加密。
  3. 完整性保護：透過訊息鑑別碼（MAC / HMAC）防止傳輸中資料遭竄改。
• 目的：防止網路通訊遭受中間人攻擊（MITM）、封包竊聽（Eavesdropping）與偽造。
• 應用與實例：網路銀行系統、電子商務線上刷卡頁面、現代 Web 網站連線（網址列前綴 https:// 與綠色鎖頭標示）。

---

(9) HTTP cookie

• 定義：由 Web 伺服器產生並經由 HTTP 回應標頭傳送至客戶端（瀏覽器），由瀏覽器保存在本機端的一小段鍵值對（Key-Value Pair）狀態資料。
• 核心內容：
  1. 伺服器透過 HTTP Response 標頭 Set-Cookie: name=value; Domain=...; Path=...; Secure; HttpOnly 寫入。
  2. 瀏覽器在後續向符合網域的請求中，自動在 HTTP Request 標頭附帶 Cookie: name=value 回傳。
• 目的：克服 HTTP 協定天生的無狀態（Stateless）特質，在客戶端與伺服器之間維護連續的對話狀態（Session Management）。
• 應用與實例：
  • 保持使用者登入狀態（記錄 Session ID 或 JWT Token）。
  • 電子商務網站跨分頁記錄購物車商品。
  • 使用者個人化介面設定（如深色/淺色主題切換標記）。

---

(10) DNS: Domain Name System

• 英文全名：Domain Name System（網域名稱系統）
• 定義：網際網路中採用分散式、階層式架構的命名與解析資料庫系統，負責在人類可讀的網域名稱（FQDN）與機器可讀的 IP 位址之間進行雙向解析。預設使用 UDP/TCP 53 連接埠。
• 核心內容：
  1. 階層架構由根伺服器（Root Nameservers .）、頂級網域伺服器（TLD Servers，如 .com, .edu）及權威名稱伺服器（Authoritative Servers）組成。
  2. 提供遞迴查詢（Recursive Query）與迭代查詢（Iterative Query）機制，並搭配快取（Caching）降低網路負載。
• 目的：消除使用者直接記憶二進位或純數值 IP 位址（如 IPv4 32-bit、IPv6 128-bit）的困難，實現主機位址變更時的透明對應。
• 應用與實例：使用者在瀏覽器輸入 www.ntu.edu.tw，DNS 解析伺服器依階層尋找並回傳對應 IP（如 140.112.8.116）。

---

(11) OOP

• 英文全名：Object-Oriented Programming（物件導向程式設計）
• 定義：一種以「物件（Object）」作為基本建構單元的軟體設計與程式設計範式（Programming Paradigm）。物件將「狀態/資料（Attributes/Fields）」與「行為/函式（Methods）」封裝為一體。
• 核心內容：具備四大核心特徵：
  1. 封裝（Encapsulation）：隱藏內部實作細節，僅透過公開介面與外界互動（Information Hiding）。
  2. 繼承（Inheritance）：子類別（Derived Class）繼承父類別（Base Class）之屬性與方法，促進程式碼重用。

這題要求將一個算術表達式轉換為對應的二元運算樹，並寫出其前序 (prefix) 和後序 (postfix) 表達式。

核心觀念： 算術表達式樹、前序遍歷、後序遍歷。

解題步驟：

1. 建立表達式樹 (Expression Tree)：

   • 從最內層的括號和最低優先級的運算子開始。
   • 運算子作為內部節點，運算元（變數或常數）作為葉節點。
   • 二元運算樹的結構反映了運算子及其運算元的組合關係。

   給定的表達式為：(A*(E/(B-F)))*(A+B)/D

   首先處理最內層的括號 (B-F)，它成為一個子樹，根為 -，左右子節點為 B 和 F。
   接著處理 E/(B-F)，根為 /，左子節點為 E，右子節點為 (B-F) 的子樹。
   然後處理 A*(E/(B-F))，根為 *，左子節點為 A，右子節點為 E/(B-F) 的子樹。
   接著處理 (A+B)，根為 +，左右子節點為 A 和 B。
   然後處理 (A*(E/(B-F)))*(A+B)，根為 *，左子節點為 A*(E/(B-F)) 的子樹，右子節點為 (A+B) 的子樹。
   最後處理 ... / D，根為 /，左子節點為 (A*(E/(B-F)))*(A+B) 的子樹，右子節點為 D。

   表達式樹結構：

           /
          / \
         *   D
        / \
       *   +
      / \ / \
     A  /  A  B
       / \
      E   -
         / \
        B   F
   

2. 前序遍歷 (Prefix Notation / Polish Notation)：

   • 遍歷順序：根節點 -> 左子樹 -> 右子樹。
   • 對於表達式樹，前序遍歷結果是：運算子 + 左子樹的前序遍歷 + 右子樹的前序遍歷。

   從根節點 / 開始：
   /
   左子樹 *：
   *
   左子樹 A：A
   右子樹 /：
   /

核心觀念

二元搜尋樹（Binary Search Tree, BST）滿足：

• 每個節點的左子樹所有鍵值皆小於該節點。
• 每個節點的右子樹所有鍵值皆大於該節點。
• 插入新鍵值時，從根節點開始比較：
  • 若新鍵值較小，往左子樹走。
  • 若新鍵值較大，往右子樹走。
  • 抵達空位置後，將新節點插入該處。

本題依序插入：

$$3,\ 9,\ 8,\ 6,\ 5,\ 4,\ 1,\ 2,\ 7$$

插入順序會影響樹形，因此必須依序處理，不能直接將鍵值排序後連成樹。

解題方法

1. 插入 $3$

樹為空，$3$ 成為根節點。

3

2. 插入 $9$

$9>3$，往右插入。

3
 \
  9

3. 插入 $8$

$8>3$，往右至 $9$；因為 $8<9$，插入 $9$ 的左子樹。

3
 \
  9
 /
8

4. 插入 $6$

$6>3$，往右至 $9$；$6<9$，往左至 $8$；$6<8$，插入 $8$ 的左子樹。

3
 \
  9
 /
8
/
6

5. 插入 $5$

比較路徑為：

$$5>3,\quad 5<9,\quad 5<8,\quad 5<6$$

因此插入 $6$ 的左子樹。

3
 \
  9
 /
8
/
6
/
5

6. 插入 $4$

比較路徑為：

$$4>3,\quad 4<9,\quad 4<8,\quad 4<6,\quad 4<5$$

因此插入 $5$ 的左子樹。

這題要求列出作業系統中導致死鎖 (deadlock) 的四個必要條件。

核心觀念： 死鎖的必要條件。

死鎖是指兩個或多個進程（或執行緒）在執行過程中，因爭奪資源而造成的一種互相等待的現象，若無外力作用，它們都將無法繼續執行。要發生死鎖，必須同時滿足以下四個必要條件：

1. 互斥 (Mutual Exclusion)： 至少有一種資源必須是非共享的，即一次只能被一個進程使用。如果有多個進程同時請求該資源，其中一個進程會被阻塞，直到持有該資源的進程釋放它。

   • 解釋： 這是死鎖的基礎，因為如果資源可以被同時使用，就不會發生等待。

2. 佔有並等待 (Hold and Wait)： 一個進程至少佔有一個資源，並且正在等待另一個進程釋放它所佔有的其他資源。

   • 解釋： 進程在持有部分資源的同時，又去請求其他資源，造成了潛在的等待鏈。

3. 非搶佔 (No Preemption)： 資源不能被強制從持有它的進程中剝奪，只能由持有者主動釋放。

   • 解釋： 如果系統可以強制剝奪資源，那麼即使進程持有資源，也可以被系統收回分配給等待的進程，從而避免死鎖。

這題要求將一個帶有小數的十進制負數轉換為二補數 (two's complement) 表示法。

核心觀念： 二補數表示法、小數轉換。

步驟：

1. 確定二補數的位元數： 題目沒有明確指定位元數。通常，如果沒有指定，會根據數值的大小來估計一個足夠的位元數。對於 -19.375，我們需要足夠的整數部分位元和足夠的小數部分位元。

   • 整數部分 -19：
     • 19 的二進制是 10011。
     • 為了表示負數，我們需要至少 1 個符號位。加上符號位，至少需要 6 位（例如 5 位值 + 1 位符號位）。
   • 小數部分 0.375：
     • 0.375 * 2 = 0.75 (取整數 0)
     • 0.75 * 2 = 1.5 (取整數 1)
     • 0.5 * 2 = 1.0 (取整數 1)
     • 所以 0.375 的二進制是 0.011。

   讓我們假設使用 8 位元來表示整數部分，並使用 3 位元來表示小數部分，總共 11 位元（不含符號位）。或者，更常見的是，我們需要固定一個總位數，例如 16 位元或 32 位元。
   如果題目是針對整數，例如 -19，通常會指定位數。對於小數，則需要指定小數點的位置。

   假設我們使用一個固定的小數點位置，例如 8 位整數部分和 8 位小數部分，總共 16 位元。

   轉換 -19 為 8 位元二補數：

   • 19 的二進制是 00010011 (8 位)。
   • 取反：11101100
   • 加 1：11101101
   • 所以，-19 的 8 位元二補數是 11101101。

   轉換 0.375 為 8 位元二進制小數：

   • 0.375 的二進制是 0.011。
   • 要轉換為 8 位元，我們需要補零：0.01100000。

   組合起來（整數部分 + 小數部分）：
   如果我們將 -19.375 視為一個固定點數 (fixed-point number)，例如 8.8 格式（8 位整數，8 位小數），那麼：

   • -19 是 11101101 (8 位)
   • 0.375 是 0.01100000 (8 位)

   將兩者組合起來，並考慮小數點位置：
   11101101.01100000 (這不是二補數表示，這是帶符號的固定點表示)

   二補數的標準做法是，先將數值轉換為二進制，然後對整個二進制表示進行二補數運算。

   方法一：先轉換為二進制，再求二補數。

   • 將 -19.375 視為一個數值。
   • 首先處理正數 19.375。
   • 19 的二進制是 10011。
   • 0.375 的二進制是 0.011。
   • 組合起來：10011.011。

   現在，我們需要決定位數。假設我們使用 16 位元來表示，其中最高位是符號位，然後是 7 位整數部分和 8 位小數部分（7.8 格式）。

   • 19 的 7 位二進制是 0010011。
   • 0.375 的 8 位二進制是 01100000。
   • 正數 19.375 的 7.8 格式表示為 0 0010011 . 01100000。

   現在，我們需要將這個正數轉換為負數的二補數。

   1. 取反 (One's Complement)： 將所有位元反轉。
      1 1101100 . 10011111
   2. 加 1： 在最低有效位 (LSB) 處加 1。
      1 1101100 . 10011111
+ 1
--------------------
1 1101100 . 10100000

   所以，-19.375 在 7.8 格式（共 16 位）的二補數表示為 11101100.10100000。

   • 注意：這裡的點 . 是小數點，它在二補數表示中是隱含的，不實際佔用位元。

   方法二：直接對負數進行二補數計算（針對整數部分）。

   • 負數 -19 的二補數：
     • 19 的二進制是 00010011 (假設 8 位整數)。
     • 取反：11101100
     • 加 1：11101101
   • 小數部分 0.375 的二進制是 0.011。
   • 如果我們將 -19.375 視為一個數，並決定總位數，例如 16 位，且小數點位於第 8 位（即 8.8 格式）。
     • -19 的 8 位二補數是 11101101。
     • 0.375 的二進制是 0.011。
     • 將 0.011 擴展到 8 位小數：0.01100000。
     • 我們需要將 -19 和 0.375 結合。
     • 這意味著 -19.375 是 -19 加上 -0.375。
     • 或者，更直接地，將 19.375 轉換為二進制，然後對其進行二補數運算。

   讓我們使用一個明確的位數，例如 16 位，並假設小數點固定在第 8 位（8.8 格式）。

   • 數值是 -19.375。

   • 正數 19.375 的二進制表示：

     • 19 是 00010011 (8 位整數部分)。
     • 0.375 是 0.011。
     • 將 0.011 轉換為 8 位小數：0.01100000。
     • 所以，19.375 的 8.8 格式二進制是 00010011.01100000。

   • 現在，我們將這個正數的二進制表示轉換為負數的二補數。

   1. 取反 (One's Complement)：
      11101100.10011111
   2. 加 1 (LSB)：
      11101100.10011111
+ 1
--------------------
11101100.10100000

這題要求寫出解決「河內塔」（Tower of Hanoi）問題的遞迴偽代碼 (recursive pseudo code)。

核心觀念： 河內塔問題、遞迴。

河內塔問題描述：
有三根柱子（A, B, C）和 N 個大小不同的圓盤。所有圓盤初始時按照大小順序堆疊在 A 柱上（最大的在底部，最小的在頂部）。目標是將所有圓盤從 A 柱移動到 C 柱，移動過程中需要遵循以下規則：

1. 一次只能移動一個圓盤。
2. 較小的圓盤可以放在較大的圓盤上面。
3. 任何時候，大圓盤都不能放在小圓盤上面。

遞迴解決思路：
要將 N 個圓盤從 from 柱移動到 to 柱，需要藉助 temp 柱。

1. 基本情況 (Base Case)： 如果只有 1 個圓盤 (N=1)，直接將它從 from 柱移動到 to 柱。
2. 遞迴步驟 (Recursive Step)：
   a. 將 N-1 個圓盤從 from 柱移動到 temp 柱，藉助 to 柱。
   b. 將第 N 個（最大的）圓盤從 from 柱移動到 to 柱。
   c. 將 N-1 個圓盤從 temp 柱移動到 to 柱，藉助 from 柱。

偽代碼 (Pseudo code)：

函數 Hanoi(from, to, temp, N)：
// from: 起始柱子
// to: 目標柱子
// temp: 輔助柱子
// N: 要移動的圓盤數量

如果 `N` 等於 1：
    輸出 "將圓盤 1 從 " + `from` + " 移動到 " + `to`
    返回

// 步驟 a: 將 N-1 個圓盤從 `from` 移動到 `temp`，藉助 `to`
調用 `Hanoi(from, temp, to, N-1)`

// 步驟 b: 移動第 N 個圓盤
輸出 "將圓盤 " + `N` + " 從 " + `from` + " 移動到 " + `to`

// 步驟 c: 將 N-1 個圓盤從 `temp` 移動到 `to`，藉助 `from`
調用 `Hanoi(temp, to, from, N-1)`

偽代碼（更為標準的寫法）：

procedure Hanoi(source, destination, auxiliary, n)
    if n == 1 then
        print "Move disk 1 from " + source + " to " + destination
    else
        // Move n-1 disks from source to auxiliary, using destination as temporary
        Hanoi(source, auxiliary, destination, n-1)

        // Move the nth disk from source to destination
        print "Move disk " + n + " from " + source + " to " + destination

        // Move the n-1 disks from auxiliary to destination, using source as temporary
        Hanoi(auxiliary, destination, source, n-1)
    end if
end procedure

例子：
如果調用 Hanoi('A', 'C', 'B', 3)：

1. Hanoi('A', 'C', 'B', 3)
   • N=3，不是 1。
   • 調用 Hanoi('A', 'B', 'C', 2) (將 2 個盤從 A 移到 B，用 C 作輔助)
     • Hanoi('A', 'B', 'C', 2)
       • N=2，不是 1。
       • 調用 Hanoi('A', 'C', 'B', 1) (將 1 個盤從 A 移到 C，用 B 作輔助)
         • Hanoi('A', 'C', 'B', 1)

這題要求解釋 ChatGPT 中 GPT 的全稱，並比較 GPT 和卷積神經網路 (CNN) 的差異、優點和缺點。

核心觀念： 大型語言模型 (LLM)、Transformer 架構、卷積神經網路 (CNN)。

1. GPT 的全稱：
GPT 的全稱是 Generative Pre-trained Transformer。

• Generative (生成式)： 指模型能夠生成新的內容，如文字、程式碼等。
• Pre-trained (預訓練)： 指模型在海量數據上進行了大規模的預訓練，學習了豐富的語言知識和模式。
• Transformer (變壓器)： 指模型採用了 Transformer 架構，該架構以其自注意力機制 (self-attention mechanism) 而聞名，非常適合處理序列資料，尤其是自然語言。

2. GPT 與 CNN 的比較：

特徵	GPT (Generative Pre-trained Transformer)	CNN (Convolutional Neural Network)
主要應用	自然語言處理 (NLP)：文本生成、翻譯、問答、摘要、對話等。	圖像處理 (CV)：圖像識別、物件偵測、影像分割、圖像生成等。
核心架構	Transformer 架構，主要依賴自注意力機制 (Self-Attention)。	卷積層 (Convolutional Layers)，池化層 (Pooling Layers)，全連接層。
處理資料	序列資料（如文本、時間序列）。擅長捕捉長距離依賴關係。	格狀資料（如圖像的像素網格）。擅長捕捉局部空間特徵（如邊緣、紋理）。
資訊提取	透過自注意力機制，模型可以關注輸入序列中的任意部分，並權衡其重要性。	透過卷積核掃描輸入，提取局部空間特徵。
模型類型	通常是生成模型 (Generative Model)，但也可用於判別任務。	通常是判別模型 (Discriminative Model)，但也可構建生成模型 (如 DCGAN)。

GPT 的優點：

• 強大的語言理解與生成能力： 基於 Transformer 架構和大規模預訓練，GPT 在理解上下文、生成流暢且有意義的文本方面表現出色。
• 捕捉長距離依賴： 自注意力機制使其能有效地處理長文本，理解遠處詞語之間的關係。
• 通用性： 預訓練模型可以透過微調 (fine-tuning) 適應多種 NLP 任務，實現「一次訓練，多處應用」。
• 上下文學習 (In-context Learning)： 無需權重更新，僅透過提供範例 (few-shot learning) 就能執行新任務。

這題要求列出馮·諾依曼 (von Neumann) 架構的四個主要組成部分。

核心觀念： 馮·諾依曼計算機架構。

馮·諾依曼架構是現代計算機的基礎設計模型，其核心思想是將指令和數據儲存在同一個記憶體中，並使用一個中央處理單元 (CPU) 來順序執行指令。它包含以下四個主要組成部分：

1. 中央處理單元 (Central Processing Unit, CPU)：
   • 負責執行指令。
   • 通常包含：
     • 算術邏輯單元 (Arithmetic Logic Unit, ALU)： 執行算術運算（加、減、乘、除）和邏輯運算（AND, OR, NOT）。
     • 控制單元 (Control Unit, CU)： 負責從記憶體中取出指令，解碼指令，並向 ALU、記憶體和其他硬體部件發出控制訊號，協調整個計算機的操作。
     • 暫存器 (Registers)： 儲存正在處理的數據、指令地址和中間結果，速度極快。

核心觀念

OSI 是 Open Systems Interconnection（開放系統互連）參考模型，由下而上分為七層，用來描述資料如何從一台主機的應用程式，經過網路傳送到另一台主機。每一層負責一類網路功能，並使用下一層提供的服務。

傳送端會逐層加入控制資訊，接收端則逐層解析；這個過程稱為封裝與解封裝。常見的資料單位由下而上依序為：位元、訊框、封包、區段，以及上層資料。

解題方法

題目要求全名、列出七層並詳細說明功能。依照資料傳輸方向，從最接近實體媒介的第一層一路列到最接近使用者應用程式的第七層；說明各層時，掌握「傳輸範圍」與「處理的資訊」即可區分相鄰層。

OSI 七層與功能

層級	名稱	主要功能
第七層	應用層（Application Layer）	提供網路應用程式使用的服務介面，例如網頁瀏覽、電子郵件、檔案傳輸與名稱解析。它處理應用程式的網路需求；使用者操作的應用程式本身不等同於應用層。
第六層	表達層（Presentation Layer）	處理資料表示方式，使不同系統能正確理解資料。功能包括格式轉換、字元編碼、資料序列化、壓縮與加密、解密。
第五層	交談層（Session Layer）	建立、管理與終止兩個應用端點之間的交談。

這題要求根據提供的圖，寫出從節點 1 開始進行廣度優先搜尋 (Breadth-First Search, BFS) 的節點訪問順序。

核心觀念： 廣度優先搜尋 (BFS)。

廣度優先搜尋 (BFS) 演算法：
BFS 是一種圖遍歷演算法，它從一個起始節點開始，首先訪問所有與起始節點相鄰的節點，然後訪問與這些相鄰節點相鄰的節點，依此類推。它按照「層級」或「距離」來遍歷節點。

BFS 的實現通常使用佇列 (Queue)：

1. 將起始節點加入佇列。
2. 標記起始節點為已訪問。
3. 當佇列不為空時：
   a. 從佇列中取出一個節點。
   b. 處理該節點（在此題中，即記錄其順序）。
   c. 遍歷該節點的所有未訪問過的鄰居。
   d. 將這些未訪問過的鄰居加入佇列，並標記為已訪問。

根據提供的圖（請參閱原卷圖片）：
圖中節點及其鄰居關係如下（假設圖是無向的）：

• Node 0: 鄰居 7
• Node 1: 鄰居 2, 3
• Node 2: 鄰居 1, 3, 4
• Node 3: 鄰居 1, 2, 8
• Node 4: 鄰居 2, 3
• Node 7: 鄰居 0, 8
• Node 8: 鄰居 3, 7

從節點 1 開始 BFS：

1. 初始化：

   • 佇列 (Queue)：[1]
   • 已訪問節點 (Visited)：{1}
   • 訪問順序 (Order)：[]

2. 第一次迭代：

   • 從佇列取出節點 1。
   • 訪問順序：[1]
   • 節點 1 的鄰居是 2 和 3。
   • 2 未訪問，加入佇列，標記為已訪問。
   • 3 未訪問，加入佇列，標記為已訪問。
   • 佇列：[2, 3]
   • 已訪問：{1, 2, 3}

3. 第二次迭代：

   • 從佇列取出節點 2。
   • 訪問順序：[1, 2]
   • 節點 2 的鄰居是 1, 3, 4。
   • 1 已訪問，忽略。
   • 3 已訪問，忽略。
   • 4 未訪問，加入佇列，標記為已訪問。
   • 佇列：[3, 4]
   • 已訪問：{1, 2, 3, 4}

4. 第三次迭代：

   • 從佇列取出節點 3。
   • 訪問順序：[1, 2, 3]
   • 節點 3 的鄰居是 1, 2, 8。
   • 1 已訪問，忽略。
   • 2 已訪問，忽略。
   • 8 未訪問，加入佇列，標記為已訪問。
   • 佇列：[4, 8]
   • 已訪問：{1, 2, 3, 4, 8}

5. 第四次迭代：

   • 從佇列取出節點 4。
   • 訪問順序：[1, 2, 3, 4]
   • 節點 4 的鄰居是 2, 3。
   • 2 已訪問，忽略。
   • 3 已訪問，忽略。
   • 佇列：[8]
   • 已訪問：{1, 2, 3, 4, 8}

6. 第五次迭代：

   • 從佇列取出節點 8。
   • 訪問順序：[1, 2, 3, 4, 8]
   • 節點 8 的鄰居是 3, 7。
   • 3 已訪問，忽略。
   • 7 未訪問，加入佇列，標記為已訪問。
   • 佇列：[7]
   • 已訪問：{1, 2, 3, 4, 8, 7}

7. 第六次迭代：

   • 從佇列取出節點 7。
   • 訪問順序：[1, 2, 3, 4, 8, 7]
   • 節點 7 的鄰居是 0, 8。
   • 0 未訪問，加入佇列，標記為已訪問。
   • 8 已訪問，忽略。
   • 佇列：[0]
   • 已訪問：{1, 2, 3, 4, 8, 7, 0}

8. 第七次迭代：

   • 從佇列取出節點 0。
   • 訪問順序：[1, 2, 3, 4, 8, 7, 0]
   • 節點 0 的鄰居是 7。
   • 7 已訪問，忽略。
   • 佇列：[]
   • 已訪問：{1, 2, 3, 4, 8, 7, 0}

9. 結束： 佇列為空，BFS 完成。

搜尋順序： 1 -> 2 -> 3 -> 4 -> 8 -> 7 -> 0

注意： 如果一個節點有多個未訪問的鄰居，它們被加入佇列的順序取決於具體的圖表示法或遍歷鄰居的順序。在此，我們假設鄰居是按照節點編號從小到大或圖中出現的順序來處理的。例如，節點 1 的鄰居是 2 和 3，我們假設先處理 2，再處理 3。

檢查圖結構：
從圖上看，節點之間的連線是：
(0,7), (1,2), (1,3), (2,3), (2,4), (3,8), (7,8)
節點 4 實際上只有連到 2 和 3。
節點 0 實際上只有連到 7。
節點 7 實際上只有連到 0 和 8。