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

這題主要在考驗學生對近年來資訊科學領域重要名詞的理解程度。

(1) 大型語言模型 (Large Language Model, LLM)：
大型語言模型是指一種深度學習模型，特別是基於 Transformer 架構的類神經網路，經過海量文本數據的訓練，使其能夠理解、生成和處理人類語言。LLM 的核心在於其龐大的參數量和訓練數據量，這使得它們能夠學習到複雜的語言模式、上下文關聯，並執行各種自然語言處理 (NLP) 任務，如文本生成、翻譯、問答、摘要等。
【答案】一種經過海量文本數據訓練的深度學習模型，能夠理解和生成人類語言，執行多樣化的 NLP 任務。

(2) 智能合約 (Smart Contract)：
智能合約是一種在區塊鏈上運行的程式碼，它自動執行、控制或記錄法律上相關的事件和行為。合約的條款直接寫成程式碼，當預設的條件被滿足時，合約就會自動執行相應的動作，例如資金的轉移、資產的釋放等。其主要優勢在於自動化、透明、不可篡改和去中心化，減少了對中間人的依賴。
【答案】在區塊鏈上執行的程式碼，可自動執行合約條款，其條款直接寫成程式碼，滿足條件時自動執行，具有自動化、透明、不可篡改的特性。

本題主要考驗對數值最佳化演算法Golden Section Search的理解與實作能力，以及與Binary Search的比較。

核心觀念：Golden Section Search 是一種尋找單峰函數極小值的方法，利用黃金比例來逐步縮小搜尋區間。

(1) 實作 golden_search 函數：
目標函數為 $f(x) = (x-2)^2$。我們需要找到此函數在給定區間 $[a, b]$ 內的極小值。黃金分割比例 $\phi = \frac{\sqrt{5}-1}{2} \approx 0.618$。
演算法步驟：

1. 初始化搜尋區間 $[a, b]$。
2. 計算兩個內點 $x_1 = b - (b-a)\phi$ 和 $x_2 = a + (b-a)\phi$。
3. 計算函數值 $f(x_1)$ 和 $f(x_2)$。
4. 比較 $f(x_1)$ 和 $f(x_2)$:
   • 如果 $f(x_1) < f(x_2)$，則新的搜尋區間為 $[a, x_2]$。
   • 如果 $f(x_1) \ge f(x_2)$，則新的搜尋區間為 $[x_1, b]$。
5. 重複步驟 2-4，直到搜尋區間的寬度 $(b-a)$ 小於 tolerance，或者連續兩次迭代計算出的極小值點的距離小於 tolerance。題目要求是「兩次連續迭代的極小值之間的距離小於 tolerance」，這通常是指新的區間寬度 $(b-a)$。如果題目嚴格指「極小值點的距離」，則需要記錄前一次的極小值點。為符合一般實作，我們以區間寬度為判斷依據。
6. 返回區間的中心點 $(a+b)/2$ 作為極小值的近似值。

以下為 Python 實作範例：

import math

def golden_search(func, a, b, tolerance):
    phi = (math.sqrt(5) - 1) / 2  # 黃金分割比例
    
    while (b - a) > tolerance:
        x1 = b - (b - a) * phi
        x2 = a + (b - a) * phi
        
        f1 = func(x1)
        f2 = func(x2)
        
        if f1 < f2:
            b = x2  # 縮小區間到 [a, x2]
        else:
            a = x1  # 縮小區間到 [x1, b]
            
    # 迭代結束，返回區間的中心點作為近似極小值
    return (a + b) / 2

# 測試範例
def target_function(x):
    return (x - 2)**2

# 假設搜尋區間為 [0, 5], 誤差容忍度為 0.001
lower_bound = 0
upper_bound = 5
tol = 0.001

min_x = golden_search(target_function, lower_bound, upper_bound, tol)
print(f"找到的極小值近似點 X: {min_x}")
# 預期輸出會接近 2.0

【答案】請參閱上述 Python 程式碼。

(2) 相較於二元搜尋法 (Binary Search), 黃金分割搜尋法的優點：
黃金分割搜尋法適用於尋找單峰函數（即在搜尋區間內只有一個極大值或極小值）的極值，而二元搜尋法（通常用於搜尋有序陣列中的特定值）則不適用於此類最佳化問題。
黃金分割搜尋法的優點在於：

• 適用於尋找函數極值：二元搜尋法用於在有序數據中查找元素，而黃金分割搜尋法則用於在連續區間內尋找單峰函數的最小值。
• 不需要計算導數：黃金分割搜尋法是一種直接搜尋法，僅需評估函數值，而不需要計算函數的導數，這在導數難以計算或不存在的情況下非常有用。
• 收斂性：在每次迭代中，黃金分割搜尋法都能保證以恆定的比例（約 0.618）縮小搜尋區間，確保了收斂性。

若題目意指「搜尋法」的比較，而將 Binary Search 類比為某種尋找函數零點的方法（例如牛頓法需要導數），則 Golden Section Search 相較於一些需要導數的方法，其優勢在於不需導數。

本題主要考驗對 SQL 查詢語言的掌握，特別是聚合函數、JOIN 操作以及分組排序的應用。

