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

本題主要在探討對稱式加密與非對稱式加密的特性及其應用情境。

核心觀念：

• 對稱式加密 (Symmetric Encryption)：使用同一把金鑰進行加密與解密。
• 非對稱式加密 (Asymmetric Encryption)：使用一對金鑰（公鑰與私鑰）進行加密與解密。公鑰用於加密，私鑰用於解密；或私鑰用於簽章，公鑰用於驗證。

詳解：
(1) 對稱式加密與非對稱式加密的主要差異如下：

特性	對稱式加密 (Symmetric Encryption)	非對稱式加密 (Asymmetric Encryption)
金鑰數量	一把金鑰（共享金鑰）	一對金鑰（公鑰、私鑰）
金鑰管理	需要安全地將金鑰傳遞給通訊雙方，金鑰管理較為複雜，尤其在多方通訊時。	公鑰可公開傳播，私鑰需妥善保管，金鑰管理相對容易。
加密速度	速度快，效率高，適合加密大量資料。	速度慢，效率低，不適合加密大量資料。

本題考察的是 SQL Injection 攻擊原理及其防範方法，是網路安全領域常見的漏洞。

核心觀念：

• SQL Injection (SQL 注入)：一種常見的網頁安全漏洞，攻擊者透過在網頁輸入欄位中插入惡意的 SQL 語句，來欺騙資料庫執行非預期的指令。
• 字串拼接的風險：將使用者輸入的資料直接拼接到 SQL 語句中，容易被惡意字串取代或修改原有的 SQL 邏輯。

詳解：
題目中的 SQL 查詢語句是 SELECT * FROM users WHERE username = '$username' AND password = '$password';。攻擊者可以利用這個語句的結構，透過輸入特殊的字串來改變查詢的條件。

(1) 攻擊者如何利用 SQL Injection 登入 admin 帳戶並繞過密碼檢查：

攻擊者可以嘗試在 $username 或 $password 的輸入欄位中注入惡意 SQL 語句。最常見的攻擊方式是利用 OR 語句來繞過條件判斷。

假設攻擊者在 username 欄位輸入：admin' OR '1'='1
然後在 password 欄位輸入任何內容（例如：anything）

那麼，經過 PHP 或其他後端語言處理後，實際執行的 SQL 語句會變成：
SELECT * FROM users WHERE username = 'admin' OR '1'='1' AND password = 'anything';

攻擊原理說明：

