資訊科學的高中數學 (High School Math in Computer Science)

• 本文整理資訊科學 (computer science) 中會使用到的中學數學 (特別是高中數學)，適合需要快速回顧的學員或者想超前學校進度的學員。保守初估實體教室上課需花費約三小時。
• 數學的目的是透過簡化問題的方式了解世界，並非要用抽象的符號來困惱學生。
  • 抽象的工具才有一般性，因此才能重複使用，能夠以一招打天下，做到見山不是山、見水不是水，培養看透外表、潛藏在背後的模式 (pattern)。
• 因此對我個人而言，數學是工具，如同時下熱門的程式語言，有需求的時候才回頭補齊數學也不遲，唯一要考慮的代價就是成長曲線有可能比較平緩：年紀小的學員普遍吸收新知與計算能力較成年人來得強，可以有較陡峭的成長曲線。
• 本文內容的預備知識：
  • 基礎算術能力：數數、四則運算、九九乘法、交換律、結合律、平方運算、根號運算。
  • 基礎幾何能力，例如：圓形、三角形等，並能夠計算周長、面積等。
  • 基礎代數能力，例如：
    \(x = 1\) 且
    \(y = x + 1\)，則
    \(y = 2\)。
  • 基礎邏輯能力，例如：且 (and)、或 (or) 的定義。
• 如果想要快速具備上述基礎能力，可以參考日劇東大特訓班的訓練方式。
  • 熟能生巧，勤能補拙。學程式語言、演算法、做專案亦如是。甚至任何一種專業都需要這段量變產生質變的過程。
  • 中國人的說法也可以參考：量變產生質變。
• 台灣現行課綱可於此網頁取得：教育部數學領域課程手冊、國高中數學學習清單
• 以台大資訊系為例，大學部的基礎數學課程有微積分、線性代數、離散數學、機率論等，近年還有開設工程數學，包含微分方程式、傅立葉分析、拉普拉斯轉換和複變分析等工程領域通用的數學。

集合論

集合

定義

• 元素
  \(x\) 屬於集合
  \(A\)，記作為
  \(x\,{\color{red}\in}\,A\)。
  • 例 1：假設一枚硬幣有面朝上
    \((h)\) 與面朝下
    \((t)\) 兩種可能。則擲一次硬幣的結果 (
    \(\Omega\)，讀作 omega) 為
    \(\Omega = \{\,h, t\,\}\)。此時我們可以說
    \(h \in \Omega\) 和
    \(t \in \Omega\)。
    
  • 例 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\)。此性質稱之為可互換 (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}\)。

文氏圖

狄摩根定律

請根據

\(A, B\) 集合找出

\(\overline{A \cup B} = \overline{A} \cap \overline{B} = ?\) 與

\(\overline{A \cap B} = \overline{A} \cup \overline{B} = ?\)。

邏輯

• 考慮
  \(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)

• 假設
  \(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)。

現代集合論

• 請參考：https://zh.wikipedia.org/wiki/集合論

康德爾集合 (Cantor Set)

• 康德爾集合為在
  \(0-1\) 數線上，挖掉中間
  \(\frac{1}{3}\) 的部分，然後再從剩下的線段，重複挖掉該片段的
  \(\frac{1}{3}\)，如上圖所示。
• 有趣的是，此線段是一個非空集合 (因為還有剩下類似
  \(\frac{1}{3}, \frac{2}{3}\) 等等之類的有理數)，但是集合的大小 (總長度) 為零。
• 這個結果在現代機率論上面是一個重要的結果：該事件的機率為零，不代表該事件不會發生。

代數

基本算術

數字系統

• 自然數 (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 在乘法運算中是毀滅性元素。

連加與連乘積

• 例 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}\)。 直覺：與自然數一樣大，可以利用自然數編號列隊者
    • 第二類無窮大：無法利用自然數編號的集合。 直覺：比自然數多很多的概念
• 無窮悖論
  • 希爾伯特的大飯店

指數

使用時機

• 科學記號
  • 例：
    \(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}\)。
• 例 3：秘書問題 (Secretary problem) aka 相親問題、止步問題、見好就收問題、蘇丹的嫁妝問題、挑剔的求婚者問題。
  • 要聘請一名秘書，有
    \(n\) 個應聘者。每次面試一人，面試後就要及時決定是否聘他，如果當時決定不聘他，他便不會回來。面試後總能清楚了解應聘者的合適程度，並能和之前的每個人做比較。問什麼樣的策略，才使最佳人選被選中的概率最大。
  • 解法是從第
    \(n \times \frac{1}{e}\) 個人開始，遇到比過去已經面試過的人都好，就直接錄取。

對數

使用時機

• 地震的芮氏規模
• 化學的酸鹼度
  • 常溫下，為什麼 pH 值 7 是中性?
• 編碼長度
  • DNA 的 ATCG 四種胺基酸，如果透過二進位做編碼的話，請問需要幾個 bit?
• 消息理論
  • 假設
    \(S\) 為某一集合，其中
    \(x \in S\) 出現的機率是
    \(p_x\)。
  • 則其熵值 (entropy) 為
    \(\sum\limits_{x \in S} p_{x} \log_{2} \frac{1}{p_{x}}\)。
  • 如何解讀
    \(\frac{1}{p_x}\)?
• 演算法的複雜度分析
  • 對數時間的演算法：
    \(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\) 為底。

函數圖形

常用的結果

• \(\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 = ?\)

參考材料

進階性質

• 對數函數的微分：
  \(\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

排列組合 (組合數學)

重複排列

• 假設有
  \(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：八皇后問題。
  • 例 3：旅行推銷員問題 (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：巴斯卡三角形 (Pascal's triangle)。
  • 例 2：卡塔蘭數 (Catalan number)。
  • 例 3：Reflection principle。

重複組合

• 假設有
  \(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–momentum_relation

積分

機率和統計

機率測度

機率密度函數 (pdf) 和累積機率函數 (cdf)

常見機率分佈：均勻分佈、伯努利分佈、二項式分佈、常態分佈

描述統計：平均值、變異數、標準差、最小值、最大值、全距、

\(x\%\)-百分位數

抽樣

估計

參考書目

離散數學

• Ali Grami, Discrete Mathematics: Essentials and Applications, 2022
  
  
• Kenneth Rosen,Discrete Mathematics and Its Applications, 8/e, 2018
  
  
• Harry Lewis and Rachel Zax, Essential Discrete Mathematics for Computer Science, 2019
  
  
• Susanna Epp, Discrete Mathematics with Applications, 5/e, 2019
  
  

線性代數

微積分

機率

統計

競程

• https://cp.wiwiho.me/