理工学部再編の関係もあってえらいことになっていて、 この授業は、理工学部数学科「応用数学I」・ 大学院理工学研究科数学専攻「応用数学特別講義I」・ 大学院理工学研究科理工学専攻情報学領域「情報数学特論」の合併講義である。 誰がどれくらい来るのかな、と思っていたが、 数学科の学生が多数、大学院生の情報系が数名、数学系が僅か、と言う感じ。 数学系の学生・院生が情報系の数学をどれくらい習っているかは大体判るが、 情報系の大学院生が学部時代にどれくらいのことを習っているのかが判らないので、 手探り状態である。 そもそもこっちもこの内容の授業の担当は初めてだし。 取り敢えずアンケートを書いてもらう。
授業内容の予定は、 情報理論・符号理論・暗号理論の入門までと、その土台となる基礎数理。 通しのテーマは「情報通信の数理とそれを支える数学」という感じ。 シラバスを作った時は、 始めのうちに数学の予備知識(有限体上の線型代数・有限体のGalois理論)を話して、 それから符号・暗号の話へ、と書いたけれども、 動機付けの点で弱いかな、と思い直して、 必要性が明らかになった所で数学の内容を入れていく方針に変更。 情報理論・符号理論・暗号理論だと、この順に代数的な準備が増える (情報理論は教養の微積・確率論くらい、符号理論はF_2上の線型代数、 暗号理論は初等整数論や素体でない有限体の話も必要になってくる) ので、この順に取り上げて、少しづつ代数的な準備を入れることにする。 いづれにせよ、本格的に講義するなら夫々で半期一コマくらい要るので、 本講義では全体を概観する程度(入門まで)ということにしたい。 「特論」の講義名が泣きますが。
初回は全体の概説。上述のような訳で次回から情報理論(情報源符号化)の話。
情報源符号化の話。ASCII codeやモールス符号(Morse code)を例に、 出現頻度(生起確率)まで考慮して定式化をする、 単純に順列組合せの数だけじゃないよ、と。 頻度の高いものは短くして、低いものは長くても良い。その方が得。 但し、長さが区々だと区切る場所の判断が生じて、 一意に復号出来るかどうかが問題になる。 という訳で、一意符号・瞬時符号の話。瞬時符号は語頭符号であること、 符号語木の話あたりまでで本日終了。
2回やってみて、やっぱりやり難いなぁ。 ここまで話した内容は、 情報系の学生さんだったら学部で習ってる程度のことだろうし、 でも数学系の人には初めてだろうし。 一方、その内容を数式で表して定式化したり処理していこうとすると、 数学系の人は馴染んでる(筈である／と想定されている)けれども、 情報系の人には馴れてなくて解り難いかも。 まぁその辺りを織り混ぜて程々に落としていくしかないかな。
朝一の授業と言うこともあり、学生さんの出足が鈍い。 人が揃うのを待ちつつ復習をぼちぼちとしていたら、時間を随分喰ってしまった。 いけませんなぁ。次回辺りは演習問題で手を動かしてもらおうかな。
復習の後は、瞬時符号に関するKraftの不等式。 これは符号語木を見れば一目瞭然ということで証明略。 次に一意符号だったら、ということでMcMillanの不等式。 瞬時符号より一意符号の方が真に条件が弱いのだが、 符号長リストに関する条件は同じというのが面白い。 だから一意符号があれば同じ符号長リストの瞬時符号が存在するんですね。 これは組合せ論的に数え上げて証明できますが、 同じことだけれど少々凝って母関数を作って示してみよう、と。 両方とも証明省略というのもあんまりなので、こちらの証明の機会に 「母関数を考える」という手法を紹介しよう、というのがむしろ目的。 判り難かったかもしれないけど、重要な考え方だから良いでしょう。 これで一意符号・瞬時符号の話は一段落。ここまでは生起確率とは関係ない話。
次に、瞬時符号という前提条件の下で、 生起確率を考慮して平均符号長を小さくしよう、という話に進み、 Huffman符号の紹介。 ここまでで時間切れ。もう少し進むつもりだったのに、いけませんなぁ。 情報源符号化の話に時間掛け過ぎ。少し急ごう。
Huffman符号の構成を復習してから、 2値情報源の場合は拡大情報源を考えるとHuffman圧縮が使えるってんで、 演習の時間を取ってみたが、思ったほど手の動きが進んでない様子。 始めに生起確率の順に並べておいても、 木の形は必ずしも端から順番に枝分かれする訳ではないのだが、 ここで誤認・即断し易いのか。
さて、n次の拡大情報源を考えてHuffman圧縮を掛けると、 nを大きくしたら幾らでも効率が上がるのか、という問に対して、 その情報源が本来内在的に持っている何がしかの量より効率が良くなるような 都合の良い話はないだろう、ということで、情報量を計る話。 演習に思いの外の時間が掛かったので、 エントロピーを定義する所までで時間切れになってしまった。 もう少し進むつもりだったのに、いけませんなぁ。