115 年 國立臺灣大學生醫電子與資訊學研究所丙組《計算機概論與演算法》

作答架構

本題為名詞解釋題，建議每一小題依序說明：

1. 全名與定義
2. 核心觀念與目的
3. 應用或例子
4. 公式、性質與常見陷阱

本題不是選擇題，沒有選項需要逐一分析。

---

（1）Viterbi algorithm

核心觀念

Viterbi algorithm（維特比演算法）是用於隱馬可夫模型（Hidden Markov Model, HMM）的動態規劃演算法，用來找出「最可能的隱藏狀態序列」。

給定觀測序列 $O=(o_1,o_2,\ldots,o_T)$，目標是求：

$$\arg\max_{q_1,\ldots,q_T}P(q_1,\ldots,q_T\mid O)$$

其中 $q_t$ 表示第 $t$ 時間點的隱藏狀態。

解題方法與遞迴式

令 $\delta_t(j)$ 表示在第 $t$ 個觀測值結束於狀態 $j$ 的最佳路徑機率：

$$\delta_t(j)=\max_i\left[\delta_{t-1}(i)a_{ij}\right]b_j(o_t)$$

其中：

• $a_{ij}$：狀態 $i$ 到狀態 $j$ 的轉移機率
• $b_j(o_t)$：狀態 $j$ 產生觀測值 $o_t$ 的機率

初始化：

$$\delta_1(j)=\pi_jb_j(o_1)$$

最後取最大值，再透過 backpointer 回溯完整路徑。

應用與技巧

常用於語音辨識、中文分詞、文字標註、手寫辨識與生物資訊分析。

常見陷阱是將 Viterbi algorithm 與 Forward algorithm 混淆：前者找「最佳狀態路徑」，後者計算「所有路徑的總機率」。

---

（2）CNN

全名與核心觀念

CNN 是 Convolutional Neural Network（卷積神經網路），利用卷積運算擷取資料中的局部特徵，特別適合影像、聲音與時間序列資料。

二維卷積可表示為：

$$Y(i,j)=\sum_m\sum_n X(i+m,j+n)K(m,n)$$

其中 $X$ 是輸入，$K$ 是卷積核，$Y$ 是特徵圖。

CNN 通常包含：

• 卷積層：擷取邊緣、紋理等局部特徵
• 激活函數：引入非線性，例如 ReLU
• 池化層：降低空間尺寸與計算量
• 全連接層：進行分類或回歸

目的與應用

卷積核在不同位置共享參數，因此參數量比一般全連接網路少，也能保留平移不變性。

應用包括人臉辨識、醫學影像判讀、物件偵測、自動駕駛與語音辨識。

解題技巧

看到「局部感受野、權重共享、特徵圖、池化」即可判斷是 CNN 的核心特色。

---

（3）TPU：Tensor Processing Unit

全名與核心觀念

TPU 是 Tensor Processing Unit（張量處理單元），由 Google 設計，專門加速機器學習中的張量運算，尤其是矩陣乘法與卷積。

神經網路常見運算為：

$$Y=WX+b$$

TPU 以大量規則排列的乘加單元組成脈動陣列（systolic array），使資料能在硬體中連續流動並完成大量乘加運算。

目的與應用

TPU 的設計重點是：

• 高吞吐量
• 高能源效率
• 適合大規模神經網路訓練與推論

常用於 TensorFlow、深度學習模型訓練、影像分類與自然語言處理。

解題技巧

CPU 著重通用控制，GPU 適合大量平行運算，TPU 則特別針對張量與神經網路運算最佳化。

---

（4）NumPy

全名與核心觀念

NumPy 是 Numerical Python 的縮寫，是 Python 的數值計算函式庫，核心資料結構為多維陣列 ndarray。

它支援：

• 向量與矩陣運算
• 廣播（broadcasting）
• 線性代數
• 隨機數
• 快速陣列索引與切片

例如：

import numpy as np

