课程名称︰自动机与形式语言 课程性质︰必带 课程教师︰林智仁 开课学院：电机资讯学院 开课系所︰资讯工程学系 考试日期（年月日）︰2013/01/08 考试时限（分钟）：90分钟 是否需发放奖励金：是 （如未明确表示，则不予发放） 试题 : *Please give details of your answer. A direct answer without explanation is not counted. *Your answers must be in English. *Please carefully read problem statements. *During the exam you are not allowed to borrow others' class notes. *Try to work on easier questions first. Problem 1 (15 pts) Is (log n)^3 =o(n) ? You can either use the formal definition of limit or calculate lim (log n)^3 / n ---(1) n→∞ However, you must show your steps of calculating (1) rather than just give your answer. We assume natural log here. Problem 2 (30 pts) 1.Assume f1(n)=O(g1(n)) and f2(n)=O(g2(n)). Is f1(n)*f2(n)=O(g1(n)*g2(n)) ? 2.Assume f1(n)=o(g1(n)) and f2(n)=o(g2(n)). Is f1(n)+f2(n)=o(g1(n)+g2(n)) ? You need to formally prove your answer. Problem 3 (15 pts) If f(n)=2^O(1) then is f(n)=O(1) ? Give a formal proof or a counter example. Problem 4 (10 pts) Give an example which is not Turing-recognizable. You need to explain why. Problem 5 (15 pts) If A and B are Turing-recognizable, is A。B Turing-recognizable? Please prove it or give a counter example. Problem 6 (15 pts) If A is Turing-decidable, is A* Turing-decidable? Please prove it or give a counter example. Problem 7 (5 or -10 pts) In Chapter Seven(or in the lecture) we mentioned one of the greatest unsolved computer science problem. What is it? If you correctly answer this question, you get 5 points. Otherwise, you get -10 points. Problem 8 (5 or 25 pts) 1.(5 pts) Calculate 38,239*7,283. 2.(Bonus 20 pts) Find 33,742,691=p*q, where p,q>1 and p,qεN. If you think your solution is correct, you need to let TAs know during the exam. They will give you another similar problem. If both are correct, you get the bonus 20 points. --

※ 发信站: 批踢踢实业坊(ptt.cc) ◆ From: 140.112.244.207