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

全文

(1)大学院入試試験問題（修士） 2007年 8月 23日、24日. 英語（40 点）数理適正試験（120 点） (20 問) 基礎科目（60 点） 6 問中 3 問選択解析・線形代数（2 問）確率・統計（2 問）離散数学（2 問）専門科目（60 点） 6 問中 3 問選択オートマトン（2 問）アルゴリズム（2 問）論理設計（2 問）. (90 分) (40 分) (120 分). (120 分).

(2) 解析・線形代数 (1) 本問を選択 (Select this problem){ する (Yes)，しない (No) }. No.. フィボナッチ数列は，f0 = 0, f1 = 1, fk+1 = fk + fk−1 (k = 1, 2, . . .) によって定義される．. Fk =. Ã. fk+1 fk fk fk−1. !. ,. k = 1, 2, . . .. とするとき，以下の問に答えよ．(Using the Fibonacci numbers defined by the recurrence equation fk+1 = fk + fk−1 with f0 = 0 and f1 = 1, we define Fk as above.). 1. F1 の固有値と固有ベクトルを求めよ．(Find the eigenvalues and eigenvectors of F1 .) 2. Fk = F1k であることを示せ．(Show that Fk = F1k for k = 1, 2, . . . .) 3. Fk の固有値と固有ベクトルを求めよ．(Find the eigenvalues and eigenvectors of Fk .).

(3) 解析・線形代数 (2) 本問を選択 (Select this problem){ する (Yes)，しない (No) }. No.. 2. f (x) = e2x −3x とする。 2 Let f (x) = e2x −3x . n. を表す。 1. 次の式を示せ。ここで、f (n) (x) は d dxf (x) n Show the following equality, where f (n) (x) represents. dn f (x) dxn .. f (n+1) (x) − (4x − 3)f (n) (x) − 4nf (n−1) (x) = 0. (n = 1, 2, . . .). 2. Fn (x) = f (n) (x)/f (x) とする。次の式を示せ。 Let Fn (x) = f (n) (x)/f (x). Show the following equality. Fn0 (x) = 4nFn−1 (x). (n = 1, 2, . . .). 3. 次の式を示せ。 Show the following equality. Fn00 (x) + (4x − 3)Fn0 (x) − 4nFn (x) = 0. (n = 1, 2, . . .).

(4) 確率・統計 (1) 本問を選択 (Select this problem){ する (Yes)，しない (No) }. 受験番号 (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.) P. P. 1 n n−1 = 1/(1 − x)2 ．(Hints: ヒント: |x| < 1 のとき、 1 n=0 x = 1/(1 − x)．この両辺を x で微分すると n=0 nx P1 P n−1 = 1/(1 − x)2 .) If |x| < 1, n=0 xn = 1/(1 − x). Differentiating both sides of the equation, 1 n=0 nx.

(5) 確率・統計 (2) 本問を選択 (Select this problem){ する (Yes)，しない (No) }. 受験番号 (No.). ある確率分布の平均値 µ について、独立な不偏推定量 X1 および X2 があり、それぞれの分散を σ12 、σ22 とする。これらを用いた µ の推定量として以下の µ ˆ を考える。ただし α1 および α2 は定数である。(X1 and X2 are independent unbiased estimators of the mean µ of a probability distribution. The variances of X1 and X2 are σ12 and σ22 , respectively. Consider µ ˆ given by the following formula as an estimator of µ, where α1 and α2 are constants.) µ ˆ = α1 X1 + α2 X2 問 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)

(7)

(8) "!$#&%('*),+-)/.102043

(9) 57698

(10) :<; =>+?)/@BA<CEDGFH%JIK)/6LANMOQP$RS%UTV;A<W*X . Y[Z$\$]. ^ :<)_0<3

(11) )_à; +7+-;cbV5?d

(12) eQàf>d>.g0<5?; d>6V5?dchi),.g045-j ) k>6<f

(13) :ahl)/.10<5-j*) k=m5 hi),.g045-j*)n; :Vd

(14) ; d

(15) )co 'p0<q 0l)nbV5?0<3r:l),q 6l;*dts u swvyx*z|{}z v~%A 4 s9[x { t%aAE . swxp { %aA $[G 57dhl)/.10<5-j ) km6<f

(16) :hi),.g0<5?j*) k

