112 年 國立政治大學圖書資訊與檔案學研究所圖書資訊學組《計算機概論》

編碼（Encoding）是將資訊轉換成另一種格式的過程，以便進行儲存、傳輸或處理。其主要目的和重要性體現在以下幾個方面：

1. 資料壓縮與效率提升：透過編碼，可以去除資料中的冗餘資訊，減少資料量，從而節省儲存空間並提高傳輸效率。例如，ZIP 壓縮演算法就是一種編碼技術。
2. 資料傳輸與通訊：在網路傳輸或通訊系統中，原始資料可能不適合直接傳輸，需要經過編碼轉換成適合傳輸的格式，例如將文字轉換成位元串，或使用特定的通訊協定編碼。
3. 資料表示與標準化：編碼提供了一種標準化的方式來表示各種資訊，如文字、圖像、聲音、影片等。例如，ASCII 和 Unicode 是文字編碼標準，JPEG 和 PNG 是圖像編碼標準。這使得不同系統和應用程式之間能夠互通。

核心觀念

Hashing function（雜湊函數）是將任意長度的鍵值（key）轉換成固定範圍內的整數索引，用來快速定位雜湊表（hash table）中的資料位置：

$$h(key)=\text{hash table 中的索引}$$

若雜湊表大小為 $m$，通常要求：

$$0\leq h(key)<m$$

雜湊的主要意義，是將原本需要逐筆搜尋的資料，轉化為依索引直接存取，使查詢、插入與刪除在平均情況下可達到 $O(1)$ 時間複雜度。

---

解題方法

1. 將鍵值轉換為數字

若 key 本身是整數，可直接使用；若 key 是字串，則先將每個字元轉換為數值，再加權組合。例如：

$$K=c_1a^{n-1}+c_2a^{n-2}+\cdots+c_n$$

其中：

• $c_i$：第 $i$ 個字元的數值
• $a$：選定的基數，例如 $31$
• $n$：字串長度

2. 將數字映射到表格索引

最常見的方法是除法取餘法（division method）：

$$h(K)=K\bmod m$$

其中 $m$ 是雜湊表大小。

例如，雜湊表大小為 $13$，key 為 $78$：

$$h(78)=78\bmod 13=0$$

因此，資料會放在索引 $0$ 的位置。

若 key 為 $57$：

$$h(57)=57\bmod 13=5$$

資料便放在索引 $5$ 的位置。

3. 處理碰撞

不同 key 可能產生相同索引，稱為碰撞（collision）。例如：

$$h(26)=26\bmod 13=0$$ $$h(39)=39\bmod 13=0$$

此時 $26$ 與 $39$ 都要放入索引 $0$，必須使用碰撞處理方法。

方法一：鏈結法

每個索引存放一條鏈結串列。發生碰撞時，將資料接在同一索引的串列中。

查詢時：

1. 先計算 $h(key)$。
2. 找到對應的鏈結串列。
3. 在串列中逐一比對 key。

若負載因子合理，平均查詢時間仍接近 $O(1)$。

方法二：開放定址法

遞迴（Recursion）是一種在程式設計和數學中常見的概念，指的是一個過程或函數「呼叫自身」來解決問題的方法。

核心概念：

1. 自我呼叫 (Self-invocation)：遞迴函數或過程的核心特徵是它會在自己的定義體內呼叫自己。
2. 基底情況 (Base Case)：為了避免無窮迴圈，遞迴必須包含至少一個「基底情況」（或稱終止條件）。當滿足基底情況時，遞迴停止，並開始將結果向上回傳。
3. 遞迴步驟 (Recursive Step)：這是函數呼叫自身的部分。遞迴步驟的目標是將原始問題分解成一個或多個規模更小的、與原始問題相似的子問題。這些子問題的解最終會被用來建構原問題的解。

遞迴的運作方式：

當一個遞迴函數被呼叫時，它會先檢查是否滿足基底情況。

