←２７大修

専門科目（午前）情報工学

時間９：３０〜1２:３０

通信情報工学專攻・計算工学専攻

注意事項

1．各解答用紙に受験番号を記入せよ．
２．次の５題をすべて解答せよ．
3．解答は１題ごとに別々の解答用紙に，問題番号を明記した上で記入せよ．必要であれば，解答用紙の裏面に記入してよいが，解答用紙の表面にその旨を明記すること．
４．１枚の解答用紙に２題以上の解答を記入した場合はそれらの解答を無効とすることがある．
５．１題の解答を２枚以上の解答用紙に記入した場合はその解答を無効とすることがある．
6．電子式卓上計算機等の使用は認めない．

１̅１ 1)T=a)T２を求めよ．

１ﾙ細ʻ(:）

に対して，以下の問に答えよ．

b)Aのすべての固有値と，それに対応する固有ベクトルを求めよ．
Ⅳ。)正の整数Ｎに対してA,v
jbおよびEAn6を求めよ．
７z＝０２）図１．１に示したグラフのノードWA,WB,WCはＡさん,Bさん,Cさんのウェブ
ページを表し，エッジはハイパーリンク，エッジに付随する数値はそのハイパーリン
クをクリックする確率を表す．

0.5Ｃ碗虚 ○oʻ⑬０．
４
図l.1a)WAからハイパーリンクを２回クリックした後に再びWAにいる確率を求めよ．
b)ハイパーリンクをⅣ回(JV>1)クリックした後にWAおよびWBにいる確率を,PAJおよびQNとする．即­，とQJv̲,を用いてPNおよびＱﾉｖを表せ．
c)最初にWAにいる確率R]および最初にWBにいる確率Qoがともに0.3のとき，
剛およびQJvをⅣの関数として求めよ．

d)似｡PNおよびlimQﾉvを求めよ．
Ⅳ­卜○○２｡

２関数ノ(")=sgn(")+cos7r"+sin57r"(-1 鰯<1)について以下の問に答えよ．
ただし,sgn(")はsgn(")=

M5"I''である．

１）２つの実数αとβを用いて関数9(")=cMcos汀鰯+Bsin5汀錘を構成するとき，E(α､β)=

公|/(錘)­９(釦)'2伽をαとβの２次関数として表せ．

）
2 E(q,B)が最小となるときのαとβとE(Q,S)の値を各々求めよ．
）
3 上記の関数ノ(お)を用いて周期関数ノ(t)(一○o<t<oo)をノ("+2m)=/(")(-1 露<1,ｍは任意の整数)のように定義する./(t)を号+E:Z,((Z"COSn7rt+6"Sinn7rt)の形にフーリエ級数展開するとき，フーリエ係数ａn(7'=0,1,2,…)と6"(n=1,2,…）を各々求めよ．

）
4 3)で求めた周期関数/(t)のフーリエ級数に現れる全ての項にt=;とt=55とt=100を代入した場合の極限値
ABCＮ・­ＺⅣ
皿２？
華恥
１= ­ ＋ ・ Ｚ
皿Ｎ２》
界叩・１­
=＋ 皿 Ｚ》
２Ｎ目= 叩 ＋ ｌ／１ｊ ａ九 Ｃ０Ｓ­１Ｐ

１
れＣ ＯＳＯ、α、

袖旗１ １九汀 ＩＩ畦沌汀 Ｊ・杣 ｎ ２ハハ ノ­似． 開 ノ
叶い１ 皿ＵＵ ｎ汀” 汀、

仰２
汀ｎ
１ ５

α れＣ ＯＳ《 ＯＵ沌を各々理由を付して求めよ．必要であれば,「フーリエ級数の各点収束定理」の結果を証明せずに用いてよい．

３

3．時刻tの実関数である受信信号『(#)をｻﾝﾌﾘﾝｸし,送信ｼﾝﾎﾙ60を判定する問題を考える．まず,r(t)をr(t)=60Q(t)+"(t)（13）.と定める．ただし，６０は士1の２値をとる確率変数とし,(I(t)のフーリエ変換A(/)=ﾉ雪:｡α(t)e̅j2"/tdt
を』 I ル { 討 繍 ʼ ʻ 2 ʼとする．ここで,jは虚数単位，/ＭはA(/)の最高周波数で正の定数である．また,n(t)は雑音であり，時刻ｔによらず平均０，分散ぴ2のガウス分布に従うものとする．すなわち,7z(t)の確率密度関数pin(t)1
は州=蔬岬礫Ｉ｛ʻ8ʼとなる．なお,n(t)と60は統計的に独立と仮定する．以下の問に答えよ．
1)Q(t)=Jg:｡A(/)ej2"ft"である．鰯が実数のとき,sin"=gl璽苛̅'"となることを用いて,a(t)をｊを含まない形で求めよ．
2)|Q(t)|が最小となる時刻ｔの条件を求めよ．
3)|Q(t)|が最大となる時刻ｔを１つ求めよ．
4)r(t)を用いて60の信号判定を行う．ただし,Q(t) ０を満たす時刻ｔに限る.a(t)r(t)>0のとき
60=1,a(t)r(t) ０のとき60=-1と判定する.60=1の場合,60の判定誤りが起きる確率P,eはPe,=方広華
ʻ ，側”（43）.となることを示せただしγ, ＝禁である
同様に，６０＝­１の場合，６０の判定誤りが起きる確率P̲1eを求めよ．

