課程名稱︰資訊工程理論基礎 課程性質︰必修 課程教師︰呂育道 開課學院：電資學院 開課系所︰資工系 考試日期（年月日）︰2014.01.07 考試時限（分鐘）：180 是否需發放獎勵金：是 （如未明確表示，則不予發放） 試題 : Theory of Computation Final Examination on January 7, 2014 Fall Semester, 2013 Problem 1 (25 points) The Jacobi symbol (a | m) is the extension of the Legendre symbol (a | p), where p is an odd prime, and ╭ 0 if (p | a), │ (a | p) = ┤ 1 if a is a quadratic residue modulep, │ ╰ -1 if a is a quadratic nonresidue module p. k Recall that when m > 1 is odd and gcd(a, m) = 1, then (a | m) = Π (a | p_i). i=1 Please calculate (1234 | 99). Please write down all the steps leading to your answer. Ans: (1234 | 99) = (46 | 99) = (46 | 9) (46 | 11) = (1 | 9) (2 | 11) (11^2 - 1)/8 = 1 * (-1) 15 = (-1) = -1 Problem 2 (25 points) Show that if SAT has no polynomial circuits, then coNP ≠ BPP. (Hint: Adleman's theorem states that all languages in BPP have polynomialcircuits.) Ans: Assume that SAT has no polynomial circuits. As all languages in BPP have polynomial circuits by Adleman's theorem, NP ≠ BPP. Hence coNP ≠ coBPP = BPP. Problem 3 (25 points) Consider the sequence a_1, a_2, ... defined by n n n a_n = 2 + 3 + 6 - 1 (n = 1, 2, ...) Determine all positive integers that are relatively prime to every term of the sequence. (Hint: Fermat's little theorem says that for all 0 < a < p, a^(p-1) ≡ 1 mod p.) Ans: p-2 p-2 p-2 If p > 3 is a prime, then a_(p-2) = 2 + 3 + 6 ≡ 1 (mod p). To see this, multiply both sides by 6 to get p-1 p-1 p-1 3 * 2 + 2 * 3 + 6 ≡ 6 (mod p) which is a consequence of Fermat's little theorem. Therefore p divides a_(p-2). Also 2 divides a_1 and 3 divides a_2. So there is no number other than 1 that is relatively prime to all the terms in the sequence. Problem 4 (25 points) Let G = (V, E) be an undirected graph in which every node has a degree of at most k. Let I be a nonempty set. I is said to be independent if there is no edge between any two nodes in I. k-DEGREE INDEPENDENT SET asks if there is an independent set of size k. Consider the following algorithm for k-DEGREE INDEPENDENT SET: 1: I := ψ; 2: while ∃v ∈ G do 3: Add v to I; 4: Delete v and all of its adjacent nodes from G; 5: end while; 6: return I; Show that this algorithm fork-DEGREE INDEPENDENT SET is a (k/(k+1))-approximation algorithm. Recall that an ε-approximation algorithm returns a solution that is at least (1 - ε) times the optimum for maximization problems. Ans: Since each stage of the algorithm adds a node to I and deletes at most k + 1 nodes from G, I has at least (|V| / (k+1)) nodes, which is at least 1/(k+1) times the size of the optimum independent set because the size of the optimum independent set is trivially at most |V|. Thus this algorithm returns solutions that are never smaller than 1 - 1/(k+1) = k/(k+1) times the optimum. --

※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 1.160.217.112 ※ 文章網址: http://webptt.com/m.aspx?n=bbs/NTU-Exam/M.1416390058.A.DFD.html