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

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

集合論

集合

定義

• 元素
  $x$ 屬於集合
  $A$，記作為
  $x\text{color}red\in A$。
  • 例 1：假設一枚硬幣有面朝上
    $(h)$ 與面朝下
    $(t)$ 兩種可能。則擲一次硬幣的結果 (
    $\mathrm{\Omega }$，讀作 omega) 為
    $\mathrm{\Omega }=\{h,t\}$。此時我們可以說
    $h\in \mathrm{\Omega }$ 和
    $t\in \mathrm{\Omega }$。
    
  • 例 2：交通號誌燈號有三種狀態：紅
    $(r)$、黃
    $(y)$、綠
    $(g)$。令
    ${\mathrm{\Omega }}^{\prime }=\{r、y、g\}$。白燈
    $w$ 不是交通號誌燈號的一種可能，記作
    $w\notin {\mathrm{\Omega }}^{\prime }$。
  • 例 3：假設
    $A=\{x|90\le x\le 100,x\in \mathbb{N}\}$。則我們可以知道
    $90,91,\dots ,100\in A$，但
    $90.5\notin A$ 且
    $101\notin A$。
• $B$ 是
  $A$ 的子集合，記作為
  $B\subset A$。
  • 例 1：
    $\{r,g\}\subset {\mathrm{\Omega }}^{\prime }$，但
    $\{r,w\}\not\subset {\mathrm{\Omega }}^{\prime }$。
  • 例 2：假設
    $A=\{x|90\le x\le 100,x\in \mathbb{N}\}$，
    $B=\{90,91,\dots ,95\}$，
    $C=\{80,91,\dots ,100\}$。則
    $B\subset A$ 但
    $C\not\subset A$。
• 若集合內沒有任何元素，則稱之為空集合，記作為
  $\varphi$。
  • 注意，
    $\varphi$ 是任何集合的子集合，尤其是
    $\varphi \subset \varphi$。
• $A$ 的大小 (基數) 是指集合的元素個數，記作為
  $|A|$。
  • 例 1：假設
    $A=\{a,b,c\}$。則
    $|A|=3$。
  • 例 2：
    $|\varphi |=0$。
