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

資料正規化（Data Normalization）與反正規化（Data Denormalization）是資料庫設計中的重要概念，主要用於優化資料儲存結構、減少資料冗餘、確保資料一致性，以及提升查詢效能。

資料正規化 (Data Normalization)

• 定義：資料正規化是一系列將資料庫結構化的過程，旨在減少資料冗餘和不一致性。它透過將大型表格分割成較小的、相關聯的表格，並定義表格之間的關係來實現。正規化通常分為多個範式（Normal Forms），如第一範式 (1NF)、第二範式 (2NF)、第三範式 (3NF) 等，層層遞進地消除資料的異常（Anomalies），例如插入異常 (Insertion Anomaly)、更新異常 (Update Anomaly) 和刪除異常 (Deletion Anomaly)。
• 目的：
  • 減少資料冗餘：避免重複儲存相同的資料。
  • 確保資料一致性：當資料冗餘減少，更新時只需修改一個地方，降低了產生不一致資料的風險。
  • 簡化資料庫維護：結構更清晰，易於理解和修改。
  • 避免資料異常：防止因資料重複儲存而引起的插入、更新、刪除問題。

星狀結構 (Star Schema) 和雪花結構 (Snowflake Schema) 是資料倉儲（Data Warehousing）中常用的兩種維度模型（Dimensional Model）設計模式，用於組織和儲存資料以支援商業智慧 (BI) 和報表分析。它們都圍繞著一個中心的事實表 (Fact Table) 展開，但維度表 (Dimension Table) 的組織方式有所不同。

星狀結構 (Star Schema)

• 定義：星狀結構是最簡單、最常見的維度模型。它包含一個中心的事實表，該事實表直接連接到多個維度表。每個維度表都包含描述該維度的屬性，且維度表通常是「扁平化」的，即它們不進一步正規化。從中心的事實表延伸出去，就像星星的「光芒」一樣，故名星狀結構。
• 特點：
  • 結構簡單，易於理解和實施。
  • 維度表通常是單一層的（非正規化）。
  • 查詢效能較高，因為 JOIN 操作較少（通常只需要連接事實表與各個維度表）。
  • 資料冗餘可能較多，因為維度屬性未進一步分解。

雪花結構 (Snowflake Schema)

• 定義：雪花結構是在星狀結構的基礎上，進一步將維度表正規化。這意味著，原本在星狀結構中較大的、包含多個屬性的維度表，在雪花結構中會被分解成多個更小的、相關聯的表格。這些分解後的表格形成了一個層次結構，從中心的事實表開始，一層一層地連接到更細粒度的維度表，如同雪花的「枝枒」一般。
• 特點：
  • 維度表進一步正規化，減少了資料冗餘。
  • 資料儲存空間效率較高。
  • 查詢時可能需要更多的 JOIN 操作，因為需要連接多個維度表，這可能導致查詢效能略低於星狀結構。
  • 結構相對複雜，理解和維護的難度較高。

關鍵差異 (Key Differences)

| 特徵 | 星狀結構 (Star Schema) | 雪花結構 (Snowflake Schema) |

抽象資料型別（Abstract Data Type, ADT）和資料結構（Data Structure）是電腦科學中處理資料的兩個核心概念，它們之間有著緊密的關係，但關注點不同。

抽象資料型別 (Abstract Data Type, ADT)

• 定義：抽象資料型別是一種數學模型，它定義了一組資料值和一組操作（方法）。ADT 的重點在於「什麼」（What），也就是它能做什麼，而不關心「如何」（How）去實現這些操作。它提供了一個抽象的介面，使用者只需要知道有哪些操作以及它們的功能，而不需要了解其底層的具體實現細節。
• 特點：
  • 抽象性：隱藏了實現細節，只暴露了介面。
  • 行為定義：定義了資料的邏輯行為（操作）。
  • 獨立於實現：使用者不需關心底層如何運作。
• 範例：
  • 堆疊 (Stack)：提供 push (壓入元素)、pop (彈出元素)、peek (查看頂端元素)、isEmpty (是否為空) 等操作。
  • 佇列 (Queue)：提供 enqueue (加入元素)、dequeue (移除元素)、front (查看隊頭元素)、isEmpty (是否為空) 等操作。
  • 列表 (List)：提供 add (加入元素)、remove (移除元素)、get (取得元素)、size (取得大小) 等操作。

資料結構 (Data Structure)

• 定義：資料結構是資料在電腦記憶體中組織、管理和儲存的一種方式，以便能被有效地存取和修改。它關注的是「如何」實現抽象資料型別所定義的操作，以及如何組織資料以達到特定的效率目標（時間和空間）。
• 特點：

