中原大學九十學年度碩士班入學招生考試─資訊工程學系計算機數學

中原大學九十學年度碩士班入學招生考試

4月28日　　第2節　資工系	誠實是我們珍視的美德，我們喜愛「拒絕作弊，堅守正直」的你！
科目：計算機數學	（共3頁第1頁）

[10%] True or False:

(a)	Let where , then .
(b)	For all , .
(c)	Any subset of size 6 from the set must contain two elements whose sum is 10.
(d)	It is not possible to construct a finite state machine that recognizes precisely those sequences in the language .(Here the alphabet for L is .
(e)	.

[10%] How many integral solutions are there of if

and

Suppose that the recurrence relation of degree k is

, for

, and that

denotes a solution of the associated homogeneous recurrence relation,

denotes a particular solution to the inhomogeneous recurrence relation . Moreover,

denotes the characteristic polynomial of the associated homogeneous recurrence relation.
(a)[5%] List the general form of

when

.
(b)[5%] List the general form of

when

and

[10%]Solve the divide-and-conquer recurrence relation

where

, for

and

(a)[5%] Find a minimal spanning tree for the graph G in the following figure
(b)[5%] Prove or disprove: G is a planar graph.

The Linear Algebra part : Please use Chinese to answer questions 7-10, unless you are sure that the English you use is good English. (以下問題是有關線性代數，除了key words可用英文以外，你一定要用中文來回答。)

[15%] Yes/No questions (此題回答yes或no即可)

(a)	Does the cross product operation of vectors satisfy the associative law?
(b)	Does the cross product operation of vectors satisfy the commutative law?
(c)	Does the cross product operation of vectors satisfy the distributive law (over vector addition)?
(d)	Can we express any two-dimensional vector (e.g., [6, 7]) as a linear combination of the four vectors [1, 2], [3, 4], [-5, -7], and [-3, -1]?
(e)	Let A and B be two matrices (A is n by m, while B is m by s; that is, they are multipliable). AB = 0 if and only if at least one of A and B is 0. Yes or no?

Please answer the following.

(a)	[5%] There are three vectors : [a1, b1], [a2, b2], and [a3, b3]. We only know that a1, b1, a2, b2, a3, and b3 are real values, but we do not know what these values are. Nevertheless, we are sure that these three vectors must be linearly dependent. Why are we so sure of it?
(b)	[5%] Is cos(x) and sin(x) linearly dependent or linearly independent? Why?

[5%] How do we know that a vector space is of dimension n (that is, what is the definition of an n-dimensional vector space)?

Please answer the following.

(a)	[5%] Give a real-world example (i.e., give a description of a problem) in which what we want to compute is the dot product (the inner product) of two vectors.
(b)	[5%] Give a real-world example (i.e., give a description of a problem) in which what we want to compute is the cross product of two vectors.

10.

[10%] A mixed triple product is of the form a ．(b×c), where a, b and c are three vectors. Suppose a, b and c are vectors in a three-dimensional vector space. We know that the following hold.

Proposition 1 : The mixed triple product of a, b and c is the volume of the parallelepiped space (平行六面體) formed by a, b and c.

Proposition 2 : a, b and c are linearly dependent if and only if a ．(b × c) = 0.

Question for you : Please use Proposition 1 (and properties of linear independence/dependence) to explain why Proposition 2 should hold.

--- END---