a = np.array([1, 2, 3])
b = np.array([4, 5, 6])
c = a + b

結果為：

$$c=[5,7,9]$$

目的與應用

NumPy 以底層最佳化程式執行陣列運算，速度通常比逐一使用 Python 迴圈快，並且是 Pandas、SciPy、 scikit-learn 等工具的基礎。

解題技巧

NumPy 本身是數值與陣列運算工具，不等同於完整的深度學習框架。

---

（5）min-max heap

核心觀念

Min-max heap（最小－最大堆積）是一種完全二元樹，同時支援快速取得最小值與最大值。

樹的層級交替為：

• 偶數層：min level，節點值小於子孫
• 奇數層：max level，節點值大於子孫

以根節點為 min level：

• 最小值在根節點
• 最大值位於根節點的兩個子節點之一

複雜度

對含有 $n$ 個元素的 min-max heap：

• 取得最小值：$O(1)$
• 取得最大值：$O(1)$
• 插入：$O(\log n)$
• 刪除最小值：$O(\log n)$
• 刪除最大值：$O(\log n)$

應用與技巧

適合實作 double-ended priority queue（雙端優先佇列）。

判斷插入節點時，必須先依其父節點所在層級決定該節點是 min level 還是 max level，再與父節點及祖父節點比較。常見錯誤是只檢查父節點，忽略 min-max heap 的主要約束是祖父與子孫之間的關係。

---

（6）AVL tree：Adelson-Velsky and Landis tree

全名與核心觀念

AVL tree 是 Adelson-Velsky and Landis tree（阿德爾松－維爾斯基與蘭迪斯樹），是一種高度平衡的二元搜尋樹。

每個節點的 balance factor 定義為：

$$BF(v)=h(\text{left}(v))-h(\text{right}(v))$$

AVL tree 必須滿足：

$$BF(v)\in\{-1,0,1\}$$

解題方法與旋轉

插入或刪除後，若節點失衡，透過旋轉恢復平衡：

• LL：右旋
• RR：左旋
• LR：先左旋，再右旋
• RL：先右旋，再左旋

AVL tree 高度為 $O(\log n)$，因此搜尋、插入與刪除平均及最壞情況皆可維持 $O(\log n)$。

應用與技巧

AVL 適合查詢頻繁且需要嚴格平衡的資料。

判斷旋轉類型時，沿著「失衡節點到新插入節點」的方向判斷：

• 左、左是 LL
• 右、右是 RR
• 左、右是 LR
• 右、左是 RL

---

（7）dynamic programming

全名與核心觀念

Dynamic programming（動態規劃）是將大問題分解成具有重疊子問題的小問題，保存子問題答案，避免重複計算。

適用條件通常包括：

1. 最佳子結構（optimal substructure）
2. 重疊子問題（overlapping subproblems）

一般形式為：

$$DP[s]=\operatorname{opt}_{a\in A(s)} \{\,\text{cost}(s,a)+DP[\operatorname{next}(s,a)]\,\}$$

其中 $\operatorname{opt}$ 可為 $\min$、$\max$ 或加總。

解題方法

常見流程為：

1. 定義狀態 $DP$
2. 寫出狀態轉移式
3. 設定初始條件
4. 決定計算順序
5. 回溯答案

例如 0/1 背包：

$$DP[i][w]=\max \left(DP[i-1][w],DP[i-1][w-w_i]+v_i\right)$$

應用與技巧

應用於最短路徑、編輯距離、背包問題、矩陣鏈乘法與 Viterbi algorithm。

判斷技巧是觀察是否存在「相同子問題被重複解決」。單純分治若子問題互不重疊，通常不需要動態規劃。

---

（8）RFID

全名與核心觀念

RFID 是 Radio Frequency Identification（無線射頻辨識），利用無線電波讀取標籤資訊。

系統主要包含：

• RFID tag：儲存識別資料
• Reader：發射與接收無線訊號
• Backend system：管理與查詢資料

