douobb

考研相關文章參考資料為 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 ...

正規語言相關文章參考資料為陳穎平教授上課講義 Regular Languages Finite Automata 有限自動機 or DFA: Deterministic finite automata 決定性有限自動機 Formal Definition of Finite Automata Definition A finite automaton is a 5-tuple (Q,Σ,δ,q0,F)(Q, Σ, δ, q_0, F)(Q,Σ,δ,q0​,F), where QQQ: is a finite set called the states; ΣΣΣ: is a finite set called the alphabet; δδδ: Q×Σ→QQ × Σ → QQ×Σ→Q is the transition function; q0∈Qq_0 ∈ Qq0​∈Q: is the start state; F⊆QF ⊆ QF⊆Q: is the set of accept states or final states. Formal Definition of C ...

考研相關文章參考資料為 wjungle 大神提供的筆記 Search Linear Search 又稱為 Sequential Search，從頭到尾一一比較是否符合 特性: 不必事先進行排序 資料可以保存在 Ramdom Access (array) 或 Sequentail Access (link list) 結構中 時間複雜度: O(n)O(n)O(n) Binary Search 預先準備 必須將資料排序 (小 -> 大) 資料必須保存在 Ramdom Access (array) 結構 可以做成 Iterative / Recursive 版本 時間複雜度: O(log⁡n)O(\log n)O(logn) 最多比較次數為 Decision Tree (高度最小化的 BT) 之樹高 名詞區分 Worst case: Binary Search: O(log⁡n)O(\log n)O(logn) Binary Search Tree: O(n)O(n)O(n) (斜曲) Sort 名詞解釋 Internal / External ...

考研相關文章參考資料為 wjungle 大神提供的筆記 Doubled-ended priority Queue 兩端皆可插入元素，一端提供 deleteMax，一端提供 deleteMin 資料結構: Min-Max Heap Deap SMMH 提供操作: Insert x Delete-Max Delete-Min Min-Max Heap 是一個 Complete BT，並且滿足: level 以 min-level 與 max-level 交替出現 x 位於 min-level: 以 x 為 root 之子樹中，x 為最小值 x 位於 max-level: 以 x 為 root 之子樹中，x 為最大值 Root 位於 min-level Insert x 把 x 放到最後一個節點的下一個位置 根據 x 的父節點 p 所在 level 進行挑戰 如果挑戰父節點成功: 將父節點下移，並挑戰父節點原本位置的祖父節點 挑戰失敗: 挑戰祖父節點 Delete-Min 刪除 root 的資料，並且刪除最後一個節點 x 的資料 (迴圈)將 x ...