99年國立成功大學工程科學所離散數學

Assume that there are n coplanar straight lines. No two of the lines are parallel and no three of the lines pass through a common point.

1.

Find a recurrence relation (or system) that describes the number of disjoint areas into which the lines divide the plane.

Assume that there are n coplanar straight lines. No two of the lines are parallel and no three of the lines pass through a common point.

2.

Solve the recurrence relation in (a).

3.

R is a relation on X. R is symmetric and transitive but not reflexive. Assume that |X| ≥ 2. Define the relation R' on X by: R' = X × X − R. Prove or disprove if R' is (a) reflexive, (b) symmetric, (c) anti-symmetric, (d) transitive.

4.

Design a nondeterministic finite-state machine that accepts all strings over {0, 1} that begin 01 and contain 110.

5.

Construct an optimal code for the set of letters in the table. (Hint: you can use Huffman code.)

6.

Suppose that there is a computer shop that offers a service to diagnosis computer virus. Suppose that approximately 15% of the customers' computers have the α virus. Furthermore, the computers that have the α virus, approximately 95% have the β virus. As for those which do not have α virus, 2% approximately have the β virus. Find the probability that a customer computer that has the α virus if it has the β virus.

7.

Suppose there are three persons who each randomly choose a personal computer among 12 consecutive personal computers in a computer classroom. What is the probability that the three chosen personal computers are consecutive?

8.

Show that NAND gate is a functionally complete set of gates.

9.

Use NAND gates only to design the exclusive-OR operation

10.

An international Standard Book Number (ISBN) uses 10 characters separated by dashes. An ISBN number consists of a group code, a publisher code, a code to uniquely identify the book and a check character. The check character is used to check the validity of an ISBN number. The check character is s mod 11, where s is the sum of the first digit plus two times the second digit plus three times the third digit, …, plus nine times the night digit. If the value is 10, use X for the check character. What is the check character for the ISBN 0-13-089008?

11.

Given that a, b, z, n are integers. It can be shown that
   ab mod z = [(a mod z)(b mod z)] mod z.
Use this formula to calculate 572²⁸ mod 713.

12.

Count exactly the number of critical operations in the pseudocode fragment. The critical operations are at lines 6, and 7.

13.

Then find the complexity reference function (big-O, or Θ) for the number of critical operations. For the big-O or Θ part, replace 30 by n.