--- tags: computer science, math --- # 資訊科學的高中數學 <font size = -1>(High School Math in Computer Science)</font> - 本文整理資訊科學中會使用到的中學數學(特別是高中數學),適合++需要快速回顧的學員++或者++想超前學校進度的學員++。初估大班教室上課需花費約三小時。 - 數學的目的是透過**簡化問題**的方式了解世界,並非要用抽象的符號來困惱學生。 - 抽象的工具才有一般性,因此才能**重複使用**,能夠以一招打天下,做到見山不是山、見水不是水,培養看透外表、潛藏在背後的模式 (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) 請根據 $A, B, C$ 三個集合在每個區域內寫下符合交集的元素。 </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$ 替換。 ### ++映射 (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 \div y$ | $6 \div 3 = 6 \times \dfrac{1}{3} = 2$ | 除法可以視作為乘上一個倒數 (乘法反元素)。 | | 餘數 | $x\,\%\,y$ | $7 \div 3 = 1$ | 基本運算。 | - 四則運算具備**交換律**與**結合律**。 - 例 1:$a \times (b \times c) = (a \times b) \times c$。 - 例 2:$a \times (b + c) = a \times b + a \times c$。 - 在資訊系大一下有一門數學課稱作為**離散數學**,其中幾章會討論到代數 (環、群、體)。以下為一些可以先知道的事實: - $0$ 為加法單位元素,任何數字加上 $0$ 都是原來的數字,例如:$x + 0 = x$。 - $1$ 為乘法單位元素,任何數字乘上 $1$ 都是原來的數字,例如:$x \times 1 = x$。 #### 連加與連乘積 - 例 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 = \infty$ or $-\dfrac{1}{12}$。 - 詳見 TBA。 - 任何數字與無窮大作運算,可以得到下面結果: - $\infty + x = \infty$ - $\infty + \infty = \infty$ - $\infty - x = \infty$ - $\infty - \infty$ 未定義 - $\infty \times \infty = \infty$ - $\infty \div \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:半衰期 - 例 2:連續複利。假設 $r$ 為年利率,$T$ 年分 $n$ 期計息。令 $\Delta t = \dfrac{T}{n}$。則我們可以得到 $\lim\limits_{n \rightarrow \infty}(1 + r \Delta t) ^ {n} = e^{rT}$。 ### ++對數++ #### 使用時機 - 地震的[芮氏規模](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) - 熵 (entropy) 的定義: $\sum\limits_{x \in S} -p_{x} \log_{2} 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:TBA ### ++不重複組合++ - 假設有 $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:巴斯卡三角形 (Pascal's triangle)。 - 例 2:TBA ### ++重複組合++ - TBA ## **線性代數** ### ++線性轉換與線性運算子++ - 令 $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}.$$ - 例 2:$$A (p \, x_1 + q \, x_2) = p\, $$ ### ++向量++ ### ++內積和長度++ ### ++正交性++ ### ++矩陣++ ## **微積分** ### ++連續、極限、可微++ ### ++微分++ #### 連鎖律 - 令 $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/