douobb

L4 連通度與路徑 符號定義 符號 意義 δ(G)\delta(G)δ(G) 最小度 (minimum degree) NG(v)N_G(v)NG​(v) vvv 的鄰居集合 (neighborhood) κ(G)\kappa(G)κ(G) 圖 GGG 的頂點連通度 (connectivity) λ(G)\lambda(G)λ(G) 圖 GGG 的邊連通度 (edge-connectivity) κ(x,y)\kappa(x,y)κ(x,y) 分開 x,yx,yx,y 所需移除的最少頂點數 λ(x,y)\lambda(x,y)λ(x,y) 講義此處用來表示 x,yx,yx,y 間最大兩兩頂點不相交路徑數 [X,Y][X,Y][X,Y] X,YX,YX,Y 兩頂點集合之間的邊集合 Vertex Cut 與 Connectivity Vertex Cut (點割) 對連通圖 GGG，若頂點集合 S⊆V(G)S\subseteq V(G)S⊆V(G) 滿足 G−SG-SG−S 有超過一個 connected component，則稱 SSS ...

Continuous Random Variables Probability Density Function (PDF) 對 continuous random variable XXX，probability density function 記為 f(x)f(x)f(x)。 區間機率由 density curve 下方的面積計算: P(a≤X≤b)=∫abf(x) dxP(a\le X\le b)=\int_a^b f(x)\,dxP(a≤X≤b)=∫ab​f(x)dx ∫−∞∞f(x) dx=1\int_{-\infty}^{\infty}f(x)\,dx=1∫−∞∞​f(x)dx=1 Cumulative Distribution Function (CDF) 對 continuous random variable: F(x)=∫−∞xf(u) duF(x)=\int_{-\infty}^{x}f(u)\,duF(x)=∫−∞x​f(u)du PDF 與 CDF 的關係: f(x)=dF(x)dxf(x)=\frac{dF(x)}{dx}f(x)=dxdF(x)​ 單點機 ...