被動式標籤沒有電池，靠讀取器提供的電磁能量啟動；主動式標籤具有電池，讀取距離較長。

目的與應用

RFID 可在不需直接視線及接觸的情況下辨識物品，應用於：

• 物流追蹤
• 門禁管制
• 圖書館借還書
• 電子票證
• 零售庫存管理

解題技巧

RFID 與條碼的差異在於 RFID 不要求光學對準，且可同時讀取多個標籤；代價是硬體與隱私管理較複雜。

---

（9）Wi-Fi

全名與核心觀念

Wi-Fi 是 Wireless Fidelity 的通稱，泛指依照 IEEE 802.11 系列標準建立的無線區域網路技術。

Wi-Fi 使用無線電波在裝置與無線基地台之間傳送資料，常見媒介存取方式為 CSMA/CA（Carrier Sense Multiple Access with Collision Avoidance）。

目的與應用

Wi-Fi 用於家庭、校園、辦公室與公共場所的無線網路連線。

基本流程為：

1. 裝置搜尋基地台
2. 完成驗證與加密協商
3. 取得 IP 位址
4. 透過無線區域網路傳送封包

解題技巧

Wi-Fi 屬於區域網路技術；行動電信網路則由基地台與電信核心網路提供廣域連線。安全性方面應優先使用 WPA2 或 WPA3，避免使用開放式網路傳送敏感資料。

---

（10）IoT：Internet of Things

全名與核心觀念

IoT 是 Internet of Things（物聯網），指各種實體裝置透過網路連接，具備感測、識別、通訊、資料處理與控制能力。

典型架構為：

$$\text{感測器}\rightarrow\text{網路}\rightarrow\text{雲端或邊緣運算}\rightarrow\text{決策與控制}$$

目的與應用

IoT 將現實世界的狀態轉換為資料，再根據資料採取行動。

應用包括：

• 智慧家庭
• 智慧工廠
• 穿戴式裝置
• 智慧農業
• 遠距醫療
• 車聯網

解題技巧

IoT 不只是「裝置可以上網」，還包括資料感測、交換、分析與控制。安全問題包括弱密碼、韌體漏洞、資料外洩與大量裝置遭控制。

---

（11）stack data structure

核心觀念

Stack（堆疊）是一種後進先出（Last In, First Out, LIFO）的線性資料結構。

主要操作為：

• push(x)：將 $x$ 放入堆疊頂端
• pop()：移除並回傳頂端元素
• top() 或 peek()：查看頂端元素但不移除
• isEmpty()：判斷是否為空

若以陣列實作，通常使用指標 top 表示堆疊頂端位置。

複雜度與應用

在一般陣列或鏈結串列實作中，各項主要操作皆為：

本題考查表達式轉換為二元運算樹，以及樹的遍歷（前序、後序）。

核心觀念：

1. 表達式樹 (Expression Tree)：一種二元樹，其中葉節點是運算元 (operands)，內部節點是運算子 (operators)。
2. 前序遍歷 (Prefix Traversal)：先訪問根節點，然後遞迴訪問左子樹，最後遞迴訪問右子樹。
3. 後序遍歷 (Postfix Traversal)：先遞迴訪問左子樹，然後遞迴訪問右子樹，最後訪問根節點。

解題步驟：

1. 構建二元運算樹：
   根據運算子的優先級和括號來構建樹。

   • 最外層的運算子是 +。
   • 左邊的子表達式是 (B*(D+E)/(C-F))，右邊的子表達式是 E*(A+F)。
   • 對於左邊的子表達式 (B*(D+E)/(C-F))，主要的運算子是 / (因為 * 和 - 的結果需要被除)。
     • 左子樹是 B*(D+E)，主要運算子是 *。
       • 左子樹是 B。
       • 右子樹是 D+E，主要運算子是 +。
         • 左子樹是 D。
         • 右子樹是 E。
     • 右子樹是 C-F，主要運算子是 -。
       • 左子樹是 C。
       • 右子樹是 F。
   • 對於右邊的子表達式 E*(A+F)，主要運算子是 *。
     • 左子樹是 E。
     • 右子樹是 A+F，主要運算子是 +。
       • 左子樹是 A。
       • 右子樹是 F。

   繪製二元運算樹如下：

           +
          / \
         /   *
        /   / \
       *   E   +
      / \     / \
     B   +   A   F
        / \
       D   E
   

   請注意，在實際繪圖時，需要確保運算子和運算元的正確層級和連接。
   更精確的樹結構（基於運算優先級）：

             +
            / \
           /   \
          /     *
         /     / \
        /     E   +
       /         / \
      *         A   F
     / \
    B   +
       / \
      D   E
   

