douobb

Computer Security ConceptsCIA TriadConfidentiality Assurance Data confidentiality: 私人或機密資訊不會洩漏給未經授權的人 Privacy: 個人可以控製或影響與其相關的信息是否被蒐集和儲存 Requirements 對資訊存取與揭露的授權限制 保護個人隱私與專有資訊的方法 Definition of Loss 資訊在未經授權的情況下被揭露 Integrity Assurance Data integrity: 資訊與程式只能以指定且經授權的方式被修改 System integrity: 系統能在未受損的狀態下，正常執行其預期功能 Requirements 防止資訊被不當修改或刪除 確保資訊的不可否認性與真實性 不可否認性 (non-repudiation): 送出訊息的人不能事後否認 Definition of Loss 資訊在被經授權的情況下被修改或刪除 Availability Assurance 系統能夠即時運作，且不會拒絕授權使用者的服務請求 Requireme ...

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

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

考研相關文章參考資料為 wjungle 大神提供的筆記 Array 元素之位置一維陣列 $A: array[l…u]$ of items 共有 $u - l + 1$ 格 起始位置: $l_0$ 元素大小: $d$ $A[i]$ 的位置: $l_0 + (i - l) * d$ 二維陣列 $A: array[l_1…u_1, l_2…u_2]$ of items 有 $u_1 - l_1 + 1$ 列，$u_2 - l_2 + 1$ 行 Row-major $A[i, j] = l_0 + [(i - l_1) (u_2 - l_2 + 1) + (j - l_2)] d$ Column-major $A[i, j] = l_0 + [(j - l_2) (u_1 - l_1 + 1) + (i - l_1)] d$ N 維陣列 $A: array[l_1…u_1, l_2…u_2, l_3…u_3, … , l_n…u_n]$ of items 令 $k_m = u_m - l_m + 1 (m = 1,2,…,n)$ Row-major (由左往右) ...

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

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

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

正規語言相關文章參考資料為陳穎平教授上課講義 L5 ReducibilityIf 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定義 $HALT_{TM} = { ⟨M, w⟩~|~M~is~a~TM~and~M~halts~on~input~w }$ Theorem $HALT_{TM}$ is undecidable. 證明: 假設 $HALT{TM}$ 的 de ...

正規語言相關文章參考資料為陳穎平教授上課講義 L4 DecidabilityDecidable LanguagesDecidable Problems Concerning Regular Languages定義 $A_{DFA} = { ⟨B, w⟩~|~B~is~a~DFA~that~accepts~input~string~w }$ Theorem $A_{DFA}$ is a decidable language. 證明: 建立一個 TM $M$ 模擬 $w$ 在 $B$ 上的行為，如果停在 accept states 則 $A_{DFA}$ appect，否則會 reject，只有這兩種可能，因此是 Decidable 的 定義 $A_{NFA} = { ⟨B, w⟩~|~B~is~a~NFA~that~accepts~input~string~w }$ Theorem $A_{NFA}$ is a decidable language. 證明: 建立一個 TM $N$，並建立與 $B$ 等價的 DFA $C$，可以將 $⟨C, w⟩$ 帶入 TM $M$ ...

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