【院試解答】東大院工学系研究科電気系工学専攻 2020年 問題3
免責
この解答・解説は当ブログ管理人のものであり、間違っている可能性もあります。
この記事の記載内容によって生じた損失や損害については、当ブログ管理人は一切責任を負いません。
が、間違っている箇所や、よりよい解法があれば後から見に来た人のためにもコメント欄に残していってもらえると、幸いです。
あと、解説でこれが解ければ院試は受かる、的なことを言っていますが、一回しか院試を受けたことがない管理人の所感なので真剣にはあてになさらず。
でももちろん、管理人が実際にそう感じたことを書いています。
問題
解答
I
(1-i) 難易度:普通
(1-ii) 難易度:普通
(2) 難易度:普通
2元対称通信路の通信路容量は教科書に載っている。
(3) 難易度:難しい
(4) 難易度:普通
英語なのでなんか読み間違えたかなと不安になる、最後なのに簡単な問題。
え、これであってるよね？
Ⅱ
(1) 難易度:普通
2×0.5nはu(n)をつけても良い。
(2) 難易度:普通
(3) 難易度:普通
(4) 難易度:普通
関連記事
【院試解答】東大院工学系研究科電気系工学専攻 2021年 問題3
免責
この解答・解説は当ブログ管理人のものであり、間違っている可能性もあります。
この記事の記載内容によって生じた損失や損害については、当ブログ管理人は一切責任を負いません。
が、間違っている箇所や、よりよい解法があれば後から見に来た人のためにもコメント欄に残していってもらえると、幸いです。
あと、解説でこれが解ければ院試は受かる、的なことを言っていますが、一回しか院試を受けたことがない管理人の所感なので真剣にはあてになさらず。
でももちろん、管理人が実際にそう感じたことを書いています。
問題
解答
I
(1) 難易度:普通
(2) 難易度:普通
解き方は次のよう。
これを拡大係数行列にして解く。
ちなみにここで、各行の一列だけにマイナスがついていることを確認しておくこと。これは簡単なチェックであるが、しなかったせいで永遠に答えが出なかった筆者の反省である。上三角行列を作っていくが、変数が3つの方程式なので、一つ式が余っても良いことに注意しておく。まず、足し引きせずに、
が作れる。①+②をすれば1列目が0になって、少ない計算で上三角行列の3行目が簡単に作れそうだなと考えるが、①+②は4列目も0となる。それはつまり(次元の面で)③’の再生産でありその方向性では3行目は作れない。(実際③’=-5×(①+②)である。)
よくよく考えてみると、マルコフ遷移だから、①~③の変形前の連立方程式の左辺の係数は縦に全部足すと全部1になる。よって(右辺も自明に係数1だから)、①~③を縦に足すと全部0になる。つまり、①、②、③から2つをとって足すと必ずもう一つが出てくるのである。逆に言えば、①~③同士の計算をする場合は一方か両方に係数をつけて(掛け算をして)足せばよいということだ。もっとも、それで計算が簡単になるとは限らないが。
この後は、次のように求まる。
とまあ、ここではきちんと順を追って書いたが、紙の上だと適当で、字が汚い筆者はそれで計算ミスをしたりする。院試では時間はたっぷりあるから、計算ミスで時間を取られるよりかは一個一個順を追ったほうがいいのかなあと思ったり思わなかったり。
ところで、一番最初の拡大係数行列で「一列だけマイナスになっていることを確認する」というチェックの方法を述べたが、ほかにもチェックの方法はある。一つは、先ほど述べたように①～③を縦に合計すると0になることを確認すること。もう一つは、①～③の前の方程式は、状態遷移図上でそれぞれs0~s3の状態から出ていく確率と入ってくる確率が釣り合った式とも解釈できるため、状態遷移図と照らし合わせて符号と係数もろとも確認するという方法である。
(3) 難易度:普通
なお、ここで次で定義されるのは一次エントロピーである。
これは無記憶情報源と見たときのエントロピーと同じである。マルコフ情報源は記憶があるから、エントロピーがこれよりも小さくなる。
(4-i) 難易度:普通
面倒くさかったから全て分数&分母を550で統一して書いた。(本番は少数や約分したものを書いた方がいいのだろうか。)
(4-ii) 難易度:普通
1情報源記号あたりの平均符号長で測る。 これが(3)のエントロピーに近いほど符号化効率が良い。
情報源記号というのはs0,s1,s2という情報源自体が出す記号のこと。
Ⅱ
(1) 難易度:普通
(2) 難易度:難しめ
ここで言っている「定義」というのは一般的なディラックのデルタ関数の定義である。ネットでは、この一般的な「定義」からフーリエ変換を導く例はあったが、問題で与えられているδ(t)の定義から導く例は見つからなかった。問題で与えられているδ(t)の定義から一般的な「定義」の方を導くのはできないと思うので、与えられているδ(t)関係なしに解くべきと判断した。なお、これ以降の回答もこの一般的な定義を使っている。
が、ここまで真面目に解かなくても、単に1とだけ書けばよい問題だったのかも。
(3) 難易度:普通
(4-i) 難易度:普通
(4-ii) 難易度:難しめ
(4)は2017年の問題B(2)と全く同じである。そちらではフーリエ変換表が与えられているため、1のフーリエ変換を断りなしに導入できる。しかしこちらはそもそもデルタ関数の定義しか与えられていないので、1のフーリエ変換がデルタ関数としていいのかは若干不安。 ほかの方法としてはデルタ関数の積分表示を使うと、フーリエ変換を介さずに答えを出せる。が、どちらにせよ問題文にないものを導入しなければならない。
(5-i) 難易度:難しめ
これもやはり図の方が分かりやすいだろうがPCで図を描く気力がなかったので使わなかった。要はこのΣのn=0の場合だけ取り出すにはどうすればよいか、ということである。
(5-ii) 難易度:普通
(5-i)で言及したように、x(t)の帯域がサンプリング周波数の1/2未満である必要がある。(5-i)が解けなくても、サンプリング定理を説明すればよい。以下ではなく未満とするのが正しそう。
関連記事
sekakota.hatenablog.com【院試解答】東大院工学系研究科電気系工学専攻 2022年 問題4
免責
この解答・解説は当ブログ管理人のものであり、間違っている可能性もあります。
この記事の記載内容によって生じた損失や損害については、当ブログ管理人は一切責任を負いません。
が、間違っている箇所や、よりよい解法があれば後から見に来た人のためにもコメント欄に残していってもらえると、幸いです。
あと、解説でこれが解ければ院試は受かる、的なことを言っていますが、一回しか院試を受けたことがない管理人の所感なので真剣にはあてになさらず。
でももちろん、管理人が実際にそう感じたことを書いています。
問題
解答
※昔から電子工作を趣味としている管理人は、問題4の難易度の感覚がバグっているので、「難しい」と記載したもの以外はあまり参考にしないでください。
I
(1-i) 難易度:普通※
(1-ii) 難易度:普通※
(1-iii) 難易度:普通※
(2) 難易度:普通※
(3-i) 難易度:普通※
(3-ii) 難易度:普通※
Ⅱ
(1) 難易度:普通※
解答は分かりやすいよう空欄だけでなくその行ごと書いてある。
// A
return new;
// B
root->left = add(root->left);
// C
root->right = add(root->right);
(2-i) 難易度:普通※
(2-ii) 難易度:普通※
(3) 難易度:普通※
解答は分かりやすいよう空欄だけでなく周りごと書いてある。
// D, E if (root->left != NULL) { enumerate(root->left); } // F, G if (root->right != NULL) { enumerate(root->right); }
(4) 難易度:普通※
0個の場合、そのノードをただ消せばよい。 1個の場合、そのノードを消すと同時にその子ノードをそのノードがあった場所に引き上げる。 2個の場合、そのノードを消すと同時に、右部分木の最小ノードを外して、 そのノードがあった場所へと移動する。 この最小ノードをはずす際はノードを削除する手順を再帰的に適用する。
(5) 難易度:普通※
同じsidを持つノードは追加されない。 問題点は一つのsidを複数個保持することはできない。問題点ってむしろそういう使い方だと思えば問題じゃないと思うけど。
(6) 難易度:普通※
要素数をnとすると、 利点は要素の探索にかかる平均計算量がO(n)の配列に比べて2分探索木はO(log n)と 短いことで、 欠点は要素の追加にかかる平均計算量がO(1)の配列に比べて2分探索木はO(log n)と 長いことである。
関連記事
【院試解答】東大院工学系研究科電気系工学専攻 2022年 問題3
免責
この解答・解説は当ブログ管理人のものであり、間違っている可能性もあります。
この記事の記載内容によって生じた損失や損害については、当ブログ管理人は一切責任を負いません。
が、間違っている箇所や、よりよい解法があれば後から見に来た人のためにもコメント欄に残していってもらえると、幸いです。
あと、解説でこれが解ければ院試は受かる、的なことを言っていますが、一回しか院試を受けたことがない管理人の所感なので真剣にはあてになさらず。
でももちろん、管理人が実際にそう感じたことを書いています。
問題
解答
I
(1) 難易度:普通
-(0.75 log 0.75 + 0.25 log 0.25) = 0.8
-(0.75 log 0.75 + 0.25 log 0.25) = 0.8
(2) 難易度:普通
下図は一例。
───┬─0────────── 0 : 00 = 9/16
└─1─┬─0────── 10 : 01 = 3/16
└─1─┬─0── 110: 10 = 3/16
└─1── 111: 11 = 1/16
平均符号長は
(9/16) + (3/16) * 2 + (3/16) * 3 + (1/16) * 3 = 27/16 = 1.6
(3) 難易度:普通
X Y
0.25: 1 ─────── 1 : 0.25 + 0.75 * 20% = 0.40
─┐ 0.75 * 20%
／
／
0.75: 0 ─────── 0 : 0.75 * 80% = 0.60
Yで、1となる確率は 0.25 + 0.75 * 20% = 0.40
(もしくは 80% * 0.25 + 20% = 0.40か。
最初こう考えたが図で表しづらく他に応用が利かないと思った。)
よって、H(Y) = -(0.4 log 0.4 + 0.6 log 0.6) = 0.94
また、
H(Y|X) = -(0.25 log 100% + (0.75*20%) log 20% + (0.75*80%) log 80%) = 0.53
I(X; Y) = H(Y) - H(Y|X) = 0.41
(H(Y{X)、I(X; Y)は計算機と答えが違う)
(4) 難易度:難しめ
ただし、Hの筆記体はエントロピー関数。書くのを忘れたが、解答では断りを入れたほうがいいだろう。
途中式を省略しているため短く見えるかもしれないが、全然簡潔ではない。
間違ってはいないだろうが、簡潔ではないので多分答えではない。が、いったいなんと答えれば正解だったんだろう…。
pを0.5より小さくすれば100%出力が反転しない1の割合が増えるので、H(Y|X)は減る。
が、同時に出力の0の割合が減るので、H(Y)も減る。これで、最初だけH(Y)が増加するとかだったらよかったが、H(Y)のピークは0.8p=0.5となるp=0.625>0.5なので0.5より左側はバリバリ単調増加である。
もし、分かった人がいたら下のコメント欄でぜひ、教えてほしい。
Ⅱ
(1)~(4) 難易度:普通
(5) 難易度:難しめ
(6) 難易度:普通
(7) 難易度:難しめ
SSB変調というやつである。多分図を入れて説明した方がもっとわかりやすい。が、PCで絵を描く気力がなかったのでこれで解答にする。
しかし、きちんと書いて思ったが、符号関数ってω=0のとき0になるから、|ω|=ωcの時だけ別に書かないといけないという。 元のスペクトルには戻らない。デルタ関数を足せばスペクトルも戻るが、、帯域を制限せよって問題だから、これでいいか。
関連記事
sekakota.hatenablog.comカテゴリー 大学院受験 とは？
カテゴリー 大学院受験 について
このカテゴリーは大学院受験に挑戦した僕(どんぐり)が大学院受験についての情報をまとめたものです。
でも明らかに僕のブログにそぐわないカテゴリーですね。
本当だったら大学院受験記についての別のはてなブログを作ったり、noteとかに寄稿すべきです。
なのになぜこのブログに書くのか？
それはこの受験記をエサにしてこのブログの記事を見てもらいたいからです！
これをマーケティングの世界で「なんとか」といいます(忘れました！)。
なので、皆さん、他の記事も見ていってくださいね。
しかし、世の中は本当に大学院受験についての情報が少ないです。
多分、内部から受ける人にとっては先輩とかに聞けばわかるんでしょうが、僕のように外部から目指す人にとっては試験範囲が分からなかったり、自分の大学では習ってないことが出たり、いろいろ情報が足りないものがあります。
多分、外部の受かる確率が低いのは頭脳面だけじゃなくて、その情報格差によるものもあるんだと思います。
けど、例えば僕が目指した専攻とかだったら外部が毎年百人以上受けているというのに、誰も発信してないのは不思議です。
、、いや、受かってるのは数十人だからその中から発信する人は少ないか。(悲しい気づき)
まあみなさんも、もし受かったら後輩のためにブログにしましょう！
今はnoteとかもあって、簡単に記事を発信できるので、もしかしたら収益化できるかもと思ったらやる気が出てきませんか？(導入コストが許容できればはてなも良いですよ)
(あ、僕が記事にする東大電気系工学専攻と電子情報学専攻は競合になっちゃうのでやめてくださいね冷)
記事一覧
解法論の本質をかみ砕く
解法論の本質をかみ砕いて説明する
解法論の本質は、詳しくはこの記事に載っています。
しかしこの記事は、正確な代わりに理解するのは難しいと思うので、より分かりやすい説明をこの記事で行おうと思います。
この記事で説明することは以下の3つです。
- 解法論とは世界の解き方であり、解法論全てに共通する本質があって、それを見方を変えて切り出すことによって使いやすい解法になる。
- 解法論の本質をかみ砕けば、理解しないということが解法である。
- 解法論って変な名前だよね
弁解
で、この記事は今はここまでで終わりです。というのは、もともと書こうとしていたことがあるのですが忘れてしまいました。思い出したときにまた書こうと思います。
世界に答えを出すブログのしばらく(12/25)
世界に答えを出すブログのしばらく
なんか「どんぐりさま、お元気ですか？前回の更新から1カ月たってますよ、そろそろ次の記事更新しませんか？もしかして、リスにでも食べられましたか？」とはてなに安否を心配されたのでブログを更新したいと思います。
そう、気づいたら前回の更新から1カ月経ってました。下の記事の通り、僕はテスト勉強のためにブログを停止していましたが、そのテストは1週間前に終わっていました。
でも、テストが終わってもちょっと忙しくて他のことやってたら、ちょうどはてなから安否確認のメールが届いたという訳です。
あ、ちなみに、上の記事ではドイツ語のテストは4週間後と言ってましたが、実は3週間後でした（、ってことを残り1週間で気づいて焦りました）。
しっかし、まだテストって終わってないんですよね。来年の1月の第3週にも期末試験があるのでそこに向けてまた勉強しなければなりません。
でも今回ブログ停止して勉強してて思ったんですけど、勉強ばっかりはつらいですね。僕にとってはブログは良いストレス発散になっていたみたいで（何かを創作する趣味はQOLを高めるのに高い効果を発揮すると考えるのは僕の自論）、勉強でかなりたまるストレスを発散するためにブログはやった方がよさそうです。
幸い、今回のテストであまり勉強しなくても意外と取れそうだなと分かったので、ブログに割く時間も作れそうです。
まあということで、これからはぼちぼち更新していきたいと思います。