核心觀念

本題考查二元搜尋樹（Binary Search Tree, BST）的插入操作。

二元搜尋樹的定義：

• 每個節點的左子樹所有鍵值都小於該節點鍵值。
• 每個節點的右子樹所有鍵值都大於該節點鍵值。
• 插入新鍵值時，從根節點開始比較：
  • 若新鍵值較小，往左子樹走。
  • 若新鍵值較大，往右子樹走。
  • 走到空位置時，將新節點插入該處。

本題所有鍵值皆不重複，因此不需處理相等鍵值的情況。

解題方法

依照題目給定的順序，逐一從根節點開始比較並插入。

插入 8

原樹為空，$8$ 成為根節點。

8

插入 3

$3 < 8$，插入 $8$ 的左子樹。

  8
 /
3

插入 1

比較路徑：

$$1 < 8,\qquad 1 < 3$$

因此插入 $3$ 的左子樹。

    8
   /
  3
 /
1

插入 4

比較路徑：

$$4 < 8,\qquad 4 > 3$$

因此插入 $3$ 的右子樹。

    8
   /
  3
 / \
1   4

插入 9

比較路徑：

$$9 > 8$$

因此插入 $8$ 的右子樹。

    8
   / \
  3   9
 / \
1   4

插入 6

比較路徑：

$$6 < 8,\qquad 6 > 3,\qquad 6 > 4$$

因此插入 $4$ 的右子樹。

    8
   / \
  3   9
 / \
1   4
     \
      6

插入 7

比較路徑：

$$7 < 8,\qquad 7 > 3,\qquad 7 > 4,\qquad 7 > 6$$

因此插入 $6$ 的右子樹。

核心觀念

網路拓樸（network topology）描述節點與連線的配置方式，可分為實體拓樸與邏輯拓樸。實體拓樸看設備實際如何接線；邏輯拓樸看資料如何在網路中傳送。本題要求畫出至少四種拓樸，並比較其優缺點。

以下以常見的區域網路拓樸為例，說明匯流排、星狀、環狀、網狀與樹狀拓樸。

解題方法

作答時，先畫出節點與連線關係，再依序比較每種拓樸的布線需求、擴充難度、故障影響範圍及成本。這些特性正是辨認各拓樸優缺點的依據。

1. 匯流排拓樸（Bus）

所有節點共用同一條主幹線，資料沿主幹線傳送。

終端器                         終端器
  │                              │
──┴────┬────────┬────────┬──────┴──
       │        │        │
      [A]      [B]      [C]

優點：

• 所需線材較少，建置成本低。
• 網路架構簡單，適合節點數量較少的環境。

缺點：

• 主幹線故障會使整段網路受到影響。
• 節點增加時，共用媒介上的競爭與碰撞機率提高，效能下降。
• 故障位置不易定位；新增或移除節點也可能影響整條主幹線。
• 主幹線兩端需設置終端器，以避免訊號反射。

2. 星狀拓樸（Star）

每個節點各自連到中央設備，例如交換器或集線器。

          [A]
           │
[B] ─── [交換器] ─── [C]
           │
          [D]

優點：

• 新增或移除節點容易，擴充性佳。
• 單一連線故障通常只影響該連線上的節點，容易定位問題。
• 使用交換器時，各節點可獨立傳送資料，通常比共用主幹線有效率。

