douobb

正規語言相關文章參考資料為陳穎平教授上課講義 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 ...

考研相關文章參考資料為 wjungle 大神提供的筆記 樹 (Tree) 由 >0 個節點 (Node) 所構成 森林 (Forest): 由 >=0 個樹所構成 (可以為空) 表示方式 Link list | Data | child | sibling | 假設 degree 為 k，並且有 n 個節點，會浪費 n*k-(n-1) 條 Link (Nil links) 轉為二元樹表示 Child-sibling 方法 | Data | child | sibling | child: 指向 leftmost-child sibling: 指向 次右兄弟 括號法 以 父(子1,子2,...子n) 表示父點與子點之間的關係，並且可以巢狀方式表示 二元樹 (BT) 可以為空，若不為空則滿足: 有 root 及左右子樹 左右子樹也是二元樹 與樹比較: 樹 二元樹 不能為空 可以為空 degree >= 0 2 >= degree >= 0 子樹之間無次序/方向之分 子樹有左右之分 基本定理 ...

L12 Work: Occupational and Lifestyle Issues in Young and Middle Adulthood Occupational Selectionn and Development The Meaning of Work 多數人認為工作的意義: 賺錢 個人成長 個人成就 發展自我 與人合作 表達自我 為他人服務 Meaning-mission fit 個人意向公司的目標是否相符 如果相符的話，會提高幸福感以及工作滿意度 Occupational Choice Revisited 工作選擇相關理論: Career construction theory 生涯建構論 人們通過個人特質和社會環境產生的行動來選擇職業 Holland’s personality-type theory 人格類型論 人們根據個人特質與職業之間的契合度選擇工作 Social cognitive career theory (SCCT) 社會認知生涯論 職業選擇是 Bandura 社會認知理論的應用，特別是 self-efficac ...