douobb

考研相關文章參考資料為 wjungle 大神提供的筆記 Stack 具有 LIFO 性質之有序串列，插入元素之操作為 push，刪除元素之操作為 push，且兩者發生於同一端，稱為頂端 (top) Stack Permutation 給予 nnn 個資料依序 push 進入 stack，並且在過程中可以進行任意合法的 pop 將資料輸出，在此模式下所產生的所有輸出之排列組合 ex: a,b,ca,b,ca,b,c 之 Stack Permutation: abc, acb, bac, bca, cab, cba 共 5 種 nnn 個資料之 Stack Permutation 個數: 1n+1Cn2n\frac{1}{n + 1}C_{n}^{2n}n+11​Cn2n​ 與下列問題之個數相同 (卡塔蘭數): nnn 個 nodes 可以形成的不同二元樹個數 nnn 組 “(” 及 “)” 之合法配對個數 (n+1)(n + 1)(n+1) 個 matrix 相乘之所有乘法組合個數 Infix, Postfix, Prefix 轉換 計算題型作法 括 ...

考研相關文章參考資料為 wjungle 大神提供的筆記 漸進式符號 Asymptotic Notations 表示時間函數的成長速率 (growth rate) 等級 符號 OOO f(n)=O(g(n))f(n) = O(g(n))f(n)=O(g(n)) iff exist two positive constants ccc and n0n_0n0​ such that f(n)≤c∗g(n)f(n) \leq c*g(n)f(n)≤c∗g(n), for all n≥n0n \geq n_0n≥n0​ 視為理論的 Upper-Bound Ω\OmegaΩ f(n)=Ω(g(n))f(n) = \Omega(g(n))f(n)=Ω(g(n)) iff exist two positive constants ccc and n0n_0n0​ such that f(n)≥c∗g(n)f(n) \geq c*g(n)f(n)≥c∗g(n), for all n≥n0n \geq n_0n≥n0​ 視為理論的 Lower-Bound Θ\ThetaΘ f(n ...

考研相關文章參考資料為 wjungle 大神提供的筆記 Array 元素之位置 一維陣列 A:array[l...u]A: array[l...u]A:array[l...u] of items 共有 u−l+1u - l + 1u−l+1 格 起始位置: l0l_0l0​ 元素大小: ddd A[i]A[i]A[i] 的位置: l0+(i−l)∗dl_0 + (i - l) * dl0​+(i−l)∗d 二維陣列 A:array[l1...u1,l2...u2]A: array[l_1...u_1, l_2...u_2]A:array[l1​...u1​,l2​...u2​] of items 有 u1−l1+1u_1 - l_1 + 1u1​−l1​+1 列，u2−l2+1u_2 - l_2 + 1u2​−l2​+1 行 Row-major A[i,j]=l0+[(i−l1)∗(u2−l2+1)+(j−l2)]∗dA[i, j] = l_0 + [(i - l_1) * (u_2 - l_2 + 1) + (j - l_2)] * dA[i,j]=l0​+[( ...

考研相關文章參考資料為 wjungle 大神提供的筆記 Graph 令 G=<V,E>G = <V, E>G=<V,E> 代表圖形是由兩個非空集合組成: VVV: 代表頂點 (Vertex) EEE: 代表邊 (Edge) 根據邊的類型，可分為兩類: Undirected Graph (無向圖) 邊不具有方向性 (i,j)=(j,i)(i,j) = (j,i)(i,j)=(j,i) 代表同一邊 Directed Graph (有向圖) 邊具有方向性 (i,j)≠(j,i)(i,j) \neq (j,i)(i,j)​=(j,i) 相關術語 Eulerian cycle (尤拉 cycle) 從某點出發，經過每個邊各一次，又回到原點 充分必要條件: 每個頂點之 degree 為偶數 Eulerian chain 從某點出發，經過每個邊各一次，不一定要回到原點 充分必要條件: 有兩個頂點之 degree 為奇數，剩餘頂點之 degree 為偶數 Hamiltonian Path (漢米爾頓路徑) 從某點出發， ...

考研相關文章參考資料為 wjungle 大神提供的筆記 Hashing 一種資料儲存與搜尋的機制，當想要存入或取出資料時，先經過 Hashing Function 求出 Hashing Address，接著到 Hash Table 中對應的 Bucket 存入或取出資料 xxx Hash Table 由 BBB 個 Bucket 組成 每個 Bucket 則由 SSS 個 Slots 組成 每個 Slot 可儲存一筆資料 優點: 資料搜尋前不用經過排序 在沒有 Collision 的情況下，資料搜尋時間為 O(n)O(n)O(n) Worst case: O(n)O(n)O(n): Hashing Function 為定值 保密性、安全性高 不知道 Hashing Function 則無法存取資料 不可回推 常用於密碼學、資料壓縮 相關術語 Collision 碰撞 不同資料經過 Hashing Function 後得到相同 Hashing Address Overflow 溢位 Collision 發生後對應的 Bucket 沒有多餘空間 ...

正規語言相關文章參考資料為陳穎平教授上課講義 L7 Time Complexity Measuring Complexity Definition Let MMM be a deterministic Turing machine that halts on all inputs. The running time or time complexity of MMM is the function f:N→Nf : N → Nf:N→N , where f(n)f (n)f(n) is the maximum number of steps that MMM uses on any input of length nnn. If f(n)f (n)f(n) is the running time of MMM , we say that MMM runs in time f(n)f (n)f(n) and that MMM is an f(n)f (n)f(n) time Turing machine. Customarily we use nnn to represent the ...

正規語言相關文章參考資料為陳穎平教授上課講義 L5 Reducibility If problem A reduces to problem B, we can use a solution to B to solve A. When A is reducible to B, solving A cannot be harder than solving B because a solution to B gives a solution to A. Therefore, if A is reducible to B, B is decidable ⇒ A is decidable; A is undecidable ⇒ B is undecidable. Undecidable Problems from Language Theory 定義 HALTTM={⟨M,w⟩ ∣ M is a TM and M halts on input w}HALT_{TM} = \{ ⟨M, w⟩~|~M~is~a~TM~and~M~halts~on~input~w \}HALTTM​={⟨ ...

正規語言相關文章參考資料為陳穎平教授上課講義 L4 Decidability Decidable Languages Decidable Problems Concerning Regular Languages 定義 ADFA={⟨B,w⟩ ∣ B is a DFA that accepts input string w}A_{DFA} = \{ ⟨B, w⟩~|~B~is~a~DFA~that~accepts~input~string~w \}ADFA​={⟨B,w⟩ ∣ B is a DFA that accepts input string w} Theorem ADFAA_{DFA}ADFA​ is a decidable language. 證明: 建立一個 TM MMM 模擬 www 在 BBB 上的行為，如果停在 accept states 則 ADFAA_{DFA}ADFA​ appect，否則會 reject，只有這兩種可能，因此是 Decidable 的 定義 ANFA={⟨B,w⟩ ∣ B is a NFA that accepts input st ...

正規語言相關文章參考資料為陳穎平教授上課講義 L3 The Church-Turing Thesis Turing Machines 圖靈機的想法: Finite control + unlimited and unrestricted memory. 在磁帶上面讀 & 寫 可以將讀取頭向左/右移動 磁帶是無限長的 可以立刻決定拒絕 (Reject) 或接受 (Accept) Formal Definition of A Turing Machine Definition A Turing machine is a 7-tuple (Q,Σ,Γ,δ,q0,qaccept,qreject)(Q, Σ, Γ, δ, q_0, q_{accept}, q_{reject})(Q,Σ,Γ,δ,q0​,qaccept​,qreject​), where Q,Σ,ΓQ, Σ, ΓQ,Σ,Γ are all finite sets and QQQ is the set of states; ΣΣΣ is the input alphabet not containing the b ...

正規語言相關文章參考資料為陳穎平教授上課講義 L2 Context-Free Languages Context-Free Grammars CFGs: 上下文無關文法，指的是字元在進行替換時不需要考慮上下文，其擁有足夠的表現力來表示大多數程式設計語言的語法 Formal Definition of CFGs Definition A context-free grammar is a 4-tuple (V,Σ,R,S)(V, Σ, R, S)(V,Σ,R,S), where VVV is a finite set called the variables; ΣΣΣ is a finite set, disjoint from VVV ,called the terminals; RRR is a finite set of rules (or productions), with each rule being a variable and a string of variables and terminals; S∈VS ∈ VS∈V is the start varia ...