春学期・木曜3時限・3-426教室
本講義は理工学部数学科「応用数学I」・ 大学院理工学研究科理工学専攻情報学領域「情報数学特論」の合併講義である。
上智大学の学部シラバス内の本授業のページ [応用数学I |情報数学特論 ]
授業時のプロジェクタ資料を掲載する予定です。 各授業日の項から見て下さい。 但し、各授業中の前回の復習部分を含んでいるので、内容に重複があります。 印刷時には必要なページだけ印刷するなどして下さい。
情報をディジタル化して転送する際、如何に効率的に通信を行なうことができるか、 情報源符号化の基礎理論をまず紹介する。 次に通信途中で生じる誤りに正しく対処するための数理技術である 誤り訂正符号の基礎について解説する。 続いて情報化社会の安全を支える数理技術である 公開鍵暗号などの現代暗号論の基礎について概説を行なう。 代数幾何・整数論などの必要な予備知識についても適宜補いつつ講義を進める。
符号理論・暗号理論の基礎数理について、入門的に紹介する。 以下は大体の予定。
配ったプリント [page 0(pdf,18KB) |アンケート(pdf,9KB) ] ・プロジェクタ資料 [4/16授業時(pdf,46KB) |4/16印刷用(pdf,34KB) ]
概説: 情報通信と符号・暗号。
合併講義のため、受講生の予備知識を確認する簡単なアンケートを行なう。 上記の講義計画はそれによって変わりうる。
プロジェクタ資料 [4/23授業時(pdf,67KB) |4/23印刷用(pdf,50KB) ]
情報理論(情報源符号化)入門まで。 情報源符号の定式化。一意符号・瞬時符号。符号語木。
配ったプリント [演習(1)(pdf,11KB) ]・ プロジェクタ資料 [4/30授業時(pdf,82KB) |4/30印刷用(pdf,69KB) ]
情報理論(情報源符号化)入門まで。 瞬時符号の符号語木。Kraftの不等式・McMillanの不等式。 生起確率も考慮した符号の効率。Huffman符号。拡大情報源とその符号化。
全学休講日でお休み。
プロジェクタ資料 [5/14授業時(pdf,71KB) |5/14印刷用(pdf,58KB) ]
情報理論(情報源符号化)入門まで。 Huffman符号。拡大情報源の符号化。
情報量。エントロピー。平均符号長はエントロピーで下から押えられる。
配ったプリント [アンケート(pdf,6KB) ] ・プロジェクタ資料 [5/21授業時(pdf,85KB) |5/21印刷用(pdf,50KB) ]
情報理論(情報源符号化)入門まで。 Shannon-Fano符号。 Shannonの第1基本定理。情報量は伝えるのに必要な手間に比例する。
符号理論(誤り訂正符号)入門まで。誤り訂正符号とは。
プロジェクタ資料 [5/28授業時(pdf,56KB) |5/28印刷用(pdf,49KB) ]
符号理論(誤り訂正符号)入門まで。距離の公理。Hamming距離。 符号の最小距離と誤り訂正性能。符号の最小距離と誤り訂正性能。 Hammingの球充填上界(sphere-packing bound)と Gilbert-Varshamovの下界。
配ったプリント [page 1(レポート課題の例)(pdf,10KB) [page 2(レポート課題の例)(pdf,27KB) ]・ プロジェクタ資料 [6/4授業時(pdf,48KB) |6/4印刷用(pdf,48KB) ]
当日はプロジェクタ機器が不調で、 用意していたプロジェクタ資料が映せなかったが、 参考のためにここに掲げておく。
線型符号。有限体とその上の線型代数。線型符号の不変量。 線型符号の例: 多数決符号・パリティ検査符号。
配ったプリント [演習(2)(pdf,13KB) ]・プロジェクタ資料 [6/11授業時(pdf,67KB) |6/11印刷用(pdf,62KB) ]
線形符号の生成行列・パリティ検査行列による表示。 同値な符号。生成行列・パリティ検査行列の標準形。 線型符号の例: Hamming符号。
プロジェクタ資料 [6/18授業時(pdf,67KB) |6/18印刷用(pdf,55KB) ]
線型符号の例: Hamming符号。 符号の自己同型。巡回符号。
プロジェクタ資料 [6/25授業時(pdf,72KB) |6/25印刷用(pdf,71KB) ]
巡回符号。 代数の準備(有限体上の多項式環・中国式剰余定理・有限体のGalois理論)。 X^l-1∈F_q[X]の既約分解。
プロジェクタ資料 [7/2授業時(pdf,74KB) |7/2印刷用(pdf,67KB) ]
数論の準備(平方剰余・平方剰余の相互律)。 平方剰余符号。冪等生成元。
プロジェクタ資料 [7/9授業時(pdf,92KB) |7/9印刷用(pdf,91KB) ]
平方剰余符号(続き)。冪等生成元。平方剰余符号の平方根下界。 良い符号の例とその背後にある数理。
暗号理論入門まで。
配ったプリント [page 3(レポート課題の例)(pdf,34KB) [page 4(レポート課題の例)(pdf,27KB) ]・ プロジェクタ資料 [7/16授業時(pdf,97KB) |7/16印刷用(pdf,82KB) ]
暗号理論入門まで。 暗号でできること(秘密通信・認証・署名・鍵共有・秘密分散など)。 共通鍵(秘密鍵)暗号・公開鍵暗号。RSA暗号の原理。
配ったプリント [演習(3)(pdf,8KB) |アンケート(pdf,6KB) ]・ プロジェクタ資料 [7/23授業時(pdf,108KB) |7/23印刷用(pdf,93KB) ]
計算量について。素因数分解問題。離散対数問題。 Deffie-Hellman鍵共有方式。ElGamal暗号方式・疑似乱数の話。
期末試験を行なった。 [期末試験問題(pdf,29KB)]