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