5）６０＝１となる確率を９(０ ９ １)とする．α(t) Ｏを満たす時刻ｔにおいて,60の判定誤りが起きる確率良を求めよ．
6)Q(t) Ｏを満たす時刻ｔのうち，足を最小にするｔを求めよ．また，その理由についても説明せよ．

４●．
41)以下の論理代数（ブール代数）の等式を証明せよ．ただしＺＷﾉはＺとりの論理和(OR),叩は.Ｅとりの論理積(AND),蚕はおの否定(NOT)を表す．
a)(z,v両咋2V万沖3VTT)=z1"2"3V万万両b)(",V両池2v")･･･(Ｚｎ­,V")(.r"VZrr)=.I,,J,2…ｚ7zV万万….z”（刀Ｚ２）2）４進同期式カウンタを実現する順序回路の設計を考える．入力を釘，出力をｙの各ʼビット，現在の状態を9,90,次の状態を９{96の各２ビットとする．初期状態は9190=００とする．
"=1が入力されるたびに,9190の値は００­０1一1０一ll­００­…（以後，同じ繰り返し）と変化する．Ｚ＝０の時，9,90の値は変化しない.":=1かつ9190=1１の時のみI/=1となり，それ以外ではＩノ=0とする．
表４．１：カルノー図
0０0１1１０1０１a)91.96Ｊそれぞれについて,",91,90によるカルノー図を示せ．カルノー図の作成には
表４．１の形式を参考にせよ．
b)a)の解を用いて,",91,90に関するNOT-AND-OR形式（｢積項の和」形式，積和標準形）で9i:96,I/それぞれを表せ．ただし，項数が最小となるように簡単化すること．
c)b)の解を用いて，順序回路図を示せ.2入力のNANDゲート,3入力のNANDゲート，および立ち上がり動作のエッジトリガ型Ｄフリップフロップのみを用いること．クロックへの入力は順序回路図では省略して良い．

3)メモリｷｬｯｼｭについて,空欄｢n〜｢可に最も適切な語句を,図4.3の選択肢群から選んで，その番号を解答せよ．同じ選択肢を何度選んでも良い．