Poisson Process 與 Poisson Distribution Poisson Process 描述在時間或空間區間內隨機發生的事件數量，例如電話到達、事故、缺陷數等。 主要假設: 在很短的區間 hhh 內，發生一次事件的機率約為 λh\lambda hλh (與長度成正比)。 當 hhh 很小時，同一區間發生兩次以上事件的機率可忽略。 互不重疊區間的事件發生次數彼此獨立。 在所考慮的範圍內，平均發生率 λ\lambdaλ 大致固定 (Homogeneous，均勻性)。 Poisson Random Variable X∼Poisson⁡(μ),μ=λtX\sim\operatorname{Poisson}(\mu),\quad \mu=\lambda tX∼Poisson(μ),μ=λt λ\lambdaλ: 每單位時間／空間的平均發生次數。 ttt:觀察長度；μ=λt\mu=\lambda tμ=λt: 整段觀察範圍的平均事件數。 XXX: 該範圍內實際發生次數，因此只能是非負整數。 PMF: P(X=x)=e−μμxx!{P(X=x)=\frac{e^ ...

Random Variable Definition Random variable 是將 sample space 中的 outcome 映射到 real line 的函數。 X:S→RX:S\rightarrow\mathbb{R}X:S→R 也就是把隨機實驗的結果轉成一個可以分析的數值。 Types of Random Variables Discrete Random Variable: possible values 可以一一列舉 Continuous Random Variable: possible values 為連續數值 Discrete Random Variables Probability Mass Function (PMF): p(x)=P(X=x)p(x)=P(X=x)p(x)=P(X=x) ∑xP(X=x)=1\sum_x P(X=x)=1∑x​P(X=x)=1 Cumulative Distribution Function (CDF): F(x)=P(X≤x)F(x)=P(X\le x)F(x)=P(X≤x) F(x)=∑a≤xP ...

Two-way Tables and Conditional Probabilities Independence 的應用: Sensitive Questions 可以透過隨機化設計，讓受訪者不必直接回答敏感問題。 基本想法: P(Yes)=P(choose A and Yes)+P(choose B and Yes)P(\text{Yes})=P(\text{choose A and Yes})+P(\text{choose B and Yes})P(Yes)=P(choose A and Yes)+P(choose B and Yes) 若「選到哪題」與敏感行為 independent，則: P(choose B and Yes)=P(choose B)P(Yes to B)P(\text{choose B and Yes})=P(\text{choose B})P(\text{Yes to B})P(choose B and Yes)=P(choose B)P(Yes to B) 因此可由整體 Yes 比例反推出敏感行為比例。 Genetics 基本名詞 名詞 意義 ...

Exploratory Data Analysis Coefficient of Variation (CV) 變異係數 CV=SXˉ×100%CV=\frac{S}{\bar X}\times 100\%CV=XˉS​×100% SSS: standard deviation Xˉ\bar XXˉ: mean Unitless (無單位) 適合比較不同單位或不同數值尺度的資料 CV 越大，表示相對變異程度越大 資料進行線性轉換: X∗=a+bXX^*=a+bXX∗=a+bX 得到 CV∗=bSa+bXˉCV^*=\frac{bS}{a+b\bar X}CV∗=a+bXˉbS​ 若 a≠0a\neq0a​=0: CV∗≠CVCV^*\neq CVCV∗​=CV Categorical Data 圖表 Side-by-side Bar Plot: 比較兩個 categorical variables Pie Chart: 各類別占整體的比例 Bar Chart: 可依特定順序排列、方便比較各 category 的大小 Numerical Data 圖表 Hist ...

圖表描述 Shape Symmetric Left-skewed Right-skewed 尾巴的方向 Stem-leaf Plot Back-to-back stem-leaf plot 描述: Symmetry / skewness Peak Center Variation Gap Outliers Descriptive Measures Robustness Measure Robust? Mean No Median Yes Five-number Summary MinMinMin: 最小值 Q1Q_1Q1​: 第一四分位數, PR25 前半部資料的 median (如果 nnn 為奇數則包含中位數) MedianMedianMedian: 中位數, PR50 nnn 為奇數: M=X(n+12)M=X_{\left(\frac{n+1}{2}\right)}M=X(2n+1​)​ nnn 為偶數: X(n/2)+X(n/2+1)2\frac{X_{(n/2)}+X_{(n/2+1)}}{2}2X(n/2)​+X(n/ ...

L3 匹配與因子 符號定義 符號 意義 M⊆E(G)M\subseteq E(G)M⊆E(G) 一組匹配(邊集合) V(M)V(M)V(M) 被 MMM 中邊覆蓋到的頂點集合 N(S)N(S)N(S) 集合 SSS 的鄰居集合；Hall 定理中 S⊆XS\subseteq XS⊆X，N(S)⊆YN(S)\subseteq YN(S)⊆Y o(G)o(G)o(G) GGG 的奇數階連通分支 (odd components) 個數 α′(G)\alpha'(G)α′(G) 最大匹配的邊數 (matching number) β(G)\beta(G)β(G) 最小頂點覆蓋大小 α(G)\alpha(G)α(G) 最大獨立集大小 β′(G)\beta'(G)β′(G) 最小邊覆蓋大小 (要求沒有孤立點) γ(G)\gamma(G)γ(G) 最小支配集大小 Matchings and Covers 名詞 定義／判斷方式 Matching (匹配) 一組兩兩沒有共同端點的邊；一個頂點最多被選中的一條邊使用。 ...

L2 樹與距離 符號定義 符號 意義 dG(u,v)d_G(u,v)dG​(u,v) uuu 與 vvv 間的最短路徑長度（距離） εG(v)\varepsilon_G(v)εG​(v) 頂點 vvv 的離心率 diam⁡(G)\operatorname{diam}(G)diam(G) 圖 GGG 的直徑 (diameter) rad⁡(G)\operatorname{rad}(G)rad(G) 圖 GGG 的半徑 (radius) G[S]G[S]G[S] 頂點集合 SSS 的導出子圖 KnK_nKn​、PnP_nPn​、CnC_nCn​ 完全圖、nnn 點路徑圖、nnn 點環圖 Km,nK_{m,n}Km,n​；K1,nK_{1,n}K1,n​ 完全二部圖；星圖 hhh；LLL；III 樹高；葉節點數；內部節點數 w(e)w(e)w(e)；w(T)w(T)w(T) 邊權重；生成樹的邊權重總和 樹與森林 名詞 定義/性質 Tree 連通 (connected) 且無環 (acyclic) 的圖。 Forest 每一 ...

L1 基本概念 符號定義 符號 意義 G=(V,E)G=(V,E)G=(V,E) 圖、頂點集、邊集 n=∥V(G)∥n=\|V(G)\|n=∥V(G)∥；m=∥E(G)∥m=\|E(G)\|m=∥E(G)∥ 頂點數；邊數 NG(v)N_G(v)NG​(v) vvv 的鄰居集合 dG(v)d_G(v)dG​(v) 或 deg⁡G(v)\deg_G(v)degG​(v) vvv 的度數 δ(G)\delta(G)δ(G)；Δ(G)\Delta(G)Δ(G) 最小度；最大度 G[S]G[S]G[S] 由頂點集 SSS 導出的子圖 G‾\overline GG GGG 的補圖 KnK_nKn​、PnP_nPn​、CnC_nCn​ 完全圖、nnn 點路徑圖、nnn 點環圖 圖表示 Adjacency matrix (鄰接矩陣) Adjacency list (鄰接串列) 內容 n×nn\times nn×n 矩陣，Aij=1  ⟺  ij∈EA_{ij}=1\iff ij\in EAij​=1⟺ij∈E 每個頂點列出所有鄰居 儲 ...