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

(1)

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

2006

年

8

月

24

日、

25

日

英語（40 点） (90 分)

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

解析・線形代数（2 問）

確率・統計（2 問）

離散数学（2 問）

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

アルゴリズム（2 問）

論理設計（2 問）

(2)

解析・線形代数

(1)

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

n

次正方行列

A

について，^t

AA = A

^t

A = E

であるとする．ここで，^t

A

は

A

の転置行列であり，

E

は単位行列である．また，

A + E

は正則であるとする．

For an n

×

n square matrix A, let

^t

AA = A

^t

A = E, where

^t

A is the transposed matrix of A, and E is the unit matrix. Also, let A + E be non-singular.

1. B = (A

−

E)(A + E)

⁻¹であるとき，^t

B =

−

B

であることを示せ．

Let B = (A

−

E)(A + E)

⁻¹

. Show

^t

B =

−

B. 2. E

−

B

が正則であることを示せ．

Show that E

−

B is non-singular.

(3)

解析・線形代数

(2)

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

0 < p < 1

のとき，以下を証明せよ．

Let 0 < p < 1. Prove that:

1. a

^p

+ b

^p

> (a + b)

^p

(a > 0, b > 0).

2. a

1p

+ a

2p

+

· · ·

+ a

np

> (a

1

+ a

2

+

· · ·

+ a

n

)

^p

(n

≥

2, a

i

> 0 (i = 1, 2,

· · ·

, n)).

(4)

確率・統計

(1)

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

確率変数

(x, y)

の確率密度関数p(x, y)が、Cを定数として次のように定義されている。

(A probability density function

p(x, y) of random variables (x, y) is deﬁned as follows.)

p(x, y) =

{ Cx2y

—

x, y≥

0

かつx

+

y≤

1

のとき

(If

x, y≥

0 and

x

+

y≤

1) 0 —

それ以外

(otherwise)

1.

yの周辺確率密度関数p(y)を求めよ。

(Obtain the marginal density function

p(y) ofy.)

2.

定数Cの値を定めよ。

(Compute the value of constant

C.)

(5)

確率・統計

(2)

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

Ui

(i = 1, . . . , 12)

は

(0, 1)

区間上の一様分布に独立に従うとする。

( Let

Ui

(i = 1, . . . , 12) be independent uniform random variables on the interval (0, 1).)

1.

Uiの期待値、分散を求めよ。

(Obtain the expectation and variance of

Ui

.)

2.

正規分布の簡易近似乱数として R

=

^∑¹²_i=1U_i−

6

を用いることがある。Rの期待値、分散を求めよ。

(R =

^∑¹²_i=1U_i−

6 can be used as an approximation of a random number having the normal distribution.

Obtain the expectation and variance of

R.)

(6)

"!$#&%('*),+-)/.10204357698:<;=>+?)/@BA<CEDGFH%JIK)/6LANMOQP RS%UT;VA4W XZY$[$\

]

)10_^`ba`4cedKfhgif&=)kjJl>T.10<5?;T>69m)/n>T)/mpo62jq;*+?+-;r961s

^E%JtuAEvxwt

ay%JtuAEvhz tZ{}|

w ~

c%JtuAEv%qa^AL%UtA

)10<)1:4@"5?T)r3)1043)/:^`a`4cpo:)5?Tb),.045-)6<l:Ub),.045-K);:9=5b),.045-*);:_T;T)s5?)8>:<;K;jJ61s

^`ba`4cedfgif"G "$_G¡ "¢£_¤G¡s

^E%JtuAEvxwt

ay%JtuAEvhz tZ{}|

w ~

c%JtuAEv%qa^AL%UtA

^`ba`4cZ¥§¦ ¨©Bª ¨©Bª ¦ ¨Z« ¬ G¯® $°¡©®$Z«²±p©}³G²´§µZ«G°§¶ ¸·Q©B¹²º Z»²¼¯µ

(7)

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

^ *21`_bacD-de0fe5gheOihe=je5keOleMmne5oe5phXq?rs?tu154*v>?68sr;=wx;=*0,8r156.<+s

y

azDh&|{e5}0B0~C{}6@7W0h0Fqrst{eO}`%_X+

<;:6@s?71=rs/2*qg

