アルゴリズム論

講義資料

• 第 1 回 Turing 機械
• 第 2 回 Turing 機械のプログラミング
• 第 3 回 計算量理論
• 第 4 回 万能 Turing 機械
• 第 5 回 停止問題
• 第 6 回 線形加速定理、階層定理(2003.5.27 改訂、2003.6.3 三訂)
• 第 7 回 下限
• 第 8 回 非決定性(1),オートマトン
• 第 9 回 非決定性(2)、完全問題
• 第 10 回 NP完全問題

レポート

同じ問題を解く計算量の異なる二つのプログラムを書き、計算量を評価しなさい。 締切 2003 年 7 月 8 日

参考文献