(17) =m5 hi),.g045-j*) " y¡$¢£¥¤$¦y§y¨¥¤$¦[ " $¡$¢G£G©[ª" §«¨B¬G$®"¯ °«±[²$³µ´_¶ u swvyx*z|{}z v~%A s9[x { t%aAE swxp { %aA.

(18)

(19)

(20) !#"%$'&)(+*-,.*0/213154

(21) 687:9

(22) ;=< >?,@*0ACB=DFEHGI&KJL*07MBONPRQ%ST&VUW<B=X Y[Z%\%] ^ *21`_bacD-d

(23) e0f e5gheOihe=j

(24) e5keOleMmne5oe5pe0f2d

(25) e0f fe-f0ghX qr s?tu1=4

(26) *v>w6@s?r;=xy;z*-,@r 1=6.<+s { a|Dh&~}e50B0C}v6@7:r9

(27) ;56@A* sh?A >w*2;0q?r s?t}e5`_LX+ < ;:6@s?7z1=r s

(28) /2* qwg { iql { fq?>?

(29) 1Ws

(30) < 1l { i &fB*21z*0;5A#6@s*W4

(31) *21=4

(32) *0; { 6873;z*0

(33) *26@+* &VgnB*21z*0;5A#6@s*W4

(34) *21=4

(35) *0; { 687:7zxhA#A*01z;56@/ &VinB*21z*0;5A#6@s*W4

(36) *21=4

(37) *0; { 687:r s1=6)7zxhA#A*01z;56@/ &jB*21z*0;5A#6@s*W4

(38) *21=4

(39) *0; { 68731z;5r s?7=6.156.+* &VknB*21z*0;5A#6@s*W4

(40) *21=4

(41) *0; { 687:r su*0h

(42) 6@r ,.*-s

(43) /2*v;=*-,@r156.<+s 6@ *vr#;z*-r 7z<+su:4hx q< ;Wr[/<+?sn1z*0;z*2r A9w,.*68sy*-r /M4/2r 7z* _aDde-feMgheOihezj?e5ke5leMmneOoe5phe-f2d

(44) e0f fe-f0ghX# H¡ ¢£ {¥¤ { a|Dh&~}e50B0C}vR¦#§¨ª©[«¬}eO`_X# H¡ ®¯%° g { iql { f3±!²%¡R³R©³´l { iC±!µ#¶ &fB { ¦#·%¸%¹'&;=*0

(45) *26@ *Bº©» &VgnB { ¦#¼%½%¹'&~7=xhA#A*21=;56@/Bº©» &VinB { ¦#·%¼%½%¹'&~r sn156¾7zxA#A*21=;=68/B©» &jB { ¦#¿%À%¹'&1=;5r s?7=6.156. *B©» &VknB { ¦%Á#Â ¢#£ &*-n?6.r ,@*0s?/*;=*0,@r 1=6@< sBº©» ÃÄ%Å%ÄHÆ «%¶ÇqÈHÉÊ!³!ËR¦#· ® ¤ ²ÌÍ#.

(46) オートマトン (1) 本問を選択 (Select this problem){ する (Yes)，しない (No) }. No.. L を 0 と 1 からなる列で 0 の個数と 1 の個数がともに等しい文字列からなる集合とする. このとき, 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.).

(47) オートマトン (2) 本問を選択 (Select this problem){ する (Yes)，しない (No) }. No.. (1) 次の文法 G により生成される言語を L1 とする． S → ² | a | b | aSa | bSb ここで，S は開始記号および非終端記号であり，a と b とは終端記号である．文法 G により ababa が導出される過程を示しなさい．. Let L1 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) 言語 L2 を次のように定義する． L2 = {w ∈ {a, b}∗ | w = wR } ただし，w の逆を wR で表す．すなわち，(xn xn−1 . . . x1 )R = x1 x2 . . . xn であり，²R = ² である．長さが 5 以上の w ∈ L2 を一つ示しなさい．. Let L2 = {w ∈ {a, b}∗ | w = wR }, where wR is the reversal of w, that is, (xn xn−1 . . . x1 )R = x1 x2 . . . xn and ²R = ². Show one exmaple w ∈ L2 such that the length of w is greater than 4. (3) L2 ⊆ L1 が成立することを証明しなさい． Prove that L2 ⊆ L1 . (4) L1 ⊆ L2 を証明しなさい． Prove that L1 ⊆ L2 .. (解答は裏面を使用しても構わない．You can use the reverse side of this paper for your answering.).

(48) アルゴリズム (1) 本問を選択 (Select this problem){ する (Yes)，しない (No) }. 受験番号 (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). void print_all(void) { struct node *x = [ (A) while(x != [ (B) ]) { printf("%c",x->key); x = x->next; } printf("\n"); }. (B). ];. 問 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.).

(49) アルゴリズム (2) 本問を選択 (Select this problem){ する (Yes)，しない (No) }. 受験番号 (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(根) のノード，深さ 2 のノード，深さ 3 ノード，. . . の順で出力する関数を定義せよ。(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, . . ..).

(50) 論理設計 (1) 本問を選択 (Select this problem){ する (Yes)，しない (No) }. No.. 2 つの値 X, Y は 2 の補数による符号あり 2 ビット 2 進数であるとする。X と Y を入力としてそれらを比較する回路を考える。ここで、出力は 2 ビットであり、X が大きいときには “01”、Y が大きいときには “10”、X と Y が等しい場合は、すべての入力ビットが等しい場合には “00”、そうでなければ “11” となるようにする。 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 “11”. 1. 真理値表を示せ。 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.).

(51) 論理設計 (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). (Q2 Q1 Q0 ) → (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 の入出力特性関数は Qn+1 = Dn である。 The characteristic equation of D-FF is Qn+1 = Dn .. . . (解答は裏面を使用しても構わない。You can use the reverse side of this paper for your answering.).

(52)