104年 - 104 國立交通大學_碩士班考試入學試題_資訊聯招：線性代數與離散數學#113284

What is the weakest condition for Q(a,b) to be true? That is, write down the weakest formula F(≠Q(a,b)) such that F → Q(a,b) is a logical consequence of the premises.

(b) (4 points) For each pair of sets below, determine if |A| ＜ |B|, |A| = |B|, or |A| ＞ |B|

(N.B. N is the set of natural numbers.)

1) A = The set of all computable functions from N to N. B = The set of all uncomputable functions from N to N.

2) A = The set of all C++ programs that terminate. B = The set of all C++ programs that don't terminate

(c) (4 points) Consider the following primality testing algorithm based on Fermat's little theorem function

FermatPrimalityTest(n,k)

Given the smallest Carmichael number 561 = 3ㆍ11ㆍ17, what is the probability that the call FermatPrimalityTest(561,1) returns true?

(d) (4 points) Find all solutions, if any, to the system of congruences.

2. (a)(4 points) Give a recursive definition of the set S of odd integers.

(b) (5 points) Prove by induction that for all n ∈ Z, 2n + 1 ∈ S, where Z is the set of integers.

(a) (3 points) A computer randomly prints three-digit codes, with no repeated digits in any code (for example, 387, 072, 760). What is the minimum number of codes that must be printed in order to guarantee that at least five of the codes are identical?

(b) (3 points) What is the largest value of n for which K_n (a complete graph on n vertices) is planar?

(c) (3 points) If the permutations of 1,2,3,4,5,6 are written in lexicographic order, with 123456 in position #1, 123465 in position #2, etc., find the permutation in position #484.

(a) (4 points) a_n, = the number of bit strings of length n with an even number of 0s. Describe the sequence recursively. Include initial condition and assume that the sequence begins with a₁.

(b) (4 points) Find the number of ways in which nine identical blocks can be given to four children, if the oldest child gets at most three blocks.

(c) (4 points) Suppose A is a set with n symbols, IAI = n. Find the number of symmetric binary relations on A.

(d) (4 points) How many non-isomorphic simple undirected graphs with 5 vertices and 3 edges?

(a) (2 points) Which statements are always false?

(b) (2 points) Which statements are al ways true?

(c) (2 points) Which statements are equivalent to the statement (B)?

(d) (2 points) What does the statement (L) imply about L?

6. (5 points) Assume A, B, and C are respectively m✕p, p✕q, and q✕n matrices, and M = ABC. Let M^kl = a_kc^l for 1 ≤ k ≤ p and 1 ≤ l ≤ q, here a_k and c^l respectively denote the k-th column vector of A and the I-th row vector of C. Prove that

(a) (4 points) Find the matrix representation of L with respect to the bases B₁ and B₂.

(b) (4 points) Find the (coordinate) transition matrix from the basis B₂ to the basis B₃.

(e) (4 points) Solve

8. (10 points) If A is a real symmetric matrix, find a matrix V such that VAV^T = I. You need to prove your answer is correct.

(a) (9 points) Find an orthonormal basis for the subspace spanned by 1, x, and x².

(b) (6 points) Find the best quadratic least squares approximation to e^x on [-1,1].

104年 - 104 國立交通大學_碩士班考試入學試題_資訊聯招：線性代數與離散數學#113284

試卷資訊

選擇題 (0)

申論題 (24)