繼承 (Inheritance) 是物件導向程式設計 (Object-Oriented Programming, OOP) 的一個核心概念，它允許一個類別（稱為子類別或衍生類別）繼承另一個類別（稱為父類別或基底類別）的屬性和方法。

定義

當一個類別 A 繼承自類別 B 時，類別 A 就擁有類別 B 的所有非私有（public 和 protected）成員（屬性/欄位和方法/函數）。類別 A 也可以新增自己特有的屬性和方法，或者覆寫（override）從父類別繼承來的某些方法，以提供更特定的行為。

• 父類別 (Superclass / Base Class)：被繼承的類別。
• 子類別 (Subclass / Derived Class)：繼承父類別的類別。

目的

繼承的主要目的是為了實現程式碼的重用 (Code Reusability) 和建立類別之間的「is-a」關係（「是一個」關係）。

1. 程式碼重用 (Code Reusability)：
   • 父類別中定義的通用屬性和行為，可以被多個子類別直接使用，而無需重複編寫。這大大減少了開發時間和維護成本。
   • 例如，如果我們有一個 Vehicle (車輛) 父類別，它可能包含 speed 屬性和 accelerate() 方法。

多型性 (Polymorphism) 是物件導向程式設計 (Object-Oriented Programming, OOP) 的三大基本特性之一（另外兩個是封裝 Encapsulation 和繼承 Inheritance）。Polymorphism 的字面意思是「多種形態」，在 OOP 中，它指的是允許不同的物件對相同的訊息（方法呼叫）做出不同的響應。

定義

多型性有兩種主要形式：

1. 編譯時期多型性 (Compile-time Polymorphism)：也稱為靜態多型性 (Static Polymorphism)。

   • 方法重載 (Method Overloading)：在同一類別中，允許有兩個或多個名稱相同但參數列表（參數的數量、類型或順序）不同的方法。編譯器會根據傳入的參數來決定呼叫哪個方法。
   • 運算子重載 (Operator Overloading)：允許為現有的運算子（如 +, -, *, /）定義新的行為，使其能夠作用於自訂的類別物件。

2. 執行時期多型性 (Run-time Polymorphism)：也稱為動態多型性 (Dynamic Polymorphism) 或子型別多型性 (Subtype Polymorphism)。

   • 方法覆寫 (Method Overriding)：當子類別重新定義了其父類別中已有的方法時，就發生了方法覆寫。在執行時期，程式會根據物件的實際類型來決定呼叫哪個版本的方法（父類別或子類別的版本）。這通常需要配合繼承和虛擬方法 (Virtual Methods) 或抽象方法 (Abstract Methods) 來實現。

目的

多型性的主要目的是為了提高程式碼的靈活性、可擴展性，並簡化程式設計。

雜湊 (Hashing)、編碼 (Encoding) 和加密 (Encryption) 都是處理資料轉換的技術，但它們的目的、原理和安全性層級有顯著差異。

1. 雜湊 (Hashing)

• 意義：雜湊是將任意大小的輸入資料，通過一個雜湊函數（Hash Function），轉換成固定大小的輸出值（稱為雜湊值、雜湊碼、摘要或指紋）。這個過程是單向的，通常無法從雜湊值反推出原始資料。
• 目的：
  • 資料完整性驗證 (Data Integrity Verification)：最常見的用途。通過比較原始資料與接收資料的雜湊值，可以判斷資料在傳輸或儲存過程中是否被篡改。如果雜湊值相同，則資料很可能未被修改。
  • 快速查找 (Fast Lookup)：在雜湊表 (Hash Table) 中，雜湊值被用作索引，可以快速定位資料。
  • 密碼儲存 (Password Storage)：儲存使用者密碼的雜湊值，而非明文密碼，以提高安全性。即使資料庫洩漏，攻擊者也無法直接獲取用戶密碼。
• 特點：
  • 單向性：不可逆。
  • 固定輸出長度：無論輸入多大，輸出長度固定。
  • 雪崩效應 (Avalanche Effect)：輸入資料的微小變動，會導致輸出雜湊值發生巨大變化。
  • 碰撞 (Collision)：不同的輸入可能產生相同的雜湊值，但好的雜湊函數會使碰撞的機率極低。
• 對資料處理與安全的貢獻：
  • 資料處理：用於快速索引和查找資料。
  • 安全：確保資料在傳輸或儲存時的完整性；保護敏感資訊（如密碼）不被直接洩露。

2. 編碼 (Encoding)

