103年 - 103 國立中山大學_碩士班招生考試_資工系(甲組)：離散數學#105841

科目： 中山◆資工◆離散數學 | 年份：103年 | 選擇題數：0 | 申論題數：19

試卷資訊

所屬科目： 中山◆資工◆離散數學

選擇題 (0)

申論題 (19)

1. (a) What is the Well-Ordering Principle?

(b) What is the Principle of Mathematical Induction?

(c) Please use the Well-Ordering Principle to prove that the Principle of Mathematical Induction is true?

(a) How many functions f:X→ Ysatisfy f(x₁)=?

(b) Let m Sn. How many functions f: X→ Yare one-to-one?

(c) Let m = n. How many bijective functions f: X→Y satisfy f(x₁) ≠y₁ ?

(d) How many relations are there from X to Y?

(e) How many relations R from X to Y satisfy x₁ R y₁ and x₂ R y₂?

(a)

(b)

(c)

4. Let I={0, 1} be the input alphabet and O = {0, 1} be the output aplphabet of a finite state machine that recognizes all strings in the language {0, 1}* {01} {0, 1}⁺. Please draw a state diagram for the finite state machine after minimization.

(a)

(b)(x⁷+x⁸+x⁹+...)⁹；

(c)

6. Consider the number of the partitions of a positive integer into positive summands without regard to order. For example, 4 = 1+1+1+1 = 1+1+2 = 2+2 = 1+3, so the integer 4 has five partitions. Find the generating function for the number of the partitions of a positive integer n into positive summands where each summand appears at most twice in each of the partitions. Please express your generating function in a closed form and indicate how to find the number of the partitions of n from your generating function.

7. Please compute , and y= ((w-x) mod 17), and then output (w, x, y).

(a) Please show that (

) is a commutative group.

(b) Prove that () is isomorphic to ().