【授業の目的】
計算機で解決が求められる様々な問題について，その問題が計算機にとって本質的に「難しい」のか「簡単」なのかを，計算時間やメモリ領域といった評価尺度に基づいて理論的に解析する計算量理論について講義する．特に，回路計算量理論に焦点あてる．
【授業の到達目標】
(1) 様々な計算量クラスの定義と意味を理解する．
(2) 計算量クラスに係る数学的命題の意味とその証明を理解する．
【授業概要（キーワード）】
回路計算量，チューリング機械，論理回路，
【科目の位置付け】
この授業は，知識情報科学，情報メディア科学の技術分野に関わる深い知識を修得し，情報科学の先端的分野に自在に応用できる能力を養うものである（情報科学専攻の学習・教育目標（A)）
【授業計画】
・授業の方法
講義形式で行う．講義の前半で計算モデルについて講義を行ない，講義の後半でいくつかの数学的な命題について講義する．
・日程
第1回:イントロダクション
第2回:論理関数の複雑さと漸近評価
第3回:数え上げ
第4回:素子削減法
第5回:論理回路
第6回:論理式
第7回:random restriction の導入
第8回:random restriction の応用
第9回:定数段論理回路と決定木
第10回:Switching Lemma の導入
第11回:Switching Lemma の応用
第12回:Discriminator の導入
第13回:Discriminator の応用
第14回:講義のまとめ
【学習の方法】
・受講のあり方
講義資料を参考に，提示される命題の意味とその証明が理解できるように努めること．
・授業時間外学習へのアドバイス
講義中の理解が正しいかを確認するため，講義資料などを参考に必ず復習すること．
【成績の評価】
・基準
計算量に関わる数学的な命題の意味を，本質的な誤解なく理解していることを合格の基準とする．
・方法
全講義終了後に提示されるレポートを100点満点で評価し，60点以上を合格とする．
【テキスト・参考書】
参考書：Stasys Jukna. Boolean Function Complexity - Advances and Frontiers. Algorithms and Combinatorics 27, Springer-Verlag Berlin Heidelberg, 2012.
【その他】
・学生へのメッセージ
数学的な命題の正しい理解に努めること．また，講義時間内に自分の理解をノートに記すことが望ましい．
・オフィス・アワー
曜日：金曜日
時間：16:00-17:00
場所：8号館2階 225室
|