計算論

関西学院大学 理工学部 情報科学科
履修基準年度:2年
担当:巳波

講義目的

与えられた問題に対して効率の良いプログラムが作れるのか,本質的に作れないのか,またプログラムを開発したとき,それ以上の効率のよいものが作れるはずなのか,本質的に望めないものなのか,新しい暗号を開発したとき,それが解読困難なものか,即座に解読する方法があるのか,などの問いをどのように扱えばよいのだろうか.本講義は,このような問いを理論的に扱う計算量理論の基礎を理解することを目的とする.

講義内容

成績評価の方法

成績評価は定期試験とレポートにより行う.

参考・推薦図書

教科書は特に使用しない.
参考書として以下のものを挙げる.

受講上の注意

参考情報