課程名稱︰ 自動機與形式語言
課程性質︰ 資工系必修
課程教師︰ 林智仁
開課學院： 電機資訊學院
開課系所︰ 資訊工程學系
考試日期（年月日）︰ 2009/01/15
考試時限（分鐘）： 90分鐘
是否需發放獎勵金： 是，謝謝
（如未明確表示，則不予發放）
試題 :
1.(15%) Explain if the following description is correct or not.
Let Σ be the alphabet of a Turing machine. We consider any binary sequence
such as
10101111...
Any such sequence is in Σ*. Using the diagonalization method, the set
of all infinite binary sequseces is countale. Therefore, Σ* is uncountable.
2.(15%) We define Primality = {n 屬於 N | n is a prime}. Explain is the
following description is correct or not.
We can test whether a number n is a prime by dividing n by
1,2,3,...,√(n)
√(n) = n^(1/2) = O(n^2). Therefore Primality 屬於 P.
3.(15%) Is EQ(DFA) 屬於 P or not?
4.(20%) Answer if the following statement is correct or not. Explanation is
needed. You cannot just say yes or no.
(a) If f(n) = 2^(O(t(n))), then [f(n)]^2 = 2^(O(t(n))).
(b) If f(n) = o(2^(2n)), then f(n) = o(2^n).
5.(15%) We know that small-o notation is defined in the following way : f(n) =
o(g(n)) if
f(n)
lim------------- = 0.
n->∞ g(n)
From the definition of limit, this means
對於所有 c ﹥0, 存在一個 N, 對於所有的 n ≧ N,
f(n)
==> ---------- < c.
g(n)
If
f(n) = n and g(n) = 3^n,
how do you find N to make the above statement correct?
─
6.(15%) We define co-NP = { L = L 屬於 NP}.
Is Primality 屬於 co-NP ? You can not use the fact 〝Primality 屬於 P〞 in your
explanation.
7. (a) (5%) Calculate 5281 X 77773 = ?
(b) (Bonus 5%) p ≦ q are primes and p X q = 203447, find p and q.
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.112.91.80