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

教授　土井 洋, 教授　大塚 玲

１．授業のねらい・到達目標

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

２．到達目標

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

３．授業計画

[計算複雑性理論]
第1回 複雑さの測定
第2回 クラスP
第3回 クラスNP
第4回 NP完全性1
第5回 NP完全性2
第6回 他のNP完全問題
第7回 演習
第8回 中間テストと解説

[情報理論]
第9回 情報源と通信路のモデル
第10回 情報源符号化
第11回 通信路符号化
第12回 情報理論的安全性と計算量的安全性
第13回 情報理論的に安全な暗号技術I
第14回 情報理論的に安全な暗号技術II
第15回 最近の話題

４．教科書

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

５．参考書

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

６．関連科目

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

７．成績評価の方法

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