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

教授　土井 洋, 教授　大塚 玲

１．授業のねらい

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

２．到達目標

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

３．授業計画と開講形態

開講形態は別途通知。
[情報理論]
第1回 情報源と通信路のモデル
第2回 情報源符号化
第3回 通信路符号化
第4回 情報理論的安全性と計算量的安全性
第5回 情報理論的に安全な暗号技術I
第6回 情報理論的に安全な暗号技術II
第7回 最近の話題

[計算複雑性理論]
第9回 複雑さの測定
第8回 クラスP
第10回 クラスNP
第11回 NP完全性1化
第12回 NP完全性2
第13回 他のNP完全問題
第14回 演習
第15回 期末テストと解説

全回教室での対面のみの開催とする．

４．教科書

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

５．参考書

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

６．関連科目

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

７．成績評価の方法

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