• 如果滿足，函數就直接返回一個預設的值（基底情況的結果），不再進行遞迴呼叫。
• 如果不滿足，函數會執行遞迴步驟：
  • 它會呼叫自己來解決一個較小的子問題。
  • 然後，它會利用子問題的解來計算原問題的解。
  • 最後，它會返回這個計算出的解。

這個過程會不斷重複，直到所有子問題都達到基底情況，然後結果一層一層地回傳，最終得到原問題的解。

這個問題涉及到最佳化（Optimization）問題的求解策略，主要區分為尋找「最佳解」（Optimal Solution）和「近似最佳解」（Approximate Solution）。

一、如何得到最佳解 (Optimal Solution)？

獲得最佳解通常意味著找到所有可能解中，在某個評估標準下（例如最小化成本、最大化收益）表現最好的那個解。達成此目標的方法取決於問題的性質：

1. 窮舉法 (Exhaustive Search / Brute-Force)：

   • 做法：檢驗所有可能的解，並比較它們的表現，最終選出最好的那個。
   • 適用性：適用於解空間較小、問題規模不大的情況。對於複雜問題，窮舉法的計算量可能呈指數級增長，變得不可行（例如旅行商問題）。
   • 優點：保證能找到最佳解。
   • 缺點：計算成本極高，時間複雜度難以接受。

2. 動態規劃 (Dynamic Programming, DP)：

   • 做法：將大問題分解為重疊的子問題，先求解子問題，並將結果儲存起來（記憶化或表格法），避免重複計算。然後利用子問題的解來逐步構建原問題的最佳解。
   • 適用性：適用於具有「最優子結構」（optimal substructure）和「重疊子問題」（overlapping subproblems）特性的問題。
   • 優點：通常比窮舉法效率高得多，能以多項式時間解決一些原本可能是指數級的問題。
   • 缺點：並非所有問題都適用；需要仔細設計狀態轉移方程。
   • 範例：最短路徑問題（如 Dijkstra 演算法，雖然 Dijkstra 本身是貪婪演算法，但其思想與 DP 有關聯；Bellman-Ford 演算法是 DP 的典型應用），背包問題，最長共同子序列。

3. 貪婪演算法 (Greedy Algorithm)：

   • 做法：在每一步選擇中，都做出當前看起來「最好」的局部選擇，期望這個局部選擇最終能導向全局的最佳解。
   • 適用性：適用於具有「貪婪選擇性質」（greedy choice property）的問題，即局部最佳選擇能夠導向全局最佳解。
   • 優點：通常比動態規劃更簡單、更快速。
   • 缺點：並非所有問題都適用；貪婪選擇不一定能保證得到全局最佳解。
   • 範例：活動選擇問題、霍夫曼編碼、Dijkstra 演算法（求單源最短路徑，適用於邊權非負的情況）。

4. 線性規劃 (Linear Programming, LP) 與整數規劃 (Integer Programming, IP)：

   • 做法：將最佳化問題表示為一組線性函數的目標函數，以及一組線性等式或不等式的約束條件。LP 允許變數為實數，IP 要求變數為整數。
   • 適用性：廣泛應用於資源分配、排程、路線規劃等領域。
   • 優點：有成熟的理論和演算法（如單形法 Simplex method、內點法 Interior-point method）來求解。
   • 缺點：IP 問題通常是 NP-hard 的，求解難度較高。

圖靈測試（Turing Test）是由英國數學家、邏輯學家艾倫·圖靈（Alan Turing）在 1950 年提出的，旨在為「機器是否能夠思考」這個問題提供一個操作性的定義和測試方法。

測試的設計與流程：

圖靈測試的標準版本通常是這樣進行的：

1. 參與者：測試包含三方：
   • 測試者 (Interrogator)：一個人類。
   • 被測試者：一個人類和一個機器（電腦程式）。
2. 隔離：測試者與被測試者（人類和機器）是物理隔離的，彼此無法看見對方。
3. 通訊方式：測試者只能透過文字訊息（例如透過鍵盤輸入和螢幕顯示）與兩位被測試者進行交流。這排除了外觀、聲音等非語言線索的影響。
4. 測試目標：測試者的任務是透過一連串的文字對話，判斷哪一位是被測試的人類，哪一位是機器。
5. 測試結果：
   • 如果測試者在經過一段時間的對話後，無法準確地區分出哪一個是人類，或者誤將機器判斷為人類，那麼這台機器就被認為通過了圖靈測試。

