情報理論 III
Information Theory III

---

講義内容

本講義では，情報伝達と計算の基礎理論である，次の二つの話題について解説する。
(1) 情報理論には多様な側面があるが，通信路の符号化及び符号理論について， その基礎理論から最新の理論展開，応用までを解説する。
(2) 「計算機で問題を解くときの，問題の難しさをはかる尺度はあるのだろうか」という問題意識のもとに，計算複雑さの理論について，基本的でかつ重要であるNP完全性を中心に説明する。

　　(1) 通信路符号化・符号理論
　　　1. 通信路符号化の概要 (背景, 意義, 応用例)
　　　2. ブロック符号と畳み込み符号 (ハミング符号, 符号化器, 復号器)
　　　3. 線形符号の諸性質 (最小距離, 誤り制御特性)
　　　4. 各種の復号法について (トレリス線図, ビタビ復号法, 準最尤復号法)

　　(2) 計算複雑さ
　　　1. 計算複雑さの定義と諸性質
　　　2. NP完全性 (Cookの定理, 還元による証明法)
　　　3. 他のクラスの完全性 (PSPACE完全性など)
　　　4. その他の話題 (多項式時間階層, 確率アルゴリズムなど)

教科書

　　とくに指定しない

参考書

１.S.Lin and D.J.Costello, Jr.: Erroro Control Coding: Fundamentals and Applications, Prentice-Hall, 1983.
２. J.E.Hopcroft and J.D.Ullman: Introduction to Automata Theory,Languages, and　　 Computation, Addison-Wesley, 1979.
　(邦訳 - J.ホップクロフト, J.ウルマン著, 野崎, 高橋, 町田, 山崎訳:オートマトン 言語理論 計算論II, サイエンス社, 1986.)

前提とする知識(必ずしも先修条件ではない)

　　解析学 (基礎数学II)
　　アルゴリズムとデータ構造 (アルゴリズム概論)
　　形式言語理論, 計算可能性 (計算理論I)