114 年 國立政治大學資訊管理學系碩士班科技組《計算機概論》

這兩題主要在探討線性模型在分類問題上的應用。

1.1. 線性迴歸 (Linear Regression) 與邏輯式迴歸 (Logistic Regression) 的比較：

• 線性迴歸 (Linear Regression)：

  • 目的：用於預測連續型的目標變數。它試圖找到一條直線（或高維空間中的超平面）來最佳地擬合數據點，使得實際值與預測值之間的誤差最小化。
  • 輸出：預測值是連續的，可以取任何實數值。
  • 模型：通常表示為 $y = \beta_0 + \beta_1 x_1 + \beta_2 x_2 + ... + \beta_n x_n + \epsilon$，其中 $y$ 是目標變數，$x_i$ 是特徵變數，$\beta_i$ 是迴歸係數，$\epsilon$ 是誤差項。
  • 損失函數：常用最小平方誤差 (Mean Squared Error, MSE)。

• 邏輯式迴歸 (Logistic Regression)：

  • 目的：用於解決二元分類問題。它不是直接預測類別，而是預測某個樣本屬於某一類別的機率。
  • 輸出：預測值是機率，介於 0 和 1 之間。這個機率值之後會透過一個閾值（通常是 0.5）來決定最終的類別。
  • 模型：它在線性模型的基礎上，使用一個激活函數（通常是 Sigmoid 函數 $\sigma(z) = \frac{1}{1+e^{-z}}$）將線性組合的輸出映射到 (0, 1) 的範圍。模型的輸出是 $P(y=1|x) = \sigma(\beta_0 + \beta_1 x_1 + ... + \beta_n x_n)$。
  • 損失函數：常用交叉熵損失 (Cross-Entropy Loss) 或對數損失 (Log Loss)。

• 主要差異：

  1. 問題類型：線性迴歸用於迴歸（預測連續值），邏輯式迴歸用於分類（預測類別機率）。
  2. 輸出範圍：線性迴歸輸出是任意實數，邏輯式迴歸輸出是 (0, 1) 間的機率。
  3. 模型結構：邏輯式迴歸在線性模型的基礎上，引入了 Sigmoid 函數來壓縮輸出到機率範圍。
  4. 損失函數：線性迴歸使用 MSE，邏輯式迴歸使用交叉熵。

這組題目主要在探討軟體開發中常用的版本控制工具 Git 和協作平台 GitHub 的工作流程。

2.1. Git Workflow 與 GitHub Workflow 的定義與差異：

• Git Workflow：

  • 定義：Git Workflow 指的是一套在專案中使用 Git 進行版本控制的規則、模式和實踐。它定義了如何創建分支、如何合併分支、如何管理提交歷史以及團隊成員如何協作。
  • 目的：確保程式碼的穩定性、可追溯性，並協調多個開發者同時工作。
  • 範例：Git Flow (包含 main, develop, feature, release, hotfix 等分支)，GitHub Flow (以 main 和 feature branches 為主)，GitLab Flow (結合了 Git Flow 和 GitHub Flow 的優點)。
  • 核心：側重於 Git 本身的版本控制操作和分支策略。

• GitHub Workflow：

  • 定義：GitHub Workflow 更具體地指在 GitHub 平台上，結合 Git 的版本控制能力以及 GitHub 提供的協作功能（如 Pull Requests, Issues, Actions 等）來完成軟體開發的流程。它通常比單純的 Git Workflow 更強調協作和代碼審查。
  • 目的：促進團隊成員之間的溝通、協作、代碼審查（Code Review）和自動化測試/部署。
  • 核心特點：
    • Pull Request (PR)：是 GitHub Workflow 的核心。開發者在自己的分支上完成功能後，提交 PR 以請求將變更合併到目標分支。PR 提供了代碼審查、討論和自動化檢查的平台。
    • Forking：對於開源專案或需要獨立開發的場景，開發者通常會先 Fork 專案到自己的 GitHub 帳號下，然後在其 Fork 的版本上開發。
    • Issues：用於追蹤 Bug、功能需求和討論。
    • Actions：用於自動化 CI/CD 流程、測試、部署等。
  • 範例：最常見的是基於 GitHub Flow 的工作流程：開發者 Fork 專案 -> 在本地創建新分支 -> 編寫程式碼 -> 提交變更 -> 推送至自己的 Fork 倉庫 -> 創建 Pull Request -> 團隊審查 -> 合併 PR -> (可選) 自動化部署。

