計算機應用數學-離散數學(和邏輯學)

前敘

筆記內容著重於，計算機與人工智慧領域所應用的數學，目的為快速導讀數理重點脈絡及公式，類似於直式的心智圖

目錄

筆記目前整理三個部分

1. 計算機應用數學-微積分 (研究連續變化、累積與極限現象的數學)
2. 計算機應用數學-線性代數 (研究向量、矩陣與線性變換的結構與操作)
3. 計算機應用數學-離散數學(和廣義邏輯學) (研究離散結構的數學，為計算理論與邏輯基礎)

程式函數與數學

程式中陣列資料，或是資料集都是**集合論(set theory)**的表現

例如: 一個陣列物件視為一個集合(set)，裡面的資料視為元素(object)

U = [1, 2, 3, 4, 5]

累加器

程式迴圈連續加法為$\sum$的表現

例如:

將U = [1, 2, 3]陣列元素相加，i=起始位子(二進制是0為起點)，3=終點目標，，

$$\sum_{i=1}^{3} U_i = 1 + 2 + 3 = 6$$

let Sum = 0;
for (let i = 0; i < U.length; i++) {
    Sum += U[i];  // 將每個元素累加
}

離散數學

Σ（總和，Summation）

從 $i=m$ 加到 $i=n$

$$\sum_{i=m}^{n} a_i = a_m + a_{m+1} + \cdots + a_n$$

Π（乘積，Product）

從 $i=m$ 乘到 $i=n$

$$\prod_{i=m}^{n} a_i = a_m \times a_{m+1} \times \cdots \times a_n$$

集合論(set theory)

集合與元素(set and object)

$$A = \{1, 2\}, B = \{1, 2\}$$

表示符號

$N$ 自然數集合

自然數集合可以表示為：

$$\mathbb{N} = \{0, 1, 2, 3, \dots\}$$

$Z$ 整數集合

整數集合包括所有的正整數、負整數和零：

$$\mathbb{Z} = \{\dots, -3, -2, -1, 0, 1, 2, 3, \dots\}$$

$R$ 實數集合

實數集合包括所有的有理數和無理數：

$$\mathbb{R} = \text{所有可表示的實數}$$

$U$ 全集

代表 全集，即在特定問題範疇內，包含所有可能元素的集合。

$| A |$

A 集合的元素各數

$$A = \{0, 1\} , | A |= 2$$

$∀$ （Universal Quantifier 全稱量詞）

唸作「For all」，表示“對所有”或“對每一個”某個範圍內的元素均成立。

$$\forall x \in \mathbb{N}, \quad x + 1 > x$$

$|$ (Such That 或 Divides)

用來表示“滿足條件”的元素

例如: 從所有實數中，挑出那些滿足 $x > 0$ 這個條件的元素，組成集合 $A$

$$A = \{x \in \mathbb{R} \mid x > 0\}$$

$P(A)$ (Power Set)

給定集合 A，幂集 P(A) 是 A 的所有的子集的集合，包括空集和 A 本身

$$A = \{1, 2\}, \quad P(A) = \{\emptyset, \{1\}, \{2\}, \{1, 2\}\}$$ $$P \iff Q$$

---

子集關係

$\in$ (Element of set)

表示單一元素是某集合的成員

元素屬於集合：

$$x \in A$$

元素不屬於集合：

$$y \notin A$$

$\subseteq$ 子集（Subset）

子集是寬鬆的定義，表示集合 $A$ 的所有元素都在集合 $B$ 中，可以等於 $B$：

$$\emptyset \subseteq A, \quad \{a\} \subseteq A, \quad \{b\} \subseteq A, \quad \{a, b\} \subseteq A$$ $$A \subseteq B$$

---

$\subset$ 真子集（Proper Subset）

真子集是嚴謹的定義，表示集合 $A$ 的所有元素都在集合 $B$ 中，且 $A \neq B$：

$$A \subset B \quad \text{當 } A \neq B$$

• 若 $A = B$，則不成立：

$$A \not\subset B$$

---

集合操作

使用例子

$$A = \{1, 2, 3\}, \quad B = \{3, 4, 5, 6\}$$

$A \cup B$ 聯集

聯集包含所有屬於集合 A 或集合 B 的元素。

$$A \cup B = \{x \mid x \in A \text{ or } x \in B\}$$ $$A \cup B = \{1,2,3,4,5,6\}$$

$A \cap B$ 交集

交集包含所有同時屬於集合 A 和集合 B 的元素。

$$A \cap B = \{x \mid x \in A \text{ and } x \in B\}$$ $$A \cap B = \{ 3\}$$

$A - B$ 差集

差集包含所有屬於集合 A 但不屬於集合 B 的元素。

$$A - B = \{x \mid x \in A \text{ and } x \notin B\}$$ $$A - B = \{1,2\}$$

$A^c$ 補集

補集包含全集中$U$不屬於集合 A 的所有元素。

