99年私立長庚大學資工所離散數學

Zipf's law states that given some corpus (text database) of a natural language (like English, Chinese, …, etc), the occurrence frequency of any word is inversely proportional to its rank in the frequency table. Take the English language as an example, the top 10 most frequently used words are ranked as follows: (1) the, (2) of, (3) and, (4) a, (5) to, (6) in, (7) is, (8) you, (9) that, (10) it. Now, we design a discrete random variable X to represent the above 10 English works, for examples, "X = 1" represents the word "the"; "X = 2" represents the word "of"; …; "X = 10" represents the word "it", … etc. By Zipf's law, X will have the probability mass function (PMF) as follows:

Please answer the following questions:

1.

To make P_X(x) be a proper probability mass function (PMF), c = ?

Zipf's law states that given some corpus (text database) of a natural language (like English, Chinese, …, etc), the occurrence frequency of any word is inversely proportional to its rank in the frequency table. Take the English language as an example, the top 10 most frequently used words are ranked as follows: (1) the, (2) of, (3) and, (4) a, (5) to, (6) in, (7) is, (8) you, (9) that, (10) it. Now, we design a discrete random variable X to represent the above 10 English works, for examples, "X = 1" represents the word "the"; "X = 2" represents the word "of"; …; "X = 10" represents the word "it", … etc. By Zipf's law, X will have the probability mass function (PMF) as follows:

Please answer the following questions:

2.

Please plot the figure for P_X(x).

Zipf's law states that given some corpus (text database) of a natural language (like English, Chinese, …, etc), the occurrence frequency of any word is inversely proportional to its rank in the frequency table. Take the English language as an example, the top 10 most frequently used words are ranked as follows: (1) the, (2) of, (3) and, (4) a, (5) to, (6) in, (7) is, (8) you, (9) that, (10) it. Now, we design a discrete random variable X to represent the above 10 English works, for examples, "X = 1" represents the word "the"; "X = 2" represents the word "of"; …; "X = 10" represents the word "it", … etc. By Zipf's law, X will have the probability mass function (PMF) as follows:

Please answer the following questions:

3.

The cumulative distribution function (CDF) , please plot a figure for F_X(x).

Zipf's law states that given some corpus (text database) of a natural language (like English, Chinese, …, etc), the occurrence frequency of any word is inversely proportional to its rank in the frequency table. Take the English language as an example, the top 10 most frequently used words are ranked as follows: (1) the, (2) of, (3) and, (4) a, (5) to, (6) in, (7) is, (8) you, (9) that, (10) it. Now, we design a discrete random variable X to represent the above 10 English works, for examples, "X = 1" represents the word "the"; "X = 2" represents the word "of"; …; "X = 10" represents the word "it", … etc. By Zipf's law, X will have the probability mass function (PMF) as follows:

Please answer the following questions:

4.

What is the probability "X ≤ 5", i.e. P["X ≤ 5"] = ?

Zipf's law states that given some corpus (text database) of a natural language (like English, Chinese, …, etc), the occurrence frequency of any word is inversely proportional to its rank in the frequency table. Take the English language as an example, the top 10 most frequently used words are ranked as follows: (1) the, (2) of, (3) and, (4) a, (5) to, (6) in, (7) is, (8) you, (9) that, (10) it. Now, we design a discrete random variable X to represent the above 10 English works, for examples, "X = 1" represents the word "the"; "X = 2" represents the word "of"; …; "X = 10" represents the word "it", … etc. By Zipf's law, X will have the probability mass function (PMF) as follows:

Please answer the following questions:

5.

The expected number E[X] is defined as, please calculate it out, i.e., E[X] = ?

6.

Prove or disprove that there are infinitely many primes

7.

Find an inverse of 13 modulo 57.

8.

A computer system considers a string of decimal digits a valid codeword if it contains an even number of 0 digits. For instance, 1230407869 is valid, whereas 120987045608 is not valid. Let a_n be the number of valid n-digit codewords. Find a recurrence relation for a_n.

9.

How many ways are there to select five bills from a cash box containing $1 bills, $2 bills, $5 bills, $10 bills, $20 bills, $50 bills, and $100 bills? Assume that the order in which the bills are chosen does not matter, that the bills of each denomination are indistinguishable, and that there are at least five bills of each type.

10.

Find all solutions of the recurrence relation a_n = 3a_n−1 + 2_n. What is the solution with a₁ = 3?

11.

Suppose that a connected planar simple graph has 20 vertices, each of degree 3. Into how many regions is the plane divided by a planar representation of this graph?

12.

Proof that if G is a connected planar simple graph, then G has a vertex of degree not exceeding five. [Hint: e ≤ 3v − 6, where e represents the number of edges and v represents the number of vertices.]

13.

Suppose that a computer science laboratory has 15 workstations and 10 servers. A cable can be used to directly connect a workstation to a server. For each server, only one direct connection to that server can be active at any time. We want to guarantee that at any time any set of 10 or fewer workstations can simultaneously access different servers via directly to every server (using 150 connections), what is the minimum number of direct connections needed to achieve this goal?