• 主要差異：

  1. 範疇：Git Workflow 是一個更廣泛的概念，涵蓋了所有使用 Git 的策略；GitHub Workflow 則是在 GitHub 平台上的具體實踐，它整合了 Git 和 GitHub 的特有功能。
  2. 協作機制：GitHub Workflow 強調使用 Pull Request 進行代碼審查和協作，這是其區別於純 Git Workflow 的一個關鍵點。Git Flow 雖然也有合併的概念，但 PR 是 GitHub 的特色。
  3. 平台依賴：GitHub Workflow 顯然依賴於 GitHub 平台及其提供的功能。而 Git Workflow 則不依賴於特定平台，可以在任何 Git 環境下實施。
  4. 自動化整合：GitHub Workflow 通常與 GitHub Actions 等 CI/CD 工具緊密結合，實現自動化流程。

【答案】
Git Workflow 是一套通用的 Git 版本控制策略，例如 Git Flow，強調分支管理和合併。GitHub Workflow 則是在 GitHub 平台上，結合 Git 功能與 PR、Issues、Actions 等協作工具的開發流程，更側重代碼審查與自動化。主要差異在於 GitHub Workflow 依賴 GitHub 平台、強調 PR 協作機制，並整合自動化工具。

2.2. 識別與解決 Git 合併衝突 (Merge Conflicts) 的步驟：

當兩個或多個分支修改了同一份文件的同一部分時，Git 在嘗試自動合併時無法決定保留哪個版本，就會產生合併衝突。

• 步驟：

  1. 觸發衝突：當你嘗試將一個分支（例如 feature 分支）合併到另一個分支（例如 main 分支）時，如果 Git 無法自動合併，它會停止合併過程並提示你存在衝突。

     git merge <source_branch>
     # Output will show something like:
     # Auto-merging <file_name>
     # CONFLICT (content): Merge conflict in <file_name>
     # Automatic merge failed; fix conflicts and then commit the result.
     

  2. 識別衝突文件：使用 git status 命令可以查看哪些文件存在衝突。

     git status
     

     這些文件會被列在 "Unmerged paths" 部分。

  3. 手動編輯衝突文件：打開有衝突的文件。Git 會在衝突區域插入特殊的標記來指示衝突的來源：

     • <<<<<<< HEAD: 表示當前分支（目標分支，例如 main）的修改內容。
     • =======: 分隔符。
     • >>>>>>> <source_branch>: 表示從源分支（例如 feature）引入的修改內容。

     你需要手動編輯這些文件，刪除 Git 插入的標記，並決定最終保留哪些程式碼。你可以選擇：

     • 保留當前分支的內容。
     • 保留源分支的內容。
     • 結合兩者的內容。
     • 編寫全新的內容。

     範例衝突標記：

     // Original code
     int x = 10;
     <<<<<<< HEAD
     // Content from main branch
     x = 20;
     =======
     // Content from feature branch
     x = 30;
     >>>>>>> feature
     // Rest of the code
     

     編輯後，你可能決定保留 x = 30;，則文件應修改為：

     // Original code
     int x = 10;
     // Content from feature branch
     x = 30;
     // Rest of the code
     

  4. 標記衝突已解決：在你編輯並保存了所有衝突文件後，你需要告訴 Git 這些衝突已經解決。使用 git add 命令將修改後的文件添加到暫存區。

     git add <file_name_with_resolved_conflict>
     # Repeat for all resolved files
     

這組題目主要探討網路傳輸中的 IP (Internet Protocol) 位址和相關概念。

3.1. 決定封包目的地的網路設備：