• 意義：編碼是將資料從一種格式轉換為另一種格式，以便於傳輸、儲存或被特定系統處理。編碼通常是可逆的，且主要關注資料表示的標準化或適應性。
• 目的：
  • 資料轉換與表示：例如，將二進位資料轉換為文字字元（如 Base64 編碼），以便在不支援二進位傳輸的環境（如電子郵件）中傳輸。
  • 字元集轉換：如 UTF-8、UTF-16 編碼，將 Unicode 字元轉換為位元序列。
  • 資料壓縮：某些編碼方式（如 Huffman 編碼）旨在減少資料的冗餘，實現壓縮。
  • URL 編碼：將 URL 中的特殊字元轉換為安全傳輸的格式。
• 特點：
  • 可逆性：可以通過解碼 (Decoding) 恢復原始資料。
  • 非安全性目的：主要目的是為了相容性、效率或表示，而非隱藏資訊。
  • 長度變化：編碼後資料的長度可能會增加或減少。
• 對資料處理與安全的貢獻：
  • 資料處理：確保資料能在不同系統或協議間正確傳輸和處理；實現資料的壓縮。
  • 安全：本身不提供安全保護，但某些編碼（如 Base64）有時會被誤認為一種「隱藏」手段，但它很容易被解碼，因此不能算作安全措施。

3. 加密 (Encryption)

• 意義：加密是將明文資料（Plaintext）轉換為密文（Ciphertext）的過程，以防止未經授權的人讀取。這個過程需要一個金鑰 (Key)，並且通常是可逆的（通過解密 Decryption）。
• 目的：
  • 保密性 (Confidentiality)：確保只有擁有正確金鑰的接收者才能讀取原始資料。
  • 資料安全傳輸：保護敏感資料在網路傳輸過程中不被竊聽。
  • 資料儲存安全：保護儲存的敏感資料（如信用卡號、個人身份資訊）免受未經授權存取的影響。
• 特點：
  • 可逆性：通過解密可以恢復明文。
  • 依賴金鑰：加密和解密都需要金鑰。金鑰管理是加密系統的關鍵。
  • 兩種主要類型：

線性迴歸 (Linear Regression) 和邏輯迴歸 (Logistic Regression) 都是監督式學習 (Supervised Learning) 中常用於預測的演算法，但它們的應用場景和輸出類型有所不同。

線性迴歸 (Linear Regression)

• 定義：線性迴歸是一種用於預測連續數值輸出的模型。它假設自變數 (independent variables, features) 與因變數 (dependent variable, target) 之間存在線性關係。模型試圖找到一條最佳擬合直線（或超平面），來描述這種關係。
• 公式：
  對於簡單線性迴歸（一個自變數）：
  $y = \beta_0 + \beta_1 x + \epsilon$
  對於多元線性迴歸（多個自變數 $x_1, x_2, ..., x_n$）：
  $y = \beta_0 + \beta_1 x_1 + \beta_2 x_2 + ... + \beta_n x_n + \epsilon$
  其中，$y$ 是因變數，$x_i$ 是自變數，$\beta_0$ 是截距項，$\beta_i$ 是各個自變數的係數，$\epsilon$ 是誤差項。
• 輸出：預測值是一個連續的數值，例如房價、溫度、銷售額等。
• 目標：最小化預測值與實際值之間的誤差（通常使用均方誤差 MSE）。

邏輯迴歸 (Logistic Regression)

• 定義：邏輯迴歸是一種用於預測離散輸出的模型，最常見的是二元分類 (Binary Classification) 問題，即預測一個事件發生的機率。儘管名稱中有「迴歸」，但它實際上用於分類任務。
• 公式：
  邏輯迴歸首先計算輸入變數的線性組合（與線性迴歸類似）：
  $z = \beta_0 + \beta_1 x_1 + \beta_2 x_2 + ... + \beta_n x_n$
  然後，將這個線性組合通過一個稱為 Sigmoid（或 Logistic）函數的轉換，將輸出壓縮到 (0, 1) 的範圍內，表示事件發生的機率：
  $P(y=1|x) = \sigma(z) = \frac{1}{1 + e^{-z}}$
  其中，$P(y=1|x)$ 是在給定輸入 $x$ 的情況下，事件 $y=1$ 發生的機率。
• 輸出：預測值是一個介於 0 和 1 之間的機率值。通常會設定一個閾值（如 0.5），如果機率大於閾值，則預測為類別 1；否則預測為類別 0。

這個方法試圖將線性迴歸應用於二元分類問題，並透過設定一個閾值來進行分類。然而，這個方法在理論上和實務上都存在一些問題，因此「不完全 makes sense」。

方法描述：

1. 將二元類別標記為 0 和 1。
2. 使用線性迴歸模型擬合資料，得到一個預測函數 $y = f(x)$。
3. 設定一個閾值 $t$。若 $f(x) \geq t$，則分類為 1；若 $f(x) < t$，則分類為 0。

