大学院入試試験問題（修士）

Size: px

Start display at page:

Download "大学院入試試験問題（修士）"

かつかげふしはら
5 years ago
Views:

1 8

2 (1) No. f 0 = 0, f 1 = 1, f k+1 = f k + f k 1 (k = 1, 2,...) F k = ( fk+1 f k f k f k 1 ), k = 1, 2,... (Using the Fibonacci numbers defined by the recurrence equation f k+1 = f k + f k 1 with f 0 = 0 and f 1 = 1, we define F k as above.) 1. F 1 (Find the eigenvalues and eigenvectors of F 1.) 2. F k = F k 1 (Show that F k = F k 1 for k = 1, 2,....) 3. F k (Find the eigenvalues and eigenvectors of F k.)

3 (2) No. f(x) = e 2x2 3x Let f(x) = e 2x2 3x. 1. f (n) (x) dn f(x) dx n Show the following equality, where f (n) (x) represents dn f(x) dx. n f (n+1) (x) (4x 3)f (n) (x) 4nf (n 1) (x) = 0 (n = 1, 2,...) 2. F n (x) = f (n) (x)/f(x) Let F n (x) = f (n) (x)/f(x). Show the following equality. F n(x) = 4nF n 1 (x) (n = 1, 2,...) 3. Show the following equality. F n (x) + (4x 3)F n(x) 4nF n (x) = 0 (n = 1, 2,...)

4 (1) (No.) 6 (We throw a fair dice repeatedly until 6 appears, and count the number of the throws.) 1: 10 (Q1: Compute the probability that we throw ten or more than ten times.) 2: (Q2: Compute the expectation of the number of the throws.) : x < 1 P 1 n=0 x n = 1/(1 x) x P 1 n=0 nx n 1 = 1/(1 x) 2 (Hints: If x < 1, P 1 n=0 x n = 1/(1 x). Differentiating both sides of the equation, P 1 n=0 nx n 1 = 1/(1 x) 2.)

5 (2) (No.) µ X 1 X 2 σ 2 1 σ2 2 µ ˆµ α 1 α 2 (X 1 and X 2 are independent unbiased estimators of the mean µ of a probability distribution. The variances of X 1 and X 2 are σ 2 1 and σ2 2, respectively. Consider ˆµ given by the following formula as an estimator of µ, where α 1 and α 2 are constants.) ˆµ = α 1 X 1 + α 2 X 2 1: ˆµ α 1 α 2 (Q1: Show the required condition so that the estimator ˆµ is unbiased.) 2: ˆµ α 1 α 2 ˆµ (Q2: Determine α 1 and α 2 so that ˆµ is unbiased and has the minimum variance. Show the value of the minimum variance too.)

6 A<W*X Y[Z$\$] ^ :<)_0<3)_à;+7+-;cbV5?deQàf>d>.g0<5?;d>6V5?dchi),.g045-j)k>6<f:ahl)/.10<5-j*)k =m5 hi),.g045-j*)n;:vd;d)co 'p0<q0l)nbv5?0<3r:l),q6l;*dts u swvyx*z {z v~% A ƒ 4 ˆ ŠŒ s9ž[x { Žt%a AE ƒ sw xp Š { %a A ƒ šœ $ [žgÿ 57dhl)/.10<5-j)km6<f: hi),.g0<5?j*)k=m5 hi),.g045-j*) "y $ œ $ y y $ [œÿ" $ $ G G [ª"œ «B G $ " «±[²$³µ _ u swvyx*z {z v~% A ƒ ˆ Š s9ž[x { Žt%a AE ƒ sw xp Š { %a A ƒ

