課程名稱︰應用代數applied algebra
課程性質︰
課程教師︰陳君明
開課學院：
開課系所︰電機資工數學
考試時間︰2006.11.27
是否需發放獎勵金：是
（如未明確表示，則不予發放）
試題 :
Part I (3 points each)
1.Which statement about Stein's gcd algorithm is FALSE?
A.The fastest gcd algorithm known for computer implementation.
B."Algorithm B" in Knuth's "The Art of Computer Programming".
C.Stein's extended gcd algorithm also exists.
D.Based on the property gcd(a,b) = gcd(b,a mod b)
E.None of the above
2.Which statement about Two-out-of-Five based bar code is FALSE?
A.Two-out-of-five bar code uses 5 bars with 2 wide ones
B.Code 39 uses 4 interior spaces with 2 wide ones
C.U.S. postal code uses tall and short bars
D.Interleaved 2-out-of-5 is nearly twice as dense as 2-out-of-5
E.None of the above
3.Which code is shown in the figure? (考卷上有附圖)
A.Morse code
B.Hollerith code
C.Braille code
D.Two-out-of-five code
E.None of the above
4.Which group is isomorphic to the Klein-4 group?
A.(Z4,+)
B.(Z5*,X) X代表乘法
C.(Z10*,X)
D.({1.-1.i.-i},X)
E.None of the above
5.Which multiplicative group is NOT of order 36?
A.Z37*
B.Z76*
C.Z108*
D.Z126*
E.None of the above
6.An integer passed the Miller-Rabin test twenty time without finding
any witness of the compositeness. What is the best estimate of the
probability that it is a prime number?
A.(3/4)^20
B.(1/4)^20
C.1-(3/4)^20
D.1-(1/4)^20
E.None of the above
7.Which mapping is NOT a group homomorphism?
A.f:(Z,+)→(Z,+) defined by f(n) = 3n
B.f:(C*,X)→(C*,X) defined by f(a+bi) = a-bi
C.f:(Z6,+)→(Z13*,X) defined by f(n) = 2^n mod 13
D.f:(Z11*,X)→(Z5,+) defined by f(2^n mod 11) = n mod 5
E.None of the above
8.Which system of equation has NO solution?
A.x≡5 (mod54) x≡41 (mod72) x≡23 (mod77)
B.x≡4 (mod56) x≡37 (mod65) x≡46 (mod98)
C.x≡19 (mod55) x≡6 (mod81) x≡47 (mod91)
D.x≡26 (mod64) x≡9 (mod69) x≡53 (mod85)
E.None of the above
9.Which statement about Hilbert matrices is FALSE?
A.det(H2)=1/12
B.det(inverse of H3) = 2160
C.(Hn)i,j = ∫(0到1)X^(i+j-2).dx
(i+j) [n+i-1][n+j-1][i+j-2]
D.(inverse of Hn)i,j=(-1) (i+j-1)[ n-j ][ n-i ][ i-1 ]
(註解：-1的上面i+j表次方，後面的[]代表C幾取幾那個東西)
E.None of the above
10.Which statement about frequency analysis in English is FALSE?
A.The letter of highest frequency is T
B.The bigram of highest frequency is TH
C.The trigram of highest frequency is THE
D.There is only one letter with relative frequency greater than 10%
E.None of the above
Part II (3 points each)
●σ=(1457)(236) and τ=(17)(25)(346) are two elements of the symmetric
group S7
(1) σ inverse = ?
(2) στ= ?
(3) The group order |S7| = ?
(4) The order of the cyclic group generated by σ is ?
(5) Using Permutation Cipher,the plaintext ALGEBRA is encrypted by σ
to the cipher text _____
●Define T={x屬於Z : 111x+124y=gcd(111,124) for some y屬於Z}
(1)The smallest positive number in T is _____
(2)The biggest negative number in T is _____
●11^2006 mod 27 = ?
●The general solution to the equation 123x≡328 (mod 656)
is x≡____ (mod____)
where x is the smallest positive number among all posibilities.
(個人認為這題最後所說應該是指：你的答案(而非x)要是最小的正數)
●S={ A=[a11 a12] : det(A)≠0 and aij屬於Z5 for all i,j } (註：A為矩陣)
[a21 a22]
is a set of 2X2 invertible matrices with all computations modulo 5.
(1) There are _____ matrices with determinants equal to 1.
(2) There are _____ matrices in S which can be expressed as LU-decomposition
●Decode the UPC-A bar code printed on the right.
(有附圖與0-9的UPC-A bar code，所以不需要背只要會看即可)
●The smallest positive generator of the cyclic group (Z22*,X) is _____
●u=(01101101) and v=(10010100)
(1)The Hamming weight of u is ______
(2)The Hamming distance of u and v is _____
●Complete the algorithm of Miller-Rabin Test.
Input:An odd integer p>1,and an integer a with 1<a<p.
Output:A message that p is a composite, or p is a potential prime.
Factor p-1 = (2^t)m where m is odd
Set b = ______ mod p
If b≡正負1 (mod p) then declare p to be a potential prime and STOP
For i from 1 to t-1 Do
Set b = _____ mod p
If b=p-1 then declare p to be a potential prime and STOP
If b=1 then declare p to be a composite and STOP
End for loop
Declare p to be a composite
Part III (write down all details of your work)
●Prove that there are infinitely many primes of the form 4k+3 (4 pts)
●Decode the following words with the Hamming encoding matrix
[1 1 1 0 0 0 0]
[1 0 0 1 1 0 0]
H=[0 1 0 1 0 1 0] and the parity checking matrix [0 0 1]
[1 1 0 1 0 0 1] [0 1 0]
[0 1 1]
(1)Hamming (7,4) code: (0011011) P=[1 0 0]
(2)Hamming (8,4) code: (10100101) [1 0 1]
(3)Hamming (8,4) code: (01111001) [1 1 0]
[1 1 1]
Note that you have to find the original 4-bit messages
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 61.228.104.20