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

這是一題名詞解釋題，要求解釋五個資訊科技相關的術語，並舉出在圖書館的應用。

核心觀念： 熟悉資訊科技的基礎名詞及其在圖書館學與圖書資訊學領域的潛在應用。

(1) 區塊鏈 (Block Chain)

• 定義與技術內涵： 區塊鏈是一種分散式、不可篡改的帳本技術。資料被組織成「區塊」，每個區塊包含交易記錄、前一個區塊的雜湊值 (hash) 以及時間戳記。這些區塊透過密碼學技術串聯起來，形成一個鏈。其分散式的特性意味著資料儲存在多個節點上，沒有單一的中央伺服器，因此難以被竄改或攻擊。主要特性包括去中心化、透明性、不可竄改性和安全性。
• 圖書館應用例子：
  • 數位資源版權管理與授權： 可以記錄數位資源（如電子書、學術論文）的版權資訊、授權條款和使用紀錄，確保創作者權益，並簡化授權流程。
  • 學術出版與論文溯源： 記錄學術論文的提交、審查、發布過程，確保學術誠信，防止學術不端行為。
  • 館藏資料的完整性驗證： 記錄館藏資料的元數據（metadata）或數位副本的雜湊值，用於驗證資料的完整性與未被篡改。

(2) 元宇宙 (Metaverse)

• 定義與技術內涵： 元宇宙是一個持久化、虛擬的、共享的、三維的空間，使用者可以透過虛擬替身 (avatar) 在其中互動、社交、工作、娛樂和交易。它通常結合了虛擬實境 (VR)、擴增實境 (AR)、網際網路、區塊鏈等技術，創造一個與現實世界平行或融合的數位體驗。
• 圖書館應用例子：
  • 虛擬圖書館空間： 建立一個沉浸式的虛擬圖書館環境，使用者可以透過虛擬替身在其中瀏覽、搜尋、借閱資源，甚至參加虛擬講座或讀書會。
  • 數位典藏的沉浸式體驗： 將珍貴的數位典藏（如歷史文物、藝術品）以 3D 模型呈現，讓使用者能在元宇宙中近距離、多角度地欣賞與互動。
  • 遠距學術交流與研究： 提供虛擬會議室或研究空間，方便全球研究者進行協作和學術討論。

(3) 數位策展 (Digital Curation)

• 定義與技術內涵： 數位策展是指對數位物件（包括數位資料、數位內容、數位藝術品等）進行選擇、組織、保存、管理和詮釋的過程，目的是確保其長期可存取性、可用性和價值。它涵蓋了從創建、獲取、儲存、維護到推廣和再利用的整個生命週期。
• 圖書館應用例子：
  • 數位典藏的建置與維護： 圖書館收集、整理、描述和保存數位化的歷史文獻、照片、錄音、錄影等，並確保它們能長期被檢索和利用。

這是一題程式設計題，要求找出 2000 以內的所有完全數，並提供附有註解的程式碼。

核心觀念： 演算法設計、迴圈、條件判斷、函數定義、程式碼註解。

完全數的定義： 一個正整數，如果它等於其所有真因數（不包括自身）的總和，那麼這個數就稱為完全數。例如，28 的真因數有 1, 2, 4, 7, 14，它們的總和是 $1+2+4+7+14 = 28$，所以 28 是完全數。

解題思路：

1. 找出一個數的所有因數： 對於一個給定的數字 n，我們可以從 1 遍歷到 n/2 (或更精確地說，到 sqrt(n))。如果 i 是 n 的因數，那麼 n/i 也是 n 的因數。
2. 計算因數總和： 將找到的所有真因數加總。
3. 判斷是否為完全數： 如果因數總和等於原數字 n，則 n 是完全數。
4. 遍歷範圍： 對於題目要求的 2000 以內的數字，從 1 開始遍歷到 2000，對每個數字執行上述步驟。

程式碼範例 (Python)：

import math