缺點：

• 中央設備故障會使整個網路停止運作。
• 每個節點都要各自連到中央設備，線材與佈線成本較高。
• 網路規模受中央設備的連接埠數量與效能限制。

3. 環狀拓樸（Ring）

節點依序相連，首尾接合形成封閉環路；資料通常沿環路傳送。

       [A] ─── [B]
        │       │
       [D] ─── [C]

核心觀念

本題考查「定點二補數表示法」。處理小數時，必須先確認：

• 整數部分轉換為二進位。
• 小數部分轉換為二進位。
• 指定小數位數後，再以二補數表示負數。
• 二補數的位元寬度必須足以容納數值。

題目未指定位元寬度與小數位數。採用能精確表示此數值的最小格式：使用 $3$ 個小數位元，因此採用 $9$ 位元二補數格式。

---

解題方法

1. 將 $23.875$ 轉成二進位

整數部分：

$$23_{10}=10111_2$$

小數部分：

$$0.875=\frac{7}{8}=0.111_2$$

因此：

$$23.875_{10}=10111.111_2$$

由於是有號二補數，正數前方補上 $0$，形成 $9$ 位元：

$$+23.875=010111.111_2$$

其中小數點右側有 $3$ 位。

2. 對正數取二補數

先將每一位元反相：

$$010111.111 \longrightarrow 101000.000$$

再加 $1$。由於小數位固定為 $3$ 位，這裡的 $1$ 代表 $0.001_2$：

$$101000.000+0.001=101000.001$$

所以：

$$-23.875=101000.001_2$$

3. 以放大倍率驗算

因為有 $3$ 個小數位元，先將數值乘以 $2^3=8$：

核心觀念

Fibonacci 數列定義如下：

$$F(0)=0,\qquad F(1)=1$$

對於 $N\ge 2$：

$$F(N)=F(N-1)+F(N-2)$$

本題要求使用遞迴（recursion）撰寫，因此函式必須包含：

1. 基底條件：$N=0$ 或 $N=1$ 時直接回傳答案。
2. 遞迴關係：將 $F(N)$ 拆成 $F(N-1)+F(N-2)$。

解題方法

函式先處理兩個基底情況，再依 Fibonacci 定義遞迴計算：

int Fibonacci(N)
    if N == 0
        return 0

    if N == 1
        return 1

    return Fibonacci(N - 1) + Fibonacci(N - 2)

若題目要求輸入 $N$ 後印出結果，可搭配主程式：

read N
print Fibonacci(N)

完整流程為：

int Fibonacci(N)
    if N == 0
        return 0

    if N == 1
        return 1

    return Fibonacci(N - 1) + Fibonacci(N - 2)


read N
print Fibonacci(N)

以 $N=5$ 為例：

$$\begin{aligned} F(5) &=F(4)+F(3)\\ &=(F(3)+F(2))+(F(2)+F(1))\\ &=5 \end{aligned}$$

核心觀念

本題考查「模型參數數量 × 每個參數所需儲存容量」的 GPU VRAM 估算。

計算公式為：

$$\text{VRAM}=\text{參數數量}\times\text{每個參數的位元數}$$

由於 $1$ byte $=8$ bits，也可寫成：

$$\text{VRAM（bytes）} = \frac{\text{參數數量}\times\text{每個參數的位元數}}{8}$$

題目中的模型共有 $6$ billion，即：

$$6\text{ billion}=6\times 10^9$$

此計算只估算模型權重本身，未包含 CUDA、模型執行暫存空間、KV cache、批次大小及其他額外記憶體。

解題方法

1. FP32

FP32 每個參數使用 $32$ bits，也就是 $4$ bytes。

$$6\times10^9\times\frac{32}{8} = 6\times10^9\times4 = 24\times10^9\text{ bytes}$$

因此：

$$\boxed{24\text{ GB}}$$