y

oqg

y

jq?>?1Ws<1i

y

l

&fBx*21*0;5A#6@s*W4*21=4*0;

y

6873;*0*26@+*

&VgnBx*21*0;5A#6@s*W4*21=4*0;

y

687:7whA#A*01;56@/

&VinBx*21*0;5A#6@s*W4*21=4*0;

y

687:rs1=6)7whA#A*01;56@/

&jBx*21*0;5A#6@s*W4*21=4*0; y 68731;5rs?7=6.156.+*

&VknBx*21*0;5A#6@s*W4*21=4*0; y 687:rsu*0h6@r,.*-s/2*;=*-,@r156.<+s

6@*r#;*-r7<+su:4hwq<;Wr[/<+?sn1*0;*2rA9,.*v68s*-r/M4/2r7*

_aD de-feMgheOihej?e5ke5leMmneOoe5pnX#¡¢H£¤

¥¦

y¨§

y azDh&|{e5}0B0~C{}R©#ª¤«¬[®¯{eO}`¤_°X#¡¢H£¤

±²%³ g y oqg

y

jv´!µ%£¤R¶R¬¶·i

y

lC´!¸#¹

&fB

y

©#º%»%¼'&;=*0*26@*B½¬¾

&VgnB

y

©#¿%À%¼'&|7=whA#A*21=;56@/ B½¬¾

&VinB y ©#º%¿%À%¼'&|rsn156Á7wA#A*21=;=68/ B¬¾

&jB y ©#Â%Ã%¼'&1=;5rs?7=6.156.*B¬¾

&VknB

y

©%Ä#Å ¥#¦ &*-n?6.r,@*0s?/*v;=*0,@r1=6@<sB½¬¾

®%¹Ê¤qËHÌÍ!¶!ÎR©#º ± µ¤ÏÐ#

(8)

! "$#&%'%)(+*-,/.+021435 6$7982:;=<>@?A$,B8DCEGFHIKJL1M82N OQPRS

T

&%LUV3W%)(MYX@1 6 "1Z/*-[M\]^+%_17]`%214[ba

Udcef:!g+h$ih)jkhBlkN4hm:gMh!inNh)oh)gMh&:lkN`8

oMpg+h2gk8cqjMhrok_i`h2gk8cdlMhLo+Kjkh)gs8tcugMhvokKlMh2gk8tcqj

oMpg+h$in8cihrok_i`h$in8ceihLo+Kjkh!i8tcqjkhvokKlMh$in8tcql

win8yxA1[+,_%202^5#m%L%2(+Y\0)]`.z({0_$.+02!,_$[k%)]`%)*"1[p%_0)][5,2*"%)*"14[}|5*6]\0)]798A1X~Ua

Kjs8M.z 6]*-[}Z/(+&%)(M$0LU02!#m14\4[5*"$$,!K]#$#m$.+%),B8Z'10)|i4ii$g4gg4g+i$g140L[M14%&a

Kls8Qq(5]`%r*6,'%)(M,2(+102%_!,_%'Z'10)|y]4^+%_17]%_1[UV0_!#m14\4[5*"$$,!K]#$#m$.+%),B8_

M8yxA1[+,_%202^5#m%]/0_$\^+ 6]0mM.+02!,2,2*"14[Y02&.502$,_![k%)*6[+\%2(+ 6][+\^+]\]4^M%2147]%_1[WU02$#&1\[5*"&!,!p]4#&#&&.5%2,B8Da

A Uq

Udcef:!g+h$ih)jkhBlkN4hm:gMh!inNh)oh)gMh&:lkN`8

oMpg+h2gk8cqjMhrok_i`h2gk8cdlMhLo+Kjkh)gs8tcugMhvokKlMh2gk8tcqj