def find_divisors_sum(n):
    # 函數：計算一個正整數 n 的所有真因數（不包括 n 本身）的總和。
    # 參數: n - 要計算的目標正整數
    # 返回值: n 的所有真因數的總和

    if n <= 1:
        # 如果 n 小於等於 1，它沒有真因數，總和為 0。
        return 0

    divisors_sum = 1  # 初始化總和，因為 1 總是任何數的因數（除了 1 本身）。
    # 遍歷從 2 到 sqrt(n) 的所有數字。
    # 我們只需要檢查到 sqrt(n) 因為如果 i 是 n 的因數，那麼 n/i 也是因數。
    # 這樣可以避免重複計算和提高效率。
    for i in range(2, int(math.sqrt(n)) + 1):
        if n % i == 0:
            # 如果 i 是 n 的因數
            divisors_sum += i  # 將 i 加到總和中
            # 如果 i 和 n/i 不相等，則 n/i 也是一個不同的因數，也加到總和中。
            # 例如，對於 n=12，i=2，n/i=6。2 和 6 都是因數。
            # 對於 n=16，i=4，n/i=4。此時 i == n/i，只加一次。
            if i * i != n:
                divisors_sum += n // i

    # 注意：這裡計算的是真因數總和。
    # 如果題目定義完全數為「因子總和等於兩倍該數」，則上面的邏輯需調整。
    # 但根據題目範例 28=1+2+4+7+14，是求「真因數總和」。
    return divisors_sum

def find_perfect_numbers(limit):
    # 函數：找出指定範圍內的「完全數」。
    # 參數: limit - 要搜尋的上限（不包含 limit）
    # 返回值: 一個包含所有完全數的列表

    perfect_numbers = []  # 初始化一個空列表，用於儲存找到的完全數。
    # 遍歷從 1 到 limit-1 的所有數字，檢查它們是否為完全數。
    for num in range(1, limit):
        # 計算當前數字 num 的真因數總和。
        sum_of_divisors = find_divisors_sum(num)
        # 檢查計算出的因數總和是否等於數字本身。
        if sum_of_divisors == num:
            # 如果是，則 num 是一個完全數，將其加入到 perfect_numbers 列表中。
            perfect_numbers.append(num)
            # 打印找到的完全數及其因數總和，方便驗證。
            # print(f"{num} is a perfect number. Sum of divisors: {sum_of_divisors}") # 可選的除錯輸出

    return perfect_numbers # 返回包含所有找到的完全數的列表。

# 設定搜尋上限為 2000。
search_limit = 2000
# 呼叫函數找出 2000 以內的完全數。
result = find_perfect_numbers(search_limit)

# 輸出結果。
print(f"The perfect numbers within {search_limit} are: {result}")

# 預期輸出：
# The perfect numbers within 2000 are: [6, 28, 496]
# （注意：下一個完全數是 8128，超過 2000 了）

程式碼註解說明：

• find_divisors_sum(n) 函數：
  • if n <= 1: return 0: 處理邊界情況，1 或以下的數沒有真因數。
  • divisors_sum = 1: 初始化，因為 1 總是真因數。

這是一題關於搜尋演算法的題目，涵蓋了循序搜尋、二分搜尋和雜湊搜尋的原理、特性、速度比較及時間複雜度分析。

核心觀念： 資料結構中的搜尋演算法，包括其工作原理、效率（時間複雜度）以及適用情境。

(1) 搜尋原理

• 循序搜尋法 (Sequential Search)

  • 原理： 這是最簡單的搜尋方法。它從資料集合的第一個元素開始，逐一檢查每個元素，直到找到目標值為止。如果檢查完所有元素都沒有找到，則表示目標值不存在於資料集合中。
  • 適用情境： 資料未排序或資料量小時適用。