在封包傳輸過程中，路由器 (Router) 是典型會檢查 IP 位址以決定封包轉送路徑的網路設備。路由器位於不同的網路之間，它會根據封包的目標 IP 位址，查詢自己的路由表，找出最佳的下一跳 (next hop) 位址，然後將封包轉送出去。交換機 (Switch) 主要在同一網路內部工作，通常是根據 MAC 位址進行轉送。

【答案】
路由器 (Router)。

3.2. 對應的 OSI 模型層級：

路由器工作的層級是 OSI 模型中的 網路層 (Network Layer)，也就是 第三層 (Layer 3)。在這個層級，設備處理的是邏輯位址，如 IP 位址，並負責實現尋址、路由和路徑選擇。

【答案】
網路層 (Network Layer) / 第三層 (Layer 3)。

3.3. TTL (Time to Live) 欄位的功能：

TTL 欄位是 IP 標頭中的一個 8 位元欄位，其主要功能是防止封包在網路中無限循環。

• 工作原理：當封包從源主機發出時，TTL 值被設定為一個初始值（通常是 64、128 或 255，具體值取決於作業系統）。
• 遞減過程：封包每經過一個路由器，TTL 值就會被減 1。
• 封包丟棄：如果 TTL 值在到達路由器時變為 0，則該路由器會丟棄這個封包，並通常會向源主機發送一個 ICMP "Time Exceeded" 訊息。
• 目的：這個機制確保了即使路由表配置錯誤或網路出現環路，封包最終也會被丟棄，而不是在網路上無限傳播，消耗網路資源。

【答案】
TTL 欄位用於限制封包在網路中存在的最大「跳數」(hops)，防止封包因網路故障（如路由環路）而無限循環。每經過一個路由器，TTL 值減 1，當 TTL 歸零時，封包即被丟棄。

3.4. 封包是否總是具有 IP 標頭：

不一定。封包是否具有 IP 標頭取決於它在網路中的哪個層級傳輸。

• 具有 IP 標頭的封包：在網際網路層（OSI 第三層）及以上傳輸的封包，通常會有 IP 標頭。例如，TCP 或 UDP 封包在傳輸時，其資料部分會被封裝在 IP 封包中，所以整個 IP 封包會有 IP 標頭。
• 不具有 IP 標頭的封包：
  • 區域網路 (LAN) 內部，設備之間通常使用 MAC 位址進行通信。例如，乙太網路 (Ethernet) 幀在區域網路內部傳輸時，主要包含乙太網路標頭（包含 MAC 位址），而不直接包含 IP 標頭。IP 封包是乙太網路幀的「載荷」(payload)。
  • 在更低層級，如資料鏈路層或實體層，封包（或稱幀、訊框）的結構與 IP 協議無關。

總結：IP 標頭是在 IP 層級（網路層）上添加的，用於實現跨網路的路由功能。在僅限於單一區域網路內部或更低層級的通信時，封包可能不需要 IP 標頭。

【答案】
不一定。只有在網際網路層 (OSI Layer 3) 及以上傳輸的封包才需要 IP 標頭。例如，乙太網路幀在區域網路內部傳輸時，主要依賴 MAC 位址，其載荷才可能是 IP 封包。

3.5. 判斷 A 和 B 是否屬於同一子網路：

要判斷兩個 IP 位址是否屬於同一子網路，需要知道它們的 IP 位址 和 子網路遮罩 (Subnet Mask)。

• 判斷方法：

  1. 將 IP 位址 A 和 IP 位址 B 分別與其對應的子網路遮罩進行 位元 AND (bitwise AND) 運算。
  2. 如果運算結果相同，則表示這兩個 IP 位址屬於同一子網路。
  3. 如果運算結果不同，則表示它們屬於不同的子網路。

• 原理：

  • 子網路遮罩用來區分 IP 位址中的「網路位址」部分和「主機位址」部分。
  • 網路位址部分決定了 IP 位址所屬的網路或子網路。
  • 對 IP 位址與子網路遮罩進行 AND 運算，實際上是提取 IP 位址的網路位址部分。

這個題目要求說明 Dijkstra 演算法的原理，並解釋其為何不能處理帶有負權重的邊。