這個方法不完全 makes sense 的原因：

1. 輸出範圍問題 (Output Range Issue)：

   • 線性迴歸模型預測的輸出 $f(x)$ 是連續的，理論上沒有範圍限制（可能為負值或大於 1）。
   • 將這些無限制的輸出直接與 0 和 1 這兩個離散標籤進行類比，並期望它們代表機率，是個誤導。雖然我們將類別標記為 0 和 1，但線性迴歸模型並非為輸出機率而設計。
   • 如果數據中有離群值（outliers），線性迴歸的預測值可能會被極大或極小地拉偏，超出合理的範圍（例如，預測值遠大於 1 或遠小於 0），這使得閾值 $t$ 的選擇變得困難且不穩定。

2. 對標籤敏感 (Sensitivity to Label Values)：

   • 線性迴歸模型對目標變數的數值敏感。如果我們將類別標記為 0 和 1，得到的迴歸線可能與標記為 0 和 100 的情況下得到的迴歸線完全不同。這意味著模型的結果會受到標籤數值選擇的影響，這不是一個好的分類器應有的特性。一個好的分類器應該只關心類別的區分，而不是它們之間的數值距離。

Git 是一個分散式版本控制系統 (Distributed Version Control System, DVCS)，而 GitHub 是一個基於 Web 的託管服務，用於 Git 專案。兩者緊密合作，但它們的「工作流程」(workflow) 是指不同的層面。

Git 工作流程 (Git Workflow)

Git 工作流程指的是開發團隊如何使用 Git 來管理程式碼的版本變更、分支、合併等活動。它是一套指導開發者如何組織和協同工作的方法論。

• 常見的 Git 工作流程：

  • Centralized Workflow (集中式工作流程)：所有開發者都與一個中心倉庫（通常是 main 或 master 分支）進行互動。開發者從中心倉庫拉取最新代碼，在本地開發，然後將變更推送到中心倉庫。類似於 SVN 的工作方式，但仍然是分散式的。
  • Feature Branch Workflow (特性分支工作流程)：為每一個新功能或修復創建一個獨立的分支（feature branch），從主分支（如 main）創建，開發完成後再合併回主分支。這是最常見和推薦的工作流程。
  • Gitflow Workflow (Gitflow 工作流程)：一個更嚴格、更複雜的工作流程，包含 main、develop、feature、release 和 hotfix 等多個長期存在的 és 短期存在的分支，適合大型或有嚴格發布週期的專案。
  • Forking Workflow (Forking 工作流程)：每個開發者在其自己的伺服器端倉庫（fork）上工作，然後通過 Pull Request (PR) 的方式將變更提交到主專案。這在開源專案中非常普遍。

• 重點：Git 工作流程關注的是如何使用 Git 命令和分支策略來管理版本控制和協同開發。

GitHub 工作流程 (GitHub Workflow)

GitHub 工作流程通常是指在 GitHub 平台上，特別是結合了 Forking Workflow 和 Pull Request (PR) 機制的協同開發模式。

• GitHub 協同開發流程 (典型)：

  1. Fork Repository：開發者首先 Fork 專案的原始倉庫到自己的 GitHub 帳戶下，創建一個屬於自己的副本。
  2. Clone & Branch：將 Fork 的倉庫 Clone 到本地，然後基於 main 分支創建一個新的特性分支（feature branch）來進行開發。
  3. Develop & Commit：在本地分支上進行開發，並頻繁提交 (commit) 變更。
  4. Push to Fork：將本地的特性分支推送到自己 Fork 的倉庫中。
  5. Create Pull Request：在 GitHub 上，從自己的 Fork 倉庫的特性分支向原始專案的 main 分支發起一個 Pull Request。
  6. Review & Discuss：專案維護者或其他貢獻者會審查 PR 中的變更，進行討論、提出修改建議。
  7. Update PR：如果需要修改，開發者可以在本地分支上繼續提交變更，推送到自己的 Fork 倉庫，PR 會自動更新。
  8. Merge PR：一旦 PR 被批准，維護者就可以將其合併到原始專案的 main 分支中。

• 重點：GitHub 工作流程關注的是如何利用 GitHub 平台提供的功能（如 Fork, Pull Request, Code Review）來促進開源專案或團隊協作。

主要差異 (Major Differences)

當兩個開發團隊在各自的特性分支（feature branch）上開發，並嘗試將變更合併回主分支（main branch）時，如果他們修改了同一個檔案的同一部分程式碼，就會發生合併衝突（Merge Conflict）。Git 無法自動決定保留哪個版本的變更，因此需要開發者手動介入解決。

解決合併衝突的步驟如下：

第一階段：識別衝突 (Identify Conflicts)