• 二分搜尋法 (Binary Search)

  • 原理： 此方法要求資料集合必須是已排序的（通常是升序或降序）。它從資料集合的中間元素開始比較。
    • 如果中間元素等於目標值，則搜尋成功。
    • 如果中間元素大於目標值（假設為升序），則目標值（如果存在）一定在中間元素的左半部分，搜尋範圍縮小至左半部分。
    • 如果中間元素小於目標值，則目標值（如果存在）一定在中間元素的右半部分，搜尋範圍縮小至右半部分。
    • 重複此過程，直到找到目標值或搜尋範圍縮小到空為止。
  • 適用情境： 資料必須預先排序，且資料量較大時效率很高。

• 雜湊搜尋法 (Hashing Search)

  • 原理： 雜湊搜尋法（也稱為散列表搜尋）是基於雜湊函數 (hash function) 的。雜湊函數將鍵值 (key) 轉換為一個索引值（雜湊值），該索引值直接指向儲存位置。理想情況下，雜湊函數能將不同的鍵值映射到不同的位置，從而實現常數時間的查找。然而，實際應用中可能會發生「碰撞」(collision)，即不同的鍵值被映射到同一個位置。碰撞處理是雜湊搜尋的關鍵，常見的方法有：
    • 鏈地址法 (Chaining)： 在每個儲存位置維護一個鏈結串列，將所有映射到該位置的鍵值儲存在鏈結串列中。
    • 開放定址法 (Open Addressing)： 當發生碰撞時，在雜湊表中尋找下一個可用的位置（例如，線性探測、二次探測、雙重雜湊）。
  • 適用情境： 資料的插入、刪除和搜尋操作都需要快速進行，且不需要保持資料的順序。

(2) 特性與速度優劣排序

• 循序搜尋法：

  • 特性： 簡單易實現，不要求資料排序，但效率最低。
  • 速度： 最慢。

• 二分搜尋法：

  • 特性： 要求資料排序，搜尋速度快，但插入和刪除操作可能較慢（需要維持排序）。
  • 速度： 比循序搜尋快得多。

• 雜湊搜尋法：

  • 特性： 插入、刪除、搜尋操作平均速度極快（接近常數時間），不要求資料排序，但需要額外的空間來處理碰撞，且如果雜湊函數設計不佳或資料分布不均，效能會顯著下降，甚至退化。
  • 速度： 平均情況下最快。

• 搜尋速度優劣排序 (由快至慢)：

  1. 雜湊搜尋法 (平均情況)
  2. 二分搜尋法
  3. 循序搜尋法

(3) 最差情況下的時間複雜度 (Big-O)

• 循序搜尋法 (Sequential Search)：

  • 在最差情況下（目標值在最後一個或不存在），需要檢查所有 $n$ 個元素。
  • 最差時間複雜度：$O(n)$

• 二分搜尋法 (Binary Search)：

  • 在最差情況下（目標值在最後一次分割時找到，或不存在），搜尋範圍每次減半。假設有 $n$ 個元素，需要進行 $\log_2 n$ 次分割。
  • 最差時間複雜度：$O(\log n)$

這是一題關於資料庫系統設計的題目，涵蓋了從需求分析到運行維護的五個主要階段，要求說明各階段的關鍵工作和應用。

核心觀念： 資料庫系統生命週期中的五個關鍵階段及其具體內容。

(1) 需求分析階段的調查工作

需求分析是資料庫系統設計的第一步，目標是了解使用者和組織對資料庫的需求。此階段的調查工作主要包括：

• 訪談使用者： 與各級使用者（包括終端使用者、管理者、開發人員）進行訪談，了解他們目前的工作流程、所需資訊、報表、查詢功能以及對新系統的期望。
• 文件分析： 審閱現有的文件、報表、表單、業務流程說明等，以了解現有系統的資料結構、資料內容和業務規則。
• 現場觀察： 觀察使用者如何執行日常工作，了解實際操作中的問題和潛在需求。
• 問卷調查： 對大量使用者發放問卷，收集系統需求、功能偏好等資訊。
• 原型設計 (Prototyping)： 建立一個簡單的原型系統，讓使用者試用並提供回饋，以幫助釐清和細化需求。
• 識別關鍵資料： 確定系統需要管理的核心資料項目，例如，學生資料庫需要學生姓名、學號、系所、成績等。
• 識別業務規則： 記錄與資料相關的各種業務規則和約束條件，例如，「學生的學期成績不能低於 0 分」，「每門課最多只能有 3 個學分」。