Dijkstra 演算法是一種用於尋找圖中單源最短路徑的貪心演算法。它適用於權重為非負的圖。

• Dijkstra 演算法的工作原理：

  演算法的核心思想是從源節點開始，逐步擴展已知最短路徑的節點集合，直到找到到達所有節點的最短路徑。它維護兩個集合：

  1. 已確定最短路徑的節點集合 (S)：初始時只包含源節點。
  2. 未確定最短路徑的節點集合 (Q)：初始時包含所有節點。

  演算法步驟如下：

  1. 初始化：

     • 為源節點 s 設定距離 dist[s] = 0，其他所有節點 v 設定距離 dist[v] = infinity。
     • 將所有節點放入一個優先佇列 (priority queue) Q 中，優先級由節點的距離 dist 值決定（距離越小，優先級越高）。
     • 建立一個記錄前驅節點的結構，例如 prev[v]，用於重建路徑。

  2. 迭代處理：當優先佇列 Q 不為空時，重複以下步驟：

     • 提取節點：從 Q 中提取具有最小距離值的節點 u（即 u = argmin_{v in Q} dist[v]）。將 u 從 Q 中移除，並加入到已確定最短路徑的集合 S 中。
     • 放鬆邊 (Relaxation)：對於節點 u 的每一個鄰居節點 v：
       • 計算從源節點經由 u 到達 v 的潛在距離：alt = dist[u] + weight(u, v)。
       • 如果 alt < dist[v]，則表示發現了一條更短的路徑到達 v。
       • 更新 dist[v] = alt，並設定 prev[v] = u。
       • 在優先佇列 Q 中更新節點 v 的優先級。

  3. 終止：當優先佇列 Q 為空時，演算法結束。此時 dist[v] 記錄了從源節點 s 到節點 v 的最短路徑長度，prev 陣列可以用來重建路徑。

• 為何不能處理負權重邊：

  Dijkstra 演算法之所以不能處理負權重邊，是因為它採用了貪心策略，即一旦一個節點被標記為「已確定最短路徑」，就認為到達該節點的最短路徑已經找到，並且不會再改變。這個假設在圖中存在負權重邊時會被打破。

  原因分析：

  1. 錯誤的「已確定」假設：當演算法提取一個節點 u 並將其加入集合 S 時，它假設 dist[u] 是從源節點到 u 的最短距離。然而，如果存在一條從源節點出發，經過一個負權重邊，然後繞過一些節點，最終到達 u 的路徑，這條路徑的總權重可能比 dist[u] 更小。但是，由於 u 已經被處理過，演算法不會再考慮更新 dist[u]。

這題要求解釋雜湊 (Hashing)、編碼 (Encoding) 和加密 (Encryption) 這三個概念，並比較它們的差異及其在數據處理和安全上的貢獻。

這三者都是數據轉換技術，但目的和應用場景截然不同。

• 雜湊 (Hashing)：

  • 意義：將任意大小的輸入數據（訊息）通過一個數學函數（雜湊函數，Hash Function）轉換成一個固定大小的輸出（雜湊值、雜湊碼、訊息摘要、Digest）。
  • 目的：
    1. 數據完整性驗證 (Data Integrity)：通過比較原始數據的雜湊值與接收到的雜湊值，判斷數據在傳輸或儲存過程中是否被篡改。如果雜湊值相同，則數據很可能沒有被改變。
    2. 快速查找 (Fast Lookup)：在雜湊表中，雜湊值用作索引，可以快速定位數據，例如密碼儲存（儲存雜湊值而非明文密碼）。
    3. 數字簽章 (Digital Signatures)：用來創建訊息摘要，然後對摘要進行加密，以驗證訊息的來源和完整性。
  • 特性：
    • 單向性 (One-way)：雜湊函數是不可逆的，即從雜湊值無法推算出原始輸入數據。
    • 確定性 (Deterministic)：相同的輸入總是產生相同的輸出。
    • 抗碰撞性 (Collision Resistance)：很難找到兩個不同的輸入產生相同的雜湊值（理想情況下）。
    • 雪崩效應 (Avalanche Effect)：輸入數據的微小改變會導致輸出的雜湊值發生巨大變化。
  • 例子：MD5, SHA-1, SHA-256。

