Scientia, Author at Scientia Potentia Est

Scientia
Computational Complexity
Space Complexity
10 11 月, 2023
0 Comments

空間複雜度

定義1：存在一組Deterministic Turing Machine M對於所有的輸入language會停住，M的space complexity可以用一個function f表達，f:[latex]N \rightarrow N[/latex], 而[latex]f(n)..

Scientia
Computational Complexity
NP-Complete
9 11 月, 2023
0 Comments

NP-completeness

首先需要一個問題叫做布林公式(Boolean formula)會像：$$\phi = (\overline{x} \wedge y) \vee (x \wedge \overline{z})$$裡面的每一個符號稱作variable，每一個variable可以給0或1的值就像在做布..

Scientia
Big-O
NP Class
7 11 月, 2023
0 Comments

時間複雜度

通長在測量複雜度的時候會使用兩種分析方法：Worst-case analysisAverage-case analysis定義一個M是Deterministic Turing Machine並且會根據輸入決定停止規範M的執行時間或者時間複雜度可以表示成一個function…

Scientia
Enumerator
Non-Deterministic
5 11 月, 2023
0 Comments

不同的Turing Machine

讓Turing Machine擁有多組tape
[latex]\delta: Q \times \Gamma^{k} \rightarrow Q \times \Gamma^{k} \times {L, R}^{k}, k[/latex]: tapes的數量…

Scientia
Computational Complexity
Turing Machine
4 11 月, 2023
0 Comments

Turing Machine

圖靈機是由Alan Turing在1936年提出的概念，現今世界上所有的計算機不管是多複雜的架構都可以使用圖靈機的概念設計出來，其主要核心精神如下圖

Scientia
Entropy
熵
31 10 月, 2023
0 Comments

我們在消息理論測量一段資訊所包含的資訊量其中一種會使用Entropy來計算。讓X作為一個discrete R.V. 並且表示成P(X)可以視作:$$H_{b}(X) = -\sum_{x \in \mathbb{X}} P(x) \cdot log_{b}P(x) = \mathbb{E}[-log_{b}P(X)] = \mathbb{E}{p} [log_{b}\frac{1}{P(x)}]$$