計算論

授業目的
与えられた問題に対して効率の良いプログラムが作れるのか,そもそも本質的に作れないのかという問いをどのように扱えばよいのだろうか.本講義は,このような問いを理論的に扱う計算理論の基礎を理解することを目的とする.
到達目標
計算モデル,計算可能性,計算の複雑さ(計算量)について,基本的な概念を理解する.
授業計画
第1回ガイダンス,基礎的概念
【授業外学修】別途指示する演習課題を解くこと.
第2回チューリングマシン(1)(定義と性質)
【授業外学修】別途指示する演習課題を解くこと.
第3回チューリングマシン(2)(非決定性チューリングマシン)
【授業外学修】別途指示する演習課題を解くこと.
第4回計算可能性(1)(認識可能性)
【授業外学修】別途指示する演習課題を解くこと.
第5回計算可能性(2)(判定可能性)
【授業外学修】別途指示する演習課題を解くこと.
第6回計算複雑性(1)(計算量の定義)
【授業外学修】別途指示する演習課題を解くこと.
第7回計算複雑性(2)(クラスPとクラスNP)
【授業外学修】別途指示する演習課題を解くこと.
第8回計算複雑性(3)(帰着)
【授業外学修】別途指示する演習課題を解くこと.
第9回計算複雑性(4)(NP完全性)
【授業外学修】別途指示する演習課題を解くこと.
第10回計算複雑性(5)(領域量,様々な計算量クラス)
【授業外学修】別途指示する演習課題を解くこと.
第11回確率アルゴリズム
【授業外学修】別途指示する演習課題を解くこと.
第12回近似アルゴリズム(1)
【授業外学修】別途指示する演習課題を解くこと.
第13回近似アルゴリズム(2)
【授業外学修】別途指示する演習課題を解くこと.
第14回先進的な話題,総合演習
【授業外学修】別途指示する演習課題およびこれまでの演習課題で残したものを解くこと.
【授業外学修】離散数理,データ構造とアルゴリズム,グラフ・ネットワーク理論,最適化理論,数理計画法実習を履修していることが望ましい.
授業中に適宜指示する演習課題に取り組むこと.
**こちらの内容は2023年4月10日を基準としたものです.最新のシラバス情報,詳細は大学提供のシラバス情報照会ページシラバス情報照会ページで確認してください**