7 ! B=X ^ *21`_bacD-de0fe5gheOihe=je5k eol emmne5ö e5p e0f2de0ff e-f0ghxqrs?tu1=4*v>w6@s?r ;=xy;z*-,@r1=6.<+s { a Dh&~e50B0 Cv ƒ6@7:r 9;56@A * sh?a >w*2;0q?rs?t e5`ˆ _LX+Š <;:6@s?7z1=rs/2*qwg { ï ql { f q?>? 1Ws<1Œl { ï Š & fžb ƒ*21z*0;5a#6@s * W4*21=4*0; { 6873;z*0 *2 6@ +*Š &VgnB ƒ*21z*0;5a#6@s * W4*21=4*0; { 687:7zxhA#A *01z;56@/ Š &VinB ƒ*21z*0;5a#6@s * W4*21=4*0; { 687:rs 1=6 )7zxhA#A *01z;56@/ Š & j B ƒ*21z*0;5a#6@s * W4*21=4*0; { 68731z;5rs?7= *Š &VknB ƒ*21z*0;5a#6@s * W4*21=4*0; { 687:rsu*0 h 6@ r,.*-s/2*v;=*-,@r 156.<+sšŠ 6@ *vr#;z*-r7z<+su :4hxq <;Wr[/<+?sn1z*0;z*2 ra 9w,.*œ68sy*-r/M4 /2r7z*Š Y[Z%\%] _ a Džd e-f emgheoihezj?e5k e5l emmneoö e5phe-f2de0ff e-f0ghx#ÿœh Š { { a Dh&~e50B0 Cv R # ª [«eo`ˆ _ X#ŸŒH Š % g { ï ql { f3±!²% ŠR³R ³ l { ic±!µ# Š & fžb { # % %¹'& ;=*0 *2 6@ *ŽBº» &VgnB { #¼%½%¹'&~7=xhA#A *21=;56@/žBº» &VinB { # %¼%½%¹'&~rsn156 ¾7zẍ A#A *21=;=68/žB» & j B { # %À%¹'& 1=;5rs?7= * B» &VknB { %Á#Â # & *- n?6. r,@*0s?/*œ;=*0,@r1=6@<sbº» Ã Ä%Å%ÄHÆ «% Ç q ÈHÉ Ê!³!ËR # ² Ì Í#Š

8 (1) No. L , L, L. Let L = {w w {0, 1, in w, the number of 0 s equals the number of 1 s. Prove or disprove that L is a regular language. ( You can use the reverse side of this paper for your answering.)

9 (2) No. (1) G L 1 S ɛ a b asa bsb S a b G ababa Let L 1 be the language generated by the following grammar G: S ɛ a b asa bsb where the start symbol is S that is also the nonterminal, and the terminals are a and b. Show a derivation of ababa by G. (2) L 2 L 2 = {w {a, b w = w R w w R (x n x n 1... x 1 ) R = x 1 x 2... x n ɛ R = ɛ 5 w L 2 Let L 2 = {w {a, b w = w R, where w R is the reversal of w, that is, (x n x n 1... x 1 ) R = x 1 x 2... x n and ɛ R = ɛ. Show one exmaple w L 2 such that the length of w is greater than 4. (3) L 2 L 1 Prove that L 2 L 1. (4) L 1 L 2 Prove that L 1 L 2. ( You can use the reverse side of this paper for your answering.)

10 (1) (No.) (char ) C init_list() insert_next() delete_next() (The following is a set of C functions dealing with a linear list whose values are characters (type char). The list is initialized by init_list(), and a node is inserted by insert_next() and deleted by delete_next(). Assuming these functions, answer the questions below.) #include <stdio.h> #include <stdlib.h> struct node { char key; struct node *next; ; struct node *head; void init_list() { head = (struct node *)malloc(sizeof(*head)); head->next = NULL; struct node *insert_next(char v, struct node *t) { struct node *x = (struct node *)malloc(sizeof(*x)); x->key = v; x->next = t->next; t->next = x; return x; void delete_next(struct node *t) { if(t->next!= NULL) { struct node *x = t->next; t->next = t->next->next; free(x); 1: ([ (A) ] [ (B) ] (Q1: The folloing function prints out all the values in the list in order. Answer the parts of the program needed in the blanks indicated by [ (A) ] and [ (B) ].) 1(A1): (A) (B) void print_all(void) { struct node *x = [ (A) ]; while(x!= [ (B) ]) { printf("%c",x->key); x = x->next; printf("\n"); 2: (Q2: Answer the output of the following program.) 2(A2): int main(void) { struct node *x; init_list(); (void)insert_next( A,head); x = insert_next( B,head); (void)insert_next( C,x); (void)insert_next( D,x); print_all(); 3: remove_char() remove_char() void char (Q3: Write function remove_char() that deletes all nodes whose value is equal to the character given through the argument. The function has one char type argument, and the return type is void. Use the reverse side for the answer.)

11 (2) (No.) left right NULL (= 0) (Answer the questions about the data structure of binary trees with labels defined below. A pointer to a child is assigned to the field left or right, and NULL (= 0) is assigned for indicating that no child exists. The reverse side can be used for the answers if needed.) typedef struct btree btree; struct btree { int label; btree *left; btree *right; ; 1: label (Q1: Define a function taking a binary tree and returning the total sum of the values of label. Use recursion in the definition.) 2: 1 (Q2: Define the same function as Q1 without recursion and with using the stack defined as follows:) int stackp; btree* stack[1000]; void initialize_stack(void) { stackp = 0; void push(btree *x) { stack[stackp++] = x; btree *pop(void) { return stack[--stackp]; int empty_stack(void) { return stackp == 0; 3: label 1( ) (Q3: Define the function taking a binary tree and printing out the values of label in order of the node in depth 1 (the root node), nodes in depth 2, nodes in depth 3,....)

12 (1) (Select this problem){ (Yes) (No) No. 2 X, Y X Y 2 X 01 Y 10 X Y Let X and Y be 2-bit signed 2 s complement binary numbers. You are to design the comparator circuit to compare two inputs X and Y, where the 2-bit output is 01 if X > Y, 10 if X < Y, 00 if X = Y and all input bits are the same, otherwise Show the truth table for the circuit. 2. Construct the Karnaugh map for the circuit. Then find the minimal sum-of-products expression using the map. 3. NAND Design the logic circuit with only NAND gates. ( You can use the reverse side of this paper for your answering.)

13 (2) (Select this problem){ (Yes) (No) No. D (D-FF) Let us consider to design a synchronous sequential circuit with the following state transition diagram using D flip-flops (D-FFs). (Q 2 Q 1 Q 0 ) (000) (001) (010) (011) (100) (000) 1. Show the state transition table. 2. Show the state transition functions. 3. Show the circuit diagram. D-FF Q n+1 = D n The characteristic equation of D-FF is Q n+1 = D n. ( You can use the reverse side of this paper for your answering.)

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.