oMpg+h$in8cihrok_i`h$in8ceihLo+Kjkh!i8tcqjkhvokKlMh$in8tcql

win8

bA

U

¡¢£¤¥

§¦¨©ª=«{8¬®=¯Q

Kjs8 bA Uq°±²i4ii$gg4gg5i$gW¬³´§µ¶8z·=¸¹ºG¸Q»=¼½¾Y

Kls8 bA UuQ³´@µ¿¶85·=± ºÀÁVÂÄÃ¿ÅVÂ ¬Æ=¯

(9)

"!#"$&%'%)(+*#,.-+/)0213!#"46587:9;<>=?",@5BADCEFG>HI0 58J KMLNO

PRQTSVUXWVY&Z\[]U_^`Q?abY&ZdcefYgcgQBh:ikj&Q8lXSnmdQ?hoY&pqQ?Ygabr\m\Y@`QTSts)u\v)wgxy[dQ8z\ZfQB[`"{

U|WX}Ds)u~@

^

wB~])dxXsw8~du&~g

^

B"xv

YgZ\[

U_^}sBBmfY&h|Si.p'igloQu&bh|Som\YgZwBhx

Z\hQ8lXSnmdQ?iababikVbZdc.efQ8hoSoiZfhT

>k]

mdigY&abaSnmfQ Xigln[fh|¡Z U W3¢ U ^ ig3aQ8Zfc&SomM£f¤\:mfQ8lQ U W [fQ8ZfigSoQ8h|SnmdQ?¥ip'r\abQ8p'QBZ"SXi&+U W

§¦¨

jQ Y'¥Ti&ZdSQT©"Sª«loQ8Q¬cglnY&p.p'Ygl:Som\Y@SVcgQBZfQTlnY@SoQ8h:U:WT

§¨

jQ Y'¥Ti&ZdSQT©"Sª«loQ8Q¬cglnY&p.p'Ygl:Som\Y@SVcgQBZfQTlnY@SoQ8h:U_^k

®]¯°²±y³µ´·¶ sku\vBw&x3¸¹]º»¼U Wt½

U

^X¾]¿ÁÀ

¹ÁÂÃÄ]ÅÆÇÈÉ

U W } s)u ~@

^ w ~ )ÊdxXsw ~ u ~g

^

)Ê"xv

UË^Ì} s8B²Ä]ÍÎ]ÏÈÐu?¹]ÑÒÓ<wV¹]ÑÒÂÕÔÊÖ

¦

Ñ×ØÙx

Ú ¹ ½ÜÛÊÝ¿ÁÀ ¹Þ]ØÄ]ßàÁÂMÉ

>k

U|W ¢ U_^XÄ]áÇÈ]âÐã²£ ¹]» ¾]äÁåMæç É

ÚÚ]è

Ý U|WéÓêU|WË¹]ëìí ¾]î ÇÖM¹ ½ ÇÈÉ

§¦

U WË¾]ïð ÇÈ]ñòÐóô]ñõ ¾]ö àÁÂMÉ

§

(10)

アルゴリズム

(1)

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

ハノイの塔の問題を解く再帰的手続き

H

1

( n, A, B, C )

を次に与える．

3

本の杭

A, B, C

^{がこの順番で一列に並} んでおり，

n

枚の大きさの異なる円盤がある．円盤の中心に穴があいており，穴を杭に通しながら円盤を積み上げていく．ただし，大きい円盤の上に小さい円盤を置かなければならない．始め

n

^{枚の円盤が}

A

^に積み上げられている時，これらの円盤を全て

C

に積み上げたい．円盤は一度に一枚しか移動できないとする．

We give a recursive procedure H

₁

( n, A, B, C ) for the Towers of Hanoi problem in the following. We have three pegs A, B, C arranged in a row and in this order, and n disks initially stacked in increasing size on peg A . The objective is to transfer the entire tower from peg A to peg C , subjected to the condition that only one disk should be moved at a time and no disk be placed above a smaller.

procedure

H

₁

( n, A, B, C );

if

n

≥

1

then begin

H

₁

( n

−

1 , A, C, B );

“move from A to C ”;

H

1

( n

−

1 , B, A, C )

end

(1)

手続き

H

1

(4 , A, B, C )

では，円盤を合計何回移動しているか説明しなさい．

Explain how many moves in the procedure H

₁

(4 , A, B, C ).

(2) H

₁

( n, A, B, C )

での円盤の移動回数を

T

₁

( n )

と書く．ここで，

T

₁

( n )

に関する再帰方程式を与えてその解を求めよ．ただし，

T

₁

(0) = 0

とする．

Let T

₁

( n ) be the number of moves in the procedure H