• 假設
  $A=\{a,b,c\}$。則
  $A$ 的冪集 (power set) 有
  $2^{|A|}=8$ 個子集合：
  $\varphi$、
  $\{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\mathrm{\setminus }B$ 或者
  $A-B$。
• $B$ 差集
  $A$ 的結果為
  $\{e,f\}$，記作為
  $B\mathrm{\setminus }A$ 或者
  $B-A$。

對稱差集 (symmetric difference)

• 取
  $A$ 和
  $B$ 對稱差集為
  $\{c,d,e,f\}$，記作為
  $A\mathrm{\Delta }B$。
• 由此運算可發現，
  $A\mathrm{\Delta }B=B\mathrm{\Delta }A$。此性質稱之為可互換 (commutative)。
  • 其他的可交換操作如：
    $A\cap B=B\cap A$；
    $A\cup B=B\cup A$。
  • 但像是差集為不可交換順序。
• $A\mathrm{\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\}$，記作為
  $\bar{A}$。
• 則
  $B$ 的補集為
  $\{c,d,g,h\}$，記作為
  $\bar{B}$。

文氏圖

狄摩根定律

請根據

$A,B$ 集合找出

$\overline{A\cup B}=\bar{A}\cap \bar{B}=?$ 與

$\overline{A\cap B}=\bar{A}\cup \bar{B}=?$。

邏輯

• 考慮
  $X$ 與
  $Y$ 兩個布林變數 (Boolean variable)，則其真值表 (Truth table) 如下：

$X$	$Y$	$\bar{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 可以用

$\mathrm{\&},\mathrm{\&}\mathrm{\&}$ 或者

$\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 \{\mathrm{紅}\mathrm{茶},\mathrm{綠}\mathrm{茶},\mathrm{奶}\mathrm{茶}\}$。
  • 例 2：考慮
    $0\le x\le 1$ 且
    $y=x+1$，則
    $1\le y\le 2$，記作為
    $y=f(x)=x+1$。我們說
    $f$ 是一個
    $x$ 的函數，將
    $0\le x\le 1$ 映射到
    $1\le y\le 2$。
• 此時，我們稱
  $A$ 為定義域，
  $B$ 為值域。若
  $f:x\in A\mapsto y\in B^{\prime }\subset B$，且
  $A$ 中的元素沒有對應到
  $B-B^{\prime }$，則稱
  $B^{\prime }$ 為對應域。一般而言，
  $B=B^{\prime }$。
• 假設
  $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 {\displaystyle \frac{1}{3}}=2$	除法可以視作為乘上一個倒數 (乘法反元素)。
餘數	$x\mathrm{\%}y$	$7\mathrm{\%}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 _{i=1}^{n}i=1+2+3+\cdots +n={\displaystyle \frac{n(n+1)}{2}}$。 高斯的梯形公式
• 例 2：
  $\prod _{i=1}^{n}i=1\times 2\times 3\times \cdots \times n=n!$。
  $n!$ 稱為
  $n$ 階乘
• 例 3：
  $\sum _{i=1}^n{i}^2=1^2+2^2+3^2+\cdots +n^2={\displaystyle \frac{n(n+1)(2n+1)}{6}}$。
• 以上的等式可以透過數學歸納法 (mathematical induction) 證明之。
  • 請參考：https://en.wikipedia.org/wiki/Mathematical_induction

無窮 (Infinity)

• 無窮可以是無窮大、無窮小、無窮多等等的概念，記作為
  $\mathrm{\infty }$，直覺是無止盡的逼近。
  • 例 1：在除法運算中，若分母為零，則計算結果為無窮大。
  • 例 2：當
    $x\to 0$，則
    ${\displaystyle \frac{1}{x}}\to \mathrm{\infty }$。
  • 例 3：當
    $x\to \mathrm{\infty }$，則
    ${\displaystyle \frac{1}{x}}\to 0$。
  • 例 4：
    $\sum _{i=1}^{\mathrm{\infty }}i=-{\displaystyle \frac{1}{12}}$。
• 任何數字與無窮大作運算，可以得到下面結果：
  • $\mathrm{\infty }+x=\mathrm{\infty }$
  • $\mathrm{\infty }+\mathrm{\infty }=\mathrm{\infty }$
  • $\mathrm{\infty }-x=\mathrm{\infty }$
  • $\mathrm{\infty }-\mathrm{\infty }$ 未定義
  • $\mathrm{\infty }\times \mathrm{\infty }=\mathrm{\infty }$
  • $\mathrm{\infty }/\mathrm{\infty }$ 未定義
• 下列集合的大小皆為無窮大。
  • $|\mathbb{N}|=|\mathbb{Z}|=|\mathbb{Q}|=\mathrm{\infty }$
  • $|\mathbb{R}|=\mathrm{\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\mathrm{\%}$，持有年數為
    $n$。則初始金額為
    $1$ 元，持有
    $n$ 年後本利和為
    $(1+{\displaystyle \frac{r}{100}}{)}^n$。
  • 例 2：假設年利率為
    $r\mathrm{\%}$，持有年數為
    $n$。則未來價值為
    $1$ 元，則現在的價值為
    $(1+{\displaystyle \frac{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\}$，我們將
  $\underset{\text{n times}}{\underbrace{x\times x\times \cdots x}}$ 記作為
  $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$ 期計息。
  • 令
    $\mathrm{\Delta }t={\displaystyle \frac{T}{n}}$。
  • 則我們可以得到
    $\underset{n\to \mathrm{\infty }}{lim}(1+r\mathrm{\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 _{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\dots$ 為底，或記作為
  $\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={\displaystyle \frac{1}{{\log }_{10}2}}$ (換底)

練習題

• ${\log }_{10}5=?$
• ${\log }_{10}8=?$
• ${\log }_{2}1024=?$
• ${\log }_{10}0.001=?$
• ${\log }_{2}3=?$

參考材料

進階性質

• 對數函數的微分：
  ${\displaystyle \frac{d\ln x}{dx}}={\displaystyle \frac{1}{x}}$。
  • 這個性質非常有趣。概念上就是當
    $x$ 越大，則斜率越小。
  • 斜率代表的是增加率。
  • 結果就是"越跑越慢"，到最後增加的幅度幾乎是微乎其微。

方程式 & 多項式

一次方程式 (直線)

• $y=ax+b$

二次方程式 (拋物線)

• $y=a{x}^2+bx+c$

圓方程式

• $(x-h{)}^2+(y-k{)}^2=r^2$

橢圓方程式

• ${\displaystyle \frac{(x-h{)}^2}{a^2}}+{\displaystyle \frac{(y-k{)}^2}{b^2}}=1$

雙曲線方程式

• ${\displaystyle \frac{(x-h{)}^2}{a^2}}-{\displaystyle \frac{(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 _{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_k^n$ 種可能性，其中
  $$C_k^n={\displaystyle \frac{n!}{k!(n-k)!}}={\displaystyle \frac{n\times (n-1)\times \cdots \times (n-k)}{k\times (k-1)\times \cdots \times 1}}=C_{n-k}^n$$
• 二項式定理：
  $C_k^n=C_{k-1}^{n-1}+C_k^{n-1}$
  • 例 1：巴斯卡三角形 (Pascal's triangle)。
  • 例 2：卡塔蘭數 (Catalan number)。
  • 例 3：Reflection principle。

重複組合

• 假設有
  $n$ 種相異物，任意挑選
  $k$ 個為一組 (排列順序無差異，但是每項可以重複選，或者是所謂的取後放回)，則總共有
  $H_k^n$ 種可能性，其中
  $$H_k^n=C_k^{n+k-1}。$$

線性代數

線性轉換與線性運算子

• 令
  $T$ 為一個轉換關係使得
  $T:a\in A\to a\in B$，記作為
  $Tx=y$。
• 假設
  $p,q\in \mathbb{R}$。若
  $T$ 滿足
  $$T(p{a}_1+q{a}_2)=pT{a}_1+qT{a}_2=p{b}_1+q{b}_2,$$則
  $T$ 為一個線性運算子。
• 例 1：
  $${\displaystyle \frac{d}{dx}}(pf(x)+qg(x))=p{\displaystyle \frac{df(x)}{dx}}+q{\displaystyle \frac{dg(x)}{dx}}.$$

向量

內積和長度

正交性

矩陣

微積分

連續

極限

可微

微分

連鎖律

• 令
  $f(x)$ 與
  $g(x)$ 可微。則
  ${\displaystyle \frac{d}{dx}}f(g(x))={\displaystyle \frac{df}{dg}}{\displaystyle \frac{dg}{dx}}$。

泰勒展開式 (Taylor's expansion)

• 對於任何可微分的函數
  $f(x)\in C^{(n)}$，
  $f(x)=f(x_0)+f^{\prime }(x_0)(x-x_0)+{\displaystyle \frac{1}{2}}{f}^{″}(x_0)(x-x_0{)}^2+\cdots =\sum _{i=1}^{\mathrm{\infty }}{\displaystyle \frac{1}{i!}}{\displaystyle \frac{d{f}^{(i)}(x_0)}{dx}}(x-x_0{)}^i$。
• 例 1：考慮連續複利
  $e^{r\mathrm{\Delta }t}$。若
  $\mathrm{\Delta }t\to 0$，則
  $e^{r\mathrm{\Delta }t}\sim 1+r\mathrm{\Delta }t$。
• 例 2：令
  $m_0$ 為靜止質量，
  $c$ 為光速。在相對論性力學中，運動體的總能量 (total energy) 為
  $E={\displaystyle \frac{m_0{c}^2}{\sqrt{1-\frac{v^2}{c^2}}}}$。若此運動體相對某相對靜止的參考坐標系運動速度為
  $v<<c$，則
  $E\sim m_0{c}^2+{\displaystyle \frac{1}{2}}{m}_0{v}^2$，其中第一項為著名的質能方程式，後者古典牛頓力學的動能項。
  • 詳見 https://en.wikipedia.org/wiki/Energy–momentum_relation

積分

機率和統計

機率測度

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

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

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

$x\mathrm{\%}$-百分位數

抽樣

估計

參考書目

離散數學

• 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/