• 編碼 (Encoding)：

  • 意義：將數據從一種格式轉換成另一種格式，以方便傳輸、儲存或處理。編碼是可逆的，並且通常不以安全為目的。
  • 目的：
    1. 數據表示：將數據轉換成適合特定介質或協議的格式。例如，將二進位數據轉換為 ASCII 字元，或將文字轉換為 URL 編碼。
    2. 壓縮 (Compression)：雖然不是所有編碼都壓縮數據，但某些編碼方式（如 Base64）可以使數據在特定環境下更方便地傳輸，或者將二進位數據表示為文本。
    3. 相容性：確保數據能在不同的系統或應用程式之間正確交換。
  • 特性：
    • 可逆性 (Reversible)：編碼過程可以通過解碼 (Decoding) 輕鬆恢復原始數據。
    • 非安全性：不提供安全保護，任何人知道編碼規則都可以解碼。
  • 例子：Base64 編碼（將二進位數據轉換為 ASCII 字串）、URL 編碼（將特殊字元轉換為 %xx 格式）、ASCII 編碼、UTF-8 編碼。

• 加密 (Encryption)：

  • 意義：使用一個算法（加密算法，Cipher）和一個密鑰 (Key)，將可讀的明文 (Plaintext) 轉換成不可讀的密文 (Ciphertext)。
  • 目的：
    1. 機密性 (Confidentiality)：保護數據不被未授權的第三方閱讀。只有擁有正確密鑰的人才能解密。
    2. 數據安全：確保敏感數據在儲存或傳輸過程中的隱私性。
  • 特性：
    • 可逆性 (Reversible)：通過解密 (Decryption) 和正確的密鑰，可以將密文恢復為明文。
    • 基於密鑰：加密和解密過程依賴於一個或多個密鑰。
    • 安全性：設計用於抵禦攻擊者，即使攻擊者知道加密算法，也難以破解密文。

這個問題要求分析一個遞迴函數 f(a, b, n) 的功能，其中 a, b, n 都是非負整數。

讓我們逐步分析函數的行為：

• 基本情況 (Base Case)：

  • if (n == 0) return a;
  • 當 n 遞減到 0 時，函數停止遞迴，並返回當前的 a 值。

• 遞迴步驟 (Recursive Steps)：

  1. 當 n 是偶數時：

     • if (n % 2 == 0) return f(a, b*b, n/2);
     • a 保持不變。
     • b 的值變為 b*b (即 $b^2$)。
     • n 的值變為 n/2。
     • 這一步相當於對 b 進行了平方操作，並將 n 除以 2。

  2. 當 n 是奇數時：

     • else return f(a*b, b, n-1);
     • a 的值變為 a*b。
     • b 保持不變。
     • n 的值變為 n-1。
     • 這一步相當於將當前的 b 乘到 a 上，並將 n 減 1。

• 分析遞迴過程：

  這個函數的結構看起來像是計算指數運算（例如 $a \times b^n$）的快速演算法，稱為「指數運算之平方求冪法」(Exponentiation by Squaring)。讓我們嘗試追蹤幾個例子：

  範例 1：計算 $a \times b^3$
  f(a, b, 3) (n=3, 奇數)
  -> f(a*b, b, 2) (n=2, 偶數)
  -> f(a*b, (b*b), 2/2) => f(a*b, b^2, 1) (n=1, 奇數)
  -> f((a*b) * (b^2), b^2, 1-1) => f(a*b^3, b^2, 0) (n=0, 基本情況)
  -> 返回 a*b^3

  範例 2：計算 $a \times b^4$
  f(a, b, 4) (n=4, 偶數)
  -> f(a, b*b, 4/2) => f(a, b^2, 2) (n=2, 偶數)
  -> f(a, (b^2)*(b^2), 2/2) => f(a, b^4, 1) (n=1, 奇數)
  -> f(a * b^4, b^4, 1-1) => f(a*b^4, b^4, 0) (n=0, 基本情況)
  -> 返回 a*b^4