--- 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/
Last changed by  
 
Zheng-Liang Lu
Writing for future me.
2366

Read more

來讀書

大學時因為國文老師的一句話所以開啟了一段大量閱讀的時期。時光荏苒，發現自己除了專業知識外，對於其他領域的涉獵實在不足。盼望能重拾閱讀的習慣，為自己留下一些閱讀的痕跡。

4/24/2024
Algorithms Lab

This short course is designed for students who plan to learn about common data structures with efficient algorithms, solve LeetCode problems, and know state-of-the-art information techniques. The achievements of Algorithms Lab are listed below:

4/8/2024
Parallel Computing & Algorithms

Multicore design is one of modern features of computer systems. You can easily see at least 4 cores in commercial CPUs in your desktop computers, laptops, even smart phones (for example, Apple A16 has one 6 cores CPU). However, the programming beginners rarely have opportunities to exploit the performance benefits of multi-core hardware, letting alone get a deep understanding of contemporary computer architecture. In recent years, Artificial Intelligence (AI) has become a prominent field, heavily relying on graphics processing units (GPUs) or accelerators for machine learning (ML). For example, the latest NVIDIA graphics card, the RTX 4090, has 16384 CUDA cores. Utilizing such an immense number of computational units has become a crucial challenge. This course shows you how to utilize these computing units (CPUs and GPUs) to unleash their computational performance. We will cover the following topics in ths course:

3/30/2024
Developers' Guide to Environment Setup

This article helps you set up your environment step by step.

3/16/2024
Read more from Zheng-Liang Lu
Published on HackMD