深度學習（Deep Learning, DL）和傳統機器學習（Traditional Machine Learning, ML）都屬於人工智能的範疇，旨在讓電腦從數據中學習並做出預測或決策。然而，它們在方法、架構和能力上存在顯著差異。

核心差異點：

1. 特徵提取 (Feature Extraction)：

   • 傳統機器學習：需要人工進行特徵工程。資料科學家或領域專家需要根據對問題的理解，手動選擇、設計和提取數據中有意義的特徵，然後將這些特徵輸入到學習模型中。例如，在識別貓的圖像時，可能需要手動定義邊緣、角點、顏色直方圖等特徵。
   • 深度學習：能夠自動從原始數據中學習特徵。深度神經網路（尤其是卷積神經網路 CNNs 和循環神經網路 RNNs）的多層結構可以逐級抽象化，從底層的簡單特徵（如邊緣、紋理）逐步學習到高層次的複雜特徵（如物體的部件、整體形態）。這大大減少了對人工特徵工程的依賴。

2. 模型架構與複雜度：

   • 傳統機器學習：模型通常較為簡單，例如支援向量機 (SVM)、決策樹 (Decision Tree)、隨機森林 (Random Forest)、邏輯迴歸 (Logistic Regression)、K-近鄰 (KNN) 等。這些模型通常假設數據之間存在某種特定的數學關係，且對特徵的品質非常敏感。
   • 深度學習：模型基於深度神經網路，具有多個（通常是數十到數百個）隱藏層。這種深層結構賦予了模型學習複雜、高維度數據表示的能力。

3. 數據量需求：

   • 傳統機器學習：在數據量相對較小時，表現往往不錯，甚至優於深度學習。
   • 深度學習：通常需要大量的標記數據才能發揮其威力。隨著數據量的增加，深度學習模型的性能通常會持續提升，而傳統機器學習模型的性能提升會趨於平緩。

4. 計算資源需求：

   • 傳統機器學習：對計算資源的要求相對較低，在普通 CPU 上即可高效運行。

深度學習模型，尤其是大型神經網路，之所以高度依賴 GPU（Graphics Processing Unit，圖形處理單元），主要是因為 GPU 的架構特性與深度學習的計算需求高度契合。

GPU 的架構優勢：

1. 大規模並行處理能力 (Massive Parallelism)：

   • CPU (Central Processing Unit)：設計用於處理各種複雜任務，擁有少量但強大的核心，擅長序列處理和複雜邏輯運算。
   • GPU：設計用於處理圖形渲染，擁有數千個較為簡單的核心。這種架構非常適合同時執行大量相同或相似的計算任務。
   • 深度學習的計算模式：深度學習的訓練和推理過程涉及大量的矩陣乘法、向量運算和元素級操作。這些運算本質上是高度並行的。例如，在神經網路的前向傳播和反向傳播中，每一層的計算都可以分解成許多獨立的、可並行的子運算。GPU 的大規模並行架構能夠同時處理這些子運算，極大地加速了整個計算過程。

2. 高記憶體頻寬 (High Memory Bandwidth)：

   • 深度學習模型通常包含數百萬甚至數十億的參數，這些參數和中間計算結果需要被頻繁地讀取和寫入。

「3奈米製程」（3nm process node）指的是半導體製造技術的先進節點，代表著晶體管的尺寸和電路密度達到了新的水平。雖然「3奈米」這個標記本身是一個市場和技術演進的代稱，實際的物理尺寸可能與標記的奈米數不完全吻合，但它代表了當前最先進的製程技術之一。其主要優點包括：

