トップ カリキュラム・授業 計算論



授業科目名 計算論
　 履修期 春   2単位   履修基準年度 2年
担当者 巳波　弘佳（MIWA HIROYOSHI）
授業目的 / Course Objectives
与えられた問題に対して効率の良いプログラムが作れるのか，そもそも本質的に作れないのかという問いをどのように扱えばよいのだろうか．本講義は，このような問いを理論的に扱う計算理論の基礎を理解することを目的とする．
到達目標 / Attainment Objectives

授業時間外の学習 (準備学習等について) / Study Required Outside of Class (Preparation etc.)
データ構造とアルゴリズム，最適化理論などと密接に関係しているため，あわせて学ぶことが望ましい．
授業計画 / Class Overall Plan
第１回　基礎的概念の整理
第２回　問題とアルゴリズム （１）
第３回　問題とアルゴリズム （２）
第４回　チューリングマシン（１）（定義）
第５回　チューリングマシン（２）（チューリングマシンによる問題とアルゴリズムのモデル化）
第６回　計算可能性（１）（認識可能性）
第７回　計算可能性（２）（認識可能性）
第８回　計算可能性（３）（判定可能性）
第９回　計算可能性（４）（判定可能性）
第10回　計算複雑性（１）（計算量の定義）
第11回　計算複雑性（２）（クラスPとクラスNP）
第12回　計算複雑性（３）（NP完全性）
第13回　計算複雑性（４）（様々な計算量クラス）
第14回　先進的な話題
第15回　演習
教科書 / Textbook(s)

参考文献 References Books
ホップクロフト＆ウルマン『オートマトン 言語理論 計算論I, II（第２版）』（サイエンス社）
授業方法 / Method of Instruction
講義方式
学生による授業評価の方法 / Course Evaluation by Students
全学統一様式による調査
成績評価 / Evaluation Criteria/Method
定期試験(Final examination)
定期試験の結果に基づく
備考 / Note

検索キーワード / Keywords
チューリングマシン/計算可能性/計算の複雑さ

ページトップへ ▲