資料結構-圖
考研相關文章參考資料為 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
正規語言相關文章參考資料為陳穎平教授上課講義
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
正規語言相關文章參考資料為陳穎平教授上課講義
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
正規語言相關文章參考資料為陳穎平教授上課講義
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
正規語言相關文章參考資料為陳穎平教授上課講義
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
正規語言相關文章參考資料為陳穎平教授上課講義
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 ...
正規語言-L1
正規語言相關文章參考資料為陳穎平教授上課講義
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(logn)O(\log n)O(logn)
最多比較次數為 Decision Tree (高度最小化的 BT) 之樹高
名詞區分
Worst case:
Binary Search: O(logn)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 ...