1. 更高的電晶體密度 (Increased Transistor Density)：

   • 製程技術的進步意味著在相同面積的晶片上可以集成更多的電晶體。3奈米製程相較於前一代製程（如 5奈米、7奈米），能夠在單位面積內塞入更多的電晶體。
   • 優點：這使得晶片設計者能夠在相同尺寸的封裝內實現更複雜的功能，或者在相同功能下製造出更小的晶片。這對於提升行動裝置（如智慧型手機、平板電腦）的性能和功能，同時保持或縮小體積至關重要。

2. 更低的功耗 (Reduced Power Consumption)：

   • 隨著電晶體尺寸的縮小和結構的優化（例如從 FinFET 到 Gate-All-Around, GAA 等新結構），電晶體的漏電流和操作電壓通常可以降低。
   • 優點：這直接轉化為更低的能源消耗。對於電池供電的設備（如智慧型手機、筆記型電腦、穿戴裝置）來說，更低的功耗意味著更長的電池續航時間。對於數據中心和伺服器而言，也能降低運營成本和散熱壓力。

GAN（Generative Adversarial Network，生成對抗網路）是一種由 Ian Goodfellow 及其同事於 2014 年提出的深度學習模型架構。它由兩個神經網路組成，這兩個網路相互競爭、相互學習，最終目標是生成逼真的數據。

GAN 的組成與工作原理：

GAN 的核心思想是「對抗學習」，它包含兩個主要組件：

1. 生成器 (Generator, G)：

   • 任務：負責生成新的數據樣本。它接收一個隨機雜訊向量（通常是從一個簡單分佈，如標準常態分佈中抽取的）作為輸入，並試圖將這個雜訊轉換成一個看起來像是真實數據的輸出。
   • 學習目標：生成器希望欺騙判別器，使其誤以為生成的數據是真實的。

2. 判別器 (Discriminator, D)：

   • 任務：負責判斷輸入的數據是真實的（來自真實數據集）還是偽造的（由生成器生成）。它接收一個數據樣本（真實或偽造）作為輸入，並輸出一個機率值，表示該樣本為真實數據的可能性。
   • 學習目標：判別器希望能夠準確地區分真實數據和生成器生成的偽造數據。

對抗學習過程 (Adversarial Training)：

這兩個網路以一種「零和博弈」（zero-sum game）或「對抗」的方式進行訓練：

RAID（Redundant Array of Independent Disks，獨立磁碟冗餘陣列）是一種將多個物理硬碟組合起來，以提供數據冗餘、性能提升或兩者兼具的技術。以下是 RAID 0、RAID 1 和 RAID 5 的介紹：

1. RAID 0 (條帶化，Striping)

• 原理：將數據分割成塊（chunks），然後在多個磁碟上連續地寫入這些數據塊。例如，塊 1 寫到磁碟 A，塊 2 寫到磁碟 B，塊 3 寫到磁碟 A，塊 4 寫到磁碟 B，以此類推。
• 目的：提升讀寫性能。由於數據被分散到多個磁碟上，讀取和寫入操作可以並行進行，大大縮短了 I/O 時間。
• 磁碟數量要求：最少 2 個磁碟。
• 容量：所有磁碟的總容量。例如，兩個 1TB 的磁碟組成 RAID 0，總容量為 2TB。
• 冗餘/容錯：無。如果其中任何一個磁碟發生故障，整個陣列的數據都將丟失，因為數據被分割儲存，無法獨立恢復。
• 適用場景：需要極高讀寫性能且數據丟失風險可接受的場景，例如影片編輯的臨時儲存、遊戲的加載加速等。

2. RAID 1 (鏡像，Mirroring)

• 原理：將一份數據完整地寫入到兩個或多個磁碟上。每個磁碟都包含一份完整的數據副本。
• 目的：提供數據冗餘和容錯能力。如果一個磁碟發生故障，系統可以從另一個磁碟上無縫地繼續工作，數據不會丟失。
• 磁碟數量要求：最少 2 個磁碟。
• 容量：最小的磁碟容量。例如，兩個 1TB 的磁碟組成 RAID 1，總容量只有 1TB，因為另一個 1TB 磁碟是作為備份。
• 性能：讀取性能通常有所提升（可以從任何一個磁碟讀取），但寫入性能與單個磁碟相當或略低（因為需要同時寫入多個磁碟）。
• 適用場景：需要高數據可靠性，且對性能要求不是極致的場景，例如作業系統啟動磁碟、關鍵應用程式的數據庫。

