シラバス参照
|
シラバス参照
|
| 講義概要/Course Information |
| 科目基礎情報/General Information |
| 授業科目名 /Course title (Japanese) |
計算理論 | ||
|---|---|---|---|
| 英文授業科目名 /Course title (English) |
Theory of Computing | ||
| 科目番号 /Code |
INS603c INS603d | ||
| 開講年度 /Academic year |
2020年度 | 開講年次 /Year offered |
3 |
| 開講学期 /Semester(s) offered |
後学期 | 開講コース・課程 /Faculty offering the course |
情報理工学域 |
| 授業の方法 /Teaching method |
講義 | 単位数 /Credits |
2 |
| 科目区分 /Category |
専門科目 | ||
| 開講学科・専攻 /Cluster/Department |
Ⅰ類 | ||
| 担当教員名 /Lecturer(s) |
岡本（吉）・垂井 | ||
| 居室 /Office |
西4-206 (岡本)，東3-824 (垂井) | ||
| 公開E-Mail |
okamotoy@uec.ac.jp, juntarui@uec.ac.jp | ||
| 授業関連Webページ /Course website |
前半は http://dopal.cs.uec.ac.jp/okamotoy/lect/2020/comp/ | ||
| 更新日 /Last updated |
2020/03/06 16:13:19 | 更新状況 /Update status |
公開中 /now open to public |
| 講義情報/Course Description |
| 主題および 達成目標 /Topic and goals |
本講義では計算機科学理論のうち，「計算可能性の理論」および｢計算量理論｣と呼ばれる分野を扱う．計算可能性の理論においては，計算・アルゴリズムとは何かについて考え，実際に計算不可能な問題が存在することを示す．計算量理論においては，問題を解くために必要な計算時間や記憶容量などを分析する．このような計算可能性の理論，計算量理論の基本的考え方について理解をしてもらうことが本講義の目標である． |
|---|---|
| 前もって履修 しておくべき科目 /Prerequisites |
離散数学 |
| 前もって履修しておくこ とが望ましい科目 /Recommended prerequisites and preparation |
形式言語理論 (オートマトン理論) |
| 教科書等 /Course textbooks and materials |
教科書：なし 参考書：笠井琢美、戸田誠之助「計算の理論」共立出版 渡辺治「計算可能性・計算の複雑さ入門」近代科学社 M. Sipser「計算理論の基礎」共立出版 鹿島亮「C言語による計算の理論」サイエンス社 T. Stuart「アンダースタンディング コンピュテーション」 など |
| 授業内容と その進め方 /Course outline and weekly schedule |
(a)授業内容 第１回：計算とは何か？（岡本） 第２回：計算モデル（岡本） 第３回：チャーチ・チューリングの定立（岡本） 第４回：コード化（岡本） 第５回：計算可能性（岡本） 第６回：停止性問題（岡本） 第７回：再帰定理（岡本） 第８回：前半のまとめ（岡本） 第９回：時間計算量，領域計算量，計算量のクラス（垂井） 第１０回：クラスＰ，クラスＮＰ，Ｐ vs ＮＰ予想（垂井） 第１１回：多項式時間計算可能な帰着，ＮＰ完全性（垂井） 第１２回：ＮＰ完全問題（垂井） 第１３回：ＮＰ完全性の証明（垂井） 第１４回：計算資源としてのランダムネス（垂井） 第１５回：近似計算，多項式時間計算の近似の限界（垂井） (b) 授業の進め方 本講義の前半（第１回～第８回，担当：岡本）では，計算可能性の理論について，計算可能／計算不可能とはどのようなことか議論し，実際に計算不可能な問題が存在することを示す．後半（第９回～第１５回，担当：垂井）では，計算量理論について，応用上も重要なＮＰ完全性に重点を置いて説明する． |
| 実務経験を活かした 授業内容 (実務経験内容も含む) /Course content utilizing practical experience |
|
| 授業時間外の学習 （予習・復習等） /Preparation and review outside class |
授業中に十分理解できなかったと思われる部分は，ノートや参考書等で理解しておくことが望ましい． |
| 成績評価方法 および評価基準 （最低達成基準を含む） /Evaluation and grading |
小テストおよびレポートの結果に基づいて評価を行なう．計算可能性および計算量理論の基本的概念について理解することが合格の最低条件である． |
| オフィスアワー： 授業相談 /Office hours |
岡本：メールにてアポイントメント． 垂井：授業の後またはメールで時間相談してください． |
| 学生へのメッセージ /Message for students |
なし |
| その他 /Others |
なし |
| キーワード /Keyword(s) |
計算可能性，計算量，ＮＰ完全性，チューリング機械 |