(2) 概念結構設計階段的 E-R 圖模型應用舉例

概念結構設計階段的主要目標是建立一個獨立於特定資料庫管理系統 (DBMS) 的、高層次的資料模型，E-R (Entity-Relationship) 圖模型是常用的工具。

舉例：設計一個簡單的「學校」系統概念模型。

• 實體 (Entity)： 代表系統中的物件，通常是名詞。

  • 學生 (Student)
  • 課程 (Course)
  • 教師 (Teacher)

• 屬性 (Attribute)： 描述實體的特性。

  • 學生 實體可能有的屬性：學號 (StudentID) (主鍵), 姓名 (Name), 系所 (Department), 出生日期 (DOB)。
  • 課程 實體可能有的屬性：課程編號 (CourseID) (主鍵), 課程名稱 (CourseName), 學分數 (Credits)。
  • 教師 實體可能有的屬性：教師編號 (TeacherID) (主鍵), 姓名 (Name), 職稱 (Title), 系所 (Department)。

• 關係 (Relationship)： 描述實體之間的關聯。

  • 學生 與 課程 之間：一個學生可以選修多門課程，一門課程可以被多個學生選修。這是一個 多對多 (Many-to-Many) 關係，可以命名為 選修 (Enroll)。
  • 教師 與 課程 之間：一個教師可以教授多門課程，一門課程可以由一個教師教授（假設簡化為一對一或一對多）。這裡我們假設一個教師可以教授多門課程，但一門課程由一位教師教授（一對多 Many-to-One 關係，從課程到教師），可以命名為 教授 (Teaches)。

• E-R 圖表示：

  +-----------+       選修 (Enroll)       +---------+
  |  學生     |-----------------------|  課程   |
  |-----------|      M:N              |---------|
  | StudentID |                       | CourseID|
  | Name      |                       | Name    |
  | Department|                       | Credits |
  | DOB       |                       +---------+
  +-----------+                           ^
                                          | 教授 (Teaches)
                                          | 1:N
                                        +---------+
                                        |  教師   |
                                        |---------|
                                        | TeacherID|
                                        | Name    |
                                        | Title   |
                                        | Department|
                                        +---------+
  

  （注意：E-R 圖通常用圖形符號表示，這裡用文字示意。M:N 表示多對多，1:N 表示一對多。）

(3) 邏輯結構設計階段：E-R 圖模型轉換為關聯式資料庫表格

邏輯結構設計階段將 E-R 圖轉換為特定資料模型（如關聯模型）的結構。對於關聯模型，我們將實體轉換為表格 (Table)，屬性轉換為欄位 (Column)，關係根據其基數 (Cardinality) 進行處理。

根據上述 E-R 圖例子轉換：

1. 實體轉換為表格：

   • 學生 (Student) 表格：
     • StudentID (Primary Key, PK)
     • Name
     • Department
     • DOB
   • 課程 (Course) 表格：
     • CourseID (PK)
     • CourseName
     • Credits
   • 教師 (Teacher) 表格：
     • TeacherID (PK)
     • Name
     • Title
     • Department

2. 關係處理：

   • 多對多 (M:N) 關係 (選修)： 需要建立一個新的「關聯表」(Association Table) 或「連接表」(Junction Table)。該表包含參與關係的兩個實體的「主鍵」作為其「複合主鍵」(Composite Primary Key)，並可能包含描述關係的屬性。
     • 選修 (Enrollment) 表格：
       • StudentID (Foreign Key, FK, part of PK)
       • CourseID (FK, part of PK)