アルゴリズム基礎（前期2単位）

教授　土井 洋, 教授　大塚 玲

１．授業のねらい

前半は計算の複雑さと計算量的に困難な問題の考え方（計算複雑性理論）について学ぶ． 後半は情報源符号化と通信路符号化に基礎概念といくつかの符号化法ついて学ぶ． 次に情報理論的に安全な暗号技術について，モデル，証明法などを学ぶ． 授業では社会科学系の学生にも理解できる平易な説明を心掛けるが， 理系の学部卒程度の数学および情報科学の知識を前提とする．

２．到達目標

　・情報理論的に安全な暗号技術の特徴を理解する．
　・計算の複雑さや計算量的に困難な問題の考え方を理解する．

３．授業計画と開講形態

[計算複雑性理論]
第1回 複雑さの測定
　　　　<ランダウの記号, 計算可能関数>
第2回 クラスP
　　　　<決定性Turing機械, 多項式時間アルゴリズム, 帰着>
第3回 クラスNP
　　　　<非決定性Turing機械, 多項式時間検証装置, 言語のクラス>
第4回 NP完全性1
　　　　<充足可能性問題, Cook-Levinの定理>
第5回 NP完全性2
　　　　<NP完全, P vs NP問題>
第6回 他のNP完全問題
　　　　<3SATとハミルトン経路問題, 部分和問題のNP完全性>
第7回 演習
第8回 期末テストと解説

[情報理論]
第9回 情報源と通信路のモデル
　　　　<エントロピー，相互情報量>
第10回 情報源符号化
　　　　<情報源符号化定理とその証明，ハフマン符号>
第11回 通信路符号化
　　　　<通信路容量，通信路符号化定理とその証明，巡回符号>
第12回 情報理論的安全性と計算量的安全性
　　　　<バーナム暗号と安全性証明，ランプ型秘密分散法と安全性証明>
第13回 情報理論的に安全な暗号技術I
　　　　<A-codeと安全性証明，情報理論的に安全な電子署名>
第14回 情報理論的に安全な暗号技術II
第15回 最近の話題

原則として全回教室での対面のみの開催とする．

４．教科書

・Michael Sipser著, 太田和夫・田中圭介監訳 計算理論の基礎３ 複雑さの理論, 共立出版, 2008.

５．参考書

• 今井秀樹，情報理論 改訂2版，2019.

６．関連科目

暗号理論，暗号プロトコルと関連がある．

７．成績評価の方法

中間テストと期末テストにより評価する．