北大 114 年資管所 計算機概論 參考答案

核心概念：以雜湊函數把鍵值直接換算成儲存位置，不必逐一比較，平均 $O(1)$ 時間就能找到資料。

運作原理：

1. 插入時計算 $h(key)$，例如 $h(key)=keymodm$，把資料放進雜湊表第 $h(key)$ 個位置。
2. 搜尋時以同一個函數算出位置，直接到該位置取資料。
3. 不同鍵值算出同一位置稱為碰撞，以鏈結法（Chaining，同一位置用串列存多筆）或開放定址法（Open Addressing，如線性探測，往下找空位）處理。

核心概念：不可否認性是讓傳送者事後無法否認自己送過某份訊息。做法是數位簽章：以密碼學雜湊函數產生訊息的摘要，再以傳送者的私鑰對摘要簽章；在私鑰未外洩的前提下，只有持有私鑰的人簽得出來，所以無法否認。

運作原理：

1. 傳送者計算訊息的雜湊值 $H(M)$（如 SHA-256）。
2. 以自己的私鑰對 $H(M)$ 簽章，連同訊息一起送出。
3. 接收者自行計算收到訊息的雜湊值，再以傳送者的公鑰驗證簽章是否與這個雜湊值相符。
4. 驗證通過，表示訊息未被竄改且確實由該私鑰持有者簽署。

核心概念：每個區塊記錄前一個區塊的雜湊值，把區塊串成鏈；任何一筆資料被修改，該區塊的雜湊值就會改變，與下一個區塊記錄的值對不上，竄改容易被發現。

運作原理：

1. 鏈結：區塊標頭包含前一區塊的雜湊值，修改舊區塊必須重算它之後所有的區塊。
2. 交易摘要：區塊內的交易以兩兩雜湊的方式建成 Merkle Tree，根雜湊值（Merkle Root）放在區塊標頭，任一筆交易被改都會改變 Merkle Root。
3. 工作量證明（Proof of Work）：礦工不斷調整 nonce 重算區塊標頭的雜湊值，直到小於目標值才算挖到區塊；找到答案要大量運算，驗證只需算一次。

(1) 演算法（乘法公式逐步計算）：

Algorithm Combination(n, k)
    if k < 0 or k > n then return 0
    if k > n - k then k ← n - k      // C(n,k) = C(n,n-k)，取較小者
    result ← 1
    for i ← 1 to k do
        result ← result × (n - k + i) / i   // 每一步都是整數
    return result

(2) 優劣：

1. 優點：時間 $O(min(k,n-k))$、空間 $O(1)$；不計算完整階乘，避免 $n!$ 溢位（64 位元整數在 $21!$ 即溢位）。
2. 缺點：必須先乘再除才能保持整數；除法前的中間值可達答案的 $k$ 倍，答案接近整數上限時仍可能溢位。

(1) 定義：用戶端是發出請求、使用服務的一方（瀏覽器、App、命令列工具）；資源是伺服器上以統一資源識別碼（URI）識別、可被操作的資料或服務。

(2) 以 AWS S3 為例：用戶端不直接接觸儲存設備，所有操作經 API 提出，由 API 驗證、轉送與回傳。

1. 用戶端以 Signature Version 4（SigV4）簽章送出 HTTP 請求，如以 PUT 上傳 photo.jpg。
2. API 驗證簽章與權限（身分與存取管理 IAM 政策、儲存貯體政策）。
3. S3 建立或修改 photo.jpg 這個物件。
4. API 回傳狀態碼；之後以 GET 取得、DELETE 刪除同一資源。

(1) Stateless：伺服器不保存對話狀態，每個請求自帶所需資訊（如 token）；任何伺服器都能處理，易於水平擴充，代價是重複傳送資訊。

(2) Uniform Interface：以 URI 識別資源、以 HTTP 方法表達動作、以表現形式傳遞狀態、訊息自我描述、以 HATEOAS（Hypermedia as the Engine of Application State）提供下一步連結；用戶端與伺服器可各自演進。

Code on Demand。

(1) Nouns（URI）：以名詞表示資源，如 /products/1001、/orders、/orders/5678。

(2) Verb（HTTP method）：GET /products/1001 瀏覽商品、POST /orders 下單、GET /orders/5678 查詢、PATCH /orders/5678 修改、DELETE /orders/5678 取消。

(3) Content-Types：下單請求標頭 Content-Type: application/json，內容為 JSON（JavaScript Object Notation）格式的訂單資料；用戶端以 Accept: application/json 指定回應格式，伺服器回應也以 JSON 表示訂單。

1. {}：物件（object），由一組無順序的「名稱：值」配對組成，配對之間以逗號分隔。例如 {"subject":"Math","score":80} 表示一筆科目成績。
2. []：陣列（array），由有順序的值組成，值之間以逗號分隔。例如最外層的 [...] 是兩位學生的清單，"report":[...] 是一位學生的各科成績清單。
3. :：分隔名稱與值，左邊是以雙引號括起的名稱（屬性），右邊是值。例如 "score":80 表示屬性 score 的值為 80。