若以二進位單位 GiB 表示：

$$\frac{24\times10^9}{2^{30}} \approx 22.35\text{ GiB}$$

2. INT8

INT8 每個參數使用 $8$ bits，也就是 $1$ byte。

$$6\times10^9\times\frac{8}{8} = 6\times10^9\text{ bytes}$$

因此：

$$\boxed{6\text{ GB}}$$

換算成 GiB：

$$\frac{6\times10^9}{2^{30}} \approx 5.59\text{ GiB}$$

3. INT4

INT4 每個參數使用 $4$ bits，也就是每個參數半個 byte。

本題考查軟體開發生命週期 (Software Development Life Cycle, SDLC) 的基本知識，要求列出其七個階段。

核心觀念：
軟體開發生命週期 (SDLC) 是一個結構化的流程，用於規劃、創建、測試和部署高品質的軟體系統。它將軟體開發過程劃分為一系列離散的階段，每個階段都有特定的目標和交付物。不同的 SDLC 模型（如瀑布模型、敏捷模型）可能在階段的劃分和順序上略有差異，但核心概念是相似的。

七個階段的 SDLC 模型：
常見的 SDLC 模型通常包含以下幾個關鍵階段。這裡列出的七個階段是比較詳盡的劃分：

1. 規劃 (Planning)：

   • 目的：確定專案的可行性、範圍、目標、資源需求、時間表和預算。
   • 活動：需求收集、可行性研究、專案規劃、風險評估。
   • 交付物：專案計劃書、可行性報告。

2. 需求分析 (Requirements Analysis)：

   • 目的：詳細定義和記錄系統的功能性 (functional) 和非功能性 (non-functional) 需求。
   • 活動：與客戶溝通、訪談、問卷調查、案例研究，產生詳細的需求規格。
   • 交付物：需求規格說明書 (SRS - Software Requirements Specification)。

3. 系統設計 (System Design)：

   • 目的：基於需求規格，設計軟體系統的架構、模組、介面、資料庫結構等。
   • 活動：高階設計 (High-level Design - HLD)，定義系統架構；低階設計 (Low-level Design - LLD)，定義模組細節。
   • 交付物：設計規格說明書 (SDS - System Design Specification)，包括架構圖、資料庫模式、模組介面定義。

4. 實作/編碼 (Implementation/Coding)：

   • 目的：根據設計規格，編寫實際的程式碼。
   • 活動：程式設計、單元測試 (unit testing) 的編寫。

本題考查雲端運算平台及其服務的知識，要求列出至少四個主要雲端平台，並詳細說明它們之間的差異、優點和缺點。

核心觀念：
雲端運算 (Cloud Computing) 提供可擴展的計算資源（如伺服器、儲存、資料庫、網路、軟體、分析和智慧）透過網際網路（雲端）按需交付。主要的雲端服務提供商（Hyperscalers）提供廣泛的服務，以不同的模型（IaaS, PaaS, SaaS）滿足各種需求。

主要的雲端平台：
全球三大雲端服務提供商是 Amazon Web Services (AWS)、Microsoft Azure 和 Google Cloud Platform (GCP)。此外，還有其他重要的平台如 Alibaba Cloud, IBM Cloud, Oracle Cloud 等。這裡我們列出四個主流平台進行比較。

---

1. Amazon Web Services (AWS)

• 簡介：由亞馬遜公司推出，是市場上最早、最成熟的雲端平台之一，擁有最廣泛的服務和最大的市佔率。
• 服務範例：
  • IaaS (Infrastructure as a Service): EC2 (虛擬伺服器), S3 (物件儲存), VPC (虛擬私有雲)。
  • PaaS (Platform as a Service): RDS (關聯式資料庫), Lambda (無伺服器運算), EKS (Kubernetes 服務)。
  • SaaS (Software as a Service): WorkSpaces (虛擬桌面)。