3. RAID 5 (帶有奇偶校驗的條帶化，Striping with Parity)

此題考查有符號數值（Signed Integer）的表示範圍。對於 $n$ bits 的有符號數值，最常見的表示法是「二補數」（Two's Complement）。

二補數的表示範圍：

對於 $n$ bits 的二補數，其表示的整數範圍是從 $-2^{n-1}$ 到 $2^{n-1} - 1$。

• 負數範圍：最小的負數是 $-2^{n-1}$。
• 正數範圍：最大的正數是 $2^{n-1} - 1$。
• 零：表示為全零。

為什麼是 $-2^{n-1} \sim 2^{n-1} - 1$？

• 總共有 $2^n$ 種可能的組合：由於有 $n$ 個位元，總共有 $2^n$ 種不同的組合。
• 分配給正負數：在二補數表示法中，最高位元（MSB）用來表示符號：0 表示正數或零，1 表示負數。
  • 為了讓正負數的表示數量盡可能平衡，並包含零，通常會這樣分配：
    • 有一個表示零的組合（全零）。
    • 剩下的 $2^n - 1$ 種組合被分配給正數和負數。
    • 正數的表示從 1 開始，到 $2^{n-1} - 1$。這樣有 $2^{n-1} - 1$ 個正數。

此題考查二進位（Binary）轉十進位（Decimal）的轉換。題目給出一個 8 位元的二進位數：11101100。

轉換方法：

二進位數的每一位代表 $2$ 的某個次方。從右邊（最低位）開始，分別是 $2^0, 2^1, 2^2, \dots$。將二進位數的每一位與其對應的 $2$ 的次方相乘，然後將所有結果加總，即可得到十進位值。

對於 8 位元的二進位數 $b_7 b_6 b_5 b_4 b_3 b_2 b_1 b_0$，其十進位值為：
$D = b_7 \times 2^7 + b_6 \times 2^6 + b_5 \times 2^5 + b_4 \times 2^4 + b_3 \times 2^3 + b_2 \times 2^2 + b_1 \times 2^1 + b_0 \times 2^0$

將題目中的二進位數 11101100 代入：
$b_7 = 1, b_6 = 1, b_5 = 1, b_4 = 0, b_3 = 1, b_2 = 1, b_1 = 0, b_0 = 0$

此題考查 Python 中列表（List）的賦值與修改行為，特別是關於「淺拷貝」與「傳遞參考」的概念。

程式碼分析：

1. a = [1,2,3]：創建一個列表 a，包含元素 1, 2, 3。
2. b = a：這行程式碼不是創建一個新的列表，而是讓變數 b 指向與 a 相同的列表物件。在 Python 中，列表是可變物件，賦值操作（如 b = a）是傳遞物件的「參考」（reference），而不是複製物件本身。因此，a 和 b 現在指向記憶體中的同一個列表。
3. b[2] = 65：這行程式碼修改的是 b 所指向的列表。由於 a 和 b 指向同一個列表，所以這個修改也會影響到 a。列表 b 的索引為 2 的元素（即第三個元素）被從 3 修改為 65。此時，列表 a 和 b 的內容都變成了 [1, 2, 65]。
4. print(a==b)：這行程式碼比較列表 a 和列表 b 是否相等。在 Python 中，== 運算子用於比較兩個物件的值是否相等。由於 a 和 b 現在都指向內容為 [1, 2, 65] 的同一個列表物件，它們的值是相等的。

此題考查物件導向程式設計（Object-Oriented Programming, OOP）的基本概念，特別是關於類別（Class）的組成和與物件的關係。

物件導向程式設計中的核心概念：