₁

( n, A, B, C ) where T

₁

(0) = 0. Give a recursive equation for T

₁

( n ) and solve it.

(3)

問題の条件としてさらに，隣接している杭の間だけで円盤は移動できるものとする．この問題を解く手続き

H

₂

( n, A, B, C )

を与えよ．

We impose the extra condition that a disk must be transferred only between adjacent pegs. Then give a recursive procedure H

₂

( n, A, B, C ) to solve this problem.

(4) H

2

( n, A, B, C )

での円盤の移動回数

T

2

( n )

を求めよ．ただし，

T

2

(0) = 0

とする．

Give T

2

( n ), i.e., the number of moves in the procedure H

2

( n, A, B, C ) where T

2

(0) = 0.

(

解答は裏面を使用しても構わない．

You can use the reverse side of this paper for your answering.)

(11)

アルゴリズム

(2)

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

1. 2

分木の定義を書きなさい。

Describe the definition of a binary tree.

2.

木の点

v

の深さ

depth(v)

と高さ

height(v)

の定義を以下に示す。空白を埋めよ。

The definitions of depth(v), which is the depth of node v in a tree, and height(v), which is the height of node v in a tree, are given as follows. Fill in the blanks.

depth(v) =

0 (v is the root)

(1) (otherwise)

height(v) =

0 (v is a leaf)

(2) (otherwise)

(1) (2)

3.

高さ

k

の完全

2

分木の頂点数

n

を、

k

を使って表現しなさい。その根拠も示すこと。

Given a complete tree, let k and n be the height of the tree and the number of nodes in the tree, respectively. Express n with k with the reason.

4.

親子関係が図左のテーブルの形で与えられ、図右のような家系図を作成することを考える。この家系図が一つの木構造になるための条件を示し、木構造を生成するアルゴリズムの概要を説明しなさい。

Given a relation as shown in the following left figure, we wish to generate a family pedigree as shown in the following right figure. Show the conditions under which the family pedigree is a tree, and explain the outline of an algorithm for creating the tree.

parent child

A B

A C

C D

C E

A

B C

D E

(

解答は裏面を使用しても構わない。

You can use the reverse side of this paper for your answering.)

(12)

論理設計⁽１⁾

本問を選択^f する，しない^g ^No.

次に示す関数に対し、以下のことを行え。⁽¹⁾ カルノー図上で関数を示し、主項をループで囲め。⁽²⁾ すべての主項を列挙し、必須主項にアンダーラインを引け。⁽³⁾最小論理和形を示せ。

f(w;x;y;z)= Y

(0;2;3;4;8;9;10;14)

なお上式は最大項の論理積を示していることに注意せよ。たとえば、セル３（即ち^(w;^x;^y;^z)⁼^(0;^0;^1;¹⁾）では^f ⁼⁰である。

For the following function, do the following: (1) Express the function on a Karnaugh map, encircling the prime

implicants. (2)Listallprimeimplicants,underliningessentialprimeimplicants. (3)Findtheminimalsum-of-products

expression.

f(w;x;y;z)= Y

(0;2;3;4;8;9;10;14)

Notethattheaboveexpressionisthemaxtermexpansionofthefunction. Forexample,inthecell3(.i.e.,(w;x;y;z)=

(13)

論理設計⁽２⁾

本問を選択^(Select ^this ^problem)fする^(yes)，しない^(no)^g ^No.

RSフリップフロップ（^RSFF）を用いて下記の状態割り当てされた状態遷移図を実現する同期式順序回路を設計せよ。

（⁽¹⁾状態遷移表、⁽²⁾状態遷移関数、⁽³⁾回路図を求めよ。）

RSFFの入出力特性関数は^Qn+1

=S

n +R

n Q

n (S

n R

n

6=1) である。

Design a synchronous circuit with the following state transition diagram using RS

ip-ops(RSFFs).

(Give(1)statetransitiontable,(2)statetransition functionsand(3)circuitdiagram.)

ThecharacteristicequationofRSFFisQ

n+1

=S

n +R

n Q

n (S

n R

n 6=1),

R

S

Q RSFF

Q

(Q

2 Q

1 Q

0

):(000)!(001)!(011)!(010)!(110)!(100)!(000)