1. 觸發合併操作：

   • 開發者首先會嘗試將自己的特性分支合併到主分支，或者將主分支的最新變更合併到自己的特性分支。假設開發者 A 嘗試將 feature-A 合併到 main。
   • 命令：git checkout main
   • 命令：git merge feature-A

2. Git 標記衝突：

   • 如果發生衝突，Git 會在合併過程中停止，並給出提示，例如：

     Auto-merging <filename>
     CONFLICT (content): Merge conflict in <filename>
     Automatic merge failed; fix conflicts and then commit the result.
     

   • Git 會在衝突檔案中插入特殊的標記來指示衝突的範圍：
     • <<<<<<< HEAD：標記了當前分支（通常是目標分支，如 main）的變更內容。
     • =======：分隔符。
     • >>>>>>> <feature-branch-name>：標記了正在合併進來的分支（如 feature-A）的變更內容。

3. 檢查衝突狀態：

   • 可以使用 git status 命令來查看哪些檔案存在衝突。git status 會將衝突檔案列在 "Unmerged paths" 區域。

第二階段：解決衝突 (Resolve Conflicts)

1. 手動編輯衝突檔案：
   • 打開衝突檔案（如上面提示中的 <filename>）。
   • 找到 <<<<<<< HEAD、======= 和 >>>>>>> <feature-branch-name> 這些標記。
   • 仔細閱讀兩個分支的變更內容，並決定最終要保留的程式碼。
   • 手動編輯檔案，刪除 Git 插入的衝突標記（<<<<<<< HEAD, =======, >>>>>>> ...），並將程式碼修改成你想要的最終版本。這可能意味著：
     • 保留當前分支 (HEAD) 的變更。
     • 保留正在合併進來的分支的變更。
     • 結合兩者的變更。
     • 重寫一部分或全部程式碼。
   • 範例：
     假設原始程式碼是 x = 5。
     feature-A 分支改為 x = 10。
     main 分支改為 x = 20。

核心觀念

• Fork：將他人的 Git repository 複製至自己的 GitHub 帳號，形成獨立的遠端倉庫，保有對原始（upstream）專案的只讀權限。
• Branch：在本地或遠端倉庫中建立分支，用於開發新功能或修正錯誤，避免直接在 main 分支上操作。
• Pull Request (PR)：向 upstream 的 main 分支提出合併請求，說明變更內容，供原始維護者審查與合併。
• Merge：經過審查後，將 PR 中的分支變更合併至 main，完成新功能的正式提交。

---

解題步驟

1. Fork repository

   • 在 GitHub 上開啟目標專案，點擊右上角的 Fork 按鈕。
   • 產生的遠端倉庫位於自己的帳號下，URL 形式為 https://github.com/<your-username>/<repo>.git。

2. Clone forked repository

   git clone https://github.com/<your-username>/<repo>.git
   cd <repo>
   

   • 本機會有一個 origin 指向自己的 fork。

3. 設定 upstream (可選但建議)

   git remote add upstream https://github.com/<original-owner>/<repo>.git
   git fetch upstream
   

   • 之後可用 git pull upstream main 同步上游 main 分支的最新變更。

4. 建立新分支

   git checkout -b <feature-branch>
   

   • 分支名稱應具描述性，例如 add-login-page。

5. 實作變更

   • 在本機編輯程式碼、文件或資源。
   • 確認變更符合專案風格與測試需求。

6. Stage & commit

   git add .
   git commit -m "Add <簡要說明> (e.g., Add login page UI)"
   

   • git commit 內的訊息遵循「動詞 + 目的」的慣例，便於審查。

7. Push 分支至自己的 fork

   git push origin <feature-branch>
   

   • 此時遠端 origin 上會出現剛推送的分支。

8. 在 GitHub 建立 Pull Request

   • 前往 fork 的 GitHub 頁面，會自動顯示 “Compare & pull request” 按鈕，點擊後會開啟 PR 編輯頁面。
   • Base repository 設為原始 owner/<repo>，Base branch 設為 main。

在網路封包傳輸過程中，檢查 IP 位址以決定封包下一跳（next hop）或最終目的地網路的裝置是路由器 (Router)。

路由器是專門負責在不同網路之間轉送封包的裝置。當路由器收到一個封包時，它會檢查封包的 IP 標頭（IP Header）中的目的 IP 位址。然後，路由器會查詢其路由表（Routing Table），該表包含了網路的路由資訊。路由器根據目的 IP 位址，查找到最適合的下一跳路由器或直接連接的網路介面，然後將封包轉送到該處。

上述提到的「檢查 IP 位址以決定封包的下一跳或最終目的地」的動作，是發生在 OSI 模型（Open Systems Interconnection Model）的第三層，即網路層 (Network Layer)。

