amzshar

..

最近收到好幾封不同人寄ㄉ一樣的 mail
　
半棵大陸妹
　
...

...
　
...
　

.

.

P, NP, coNP, NP-COMPLETE, NP-HARD
　
[ class P ] : 可以用 Polynomial 演算法解決的問題，亦即解決時間為 Polynomial time.
DEFINITION : The class of languages that are Decidable in Polynomial time
　　　　　　　on a Deterministic single-tape Turing Machine.
=> 在 Deterministic 單 tape TM 上, 所有多項式時間內可解的 Decidable 語言所成的集合.
=> 多項式時間, 亦即 t(n), 也就是 n 的 k 次方
　
Example：
　1. PATH(有向圖的路徑問題) ∈ P
　2. RELPRIME(互為質數問題) ∈ P
　3. CFL(Every Context-free language) ∈ P
　
[ class NP ] : 可以用 Non-deterministic Polynomial 演算法解決的問題.
DEFINITION : The class of languages that have Polynomial time Verifiers.
THEOREM : A language is in NP iff it is decided by some Non-deterministic Polynomial time Turing Machine.
=> 在 Nondeterministic TM (NTM N) 上, 多項式時間內可解的 Decidable 語言所成的集合.
=> Nondeterministic 就是 多管齊下 ! 而 Verifying is easy, Determinig is hard.
　
Example :
　1. CLIQUE (k-clique : Graph裡有k個nodes, 是彼此相連的) ∈ NP
　　亦即 CLIQUE = { G is an undirected graph with k-clique } ∈ NP
　
　　(Proof : The clique is the certificate. )
　　V = "On input < , c > :
　　　　　1. Test whether c is a set of k nodes in G
　　　　　2. Test Whether G contains all edges connecting nodes in c
　　　　　3. If both pass, ACCEPT; Otherwise, REJECT."
　　　(Proof : by NTM. )
　　N = "On input , where G is a graph :
　　　　　1. Nondeterministically select a subset c of k nodes of G
　　　　　2. Test whether G contains all edges connecting nodes in c
　　　　　3. If yes, ACCEPT; Otherwise, REJECT."
　
　2. SUBSET-SUM Problem (子集之和) ∈ NP
　　亦即 SUBSET-SUM = { S = {x1, ...,xk} and for some {y1,...,yk} ⊆ {x1,...,xk}, we have ∑ yi = t } ∈ NP
　　( 比如說：S = < { 2, 3, 8, 31, 40, 44 }, 45 > 中, 因為 3 + 3 + 8 + 31 = 45 ... 所以 S 就是 SUBSET-SUM )
　　(Proof : The subset is the certificate. )
　　V = "On input < , c > :
　　　　　1. Test whether c is a collection of numbers that sum to t
　　　　　2. Test whether S contains all the numbers in c
　　　　　3. If both pass, ACCEPT; Otherwise, REJECT."
　
　　(Proof : by NTM. )
　　N = "On input :
　　　　　1. Nondeterministically select a subset c of the numbers in S
　　　　　2. Test whether c is a collection of numbers that sum to t
　　　　　3. If the test pass, ACCEPT; Otherwise, REJECT."
　
[ class coNP ] : which contains the languages that are complements of languages in NP. (NP的補數)
　
[ P vs NP ] :
　 P = the class of languages for which membership can be DECIDED quickly.
　NP = the class of languages for which membership can be VERIFIED quickly.
　
[ P = NP ? ] 或是 [ P ≠ NP ? ] :
This is the greatest unsolved problems in Theoretical Computer Science and Contemporary Mathmatics.
　
[ NP-COMPLETE ] :
DEFINITION : A language B is NP-complete if it satisfies two conditions :
　　　　　　1. B is in NP, and
　　　　　　2. every A in NP is polynomial time reducible to B. (此2.亦即 NP-Hard)
　
[ Polynomial time mapping reducible ] :
DEFINITION : Language A is Polynomial Time Mapping Reducible to language B, written A ≤p B ,
　　　　　　　if a Polynimial time computable function f : ∑* -> ∑* exists, where for every w,
　　　　　　　w ∈ A <=> f(w) ∈ B
　　　　　　　The function f is called the Polynomial time reduction of A to B.
=> This is also called [ Polynomial Time Reducible ] or [ Polynomial Time many-one reducibility ]
　
[ NP-Hard ] :
Every A in NP is polynomial time reducible to B.
=> 任何 Language in NP 問題, 都可 Polynomial time reducible to B
=> 若一 Problem, 是 NP Problem, 又是 NP-Hard Problem, 則就是NP-Complete Problem.
　

...

暑修的成績公布了，得了 95 分 ... 哇哈哈～ 還蠻開心的 ...

一轉眼，碩二上學期也已經過了 1/3 ，
這學期修了最後一門 Formal Language (正規語言)，
是研究 Automata 的一門學科 ...
其中的 δ：Transition function 對研究的"非同步電路設計"應該很有幫助。

目前正在搞 ：
Regular Language(RL)、Finite Automata(FA)、
NonDeterministic Finite Automaton(NFA)、
NonRegular Language (Pumping Lemma、Myhill-Nerode Theorem)、
Contrxt-Free Grammer(CFG)、Context-Free Language(CFL)、
PushDown Automata(PDA)、
Non-Context-Free Language、
以及後面ㄉ Church-Turing Thesis (Tuning Machines) ... 等等

目前的戰績是 21 學分，剩 3 學分：
942 Embedded O.S. Design (嵌入式系統設計)
951 Operating System (作業系統)
953 Asynchronous Circuit Design (非同步電路設計)
961 Computer Architecture (計算機結構)
962 Advanced Database Management System (高等資料庫管理系統)
962 Multimedia Information System (多媒體資訊系統)
963 Computer Operations, Organization and Categorization (計算機運算與組織)

希望一切都順順利利 ... : )