計算論

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

講義目的

与えられた問題に対して効率の良いプログラムが作れるのか，本質的に作れないのかという問いをどのように扱えばよいのだろうか．本講義は，このような問いを理論的に扱う計算量理論の基礎を理解することを目的とする．

講義内容

・ 問題とアルゴリズム、計算の複雑さ （１）
・ チューリングマシン （２, ３）
・ 計算可能性 （４～８）
・ 計算の複雑さ （９～13）
・ 先進的な話題 （14, 15）

成績評価の方法

定期試験

参考・推薦図書

ホップクロフト＆ウルマン『オートマトン 言語理論 計算論I, II（第２版）』（サイエンス社）

受講上の注意

「データ構造とアルゴリズム」，「最適化理論」などと密接に関係しているため，あわせて学ぶことが望ましい．