a)メモリキャッシュはCPUとメモリの間に配置する記憶装置であり，メモリよりも小容量で高速に動作する一般的にﾒﾓﾘｱｸｾｽには参照の「河があるためメ, モリ
キャッシュにメモリ中のデータの一部を一時的に保存することで，全体の平均アクセス時間を向上させることができる．アクセスされたメモリがすぐに再度アクセスされる可能性が高いことをＥ百Ｔ祠といい,ｱｸｾｽされたﾒﾓﾘと近い番地のﾒﾓﾘが，同時あるいはすぐﾗ'ｸｾｽきれる可能性が高いことを「可｢口という．
b)メモリｷｬｯｼｭの書き込み操作には大きく2つの方式がある．匝。方式は書き込み操作をメモリキャッシュとメモリの両方に同時に行うため，メモリキャッシュとメモリの内容が常に一貫しているが書, き込み速度は向上しない一. 方，「司方式はメモリキャッシュのみに書き込みを行い，メモリへの書き込みはフラッシュ時などに遅延して実行されるため，書き込み速度が向上する．
(次ページにつづく）

５"(前ページのつづき）

c)メモリ中のデータをメモリキャッシュのどこに格納することを許すか，すなわちメモリとメモリｷｬｯｼｭの対応づけの違いで大, きく3つの方式がある．匡]方式はあるメ
モリのﾃｰﾀの格納をﾒﾓﾘｷｬｯｼｭの一箇所のみに許す(図42の①)回方式はメモリキャッシュ内で事前に限定された一部の複数箇所への格納を許し，その複数箇所からつʻ を選んで格納する(図42の②)．「詞方式は全ての場所への格納を許し,1つを選んで格納する（図4.2の③).この３つの方式のうち，一般的に最もキャッシュミスしやすいのリ
クセス時間が最も短いのはﾒモリメモリキャッシュ１弄方蕊静=たｷｬ，ｼ 脚蝪合のア
ﾒモリメモリキャッシュ

蕊舗舗翻

霊、無州一、 … 熱

蝋、蝋ﾐ、、=ご菫蕊州ﾐﾐ、

ﾒモリメモリキャッシュ｡、､、善、、、、、、、､、、、①対応は­箇所に固定②複数の場所に対応づける③全ての場所に対応づける
図４．２：メモリとメモリキャッシュの対応関係d)キャッシュ置換アルゴリズムとは，メモリ中のデータを新たにメモリキャッシュに格納するために，メモリキャッシュ中から捨てるデータを選択するアルゴリズムのことであり様, 々な方式がある．「詞は最近のある一定期間内のｱｸｾｽ頻度が最少のﾃー
夕を捨て捨てろ．

１言証円最篁蒜ﾘﾆ蝋1憩舅遡蕪豐鯏古いﾃｰﾀゞe)メモリ中のデータをメモリキャッシュに転送する方式には大きく２つの方式がある．

