h23w1.dvi

Size: px

Start display at page:

Download "h23w1.dvi"

さあしゃまるこ
4 years ago
Views:

1 24 I :00 12:30 1),. Do not open this problem booklet until the start of the examination is announced. 2) 3.. Answer the following 3 problems. Use the designated answer sheet for each problem. 3). Do not take this problem booklet or any answer sheet out of the examination room.. Write your examinee s number in the box below. No.

2 blank page) Usable for memos; do not detach. 2

3 blank page) Usable for memos; do not detach. 3

4 1 3 x,y,z),y,z ) 4 4 M x x y z = M y z 1 1 M Tt x,t y,t z ) : t x,t y,t z ) R x cos θ,sinθ) : x θ R y cos θ,sin θ) : y θ R z cos θ,sinθ) : z θ 1) 4 4 Tt x,t y,t z ),R x cos θ,sinθ),r y cos θ,sin θ),r z cos θ,sinθ) x x 0 l x = y y 0 l y = z z 0 l z θ P lx 2 + l2 y + l2 z = 1 l x,l y,l z ) P A B C D A x xz B y z C z θ D 2) A 3) B 4) C 5) P A B C D 4

5 Problem 1 Let us represent a transformation from 3D coordinates x,y,z) to x,y,z ), using their homogeneous coordinate representations and a 4 4 matrix M as follows. x y z 1 = M We consider the following matrices as the transformation matrix M. Tt x,t y,t z ) : translation by a 3D vector t x,t y,t z ) R x cos θ,sinθ) : rotation by an angle θ about the x-axis x y z 1 R y cos θ,sin θ) : rotation by an angle θ about the y-axis R z cos θ,sinθ) : rotation by an angle θ about the z-axis Assume that the coordinate system is right-handed and the positive rotation angle is directed counter-clockwise when we see the corresponding coordinate axis from the positive to the negative direction. Answer the following questions. 1) Write the elements of the 4 4 matrices Tt x,t y,t z ),R x cos θ,sinθ),r y cos θ,sin θ) and R z cos θ,sinθ). Next we consider the transformation matrix P for rotation by an angle θ about the rotation axis defined by x x 0 = y y 0 = z z 0. l x l y l z Here l 2 x + l 2 y + l 2 z = 1 and the vector l x,l y,l z ) is the rotation axis positive direction. The matrix P can be expressed using the following matrices A,B,C and D. A represents the translation so that the rotation axis passes through the origin of the coordinate system, B represents the rotation about the x-axis so that the rotation axis lies on the xz-plane, C represents the rotation about the y-axis so that the rotation axis lies along the z-axis, and D represents the rotation by the angle θ about the z-axis. 2) Write the elements of A. 3) Write the elements of B. 4) Write the elements of C. 5) Express the matrix P using A,B,C, and D. 5

6 2 b 1 b b + 1= b ) t,t 1,t 2,v,b 0 ) t t + 1 ) = ) ) att,v,b) got,b) t,t 1,t 2 ID v ID b b 1 b b ) att,v,b) t v b got,b) t b b v b v b Φ att,v,b) t 1 t1 t att 1,v,b ) ) 1) 3 Φ 1,Φ 2,Φ 3 Φ 1 Φ 2 Φ 3 Φ ) Φ 1 : att,v,b) got,b) t1 t1 t att 1,v,b ) ) Φ 2 : att,v,b) t 1 t1 t got 1,b) ) Φ 3 : att,v,b) t 1 t2 t2 t t 1 t 2 ) att 2,v,b ) ) t 2 t2 t t 1 t 2 ) att 2,v,b) ) ) 2) 3 Φ 1,Φ 2,Φ 3 3) Φ 3 Φ 1 Φ 2 Φ Φ 1 Φ 2 Φ 6

7 Problem 2 We are to describe specifications of a train control system in a first-order theory of non-negative integers. The target system controls trains by signals. The track is divided into blocks; and there is a signal at the end of each block. Block b 1 Block b Block b + 1= b ) The first-order theory comes with the following symbols. Variables: t,t 1,t 2,v,b and so on Symbols for non-negative integers: 0 a constant), the successor function; t means t + 1), = equality) and inequality) Predicate symbols for describing specifications introduced later): att,v,b) and got,b) We shall represent time by t,t 1,t 2 ; a train s identifier by v; and a block s identifier by b. We assume that b increases by 1 in the direction of the trains movement. Therefore, a train at the block b is expected to move ahead to the block b. Following those conventions, we introduce the following predicate symbols. att,v,b): the train v is at the block b at time t got,b): at time t, the signal between the blocks b and b says go Now, the following specification if the train v is at the block b, the train v will eventually move to the block b can be formally described as follows. Answer the following questions. Φ : att,v,b) t 1 t1 t att 1,v,b ) ) 1) Prove that the following three formulas Φ 1,Φ 2 and Φ 3 satisfy Φ 1 Φ 2 Φ 3 Φ. ) Φ 1 : att,v,b) got,b) t1 t1 t att 1,v,b ) ) Φ 2 : att,v,b) t 1 t1 t got 1,b) ) Φ 3 : att,v,b) t 1 t2 t2 t t 1 t 2 ) att 2,v,b ) ) t 2 t2 t t 1 t 2 ) att 2,v,b) ) ) 2) Describe in English or Japanese) the meaning of each of the formulas Φ 1,Φ 2 and Φ 3. 3) If we drop Φ 3, it is not necessarily the case that Φ 1 Φ 2 Φ is true. Describe an example where Φ 1 Φ 2 is true while Φ is not. 7

8 3 1) 32, 18, 19, 21, ) m n 3) 2) 4) 2) 8

9 Problem 3 Answer the following questions on a chained hash table. Here the elements of a hash table are assumed to be integers. 1) Consider a hash table whose size is five, with a hash function that returns the remainder of the inserted value divided by five. For this hash table, draw its internal state after the insertion operations of integers 32, 18, 19, 21 and 22 in this order. 2) Assume a search of an element in a hash table, when the size of the hash table is m, and n elements are stored in it. Find the worst-case time-complexity of the search. 3) Find the average time-complexity of a search for the hash table in Question 2). Assume that the hash function returns uniformly distributed hash values. 4) For the hash table in Question 2), consider a new hash algorithm where each chain is replaced with a binary search tree. For the new hash algorithm, find the worst-case and average time-complexity of a search. 9

10 blank page) Usable for memos; do not detach. 10

11 blank page) Usable for memos; do not detach. 11

25 II :30 16:00 (1),. Do not open this problem booklet until the start of the examination is announced. (2) 3.. Answer the following 3 proble

25 II :30 16:00 (1),. Do not open this problem booklet until the start of the examination is announced. (2) 3.. Answer the following 3 proble 25 II 25 2 6 13:30 16:00 (1),. Do not open this problem boolet until the start of the examination is announced. (2) 3.. Answer the following 3 problems. Use the designated answer sheet for each problem.