• 類別 (Class)：是創建物件的藍圖或模板。它定義了一組屬性 (Attributes) 和方法 (Methods)，這些是物件將擁有的數據和行為。
• 物件 (Object)：是類別的實例 (Instance)。每個物件都擁有類別定義的屬性和方法，並且可以擁有自己的數據值。
• 屬性 (Attribute)：代表物件的狀態或數據。例如，一個「汽車」類別可能有「顏色」、「品牌」、「速度」等屬性。
• 方法 (Method)：代表物件的行為或操作。例如，一個「汽車」類別可能有「啟動引擎」、「加速」、「煞車」等方法。
• 繼承 (Inheritance)：是一種機制，允許一個類別（子類別或衍生類別）繼承另一個類別（父類別或基底類別）的屬性和方法。這促進了程式碼的重用和建立「is-a」關係。例如，「跑車」類別可以繼承「汽車」類別。

此題考查數位影像中像素的顏色表示與記憶體佔用。

「全彩影像」（True Color）通常指的是能夠顯示 24 位元色彩深度，也就是每個像素使用 24 位元來表示其顏色。

色彩深度與位元：

• 位元 (bit)：是電腦儲存資訊的最小單位，只能是 0 或 1。
• 位元組 (byte)：通常由 8 個位元組成 ($1 \text{ byte} = 8 \text{ bits}$)。
• 色彩深度 (Color Depth)：指在一個像素中，用多少位元來表示其顏色。

全彩 (True Color) 的標準表示：

在最常見的全彩標準中，每個像素由三個顏色通道組成：紅 (Red, R)、綠 (Green, G)、藍 (Blue, B)。這就是 RGB 色彩模型。

• 每個顏色通道（R, G, B）通常分配 8 位元來表示其強度。
• 因此，一個像素的總色彩深度為：8 位元 (R) + 8 位元 (G) + 8 位元 (B) = 24 位元。

位元轉位元組：

由於 1 位元組 (byte) = 8 位元 (bits)，我們可以將 24 位元轉換為位元組：

此題考查對當前大型語言模型（LLM）底層架構的了解。ChatGPT 是由 OpenAI 開發的，其核心是基於 Transformer 架構。

ChatGPT 的架構背景：

• Transformer 架構：Transformer 模型於 2017 年在論文 "Attention Is All You Need" 中提出，徹底改變了自然語言處理（NLP）領域。它引入了「自注意力機制」（Self-Attention Mechanism），能夠有效地捕捉序列中長距離的依賴關係，並且在並行計算方面比傳統的 RNN 和 LSTM 更具優勢。
• GPT 系列：OpenAI 開發的 GPT（Generative Pre-trained Transformer）系列模型，包括 GPT-2、GPT-3、GPT-3.5 (ChatGPT 的基礎) 和 GPT-4，都是基於 Transformer 架構的解碼器 (Decoder) 部分進行預訓練和微調的。它們通過在海量文本數據上進行預訓練，學習語言的模式、知識和推理能力，然後通過微調（包括人類反饋的強化學習 RLHF）來優化其對話和指令遵循能力。

選項分析：

泡沫排序（Bubble Sort）是一種簡單的排序演算法，它重複地走訪要排序的列表，一次比較兩個相鄰的元素，如果它們的順序錯誤就把它們交換過來。走訪列表的工作是重複地進行直到沒有再需要交換，也就是該列表已經排序完成。這個演算法的名字由來是因為越小的元素會經由交換慢慢「浮」到列表的頂端（或大的元素「沉」到底部）。

演算法邏輯：

1. 從列表的起始位置開始，比較第一個元素和第二個元素。
2. 如果第一個元素大於第二個元素，則交換它們的位置。
3. 移動到下一對元素（第二個和第三個），重複步驟 2。
4. 持續這個過程，直到列表的末尾。此時，最大的元素會被移動到列表的最後一個位置。
5. 重複上述步驟，但每次走訪時，由於最後一個元素（或最後幾個元素）已經排序好，可以縮小走訪的範圍。
6. 當某一次完整的走訪過程中，沒有發生任何交換，表示列表已經完全排序，演算法可以終止。

Pseudo Code 實現：

以下是用 Pseudo Code 實現的泡沫排序算法，用於排序一個包含 10 個數字的列表（假設列表名為 arr，長度為 n，這裡 n=10）：