囹,隻溌蕊韓駕鰍鑪麗三幕舞蕩弱
方式のうち，「百Ｔ河が無く,次にｱｸｾｽするﾃｰﾀを予測しやすい処理の場
合，例えば巨大な配列の各要素を先頭から逐次的に一回ずつアクセスする場合などは，［下１の方が性能の向上を期待できる．
(1) インダイレクト・マッズ（２）完全性，（３）局所性，（４）空間的，（５）健全性，(6) 構造的，（７）時間的，（８）スワッピンク：（９）脆弱性,(1０)セグメンテーション，(11) 絶対的,(１２)セット・アソシアテイ式(1３)相対的,(14)ダイレクト・マッズ(15) デマンドフェッチ,(16)透過性,(17)バッファリンク:(1８)ビジーウェイト，(19) 物理的，（20）プリフェッチ,(21)フル・アソシアテイフ:(22)ページンク､
2(3） ポーリンク：（24）ライトスルー，（25）ライトパック，（26）ラウンドロビン，
2(7） ランダム，（28）論理的，（29）割り込み,(30)FIFO,(31)LFU,(32)LRU
図４．３：選択肢群６

６．
5 αを整数列とし，その項をαi(jは非負整数）で表す．河をn>1をみたす整数とする．αの最初の冗項α0,α,,…,α"-,における，長さ１以上の連続する項の和で最大のものをf((I,")とす
ると，これは以下のように定義できる．

加,")=max{恥｡除|｡ '三j<">例えばα＝(20,-24,36,3,-7,27,-40,37,-28,6)の場合，ノ(α,10)＝36＋３＋(-7)＋27＝５９となる．以下，ノ(αʼ九)を計算する関数のプログラミング言語ｃによる定義を試みる．整数列αは配列ａとして与えられるものとする．与えられる配列は十分長く，範囲外の参照は生じないと仮定する．加えて，整数の演算についてオーバーフロー等は生じないと仮定する．また，引数、の値は１以上であるとする．
1）まずは上の定義に従い,/(q,'z)を計算する関数ｆおよび付随する関数を図5.1のように定義した．
intf(inta[],intn){
ints=a[O];f o r ( i n t i = 0 ; i < n ; i++)for(intj=「貢可;j <n;j++)s=max(s,sum(a, i , j ) ) ;returns;）

intmax(intx,inty){
ｒｅｔｕｒｎｘ＞ｙ？ｘ：ｙ；｝intsum(inta[],inti,intj){
ints=0;for(intk=i;k<=j;k++)s=s+a[k];returns;）

図5.1a)空欄囚に入る式を答えよ．
b)図5.1の関数ｆによる/(q,")の計算時間を四(”)としたとき,zl,(")=o(t,("))をみたすとする.t,(")にあてはまる式でｎに対する増え方が最も小さいものを以下の選択肢から選べ．
1,logn,，/丙，刀,7zlogn,河2,7z21og",n,:,,z3,,34,2",22".(*)
ここでzl,(n)は配列ａの要素を参照する回数A,(")および定数c,,ciを使ってzi(n)=c,A,(n)+ciと表せるものとする．なお，以下の問題においても関数の計算時間は同様に表せるものとする．
2）図5.1のプログラムではあまりに計算に時間がかかると考えたので，少し工夫をして関数fの定義を図52のように変更した.空欄囚に入る式は問la)のものと同じとする．
a)空欄回に入る式を答えよ．
b)図5.2の関数ｆによるノ(q,'z)の計算時間を過(n)としたとき，乃(")=O(t2(n))
をみたすとする.t2(")にあてはまる式で”に対する増え方が最も小さいものを問1b)の選択肢(*)から選べ．

intf(inta[],intn){
ints=a[O];for(inti=0;i<n;i++){intt=0;for(intj=m;j<n;j++){t = t + r m ;s=max(s,t);））
returns;）
図5.2(次ページにつづく）

ワ

(前ページのつづき）

c)図5.1から図5.2への変更によって計算時間のオーダーが小さくなる理由を100字程度までで述べよ．

3）図5.2のプログラムはこれ以上工夫の余地がなさそうなので，ここで少し考え方を変えてみる．冗三２である場合について，αの最初の冗項α0,α,,．..，α"­，における連続した項の和を，末尾の項α"-'を含まない場合と含む場合に分けて考える．前者の最大値はノ(α,九一1)で与えられる．後者の最大値を９(α,河)とすると，これは以下のように定義できる．

9(q,7z)=max{酬三:｡,.|0 #<'J/(α,冗)の定義より,7Z ２をみたす任意の九についてノ(α,'Z)=max{/(q,”­1),9(｡,")}がなりたつ．この考え方をもとに，９(αʼ九)およびノ(Q,'z)を計算する関数ｇおよびｆを図5.3のように定義した．
intf(inta[],intn){
ints=a[O];for(intk=1;k<n;k++)s=max(「訂,g(a,｢F司));
returns;）intg(inta[],intn){
intt=「石司；for(intk=1;k<n;k++)t=max(t+口工],「面司);returnt;｝

図5.3a)空欄回回回および回に入る式を答えよ．
b)図5.3の関数ｆによるノ(α,凡)の計算時間を乃(泥)としたとき，巧(")=O(t3(n))をみたすとする．t3(")にあてはまる式でれに対する増え方が最も小さいものを問1b)の選択肢(*)
から選べ．
4）図5.3の２つの関数g,fはよく似ている．そこでこれらを組み合わせ,9(Q,")とノ(α〃)を一緒に計算することで計算時間を減らせると考えた．このアイデアにもとづいて定義した関数ｆを

図54に示す.空欄回回および回に入る式
は問3a)のものと同じとする．

intf(inta[],intn){
intt=「石司,s=a[O];for(intk=1;k<n;i++){t=max(t+m̅],m̅]);s=max(E疽可,E面可);）
returns;）
図5.4a)空欄回に入る式を答えよ．

b)図5.4の関数ｆによるノ(α,”)の計算時間をZ4(")としたとき,Z14(")=O(t4(n))をみたすとする.t4(")にあてはまる式で冗に対する増え方が最も小さいものを問1b)の選択肢(*)
から選べ．
c)図5.3から図5.4への変更によって計算時間のオーダーが小さくなる理由を100字程度までで述べよ．

Ｓ