--- tags: computer science, math --- # 資訊科學的高中數學 <font size = -1>(High School Math in Computer Science)</font> - 本文整理資訊科學 (computer science) 中會使用到的中學數學 (特別是高中數學)，適合++需要快速回顧的學員++或者++想超前學校進度的學員++。保守初估實體教室上課需花費約三小時。 - 數學的目的是透過**簡化問題**的方式了解世界，並非要用抽象的符號來困惱學生。 - 抽象的工具才有一般性，因此才能**重複使用**，能夠以一招打天下，做到見山不是山、見水不是水，培養看透外表、潛藏在背後的模式 (pattern)。 - 因此對我個人而言，**數學是工具**，如同時下熱門的程式語言，有需求的時候才回頭補齊數學也不遲，唯一要考慮的代價就是成長曲線有可能比較平緩：年紀小的學員普遍吸收新知與計算能力較成年人來得強，可以有較陡峭的成長曲線。<img src = "https://hackmd.io/_uploads/Bk5u9QG59.png" height = 200px style="float:right"/> - 本文內容的預備知識： - 基礎算術能力：數數、四則運算、九九乘法、交換律、結合律、平方運算、根號運算。 - 基礎幾何能力，例如：圓形、三角形等，並能夠計算周長、面積等。 - 基礎代數能力，例如：$x = 1$ 且 $y = x + 1$，則 $y = 2$。 - 基礎邏輯能力，例如：且 (and)、或 (or) 的定義。 - 如果想要快速具備上述基礎能力，可以參考日劇[東大特訓班](https://zh.m.wikipedia.org/zh-tw/%E6%9D%B1%E5%A4%A7%E7%89%B9%E8%A8%93%E7%8F%AD)的訓練方式。 - **熟能生巧，勤能補拙**。學程式語言、演算法、做專案亦如是。甚至任何一種專業都需要這段量變產生質變的過程。 - 中國人的說法也可以參考：**量變產生質變。** - 台灣現行課綱可於此網頁取得：[教育部數學領域課程手冊](https://www.naer.edu.tw/upload/1/16/doc/2069/%E6%95%B8%E5%AD%B8%E9%A0%98%E5%9F%9F%E8%AA%B2%E7%A8%8B%E6%89%8B%E5%86%8A(%E5%AE%9A%E7%A8%BF%E7%89%88).pdf)、[國高中數學學習清單](https://www.learnmode.net/knowledge/version?p=36) - 以台大資訊系為例，大學部的基礎數學課程有微積分、線性代數、[離散數學](https://www.csie.ntu.edu.tw/~lyuu/dm.html)、機率論等，近年還有開設工程數學，包含微分方程式、傅立葉分析、拉普拉斯轉換和複變分析等工程領域通用的數學。 ## **集合論** ### ++集合++ #### 定義 - 元素 $x$ <font color = "red">屬於</font>集合 $A$，記作為 $x\,{\color{red}\in}\,A$。 - 例 1：假設一枚硬幣有面朝上 $(h)$ 與面朝下 $(t)$ 兩種可能。則擲一次硬幣的結果 ($\Omega$，讀作 omega) 為 $\Omega = \{\,h, t\,\}$。此時我們可以說 $h \in \Omega$ 和 $t \in \Omega$。 <img src = "https://hackmd.io/_uploads/HyNUIObc9.png" height = 50px style="float:right"/> - 例 2：交通號誌燈號有三種狀態：紅 $(r)$、黃 $(y)$、綠 $(g)$。令 $\Omega' = \{\,r、y、g\,\}$。白燈 $w$ 不是交通號誌燈號的一種可能，記作 $w \notin \Omega'$。 - 例 3：假設 $A = \{\,x \,|\, 90 \leq x \leq 100,\, x \in \mathbb{N}\,\}$。則我們可以知道 $90, 91, \ldots,100 \in A$，但 $90.5 \notin A$ 且 $101 \notin A$。 - $B$ 是 $A$ 的子集合，記作為 $B \subset A$。 - 例 1：$\{\,r, g\,\} \subset \Omega'$，但 $\{\,r, w\,\} \not\subset \Omega'$。 - 例 2：假設 $A = \{\,x \,|\, 90 \leq x \leq 100,\, x \in \mathbb{N}\,\}$，$B = \{\,90, 91, \ldots,95\,\}$，$C = \{\,80, 91, \ldots,100\,\}$。則 $B \subset A$ 但 $C \not\subset A$。 - 若集合內沒有任何元素，則稱之為空集合，記作為 $\phi$。 - 注意，$\phi$ 是任何集合的子集合，尤其是 $\phi \subset \phi$。 - $A$ 的大小 (基數) 是指集合的元素個數，記作為 $|\,A\,|$。 - 例 1：假設 $A = \{\,a,b,c\,\}$。則 $|\,A\,| = 3$。 - 例 2：$|\,\phi\,| = 0$。 - 假設 $A = \{\,a, b, c\,\}$。則 $A$ 的冪集 (power set) 有 $2 ^ {|\,A\,|} = 8$ 個子集合：$\phi$、$\{\,a\,\}$、$\{\,b\,\}$、$\{\,c\,\}$、$\{\,a, b\,\}$、$\{\,a, c\,\}$、$\{\,b, c\,\}$、$\{\,a, b, c\,\}$。 ### ++集合的運算++ - 假設 $A = \{\,a, b, c, d\,\}$ 與 $B = \{\,a, b, e, f\,\}$。 #### 宇集 (universal set) - 宇集代表一個問題所有的可能性 (所有的元素)，常記作為 $U$。 #### 交集 (intersection) - $A$ 和 $B$ 的交集為 $\{\,a, b\,\}$，記作為 $A \cap B$。 #### 聯集 (union) - $A$ 和 $B$ 的聯集為 $\{\,a, b, c, d, e, f\,\}$，記作為 $A \cup B$。 #### 差集 (difference) - $A$ 差集 $B$ 的結果為 $\{\,c, d\,\}$，記作為 $A\,\backslash\,B$ 或者 $A - B$。 - $B$ 差集 $A$ 的結果為 $\{\,e, f\,\}$，記作為 $B\,\backslash\,A$ 或者 $B - A$。 #### 對稱差集 (symmetric difference) - 取 $A$ 和 $B$ 對稱差集為 $\{\,c, d, e, f\,\}$，記作為 $A\,\Delta\,B$。 - 由此運算可發現，$A\,\Delta\,B = B\,\Delta\,A$。此性質稱之為<font color = "red">可互換</font> (commutative)。 - 其他的可交換操作如：$A \cap B = B \cap A$；$A \cup B = B \cup A$。 - 但像是差集為不可交換順序。 - $A\,\Delta\,B$ 等價於 $A \cup B - A \cap B$。 (Why?) - 在 Boolean algebra 中，對稱差集相當於互斥或 (exclusive or)。 #### 補集 (complement) - 假設 $C = \{\,g, h\,\}$ 且 $U = A \cup B \cup C$。 - 則 $A$ 的補集為 $\{\,e, f, g, h\,\}$，記作為 $\overline{A}$。 - 則 $B$ 的補集為 $\{\,c, d, g, h\,\}$，記作為 $\overline{B}$。 ### ++文氏圖++ <center> ![](https://hackmd.io/_uploads/HyOJUTx59.png =250x) </center> ### ++狄摩根定律++ <center> ![](https://hackmd.io/_uploads/Bk4fUpg95.png =400x) 請根據 $A, B$ 集合找出 $\overline{A \cup B} = \overline{A} \cap \overline{B} = ?$ 與 $\overline{A \cap B} = \overline{A} \cup \overline{B} = ?$。 </center> ### ++邏輯++ - 考慮 $X$ 與 $Y$ 兩個布林變數 (Boolean variable)，則其真值表 (Truth table) 如下： | $X$ | $Y$ | $\overline{X}$ | $X$ AND $Y$ | $X$ OR $Y$ | $X$ XOR $Y$ | | --- | --- | -------------- | ----------- | ---------- | ----------- | | F | F | T | F | F | F | | F | T | T | F | T | T | | T | F | F | F | T | T | | T | T | F | T | T | F | AND 可以用 $\&,\,\&\&$ 或者 $\times$ 替換；OR 可以用 $|,\,||$ 或者 $+$ 替換；XOR (互斥或) 可以用 $\wedge$ 或者 $\oplus$ 替換。 - 問：若 P 則 Q 的等價敘述 (equivalence) 是? ### ++映射 (mapping) & 函數 (function)++ <center> ![](https://hackmd.io/_uploads/H1Rukybqc.png =300x) </center> - 假設 $f$ 為使 $A$ 中元素 $x$ 映射到 $B$ 中的元素 $y$ 的**函數**，記作為 $f: x \in A \mapsto y \in B$，或者 $y = f(x)$。 - 例 1：販賣機有三個按鈕，編號分別是 $1, 2, 3$，選定後分別對應到紅茶、綠茶、奶茶。則我們可以說販賣機 : $\{\,1, 2, 3\,\} \mapsto \{\,紅茶, 綠茶, 奶茶\,\}$。 - 例 2：考慮 $0 \leq x \leq 1$ 且 $y = x + 1$，則 $1 \leq y \leq 2$，記作為 $y = f(x) = x + 1$。我們說 $f$ 是一個 $x$ 的函數，將 $0 \leq x \leq 1$ 映射到 $1 \leq y \leq 2$。 - 此時，我們稱 $A$ 為**定義域**，$B$ 為**值域**。若 $f: x \in A \mapsto y \in B' \subset B$，且 $A$ 中的元素沒有對應到 $B - B'$，則稱 $B'$ 為對應域。一般而言，$B = B'$。 - 假設 $f : x \in A \mapsto y \in B$ 且 $g : y \in B \mapsto z \in C$。則**合成函數** $g(f(x)) = g(y) = z$。 - 例：令 $f(x) = x^2$ 與 $g(x) = x + 1$，則 $g(f(1)) = 2$ 而 $f(g(1)) = 4$。 ==無交換律== - 假設 $f : x \in A \mapsto y \in B$，若存在一個函數使得 $y \in B \mapsto x \in A$，則稱之為**反函數**，記作為 $f^{-1}$。 - 注意，這個定義並不完整，但是說法上比較容易想像這個概念。 - 例 1：$f^{-1}(f(x)) = x$。 - 從這個關係來看，可以逆推反函數成立的條件是**一對一**且**映成** (值域內所有元素都能對應到定義域的某元素)。 - 例 2：指數與對數互為反函數，如下圖所示。特別可以留意的是，兩個函數以 $y = x$ 這條直線作鏡射 (mirroring)。 <center> ![](https://hackmd.io/_uploads/HJVwy4F3o.png =400x) </center> ### ++現代集合論++ <img src = "https://hackmd.io/_uploads/rJNuy0gq9.png" height = 300px style="float:right"/> - 請參考：https://zh.wikipedia.org/wiki/集合論 #### 康德爾集合 (Cantor Set) ![](https://hackmd.io/_uploads/S1SogAlq5.png =500x) - 康德爾集合為在 $0-1$ 數線上，挖掉中間 $\frac{1}{3}$ 的部分，然後再從剩下的線段，重複挖掉該片段的 $\frac{1}{3}$，如上圖所示。 - 有趣的是，此線段是一個非空集合 (因為還有剩下類似 $\frac{1}{3}, \frac{2}{3}$ 等等之類的有理數)，但是集合的大小 (總長度) 為零。 - 這個結果在現代機率論上面是一個重要的結果：**該事件的機率為零，不代表該事件不會發生**。 <img src = "https://hackmd.io/_uploads/Hyf32-z59.png" height = 250px style="float:right"/> ## **代數** ### ++基本算術++ #### 數字系統 - **自然數** (natural number) 或稱正整數，記作 $\mathbb{N}$。 - **整數** (integers) 包含自然數、$0$ 與負整數，記作 $\mathbb{Z}$。 - **有理數** (rational number) 包含整數與可以透過兩個整數相除 (分母不為零) 表示的非整數，記作 $\mathbb{Q}$。 - **實數** (real number) 包含有理數與非有理數 (例如：$\pi$、$\sqrt{2}$ 等)，記作 $\mathbb{R}$。 - 一般而言，沒有特別說明的話，我們討論的數字都是實數。 - **複數** (complex number) 包含實數與帶虛數 ($i = \sqrt{-1}$) 的數，記作 $\mathbb{C}$。 #### 四則運算 - 假設 $x, y \in \mathbb{R}$，則下表為四則運算的結果： | 運算子名稱 | 符號 | 案例 | 注意事項 | | ---------- |:------------:|:----------------------------------------- | ----------------------------------------- | | 加法 | $x + y$ | $1 + 2 = 3$ | 基本運算。 | | 減法 | $x - y$ | $3 - 4 = 3 + (-4) = -1$ | 減法可以視作為加上一個負數 (加法反元素)。 | | 乘法 | $x \times y$ | $5 \times 6 = 5 + 5 + 5 + 5 + 5 + 5 = 30$ | 基本運算。 | | 除法 | $x\,/\, y$ | $6\,/\,3 = 6 \times \dfrac{1}{3} = 2$ | 除法可以視作為乘上一個倒數 (乘法反元素)。 | | 餘數 | $x\,\%\,y$ | $7\,\%\,3 = 1$ | 基本運算。 | - 四則運算具備**交換律**與**結合律**。 - 例 1：$a \times (b \times c) = (a \times b) \times c$。 - 例 2：$a \times (b + c) = a \times b + a \times c$。 - 在資訊系大一下有一門數學課稱作為**離散數學**，其中幾章會討論到代數 (環 ring、群 group、體 field)。以下為一些可以先知道的事實： - $0$ 為加法單位元素，任何數字加上 $0$ 都是原來的數字，例如：$x + 0 = x$。 - 對應到撰寫程式中，如果要對累加的變數初始化，則通常是設定為 0。 - $1$ 為乘法單位元素，任何數字乘上 $1$ 都是原來的數字，例如：$x \times 1 = x$。 - 對應到撰寫程式中，如果要對累乘的變數初始化，則通常是設定為 1。 - 0 在乘法運算中是<font color = "red">毀滅</font>性元素。 #### 連加與連乘積 - 例 1：$\sum\limits_{i = 1}^{n} i = 1 + 2 + 3 + \cdots + n = \dfrac{n(n + 1)}{2}$。 ==高斯的梯形公式== - 例 2：$\prod\limits_{i = 1}^{n} i = 1 \times 2 \times 3 \times \cdots \times n = n!$。 ==$n!$ 稱為 $n$ 階乘== - 例 3：$\sum\limits_{i = 1}^{n} i^2 = 1^2 + 2^2 + 3^2 + \cdots + n^2 = \dfrac{n(n + 1)(2n+1)}{6}$。 - 以上的等式可以透過**數學歸納法** (mathematical induction) 證明之。 - 請參考：https://en.wikipedia.org/wiki/Mathematical_induction #### 無窮 (Infinity) - 無窮可以是無窮大、無窮小、無窮多等等的概念，記作為 $\infty$，直覺是**無止盡的逼近**。 - 例 1：在除法運算中，若分母為零，則計算結果為無窮大。 - 例 2：當 $x \rightarrow 0$，則 $\dfrac{1}{x} \rightarrow \infty$。 - 例 3：當 $x \rightarrow \infty$，則 $\dfrac{1}{x} \rightarrow 0$。 - 例 4：$\sum\limits_{i = 1}^{\infty} i = -\dfrac{1}{12}$。 - 任何數字與無窮大作運算，可以得到下面結果： - $\infty + x = \infty$ - $\infty + \infty = \infty$ - $\infty - x = \infty$ - $\infty - \infty$ 未定義 - $\infty \times \infty = \infty$ - $\infty\,/\,\infty$ 未定義 - 下列集合的大小皆為無窮大。 - $|\,\mathbb{N}\,| = |\,\mathbb{Z}\,| = |\,\mathbb{Q}\,| = \infty$ - $|\,\mathbb{R}\,| = \infty$ - 因為 $\mathbb{N} \subset \mathbb{R}$，一個有趣的結果是 $|\,\mathbb{N}\,| < |\,\mathbb{R}\,|$。也就是說單獨看都是無窮大的集合，但是自然數的無窮大比實數的無窮大來得小?! - 第一類無窮大：one-to-one correspondence with $\mathbb{N}$。 ==直覺：與自然數一樣大，可以利用自然數編號列隊者== - 第二類無窮大：無法利用自然數編號的集合。 ==直覺：比自然數多很多的概念== - 無窮悖論 - [希爾伯特的大飯店](https://en.wikipedia.org/wiki/Hilbert%27s_paradox_of_the_Grand_Hotel) ### ++指數++ #### 使用時機 - 科學記號 - 例：$31415.926 = 3.1415926 \times 10^{4}$。 - 金融計算 - 例 1：假設年利率為 $r\,\%$，持有年數為 $n$。則初始金額為 $1$ 元，持有 $n$ 年後本利和為 $(1 + \dfrac{r}{100}) ^ n$。 - 例 2：假設年利率為 $r\,\%$，持有年數為 $n$。則未來價值為 $1$ 元，則現在的價值為 $(1 + \dfrac{r}{100}) ^ {-n}$，稱之為**折現** (discounting)。 - 演算法分析中，若程式的計算時間具有遞迴關係 $T(n) = T(n - 1) + T(n - 2)$，則經過進一步計算後可得 $T(n) = O(2 ^ n)$，稱為指數時間的演算法。 - 傳染病防治 - Ct (cycle threshold) 值，全名為**循環數閾值**，是 COVID-19 (新冠肺炎) 病毒基因在實驗室中，透過病毒核酸檢測 (PCR) 之後所測出來的數值。由於 COVID-19 病毒極小，必須透過 PCR 放大基因觀測，每放大 2 倍就是 1 單位的 Ct 值，複製的次數越多次，表示感染者體內的病毒含量越低；也就是 Ct 值越高，越沒有傳染力。Ct 值若檢測在 35 以下為確診者；目前日本、美國的確診 Ct 值則為40。 - 也就是說，病毒量透過倍增 $40$ 次，相當於放大 $2^{40} \sim 10^{12}$ 倍。 #### 定義 - 假設 $n \in \mathbb{N} \cup \{\,0\,\}$，我們將 $\underbrace{x \times x \times \cdots x}_{\text{n times}}$ 記作為 $x^n$。 - 例 1：$x^{0} = 1$。 - 例 2：$x^{2}x^{3} = x^{5}$。 ==指數加法== - 例 3：$(x^{2})^{3} = x^{6}$。 ==指數乘法== - 例 3：$x^{-1} = \frac{1}{x}$。 ==乘法反元素== - 例 4：$x^{-n} = (x^{-1})^{n} = \frac{1}{x^n}$。 - 例 5：$i^{2} = ((-1)^{\frac{1}{2}})^{2} = -1$。 - 假設 $n = \frac{1}{2}$，則 $x ^{\frac{1}{2}} = \sqrt{x}$。 - $(x ^{\frac{1}{2}})^2 = x ^{\frac{1}{2} \times 2} = x$。 - 故指數律可以推廣至 $n \in \mathbb{Q}$，在未來微積分的課程中，我們會推廣至 $n \in \mathbb{R}$，甚至 $n \in \mathbb{C}$。 #### 歐拉數 - 例 1：[半衰期](https://zh.wikipedia.org/zh-tw/%E5%8D%8A%E8%A1%B0%E6%9C%9F)。 - 例 2：連續複利。 - 假設 $r$ 為年利率，$T$ 年分 $n$ 期計息。 - 令 $\Delta t = \dfrac{T}{n}$。 - 則我們可以得到 $\lim\limits_{n \rightarrow \infty}(1 + r \Delta t) ^ {n} = e^{rT}$。 - 例 3：[秘書問題](https://zh.wikipedia.org/zh-tw/%E7%A7%98%E6%9B%B8%E5%95%8F%E9%A1%8C) (Secretary problem) aka 相親問題、止步問題、見好就收問題、蘇丹的嫁妝問題、挑剔的求婚者問題。 - 要聘請一名秘書，有 $n$ 個應聘者。每次面試一人，面試後就要及時決定是否聘他，如果當時決定不聘他，他便不會回來。面試後總能清楚了解應聘者的合適程度，並能和之前的每個人做比較。問什麼樣的策略，才使最佳人選被選中的概率最大。 - 解法是從第 $n \times \frac{1}{e}$ 個人開始，遇到比過去已經面試過的人都好，就直接錄取。 ### ++對數++ #### 使用時機 - 地震的[芮氏規模](https://zh.wikipedia.org/wiki/%E9%87%8C%E6%B0%8F%E5%9C%B0%E9%9C%87%E8%A6%8F%E6%A8%A1) - 化學的[酸鹼度](https://zh.m.wikipedia.org/zh-tw/PH%E5%80%BC) - 常溫下，為什麼 pH 值 7 是中性? - 編碼長度 - DNA 的 ATCG 四種胺基酸，如果透過二進位做編碼的話，請問需要幾個 bit? - [消息理論](https://zh.wikipedia.org/zh-tw/%E4%BF%A1%E6%81%AF%E8%AE%BA) - 假設 $S$ 為某一集合，其中 $x \in S$ 出現的機率是 $p_x$。 - 則其熵值 (entropy) 為 $\sum\limits_{x \in S} p_{x} \log_{2} \frac{1}{p_{x}}$。 - 如何解讀 $\frac{1}{p_x}$? - 演算法的[複雜度分析](https://zh.wikipedia.org/zh-tw/%E6%97%B6%E9%97%B4%E5%A4%8D%E6%9D%82%E5%BA%A6) - 對數時間的演算法：$O(\log n)$。 - 資料結構中的二元樹 (binary tree)，若節點數量為 $n$，若該樹是左右平衡，則搜尋深度為樹高，記作為 $O(\log_2 n)$。 #### 定義 - 我們透過稍早學到的指數律可知，$x ^ a = b$，則對數是指數的反函數，即 $a = \log_x\,b.$ - 意思是說，如果想要知道 $2$ 的幾次方才會是 $8$，此時可以透過 $\log_2\,8 = \log_2\,2 ^ 3 = 3$。 - 在高中數學中，寫 $\log\,x$ 時通常是指 $\log$ 以 $10$ 為底，即 $\log_{10}\,x$。 - 在大學數學中，寫 $\log\,x$ 時通常是指 $\log$ 以歐拉數 $e = 2.7183\ldots$ 為底，或記作為 $\ln x$。 - 在資訊科學中，寫 $\log\,x$ 時通常是指 $\log$ 以 $2$ 為底。 #### 函數圖形 <center> ![](https://hackmd.io/_uploads/S1r3gplqc.png) </center> #### 常用的結果 - $\log_{10} 1 = 0$ - $\log_{2} 1 = 0$ - $\log_{10} 10 = 1$ - $\log_{2} 2 = 1$ - $\log_{a} 1 = 0$ with $a > 0$ - $\log_{a} a = 1$ with $a > 0$ - $\log_{10} 2 = 0.3010$ - $\log_{10} 3 = 0.4771$ - $\log_{10} 6 = \log_{10} 2 \times 3 = \log_{10} 2 + \log_{10} 3$ (相乘變相加) - $\log_{10} 4 = \log_{10} 2 ^ 2 = 2 \log_{10} 2$ (指數在取 $\log$ 之後變成倍數) - $\log_{10} 7 = 0.8451$ - $\log_{2} 10 = \dfrac{1}{\log_{10} 2}$ (換底) #### 練習題 - $\log_{10} 5 = ?$ - $\log_{10} 8 = ?$ - $\log_{2} 1024 = ?$ - $\log_{10} 0.001 = ?$ - $\log_{2} 3 = ?$ #### 參考材料 #### 進階性質 <center> ![](https://hackmd.io/_uploads/SkdyMpgcq.png) </center> - 對數函數的微分：$\dfrac{d \ln x}{dx} = \dfrac{1}{x}$。 - 這個性質非常有趣。概念上就是當 $x$ 越大，則斜率越小。 - 斜率代表的是增加率。 - 結果就是"越跑越慢"，到最後增加的幅度幾乎是微乎其微。 ### ++方程式 & 多項式++ #### 一次方程式 (直線) - $y = a x + b$ #### 二次方程式 (拋物線) - $y = a x^2 + bx + c$ ##### 圓方程式 - $(x - h)^2 + (y - k)^2 = r ^2$ ##### 橢圓方程式 - $\dfrac{(x - h)^2}{a^2} + \dfrac{(y - k)^2}{b^2} = 1$ ##### 雙曲線方程式 - $\dfrac{(x - h)^2}{a^2} - \dfrac{(y - k)^2}{b^2} = 1$ #### $n$ 次多項式 - $y = a_n x ^n +a_{n - 1} x^{n - 1} + \cdots + a_1 x + a_0 = \sum\limits_{i = 0}^{n} a_i x^i$ ## 幾何 - 直線方程式 - 斜率 - 二次曲線 - 圓、橢圓 - 拋物線 - 雙曲線 - 三角不等式、詹森不等式 ## 邏輯 ### 敘述 & 真偽 - 例 1：今天天氣晴。這句話是對的還是錯的? - 例 2：十進位的 $1 + 1 = 2$。這句話是對的還是錯的? - 以上兩例，前句為敘述 (statement)，後者的判斷是針對這句話是否為正確。 - 一般而言，我們用布林變數 (boolean variable) 表示之。 - 布林 (boolean) 是紀念英國數學家 George Boole 發明了一套代數規則，故稱之為布林代數 (Boolean Algebra)。 - 不過其實應該是布爾變數、布爾代數。原因是 Boolean 是 Boole 的所有格... - https://www.google.com/doodles/george-booles-200th-birthday <center> ![](https://hackmd.io/_uploads/Skt1A_Z5c.png) </center> ## 排列組合 (組合數學) ### ++重複排列++ - 假設有 $n$ 種相異物，考慮個別的選取與否 (兩種狀態)，總共有 $2^n$ 種可能性。 - 例 1：假設 $A = \{a, b, c\}$，則 $A$ 的所有子集合有 $2^n$ 個。 ==冪集合== - 例 2：十進位的三位數有 $10^3$ 種可能的數字。 - 例 3：二進位的 32 bits 可以表示 $2^{32}$ 種可能的狀態。若只考慮正整數，則最大值為 $2^{32} - 1 \sim 4 \times 10^9$。 ### ++不重複排列++ - 假設有 $n$ 種相異物，考慮所有可能的排列順序 (順序交換算不同排排列)，總共有 $n!$ 種可能性。 - 例 1：假設 $A = \{a, b, c\}$，則會有 $3! = 6$ 種相異的排列：$abc, acb, bac, bca, cab, cba$。 - 例 2：[八皇后問題](https://zh.wikipedia.org/zh-tw/%E5%85%AB%E7%9A%87%E5%90%8E%E9%97%AE%E9%A2%98)。 - 例 3：[旅行推銷員問題](https://zh.wikipedia.org/zh-tw/%E6%97%85%E8%A1%8C%E6%8E%A8%E9%94%80%E5%91%98%E9%97%AE%E9%A2%98) (TSP)。 ### ++不重複組合++ - 假設有 $n$ 種相異物，任意挑選 $k$ 個為一組 (排列順序無差異，但每項只能挑一個)，則總共有 $C^{n}_k$ 種可能性，其中 $$C^{n}_k = \dfrac{n!}{k! (n - k)!} = \dfrac{n \times (n - 1) \times \cdots \times (n - k)}{k \times (k - 1) \times \cdots \times 1} = C^{n}_{n - k}$$ - 二項式定理：$C^{n}_k = C^{n - 1}_{k - 1} + C^{n - 1}_{k}$ - 例 1：[巴斯卡三角形](https://zh.wikipedia.org/zh-tw/%E6%9D%A8%E8%BE%89%E4%B8%89%E8%A7%92%E5%BD%A2) (Pascal's triangle)。 - 例 2：[卡塔蘭數](https://zh.wikipedia.org/zh-tw/%E5%8D%A1%E5%A1%94%E5%85%B0%E6%95%B0) (Catalan number)。 - 例 3：[Reflection principle](https://en.wikipedia.org/wiki/Reflection_principle)。 <center> ![image](https://hackmd.io/_uploads/HJsf3bwIp.png =500x) </center> ### ++重複組合++ - 假設有 $n$ 種相異物，任意挑選 $k$ 個為一組 (排列順序無差異，但是每項可以重複選，或者是所謂的取後放回)，則總共有 $H^{n}_k$ 種可能性，其中 $$H^{n}_k = C^{n + k - 1}_{k}。$$ ## **線性代數** ### ++線性轉換與線性運算子++ - 令 $T$ 為一個轉換關係使得 $T : a \in A \rightarrow a \in B$，記作為 $T x = y$。 - 假設 $p, q \in \mathbb{R}$。若 $T$ 滿足 $$T (p\,a_1 + q\,a_2) = p\,T\,a_1 + q\,T\,a_2 = p\,b_1 + q\,b_2, $$則 $T$ 為一個線性運算子。 - 例 1：$$\dfrac{d}{dx} (p f(x) + q g(x)) = p\dfrac{df(x)}{dx} + q\dfrac{dg(x)}{dx}.$$ ### ++向量++ ### ++內積和長度++ ### ++正交性++ ### ++矩陣++ ## **微積分** ### ++連續++ ### ++極限++ ### ++可微++ ### ++微分++ #### 連鎖律 - 令 $f(x)$ 與 $g(x)$ 可微。則 $\dfrac{d}{dx}f(g(x)) = \dfrac{df}{dg}\dfrac{dg}{dx}$。 #### 泰勒展開式 (Taylor's expansion) - 對於任何可微分的函數 $f(x) \in C^{(n)}$，$f(x) = f(x_0) + f'(x_0)(x - x_0) + \dfrac{1}{2} f''(x_0)(x - x_0)^2 + \cdots = \sum\limits_{i = 1}^{\infty} \dfrac{1}{i!}\dfrac{df^{(i)}(x_0)}{dx}(x - x_0)^{i}$。 - 例 1：考慮連續複利 $e^{r\Delta t}$。若 $\Delta t \rightarrow 0$，則 $e^{r\Delta t} \sim 1 + r\Delta t$。 - 例 2：令 $m_0$ 為靜止質量，$c$ 為光速。在相對論性力學中，運動體的總能量 (total energy) 為 $E = \dfrac{m_0c^2}{\sqrt{1 - \frac{v^2}{c^2}}}$。若此運動體相對某相對靜止的參考坐標系運動速度為 $v << c$，則 $E \sim m_0c^2 + \dfrac{1}{2}m_0v^2$，其中第一項為著名的質能方程式，後者古典牛頓力學的動能項。 - 詳見 https://en.wikipedia.org/wiki/Energy%E2%80%93momentum_relation ### ++積分++ ## **機率和統計** ### ++機率測度++ ### ++機率密度函數 (pdf) 和累積機率函數 (cdf)++ ### ++常見機率分佈：均勻分佈、伯努利分佈、二項式分佈、常態分佈++ ### ++描述統計：平均值、變異數、標準差、最小值、最大值、全距、$x\%$-百分位數++ ### ++抽樣++ ### ++估計++ ## 參考書目 ### 離散數學 - Ali Grami, [Discrete Mathematics: Essentials and Applications](https://www.amazon.com/Discrete-Mathematics-Applications-Grami-Ph-D/dp/012820656X), 2022 ![](https://hackmd.io/_uploads/HkQgL5VLh.png =100x) - Kenneth Rosen,[Discrete Mathematics and Its Applications](https://www.amazon.com/Discrete-Mathematics-Applications-Kenneth-Rosen/dp/125967651X), 8/e, 2018 ![](https://hackmd.io/_uploads/SJ9LIcEUh.png =100x) - Harry Lewis and Rachel Zax, [Essential Discrete Mathematics for Computer Science](https://www.amazon.com/Essential-Discrete-Mathematics-Computer-Science/dp/0691179298), 2019 ![](https://hackmd.io/_uploads/Hy4uwcVLh.png =100x) - Susanna Epp, [Discrete Mathematics with Applications](https://www.amazon.com/Discrete-Mathematics-Applications-Metric-Susanna/dp/0357114086/), 5/e, 2019 ![](https://hackmd.io/_uploads/BJHwv9ELh.png =100x) ### 線性代數 ### 微積分 ### 機率 ### 統計 ### 競程 - https://cp.wiwiho.me/