阿摩線上測驗
登入
首頁
>
交大◆資工◆線性代數與離散數學
>
104年 - 104 國立交通大學_碩士班考試入學試題_資訊聯招：線性代數與離散數學#113284
> 申論題
題組內容
4. In the following questions, just give the answer, do not give any explanation.
(c) (4 points) Suppose A is a set with n symbols, IAI = n. Find the number of symmetric binary relations on A.
相關申論題
(a) (4 points) Given the premisesWhat 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.
#484107
(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
#484108
(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?
#484109
(d) (4 points) Find all solutions, if any, to the system of congruences.
#484110
2. (a)(4 points) Give a recursive definition of the set S of odd integers.
#484111
(b) (5 points) Prove by induction that for all n ∈ Z, 2n + 1 ∈ S, where Z is the set of integers.
#484112
(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?
#484113
(b) (3 points) What is the largest value of n for which Kn (a complete graph on n vertices) is planar?
#484114
(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.
#484115
(a) (4 points) an, = 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 a1.
#484116
相關試卷
104年 - 104 國立交通大學_碩士班考試入學試題_資訊聯招：線性代數與離散數學#113284
104年 · #113284
阿摩線上測驗
登入
阿摩線上測驗
登入