OSI 模型層級與功能：

• 第一層：實體層 (Physical Layer)：負責傳輸原始的位元流（bit stream），處理電氣、機械、過程和功能介面。
• 第二層：資料連結層 (Data Link Layer)：負責在相鄰節點之間傳輸資料幀（frames），處理 MAC 位址，並提供錯誤偵測和糾正。例如乙太網路 (Ethernet)。
• 第三層：網路層 (Network Layer)：負責處理邏輯位址（如 IP 位址），以及負責在不同網路之間路由（轉送）封包。這是 IP 位址發揮作用的層級。

TTL (Time to Live) 欄位位於 IP 標頭中，其主要功能是防止封包在網路上無限循環傳播。

功能說明：

1. 計數器：TTL 欄位是一個 8 位元的無符號整數，其值通常在 0 到 255 之間。當封包從來源主機發出時，發送方會設定一個初始的 TTL 值（這個值通常由作業系統預設，一般為 64、128 或 255）。
2. 遞減過程：每當封包通過一個路由器（即每經過一個「跳」），路由器都會將 TTL 值減 1。
3. 封包丟棄：如果 TTL 值在路由器處被減到 0，則該路由器會丟棄該封包，並且通常會向來源主機發送一個 ICMP (Internet Control Message Protocol) 訊息，告知封包已超時。

不，並非所有在網路上傳輸的封包都一定包含 IP 標頭 (IP Header)。

原因：

IP (Internet Protocol) 是網路層（OSI Layer 3）的協定，它負責在不同網路之間進行邏輯定址和路由轉送。IP 標頭包含了目的 IP 位址、來源 IP 位址、TTL 等關鍵資訊，這些資訊對於路由器進行封包轉送至關重要。

然而，在某些情況下，封包可能不需要 IP 標頭：

1. 非 IP 網路：
   • 網際網路 (Internet) 主要基於 IP 協定，但並非所有網路都必須使用 IP。在區域網路 (LAN) 或一些專用網路中，可能會使用其他 Layer 2 或 Layer 2.5 協定來傳輸封包，例如：
     • 乙太網路廣播 (Ethernet Broadcast)：在區域網路內，乙太網路幀 (Ethernet Frame) 可以直接廣播給同一網段內的所有設備，而不需要 IP 位址進行路由。

要判斷兩台主機 A 和 B 是否屬於同一個子網路（Subnetwork），我們需要知道它們各自的 IP 位址以及它們所使用的子網路遮罩（Subnet Mask）。

判斷方法：

將主機 A 的 IP 位址與其子網路遮罩進行位元 AND 運算，得到主機 A 的網路位址 (Network Address)。
將主機 B 的 IP 位址與其子網路遮罩進行位元 AND 運算，得到主機 B 的網路位址。

如果兩台主機計算出的網路位址相同，則它們屬於同一個子網路。反之，則不屬於。

運算說明：

位元 AND 運算規則：

• 1 AND 1 = 1
• 1 AND 0 = 0
• 0 AND 1 = 0
• 0 AND 0 = 0

步驟詳解：

1. 獲取 IP 位址和子網路遮罩：

   • 主機 A 的 IP 位址：$IP_A$
   • 主機 A 的子網路遮罩：$Mask_A$
   • 主機 B 的 IP 位址：$IP_B$
   • 主機 B 的子網路遮罩：$Mask_B$

   重要假設：在判斷是否屬於同一個子網路時，通常假設兩台主機使用相同的子網路遮罩。如果它們使用不同的子網路遮罩，則判斷會變得複雜，可能需要更進一步的路由資訊。但標準的子網路判斷是基於共同的子網路遮罩。我們這裡假設 $Mask_A = Mask_B = Mask$。

2. 進行位元 AND 運算：

   • 計算 A 的網路位址：$NetworkAddress_A = IP_A \text{ AND } Mask$
   • 計算 B 的網路位址：$NetworkAddress_B = IP_B \text{ AND } Mask$

3. 比較網路位址：

   • 如果 $NetworkAddress_A = NetworkAddress_B$，則 A 和 B 屬於同一個子網路。
   • 否則，它們屬於不同的子網路。

範例：

IP 位址被分為公開 IP (Public IP) 和私有 IP (Private IP)，這是為了更有效地管理和使用有限的 IPv4 位址空間，同時也為了網路安全。

1. 公開 IP 位址 (Public IP Address)

• 定義：
  公開 IP 位址是分配給連接到網際網路的裝置的唯一 IP 位址。這些位址由網際網路位址分配機構 (IANA) 分配給區域網路註冊機構 (RIRs)，再由 RIRs 分配給 ISP (網際網路服務提供者)。
  公開 IP 位址在整個網際網路上是可路由的，並且是全球唯一的。