• 原查詢是 WHERE username = '$username' AND password = '$password'。
• 注入後，`

本題考查圖 (Graph) 的兩種常用表示方法：鄰接矩陣 (Adjacency Matrix) 和鄰接串列 (Adjacency List)，以及在特定應用場景下的選擇。

核心觀念：

• 圖 (Graph)：由節點 (Vertices) 和邊 (Edges) 組成，用於表示物件之間的關係。
• 鄰接矩陣 (Adjacency Matrix)：使用一個 $V \times V$ 的二維陣列來表示圖，其中 $V$ 是節點的數量。矩陣中的元素 $M[i][j]$ 為 1（或權重）表示節點 $i$ 和節點 $j$ 之間有邊，為 0 表示沒有邊。
• 鄰接串列 (Adjacency List)：為圖中的每個節點維護一個串列，其中包含與該節點相鄰的所有節點。
• 稀疏圖 (Sparse Graph)：圖中的邊數遠少於可能的最大邊數（對於無向圖，最大邊數為 $V(V-1)/2$）。
• 稠密圖 (Dense Graph)：圖中的邊數接近可能的最大邊數。

詳解：
題目描述的社群網路具有以下特點：

1. 節點數量龐大：上百萬名使用者，意味著 $V$ 非常大。
2. 邊的數量相對稀疏：大部分使用者的好友數很少。這意味著圖是稀疏圖。

我們來分析兩種表示方法的空間複雜度和時間複雜度，並結合稀疏圖的特性進行判斷。

1. 鄰接矩陣 (Adjacency Matrix)

• 空間複雜度：$O(V^2)$。
  • 無論圖中有多少邊，都需要一個 $V \times V$ 的矩陣。
  • 在這個問題中，$V$ 是上百萬，所以 $V^2$ 會是一個天文數字（例如 $10^6 \times 10^6 = 10^{12}$），佔用的記憶體空間將會非常巨大，幾乎不可能儲存。
• 查詢兩節點間是否有邊：$O(1)$。
  • 直接查閱矩陣元素 $M[i][j]$ 即可。
• 遍歷某節點的所有鄰居：$O(V)$。
  • 需要掃描該節點對應的一整行（或一整列）。

本題探討網路位址轉換 (NAT) 的概念、原理與應用。

核心觀念：

• IP 位址枯竭問題：IPv4 位址數量有限，無法為全球所有裝置分配獨立的公共 IP 位址。
• 私有 IP 位址 (Private IP Addresses)：保留部分 IP 位址範圍（如 10.0.0.0/8, 172.16.0.0/12, 192.168.0.0/16）供內部網路使用，這些位址在 Internet 上不可路由。
• 公共 IP 位址 (Public IP Addresses)：可在 Internet 上唯一識別的 IP 位址，由 ISP 分配。
• NAT (Network Address Translation)：一種將私有 IP 位址轉換為公共 IP 位址（反之亦然）的技術，允許內部網路中的多個裝置共用一個或少數幾個公共 IP 位址與 Internet 通訊。
• 埠號 (Port Number)：用於區分同一主機上不同應用程式的 TCP 或 UDP 連接。

詳解：
(1) NAT 的功能與目的，以及位址與埠號的轉換：

• 功能與目的：
  NAT 的主要功能是實現私有 IP 位址與公共 IP 位址之間的轉換。其主要目的是緩解 IPv4 位址枯竭的危機，允許大量使用私有 IP 位址的內部網路裝置，僅需一個或少數幾個公共 IP 位址就能連上 Internet。此外，NAT 也能在一定程度上增強內部網路的安全性，因為外部網路無法直接存取內部網路的私有 IP 位址。

• 轉換位址與埠號實現雙向通訊：
  NAT 設備（通常是路由器）維護一個 NAT 轉換表 (NAT Translation Table)。當內部網路的裝置發起與外部網路的通訊時，NAT 設備會執行以下操作：

  1. 出站封包 (Outbound Packet)：
     • 內部裝置（例如 IP: 192.168.1.100，Port: 12345）發送封包到外部伺服器（例如 IP: 203.0.113.1，Port: 80）。
     • NAT 路由器收到封包後，會將來源 IP 位址 (192.168.1.100) 替換為路由器本身的公共 IP 位址（例如 IP: 203.0.113.50）。
     • 同時，它會為這個連接分配一個新的來源埠號（例如：50000）。
     • NAT 路由器會在轉換表中記錄這個映射關係：(內部 IP: 192.168.1.100, 內部 Port: 12345) <--> (公共 IP: 203.0.113.50, 公共 Port: 50000)。
     • 修改後的封包（來源 IP: 203.0.113.50, 來源 Port: 50000）被發送到 Internet。
  2. 入站封包 (Inbound Packet)：
     • 外部伺服器回應的封包，其目的 IP 位址是路由器的公共 IP (203.0.113.50)，目的埠號是之前分配的埠號 (50000)。
     • NAT 路由器收到封包後，查詢其 NAT 轉換表，找到與 (公共 IP: 203.0.113.50, 公共 Port: 50000) 匹配的記錄。
     • 它將目的 IP 位址 (203.0.113.50) 轉換回原始的內部 IP 位址 (192.168.1.100)，並將目的埠號 (50000) 轉換回原始的內部埠號 (12345)。
     • 修改後的封包被轉發到內部網路的目標裝置。

通過這種方式，NAT 設備充當了內部網路與外部網路之間的橋樑，通過修改封包的 IP 位址和埠號，實現了多個內部裝置能夠共用一個公共 IP 位址進行雙向通訊。

本題探討作業系統中的死結 (Deadlock) 問題，包括其發生條件、定義、運作過程，以及如何透過策略來避免。

核心觀念：

• 死結 (Deadlock)：在多個程序（或執行緒）競爭有限資源的系統中，當每個程序都持有某個資源，並在等待其他程序釋放它所需要的資源時，就可能發生死結。所有程序都處於等待狀態，無法繼續執行。
• 死結的四個必要條件 (Coffman Conditions)：
  1. 互斥 (Mutual Exclusion)：資源一次只能被一個程序使用。
  2. 持有並等待 (Hold and Wait)：程序至少已獲得一個資源，並正在等待另一個程序所持有的資源。
  3. 非搶佔 (No Preemption)：資源不能被強行從持有它的程序中剝奪，只能由持有者主動釋放。
  4. 循環等待 (Circular Wait)：存在一個程序序列 $P_1, P_2, ..., P_n$，其中 $P_1$ 等待 $P_2$ 持有的資源，$P_2$ 等待 $P_3$ 持有的資源，...，$P_n$ 等待 $P_1$ 持有的資源。

詳解：
死結的定義與運作過程：
死結發生時，系統會進入一種僵持狀態，所有涉及的程序都無法繼續執行，直到外部干預（如重啟系統）或其中一個程序異常終止。其運作過程就是不斷滿足上述四個必要條件，形成一個封閉的等待迴圈。

死結的四個必要條件：

1. 互斥 (Mutual Exclusion)：
   • 定義：資源是不可共享的，一次只能被一個程序佔用。例如，印表機、硬碟機等。
   • 運作過程：當程序 A 請求並獲得了資源 X，其他程序（如 B）就無法再使用資源 X，除非 A 主動釋放。
2. 持有並等待 (Hold and Wait)：
   • 定義：一個程序至少已經獲得了某個資源，但同時又在等待獲取其他程序所持有的資源。
   • 運作過程：程序 A 獲得資源 X，然後又去請求資源 Y，而資源 Y 正被程序 B 持有。
3. 非搶佔 (No Preemption)：
   • 定義：已經分配給某程序的資源，不能被強制從該程序中奪取，必須由該程序自願釋放。
   • 運作過程：即使系統發現程序 A 持有資源 X 並等待資源 Y，如果資源 Y 是非搶佔的，系統也不能直接將資源 Y 從持有者 B 那裡搶過來給 A。
4. 循環等待 (Circular Wait)：
   • 定義：形成一個程序等待鏈，鏈中的每個程序都在等待鏈中下一個程序所持有的資源。
   • 運作過程：例如，$P_1$ 持有 $R_1$ 等待 $R_2$，$P_2$ 持有 $R_2$ 等待 $R_3$，...，$P_n$ 持有 $R_n$ 等待 $R_1$。

情境分析與死結風險：

• 資源：資源 A，資源 B。
• 程序：P1，P2。
• P1 的需求：先取得 A，再取得 B。
• P2 的需求：先取得 B，再取得 A。

死結發生的情境：

1. P1 獲得資源 A (滿足持有並等待的「持有」部分)。
2. P2 獲得資源 B (滿足持有並等待的「持有」部分)。

核心觀念

• 專案網路圖 (Network Diagram)：以活動為節點、前置關係為有向邊的圖形，用以表示工作流程。
• 最早開始時間 (ES) / 最早完成時間 (EF)：由「前置活動」的 EF 推算，不可早於任何前置活動完成。
• 最遲開始時間 (LS) / 最遲完成時間 (LF)：由「後續活動」的 LS 逆推，保證不延遲整體工期。
• 總浮時 (Total Float, Slack)：$TF = LS - ES = LF - EF$，表示該活動可延遲而不影響專案完工時間。
• 關鍵路徑 (Critical Path)：所有浮時為 $0$ 的活動組成，決定專案最短完成時間。

---

解題方法

1. 繪製網路圖

   • 以「開始」節點 → 活動 → 「結束」節點的形式連接。
   • 每條有向邊表示「前置活動 → 後續活動」。

2. 前向傳遞 (Forward Pass)

   • 計算每個活動的 ES 與 EF：

$$\text{ES}_i = \max_{j \in \text{predecessors}(i)} \text{EF}_j,\qquad \text{EF}_i = \text{ES}_i + \text{Duration}_i$$

3. 後向傳遞 (Backward Pass)
   • 先將所有「末端」活動的 LF 設為專案完工時間（由前向傳遞得到的最大 EF）。
   • 再逆推每個活動的 LS 與 LF：

$$\text{LF}_i = \min_{k \in \text{successors}(i)} \text{LS}_k,\qquad \text{LS}_i = \text{LF}_i - \text{Duration}_i$$

4. 計算浮時

   • $TF_i = LS_i - ES_i = LF_i - EF_i$。

5. 判定關鍵路徑

   • $TF_i = 0$ 的活動即為關鍵路徑上的活動。

---

步驟詳解

1️⃣ 網路圖 (Network Diagram)

Start
  |
  v
[1] A (5天)
 / \
v   v
[2] B (2天)   [3] C (6天)
 |
 v
[4] D (8天)
 / \
v   v
[5] E (2天)   [6] F (3天)
 \   /
  \ /
  End

• 活動 1 無前置 → 直接從 Start 開始。
• 活動 2、3 皆以 1 為前置。
• 活動 4 以 2 為前置。
• 活動 5、6 皆以 4 為前置，最後彙聚於 End。

2️⃣ 前向傳遞 (計算 ES / EF)

核心觀念

本題考查實體關係模型（Entity-Relationship Model, ER Model）中的：

• 實體（Entity）與屬性（Attribute）
• 鍵值屬性（Key Attribute）
• 一對多基數關係（One-to-Many Cardinality）
• 參與的必要性與選擇性（例如 $0..N$、$1..N$）

題目指出：

1. 應收帳目保存客戶基本資料。
2. 一位客戶一個月內可有多次付款。
3. 一位客戶同月份內可收到多張發票。

因此，付款與發票都應獨立成為實體，不能將同月份的多筆資料合併成一筆。

---

實體與屬性

題目沒有明確列出所有欄位，以下採用合理且完整的資料庫設計。

1. 應收帳目（Customer Account）

代表一位客戶的應收帳戶及基本資料。

屬性	說明
客戶編號（CustomerID）	主鍵，唯一識別客戶
客戶名稱（CustomerName）	客戶姓名或公司名稱
客戶地址（Address）	客戶地址
客戶電話（Phone）	聯絡電話
客戶電子郵件（Email）	電子郵件

其中，CustomerID 為鍵值屬性。

2. 付款（Payment）

代表客戶所進行的一筆付款交易。

屬性	說明
付款編號（PaymentID）	主鍵，唯一識別付款紀錄
付款日期（PaymentDate）	實際付款日期
付款金額（PaymentAmount）	本次付款金額
付款方式（PaymentMethod）	現金、轉帳、信用卡等
客戶編號（CustomerID）	外鍵，指向應收帳目

其中，PaymentID 為鍵值屬性，CustomerID 為外鍵。

3. 發票摘要（Invoice Summary）

代表開立給客戶的一張發票或一筆發票摘要。

屬性	說明
發票編號（InvoiceID）	主鍵，唯一識別發票
發票日期（InvoiceDate）	發票開立日期
發票金額（InvoiceAmount）	發票總金額
發票狀態（InvoiceStatus）	未付款、部分付款、已付款等
客戶編號（CustomerID）	外鍵，指向應收帳目

其中，InvoiceID 為鍵值屬性，CustomerID 為外鍵。

---

實體關係圖

本題為申論題，共分為兩部分：定義人工智慧 (AI) 以及說明 AI 對企業的價值。

核心觀念：

• 人工智慧 (Artificial Intelligence, AI)：模擬人類智能過程的計算機科學領域，包括學習、解決問題、感知、語言理解等。
• 企業價值：指 AI 技術如何幫助企業提高效率、降低成本、增加收入、改善決策、提升競爭力等。

詳解：

第一部分：何謂人工智慧？

人工智慧 (AI) 是一個廣泛的電腦科學領域，其目標是創造能夠執行通常需要人類智能才能完成的任務的系統。這些任務包括但不限於：

• 學習 (Learning)：從數據中獲取知識或技能。
• 推理 (Reasoning)：根據已知資訊進行邏輯推斷。
• 問題解決 (Problem Solving)：找到達成目標的方法。
• 感知 (Perception)：理解視覺、聽覺等感官資訊。
• 語言理解 (Language Understanding)：處理和理解人類語言。
• 決策制定 (Decision Making)：根據資訊選擇最佳行動方案。

AI 可以大致分為兩類：

1. 狹義 AI (Narrow AI / Weak AI)：專注於執行單一特定任務，例如語音辨識、圖像識別、推薦系統。目前大多數實際應用都屬於此類。
2. 廣義 AI (General AI / Strong AI)：擁有與人類相當的廣泛認知能力，能夠理解、學習和應用知識來解決任何問題。目前仍處於理論和研究階段。

簡而言之，人工智慧就是讓機器能夠「像人一樣思考」或「像人一樣行動」的技術。

第二部分：人工智慧對企業組織帶來的價值

人工智慧為企業組織帶來了巨大的價值，主要體現在以下幾個方面：

1. 提升營運效率與自動化：
   • AI 可以自動化重複性、規則性的任務，例如資料輸入、客戶服務（聊天機器人）、生產線上的品質檢測、文件處理等。
   • 這釋放了人力資源，使其能專注於更具創造性、策略性的工作，同時也提高了處理速度和準確性。
   • 範例：銀行業利用 AI 進行自動化文件審核；

本題探討機器學習中的兩種主要學習範式：監督式學習 (Supervised Learning) 和非監督式學習 (Unsupervised Learning)，並要求舉例說明其在商業環境中的應用。

核心觀念：

• 機器學習 (Machine Learning, ML)：讓電腦系統能夠從數據中學習，而無需進行明確編程。
• 監督式學習 (Supervised Learning)：使用帶有標籤 (label) 的訓練數據進行學習。模型學習輸入特徵與輸出標籤之間的映射關係。目標是預測新數據的標籤。
  • 分類 (Classification)：預測離散的類別標籤（如：垃圾郵件/非垃圾郵件）。
  • 迴歸 (Regression)：預測連續的數值標籤（如：房價、股票價格）。
• 非監督式學習 (Unsupervised Learning)：使用沒有標籤的訓練數據進行學習。模型尋找數據中的結構、模式或關聯性。
  • 分群/聚類 (Clustering)：將數據點分組到不同的簇 (cluster) 中，使同一簇內的數據點相似，不同簇的數據點差異大。
  • 關聯規則學習 (Association Rule Learning)：發現數據集中不同項之間的有趣關聯（如：購物籃分析）。
  • 降維 (Dimensionality Reduction)：減少數據集的特徵數量，同時盡可能保留重要資訊。

詳解：

第一部分：監督式學習與非監督式學習的定義

1. 監督式學習 (Supervised Learning)：

   • 定義：在監督式學習中，訓練數據包含「輸入特徵」(input features) 和對應的「正確輸出標籤」(correct output labels)。演算法的目標是學習一個模型，該模型能夠根據輸入特徵準確地預測出輸出標籤。可以想像成有一個「老師」在提供正確答案，指導模型學習。
   • 訓練過程：模型接收成對的 (輸入, 輸出) 數據，並根據預測結果與實際標籤的差異來調整自身參數，以最小化誤差。
   • 主要任務：分類 (Classification) 和迴歸 (Regression)。

2. 非監督式學習 (Unsupervised Learning)：

   • 定義：在非監督式學習中，訓練數據僅包含「輸入特徵」，而沒有預先定義的輸出標籤。演算法的任務是自主地在數據中尋找結構、模式、規律或關聯性。沒有「老師」提供答案，模型需要自己探索數據。
   • 訓練過程：模型試圖理解數據的內在結構，例如將相似的數據點分組，或找出經常一起出現的特徵組合。
   • 主要任務：分群 (Clustering)、關聯規則學習 (Association Rule Learning)、降維 (Dimensionality Reduction)。

---

第二部分：在商業環境中的應用舉例

1. 監督式學習的商業應用：

   • 分類 (Classification) 應用：

     • 垃圾郵件過濾 (Spam Filtering)：
       • 數據：包含郵件內容、寄件者、標題等特徵的郵件，以及標示為「垃圾郵件」或「非垃圾郵件」的標籤。
       • 模型學習：學習哪些特徵組合預示著一封郵件是垃圾郵件。
       • 商業價值：幫助企業過濾掉無用或惡意的郵件，提高員工生產力，保護網絡安全。
     • 客戶流失預測 (Customer Churn Prediction)：
       • 數據：客戶的交易記錄、使用行為、人口統計資料等特徵，以及標示為「已流失」或「未流失」的標籤。
       • 模型學習：識別哪些客戶更有可能在未來流失。
       • 商業價值：企業可以主動採取措施挽留潛在流失的客戶，降低客戶獲取成本，保持營收穩定。
     • 圖像識別用於品質檢測：
       • 數據：產品圖像，以及標示為「合格」或「不合格」的標籤。
       • 模型學習：識別圖像中的缺陷。
       • 商業價值：在製造業中自動化產品品質檢測，提高檢測效率和準確性。

   • 迴歸 (Regression) 應用：

     • 房價預測 (House Price Prediction)：