$$A^c = \{x \mid x \notin A\}$$ $$U = \{1, 2, 3, 4\} ， A = \{1, 2\}，則 A^c = \{3, 4\}$$

排列組合

排列

考慮順序，重n個元素中排列進k個位子

1. 不重複選擇排列

$${\displaystyle P_{k}^{n}={\frac {n!}{(n-k)!}}}$$

1. 可重複選擇排列

$$\displaystyle n^{k}$$

組合

考慮可能的組合，重n個元素中排列進k個位子

$${\displaystyle C_{k}^{n}=\frac{n!}{k!(n-k)!}}$$ $${\displaystyle C_{k}^{n}= {n \choose k}= \frac {P_{k}^{n}}{k!}= \frac{\frac{n!}{(n-k)!}}{k!}= \frac {n!}{k!(n-k)!}}$$

統計學

Z-Score Scaling

是一個統計學方法，衡量資料離平均值有多少差距方式，如果原始資料接近常態分佈(standard deviations)，大部分 z-score 值會落在 $[-4, +4]$ 區間內，均值為 0、標準差為 1。 $z = \frac{x - \mu}{\sigma}$ 其中：

• $x$：原始資料點

• $\mu$：平均值

• $\sigma$：標準差

一般來說，$[-2, +2]$ 區間以外可以視為極端值

連續資料的平均值（$\mu$）

$$\mu = \frac{1}{n} \sum_{i=1}^{n} x_i$$

標準差（$\sigma$）

標準差是用來衡量一組數據「離平均值有多分散」的一個數值，愈大表示越分散。

$$\sigma = \sqrt{\frac{1}{n-1} \sum_{i=1}^{n} (x_i - \mu)^2}$$

• $x_i$：第 $i$ 個數據點

• $\mu$：平均值（mean）

• $N$：資料點個數

• $\sigma$：標準差

中位數（Median）

描述：

• 中位數是資料排序後的中間值。
• 在資料偏態或有極端值時，比平均數更穩健。
• 有 50% 的資料小於等於中位數，50% 大於等於中位數。

四分位數（Quartiles）

描述：

• 四分位數將資料分為四等份。
• 常見的三個分界點為：
  • 第一四分位數 $Q_1$：第 25 百分位
  • 第二四分位數 $Q_2$：第 50 百分位 = 中位數
  • 第三四分位數 $Q_3$：第 75 百分位
• 四分位距（Interquartile Range, IQR） 定義如下：

$$\text{IQR} = Q_3 - Q_1$$

• 四分位法常用於判斷離群值（如下）：
  • 離群值定義為低於 $Q_1 - 1.5 \cdot \text{IQR}$ 或高於 $Q_3 + 1.5 \cdot \text{IQR}$

常態分佈（Normal Distribution）

描述：

• 常態分佈是一種對稱的鐘形曲線，具有以下特性：
  • $\mu = \text{mean} = \text{median} = \text{mode}$
  • 大多數資料集中在平均值附近

經驗法則（Empirical Rule）：

• 約 68% 的資料位於區間 $\mu \pm \sigma$
• 約 95% 的資料位於區間 $\mu \pm 2\sigma$
• 約 99.7% 的資料位於區間 $\mu \pm 3\sigma$

---

機率論（Probability Theory）

普通機率（Ordinary Probability）

事件 $A$ 發生的機率是所有可能結果中，屬於 $A$ 的結果比例 $0 \le P(A) \le 1$

$$P(A) \in [0,1]$$

條件機率：在 $B$ 發生的條件下 $A$ 發生的機率 $P(A \mid B)$

聯合機率 (Joint Probability)

兩個或多個隨機變數同時發生的機率 $p(x,y)$

邊緣化 (Marginalization)

從聯合機率分布中「消去」一個或多個變數，得到剩下變數的機率分布 $P(X = x) = \sum_y P(X = x, Y = y)$

---

條件機率（Conditional Probability）

在事件 $B$ 已經發生的前提下，事件 $A$ 發生的機率：

$$P(A \mid B) = \frac{P(A \cap B)}{P(B)}, \quad P(B) > 0$$

• $P(A \cap B)$：$A$ 與 $B$ 同時發生的機率（交集機率）
• $P(B)$：$B$ 發生的機率
• $P(A \mid B)$：在 $B$ 發生的情況下，$A$ 發生的比例

如果 $B$ 是必然事件，$P(B) = 1$：

$$P(A \mid B) = \frac{P(A \cap B)}{1} = P(A \cap B)$$

獨立事件（Independent Events）

事件 $A$ 與 $B$ 獨立

$$P(A \cap B) = P(A) \cdot P(B)$$

$A$ 發生與否不影響 $B$ 發生的機率

條件機率形式：

$$P(A \mid B) = \frac{P(A \cap B)}{P(B)} = \frac{P(A)\cdot P(B)}{P(B)} = P(A)$$

而事件B的發生機率為

$$P(B \mid A) = P(B)$$