課程名稱︰離散數學
課程性質︰
課程教師︰雷欽隆教授
開課學院：
開課系所︰電機系
考試日期（年月日）︰2007/4/27
考試時限（分鐘）：100mins
是否需發放獎勵金：是
（如未明確表示，則不予發放）
試題 :
1.(15pts)
In the questions below suppose the variable x represents students,
y represents courses, and T(x,y) means "x is taking y". Match the English
statements with all its equivalent symbolic statement in this list:
(以下以A代表for any,以E代表there exist,_代表negation)
(1)ExAyT(x,y)
(2)EyAxT(x,y)
(3)_ExEyT(x,y)
(4)AxEyT(x,y)
(5)_AxEy_T(x,y)
(6)AyExT(x,y)
(7)EyAx_T(x,y)
(8)_AxEyT(x,y)
(9)_EyAxT(x,y)
(10)AxEy_T(x,y)
(11)_Ax_Ay_T(x,y)
(12)ExAy_T(x,y)
(a) Every courses is being taken by at least one student.
(b) Some students are taking no courses.
(c) No student is taking all courses.
2.(10pts)
Prove that there are infinitely many primes.
3.(10pts)
Let f:{1,2,3,4,5}→{1,2,3,4,5,6} be a function.
(a)How many total functions are there?
(b)How many of these functions are one-to-one?
4.(10pts)
For each of the following functions,find its inverse if it exists.
f:Z→Z where f(x) = x mod 10
g:R→R where g(x) = 3x-5
h:R→R where h(x) = floor[2x]
5.(5pts)
Let F = {⊕|⊕ is an n-ary Boolean operator}. What is the cardinality of F.
6.(10pts)
Let N denote the set of natural numbers. Show that N×N has the same
cardinality as N.
7.(10pts)
One of the following five statements is true. Find it out and prove it.
(a)A-(B-C)=(A-B)-C
(b)A∪(B∩C)=(A∪B)∩(A∪C)
(c)(A-C)-(B-C)=A-B
(d)A∩(B∪C)=(A∪B)∩(A∪C)
(e)If A∪C=B∪C,then A=B
8.(10pts)
Let S={a,b,c} be the set of alphabet. What is the cardinality of S^3?
What is S*?
9.(10pts)
Consider the series {a_n}=a_0,a_1,...,where a_0=a_1=1,and for any n≧2,
a_n=f(n)=a_n-a+a_n-2. What is f(10)? Consider the following programs f1
and f2,what are the relationship among the values f(100),f1(100) and f2(100)
Function f1(n:integer):integer;
begin
if n≦1 then return 1
else return (f(n-1)+f(n-2))
end.
Function f2(n:integer):integer;
var a,b,i:integer;
begin
a:=1;
b:=1;
for i:=2 to n do begin b:=a+b;a:=b-a end;
return b
end.
10.(10pts)
Rank the following functions by the order of their growth rates from smallest
to largest using the Big-O notation.
(a)(1+1/n)^n
(b)(log n)!
(c)(log n)^2007
(d)n^1.001
(e)log(n!)
(f)1.001^n
11.(10pts)
Find the "best" big-oh notation to describe the complexity of the algorithm
below.
(a)A binary search of n ordered elements.
(b)An algorithm that lists all ways to put the numbers 1,2,3,... in a row
(c)A linear search to find the smallest numbers in a list of n numbers.
(d)An algorithm that prints all bit strings of length n.
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 61.228.106.117