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

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

2007年8月 23日、24日

英語 （40 点）    (90 分) 

数理適正試験 （120 点） (20 問)    (40 分)  基礎科目 （60 点）  6 問中 3 問選択   (120 分) 

解析・線形代数 （2 問） 

確率・統計 （2 問） 

離散数学 （2 問） 

専門科目 （60 点）  6 問中 3 問選択   (120 分)  オートマトン （2 問） 

アルゴリズム （2 問） 

論理設計 （2 問） 

解析・線形代数 (1)

本問を選択(Select this problem){ ^する(Yes)，しない(No) } No.

フィボナッチ数列は，f₀ = 0,f₁ = 1,f_k+1 =f_k+f_k−1 (k= 1,2, . . .) によって定義される．

F_k =

à f_k+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 withf₀= 0 and f₁ = 1, we define F_k as above.)

1. F₁ の固有値と固有ベクトルを求めよ．(Find the eigenvalues and eigenvectors ofF₁.) 2. F_k=F₁^k であることを示せ．(Show thatF_k=F₁^k fork= 1,2, . . . .)

3. F_k の固有値と固有ベクトルを求めよ．(Find the eigenvalues and eigenvectors ofF_k.)

解析・線形代数 (2)

本問を選択(Select this problem){ ^する(Yes)，しない(No) } No.

f(x) =e^2x2−3xとする。

Let f(x) =e^2x2−3x.

1. 次の式を示せ。ここで、f⁽ⁿ⁾(x)は ^dn_dx^f(x)n を表す。

Show the following equality, where f⁽ⁿ⁾(x) represents ^dn_dx^f(x)n .

f⁽ⁿ⁺¹⁾(x)−(4x−3)f⁽ⁿ⁾(x)−4nf⁽ⁿ⁻¹⁾(x) = 0 (n= 1,2, . . .) 2. F_n(x) =f⁽ⁿ⁾(x)/f(x)とする。次の式を示せ。

Let Fn(x) =f⁽ⁿ⁾(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, . . .)

確率・統計 (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.)

ヒント: |x|<1のとき、^P1_n=0xⁿ= 1/(1−x)．この両辺をxで微分すると^P1_n=0nxⁿ⁻¹ = 1/(1−x)²．(Hints:

If |x|<1,^P1_n=0xⁿ= 1/(1−x). Differentiating both sides of the equation, ^P1_n=0nxⁿ⁻¹ = 1/(1−x)².)

確率・統計 (2)

本問を選択(Select this problem){ ^する(Yes)^，しない(No) } ^受験番号(No.)

ある確率分布の平均値µについて、独立な不偏推定量X₁^およびX₂があり、それぞれの分散をσ²₁^、σ²₂^とす る。これらを用いたµの推定量として以下のµˆを考える。ただしα₁およびα₂は定数である。(X₁ andX₂ are independent unbiased estimators of the mean µ of a probability distribution. The variances of X₁ and X₂ are σ₁² and σ₂², respectively. Consider ˆµgiven by the following formula as an estimator ofµ, where α₁ and α2 are constants.)

ˆ

µ=α₁X₁+α₂X₂

問1:^推定量µˆが不偏になるために満たすべきα1とα2の関係を求めよ。(Q1: Show the required condition so that the estimator ˆµis unbiased.)

問2:推定量µˆが不偏で，かつ分散が最小になるようにα₁とα₂を求めよ．また、そのときの推定量µˆの分散 を求めよ。(Q2: Determineα1 andα2 so that ˆµis unbiased and has the minimum variance. Show the value of the minimum variance too.)

"!$#&%('*),+-)/.10204357698:<;=>+?)/@BA<CEDGFH%JIK)/6LANMOQP$RS%UTV;A<W*X Y[Z$\$]

^

