理論電腦科學 Archives - Scientia Potentia Est

Scientia
理論電腦科學 , 計算理論
15 3 月, 2024
84 views

NP-Completeness

首先需要一個問題叫做布林公式(Boolean formula)會像：

$\phi = (\bar{x} \wedge y) \vee (x \wedge \bar{z})$

裡面的每一個符號稱作variable，每一個variable可以給0或1的值就像在做.

Scientia
理論電腦科學 , 計算理論
7 11 月, 2023
88 views

時間複雜度

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

Scientia
理論電腦科學 , 計算理論
5 11 月, 2023
136 views

不同的Turing Machine

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

Scientia
理論電腦科學 , 計算理論
4 11 月, 2023
135 views

Turing Machine

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

Scientia
理論電腦科學 , 資訊理論
31 10 月, 2023
182 views

熵 Entropy

我們在消息理論測量一段資訊所包含的資訊量其中一種會使用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)}]$

Scientia
理論電腦科學 , 資訊理論
31 10 月, 2023
173 views

資訊測量符號

測量一組資訊的方法有好幾種，例如像是使用entropy, mutual information, relative entropy等等方法，另外需要了解這些方法之間的交互作用。

Scientia
理論電腦科學 , 資訊理論
1 8 月, 2023
488 views

Mutual Information

mutual information用來測量兩個random variables之間的關係，主要是有多少資訊量被傳輸過去。其中一個random variable會告訴我有多少資訊量從另一個random variable傳過來。

Scientia
密碼理論 , 理論電腦科學
4 6 月, 2023
211 views

NIST美國國家標準與科技機構發起的Public Key公開金鑰加解密系統競賽，RSA (Rivest–Shamir–Adleman)加密演算法由三位密碼學家共同研究出來在1973年發表，最終獲選最早為公開金鑰系統標準之一，雖然後來英國Government Communications Headquarters(GCHQ)國家通訊總部說他們的英國密碼學家早在1970年就已經研究出Non-Secret Encryption這種非對稱式加解密系統，但不管怎麼說，RSA在當時算是非常突破性的成果。