核心觀念：SQL (Structured Query Language) 是用於管理關聯式資料庫的標準語言。

(1) 找出每位學生的姓名、院系,以及他們修讀的所有課程的平均分數。
這個查詢需要連接 Students 和 Grades 兩個表格，因為學生的姓名和院系在 Students 表，而課程分數在 Grades 表。我們需要根據 StudentID 將兩個表連接起來，然後按學生分組，計算每個學生的平均分數。

• JOIN: 使用 INNER JOIN (或 JOIN) 連接 Students 和 Grades 表，基於 s.StudentID = g.StudentID。
• GROUP BY: 按學生的 StudentID、Name 和 Department 分組，這樣我們就可以計算每個學生的平均分數。
• AVG(): 使用 AVG(g.Score) 函數計算每個學生的平均分數。
• SELECT: 選擇學生的姓名 (s.Name)、院系 (s.Department) 和計算出的平均分數。

SELECT
    s.Name,
    s.Department,
    AVG(g.Score) AS AverageScore
FROM
    Students AS s
JOIN
    Grades AS g ON s.StudentID = g.StudentID
GROUP BY
    s.StudentID, s.Name, s.Department;

注意: 如果有些學生沒有修讀任何課程 (即在 Grades 表中沒有對應的 StudentID)，使用 INNER JOIN 將不會顯示這些學生。如果需要顯示所有學生，即使他們沒有分數，則應使用 LEFT JOIN，並處理 NULL 值（例如使用 COALESCE(AVG(g.Score), 0)）。但題目要求「他們修讀的所有課程的平均分數」，暗示只考慮有課程的學生，因此 INNER JOIN 是合適的。

【答案】

SELECT
    s.Name,
    s.Department,
    AVG(g.Score) AS AverageScore
FROM
    Students AS s
JOIN
    Grades AS g ON s.StudentID = g.StudentID
GROUP BY
    s.StudentID, s.Name, s.Department;

這題主要考驗對作業系統核心概念「臨界區域」的理解，以及其在並行與並發環境下的應用。

核心觀念：臨界區域 (Critical Section) 是指在多個執行緒或行程共享同一資源時，其中一段程式碼，這段程式碼在同一時間只允許一個執行緒或行程執行，以避免資源競爭導致的資料不一致問題。

臨界區域 (Critical Section) 的定義：
在並發程式設計中，臨界區域是指一個程序或執行緒中，用來存取共享資源（例如變數、檔案、硬體設備等）的一段程式碼。為了確保共享資源的完整性與一致性，作業系統或程式設計師必須確保在任何時刻，最多只能有一個執行緒或行程能夠進入其臨界區域執行。這種互斥（Mutual Exclusion）的機制是防止數據損壞的關鍵。

需要滿足的條件：
一個有效的臨界區域解決方案通常需要滿足以下三個條件：

1. 互斥 (Mutual Exclusion)：如果一個執行緒正在其臨界區域執行，那麼任何其他嘗試進入其臨界區域的執行緒都必須等待。
2. 前進 (Progress)：如果沒有執行緒在其臨界區域執行，並且有執行緒希望進入臨界區域，那麼只有那些不在剩餘區段 (Remainder Section) 執行的執行緒才能參與決定下一個進入臨界區域的執行緒，並且這個選擇不能被無限期地推遲。
3. 有限等待 (Bounded Waiting)：對於一個希望進入其臨界區域的執行緒，必須存在一個對其他執行緒進入其臨界區域的次數的上限，也就是說，這個執行緒進入臨界區域的等待時間不能是無限的。

簡單的實際例子：

假設有兩個銀行帳戶，分別為帳戶 A 和帳戶 B，初始金額均為 1000 元。我們有兩個獨立的執行緒（或行程）：

• 執行緒 1：從帳戶 A 轉帳 100 元到帳戶 B。
• 執行緒 2：從帳戶 B 轉帳 50 元到帳戶 A。

這兩個執行緒操作的程式碼段，涉及讀取、修改和寫入共享資源（帳戶餘額），就構成臨界區域。

臨界區域程式碼示意：

共享資源：
account_A_balance = 1000
account_B_balance = 1000

執行緒 1 (Transfer A to B):

// 臨界區域開始
lock(resource_accounts); // 獲取鎖，確保互斥
read account_A_balance;
account_A_balance = account_A_balance - 100;
write account_A_balance;
read account_B_balance;
account_B_balance = account_B_balance + 100;
write account_B_balance;
unlock(resource_accounts); // 釋放鎖
// 臨界區域結束

執行緒 2 (Transfer B to A):

// 臨界區域開始
lock(resource_accounts); // 獲取鎖，確保互斥
read account_B_balance;
account_B_balance = account_B_balance - 50;
write account_B_balance;
read account_A_balance;
account_A_balance = account_A_balance + 50;
write account_A_balance;
unlock(resource_accounts); // 釋放鎖
// 臨界區域結束

說明：
如果沒有臨界區域的保護，可能會發生以下情況：

1. 執行緒 1 開始執行，讀取 account_A_balance (1000)。
2. 執行緒 2 也開始執行，它讀取 account_B_balance (1000)。
3. 執行緒 1 接著讀取 account_B_balance (1000)，然後更新 account_B_balance 為 1100。