• 使用時機：
  • 伺服器（如網站伺服器、郵件伺服器）需要一個公開 IP 位址，以便全世界的用戶都能夠存取。
  • 直接連接到網際網路的裝置，例如 ISP 分配給家庭路由器 WAN 口的位址。
  • 需要從外部網路直接存取的任何裝置。

2. 私有 IP 位址 (Private IP Address)

• 定義：
  私有 IP 位址是保留用於內部網路（如家庭網路、公司內部網路）的 IP 位址範圍。這些位址範圍根據 RFC 1918 標準被指定，並且不會在網際網路上進行路由。
  私有 IP 位址範圍包括：
  • $10.0.0.0$ 到 $10.255.255.255$ (10.0.0.0/8)
  • $172.16.0.0$ 到 $172.31.255.255$ (172.16.0.0/12)
  • $192.168.0.0$ 到 $192.168.255.255$ (192.168.0.0/16)
• 使用時機：
  • 內部網路中的個人電腦、筆記型電腦、智慧手機、印表機等裝置。
  • 這些裝置透過網路位址轉換 (Network Address Translation, NAT) 裝置（通常是路由器）與網際網路進行通訊。NAT 裝置會將內部私有 IP 位址轉換為一個或多個公開 IP 位址，反之亦然。

公開 IP 與私有 IP 的關係：

核心觀念

• 遞迴與不變式：在遞迴過程中保持某個不變式（Invariant），可用來推導最終結果。
• 指數快速冪 (Exponentiation by Squaring)：利用 $n$ 的二進位表示，把指數運算的時間從 $O(n)$ 降至 $O(\log n)$。
• 數學歸納法：證明遞迴函式的正確性時，常以「若在第 $k$ 步成立，則第 $k+1$ 步亦成立」的方式進行。

---

解題方法

1. 觀察遞迴結構

   • 基礎情況：n == 0 時回傳 a。
   • 偶數情況：n 為偶數時，遞迴呼叫 f(a, b*b, n/2)。
   • 奇數情況：n 為奇數時，遞迴呼叫 f(a*b, b, n-1)。

2. 建立不變式
   在任意遞迴呼叫 f(a', b', n') 中，不變式 為
   $\text{目前的結果} = a' \times (b')^{\,n'}$
   只要此不變式在每一步轉換後仍然成立，最終返回值即為原始參數的 $a \times b^{\,n}$。

3. 驗證每一個分支

   • 基礎情況 (n' = 0)
     $a' \times (b')^{\,0}=a'$
     函式回傳 a'，符合不變式。

   • 偶數情況 (n' = 2k)
     先把 $b'$ 平方並把指數除半：

$f(a', b', 2k) \to f\bigl(a', (b')^{2}, k\bigr)$

 不變式變為  

$a' \times \bigl((b')^{2}\bigr)^{k}=a' \times (b')^{2k}$

 與原式等價，故不變式保持。  

