→ rod24574575 : 已收資訊系精華區! 08/23 17:35
課程名稱︰離散數學
課程性質︰選修
課程教師：呂育道
開課學院：電資學院
開課系所︰資工系
考試日期（年月日）︰2014.06.19
考試時限（分鐘）：
試題 :
Discrete Mathematics
Examination on June 19, 2014
Spring Semester, 2014
Note: You may use any results proved in the class unless stated otherwise.
Problem 1 (10 points)
Determine the sequence generated by the following generating functions:
1) (5 points) 1 / (3 - x)
2) (5 points) x / (1 - x)^2
Ans:
1) 1, 1/3, (1/3)^2, …
2) See p. 452 of the slides.
Problem 2 (10 points)
Solve the following recurrence relations:
1) (5 points) a_(n+2) = a_(n+1) + a_n, a_0 = 1, a_1 = 1/2.
2) (5 points) a_n + 2a_(n-1) + 2a_(n-2) = 0, n ≧ 2, a_0 = 1, a_1 = 3.
Ans:
1 ╭╭ 1 + √5 ╮n ╭ 1 - √5 ╮n ╮
1) a_n =──││──── │ + │──── │ │. (The steps are similar to
2 ╰╰ 2 ╯ ╰ 2 ╯ ╯
pp. 531-533 of the slides.)
n ╭ 3nπ ╮ ╭ 3nπ ╮
2) a_n = (√2) (cos│───│ + 4sin│───│). (The steps are similar to
╰ 4 ╯ ╰ 4 ╯
pp. 553-554 of the slides.)
Problem 3 (10 points)
Solve the recurrence relation a_n - 3a_(n-1) = n with a_0 = 1 by the
generating function method.
Ans:
See pp. 588-591 of the slides.
Problem 4 (10 points)
1 + √(1 + 8 * |E|)
Let G = (V, E) be an undirected graph. Show that |V| ≧ ───────────
2
Ans:
See p. 621 of the slides.
Problem 5 (10 points)
Let G = (V1, V2, E) be a connected bipartite undirected graph. Show that if
|V1| ≠ |V2|, then G has no Hamiltonian cycles.
Ans:
The nodes on a Hamiltonian cycle in G must alternate between nodes in V1 and
those in V2 as G is bipartite. As the cycle must exhaust all nodes,
|V1| = |V2|.
Problem 6 (10 points)
Let T = (V, E) be a tree. Show that T is planar.
Ans:
See p. 696 of the slides.
Problem 7 (10 points)
Let T = (V, E) be a rooted binary tree and |V| = n.
1) (5 points) Determine the maximum height that T can attain.
2) (5 points) If T is complete and n is odd, what is the maximum height that
T can attain?
Ans:
1) n - 1
2) (n - 1) / 2
Problem 8 (10 points)
Let (R, +, ·) be a ring. Show that a unit in a ring R cannot be a proper
divisor of zero. (Recall that if there exists z ∈ R such that
z + a = a + z = a for every a ∈ R, then z is called a zero. Note that such z
is unique. For any a ∈ R, if there is one element b ∈ R where a·b = z or
b·a = z, then a is called a proper divisor of zero. For any a ∈ R, if there
is an element u ∈ R such that a·u = u·a = a, then u is called a unit.)
Ans:
See p. 725 of the slides.
Problem 9 (10 points)
Let n be any positive integer. Show that the congruence modulo n is an
equivalence relation on Z. (Recall that a relation is an equivalence one if it
is reflexive, symmetric and transitive.)
Ans:
It suffices to verify the reflexive, symmetric, and transitive properties. Let
a, b, c ∈ Z.
1) (Reflexivity) a - a = 0 and n divides 0, so a ≡ a mod n.
2) (Symmetry) Let a ≡ b mod n. Then a - b = kn for some integer k.
b - a = -(a - b) = -kn, so n divides b - a and b ≡ a mod n.
1) (Transitivity) Let a ≡ b mod n and b ≡ c mod n. Then a - b = kn and
b - c = k'n for some integers k, k'. So, a - c = (k + k')n and
a ≡ c mod n.
Problem 10 (10 points)
Show that every group of prime order is cyclic.
Ans:
Pick any element a ≠ e of the group G. Note that o(a) > 1. As o(a) divides
|G|, a prime number, o(a) = |G|. This implies that every b ∈ G must be of the
form a^k for some k ∈ Z.
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 61.228.146.150
※ 文章網址: https://www.ptt.cc/bbs/NTU-Exam/M.1440322440.A.5DA.html