京都大学 情報学研究科 知能情報学専攻 2023年8月実施 専門科目 S-4

Author

Isidore, 祭音Myyura

Description

以下ではすべて記憶のない定常情報源を考える。なお、解答には理由も明確に示すこと。

設問1

をアルファベットとし、各記号の生起確率が , で与えられる情報源を考える。 を変化させた時、この情報源のエントロピーの最大値と最小値を求めよ。

設問2

を正の定数とする。 をアルファベットとし、各記号の生起確率が次式で与えられる情報源を考える。

ただし、 とする。 を変化させた時、この情報源のエントロピーの最大値と最小値を求めよ。

設問3

をアルファベットとし、各記号の生起確率が である情報源を考える。 この情報源に対する 2 元ハフマン符号の平均長を求めよ。

設問4

を正整数とし、 とする。 をアルファベットとし、すべての記号の生起確率が である情報源を考える。 この情報源に対する 2 元ハフマン符号の平均長を求めよ。

設問5

次の通信路行列により定まる通信路の容量を求めよ。 なお、入力アルファベットのサイズは 2、出力アルファベットのサイズは 3 である。

設問6

次の通信路行列により定まる通信路の容量を とする。 なお、入力アルファベットのサイズは 、出力アルファベットのサイズは である。

すると、 に関する関数 を用いて、 と書ける。 を求めよ。

Kai

設問1

By solving the following equation

we have . Also,

Thus the maximum of is , the minimum of is .

設問2

By using the method of Lagrange multiplier, we have

Then, by solving the following equations,

we have

hence is maximized when and the maximum of entropy is

By Q1 we know that the entropy is minimized when or .

If , then the entropy is minimized when

and

If , then and the minimum is .

設問3

設問4

設問5

, where could be calculated from . Then, we construct the function

Get the maximum when

設問6