• 奇數情況 (n' = 2k+1)
  先把 $a'$ 乘上一個 $b'$，再減一個指數：

$f(a', b', 2k+1) \to f\bigl(a'\,b', b', 2k\bigr)$

 不變式變為  

$(a' b') \times (b')^{\,2k}=a' \times (b')^{\,2k+1}$

這是一個典型的拓撲排序 (Topological Sort) 問題。我們需要判斷給定的課程先修要求是否構成一個有向無環圖 (Directed Acyclic Graph, DAG)，如果構成 DAG，則表示可以完成所有課程；如果存在環（循環依賴），則無法完成所有課程。

問題模型：

• 節點 (Nodes)：每個課程代表圖中的一個節點。
• 邊 (Edges)：如果為了上課 i，必須先上課 c，那麼我們就從節點 c 指向節點 i 建立一條有向邊 $c \rightarrow i$。這表示「c 是 i 的先修課程」。
• 目標：判斷這個圖中是否存在有向環。如果沒有環，則可以完成所有課程（返回 true）；如果存在環，則無法完成（返回 false）。

演算法：深度優先搜尋 (Depth-First Search, DFS) 進行環檢測

DFS 是檢測有向圖中環的常用方法。我們需要追蹤節點的三種狀態：

1. 未訪問 (Unvisited)：節點尚未被 DFS 訪問過。
2. 訪問中 (Visiting)：節點正在被 DFS 訪問，即它在當前的 DFS 遞迴呼叫堆疊中。
3. 已訪問 (Visited)：節點及其所有子節點都已被 DFS 訪問完畢。

演算法步驟：

1. 建立圖的表示：

   • 我們需要一個圖的鄰接表 (Adjacency List) 來表示課程之間的依賴關係。
   • prerequisites 陣列 p 實際上定義了圖的邊。對於 p[i] = [c1, c2, ..., ck]，這意味著存在邊 $c_1 \rightarrow i$, $c_2 \rightarrow i$, ..., $c_k \rightarrow i$。
   • 我們可以構建一個 graph，其中 graph[course] 是一個列表，包含所有依賴於 course 的課程。也就是說，如果 c 是 i 的先修，我們在圖中表示為 $c \rightarrow i$。
   • 例如，對於 n = 3, p = [[1, 2], [], [1]]：
     • 課程 0 的先修是 1 和 2。所以有邊 $1 \rightarrow 0$ 和 $2 \rightarrow 0$。
     • 課程 1 沒有先修。
     • 課程 2 的先修是 1。所以有邊 $1 \rightarrow 2$。
   • 構建的鄰接表（表示「誰依賴於我」）：
     graph[0] = []
graph[1] = [0, 2]
graph[2] = [0]

2. 初始化狀態標記：

   • 創建一個陣列 visited_status，大小為 n，所有元素初始化為 0 (未訪問)。
     • 0: Unvisited
     • 1: Visiting
     • 2: Visited

3. 遍歷所有課程進行 DFS：

   • 迴圈遍歷所有課程 i 從 0 到 n-1。
   • 如果 visited_status[i] 是 0 (未訪問)，則呼叫 DFS 函數 hasCycle(i, graph, visited_status)。
   • 如果在任何一次 DFS 呼叫中發現了環（hasCycle 返回 true），則整個課程系統存在循環依賴，返回 false。

4. DFS 函數 hasCycle(course, graph, visited_status)：

   • 標記為訪問中：將 visited_status[course] 設置為 1 (Visiting)。
   • 遍歷鄰居：對於 course 的每一個鄰居 neighbor (即 graph[course] 中的課程)：
     • 如果 visited_status[neighbor] 是 1 (Visiting)：這表示我們發現了一個環，因為我們遇到了正在訪問的節點。返回 true。
     • 如果 visited_status[neighbor] 是 0 (Unvisited)：遞迴呼叫 hasCycle(neighbor, graph, visited_status)。如果遞迴呼叫返回 true，則表示在 neighbor 的子圖中存在環，直接返回 true。
   • 標記為已訪問：如果遍歷完所有鄰居都沒有發現環，則將 visited_status[course] 設置為 2 (Visited)。
   • 返回 false：表示從當前節點開始的 DFS 路徑沒有發現環。

5. 最終結果：

   • 如果在遍歷所有課程後，沒有任何 DFS 呼叫返回 true，則表示圖是 DAG，可以完成所有課程，返回 true。

時間複雜度分析：

• 圖的構建：需要遍歷 p 陣列。對於每個課程 i，我們遍歷其先修課程 c1, ..., ck，並在鄰接表中添加邊 $c_j \rightarrow i$。總共需要處理的邊的數量是所有課程的先修課程總數，即 $\sum_{i=0}^{n-1} len(p[i])$。這部分時間複雜度是 $O(n + E)$，其中 $E = \sum_{i=0}^{n-1} len(p[i])$ 是總邊數。
• DFS 遍歷：每個節點 (課程) 和每條邊 (先修關係) 在 DFS 中最多被訪問一次。因此，DFS 的時間複雜度也是 $O(n + E)$。
• 總體時間複雜度：$O(n + E)$，其中 $E$ 是所有課程的先修課程總數。這符合題目要求的線性時間複雜度 $O(\sum len(p[i]))$。

空間複雜度分析：

• 鄰接表：$O(n + E)$
• visited_status 陣列：$O(n)$
• DFS 遞迴堆疊：最壞情況下，如果圖是線性的，堆疊深度可能達到 $O(n)$。
• 總體空間複雜度：$O(n + E)$。

範例 1 驗證：n = 3, p = [[1, 2], [], [1]]

• 圖：$1 \rightarrow 0$, $2 \rightarrow 0$, $1 \rightarrow 2$。
• 鄰接表：graph[0] = [], graph[1] = [0, 2], graph[2] = [0]。
• visited_status = [0, 0, 0]

1. 呼叫 hasCycle(0):

   • visited_status[0] = 1
   • graph[0] 為空，無鄰居。
   • visited_status[0] = 2。返回 false。
   • visited_status = [2, 0, 0]

2. 呼叫 hasCycle(1):

   • visited_status[1] = 1
   • 鄰居是 0 和 2。
   • 處理鄰居 0：visited_status[0] 是 2 (Visited)，跳過。
   • 處理鄰居 2：visited_status[2] 是 0 (Unvisited)。呼叫 hasCycle(2)。