:<)_0<3)_`a;+7+-;cbV5?deQ`af>d>.g0<5?;d>6V5?dchi),.g045-j)k>6<f:ahl)/.10<5-j*)k=m5hi),.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=m5hi),.g045-j*) ›" y¡$¢œ£¥¤$¦y§y¨¥¤$¦[ œŸ" $¡$¢G£G©[ª" œ§«¨B¬G­$®"¯

°«±[²$³µ´_¶

u

swvyx*z|{}z

v~%€A‚„ƒ†… ‡ˆ‰

Š ‹

 s9Ž[x

‰’‘

{“

‰’‘

Žt%a”AE‚

 

ƒsw•–xp

Š ‰ {“ —

! #"%$'&)(+*-,.*0/213154687:9;=<>?,@*0ACB=DFEHGI&KJL*07MBONPRQ%ST&VUW<B=X Y[Z%\%]

^ *21`_bacD-de0fe5gheOihe=je5keOleMmne5oe5pe0f2de0ffe-f0ghXqrs?tu1=4*v>w6@s?r;=xy;z*-,@r1=6.<+s

{

a|Dh&~}e50B0€C}v‚ƒ6@7:r„9;56@A„*…sh†?A…>w*2;0q?rs?t‡}e5`ˆ‰_LX+Š

‹

<;:6@s?7z1=rs/2*qwg

{

iql

{

fq?>?†1Ws<1Œl

{

iŠ

&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:rs1=6—–)7zxhA#A„*01z;56@/Š

&˜jBƒ*21z*0;5A#6@s*’‘W4*21=4*0; { 68731z;5rs?7=6.156.•+*Š

&VknBƒ*21z*0;5A#6@s*’‘W4*21=4*0; { 687:rsu*0™h†6@•r,.*-s/2*v;=*-,@r156.<+sšŠ

› 6@•*vr#;z*-r7z<+su‘:4hxq<;Wr[/<+†?sn1z*0;z*2”rA„9w,.*œ68sy*-r/M4‡/2r7z*Š

_aDžde-feMgheOihezj?e5ke5leMmneOoe5phe-f2de0ffe-f0ghX#ŸŒ H¡‰Š

¢„£

{¥¤

{ a|Dh&~}e50B0€C}v‚R¦#§‰¨ª©[«¬}eO`ˆ‰_­X#ŸŒ H¡‰Š

®‚¯%° g { iql

{

f3±!²%¡‰ŠR³R©³´l

{

iC±!µ#¶‚Š

&fŽB

{

¦#·%¸%¹'&˜;=*0“*2”6@•*ŽBº©»

&VgnB

{

¦#¼%½%¹'&~7=xhA#A„*21=;56@/žBº©»

&VinB { ¦#·%¼%½%¹'&~rsn156—–¾7zxA#A„*21=;=68/žB©»

&˜jB { ¦#¿%À%¹'&˜1=;5rs?7=6.156.•*B©»

&VknB

{

¦%Á# ¢#£ &˜*-™n†?6.•r,@*0s?/*œ;=*0,@r1=6@<sBº©»

«%¶‚ljqÈHɂÊ!³!ËR¦#· ® ²‰Ì‚Í#Š

オートマトン (1)

本問を選択(Select this problem){ する(Yes)，しない(No) } No.

Lを0と1からなる列で0の個数と1の個数がともに等しい文字列からなる集合とする. このとき,Lが正則 言語であることを示すか,またはLが正則言語でないことを示せ.

Let L={w|w∈ {0,1}^∗,inw, the number of 0’s equals the number of 1’s }. Prove or disprove that Lis a regular language.

(解答は裏面を使用しても構わない．You can use the reverse side of this paper for your answering.)

オートマトン (2)

本問を選択(Select this problem){ する(Yes)，しない(No) } No.

(1) 次の文法Gにより生成される言語をL1とする．

S →²|a|b|aSa|bSb

ここで，Sは開始記号および非終端記号であり，aとbとは終端記号である．

文法Gにより ababaが導出される過程を示しなさい．

Let L₁ 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 areaand b.

Show a derivation of abababy G.

(2) 言語L2を次のように定義する．

L₂ ={w∈ {a,b}^∗ |w=w^R}

ただし，wの逆をw^Rで表す．すなわち，(xnxn−1. . . x1)^R=x1x2. . . xnであり，²^R=²である．

長さが5以上のw∈L₂を一つ示しなさい．

Let L₂={w∈ {a,b}^∗ |w=w^R}, where w^R is the reversal ofw, that is, (x_nx_n−1. . . x₁)^R=x₁x₂. . . x_n and ²^R=².

Show one exmaple w∈L₂ such that the length ofwis greater than 4.

(3) L2⊆L1が成立することを証明しなさい．

Prove that L2 ⊆L1. (4) L₁⊆L₂を証明しなさい．

Prove that L1 ⊆L2.

(解答は裏面を使用しても構わない．You can use the reverse side of this paper for your answering.)

アルゴリズム(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 (typechar). The list is initialized byinit_list(), and a node is inserted byinsert_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 functionremove_char()that deletes all nodes whose value is equal to the character given through the argument. The function has onechar type argument, and the return type isvoid. Use the reverse side for the answer.)

アルゴリズム(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 labelin order of the node in depth 1 (the root node), nodes in depth 2, nodes in depth 3, . . ..)

論理設計 (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” ifX > Y, “10” ifX < Y, “00” ifX =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.)

論理設計 (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₂Q₁Q₀)→(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 isQ_n+1 =D_n.

(解答は裏面を使用しても構わない。You can use the reverse side of this paper for your answering.)