課程名稱︰自動機與形式語言
課程性質︰必帶
課程教師︰林智仁
開課學院：電機資訊學院
開課系所︰資訊工程學系
考試日期（年月日）︰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