計算論 2018 サポートページ

担当: 池口 徹 (東京理科大学 工学部 情報工学科 教授)
TA: 藤田実沙 (東京理科大学大学院 工学研究科 経営工学専攻 D2)
時間: 前期後半，火曜日，2,3限＠2A1教室

概要:

計算とは何か， 計算できるとは何か， 計算できないとは何か， 計算の複雑さについて学びます．

資料 (教科書・参考書)／ 評価 ／ コメントに対する返信

授業予定: 変更する可能性が十分あります．必ず講義前に確認をしてください．

• 6月12日(火) (第01週):

  • 休講

• 6月19日(火) (第02週):

  • イントロダクション
  • 講義の内容
  • 講義の進め方，
  • 内容，評価方法などについて．
  • 有限オートマトンとは
  • 有限オートマトンの正式な定義
  • コメント用紙に対する 返信

• 6月26日(火) (第03週):

  • 有限オートマトンによる計算の正式な定義

• 7月03日(火) (第04週):

  • チューリングマシン
  • 万能チューリングマシン

• 7月10日(火) (第05週):

  • グラフ・アルゴリズムと計算量(1)

• 7月17日(火) (第06週):

  • グラフ・アルゴリズムと計算量(2)

• 7月24日(火) (第07週):

  • NP，NP完全，P対NP
  • 計算の複雑さとその応用
  • この講義のまとめ