• 優點：
  • 最全面的服務組合：提供最廣泛的服務種類，幾乎能滿足所有需求。
  • 市場領導者與成熟度：技術成熟，生態系統龐大，社群支援豐富，有大量第三方工具和整合。
  • 彈性與可擴展性：極高的彈性和隨需擴展能力。
  • 全球化佈局：擁有最多的區域 (Regions) 和可用區域 (Availability Zones)，提供最佳的地理分佈和容災能力。
• 缺點：
  • 複雜性：服務種類繁多，對於新手可能較難掌握和管理。
  • 成本管理：複雜的計費模式，若管理不當，成本可能快速增長。
  • 特定服務鎖定 (Vendor Lock-in)：部分 AWS 特有的服務可能難以遷移到其他平台。

---

2. Microsoft Azure

• 簡介：由微軟公司推出，是市場上的第二大雲端平台，特別擅長與微軟現有的企業級產品（如 Windows Server, Office 365, Active Directory）整合。
• 服務範例：
  • IaaS: Virtual Machines, Blob Storage, Virtual Network.
  • PaaS: Azure SQL Database, Azure Functions, Azure Kubernetes Service (AKS).
  • SaaS: Microsoft 365 (部分整合)。
• 優點：
  • 企業級整合：對現有微軟企業客戶而言，與其現有 IT 環境的整合非常順暢，便於遷移。
  • 混合雲能力：Azure Arc 等服務使其在混合雲（公有雲與私有雲結合）策略上表現出色。
  • 開發者工具：與 Visual Studio, .NET 等微軟開發工具鏈整合良好。
  • 快速成長的服務範圍：服務種類不斷增加，特別是在 AI 和大數據領域。
• 缺點：
  • 文件與文件更新：有時文件更新不及時，或存在一些不一致之處。
  • 複雜性：服務種類眾多，複雜性也較高。
  • 部分服務的成熟度：相較於 AWS，某些新服務的成熟度和穩定性可能稍遜一籌。

---

3. Google Cloud Platform (GCP)

• 簡介：由 Google 公司推出，以其在數據分析、機器學習、容器化 (Kubernetes) 和開源技術方面的領導地位而聞名。
• 服務範例：
  • IaaS: Compute Engine, Cloud Storage, Virtual Private Cloud.
  • PaaS: BigQuery (數據倉儲), Cloud Functions, Google Kubernetes Engine (GKE).
  • SaaS: Google Workspace (部分整合)。
• 優點：
  • 數據分析與機器學習：在 BigQuery、AI Platform、TensorFlow 等領域具有強大優勢，是 AI/ML 應用的首選之一。
  • 容器化技術：GKE (Google Kubernetes Engine) 是業界領先的託管 Kubernetes 服務。
  • 開源技術支持：積極推動和支持開源專案，如 Kubernetes。
  • 網路效能：Google 擁有全球頂尖的網路基礎設施，提供高效能的全球網路服務。
  • 定價創新：提供創新的定價模式，如持續使用折扣 (Sustained Usage Discounts)。
• 缺點：

核心觀念

Kruskal 演算法用來尋找最小生成樹：在連通圖中選出連接所有頂點、且不形成環的邊，使邊權重總和最小。若圖有 $n$ 個頂點，生成樹必須恰有 $n-1$ 條邊。

演算法將所有邊依權重由小到大排序，逐一考慮：若加入某邊不會形成環，就選取；若會形成環，就略過。判斷兩端是否已連通，可用並查集（Union-Find）。

解題方法

圖中頂點為 $A,B,C,D,E,F,G$，共 $7$ 個，因此最小生成樹需要選取 $6$ 條邊。依權重排序如下：

權重	邊	處理結果
5	$AD$	選取
5	$CE$	選取
6	$DF$	選取
7	$AB$	選取
7	$BE$	選取
8	$BC$	略過，會形成環
8	$EF$	略過，會形成環
9	$BD$	略過，會形成環
9	$EG$	選取
11	$FG$	不必再考慮
15	$DE$	不必再考慮

逐步看連通情形：